home *** CD-ROM | disk | FTP | other *** search
/ Borland Programmer's Resource / Borland_Programmers_Resource_CD_1995.iso / ntcode / gnugrep / kwset.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-05-19  |  17.3 KB  |  666 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. #include <stdlib.h>
  23. #include <stddef.h>
  24. #include <limits.h>
  25. #include <ctype.h>
  26. #ifdef __TURBOC__
  27. #include <alloc.h>
  28. #else
  29. #include <malloc.h>
  30. #endif /*__TURBOC__*/
  31.  
  32. /* The algorithm implemented by these routines bears a startling resemblence
  33.    to one discovered by Beate Commentz-Walter, although it is not identical.
  34.    See "A String Matching Algorithm Fast on the Average," Technical Report,
  35.    IBMGermany, Scientific Center Heidelberg, Tiergartenstrasse 15, D-6900
  36.    Heidelberg, Germany.  See also Aho, A.V., and M. Corasick, "Efficient
  37.    String Matching:  An Aid to Bibliographic Search," CACM June 1975,
  38.    Vol. 18, No. 6, which describes the failur function used below. */
  39.  
  40. #include "kwset.h"
  41. #include "obstack.h"
  42.  
  43. #define NCHAR (UCHAR_MAX + 1)
  44. #define obstack_chunk_alloc malloc
  45. #define obstack_chunk_free free
  46.  
  47. /* Balanced tree of edges and labels leaving a given trie node. */
  48. struct tree
  49. {
  50.   struct tree *llink;        /* Left link; MUST be first field. */
  51.   struct tree *rlink;        /* Right link (to larger labels). */
  52.   struct trie *trie;        /* Trie node pointed to by this edge. */
  53.   unsigned char label;        /* Label on this edge. */
  54.   char balance;            /* Difference i depths of subtrees. */
  55. };
  56.  
  57. /* Node of a trie representing a set of reversed keywords. */
  58. struct trie
  59. {
  60.   unsigned int accepting;    /* Word index of accepted word, or zero. */
  61.   struct tree *links;        /* Tree of edges leaving this node. */
  62.   struct trie *parent;        /* Parent of this node. */
  63.   struct trie *next;        /* List of all trie nodes in level order. */
  64.   struct trie *fail;        /* Aho-Corasick failure function. */
  65.   int depth;            /* Depth of this node from the root. */
  66.   int shift;            /* Shift function for search filures. */
  67.   int maxshift;            /* Max shift of self and descendents. */
  68. };
  69.  
  70. /* Structure returned opaquely to the caller, containing everything. */
  71. struct kwset
  72. {
  73.   struct obstack obstack;    /* Obstack for node allocation. */
  74.   int words;            /* Number of words n the trie. */
  75.   struct trie *trie;        /* The trie itself. */
  76.   int mind;            /* Minimum depth of an accepting node. */
  77.   int maxd;            /* Maximum depth of any node. */
  78.   int delta[NCHAR];        /* Delta table for rapid search. */
  79.   struct trie *next[NCHAR];    /* Tableof children of the root. */
  80.   const char *trans;        /* Character translation table. */
  81. };
  82.  
  83. /* Allocate and initialize a keyword set object, returning an opaque
  84.    pointer to it.  Return NULL if memory is not available. */
  85. kwset_t
  86. kwsalloc(trans)
  87. const char *trans;
  88. {
  89.     struct kwset *kwset;
  90.  
  91.     if ( (kwset = (struct kwset *)malloc(sizeof(struct kwset))) ==
  92.                             (struct kwset *)0 )
  93.         return ( (kwset_t)0 );
  94.  
  95.     obstack_init(&kwset->obstack);
  96.     kwset->words = 0;
  97.     kwset->trie = (struct trie *)obstack_alloc(&kwset->obstack, sizeof(struct trie));
  98.     if ( !kwset->trie )
  99.     {
  100.         kwsfree((kwset_t)kwset);
  101.         return ( (kwset_t)0 );
  102.     }
  103.  
  104.     kwset->trie->accepting = 0;
  105.     kwset->trie->links = NULL;
  106.     kwset->trie->parent = NULL;
  107.     kwset->trie->next = NULL;
  108.     kwset->trie->fail = NULL;
  109.     kwset->trie->depth = 0;
  110.     kwset->trie->shift = 0;
  111.     kwset->mind = INT_MAX;
  112.     kwset->maxd = -1;
  113.     kwset->trans = trans;
  114.     return ( (kwset_t)kwset );
  115. }
  116.  
  117. /* Add the given string to the contents of the keyword set.  Return NULL
  118.    for success, an error message otherwise. */
  119. const char *
  120. kwsincr(kws, text, len)
  121. kwset_t kws;
  122. const char *text;
  123. size_t len;
  124. {
  125.     struct kwset *kwset;
  126.     struct trie *trie;
  127.     unsigned char label;
  128.     struct tree *link;
  129.     int depth;
  130.     struct tree *links[12];
  131.     enum { L, R } dirs[12];
  132.     struct tree *t;
  133.     struct tree *r;
  134.     struct tree *l;
  135.     struct tree *rl;
  136.     struct tree *lr;
  137.  
  138.     kwset = (struct kwset *)kws;
  139.     trie = kwset->trie;
  140.     text += len;
  141.  
  142.     /*
  143.      *  Descend the trie (built of reversed keywords) char-by-char,
  144.      *  installing new nodes when necessary.
  145.      */
  146.     while ( len-- )
  147.     {
  148.         label = kwset->trans ? kwset->trans[(unsigned char)*--text] :
  149.                                 *--text;
  150.  
  151.         /*
  152.          *  Descend the tree of outgoing links for this trie node,
  153.          *  looking for the current character and keeping track
  154.          *  of the path followed.
  155.          */
  156.         link = trie->links;
  157.         links[0] = (struct tree *)&trie->links;
  158.         dirs[0] = L;
  159.         depth = 1;
  160.  
  161.         while ( link && (label != link->label) )
  162.         {
  163.             links[depth] = link;
  164.             if ( label < link->label )
  165.             {
  166.                 dirs[depth++] = L;
  167.                 link = link->llink;
  168.             }
  169.             else
  170.             {
  171.                 dirs[depth++] = R;
  172.                 link = link->rlink;
  173.             }
  174.         }
  175.  
  176.         /*
  177.          *  The current character doesn't have an outgoing link at
  178.          *  this trie node, so build a new trie node and install
  179.          *  a link in the current trie node's tree.
  180.          */
  181.         if ( !link )
  182.         {
  183.             link = (struct tree *)obstack_alloc(&kwset->obstack,
  184.                                sizeof(struct tree));
  185.             if ( !link )
  186.                 return ( "memory exhausted" );
  187.             link->llink = NULL;
  188.             link->rlink = NULL;
  189.             link->trie =
  190.                 (struct trie *)obstack_alloc(&kwset->obstack,
  191.                             sizeof(struct trie));
  192.             if ( !link->trie )
  193.                 return ( "memory exhausted" );
  194.             link->trie->accepting = 0;
  195.             link->trie->links = NULL;
  196.             link->trie->parent = trie;
  197.             link->trie->next = NULL;
  198.             link->trie->fail = NULL;
  199.             link->trie->depth = trie->depth + 1;
  200.             link->trie->shift = 0;
  201.             link->label = label;
  202.             link->balance = 0;
  203.  
  204.             /*  Install the new tree node in its parent.  */
  205.             if ( dirs[--depth] == L )
  206.                 links[depth]->llink = link;
  207.             else
  208.                 links[depth]->rlink = link;
  209.  
  210.             /* Back up the tree fixing the balance flags. */
  211.             while ( depth && !links[depth]->balance )
  212.             {
  213.                 if ( dirs[depth] == L )
  214.                     links[depth]->balance--;
  215.                 else
  216.                     links[depth]->balance++;
  217.                 depth--;
  218.             }
  219.  
  220.             /*  Rebalance the tree by pointer rotations if necessary.  */
  221.             if ( depth && ((dirs[depth] == L) && --links[depth]->balance || (dirs[depth] == R) && ++links[depth]->balance) )
  222.             {
  223.                 switch ( links[depth]->balance )
  224.                 {
  225.                 case (char)-2:
  226.                     switch ( dirs[depth + 1] )
  227.                     {
  228.                     case L:
  229.                         r = links[depth];
  230.                         t = r->llink;
  231.                         rl = t->rlink;
  232.                         t->rlink = r;
  233.                         r->llink = rl;
  234.                         t->balance = r->balance = 0;
  235.                         break;
  236.                     case R:
  237.                         r = links[depth];
  238.                         l = r->llink;
  239.                         t = l->rlink;
  240.                         rl = t->rlink;
  241.                         lr = t->llink;
  242.                         t->llink = l;
  243.                         l->rlink = lr;
  244.                         t->rlink = r;
  245.                         r->llink = rl;
  246.                         l->balance = t->balance != 1 ? 0 : -1;
  247.                         r->balance = t->balance != (char) -1 ? 0 : 1;
  248.                         t->balance = 0;
  249.                         break;
  250.                     }
  251.                     break;
  252.                 case 2:
  253.                     switch ( dirs[depth + 1] )
  254.                     {
  255.                     case R:
  256.                         l = links[depth];
  257.                         t = l->rlink;
  258.                         lr = t->llink;
  259.                         t->llink = l;
  260.                         l->rlink = lr;
  261.                         t->balance = l->balance = 0;
  262.                         break;
  263.                     case L:
  264.                         l = links[depth];
  265.                         r = l->rlink;
  266.                         t = r->llink;
  267.                         lr = t->llink;
  268.                         rl = t->rlink;
  269.                         t->llink = l;
  270.                         l->rlink = lr;
  271.                         t->rlink = r;
  272.                         r->llink = rl;
  273.                         l->balance = t->balance != 1 ? 0 : -1;
  274.                         r->balance = t->balance != (char) -1 ? 0 : 1;
  275.                         t->balance = 0;
  276.                         break;
  277.                     }
  278.                     break;
  279.                 }
  280.             if ( dirs[depth - 1] == L )
  281.                 links[depth - 1]->llink = t;
  282.             else
  283.                 links[depth - 1]->rlink = t;
  284.             }
  285.         }
  286.         trie = link->trie;
  287.     }
  288.  
  289.     /* Mark the node we finally reached as accepting, encoding the
  290.     index number of this word in the keyword set so far. */
  291.     if ( !trie->accepting )
  292.         trie->accepting = 1 + 2 * kwset->words;
  293.     kwset->words++;
  294.  
  295.     /* Keep track of the longest and shortest string of the keyword set. */
  296.     if ( trie->depth < kwset->mind )
  297.         kwset->mind = trie->depth;
  298.     if ( trie->depth > kwset->maxd )
  299.         kwset->maxd = trie->depth;
  300.  
  301.     return ( NULL );
  302. }
  303.  
  304. /* Enqueue the trie nodes referenced from the given tree in the
  305.    given queue. */
  306. static void
  307. enqueue(tree, last)
  308. struct tree *tree;
  309. struct trie **last;
  310. {
  311.     if ( !tree )
  312.         return;
  313.     enqueue(tree->llink, last);
  314.     enqueue(tree->rlink, last);
  315.     (*last) = (*last)->next = tree->trie;
  316. }
  317.  
  318. /* Compute the Aho-Corasick failure function for the trie nodes referenced
  319.    from the given tree, given the failure function for their parent as
  320.    well as a last resort failure node. */
  321. static void
  322. treefails(tree, fail, recourse)
  323. struct tree *tree;
  324. struct trie *fail;
  325. struct trie *recourse;
  326. {
  327.     struct tree *link;
  328.  
  329.     if ( !tree )
  330.         return;
  331.  
  332.     treefails(tree->llink, fail, recourse);
  333.     treefails(tree->rlink, fail, recourse);
  334.  
  335.     /* Find, in the chain of fails going back to the root, the first
  336.     node that has a descendent on the current label. */
  337.     while ( fail )
  338.     {
  339.         link = fail->links;
  340.         while ( link && (tree->label != link->label) )
  341.             if ( tree->label < link->label )
  342.                 link = link->llink;
  343.             else
  344.                 link = link->rlink;
  345.         if ( link )
  346.         {
  347.             tree->trie->fail = link->trie;
  348.             return;
  349.         }
  350.         fail = fail->fail;
  351.     }
  352.     tree->trie->fail = recourse;
  353. }
  354.  
  355. /* Set delta entries for the links of the given tree such that
  356.    the preexisting delta value is larger than the current depth. */
  357. static void
  358. treedelta(tree, depth, delta)
  359. struct tree *tree;
  360. int depth;
  361. int delta[];
  362. {
  363.     if ( !tree )
  364.         return;
  365.     treedelta(tree->llink, depth, delta);
  366.     treedelta(tree->rlink, depth, delta);
  367.     if ( depth < delta[tree->label] )
  368.         delta[tree->label] = depth;
  369. }
  370.  
  371. /* Return true if A has every label in B. */
  372. static int
  373. hasevery(a, b)
  374. struct tree *a;
  375. struct tree *b;
  376. {
  377.     if ( !b )
  378.         return ( 1 );
  379.     if ( !hasevery(a, b->llink) )
  380.         return ( 0 );
  381.     if ( !hasevery(a, b->rlink) )
  382.         return ( 0 );
  383.     while ( a && (b->label != a->label) )
  384.         if ( b->label < a->label )
  385.             a = a->llink;
  386.         else
  387.             a = a->rlink;
  388.     return ( !!a );
  389. }
  390.  
  391. /* Compute a vector, indexed by character code, of the trie nodes
  392.    referenced from the given tree. */
  393. static void
  394. treenext(tree, next)
  395. struct tree *tree;
  396. struct trie *next[];
  397. {
  398.   if (!tree)
  399.     return;
  400.   treenext(tree->llink, next);
  401.   treenext(tree->rlink, next);
  402.   next[tree->label] = tree->trie;
  403. }
  404.  
  405. /* Compute the shift for each trie node, as well as the delta
  406.    table and next cache for the given keyword set. */
  407. const char *
  408. kwsprep(kws)
  409. kwset_t kws;
  410. {
  411.   register struct kwset *kwset;
  412.   register int i;
  413.   register struct trie *curr, *fail;
  414.   register const char *trans;
  415.   int delta[NCHAR];
  416.   struct trie *last, *next[NCHAR];
  417.  
  418.   kwset = (struct kwset *) kws;
  419.  
  420.   /* Initial values for the delta table; will be changed later.  The
  421.      delta entry for a given character is the smallest depth of any
  422.      node at which an outgoing edge is labeled by that character. */
  423.   for (i = 0; i < NCHAR; ++i)
  424.     delta[i] = kwset->mind;
  425.  
  426.   /* Traverse the nodes of the trie in level order, simultaneously
  427.      computing the delta table, failure function, and shift function. */
  428.   for (curr = last = kwset->trie; curr; curr = curr->next)
  429.     {
  430.       /* Enqueue the immediate descendents in the level order queue. */
  431.       enqueue(curr->links, &last);
  432.  
  433.       curr->shift = kwset->mind;
  434.       curr->maxshift = kwset->mind;
  435.  
  436.       /* Update the delta table for the descendents of this node. */
  437.       treedelta(curr->links, curr->depth, delta);
  438.  
  439.       /* Compute the failure function for the decendents of this node. */
  440.       treefails(curr->links, curr->fail, kwset->trie);
  441.  
  442.       /* Update the shifts at each node in the current node's chain
  443.      of fails back to the root. */
  444.       for (fail = curr->fail; fail; fail = fail->fail)
  445.     {
  446.       /* If the current node has some outgoing edge that the fail
  447.          doesn't, then the shift at the fail should be no larger
  448.          than the difference of their depths. */
  449.       if (!hasevery(fail->links, curr->links))
  450.         if (curr->depth - fail->depth < fail->shift)
  451.           fail->shift = curr->depth - fail->depth;
  452.  
  453.       /* If the current node is accepting then the shift at the
  454.          fail and its descendents should be no larger than the
  455.          difference of their depths. */
  456.       if (curr->accepting && fail->maxshift > curr->depth - fail->depth)
  457.         fail->maxshift = curr->depth - fail->depth;
  458.     }
  459.     }
  460.  
  461.   /* Traverse the trie in level order again, fixing up all nodes whose
  462.      shift exceeds their inherited maxshift. */
  463.   for (curr = kwset->trie->next; curr; curr = curr->next)
  464.     {
  465.       if (curr->maxshift > curr->parent->maxshift)
  466.     curr->maxshift = curr->parent->maxshift;
  467.       if (curr->shift > curr->maxshift)
  468.     curr->shift = curr->maxshift;
  469.     }
  470.  
  471.   /* Create a vector, indexed by character code, of the outgoing links
  472.      from the root node. */
  473.   for (i = 0; i < NCHAR; ++i)
  474.     next[i] = NULL;
  475.   treenext(kwset->trie->links, next);
  476.  
  477.   /* Fix things up for any translation table. */
  478.   if ( (trans = kwset->trans) != NULL )
  479.     for (i = 0; i < NCHAR; ++i)
  480.       {
  481.     kwset->delta[i] = delta[(unsigned char) trans[i]];
  482.     kwset->next[i] = next[(unsigned char) trans[i]];
  483.       }
  484.   else
  485.     for (i = 0; i < NCHAR; ++i)
  486.       {
  487.     kwset->delta[i] = delta[i];
  488.     kwset->next[i] = next[i];
  489.       }
  490.  
  491.   return NULL;
  492. }
  493.  
  494. /* Search through the given text for a match of any member of the
  495.    given keyword set.  Return a pointer to the first character of
  496.    the matching substring, or NULL if no match is found.  If FOUNDLEN
  497.    is non-NULL store in the referenced location the length of the
  498.    matching substring.  Similarly, if FOUNDIDX is non-NULL, store
  499.    in the referenced location the index number of the particular
  500.    keyword matched. */
  501. char *
  502. kwsexec(kws, text, len, kwsmatch)
  503. kwset_t kws;
  504. char *text;
  505. size_t len;
  506. struct kwsmatch *kwsmatch;
  507. {
  508.   struct kwset *kwset;
  509.   struct trie **next, *trie, *accept;
  510.   char *beg, *lim, *mch, *lmch;
  511.   register unsigned char c;
  512.   register int *delta, d;
  513.   register char *end, *qlim;
  514.   register struct tree *tree;
  515.   register const char *trans;
  516.  
  517.   /* Initialize register copies and look for easy ways out. */
  518.   kwset = (struct kwset *) kws;
  519.   if (len < kwset->mind)
  520.     return NULL;
  521.   next = kwset->next;
  522.   delta = kwset->delta;
  523.   trans = kwset->trans;
  524.   lim = text + len;
  525.   end = text;
  526.   if ( (d = kwset->mind) != 0 )
  527.     mch = NULL;
  528.   else
  529.     {
  530.       mch = text, accept = kwset->trie;
  531.       goto match;
  532.     }
  533.  
  534.   if (len >= 4 * kwset->mind)
  535.     qlim = lim - 4 * kwset->mind;
  536.   else
  537.     qlim = NULL;
  538.  
  539.   while (lim - end >= d)
  540.     {
  541.       if (qlim && end <= qlim)
  542.     {
  543.       end += d - 1;
  544.       while ( ((d = delta[c = *end]) != 0) && (end < qlim) )
  545.         {
  546.           end += d;
  547.           end += delta[(unsigned char) *end];
  548.           end += delta[(unsigned char) *end];
  549.         }
  550.       ++end;
  551.     }
  552.       else
  553.     d = delta[c = (end += d)[-1]];
  554.       if (d)
  555.     continue;
  556.       beg = end - 1;
  557.       trie = next[c];
  558.       if (trie->accepting)
  559.     {
  560.       mch = beg;
  561.       accept = trie;
  562.     }
  563.       d = trie->shift;
  564.       while (beg > text)
  565.     {
  566.       c = trans ? trans[(unsigned char) *--beg] : *--beg;
  567.       tree = trie->links;
  568.       while (tree && c != tree->label)
  569.         if (c < tree->label)
  570.           tree = tree->llink;
  571.         else
  572.           tree = tree->rlink;
  573.       if (tree)
  574.         {
  575.           trie = tree->trie;
  576.           if (trie->accepting)
  577.         {
  578.           mch = beg;
  579.           accept = trie;
  580.         }
  581.         }
  582.       else
  583.         break;
  584.       d = trie->shift;
  585.     }
  586.       if (mch)
  587.     goto match;
  588.     }
  589.   return NULL;
  590.  
  591.  match:
  592.   /* Given a known match, find the longest possible match anchored
  593.      at or before its starting point.  This is nearly a verbatim
  594.      copy of the preceding main search loops. */
  595.   if (lim - mch > kwset->maxd)
  596.     lim = mch + kwset->maxd;
  597.   lmch = NULL;
  598.   d = 1;
  599.   while (lim - end >= d)
  600.     {
  601.       if ( (d = delta[c = (end += d)[-1]]) != 0 )
  602.     continue;
  603.       beg = end - 1;
  604.       if ( (trie = next[c]) != (struct trie *)0 )
  605.     {
  606.       d = 1;
  607.       continue;
  608.     }
  609.       if (trie->accepting && beg <= mch)
  610.     {
  611.       lmch = beg;
  612.       accept = trie;
  613.     }
  614.       d = trie->shift;
  615.       while (beg > text)
  616.     {
  617.       c = trans ? trans[(unsigned char) *--beg] : *--beg;
  618.       tree = trie->links;
  619.       while (tree && c != tree->label)
  620.         if (c < tree->label)
  621.           tree = tree->llink;
  622.         else
  623.           tree = tree->rlink;
  624.       if (tree)
  625.         {
  626.           trie = tree->trie;
  627.           if (trie->accepting && beg <= mch)
  628.         {
  629.           lmch = beg;
  630.           accept = trie;
  631.         }
  632.         }
  633.       else
  634.         break;
  635.       d = trie->shift;
  636.     }
  637.       if (lmch)
  638.     {
  639.       mch = lmch;
  640.       goto match;
  641.     }
  642.       if (!d)
  643.     d = 1;
  644.     }
  645.  
  646.   if (kwsmatch)
  647.     {
  648.       kwsmatch->index = accept->accepting / 2;
  649.       kwsmatch->beg[0] = mch;
  650.       kwsmatch->size[0] = accept->depth;
  651.     }
  652.   return mch;
  653. }
  654.   
  655. /* Free the components of the given keyword set. */
  656. void
  657. kwsfree(kws)
  658. kwset_t kws;
  659. {
  660.     struct kwset *kwset;
  661.  
  662.     kwset = (struct kwset *)kws;
  663.     obstack_free(&kwset->obstack, (void *)NULL);
  664.     free((void *)kws);
  665. }
  666.