kwset.c

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