gettext-tools/libgrep/kwset.c

52 /* Balanced tree of edges and labels leaving a given trie node. */
57   struct trie *trie;		/* Trie node pointed to by this edge. */
62 /* Node of a trie representing a set of reversed keywords. */
63 struct trie
67   struct trie *parent;		/* Parent of this node. */
68   struct trie *next;		/* List of all trie nodes in level order. */
69   struct trie *fail;		/* Aho-Corasick failure function. */
79   int words;			/* Number of words in the trie. */
80   struct trie *trie;		/* The trie itself. */
84   struct trie *next[NCHAR];	/* Table of children of the root. */
103   kwset->trie
104     = (struct trie *) obstack_alloc(&kwset->obstack, sizeof (struct trie));
105   if (!kwset->trie)
110   kwset->trie->accepting = 0;
111   kwset->trie->links = 0;
112   kwset->trie->parent = 0;
113   kwset->trie->next = 0;
114   kwset->trie->fail = 0;
115   kwset->trie->depth = 0;
116   kwset->trie->shift = 0;
131   register struct trie *trie;
140   trie = kwset->trie;
143   /* Descend the trie (built of reversed keywords) character-by-character,
149       /* Descend the tree of outgoing links for this trie node,
152       link = trie->links;
153       links[0] = (struct tree *) &trie->links;
167 	 this trie node, so build a new trie node and install
168 	 a link in the current trie node's tree. */
177 	  link->trie = (struct trie *) obstack_alloc(&kwset->obstack,
178 						     sizeof (struct trie));
179 	  if (!link->trie)
181 	  link->trie->accepting = 0;
182 	  link->trie->links = 0;
183 	  link->trie->parent = trie;
184 	  link->trie->next = 0;
185 	  link->trie->fail = 0;
186 	  link->trie->depth = trie->depth + 1;
187 	  link->trie->shift = 0;
264       trie = link->trie;
269   if (!trie->accepting)
270     trie->accepting = 1 + 2 * kwset->words;
274   if (trie->depth < kwset->mind)
275     kwset->mind = trie->depth;
276   if (trie->depth > kwset->maxd)
277     kwset->maxd = trie->depth;
282 /* Enqueue the trie nodes referenced from the given tree in the
285 enqueue (struct tree *tree, struct trie **last)
291   (*last) = (*last)->next = tree->trie;
294 /* Compute the Aho-Corasick failure function for the trie nodes referenced
298 treefails (register struct tree const *tree, struct trie const *fail,
299 	   struct trie *recourse)
321 	  tree->trie->fail = link->trie;
327   tree->trie->fail = recourse;
363 /* Compute a vector, indexed by character code, of the trie nodes
366 treenext (struct tree const *tree, struct trie *next[])
372   next[tree->label] = tree->trie;
375 /* Compute the shift for each trie node, as well as the delta
382   register struct trie *curr, *fail;
385   struct trie *last, *next[NCHAR];
403       /* Looking for just one string.  Extract it from the trie. */
405       for (i = kwset->mind - 1, curr = kwset->trie; i >= 0; --i)
408 	  curr = curr->links->trie;
422       /* Traverse the nodes of the trie in level order, simultaneously
424       for (curr = last = kwset->trie; curr; curr = curr->next)
436 	  treefails(curr->links, curr->fail, kwset->trie);
457       /* Traverse the trie in level order again, fixing up all nodes whose
459       for (curr = kwset->trie->next; curr; curr = curr->next)
471       treenext(kwset->trie->links, next);
585   struct trie * const *next;
586   struct trie const *trie;
587   struct trie const *accept;
611       mch = text, accept = kwset->trie;
638       trie = next[c];
639       if (trie->accepting)
642 	  accept = trie;
644       d = trie->shift;
648 	  tree = trie->links;
656 	      trie = tree->trie;
657 	      if (trie->accepting)
660 		  accept = trie;
665 	  d = trie->shift;
685       if (!(trie = next[c]))
690       if (trie->accepting && beg <= mch)
693 	  accept = trie;
695       d = trie->shift;
699 	  tree = trie->links;
707 	      trie = tree->trie;
708 	      if (trie->accepting && beg <= mch)
711 		  accept = trie;
716 	  d = trie->shift;