/* kwset.c - search for any of a set of keywords.
Copyright 1989 Free Software Foundation
Written August 1989 by Mike Haertel.
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 1, or (at your option)
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
The author may be reached (Email) at the address mike@ai.mit.edu,
or (US mail) as Mike Haertel c/o Free Software Foundation. */
/* The algorithm implemented by these routines bears a startling resemblence
to one discovered by Beate Commentz-Walter, although it is not identical.
See "A String Matching Algorithm Fast on the Average," Technical Report,
IBM-Germany, Scientific Center Heidelberg, Tiergartenstrasse 15, D-6900
Heidelberg, Germany. See also Aho, A.V., and M. Corasick, "Efficient
String Matching: An Aid to Bibliographic Search," CACM June 1975,
Vol. 18, No. 6, which describes the failure function used below. */
#define INT_MAX 2147483647
#define NCHAR (UCHAR_MAX + 1)
#define obstack_chunk_alloc malloc
#define obstack_chunk_free free
/* Balanced tree of edges and labels leaving a given trie node. */
struct tree
*llink
; /* Left link; MUST be first field. */
struct tree
*rlink
; /* Right link (to larger labels). */
struct trie
*trie
; /* Trie node pointed to by this edge. */
unsigned char label
; /* Label on this edge. */
char balance
; /* Difference in depths of subtrees. */
/* Node of a trie representing a set of reversed keywords. */
unsigned int accepting
; /* Word index of accepted word, or zero. */
struct tree
*links
; /* Tree of edges leaving this node. */
struct trie
*parent
; /* Parent of this node. */
struct trie
*next
; /* List of all trie nodes in level order. */
struct trie
*fail
; /* Aho-Corasick failure function. */
int depth
; /* Depth of this node from the root. */
int shift
; /* Shift function for search failures. */
int maxshift
; /* Max shift of self and descendents. */
/* Structure returned opaquely to the caller, containing everything. */
struct obstack obstack
; /* Obstack for node allocation. */
int words
; /* Number of words in the trie. */
struct trie
*trie
; /* The trie itself. */
int mind
; /* Minimum depth of an accepting node. */
int maxd
; /* Maximum depth of any node. */
unsigned char delta
[NCHAR
]; /* Delta table for rapid search. */
struct trie
*next
[NCHAR
]; /* Table of children of the root. */
char *target
; /* Target string if there's only one. */
int mind2
; /* Used in Boyer-Moore search for one string. */
char *trans
; /* Character translation table. */
/* Allocate and initialize a keyword set object, returning an opaque
pointer to it. Return NULL if memory is not available. */
kwset
= (struct kwset
*) malloc(sizeof (struct kwset
));
obstack_init(&kwset
->obstack
);
= (struct trie
*) obstack_alloc(&kwset
->obstack
, sizeof (struct trie
));
kwsfree((kwset_t
) kwset
);
kwset
->trie
->accepting
= 0;
/* Add the given string to the contents of the keyword set. Return NULL
for success, an error message otherwise. */
register struct trie
*trie
;
register unsigned char label
;
register struct tree
*link
;
struct tree
*t
, *r
, *l
, *rl
, *lr
;
kwset
= (struct kwset
*) kws
;
/* Descend the trie (built of reversed keywords) character-by-character,
installing new nodes when necessary. */
label
= kwset
->trans
? kwset
->trans
[(unsigned char) *--text
] : *--text
;
/* Descend the tree of outgoing links for this trie node,
looking for the current character and keeping track
links
[0] = (struct tree
*) &trie
->links
;
while (link
&& label
!= link
->label
)
dirs
[depth
++] = L
, link
= link
->llink
;
dirs
[depth
++] = R
, link
= link
->rlink
;
/* The current character doesn't have an outgoing link at
this trie node, so build a new trie node and install
a link in the current trie node's tree. */
link
= (struct tree
*) obstack_alloc(&kwset
->obstack
,
return "memory exhausted";
link
->trie
= (struct trie
*) obstack_alloc(&kwset
->obstack
,
return "memory exhausted";
link
->trie
->accepting
= 0;
link
->trie
->parent
= trie
;
link
->trie
->depth
= trie
->depth
+ 1;
/* Install the new tree node in its parent. */
links
[depth
]->llink
= link
;
links
[depth
]->rlink
= link
;
/* Back up the tree fixing the balance flags. */
while (depth
&& !links
[depth
]->balance
)
/* Rebalance the tree by pointer rotations if necessary. */
if (depth
&& ((dirs
[depth
] == L
&& --links
[depth
]->balance
)
|| (dirs
[depth
] == R
&& ++links
[depth
]->balance
)))
switch (links
[depth
]->balance
)
r
= links
[depth
], t
= r
->llink
, rl
= t
->rlink
;
t
->rlink
= r
, r
->llink
= rl
;
t
->balance
= r
->balance
= 0;
r
= links
[depth
], l
= r
->llink
, t
= l
->rlink
;
rl
= t
->rlink
, lr
= t
->llink
;
t
->llink
= l
, l
->rlink
= lr
, t
->rlink
= r
, r
->llink
= rl
;
l
->balance
= t
->balance
!= 1 ? 0 : -1;
r
->balance
= t
->balance
!= (char) -1 ? 0 : 1;
l
= links
[depth
], t
= l
->rlink
, lr
= t
->llink
;
t
->llink
= l
, l
->rlink
= lr
;
t
->balance
= l
->balance
= 0;
l
= links
[depth
], r
= l
->rlink
, t
= r
->llink
;
lr
= t
->llink
, rl
= t
->rlink
;
t
->llink
= l
, l
->rlink
= lr
, t
->rlink
= r
, r
->llink
= rl
;
l
->balance
= t
->balance
!= 1 ? 0 : -1;
r
->balance
= t
->balance
!= (char) -1 ? 0 : 1;
if (dirs
[depth
- 1] == L
)
links
[depth
- 1]->llink
= t
;
links
[depth
- 1]->rlink
= t
;
/* Mark the node we finally reached as accepting, encoding the
index number of this word in the keyword set so far. */
trie
->accepting
= 1 + 2 * kwset
->words
;
/* Keep track of the longest and shortest string of the keyword set. */
if (trie
->depth
< kwset
->mind
)
kwset
->mind
= trie
->depth
;
if (trie
->depth
> kwset
->maxd
)
kwset
->maxd
= trie
->depth
;
/* Enqueue the trie nodes referenced from the given tree in the
enqueue(tree
->llink
, last
);
enqueue(tree
->rlink
, last
);
(*last
) = (*last
)->next
= tree
->trie
;
/* Compute the Aho-Corasick failure function for the trie nodes referenced
from the given tree, given the failure function for their parent as
well as a last resort failure node. */
treefails(tree
, fail
, recourse
)
register struct tree
*tree
;
register struct tree
*link
;
treefails(tree
->llink
, fail
, recourse
);
treefails(tree
->rlink
, fail
, recourse
);
/* Find, in the chain of fails going back to the root, the first
node that has a descendent on the current label. */
while (link
&& tree
->label
!= link
->label
)
if (tree
->label
< link
->label
)
tree
->trie
->fail
= link
->trie
;
tree
->trie
->fail
= recourse
;
/* Set delta entries for the links of the given tree such that
the preexisting delta value is larger than the current depth. */
treedelta(tree
, depth
, delta
)
register struct tree
*tree
;
register unsigned int depth
;
treedelta(tree
->llink
, depth
, delta
);
treedelta(tree
->rlink
, depth
, delta
);
if (depth
< delta
[tree
->label
])
delta
[tree
->label
] = depth
;
/* Return true if A has every label in B. */
if (!hasevery(a
, b
->llink
))
if (!hasevery(a
, b
->rlink
))
while (a
&& b
->label
!= a
->label
)
/* Compute a vector, indexed by character code, of the trie nodes
referenced from the given tree. */
treenext(tree
->llink
, next
);
treenext(tree
->rlink
, next
);
next
[tree
->label
] = tree
->trie
;
/* Compute the shift for each trie node, as well as the delta
table and next cache for the given keyword set. */
register struct kwset
*kwset
;
register struct trie
*curr
, *fail
;
unsigned char delta
[NCHAR
];
struct trie
*last
, *next
[NCHAR
];
kwset
= (struct kwset
*) kws
;
/* Initial values for the delta table; will be changed later. The
delta entry for a given character is the smallest depth of any
node at which an outgoing edge is labeled by that character. */
for (i
= 0; i
< NCHAR
; ++i
)
for (i
= 0; i
< NCHAR
; ++i
)
/* Check if we can use the simple boyer-moore algorithm, instead
of the hairy commentz-walter algorithm. */
if (kwset
->words
== 1 && kwset
->trans
== 0)
/* Looking for just one string. Extract it from the trie. */
kwset
->target
= obstack_alloc(&kwset
->obstack
, kwset
->mind
);
for (i
= kwset
->mind
- 1, curr
= kwset
->trie
; i
>= 0; --i
)
kwset
->target
[i
] = curr
->links
->label
;
curr
= curr
->links
->trie
;
/* Build the Boyer Moore delta. Boy that's easy compared to CW. */
for (i
= 0; i
< kwset
->mind
; ++i
)
delta
[(unsigned char) kwset
->target
[i
]] = kwset
->mind
- (i
+ 1);
kwset
->mind2
= kwset
->mind
;
/* Find the minimal delta2 shift that we might make after
a backwards match has failed. */
for (i
= 0; i
< kwset
->mind
- 1; ++i
)
if (kwset
->target
[i
] == kwset
->target
[kwset
->mind
- 1])
kwset
->mind2
= kwset
->mind
- (i
+ 1);
/* Traverse the nodes of the trie in level order, simultaneously
computing the delta table, failure function, and shift function. */
for (curr
= last
= kwset
->trie
; curr
; curr
= curr
->next
)
/* Enqueue the immediate descendents in the level order queue. */
enqueue(curr
->links
, &last
);
curr
->shift
= kwset
->mind
;
curr
->maxshift
= kwset
->mind
;
/* Update the delta table for the descendents of this node. */
treedelta(curr
->links
, curr
->depth
, delta
);
/* Compute the failure function for the decendents of this node. */
treefails(curr
->links
, curr
->fail
, kwset
->trie
);
/* Update the shifts at each node in the current node's chain
of fails back to the root. */
for (fail
= curr
->fail
; fail
; fail
= fail
->fail
)
/* If the current node has some outgoing edge that the fail
doesn't, then the shift at the fail should be no larger
than the difference of their depths. */
if (!hasevery(fail
->links
, curr
->links
))
if (curr
->depth
- fail
->depth
< fail
->shift
)
fail
->shift
= curr
->depth
- fail
->depth
;
/* If the current node is accepting then the shift at the
fail and its descendents should be no larger than the
difference of their depths. */
if (curr
->accepting
&& fail
->maxshift
> curr
->depth
- fail
->depth
)
fail
->maxshift
= curr
->depth
- fail
->depth
;
/* Traverse the trie in level order again, fixing up all nodes whose
shift exceeds their inherited maxshift. */
for (curr
= kwset
->trie
->next
; curr
; curr
= curr
->next
)
if (curr
->maxshift
> curr
->parent
->maxshift
)
curr
->maxshift
= curr
->parent
->maxshift
;
if (curr
->shift
> curr
->maxshift
)
curr
->shift
= curr
->maxshift
;
/* Create a vector, indexed by character code, of the outgoing links
for (i
= 0; i
< NCHAR
; ++i
)
treenext(kwset
->trie
->links
, next
);
if ((trans
= kwset
->trans
) != 0)
for (i
= 0; i
< NCHAR
; ++i
)
kwset
->next
[i
] = next
[(unsigned char) trans
[i
]];
for (i
= 0; i
< NCHAR
; ++i
)
kwset
->next
[i
] = next
[i
];
/* Fix things up for any translation table. */
if ((trans
= kwset
->trans
) != 0)
for (i
= 0; i
< NCHAR
; ++i
)
kwset
->delta
[i
] = delta
[(unsigned char) trans
[i
]];
for (i
= 0; i
< NCHAR
; ++i
)
kwset
->delta
[i
] = delta
[i
];
#define U(C) ((unsigned char) (C))
/* Fast boyer-moore search. */
register unsigned char *d1
;
register char *ep
, *sp
, *tp
;
register int d
, gc
, i
, len
, md2
;
kwset
= (struct kwset
*) kws
;
return memchr(text
, kwset
->target
[0], size
);
sp
= kwset
->target
+ len
;
/* Significance of 12: 1 (initial offset) + 10 (skip loop) + 1 (md2). */
/* 11 is not a bug, the initial offset happens only once. */
for (ep
= text
+ size
- 11 * len
;;)
d
= d1
[U(tp
[-1])], tp
+= d
;
d
= d1
[U(tp
[-1])], tp
+= d
;
d
= d1
[U(tp
[-1])], tp
+= d
;
d
= d1
[U(tp
[-1])], tp
+= d
;
d
= d1
[U(tp
[-1])], tp
+= d
;
d
= d1
[U(tp
[-1])], tp
+= d
;
d
= d1
[U(tp
[-1])], tp
+= d
;
d
= d1
[U(tp
[-1])], tp
+= d
;
d
= d1
[U(tp
[-1])], tp
+= d
;
d
= d1
[U(tp
[-1])], tp
+= d
;
for (i
= 3; i
<= len
&& U(tp
[-i
]) == U(sp
[-i
]); ++i
)
/* Now we have only a few characters left to search. We
carefully avoid ever producing an out-of-bounds pointer. */
d
= d1
[U((tp
+= d
)[-1])];
for (i
= 3; i
<= len
&& U(tp
[-i
]) == U(sp
[-i
]); ++i
)
/* Hairy multiple string search. */
cwexec(kws
, text
, len
, kwsmatch
)
struct kwsmatch
*kwsmatch
;
struct trie
**next
, *trie
, *accept
;
char *beg
, *lim
, *mch
, *lmch
;
register unsigned char c
, *delta
;
register char *end
, *qlim
;
register struct tree
*tree
;
/* Initialize register copies and look for easy ways out. */
kwset
= (struct kwset
*) kws
;
if ((d
= kwset
->mind
) != 0)
mch
= text
, accept
= kwset
->trie
;
if (len
>= 4 * kwset
->mind
)
qlim
= lim
- 4 * kwset
->mind
;
while ((d
= delta
[c
= *end
]) && end
< qlim
)
end
+= delta
[(unsigned char) *end
];
end
+= delta
[(unsigned char) *end
];
d
= delta
[c
= (end
+= d
)[-1]];
c
= trans
? trans
[(unsigned char) *--beg
] : *--beg
;
while (tree
&& c
!= tree
->label
)
/* Given a known match, find the longest possible match anchored
at or before its starting point. This is nearly a verbatim
copy of the preceding main search loops. */
if (lim
- mch
> kwset
->maxd
)
if ((d
= delta
[c
= (end
+= d
)[-1]]) != 0)
if (trie
->accepting
&& beg
<= mch
)
c
= trans
? trans
[(unsigned char) *--beg
] : *--beg
;
while (tree
&& c
!= tree
->label
)
if (trie
->accepting
&& beg
<= mch
)
kwsmatch
->index
= accept
->accepting
/ 2;
kwsmatch
->size
[0] = accept
->depth
;
/* Search through the given text for a match of any member of the
given keyword set. Return a pointer to the first character of
the matching substring, or NULL if no match is found. If FOUNDLEN
is non-NULL store in the referenced location the length of the
matching substring. Similarly, if FOUNDIDX is non-NULL, store
in the referenced location the index number of the particular
kwsexec(kws
, text
, size
, kwsmatch
)
struct kwsmatch
*kwsmatch
;
kwset
= (struct kwset
*) kws
;
if (kwset
->words
== 1 && kwset
->trans
== 0)
ret
= bmexec(kws
, text
, size
);
if (kwsmatch
!= 0 && ret
!= 0)
kwsmatch
->size
[0] = kwset
->mind
;
return cwexec(kws
, text
, size
, kwsmatch
);
/* Free the components of the given keyword set. */
kwset
= (struct kwset
*) kws
;
obstack_free(&kwset
->obstack
, 0);