usr.bin/grep/kwset.c

51 /* Balanced tree of edges and labels leaving a given trie node. */
52 struct tree
54   struct tree *llink;		/* Left link; MUST be first field. */
55   struct tree *rlink;		/* Right link (to larger labels). */
65   struct tree *links;		/* Tree of edges leaving this node. */
132   register struct tree *link;
134   struct tree *links[12];
136   struct tree *t, *r, *l, *rl, *lr;
148       /* Descend the tree of outgoing links for this trie node,
152       links[0] = (struct tree *) &trie->links;
167 	 a link in the current trie node's tree. */
170 	  link = (struct tree *) obstack_alloc(&kwset->obstack,
171 					       sizeof (struct tree));
190 	  /* Install the new tree node in its parent. */
196 	  /* Back up the tree fixing the balance flags. */
206 	  /* Rebalance the tree by pointer rotations if necessary. */
281 /* Enqueue the trie nodes referenced from the given tree in the
284 enqueue (struct tree *tree, struct trie **last)
286   if (!tree)
288   enqueue(tree->llink, last);
289   enqueue(tree->rlink, last);
290   (*last) = (*last)->next = tree->trie;
294    from the given tree, given the failure function for their parent as
297 treefails (register struct tree const *tree, struct trie const *fail,
300   register struct tree *link;
302   if (!tree)
305   treefails(tree->llink, fail, recourse);
306   treefails(tree->rlink, fail, recourse);
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
332 treedelta (register struct tree const *tree,
336   if (!tree)
338   treedelta(tree->llink, depth, delta);
339   treedelta(tree->rlink, depth, delta);
340   if (depth < delta[tree->label])
341     delta[tree->label] = depth;
346 hasevery (register struct tree const *a, register struct tree const *b)
363    referenced from the given tree. */
365 treenext (struct tree const *tree, struct trie *next[])
367   if (!tree)
369   treenext(tree->llink, next);
370   treenext(tree->rlink, next);
371   next[tree->label] = tree->trie;
592   register struct tree const *tree;
649 	  tree = trie->links;
650 	  while (tree && c != tree->label)
651 	    if (c < tree->label)
652 	      tree = tree->llink;
654 	      tree = tree->rlink;
655 	  if (tree)
657 	      trie = tree->trie;
700 	  tree = trie->links;
701 	  while (tree && c != tree->label)
702 	    if (c < tree->label)
703 	      tree = tree->llink;
705 	      tree = tree->rlink;
706 	  if (tree)
708 	      trie = tree->trie;