/* Performs a compression transformation |count| times, starting at |root|. */ static void compress (struct bst_node *root, unsigned long count) { assert (root != NULL); while (count--) { struct bst_node *red = root->bst_link[0]; struct bst_node *black = red->bst_link[0]; root->bst_link[0] = black; red->bst_link[0] = black->bst_link[1]; black->bst_link[1] = red; root = black; } } /* Converts |tree|, which must be in the shape of a vine, into a balanced tree. */ static void vine_to_tree (struct bst_table *tree) { unsigned long vine; /* Number of nodes in main vine. */ unsigned long leaves; /* Nodes in incomplete bottom level, if any. */ int height; /* Height of produced balanced tree. */ leaves = tree->bst_count + 1; for (;;) { unsigned long next = leaves & (leaves - 1); if (next == 0) break; leaves = next; } leaves = tree->bst_count + 1 - leaves; compress ((struct bst_node *) &tree->bst_root, leaves); vine = tree->bst_count - leaves; height = 1 + (leaves > 0); while (vine > 1) { compress ((struct bst_node *) &tree->bst_root, vine / 2); vine /= 2; height++; } if (height > BST_MAX_HEIGHT) { fprintf (stderr, "libavl: Tree too big (%lu nodes) to handle.", (unsigned long) tree->bst_count); exit (EXIT_FAILURE); } }