home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 22 gnu / 22-gnu.zip / gnugrep.zip / kwset.c < prev    next >
C/C++ Source or Header  |  1993-05-02  |  21KB  |  806 lines
  1. /* kwset.c - search for any of a set of keywords.
  2.    Copyright 1989 Free Software Foundation
  3.           Written August 1989 by Mike Haertel.
  4.  
  5.    This program is free software; you can redistribute it and/or modify
  6.    it under the terms of the GNU General Public License as published by
  7.    the Free Software Foundation; either version 1, or (at your option)
  8.    any later version.
  9.  
  10.    This program is distributed in the hope that it will be useful,
  11.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13.    GNU General Public License for more details.
  14.  
  15.    You should have received a copy of the GNU General Public License
  16.    along with this program; if not, write to the Free Software
  17.    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18.  
  19.    The author may be reached (Email) at the address mike@ai.mit.edu,
  20.    or (US mail) as Mike Haertel c/o Free Software Foundation. */
  21.  
  22. /* The algorithm implemented by these routines bears a startling resemblence
  23.    to one discovered by Beate Commentz-Walter, although it is not identical.
  24.    See "A String Matching Algorithm Fast on the Average," Technical Report,
  25.    IBM-Germany, Scientific Center Heidelberg, Tiergartenstrasse 15, D-6900
  26.    Heidelberg, Germany.  See also Aho, A.V., and M. Corasick, "Efficient
  27.    String Matching:  An Aid to Bibliographic Search," CACM June 1975,
  28.    Vol. 18, No. 6, which describes the failure function used below. */
  29.  
  30.  
  31. #ifdef STDC_HEADERS
  32. #include <limits.h>
  33. #include <stdlib.h>
  34. #else
  35. #define INT_MAX 2147483647
  36. #define UCHAR_MAX 255
  37. #ifdef __STDC__
  38. #include <stddef.h>
  39. #else
  40. #include <sys/types.h>
  41. #endif
  42. extern char *malloc();
  43. extern void free();
  44. #endif
  45.  
  46. #ifdef HAVE_MEMCHR
  47. #include <string.h>
  48. #ifdef NEED_MEMORY_H
  49. #include <memory.h>
  50. #endif
  51. #else
  52. #ifdef __STDC__
  53. extern void *memchr();
  54. #else
  55. extern char *memchr();
  56. #endif
  57. #endif
  58.  
  59. #ifdef GREP
  60. extern char *xmalloc();
  61. #define malloc xmalloc
  62. #endif
  63.  
  64. #include "kwset.h"
  65. #include "obstack.h"
  66.  
  67. #define NCHAR (UCHAR_MAX + 1)
  68. #define obstack_chunk_alloc malloc
  69. #define obstack_chunk_free free
  70.  
  71. /* Balanced tree of edges and labels leaving a given trie node. */
  72. struct tree
  73. {
  74.   struct tree *llink;        /* Left link; MUST be first field. */
  75.   struct tree *rlink;        /* Right link (to larger labels). */
  76.   struct trie *trie;        /* Trie node pointed to by this edge. */
  77.   unsigned char label;        /* Label on this edge. */
  78.   char balance;            /* Difference in depths of subtrees. */
  79. };
  80.  
  81. /* Node of a trie representing a set of reversed keywords. */
  82. struct trie
  83. {
  84.   unsigned int accepting;    /* Word index of accepted word, or zero. */
  85.   struct tree *links;        /* Tree of edges leaving this node. */
  86.   struct trie *parent;        /* Parent of this node. */
  87.   struct trie *next;        /* List of all trie nodes in level order. */
  88.   struct trie *fail;        /* Aho-Corasick failure function. */
  89.   int depth;            /* Depth of this node from the root. */
  90.   int shift;            /* Shift function for search failures. */
  91.   int maxshift;            /* Max shift of self and descendents. */
  92. };
  93.  
  94. /* Structure returned opaquely to the caller, containing everything. */
  95. struct kwset
  96. {
  97.   struct obstack obstack;    /* Obstack for node allocation. */
  98.   int words;            /* Number of words in the trie. */
  99.   struct trie *trie;        /* The trie itself. */
  100.   int mind;            /* Minimum depth of an accepting node. */
  101.   int maxd;            /* Maximum depth of any node. */
  102.   unsigned char delta[NCHAR];    /* Delta table for rapid search. */
  103.   struct trie *next[NCHAR];    /* Table of children of the root. */
  104.   char *target;            /* Target string if there's only one. */
  105.   int mind2;            /* Used in Boyer-Moore search for one string. */
  106.   char *trans;            /* Character translation table. */
  107. };
  108.  
  109. /* Allocate and initialize a keyword set object, returning an opaque
  110.    pointer to it.  Return NULL if memory is not available. */
  111. kwset_t
  112. kwsalloc(trans)
  113.      char *trans;
  114. {
  115.   struct kwset *kwset;
  116.  
  117.   kwset = (struct kwset *) malloc(sizeof (struct kwset));
  118.   if (!kwset)
  119.     return 0;
  120.  
  121.   obstack_init(&kwset->obstack);
  122.   kwset->words = 0;
  123.   kwset->trie
  124.     = (struct trie *) obstack_alloc(&kwset->obstack, sizeof (struct trie));
  125.   if (!kwset->trie)
  126.     {
  127.       kwsfree((kwset_t) kwset);
  128.       return 0;
  129.     }
  130.   kwset->trie->accepting = 0;
  131.   kwset->trie->links = 0;
  132.   kwset->trie->parent = 0;
  133.   kwset->trie->next = 0;
  134.   kwset->trie->fail = 0;
  135.   kwset->trie->depth = 0;
  136.   kwset->trie->shift = 0;
  137.   kwset->mind = INT_MAX;
  138.   kwset->maxd = -1;
  139.   kwset->target = 0;
  140.   kwset->trans = trans;
  141.  
  142.   return (kwset_t) kwset;
  143. }
  144.  
  145. /* Add the given string to the contents of the keyword set.  Return NULL
  146.    for success, an error message otherwise. */
  147. char *
  148. kwsincr(kws, text, len)
  149.      kwset_t kws;
  150.      char *text;
  151.      size_t len;
  152. {
  153.   struct kwset *kwset;
  154.   register struct trie *trie;
  155.   register unsigned char label;
  156.   register struct tree *link;
  157.   register int depth;
  158.   struct tree *links[12];
  159.   enum { L, R } dirs[12];
  160.   struct tree *t, *r, *l, *rl, *lr;
  161.  
  162.   kwset = (struct kwset *) kws;
  163.   trie = kwset->trie;
  164.   text += len;
  165.  
  166.   /* Descend the trie (built of reversed keywords) character-by-character,
  167.      installing new nodes when necessary. */
  168.   while (len--)
  169.     {
  170.       label = kwset->trans ? kwset->trans[(unsigned char) *--text] : *--text;
  171.  
  172.       /* Descend the tree of outgoing links for this trie node,
  173.      looking for the current character and keeping track
  174.      of the path followed. */
  175.       link = trie->links;
  176.       links[0] = (struct tree *) &trie->links;
  177.       dirs[0] = L;
  178.       depth = 1;
  179.  
  180.       while (link && label != link->label)
  181.     {
  182.       links[depth] = link;
  183.       if (label < link->label)
  184.         dirs[depth++] = L, link = link->llink;
  185.       else
  186.         dirs[depth++] = R, link = link->rlink;
  187.     }
  188.  
  189.       /* The current character doesn't have an outgoing link at
  190.      this trie node, so build a new trie node and install
  191.      a link in the current trie node's tree. */
  192.       if (!link)
  193.     {
  194.       link = (struct tree *) obstack_alloc(&kwset->obstack,
  195.                            sizeof (struct tree));
  196.       if (!link)
  197.         return "memory exhausted";
  198.       link->llink = 0;
  199.       link->rlink = 0;
  200.       link->trie = (struct trie *) obstack_alloc(&kwset->obstack,
  201.                              sizeof (struct trie));
  202.       if (!link->trie)
  203.         return "memory exhausted";
  204.       link->trie->accepting = 0;
  205.       link->trie->links = 0;
  206.       link->trie->parent = trie;
  207.       link->trie->next = 0;
  208.       link->trie->fail = 0;
  209.       link->trie->depth = trie->depth + 1;
  210.       link->trie->shift = 0;
  211.       link->label = label;
  212.       link->balance = 0;
  213.  
  214.       /* Install the new tree node in its parent. */
  215.       if (dirs[--depth] == L)
  216.         links[depth]->llink = link;
  217.       else
  218.         links[depth]->rlink = link;
  219.  
  220.       /* Back up the tree fixing the balance flags. */
  221.       while (depth && !links[depth]->balance)
  222.         {
  223.           if (dirs[depth] == L)
  224.         --links[depth]->balance;
  225.           else
  226.         ++links[depth]->balance;
  227.           --depth;
  228.         }
  229.  
  230.       /* Rebalance the tree by pointer rotations if necessary. */
  231.       if (depth && ((dirs[depth] == L && --links[depth]->balance)
  232.             || (dirs[depth] == R && ++links[depth]->balance)))
  233.         {
  234.           switch (links[depth]->balance)
  235.         {
  236.         case (char) -2:
  237.           switch (dirs[depth + 1])
  238.             {
  239.             case L:
  240.               r = links[depth], t = r->llink, rl = t->rlink;
  241.               t->rlink = r, r->llink = rl;
  242.               t->balance = r->balance = 0;
  243.               break;
  244.             case R:
  245.               r = links[depth], l = r->llink, t = l->rlink;
  246.               rl = t->rlink, lr = t->llink;
  247.               t->llink = l, l->rlink = lr, t->rlink = r, r->llink = rl;
  248.               l->balance = t->balance != 1 ? 0 : -1;
  249.               r->balance = t->balance != (char) -1 ? 0 : 1;
  250.               t->balance = 0;
  251.               break;
  252.             }
  253.           break;
  254.         case 2:
  255.           switch (dirs[depth + 1])
  256.             {
  257.             case R:
  258.               l = links[depth], t = l->rlink, lr = t->llink;
  259.               t->llink = l, l->rlink = lr;
  260.               t->balance = l->balance = 0;
  261.               break;
  262.             case L:
  263.               l = links[depth], r = l->rlink, t = r->llink;
  264.               lr = t->llink, rl = t->rlink;
  265.               t->llink = l, l->rlink = lr, t->rlink = r, r->llink = rl;
  266.               l->balance = t->balance != 1 ? 0 : -1;
  267.               r->balance = t->balance != (char) -1 ? 0 : 1;
  268.               t->balance = 0;
  269.               break;
  270.             }
  271.           break;
  272.         }
  273.  
  274.           if (dirs[depth - 1] == L)
  275.         links[depth - 1]->llink = t;
  276.           else
  277.         links[depth - 1]->rlink = t;
  278.         }
  279.     }
  280.  
  281.       trie = link->trie;
  282.     }
  283.  
  284.   /* Mark the node we finally reached as accepting, encoding the
  285.      index number of this word in the keyword set so far. */
  286.   if (!trie->accepting)
  287.     trie->accepting = 1 + 2 * kwset->words;
  288.   ++kwset->words;
  289.  
  290.   /* Keep track of the longest and shortest string of the keyword set. */
  291.   if (trie->depth < kwset->mind)
  292.     kwset->mind = trie->depth;
  293.   if (trie->depth > kwset->maxd)
  294.     kwset->maxd = trie->depth;
  295.  
  296.   return 0;
  297. }
  298.  
  299. /* Enqueue the trie nodes referenced from the given tree in the
  300.    given queue. */
  301. static void
  302. enqueue(tree, last)
  303.      struct tree *tree;
  304.      struct trie **last;
  305. {
  306.   if (!tree)
  307.     return;
  308.   enqueue(tree->llink, last);
  309.   enqueue(tree->rlink, last);
  310.   (*last) = (*last)->next = tree->trie;
  311. }
  312.  
  313. /* Compute the Aho-Corasick failure function for the trie nodes referenced
  314.    from the given tree, given the failure function for their parent as
  315.    well as a last resort failure node. */
  316. static void
  317. treefails(tree, fail, recourse)
  318.      register struct tree *tree;
  319.      struct trie *fail;
  320.      struct trie *recourse;
  321. {
  322.   register struct tree *link;
  323.  
  324.   if (!tree)
  325.     return;
  326.  
  327.   treefails(tree->llink, fail, recourse);
  328.   treefails(tree->rlink, fail, recourse);
  329.  
  330.   /* Find, in the chain of fails going back to the root, the first
  331.      node that has a descendent on the current label. */
  332.   while (fail)
  333.     {
  334.       link = fail->links;
  335.       while (link && tree->label != link->label)
  336.     if (tree->label < link->label)
  337.       link = link->llink;
  338.     else
  339.       link = link->rlink;
  340.       if (link)
  341.     {
  342.       tree->trie->fail = link->trie;
  343.       return;
  344.     }
  345.       fail = fail->fail;
  346.     }
  347.  
  348.   tree->trie->fail = recourse;
  349. }
  350.  
  351. /* Set delta entries for the links of the given tree such that
  352.    the preexisting delta value is larger than the current depth. */
  353. static void
  354. treedelta(tree, depth, delta)
  355.      register struct tree *tree;
  356.      register unsigned int depth;
  357.      unsigned char delta[];
  358. {
  359.   if (!tree)
  360.     return;
  361.   treedelta(tree->llink, depth, delta);
  362.   treedelta(tree->rlink, depth, delta);
  363.   if (depth < delta[tree->label])
  364.     delta[tree->label] = depth;
  365. }
  366.  
  367. /* Return true if A has every label in B. */
  368. static int
  369. hasevery(a, b)
  370.      register struct tree *a;
  371.      register struct tree *b;
  372. {
  373.   if (!b)
  374.     return 1;
  375.   if (!hasevery(a, b->llink))
  376.     return 0;
  377.   if (!hasevery(a, b->rlink))
  378.     return 0;
  379.   while (a && b->label != a->label)
  380.     if (b->label < a->label)
  381.       a = a->llink;
  382.     else
  383.       a = a->rlink;
  384.   return !!a;
  385. }
  386.  
  387. /* Compute a vector, indexed by character code, of the trie nodes
  388.    referenced from the given tree. */
  389. static void
  390. treenext(tree, next)
  391.      struct tree *tree;
  392.      struct trie *next[];
  393. {
  394.   if (!tree)
  395.     return;
  396.   treenext(tree->llink, next);
  397.   treenext(tree->rlink, next);
  398.   next[tree->label] = tree->trie;
  399. }
  400.  
  401. /* Compute the shift for each trie node, as well as the delta
  402.    table and next cache for the given keyword set. */
  403. char *
  404. kwsprep(kws)
  405.      kwset_t kws;
  406. {
  407.   register struct kwset *kwset;
  408.   register int i;
  409.   register struct trie *curr, *fail;
  410.   register char *trans;
  411.   unsigned char delta[NCHAR];
  412.   struct trie *last, *next[NCHAR];
  413.  
  414.   kwset = (struct kwset *) kws;
  415.  
  416.   /* Initial values for the delta table; will be changed later.  The
  417.      delta entry for a given character is the smallest depth of any
  418.      node at which an outgoing edge is labeled by that character. */
  419.   if (kwset->mind < 256)
  420.     for (i = 0; i < NCHAR; ++i)
  421.       delta[i] = kwset->mind;
  422.   else
  423.     for (i = 0; i < NCHAR; ++i)
  424.       delta[i] = 255;
  425.  
  426.   /* Check if we can use the simple boyer-moore algorithm, instead
  427.      of the hairy commentz-walter algorithm. */
  428.   if (kwset->words == 1 && kwset->trans == 0)
  429.     {
  430.       /* Looking for just one string.  Extract it from the trie. */
  431.       kwset->target = obstack_alloc(&kwset->obstack, kwset->mind);
  432.       for (i = kwset->mind - 1, curr = kwset->trie; i >= 0; --i)
  433.     {
  434.       kwset->target[i] = curr->links->label;
  435.       curr = curr->links->trie;
  436.     }
  437.       /* Build the Boyer Moore delta.  Boy that's easy compared to CW. */
  438.       for (i = 0; i < kwset->mind; ++i)
  439.     delta[(unsigned char) kwset->target[i]] = kwset->mind - (i + 1);
  440.       kwset->mind2 = kwset->mind;
  441.       /* Find the minimal delta2 shift that we might make after
  442.      a backwards match has failed. */
  443.       for (i = 0; i < kwset->mind - 1; ++i)
  444.     if (kwset->target[i] == kwset->target[kwset->mind - 1])
  445.       kwset->mind2 = kwset->mind - (i + 1);
  446.     }
  447.   else
  448.     {
  449.       /* Traverse the nodes of the trie in level order, simultaneously
  450.      computing the delta table, failure function, and shift function. */
  451.       for (curr = last = kwset->trie; curr; curr = curr->next)
  452.     {
  453.       /* Enqueue the immediate descendents in the level order queue. */
  454.       enqueue(curr->links, &last);
  455.  
  456.       curr->shift = kwset->mind;
  457.       curr->maxshift = kwset->mind;
  458.  
  459.       /* Update the delta table for the descendents of this node. */
  460.       treedelta(curr->links, curr->depth, delta);
  461.  
  462.       /* Compute the failure function for the decendents of this node. */
  463.       treefails(curr->links, curr->fail, kwset->trie);
  464.  
  465.       /* Update the shifts at each node in the current node's chain
  466.          of fails back to the root. */
  467.       for (fail = curr->fail; fail; fail = fail->fail)
  468.         {
  469.           /* If the current node has some outgoing edge that the fail
  470.          doesn't, then the shift at the fail should be no larger
  471.          than the difference of their depths. */
  472.           if (!hasevery(fail->links, curr->links))
  473.         if (curr->depth - fail->depth < fail->shift)
  474.           fail->shift = curr->depth - fail->depth;
  475.  
  476.           /* If the current node is accepting then the shift at the
  477.          fail and its descendents should be no larger than the
  478.          difference of their depths. */
  479.           if (curr->accepting && fail->maxshift > curr->depth - fail->depth)
  480.         fail->maxshift = curr->depth - fail->depth;
  481.         }
  482.     }
  483.  
  484.       /* Traverse the trie in level order again, fixing up all nodes whose
  485.      shift exceeds their inherited maxshift. */
  486.       for (curr = kwset->trie->next; curr; curr = curr->next)
  487.     {
  488.       if (curr->maxshift > curr->parent->maxshift)
  489.         curr->maxshift = curr->parent->maxshift;
  490.       if (curr->shift > curr->maxshift)
  491.         curr->shift = curr->maxshift;
  492.     }
  493.  
  494.       /* Create a vector, indexed by character code, of the outgoing links
  495.      from the root node. */
  496.       for (i = 0; i < NCHAR; ++i)
  497.     next[i] = 0;
  498.       treenext(kwset->trie->links, next);
  499.  
  500.       if ((trans = kwset->trans) != 0)
  501.     for (i = 0; i < NCHAR; ++i)
  502.       kwset->next[i] = next[(unsigned char) trans[i]];
  503.       else
  504.     for (i = 0; i < NCHAR; ++i)
  505.       kwset->next[i] = next[i];
  506.     }
  507.  
  508.   /* Fix things up for any translation table. */
  509.   if ((trans = kwset->trans) != 0)
  510.     for (i = 0; i < NCHAR; ++i)
  511.       kwset->delta[i] = delta[(unsigned char) trans[i]];
  512.   else
  513.     for (i = 0; i < NCHAR; ++i)
  514.       kwset->delta[i] = delta[i];
  515.  
  516.   return 0;
  517. }
  518.  
  519. #define U(C) ((unsigned char) (C))
  520.  
  521. /* Fast boyer-moore search. */
  522. static char *
  523. bmexec(kws, text, size)
  524.      kwset_t kws;
  525.      char *text;
  526.      size_t size;
  527. {
  528.   struct kwset *kwset;
  529.   register unsigned char *d1;
  530.   register char *ep, *sp, *tp;
  531.   register int d, gc, i, len, md2;
  532.  
  533.   kwset = (struct kwset *) kws;
  534.   len = kwset->mind;
  535.  
  536.   if (len == 0)
  537.     return text;
  538.   if (len > size)
  539.     return 0;
  540.   if (len == 1)
  541.     return memchr(text, kwset->target[0], size);
  542.  
  543.   d1 = kwset->delta;
  544.   sp = kwset->target + len;
  545.   gc = U(sp[-2]);
  546.   md2 = kwset->mind2;
  547.   tp = text + len;
  548.  
  549.   /* Significance of 12: 1 (initial offset) + 10 (skip loop) + 1 (md2). */
  550.   if (size > 12 * len)
  551.     /* 11 is not a bug, the initial offset happens only once. */
  552.     for (ep = text + size - 11 * len;;)
  553.       {
  554.     while (tp <= ep)
  555.       {
  556.         d = d1[U(tp[-1])], tp += d;
  557.         d = d1[U(tp[-1])], tp += d;
  558.         if (d == 0)
  559.           goto found;
  560.         d = d1[U(tp[-1])], tp += d;
  561.         d = d1[U(tp[-1])], tp += d;
  562.         d = d1[U(tp[-1])], tp += d;
  563.         if (d == 0)
  564.           goto found;
  565.         d = d1[U(tp[-1])], tp += d;
  566.         d = d1[U(tp[-1])], tp += d;
  567.         d = d1[U(tp[-1])], tp += d;
  568.         if (d == 0)
  569.           goto found;
  570.         d = d1[U(tp[-1])], tp += d;
  571.         d = d1[U(tp[-1])], tp += d;
  572.       }
  573.     break;
  574.       found:
  575.     if (U(tp[-2]) == gc)
  576.       {
  577.         for (i = 3; i <= len && U(tp[-i]) == U(sp[-i]); ++i)
  578.           ;
  579.         if (i > len)
  580.           return tp - len;
  581.       }
  582.     tp += md2;
  583.       }
  584.  
  585.   /* Now we have only a few characters left to search.  We
  586.      carefully avoid ever producing an out-of-bounds pointer. */
  587.   ep = text + size;
  588.   d = d1[U(tp[-1])];
  589.   while (d <= ep - tp)
  590.     {
  591.       d = d1[U((tp += d)[-1])];
  592.       if (d != 0)
  593.     continue;
  594.       if (tp[-2] == gc)
  595.     {
  596.       for (i = 3; i <= len && U(tp[-i]) == U(sp[-i]); ++i)
  597.         ;
  598.       if (i > len)
  599.         return tp - len;
  600.     }
  601.       d = md2;
  602.     }
  603.  
  604.   return 0;
  605. }
  606.  
  607. /* Hairy multiple string search. */
  608. static char *
  609. cwexec(kws, text, len, kwsmatch)
  610.      kwset_t kws;
  611.      char *text;
  612.      size_t len;
  613.      struct kwsmatch *kwsmatch;
  614. {
  615.   struct kwset *kwset;
  616.   struct trie **next, *trie, *accept;
  617.   char *beg, *lim, *mch, *lmch;
  618.   register unsigned char c, *delta;
  619.   register int d;
  620.   register char *end, *qlim;
  621.   register struct tree *tree;
  622.   register char *trans;
  623.  
  624.   /* Initialize register copies and look for easy ways out. */
  625.   kwset = (struct kwset *) kws;
  626.   if (len < kwset->mind)
  627.     return 0;
  628.   next = kwset->next;
  629.   delta = kwset->delta;
  630.   trans = kwset->trans;
  631.   lim = text + len;
  632.   end = text;
  633.   if ((d = kwset->mind) != 0)
  634.     mch = 0;
  635.   else
  636.     {
  637.       mch = text, accept = kwset->trie;
  638.       goto match;
  639.     }
  640.  
  641.   if (len >= 4 * kwset->mind)
  642.     qlim = lim - 4 * kwset->mind;
  643.   else
  644.     qlim = 0;
  645.  
  646.   while (lim - end >= d)
  647.     {
  648.       if (qlim && end <= qlim)
  649.     {
  650.       end += d - 1;
  651.       while ((d = delta[c = *end]) && end < qlim)
  652.         {
  653.           end += d;
  654.           end += delta[(unsigned char) *end];
  655.           end += delta[(unsigned char) *end];
  656.         }
  657.       ++end;
  658.     }
  659.       else
  660.     d = delta[c = (end += d)[-1]];
  661.       if (d)
  662.     continue;
  663.       beg = end - 1;
  664.       trie = next[c];
  665.       if (trie->accepting)
  666.     {
  667.       mch = beg;
  668.       accept = trie;
  669.     }
  670.       d = trie->shift;
  671.       while (beg > text)
  672.     {
  673.       c = trans ? trans[(unsigned char) *--beg] : *--beg;
  674.       tree = trie->links;
  675.       while (tree && c != tree->label)
  676.         if (c < tree->label)
  677.           tree = tree->llink;
  678.         else
  679.           tree = tree->rlink;
  680.       if (tree)
  681.         {
  682.           trie = tree->trie;
  683.           if (trie->accepting)
  684.         {
  685.           mch = beg;
  686.           accept = trie;
  687.         }
  688.         }
  689.       else
  690.         break;
  691.       d = trie->shift;
  692.     }
  693.       if (mch)
  694.     goto match;
  695.     }
  696.   return 0;
  697.  
  698.  match:
  699.   /* Given a known match, find the longest possible match anchored
  700.      at or before its starting point.  This is nearly a verbatim
  701.      copy of the preceding main search loops. */
  702.   if (lim - mch > kwset->maxd)
  703.     lim = mch + kwset->maxd;
  704.   lmch = 0;
  705.   d = 1;
  706.   while (lim - end >= d)
  707.     {
  708.       if ((d = delta[c = (end += d)[-1]]) != 0)
  709.     continue;
  710.       beg = end - 1;
  711.       if (!(trie = next[c]))
  712.     {
  713.       d = 1;
  714.       continue;
  715.     }
  716.       if (trie->accepting && beg <= mch)
  717.     {
  718.       lmch = beg;
  719.       accept = trie;
  720.     }
  721.       d = trie->shift;
  722.       while (beg > text)
  723.     {
  724.       c = trans ? trans[(unsigned char) *--beg] : *--beg;
  725.       tree = trie->links;
  726.       while (tree && c != tree->label)
  727.         if (c < tree->label)
  728.           tree = tree->llink;
  729.         else
  730.           tree = tree->rlink;
  731.       if (tree)
  732.         {
  733.           trie = tree->trie;
  734.           if (trie->accepting && beg <= mch)
  735.         {
  736.           lmch = beg;
  737.           accept = trie;
  738.         }
  739.         }
  740.       else
  741.         break;
  742.       d = trie->shift;
  743.     }
  744.       if (lmch)
  745.     {
  746.       mch = lmch;
  747.       goto match;
  748.     }
  749.       if (!d)
  750.     d = 1;
  751.     }
  752.  
  753.   if (kwsmatch)
  754.     {
  755.       kwsmatch->index = accept->accepting / 2;
  756.       kwsmatch->beg[0] = mch;
  757.       kwsmatch->size[0] = accept->depth;
  758.     }
  759.   return mch;
  760. }
  761.   
  762. /* Search through the given text for a match of any member of the
  763.    given keyword set.  Return a pointer to the first character of
  764.    the matching substring, or NULL if no match is found.  If FOUNDLEN
  765.    is non-NULL store in the referenced location the length of the
  766.    matching substring.  Similarly, if FOUNDIDX is non-NULL, store
  767.    in the referenced location the index number of the particular
  768.    keyword matched. */
  769. char *
  770. kwsexec(kws, text, size, kwsmatch)
  771.      kwset_t kws;
  772.      char *text;
  773.      size_t size;
  774.      struct kwsmatch *kwsmatch;
  775. {
  776.   struct kwset *kwset;
  777.   char *ret;
  778.  
  779.   kwset = (struct kwset *) kws;
  780.   if (kwset->words == 1 && kwset->trans == 0)
  781.     {
  782.       ret = bmexec(kws, text, size);
  783.       if (kwsmatch != 0 && ret != 0)
  784.     {
  785.       kwsmatch->index = 0;
  786.       kwsmatch->beg[0] = ret;
  787.       kwsmatch->size[0] = kwset->mind;
  788.     }
  789.       return ret;
  790.     }
  791.   else
  792.     return cwexec(kws, text, size, kwsmatch);
  793. }
  794.  
  795. /* Free the components of the given keyword set. */
  796. void
  797. kwsfree(kws)
  798.      kwset_t kws;
  799. {
  800.   struct kwset *kwset;
  801.  
  802.   kwset = (struct kwset *) kws;
  803.   obstack_free(&kwset->obstack, 0);
  804.   free(kws);
  805. }
  806.