usr.bin/grep/kwset.c

51 /* Balanced tree of edges and labels leaving a given trie node. */
56   struct trie *trie;		/* Trie node pointed to by this edge. */
61 /* Node of a trie representing a set of reversed keywords. */
62 struct trie
66   struct trie *parent;		/* Parent of this node. */
67   struct trie *next;		/* List of all trie nodes in level order. */
68   struct trie *fail;		/* Aho-Corasick failure function. */
78   int words;			/* Number of words in the trie. */
79   struct trie *trie;		/* The trie itself. */
83   struct trie *next[NCHAR];	/* Table of children of the root. */
102   kwset->trie
103     = (struct trie *) obstack_alloc(&kwset->obstack, sizeof (struct trie));
104   if (!kwset->trie)
109   kwset->trie->accepting = 0;
110   kwset->trie->links = 0;
111   kwset->trie->parent = 0;
112   kwset->trie->next = 0;
113   kwset->trie->fail = 0;
114   kwset->trie->depth = 0;
115   kwset->trie->shift = 0;
130   register struct trie *trie;
139   trie = kwset->trie;
142   /* Descend the trie (built of reversed keywords) character-by-character,
148       /* Descend the tree of outgoing links for this trie node,
151       link = trie->links;
152       links[0] = (struct tree *) &trie->links;
166 	 this trie node, so build a new trie node and install
167 	 a link in the current trie node's tree. */
176 	  link->trie = (struct trie *) obstack_alloc(&kwset->obstack,
177 						     sizeof (struct trie));
178 	  if (!link->trie)
180 	  link->trie->accepting = 0;
181 	  link->trie->links = 0;
182 	  link->trie->parent = trie;
183 	  link->trie->next = 0;
184 	  link->trie->fail = 0;
185 	  link->trie->depth = trie->depth + 1;
186 	  link->trie->shift = 0;
263       trie = link->trie;
268   if (!trie->accepting)
269     trie->accepting = 1 + 2 * kwset->words;
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)
290   (*last) = (*last)->next = tree->trie;
293 /* Compute the Aho-Corasick failure function for the trie nodes referenced
297 treefails (register struct tree const *tree, struct trie const *fail,
298 	   struct trie *recourse)
320 	  tree->trie->fail = link->trie;
326   tree->trie->fail = recourse;
362 /* Compute a vector, indexed by character code, of the trie nodes
365 treenext (struct tree const *tree, struct trie *next[])
371   next[tree->label] = tree->trie;
374 /* Compute the shift for each trie node, as well as the delta
381   register struct trie *curr, *fail;
384   struct trie *last, *next[NCHAR];
402       /* Looking for just one string.  Extract it from the trie. */
404       for (i = kwset->mind - 1, curr = kwset->trie; i >= 0; --i)
407 	  curr = curr->links->trie;
421       /* Traverse the nodes of the trie in level order, simultaneously
423       for (curr = last = kwset->trie; curr; curr = curr->next)
435 	  treefails(curr->links, curr->fail, kwset->trie);
456       /* Traverse the trie in level order again, fixing up all nodes whose
458       for (curr = kwset->trie->next; curr; curr = curr->next)
470       treenext(kwset->trie->links, next);
584   struct trie * const *next;
585   struct trie const *trie;
586   struct trie const *accept;
612       mch = text, accept = kwset->trie;
639       trie = next[c];
640       if (trie->accepting)
643 	  accept = trie;
645       d = trie->shift;
649 	  tree = trie->links;
657 	      trie = tree->trie;
658 	      if (trie->accepting)
661 		  accept = trie;
666 	  d = trie->shift;
686       if (!(trie = next[c]))
691       if (trie->accepting && beg <= mch)
694 	  accept = trie;
696       d = trie->shift;
700 	  tree = trie->links;
708 	      trie = tree->trie;
709 	      if (trie->accepting && beg <= mch)
712 		  accept = trie;
717 	  d = trie->shift;