Lines Matching refs:tree
63 * Primitive splay tree operations.
86 * The tree is stored in an unassembled form. If ist_root is null,
87 * then the tree has no entries. Otherwise, ist_name records
89 * middle tree obtained from the top-down splay. ist_ltree and
91 * are all smaller (larger) than those in the middle tree.
105 * When descending down the tree, child pointers are reversed
109 * The biggest potential problem with the splay tree implementation
112 * the splay tree doesn't require its own lock, and ist_lock/ist_unlock
118 * there is hope. Use a read/write lock on the splay tree.
119 * Keep track of the number of entries in the tree. When doing
121 * with a bound (based on log of size of the tree) on the number of
125 * of the tree, then lookups run in parallel and do no restructuring.
128 * If that is a problem, the tree could be changed from an lchild/rchild
145 * Searches for the node labeled name in the splay tree.
149 * ipc_splay_prim_lookup splits the supplied tree into
153 * If name is present in the tree, then it is at
154 * the root of the middle tree. Otherwise, the root
155 * of the middle tree is the last node traversed.
167 ipc_tree_entry_t tree,
177 assert(tree != ITE_NULL);
181 *ltreep = tree; \
182 ltreep = &tree->ite_rchild; \
183 tree = *ltreep; \
188 *rtreep = tree; \
189 rtreep = &tree->ite_lchild; \
190 tree = *rtreep; \
195 ipc_tree_entry_t temp = tree; \
197 tree = temp->ite_rchild; \
198 temp->ite_rchild = tree->ite_lchild; \
199 tree->ite_lchild = temp; \
204 ipc_tree_entry_t temp = tree; \
206 tree = temp->ite_lchild; \
207 temp->ite_lchild = tree->ite_rchild; \
208 tree->ite_rchild = temp; \
211 while (name != (tname = tree->ite_name)) {
215 lchild = tree->ite_lchild;
230 rchild = tree->ite_rchild;
244 assert(tree != ITE_NULL);
247 *treep = tree;
261 * into a splay tree with the found node at the root.
269 ipc_tree_entry_t tree,
275 assert(tree != ITE_NULL);
277 *ltreep = tree->ite_lchild;
278 *rtreep = tree->ite_rchild;
280 tree->ite_lchild = *ltree;
281 tree->ite_rchild = *rtree;
287 * Initialize a raw splay tree for use.
300 * Picks and returns a random entry in a splay tree.
301 * Returns FALSE if the splay tree is empty.
328 * Finds an entry in a splay tree.
366 * Inserts a new entry into a splay tree.
368 * The name can't already be present in the tree.
427 * Deletes an entry from a splay tree.
428 * The name must be present in the tree.
499 * Split a splay tree. Puts all entries smaller than "name"
500 * into a new tree, "small".
503 * should be fiddling with the uninitialized tree.
618 /* get smallest entry in splay tree to top */
652 * in the tree that is smaller than or equal to the name,
659 * and name is present in the tree
661 * then the tree is empty
663 * and upper is smallest value in tree
665 * and lower is largest value in tree
746 * Perform a symmetric order traversal of a splay tree.
756 * is removed from the tree and deallocated.
758 * During the traversal, the splay tree is locked.
809 /* we must delete current and patch the tree */