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
7 /* kwset.c - search for any of a set of keywords.
8 Copyright 1989, 1998, 2000, 2005 Free Software Foundation, Inc.
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)
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.
20 You should have received a copy of the GNU General Public License
21 along with this program; if not, see <http://www.gnu.org/licenses/>. */
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. */
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. */
38 #include "compat/obstack.h"
40 #define NCHAR (UCHAR_MAX + 1)
41 #define obstack_chunk_alloc xmalloc
42 #define obstack_chunk_free free
44 #define U(c) ((unsigned char) (c))
46 /* Balanced tree of edges and labels leaving a given trie node. */
49 struct tree
*llink
; /* Left link; MUST be first field. */
50 struct tree
*rlink
; /* Right link (to larger labels). */
51 struct trie
*trie
; /* Trie node pointed to by this edge. */
52 unsigned char label
; /* Label on this edge. */
53 char balance
; /* Difference in depths of subtrees. */
56 /* Node of a trie representing a set of reversed keywords. */
59 unsigned int accepting
; /* Word index of accepted word, or zero. */
60 struct tree
*links
; /* Tree of edges leaving this node. */
61 struct trie
*parent
; /* Parent of this node. */
62 struct trie
*next
; /* List of all trie nodes in level order. */
63 struct trie
*fail
; /* Aho-Corasick failure function. */
64 int depth
; /* Depth of this node from the root. */
65 int shift
; /* Shift function for search failures. */
66 int maxshift
; /* Max shift of self and descendants. */
69 /* Structure returned opaquely to the caller, containing everything. */
72 struct obstack obstack
; /* Obstack for node allocation. */
73 int words
; /* Number of words in the trie. */
74 struct trie
*trie
; /* The trie itself. */
75 int mind
; /* Minimum depth of an accepting node. */
76 int maxd
; /* Maximum depth of any node. */
77 unsigned char delta
[NCHAR
]; /* Delta table for rapid search. */
78 struct trie
*next
[NCHAR
]; /* Table of children of the root. */
79 char *target
; /* Target string if there's only one. */
80 int mind2
; /* Used in Boyer-Moore search for one string. */
81 unsigned char const *trans
; /* Character translation table. */
84 /* Allocate and initialize a keyword set object, returning an opaque
85 pointer to it. Return NULL if memory is not available. */
87 kwsalloc (unsigned char const *trans
)
91 kwset
= (struct kwset
*) xmalloc(sizeof (struct kwset
));
93 obstack_init(&kwset
->obstack
);
96 = (struct trie
*) obstack_alloc(&kwset
->obstack
, sizeof (struct trie
));
99 kwsfree((kwset_t
) kwset
);
102 kwset
->trie
->accepting
= 0;
103 kwset
->trie
->links
= NULL
;
104 kwset
->trie
->parent
= NULL
;
105 kwset
->trie
->next
= NULL
;
106 kwset
->trie
->fail
= NULL
;
107 kwset
->trie
->depth
= 0;
108 kwset
->trie
->shift
= 0;
109 kwset
->mind
= INT_MAX
;
111 kwset
->target
= NULL
;
112 kwset
->trans
= trans
;
114 return (kwset_t
) kwset
;
117 /* This upper bound is valid for CHAR_BIT >= 4 and
118 exact for CHAR_BIT in { 4..11, 13, 15, 17, 19 }. */
119 #define DEPTH_SIZE (CHAR_BIT + CHAR_BIT/2)
121 /* Add the given string to the contents of the keyword set. Return NULL
122 for success, an error message otherwise. */
124 kwsincr (kwset_t kws
, char const *text
, size_t len
)
127 register struct trie
*trie
;
128 register unsigned char label
;
129 register struct tree
*link
;
131 struct tree
*links
[DEPTH_SIZE
];
132 enum { L
, R
} dirs
[DEPTH_SIZE
];
133 struct tree
*t
, *r
, *l
, *rl
, *lr
;
135 kwset
= (struct kwset
*) kws
;
139 /* Descend the trie (built of reversed keywords) character-by-character,
140 installing new nodes when necessary. */
143 label
= kwset
->trans
? kwset
->trans
[U(*--text
)] : *--text
;
145 /* Descend the tree of outgoing links for this trie node,
146 looking for the current character and keeping track
147 of the path followed. */
149 links
[0] = (struct tree
*) &trie
->links
;
153 while (link
&& label
!= link
->label
)
156 if (label
< link
->label
)
157 dirs
[depth
++] = L
, link
= link
->llink
;
159 dirs
[depth
++] = R
, link
= link
->rlink
;
162 /* The current character doesn't have an outgoing link at
163 this trie node, so build a new trie node and install
164 a link in the current trie node's tree. */
167 link
= (struct tree
*) obstack_alloc(&kwset
->obstack
,
168 sizeof (struct tree
));
170 return "memory exhausted";
173 link
->trie
= (struct trie
*) obstack_alloc(&kwset
->obstack
,
174 sizeof (struct trie
));
177 obstack_free(&kwset
->obstack
, link
);
178 return "memory exhausted";
180 link
->trie
->accepting
= 0;
181 link
->trie
->links
= NULL
;
182 link
->trie
->parent
= trie
;
183 link
->trie
->next
= NULL
;
184 link
->trie
->fail
= NULL
;
185 link
->trie
->depth
= trie
->depth
+ 1;
186 link
->trie
->shift
= 0;
190 /* Install the new tree node in its parent. */
191 if (dirs
[--depth
] == L
)
192 links
[depth
]->llink
= link
;
194 links
[depth
]->rlink
= link
;
196 /* Back up the tree fixing the balance flags. */
197 while (depth
&& !links
[depth
]->balance
)
199 if (dirs
[depth
] == L
)
200 --links
[depth
]->balance
;
202 ++links
[depth
]->balance
;
206 /* Rebalance the tree by pointer rotations if necessary. */
207 if (depth
&& ((dirs
[depth
] == L
&& --links
[depth
]->balance
)
208 || (dirs
[depth
] == R
&& ++links
[depth
]->balance
)))
210 switch (links
[depth
]->balance
)
213 switch (dirs
[depth
+ 1])
216 r
= links
[depth
], t
= r
->llink
, rl
= t
->rlink
;
217 t
->rlink
= r
, r
->llink
= rl
;
218 t
->balance
= r
->balance
= 0;
221 r
= links
[depth
], l
= r
->llink
, t
= l
->rlink
;
222 rl
= t
->rlink
, lr
= t
->llink
;
223 t
->llink
= l
, l
->rlink
= lr
, t
->rlink
= r
, r
->llink
= rl
;
224 l
->balance
= t
->balance
!= 1 ? 0 : -1;
225 r
->balance
= t
->balance
!= (char) -1 ? 0 : 1;
233 switch (dirs
[depth
+ 1])
236 l
= links
[depth
], t
= l
->rlink
, lr
= t
->llink
;
237 t
->llink
= l
, l
->rlink
= lr
;
238 t
->balance
= l
->balance
= 0;
241 l
= links
[depth
], r
= l
->rlink
, t
= r
->llink
;
242 lr
= t
->llink
, rl
= t
->rlink
;
243 t
->llink
= l
, l
->rlink
= lr
, t
->rlink
= r
, r
->llink
= rl
;
244 l
->balance
= t
->balance
!= 1 ? 0 : -1;
245 r
->balance
= t
->balance
!= (char) -1 ? 0 : 1;
256 if (dirs
[depth
- 1] == L
)
257 links
[depth
- 1]->llink
= t
;
259 links
[depth
- 1]->rlink
= t
;
266 /* Mark the node we finally reached as accepting, encoding the
267 index number of this word in the keyword set so far. */
268 if (!trie
->accepting
)
269 trie
->accepting
= 1 + 2 * kwset
->words
;
272 /* Keep track of the longest and shortest string of the keyword set. */
273 if (trie
->depth
< kwset
->mind
)
274 kwset
->mind
= trie
->depth
;
275 if (trie
->depth
> kwset
->maxd
)
276 kwset
->maxd
= trie
->depth
;
281 /* Enqueue the trie nodes referenced from the given tree in the
284 enqueue (struct tree
*tree
, struct trie
**last
)
288 enqueue(tree
->llink
, last
);
289 enqueue(tree
->rlink
, last
);
290 (*last
) = (*last
)->next
= tree
->trie
;
293 /* Compute the Aho-Corasick failure function for the trie nodes referenced
294 from the given tree, given the failure function for their parent as
295 well as a last resort failure node. */
297 treefails (register struct tree
const *tree
, struct trie
const *fail
,
298 struct trie
*recourse
)
300 register struct tree
*link
;
305 treefails(tree
->llink
, fail
, recourse
);
306 treefails(tree
->rlink
, fail
, recourse
);
308 /* Find, in the chain of fails going back to the root, the first
309 node that has a descendant on the current label. */
313 while (link
&& tree
->label
!= link
->label
)
314 if (tree
->label
< link
->label
)
320 tree
->trie
->fail
= link
->trie
;
326 tree
->trie
->fail
= recourse
;
329 /* Set delta entries for the links of the given tree such that
330 the preexisting delta value is larger than the current depth. */
332 treedelta (register struct tree
const *tree
,
333 register unsigned int depth
,
334 unsigned char delta
[])
338 treedelta(tree
->llink
, depth
, delta
);
339 treedelta(tree
->rlink
, depth
, delta
);
340 if (depth
< delta
[tree
->label
])
341 delta
[tree
->label
] = depth
;
344 /* Return true if A has every label in B. */
346 hasevery (register struct tree
const *a
, register struct tree
const *b
)
350 if (!hasevery(a
, b
->llink
))
352 if (!hasevery(a
, b
->rlink
))
354 while (a
&& b
->label
!= a
->label
)
355 if (b
->label
< a
->label
)
362 /* Compute a vector, indexed by character code, of the trie nodes
363 referenced from the given tree. */
365 treenext (struct tree
const *tree
, struct trie
*next
[])
369 treenext(tree
->llink
, next
);
370 treenext(tree
->rlink
, next
);
371 next
[tree
->label
] = tree
->trie
;
374 /* Compute the shift for each trie node, as well as the delta
375 table and next cache for the given keyword set. */
377 kwsprep (kwset_t kws
)
379 register struct kwset
*kwset
;
381 register struct trie
*curr
;
382 register unsigned char const *trans
;
383 unsigned char delta
[NCHAR
];
385 kwset
= (struct kwset
*) kws
;
387 /* Initial values for the delta table; will be changed later. The
388 delta entry for a given character is the smallest depth of any
389 node at which an outgoing edge is labeled by that character. */
390 memset(delta
, kwset
->mind
< UCHAR_MAX
? kwset
->mind
: UCHAR_MAX
, NCHAR
);
392 /* Check if we can use the simple boyer-moore algorithm, instead
393 of the hairy commentz-walter algorithm. */
394 if (kwset
->words
== 1 && kwset
->trans
== NULL
)
398 /* Looking for just one string. Extract it from the trie. */
399 kwset
->target
= obstack_alloc(&kwset
->obstack
, kwset
->mind
);
401 return "memory exhausted";
402 for (i
= kwset
->mind
- 1, curr
= kwset
->trie
; i
>= 0; --i
)
404 kwset
->target
[i
] = curr
->links
->label
;
405 curr
= curr
->links
->trie
;
407 /* Build the Boyer Moore delta. Boy that's easy compared to CW. */
408 for (i
= 0; i
< kwset
->mind
; ++i
)
409 delta
[U(kwset
->target
[i
])] = kwset
->mind
- (i
+ 1);
410 /* Find the minimal delta2 shift that we might make after
411 a backwards match has failed. */
412 c
= kwset
->target
[kwset
->mind
- 1];
413 for (i
= kwset
->mind
- 2; i
>= 0; --i
)
414 if (kwset
->target
[i
] == c
)
416 kwset
->mind2
= kwset
->mind
- (i
+ 1);
420 register struct trie
*fail
;
421 struct trie
*last
, *next
[NCHAR
];
423 /* Traverse the nodes of the trie in level order, simultaneously
424 computing the delta table, failure function, and shift function. */
425 for (curr
= last
= kwset
->trie
; curr
; curr
= curr
->next
)
427 /* Enqueue the immediate descendants in the level order queue. */
428 enqueue(curr
->links
, &last
);
430 curr
->shift
= kwset
->mind
;
431 curr
->maxshift
= kwset
->mind
;
433 /* Update the delta table for the descendants of this node. */
434 treedelta(curr
->links
, curr
->depth
, delta
);
436 /* Compute the failure function for the descendants of this node. */
437 treefails(curr
->links
, curr
->fail
, kwset
->trie
);
439 /* Update the shifts at each node in the current node's chain
440 of fails back to the root. */
441 for (fail
= curr
->fail
; fail
; fail
= fail
->fail
)
443 /* If the current node has some outgoing edge that the fail
444 doesn't, then the shift at the fail should be no larger
445 than the difference of their depths. */
446 if (!hasevery(fail
->links
, curr
->links
))
447 if (curr
->depth
- fail
->depth
< fail
->shift
)
448 fail
->shift
= curr
->depth
- fail
->depth
;
450 /* If the current node is accepting then the shift at the
451 fail and its descendants should be no larger than the
452 difference of their depths. */
453 if (curr
->accepting
&& fail
->maxshift
> curr
->depth
- fail
->depth
)
454 fail
->maxshift
= curr
->depth
- fail
->depth
;
458 /* Traverse the trie in level order again, fixing up all nodes whose
459 shift exceeds their inherited maxshift. */
460 for (curr
= kwset
->trie
->next
; curr
; curr
= curr
->next
)
462 if (curr
->maxshift
> curr
->parent
->maxshift
)
463 curr
->maxshift
= curr
->parent
->maxshift
;
464 if (curr
->shift
> curr
->maxshift
)
465 curr
->shift
= curr
->maxshift
;
468 /* Create a vector, indexed by character code, of the outgoing links
469 from the root node. */
470 for (i
= 0; i
< NCHAR
; ++i
)
472 treenext(kwset
->trie
->links
, next
);
474 if ((trans
= kwset
->trans
) != NULL
)
475 for (i
= 0; i
< NCHAR
; ++i
)
476 kwset
->next
[i
] = next
[U(trans
[i
])];
478 COPY_ARRAY(kwset
->next
, next
, NCHAR
);
481 /* Fix things up for any translation table. */
482 if ((trans
= kwset
->trans
) != NULL
)
483 for (i
= 0; i
< NCHAR
; ++i
)
484 kwset
->delta
[i
] = delta
[U(trans
[i
])];
486 memcpy(kwset
->delta
, delta
, NCHAR
);
491 /* Fast boyer-moore search. */
493 bmexec (kwset_t kws
, char const *text
, size_t size
)
495 struct kwset
const *kwset
;
496 register unsigned char const *d1
;
497 register char const *ep
, *sp
, *tp
;
498 register int d
, gc
, i
, len
, md2
;
500 kwset
= (struct kwset
const *) kws
;
509 tp
= memchr (text
, kwset
->target
[0], size
);
510 return tp
? tp
- text
: -1;
514 sp
= kwset
->target
+ len
;
519 /* Significance of 12: 1 (initial offset) + 10 (skip loop) + 1 (md2). */
521 /* 11 is not a bug, the initial offset happens only once. */
522 for (ep
= text
+ size
- 11 * len
;;)
526 d
= d1
[U(tp
[-1])], tp
+= d
;
527 d
= d1
[U(tp
[-1])], tp
+= d
;
530 d
= d1
[U(tp
[-1])], tp
+= d
;
531 d
= d1
[U(tp
[-1])], tp
+= d
;
532 d
= d1
[U(tp
[-1])], tp
+= d
;
535 d
= d1
[U(tp
[-1])], tp
+= d
;
536 d
= d1
[U(tp
[-1])], tp
+= d
;
537 d
= d1
[U(tp
[-1])], tp
+= d
;
540 d
= d1
[U(tp
[-1])], tp
+= d
;
541 d
= d1
[U(tp
[-1])], tp
+= d
;
547 for (i
= 3; i
<= len
&& U(tp
[-i
]) == U(sp
[-i
]); ++i
)
550 return tp
- len
- text
;
555 /* Now we have only a few characters left to search. We
556 carefully avoid ever producing an out-of-bounds pointer. */
561 d
= d1
[U((tp
+= d
)[-1])];
566 for (i
= 3; i
<= len
&& U(tp
[-i
]) == U(sp
[-i
]); ++i
)
569 return tp
- len
- text
;
577 /* Hairy multiple string search. */
579 cwexec (kwset_t kws
, char const *text
, size_t len
, struct kwsmatch
*kwsmatch
)
581 struct kwset
const *kwset
;
582 struct trie
* const *next
;
583 struct trie
const *trie
;
584 struct trie
const *accept
;
585 char const *beg
, *lim
, *mch
, *lmch
;
586 register unsigned char c
;
587 register unsigned char const *delta
;
589 register char const *end
, *qlim
;
590 register struct tree
const *tree
;
591 register unsigned char const *trans
;
595 /* Initialize register copies and look for easy ways out. */
596 kwset
= (struct kwset
*) kws
;
597 if (len
< kwset
->mind
)
600 delta
= kwset
->delta
;
601 trans
= kwset
->trans
;
604 if ((d
= kwset
->mind
) != 0)
608 mch
= text
, accept
= kwset
->trie
;
612 if (len
>= 4 * kwset
->mind
)
613 qlim
= lim
- 4 * kwset
->mind
;
617 while (lim
- end
>= d
)
619 if (qlim
&& end
<= qlim
)
622 while ((d
= delta
[c
= *end
]) && end
< qlim
)
625 end
+= delta
[U(*end
)];
626 end
+= delta
[U(*end
)];
631 d
= delta
[c
= (end
+= d
)[-1]];
644 c
= trans
? trans
[U(*--beg
)] : *--beg
;
646 while (tree
&& c
!= tree
->label
)
670 /* Given a known match, find the longest possible match anchored
671 at or before its starting point. This is nearly a verbatim
672 copy of the preceding main search loops. */
673 if (lim
- mch
> kwset
->maxd
)
674 lim
= mch
+ kwset
->maxd
;
677 while (lim
- end
>= d
)
679 if ((d
= delta
[c
= (end
+= d
)[-1]]) != 0)
682 if (!(trie
= next
[c
]))
687 if (trie
->accepting
&& beg
<= mch
)
695 c
= trans
? trans
[U(*--beg
)] : *--beg
;
697 while (tree
&& c
!= tree
->label
)
705 if (trie
->accepting
&& beg
<= mch
)
726 kwsmatch
->index
= accept
->accepting
/ 2;
727 kwsmatch
->offset
[0] = mch
- text
;
728 kwsmatch
->size
[0] = accept
->depth
;
733 /* Search through the given text for a match of any member of the
734 given keyword set. Return a pointer to the first character of
735 the matching substring, or NULL if no match is found. If FOUNDLEN
736 is non-NULL store in the referenced location the length of the
737 matching substring. Similarly, if FOUNDIDX is non-NULL, store
738 in the referenced location the index number of the particular
741 kwsexec (kwset_t kws
, char const *text
, size_t size
,
742 struct kwsmatch
*kwsmatch
)
744 struct kwset
const *kwset
= (struct kwset
*) kws
;
745 if (kwset
->words
== 1 && kwset
->trans
== NULL
)
747 size_t ret
= bmexec (kws
, text
, size
);
748 if (kwsmatch
!= NULL
&& ret
!= (size_t) -1)
751 kwsmatch
->offset
[0] = ret
;
752 kwsmatch
->size
[0] = kwset
->mind
;
757 return cwexec(kws
, text
, size
, kwsmatch
);
760 /* Free the components of the given keyword set. */
762 kwsfree (kwset_t kws
)
766 kwset
= (struct kwset
*) kws
;
767 obstack_free(&kwset
->obstack
, NULL
);