+/* Ways that nodes can be inserted. */
+enum insertion_method
+ {
+ INSERT, /* With abt_insert. */
+ INSERT_AFTER, /* With abt_insert_after. */
+ INSERT_BEFORE /* With abt_insert_before. */
+ };
+
+/* Inserts INSERT into ABT with the given METHOD. */
+static void
+insert_node (struct abt *abt, struct element *insert,
+ enum insertion_method method)
+{
+ if (method == INSERT)
+ check (abt_insert (abt, &insert->node) == NULL);
+ else
+ {
+ struct abt_node *p = abt->root;
+ int dir = 0;
+ if (p != NULL)
+ for (;;)
+ {
+ dir = insert->data > abt_node_to_element (p)->data;
+ if (p->down[dir] == NULL)
+ break;
+ p = p->down[dir];
+ }
+ if (method == INSERT_AFTER)
+ {
+ if (p != NULL && (dir != 1 || p->down[1] != NULL))
+ p = abt_prev (abt, p);
+ abt_insert_after (abt, p, &insert->node);
+ }
+ else
+ {
+ if (p != NULL && (dir != 0 || p->down[0] != NULL))
+ p = abt_next (abt, p);
+ abt_insert_before (abt, p, &insert->node);
+ }
+ }
+}
+
+