/* Refreshes the stack of parent pointers in |trav| and updates its generation number. */ static void trav_refresh (struct avl_traverser *trav) { assert (trav != NULL); trav->avl_generation = trav->avl_table->avl_generation; if (trav->avl_node != NULL) { avl_comparison_func *cmp = trav->avl_table->avl_compare; void *param = trav->avl_table->avl_param; struct avl_node *node = trav->avl_node; struct avl_node *i; trav->avl_height = 0; for (i = trav->avl_table->avl_root; i != node; ) { assert (trav->avl_height < AVL_MAX_HEIGHT); assert (i != NULL); trav->avl_stack[trav->avl_height++] = i; i = i->avl_link[cmp (node->avl_data, i->avl_data, param) > 0]; } } } /* Initializes |trav| for use with |tree| and selects the null node. */ void avl_t_init (struct avl_traverser *trav, struct avl_table *tree) { trav->avl_table = tree; trav->avl_node = NULL; trav->avl_height = 0; trav->avl_generation = tree->avl_generation; } /* Initializes |trav| for |tree| and selects and returns a pointer to its least-valued item. Returns |NULL| if |tree| contains no nodes. */ void * avl_t_first (struct avl_traverser *trav, struct avl_table *tree) { struct avl_node *x; assert (tree != NULL && trav != NULL); trav->avl_table = tree; trav->avl_height = 0; trav->avl_generation = tree->avl_generation; x = tree->avl_root; if (x != NULL) while (x->avl_link[0] != NULL) { assert (trav->avl_height < AVL_MAX_HEIGHT); trav->avl_stack[trav->avl_height++] = x; x = x->avl_link[0]; } trav->avl_node = x; return x != NULL ? x->avl_data : NULL; } /* Initializes |trav| for |tree| and selects and returns a pointer to its greatest-valued item. Returns |NULL| if |tree| contains no nodes. */ void * avl_t_last (struct avl_traverser *trav, struct avl_table *tree) { struct avl_node *x; assert (tree != NULL && trav != NULL); trav->avl_table = tree; trav->avl_height = 0; trav->avl_generation = tree->avl_generation; x = tree->avl_root; if (x != NULL) while (x->avl_link[1] != NULL) { assert (trav->avl_height < AVL_MAX_HEIGHT); trav->avl_stack[trav->avl_height++] = x; x = x->avl_link[1]; } trav->avl_node = x; return x != NULL ? x->avl_data : NULL; } /* Searches for |item| in |tree|. If found, initializes |trav| to the item found and returns the item as well. If there is no matching item, initializes |trav| to the null item and returns |NULL|. */ void * avl_t_find (struct avl_traverser *trav, struct avl_table *tree, void *item) { struct avl_node *p, *q; assert (trav != NULL && tree != NULL && item != NULL); trav->avl_table = tree; trav->avl_height = 0; trav->avl_generation = tree->avl_generation; for (p = tree->avl_root; p != NULL; p = q) { int cmp = tree->avl_compare (item, p->avl_data, tree->avl_param); if (cmp < 0) q = p->avl_link[0]; else if (cmp > 0) q = p->avl_link[1]; else /* |cmp == 0| */ { trav->avl_node = p; return p->avl_data; } assert (trav->avl_height < AVL_MAX_HEIGHT); trav->avl_stack[trav->avl_height++] = p; } trav->avl_height = 0; trav->avl_node = NULL; return NULL; } /* Attempts to insert |item| into |tree|. If |item| is inserted successfully, it is returned and |trav| is initialized to its location. If a duplicate is found, it is returned and |trav| is initialized to its location. No replacement of the item occurs. If a memory allocation failure occurs, |NULL| is returned and |trav| is initialized to the null item. */ void * avl_t_insert (struct avl_traverser *trav, struct avl_table *tree, void *item) { void **p; assert (trav != NULL && tree != NULL && item != NULL); p = avl_probe (tree, item); if (p != NULL) { trav->avl_table = tree; trav->avl_node = ((struct avl_node *) ((char *) p - offsetof (struct avl_node, avl_data))); trav->avl_generation = tree->avl_generation - 1; return *p; } else { avl_t_init (trav, tree); return NULL; } } /* Initializes |trav| to have the same current node as |src|. */ void * avl_t_copy (struct avl_traverser *trav, const struct avl_traverser *src) { assert (trav != NULL && src != NULL); if (trav != src) { trav->avl_table = src->avl_table; trav->avl_node = src->avl_node; trav->avl_generation = src->avl_generation; if (trav->avl_generation == trav->avl_table->avl_generation) { trav->avl_height = src->avl_height; memcpy (trav->avl_stack, (const void *) src->avl_stack, sizeof *trav->avl_stack * trav->avl_height); } } return trav->avl_node != NULL ? trav->avl_node->avl_data : NULL; } /* Returns the next data item in inorder within the tree being traversed with |trav|, or if there are no more data items returns |NULL|. */ void * avl_t_next (struct avl_traverser *trav) { struct avl_node *x; assert (trav != NULL); if (trav->avl_generation != trav->avl_table->avl_generation) trav_refresh (trav); x = trav->avl_node; if (x == NULL) { return avl_t_first (trav, trav->avl_table); } else if (x->avl_link[1] != NULL) { assert (trav->avl_height < AVL_MAX_HEIGHT); trav->avl_stack[trav->avl_height++] = x; x = x->avl_link[1]; while (x->avl_link[0] != NULL) { assert (trav->avl_height < AVL_MAX_HEIGHT); trav->avl_stack[trav->avl_height++] = x; x = x->avl_link[0]; } } else { struct avl_node *y; do { if (trav->avl_height == 0) { trav->avl_node = NULL; return NULL; } y = x; x = trav->avl_stack[--trav->avl_height]; } while (y == x->avl_link[1]); } trav->avl_node = x; return x->avl_data; } /* Returns the previous data item in inorder within the tree being traversed with |trav|, or if there are no more data items returns |NULL|. */ void * avl_t_prev (struct avl_traverser *trav) { struct avl_node *x; assert (trav != NULL); if (trav->avl_generation != trav->avl_table->avl_generation) trav_refresh (trav); x = trav->avl_node; if (x == NULL) { return avl_t_last (trav, trav->avl_table); } else if (x->avl_link[0] != NULL) { assert (trav->avl_height < AVL_MAX_HEIGHT); trav->avl_stack[trav->avl_height++] = x; x = x->avl_link[0]; while (x->avl_link[1] != NULL) { assert (trav->avl_height < AVL_MAX_HEIGHT); trav->avl_stack[trav->avl_height++] = x; x = x->avl_link[1]; } } else { struct avl_node *y; do { if (trav->avl_height == 0) { trav->avl_node = NULL; return NULL; } y = x; x = trav->avl_stack[--trav->avl_height]; } while (y == x->avl_link[0]); } trav->avl_node = x; return x->avl_data; } /* Returns |trav|'s current item. */ void * avl_t_cur (struct avl_traverser *trav) { assert (trav != NULL); return trav->avl_node != NULL ? trav->avl_node->avl_data : NULL; } /* Replaces the current item in |trav| by |new| and returns the item replaced. |trav| must not have the null item selected. The new item must not upset the ordering of the tree. */ void * avl_t_replace (struct avl_traverser *trav, void *new) { void *old; assert (trav != NULL && trav->avl_node != NULL && new != NULL); old = trav->avl_node->avl_data; trav->avl_node->avl_data = new; return old; }