/* Performs root insertion of |n| at |root| within |tree|. Subtree |root| must not contain a node matching |n|. Returns nonzero only if successful. */ static int root_insert (struct bst_table *tree, struct bst_node **root, struct bst_node *n) { struct bst_node *pa[BST_MAX_HEIGHT]; /* Nodes on stack. */ unsigned char da[BST_MAX_HEIGHT]; /* Directions moved from stack nodes. */ int k; /* Stack height. */ struct bst_node *p; /* Traverses tree looking for insertion point. */ assert (tree != NULL && n != NULL); pa[0] = (struct bst_node *) root; da[0] = 0; k = 1; for (p = *root; p != NULL; p = p->bst_link[da[k - 1]]) { int cmp = tree->bst_compare (n->bst_data, p->bst_data, tree->bst_param); assert (cmp != 0); if (k >= BST_MAX_HEIGHT) return 0; pa[k] = p; da[k++] = cmp > 0; } pa[k - 1]->bst_link[da[k - 1]] = n; for (; k > 1; k--) { struct bst_node *q = pa[k - 1]; if (da[k - 1] == 0) { q->bst_link[0] = n->bst_link[1]; n->bst_link[1] = q; } else /* |da[k - 1] == 1| */ { q->bst_link[1] = n->bst_link[0]; n->bst_link[0] = q; } pa[k - 2]->bst_link[da[k - 2]] = n; } return 1; }