Lines Matching refs:tree
50 /* Balanced tree of edges and labels leaving a given trie node. */
51 struct tree
53 struct tree *llink; /* Left link; MUST be first field. */
54 struct tree *rlink; /* Right link (to larger labels). */
64 struct tree *links; /* Tree of edges leaving this node. */
131 register struct tree *link;
133 struct tree *links[12];
135 struct tree *t, *r, *l, *rl, *lr;
147 /* Descend the tree of outgoing links for this trie node,
151 links[0] = (struct tree *) &trie->links;
166 a link in the current trie node's tree. */
169 link = (struct tree *) obstack_alloc(&kwset->obstack,
170 sizeof (struct tree));
189 /* Install the new tree node in its parent. */
195 /* Back up the tree fixing the balance flags. */
205 /* Rebalance the tree by pointer rotations if necessary. */
280 /* Enqueue the trie nodes referenced from the given tree in the
283 enqueue (struct tree *tree, struct trie **last)
285 if (!tree)
287 enqueue(tree->llink, last);
288 enqueue(tree->rlink, last);
289 (*last) = (*last)->next = tree->trie;
293 from the given tree, given the failure function for their parent as
296 treefails (register struct tree const *tree, struct trie const *fail,
299 register struct tree *link;
301 if (!tree)
304 treefails(tree->llink, fail, recourse);
305 treefails(tree->rlink, fail, recourse);
312 while (link && tree->label != link->label)
313 if (tree->label < link->label)
319 tree->trie->fail = link->trie;
325 tree->trie->fail = recourse;
328 /* Set delta entries for the links of the given tree such that
331 treedelta (register struct tree const *tree,
335 if (!tree)
337 treedelta(tree->llink, depth, delta);
338 treedelta(tree->rlink, depth, delta);
339 if (depth < delta[tree->label])
340 delta[tree->label] = depth;
345 hasevery (register struct tree const *a, register struct tree const *b)
362 referenced from the given tree. */
364 treenext (struct tree const *tree, struct trie *next[])
366 if (!tree)
368 treenext(tree->llink, next);
369 treenext(tree->rlink, next);
370 next[tree->label] = tree->trie;
591 register struct tree const *tree;
646 tree = trie->links;
647 while (tree && c != tree->label)
648 if (c < tree->label)
649 tree = tree->llink;
651 tree = tree->rlink;
652 if (tree)
654 trie = tree->trie;
697 tree = trie->links;
698 while (tree && c != tree->label)
699 if (c < tree->label)
700 tree = tree->llink;
702 tree = tree->rlink;
703 if (tree)
705 trie = tree->trie;