freshlybakedca.ke
Git fork
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` */
44static 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 */
55const 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. */
91struct 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. */
101struct 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. */
114struct 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. */
130kwset_t
131kwsalloc (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. */
167const char *
168kwsincr (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. */
330static void
331enqueue (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. */
343static void
344treefails (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. */
378static void
379treedelta (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. */
392static int
393hasevery (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. */
411static void
412treenext (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. */
423const char *
424kwsprep (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. */
539static size_t
540bmexec (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. */
625static size_t
626cwexec (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. */
788size_t
789kwsexec (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. */
809void
810kwsfree (kwset_t kws)
811{
812 struct kwset *kwset;
813
814 kwset = (struct kwset *) kws;
815 obstack_free(&kwset->obstack, NULL);
816 free(kws);
817}