Changeset bd48f4c in mainline for kernel/generic/src/adt/btree.c

Timestamp:

2010-07-12T10:53:30Z (14 years ago)

Author:

Jiri Svoboda <jiri@…>

Branches:

lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export

Children:

bd11d3e

Parents:

c40e6ef (diff), bee2d4c (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Message:

Merge mainline changes.

File:

• kernel/generic/src/adt/btree.c (modified) (22 diffs)

kernel/generic/src/adt/btree.c

@@ -33 +33 @@
 /**
  * @file
- * @brief       B+tree implementation.
+ * @brief B+tree implementation.
  *
  * This file implements B+tree type and operations.
@@ -53 +53 @@
 #include <panic.h>
 #include <print.h>
-
-static void btree_destroy_subtree(btree_node_t *root);
-static void _btree_insert(btree_t *t, btree_key_t key, void *value, btree_node_t *rsubtree, btree_node_t *node);
-static void _btree_remove(btree_t *t, btree_key_t key, btree_node_t *node);
-static void node_initialize(btree_node_t *node);
-static void node_insert_key_and_lsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *lsubtree);
-static void node_insert_key_and_rsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree);
-static void node_remove_key_and_lsubtree(btree_node_t *node, btree_key_t key);
-static void node_remove_key_and_rsubtree(btree_node_t *node, btree_key_t key);
-static btree_node_t *node_split(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree, btree_key_t *median);
-static btree_node_t *node_combine(btree_node_t *node);
-static size_t find_key_by_subtree(btree_node_t *node, btree_node_t *subtree, bool right);
-static void rotate_from_right(btree_node_t *lnode, btree_node_t *rnode, size_t idx);
-static void rotate_from_left(btree_node_t *lnode, btree_node_t *rnode, size_t idx);
-static bool try_insert_by_rotation_to_left(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree);
-static bool try_insert_by_rotation_to_right(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree);
-static bool try_rotation_from_left(btree_node_t *rnode);
-static bool try_rotation_from_right(btree_node_t *lnode);
-
-#define ROOT_NODE(n)            (!(n)->parent)
-#define INDEX_NODE(n)           ((n)->subtree[0] != NULL)
-#define LEAF_NODE(n)            ((n)->subtree[0] == NULL)
-
-#define FILL_FACTOR             ((BTREE_M-1)/2)
-
-#define MEDIAN_LOW_INDEX(n)     (((n)->keys-1)/2)
-#define MEDIAN_HIGH_INDEX(n)    ((n)->keys/2)
-#define MEDIAN_LOW(n)           ((n)->key[MEDIAN_LOW_INDEX((n))]);
-#define MEDIAN_HIGH(n)          ((n)->key[MEDIAN_HIGH_INDEX((n))]);
+#include <trace.h>
 
 static slab_cache_t *btree_node_slab;
+
+#define ROOT_NODE(n)   (!(n)->parent)
+#define INDEX_NODE(n)  ((n)->subtree[0] != NULL)
+#define LEAF_NODE(n)   ((n)->subtree[0] == NULL)
+
+#define FILL_FACTOR  ((BTREE_M - 1) / 2)
+
+#define MEDIAN_LOW_INDEX(n)   (((n)->keys-1) / 2)
+#define MEDIAN_HIGH_INDEX(n)  ((n)->keys / 2)
+#define MEDIAN_LOW(n)         ((n)->key[MEDIAN_LOW_INDEX((n))]);
+#define MEDIAN_HIGH(n)        ((n)->key[MEDIAN_HIGH_INDEX((n))]);
 
 /** Initialize B-trees. */
 void btree_init(void)
 {
-        btree_node_slab = slab_cache_create("btree_node_slab", sizeof(btree_node_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED);
+        btree_node_slab = slab_cache_create("btree_node_slab",
+            sizeof(btree_node_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED);
+}
+
+/** Initialize B-tree node.
+ *
+ * @param node B-tree node.
+ *
+ */
+NO_TRACE static void node_initialize(btree_node_t *node)
+{
+        unsigned int i;
+        
+        node->keys = 0;
+        
+        /* Clean also space for the extra key. */
+        for (i = 0; i < BTREE_MAX_KEYS + 1; i++) {
+                node->key[i] = 0;
+                node->value[i] = NULL;
+                node->subtree[i] = NULL;
+        }
+        
+        node->subtree[i] = NULL;
+        node->parent = NULL;
+        
+        link_initialize(&node->leaf_link);
+        link_initialize(&node->bfs_link);
+        node->depth = 0;
 }
 
@@ -94 +104 @@
  *
  * @param t B-tree.
+ *
  */
 void btree_create(btree_t *t)
@@ -103 +114 @@
 }
 
-/** Destroy empty B-tree. */
-void btree_destroy(btree_t *t)
-{
-        btree_destroy_subtree(t->root);
-}
-
-/** Insert key-value pair into B-tree.
- *
- * @param t B-tree.
- * @param key Key to be inserted.
- * @param value Value to be inserted.
- * @param leaf_node Leaf node where the insertion should begin.
- */ 
-void btree_insert(btree_t *t, btree_key_t key, void *value, btree_node_t *leaf_node)
-{
-        btree_node_t *lnode;
-        
-        ASSERT(value);
-        
-        lnode = leaf_node;
-        if (!lnode) {
-                if (btree_search(t, key, &lnode)) {
-                        panic("B-tree %p already contains key %" PRIu64 ".", t, key);
-                }
-        }
-        
-        _btree_insert(t, key, value, NULL, lnode);
-}
-
 /** Destroy subtree rooted in a node.
  *
  * @param root Root of the subtree.
- */
-void btree_destroy_subtree(btree_node_t *root)
+ *
+ */
+NO_TRACE static void btree_destroy_subtree(btree_node_t *root)
 {
         size_t i;
-
+        
         if (root->keys) {
                 for (i = 0; i < root->keys + 1; i++) { 
@@ -146 +129 @@
                 }
         }
+        
         slab_free(btree_node_slab, root);
 }
 
+/** Destroy empty B-tree. */
+void btree_destroy(btree_t *t)
+{
+        btree_destroy_subtree(t->root);
+}
+
+/** Insert key-value-rsubtree triplet into B-tree node.
+ *
+ * It is actually possible to have more keys than BTREE_MAX_KEYS.
+ * This feature is used during splitting the node when the
+ * number of keys is BTREE_MAX_KEYS + 1. Insert by left rotation
+ * also makes use of this feature.
+ *
+ * @param node     B-tree node into wich the new key is to be inserted.
+ * @param key      The key to be inserted.
+ * @param value    Pointer to value to be inserted.
+ * @param rsubtree Pointer to the right subtree.
+ *
+ */
+NO_TRACE static void node_insert_key_and_rsubtree(btree_node_t *node,
+    btree_key_t key, void *value, btree_node_t *rsubtree)
+{
+        size_t i;
+        
+        for (i = 0; i < node->keys; i++) {
+                if (key < node->key[i]) {
+                        size_t j;
+                        
+                        for (j = node->keys; j > i; j--) {
+                                node->key[j] = node->key[j - 1];
+                                node->value[j] = node->value[j - 1];
+                                node->subtree[j + 1] = node->subtree[j];
+                        }
+                        
+                        break;
+                }
+        }
+        
+        node->key[i] = key;
+        node->value[i] = value;
+        node->subtree[i + 1] = rsubtree;
+        node->keys++;
+}
+
+/** Find key by its left or right subtree.
+ *
+ * @param node    B-tree node.
+ * @param subtree Left or right subtree of a key found in node.
+ * @param right   If true, subtree is a right subtree. If false,
+ *                subtree is a left subtree.
+ *
+ * @return Index of the key associated with the subtree.
+ *
+ */
+NO_TRACE static size_t find_key_by_subtree(btree_node_t *node,
+    btree_node_t *subtree, bool right)
+{
+        size_t i;
+        
+        for (i = 0; i < node->keys + 1; i++) {
+                if (subtree == node->subtree[i])
+                        return i - (int) (right != false);
+        }
+        
+        panic("Node %p does not contain subtree %p.", node, subtree);
+}
+
+/** Remove key and its left subtree pointer from B-tree node.
+ *
+ * Remove the key and eliminate gaps in node->key array.
+ * Note that the value pointer and the left subtree pointer
+ * is removed from the node as well.
+ *
+ * @param node B-tree node.
+ * @param key  Key to be removed.
+ *
+ */
+NO_TRACE static void node_remove_key_and_lsubtree(btree_node_t *node,
+    btree_key_t key)
+{
+        size_t i;
+        size_t j;
+        
+        for (i = 0; i < node->keys; i++) {
+                if (key == node->key[i]) {
+                        for (j = i + 1; j < node->keys; j++) {
+                                node->key[j - 1] = node->key[j];
+                                node->value[j - 1] = node->value[j];
+                                node->subtree[j - 1] = node->subtree[j];
+                        }
+                        
+                        node->subtree[j - 1] = node->subtree[j];
+                        node->keys--;
+                        
+                        return;
+                }
+        }
+        
+        panic("Node %p does not contain key %" PRIu64 ".", node, key);
+}
+
+/** Remove key and its right subtree pointer from B-tree node.
+ *
+ * Remove the key and eliminate gaps in node->key array.
+ * Note that the value pointer and the right subtree pointer
+ * is removed from the node as well.
+ *
+ * @param node B-tree node.
+ * @param key  Key to be removed.
+ *
+ */
+NO_TRACE static void node_remove_key_and_rsubtree(btree_node_t *node,
+    btree_key_t key)
+{
+        size_t i, j;
+        
+        for (i = 0; i < node->keys; i++) {
+                if (key == node->key[i]) {
+                        for (j = i + 1; j < node->keys; j++) {
+                                node->key[j - 1] = node->key[j];
+                                node->value[j - 1] = node->value[j];
+                                node->subtree[j] = node->subtree[j + 1];
+                        }
+                        
+                        node->keys--;
+                        return;
+                }
+        }
+        
+        panic("Node %p does not contain key %" PRIu64 ".", node, key);
+}
+
+/** Insert key-value-lsubtree triplet into B-tree node.
+ *
+ * It is actually possible to have more keys than BTREE_MAX_KEYS.
+ * This feature is used during insert by right rotation.
+ *
+ * @param node     B-tree node into wich the new key is to be inserted.
+ * @param key      The key to be inserted.
+ * @param value    Pointer to value to be inserted.
+ * @param lsubtree Pointer to the left subtree.
+ *
+ */
+NO_TRACE static void node_insert_key_and_lsubtree(btree_node_t *node,
+    btree_key_t key, void *value, btree_node_t *lsubtree)
+{
+        size_t i;
+        
+        for (i = 0; i < node->keys; i++) {
+                if (key < node->key[i]) {
+                        size_t j;
+                        
+                        for (j = node->keys; j > i; j--) {
+                                node->key[j] = node->key[j - 1];
+                                node->value[j] = node->value[j - 1];
+                                node->subtree[j + 1] = node->subtree[j];
+                        }
+                        
+                        node->subtree[j + 1] = node->subtree[j];
+                        break;
+                }
+        }
+        
+        node->key[i] = key;
+        node->value[i] = value;
+        node->subtree[i] = lsubtree;
+        
+        node->keys++;
+}
+
+/** Rotate one key-value-rsubtree triplet from the left sibling to the right sibling.
+ *
+ * The biggest key and its value and right subtree is rotated
+ * from the left node to the right. If the node is an index node,
+ * than the parent node key belonging to the left node takes part
+ * in the rotation.
+ *
+ * @param lnode Left sibling.
+ * @param rnode Right sibling.
+ * @param idx   Index of the parent node key that is taking part
+ *              in the rotation.
+ *
+ */
+NO_TRACE static void rotate_from_left(btree_node_t *lnode, btree_node_t *rnode,
+    size_t idx)
+{
+        btree_key_t key = lnode->key[lnode->keys - 1];
+        
+        if (LEAF_NODE(lnode)) {
+                void *value = lnode->value[lnode->keys - 1];
+                
+                node_remove_key_and_rsubtree(lnode, key);
+                node_insert_key_and_lsubtree(rnode, key, value, NULL);
+                lnode->parent->key[idx] = key;
+        } else {
+                btree_node_t *rsubtree = lnode->subtree[lnode->keys];
+                
+                node_remove_key_and_rsubtree(lnode, key);
+                node_insert_key_and_lsubtree(rnode, lnode->parent->key[idx], NULL, rsubtree);
+                lnode->parent->key[idx] = key;
+                
+                /* Fix parent link of the reconnected right subtree. */
+                rsubtree->parent = rnode;
+        }
+}
+
+/** Rotate one key-value-lsubtree triplet from the right sibling to the left sibling.
+ *
+ * The smallest key and its value and left subtree is rotated
+ * from the right node to the left. If the node is an index node,
+ * than the parent node key belonging to the right node takes part
+ * in the rotation.
+ *
+ * @param lnode Left sibling.
+ * @param rnode Right sibling.
+ * @param idx   Index of the parent node key that is taking part
+ *              in the rotation.
+ *
+ */
+NO_TRACE static void rotate_from_right(btree_node_t *lnode, btree_node_t *rnode,
+    size_t idx)
+{
+        btree_key_t key = rnode->key[0];
+        
+        if (LEAF_NODE(rnode)) {
+                void *value = rnode->value[0];
+                
+                node_remove_key_and_lsubtree(rnode, key);
+                node_insert_key_and_rsubtree(lnode, key, value, NULL);
+                rnode->parent->key[idx] = rnode->key[0];
+        } else {
+                btree_node_t *lsubtree = rnode->subtree[0];
+                
+                node_remove_key_and_lsubtree(rnode, key);
+                node_insert_key_and_rsubtree(lnode, rnode->parent->key[idx], NULL, lsubtree);
+                rnode->parent->key[idx] = key;
+                
+                /* Fix parent link of the reconnected left subtree. */
+                lsubtree->parent = lnode;
+        }
+}
+
+/** Insert key-value-rsubtree triplet and rotate the node to the left, if this operation can be done.
+ *
+ * Left sibling of the node (if it exists) is checked for free space.
+ * If there is free space, the key is inserted and the smallest key of
+ * the node is moved there. The index node which is the parent of both
+ * nodes is fixed.
+ *
+ * @param node     B-tree node.
+ * @param inskey   Key to be inserted.
+ * @param insvalue Value to be inserted.
+ * @param rsubtree Right subtree of inskey.
+ *
+ * @return True if the rotation was performed, false otherwise.
+ *
+ */
+NO_TRACE static bool try_insert_by_rotation_to_left(btree_node_t *node,
+    btree_key_t inskey, void *insvalue, btree_node_t *rsubtree)
+{
+        size_t idx;
+        btree_node_t *lnode;
+        
+        /*
+         * If this is root node, the rotation can not be done.
+         */
+        if (ROOT_NODE(node))
+                return false;
+        
+        idx = find_key_by_subtree(node->parent, node, true);
+        if ((int) idx == -1) {
+                /*
+                 * If this node is the leftmost subtree of its parent,
+                 * the rotation can not be done.
+                 */
+                return false;
+        }
+        
+        lnode = node->parent->subtree[idx];
+        if (lnode->keys < BTREE_MAX_KEYS) {
+                /*
+                 * The rotaion can be done. The left sibling has free space.
+                 */
+                node_insert_key_and_rsubtree(node, inskey, insvalue, rsubtree);
+                rotate_from_right(lnode, node, idx);
+                return true;
+        }
+        
+        return false;
+}
+
+/** Insert key-value-rsubtree triplet and rotate the node to the right, if this operation can be done.
+ *
+ * Right sibling of the node (if it exists) is checked for free space.
+ * If there is free space, the key is inserted and the biggest key of
+ * the node is moved there. The index node which is the parent of both
+ * nodes is fixed.
+ *
+ * @param node     B-tree node.
+ * @param inskey   Key to be inserted.
+ * @param insvalue Value to be inserted.
+ * @param rsubtree Right subtree of inskey.
+ *
+ * @return True if the rotation was performed, false otherwise.
+ *
+ */
+NO_TRACE static bool try_insert_by_rotation_to_right(btree_node_t *node,
+    btree_key_t inskey, void *insvalue, btree_node_t *rsubtree)
+{
+        size_t idx;
+        btree_node_t *rnode;
+        
+        /*
+         * If this is root node, the rotation can not be done.
+         */
+        if (ROOT_NODE(node))
+                return false;
+        
+        idx = find_key_by_subtree(node->parent, node, false);
+        if (idx == node->parent->keys) {
+                /*
+                 * If this node is the rightmost subtree of its parent,
+                 * the rotation can not be done.
+                 */
+                return false;
+        }
+        
+        rnode = node->parent->subtree[idx + 1];
+        if (rnode->keys < BTREE_MAX_KEYS) {
+                /*
+                 * The rotaion can be done. The right sibling has free space.
+                 */
+                node_insert_key_and_rsubtree(node, inskey, insvalue, rsubtree);
+                rotate_from_left(node, rnode, idx);
+                return true;
+        }
+        
+        return false;
+}
+
+/** Split full B-tree node and insert new key-value-right-subtree triplet.
+ *
+ * This function will split a node and return a pointer to a newly created
+ * node containing keys greater than or equal to the greater of medians
+ * (or median) of the old keys and the newly added key. It will also write
+ * the median key to a memory address supplied by the caller.
+ *
+ * If the node being split is an index node, the median will not be
+ * included in the new node. If the node is a leaf node,
+ * the median will be copied there.
+ *
+ * @param node     B-tree node wich is going to be split.
+ * @param key      The key to be inserted.
+ * @param value    Pointer to the value to be inserted.
+ * @param rsubtree Pointer to the right subtree of the key being added.
+ * @param median   Address in memory, where the median key will be stored.
+ *
+ * @return Newly created right sibling of node.
+ *
+ */
+NO_TRACE static btree_node_t *node_split(btree_node_t *node, btree_key_t key,
+    void *value, btree_node_t *rsubtree, btree_key_t *median)
+{
+        btree_node_t *rnode;
+        size_t i;
+        size_t j;
+        
+        ASSERT(median);
+        ASSERT(node->keys == BTREE_MAX_KEYS);
+        
+        /*
+         * Use the extra space to store the extra node.
+         */
+        node_insert_key_and_rsubtree(node, key, value, rsubtree);
+        
+        /*
+         * Compute median of keys.
+         */
+        *median = MEDIAN_HIGH(node);
+        
+        /*
+         * Allocate and initialize new right sibling.
+         */
+        rnode = (btree_node_t *) slab_alloc(btree_node_slab, 0);
+        node_initialize(rnode);
+        rnode->parent = node->parent;
+        rnode->depth = node->depth;
+        
+        /*
+         * Copy big keys, values and subtree pointers to the new right sibling.
+         * If this is an index node, do not copy the median.
+         */
+        i = (size_t) INDEX_NODE(node);
+        for (i += MEDIAN_HIGH_INDEX(node), j = 0; i < node->keys; i++, j++) {
+                rnode->key[j] = node->key[i];
+                rnode->value[j] = node->value[i];
+                rnode->subtree[j] = node->subtree[i];
+                
+                /*
+                 * Fix parent links in subtrees.
+                 */
+                if (rnode->subtree[j])
+                        rnode->subtree[j]->parent = rnode;
+        }
+        
+        rnode->subtree[j] = node->subtree[i];
+        if (rnode->subtree[j])
+                rnode->subtree[j]->parent = rnode;
+        
+        rnode->keys = j;  /* Set number of keys of the new node. */
+        node->keys /= 2;  /* Shrink the old node. */
+        
+        return rnode;
+}
+
 /** Recursively insert into B-tree.
  *
- * @param t B-tree.
- * @param key Key to be inserted.
- * @param value Value to be inserted.
+ * @param t        B-tree.
+ * @param key      Key to be inserted.
+ * @param value    Value to be inserted.
  * @param rsubtree Right subtree of the inserted key.
- * @param node Start inserting into this node.
- */
-void _btree_insert(btree_t *t, btree_key_t key, void *value, btree_node_t *rsubtree, btree_node_t *node)
+ * @param node     Start inserting into this node.
+ *
+ */
+NO_TRACE static void _btree_insert(btree_t *t, btree_key_t key, void *value,
+    btree_node_t *rsubtree, btree_node_t *node)
 {
         if (node->keys < BTREE_MAX_KEYS) {
@@ -183 +584 @@
                  * bigger keys (i.e. the new node) into its parent.
                  */
-
+                
                 rnode = node_split(node, key, value, rsubtree, &median);
-
+                
                 if (LEAF_NODE(node)) {
                         list_prepend(&rnode->leaf_link, &node->leaf_link);
@@ -202 +603 @@
                          * Left-hand side subtree will be the old root (i.e. node).
                          * Right-hand side subtree will be rnode.
-                         */                     
+                         */
                         t->root->subtree[0] = node;
-
+                        
                         t->root->depth = node->depth + 1;
                 }
                 _btree_insert(t, median, NULL, rnode, node->parent);
-        }       
-                
-}
-
-/** Remove B-tree node.
- *
- * @param t B-tree.
- * @param key Key to be removed from the B-tree along with its associated value.
- * @param leaf_node If not NULL, pointer to the leaf node where the key is found.
- */
-void btree_remove(btree_t *t, btree_key_t key, btree_node_t *leaf_node)
+        }
+}
+
+/** Insert key-value pair into B-tree.
+ *
+ * @param t         B-tree.
+ * @param key       Key to be inserted.
+ * @param value     Value to be inserted.
+ * @param leaf_node Leaf node where the insertion should begin.
+ *
+ */
+void btree_insert(btree_t *t, btree_key_t key, void *value,
+    btree_node_t *leaf_node)
 {
         btree_node_t *lnode;
+        
+        ASSERT(value);
         
         lnode = leaf_node;
         if (!lnode) {
-                if (!btree_search(t, key, &lnode)) {
-                        panic("B-tree %p does not contain key %" PRIu64 ".", t, key);
-                }
-        }
-        
-        _btree_remove(t, key, lnode);
+                if (btree_search(t, key, &lnode))
+                        panic("B-tree %p already contains key %" PRIu64 ".", t, key);
+        }
+        
+        _btree_insert(t, key, value, NULL, lnode);
+}
+
+/** Rotate in a key from the left sibling or from the index node, if this operation can be done.
+ *
+ * @param rnode Node into which to add key from its left sibling
+ *              or from the index node.
+ *
+ * @return True if the rotation was performed, false otherwise.
+ *
+ */
+NO_TRACE static bool try_rotation_from_left(btree_node_t *rnode)
+{
+        size_t idx;
+        btree_node_t *lnode;
+        
+        /*
+         * If this is root node, the rotation can not be done.
+         */
+        if (ROOT_NODE(rnode))
+                return false;
+        
+        idx = find_key_by_subtree(rnode->parent, rnode, true);
+        if ((int) idx == -1) {
+                /*
+                 * If this node is the leftmost subtree of its parent,
+                 * the rotation can not be done.
+                 */
+                return false;
+        }
+        
+        lnode = rnode->parent->subtree[idx];
+        if (lnode->keys > FILL_FACTOR) {
+                rotate_from_left(lnode, rnode, idx);
+                return true;
+        }
+        
+        return false;
+}
+
+/** Rotate in a key from the right sibling or from the index node, if this operation can be done.
+ *
+ * @param lnode Node into which to add key from its right sibling
+ *              or from the index node.
+ *
+ * @return True if the rotation was performed, false otherwise.
+ *
+ */
+NO_TRACE static bool try_rotation_from_right(btree_node_t *lnode)
+{
+        size_t idx;
+        btree_node_t *rnode;
+        
+        /*
+         * If this is root node, the rotation can not be done.
+         */
+        if (ROOT_NODE(lnode))
+                return false;
+        
+        idx = find_key_by_subtree(lnode->parent, lnode, false);
+        if (idx == lnode->parent->keys) {
+                /*
+                 * If this node is the rightmost subtree of its parent,
+                 * the rotation can not be done.
+                 */
+                return false;
+        }
+        
+        rnode = lnode->parent->subtree[idx + 1];
+        if (rnode->keys > FILL_FACTOR) {
+                rotate_from_right(lnode, rnode, idx);
+                return true;
+        }
+        
+        return false;
+}
+
+/** Combine node with any of its siblings.
+ *
+ * The siblings are required to be below the fill factor.
+ *
+ * @param node Node to combine with one of its siblings.
+ *
+ * @return Pointer to the rightmost of the two nodes.
+ *
+ */
+NO_TRACE static btree_node_t *node_combine(btree_node_t *node)
+{
+        size_t idx;
+        btree_node_t *rnode;
+        size_t i;
+        
+        ASSERT(!ROOT_NODE(node));
+        
+        idx = find_key_by_subtree(node->parent, node, false);
+        if (idx == node->parent->keys) {
+                /*
+                 * Rightmost subtree of its parent, combine with the left sibling.
+                 */
+                idx--;
+                rnode = node;
+                node = node->parent->subtree[idx];
+        } else
+                rnode = node->parent->subtree[idx + 1];
+        
+        /* Index nodes need to insert parent node key in between left and right node. */
+        if (INDEX_NODE(node))
+                node->key[node->keys++] = node->parent->key[idx];
+        
+        /* Copy the key-value-subtree triplets from the right node. */
+        for (i = 0; i < rnode->keys; i++) {
+                node->key[node->keys + i] = rnode->key[i];
+                node->value[node->keys + i] = rnode->value[i];
+                
+                if (INDEX_NODE(node)) {
+                        node->subtree[node->keys + i] = rnode->subtree[i];
+                        rnode->subtree[i]->parent = node;
+                }
+        }
+        
+        if (INDEX_NODE(node)) {
+                node->subtree[node->keys + i] = rnode->subtree[i];
+                rnode->subtree[i]->parent = node;
+        }
+        
+        node->keys += rnode->keys;
+        return rnode;
 }
 
 /** Recursively remove B-tree node.
  *
- * @param t B-tree.
- * @param key Key to be removed from the B-tree along with its associated value.
+ * @param t    B-tree.
+ * @param key  Key to be removed from the B-tree along with its associated value.
  * @param node Node where the key being removed resides.
- */
-void _btree_remove(btree_t *t, btree_key_t key, btree_node_t *node)
+ *
+ */
+NO_TRACE static void _btree_remove(btree_t *t, btree_key_t key,
+    btree_node_t *node)
 {
         if (ROOT_NODE(node)) {
-                if (node->keys == 1 && node->subtree[0]) {
+                if ((node->keys == 1) && (node->subtree[0])) {
                         /*
                          * Free the current root and set new root.
@@ -257 +789 @@
                         node_remove_key_and_rsubtree(node, key);
                 }
+                
                 return;
         }
@@ -271 +804 @@
         if (node->keys > FILL_FACTOR) {
                 size_t i;
-
+                
                 /*
                  * The key can be immediatelly removed.
@@ -280 +813 @@
                  */
                 node_remove_key_and_rsubtree(node, key);
+                
                 for (i = 0; i < node->parent->keys; i++) {
                         if (node->parent->key[i] == key)
                                 node->parent->key[i] = node->key[0];
                 }
-                
         } else {
                 size_t idx;
-                btree_node_t *rnode, *parent;
-
+                btree_node_t *rnode;
+                btree_node_t *parent;
+                
                 /*
                  * The node is below the fill factor as well as its left and right sibling.
@@ -298 +832 @@
                 node_remove_key_and_rsubtree(node, key);
                 rnode = node_combine(node);
+                
                 if (LEAF_NODE(rnode))
                         list_remove(&rnode->leaf_link);
+                
                 idx = find_key_by_subtree(parent, rnode, true);
                 ASSERT((int) idx != -1);
@@ -307 +843 @@
 }
 
+/** Remove B-tree node.
+ *
+ * @param t         B-tree.
+ * @param key       Key to be removed from the B-tree along
+ *                  with its associated value.
+ * @param leaf_node If not NULL, pointer to the leaf node where
+ *                  the key is found.
+ *
+ */
+void btree_remove(btree_t *t, btree_key_t key, btree_node_t *leaf_node)
+{
+        btree_node_t *lnode;
+        
+        lnode = leaf_node;
+        if (!lnode) {
+                if (!btree_search(t, key, &lnode))
+                        panic("B-tree %p does not contain key %" PRIu64 ".", t, key);
+        }
+        
+        _btree_remove(t, key, lnode);
+}
+
 /** Search key in a B-tree.
  *
- * @param t B-tree.
- * @param key Key to be searched.
+ * @param t         B-tree.
+ * @param key       Key to be searched.
  * @param leaf_node Address where to put pointer to visited leaf node.
  *
  * @return Pointer to value or NULL if there is no such key.
+ *
  */
 void *btree_search(btree_t *t, btree_key_t key, btree_node_t **leaf_node)
@@ -323 +882 @@
          */
         for (cur = t->root; cur; cur = next) {
-
-                /* Last iteration will set this with proper leaf node address. */
+                /*
+                 * Last iteration will set this with proper
+                 * leaf node address.
+                 */
                 *leaf_node = cur;
                 
@@ -337 +898 @@
                         void *val;
                         size_t i;
-                
+                        
                         /*
                          * Now if the key is smaller than cur->key[i]
@@ -347 +908 @@
                                         next = cur->subtree[i];
                                         val = cur->value[i - 1];
-
+                                        
                                         if (LEAF_NODE(cur))
                                                 return key == cur->key[i - 1] ? val : NULL;
-
+                                        
                                         goto descend;
-                                } 
+                                }
                         }
                         
                         /*
-                         * Last possibility is that the key is in the rightmost subtree.
+                         * Last possibility is that the key is
+                         * in the rightmost subtree.
                          */
                         next = cur->subtree[i];
                         val = cur->value[i - 1];
+                        
                         if (LEAF_NODE(cur))
                                 return key == cur->key[i - 1] ? val : NULL;
                 }
                 descend:
-                        ;
-        }
-
+                ;
+        }
+        
         /*
-         * The key was not found in the *leaf_node and is smaller than any of its keys.
+         * The key was not found in the *leaf_node and
+         * is smaller than any of its keys.
          */
         return NULL;
@@ -375 +939 @@
 /** Return pointer to B-tree leaf node's left neighbour.
  *
- * @param t B-tree.
+ * @param t    B-tree.
  * @param node Node whose left neighbour will be returned.
  *
- * @return Left neighbour of the node or NULL if the node does not have the left neighbour.
+ * @return Left neighbour of the node or NULL if the node
+ *         does not have the left neighbour.
+ *
  */
 btree_node_t *btree_leaf_node_left_neighbour(btree_t *t, btree_node_t *node)
 {
         ASSERT(LEAF_NODE(node));
+        
         if (node->leaf_link.prev != &t->leaf_head)
                 return list_get_instance(node->leaf_link.prev, btree_node_t, leaf_link);
@@ -391 +958 @@
 /** Return pointer to B-tree leaf node's right neighbour.
  *
- * @param t B-tree.
+ * @param t    B-tree.
  * @param node Node whose right neighbour will be returned.
  *
- * @return Right neighbour of the node or NULL if the node does not have the right neighbour.
+ * @return Right neighbour of the node or NULL if the node
+ *         does not have the right neighbour.
+ *
  */
 btree_node_t *btree_leaf_node_right_neighbour(btree_t *t, btree_node_t *node)
 {
         ASSERT(LEAF_NODE(node));
+        
         if (node->leaf_link.next != &t->leaf_head)
                 return list_get_instance(node->leaf_link.next, btree_node_t, leaf_link);
@@ -405 +975 @@
 }
 
-/** Initialize B-tree node.
- *
- * @param node B-tree node.
- */
-void node_initialize(btree_node_t *node)
-{
-        int i;
-
-        node->keys = 0;
-        
-        /* Clean also space for the extra key. */
-        for (i = 0; i < BTREE_MAX_KEYS + 1; i++) {
-                node->key[i] = 0;
-                node->value[i] = NULL;
-                node->subtree[i] = NULL;
-        }
-        node->subtree[i] = NULL;
-        
-        node->parent = NULL;
-        
-        link_initialize(&node->leaf_link);
-
-        link_initialize(&node->bfs_link);
-        node->depth = 0;
-}
-
-/** Insert key-value-lsubtree triplet into B-tree node.
- *
- * It is actually possible to have more keys than BTREE_MAX_KEYS.
- * This feature is used during insert by right rotation.
- *
- * @param node B-tree node into wich the new key is to be inserted.
- * @param key The key to be inserted.
- * @param value Pointer to value to be inserted.
- * @param lsubtree Pointer to the left subtree.
- */ 
-void node_insert_key_and_lsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *lsubtree)
-{
-        size_t i;
-
-        for (i = 0; i < node->keys; i++) {
-                if (key < node->key[i]) {
-                        size_t j;
-                
-                        for (j = node->keys; j > i; j--) {
-                                node->key[j] = node->key[j - 1];
-                                node->value[j] = node->value[j - 1];
-                                node->subtree[j + 1] = node->subtree[j];
-                        }
-                        node->subtree[j + 1] = node->subtree[j];
-                        break;  
-                }
-        }
-        node->key[i] = key;
-        node->value[i] = value;
-        node->subtree[i] = lsubtree;
-                        
-        node->keys++;
-}
-
-/** Insert key-value-rsubtree triplet into B-tree node.
- *
- * It is actually possible to have more keys than BTREE_MAX_KEYS.
- * This feature is used during splitting the node when the
- * number of keys is BTREE_MAX_KEYS + 1. Insert by left rotation
- * also makes use of this feature.
- *
- * @param node B-tree node into wich the new key is to be inserted.
- * @param key The key to be inserted.
- * @param value Pointer to value to be inserted.
- * @param rsubtree Pointer to the right subtree.
- */ 
-void node_insert_key_and_rsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree)
-{
-        size_t i;
-
-        for (i = 0; i < node->keys; i++) {
-                if (key < node->key[i]) {
-                        size_t j;
-                
-                        for (j = node->keys; j > i; j--) {
-                                node->key[j] = node->key[j - 1];
-                                node->value[j] = node->value[j - 1];
-                                node->subtree[j + 1] = node->subtree[j];
-                        }
-                        break;  
-                }
-        }
-        node->key[i] = key;
-        node->value[i] = value;
-        node->subtree[i + 1] = rsubtree;
-                        
-        node->keys++;
-}
-
-/** Remove key and its left subtree pointer from B-tree node.
- *
- * Remove the key and eliminate gaps in node->key array.
- * Note that the value pointer and the left subtree pointer
- * is removed from the node as well.
- *
- * @param node B-tree node.
- * @param key Key to be removed.
- */
-void node_remove_key_and_lsubtree(btree_node_t *node, btree_key_t key)
-{
-        size_t i, j;
-        
-        for (i = 0; i < node->keys; i++) {
-                if (key == node->key[i]) {
-                        for (j = i + 1; j < node->keys; j++) {
-                                node->key[j - 1] = node->key[j];
-                                node->value[j - 1] = node->value[j];
-                                node->subtree[j - 1] = node->subtree[j];
-                        }
-                        node->subtree[j - 1] = node->subtree[j];
-                        node->keys--;
-                        return;
-                }
-        }
-        panic("Node %p does not contain key %" PRIu64 ".", node, key);
-}
-
-/** Remove key and its right subtree pointer from B-tree node.
- *
- * Remove the key and eliminate gaps in node->key array.
- * Note that the value pointer and the right subtree pointer
- * is removed from the node as well.
- *
- * @param node B-tree node.
- * @param key Key to be removed.
- */
-void node_remove_key_and_rsubtree(btree_node_t *node, btree_key_t key)
-{
-        size_t i, j;
-        
-        for (i = 0; i < node->keys; i++) {
-                if (key == node->key[i]) {
-                        for (j = i + 1; j < node->keys; j++) {
-                                node->key[j - 1] = node->key[j];
-                                node->value[j - 1] = node->value[j];
-                                node->subtree[j] = node->subtree[j + 1];
-                        }
-                        node->keys--;
-                        return;
-                }
-        }
-        panic("Node %p does not contain key %" PRIu64 ".", node, key);
-}
-
-/** Split full B-tree node and insert new key-value-right-subtree triplet.
- *
- * This function will split a node and return a pointer to a newly created
- * node containing keys greater than or equal to the greater of medians
- * (or median) of the old keys and the newly added key. It will also write
- * the median key to a memory address supplied by the caller.
- *
- * If the node being split is an index node, the median will not be
- * included in the new node. If the node is a leaf node,
- * the median will be copied there.
- *
- * @param node B-tree node wich is going to be split.
- * @param key The key to be inserted.
- * @param value Pointer to the value to be inserted.
- * @param rsubtree Pointer to the right subtree of the key being added.
- * @param median Address in memory, where the median key will be stored.
- *
- * @return Newly created right sibling of node.
- */ 
-btree_node_t *node_split(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree, btree_key_t *median)
-{
-        btree_node_t *rnode;
-        size_t i, j;
-
-        ASSERT(median);
-        ASSERT(node->keys == BTREE_MAX_KEYS);
-
-        /*
-         * Use the extra space to store the extra node.
-         */
-        node_insert_key_and_rsubtree(node, key, value, rsubtree);
-
-        /*
-         * Compute median of keys.
-         */
-        *median = MEDIAN_HIGH(node);
-                
-        /*
-         * Allocate and initialize new right sibling.
-         */
-        rnode = (btree_node_t *) slab_alloc(btree_node_slab, 0);
-        node_initialize(rnode);
-        rnode->parent = node->parent;
-        rnode->depth = node->depth;
-        
-        /*
-         * Copy big keys, values and subtree pointers to the new right sibling.
-         * If this is an index node, do not copy the median.
-         */
-        i = (size_t) INDEX_NODE(node);
-        for (i += MEDIAN_HIGH_INDEX(node), j = 0; i < node->keys; i++, j++) {
-                rnode->key[j] = node->key[i];
-                rnode->value[j] = node->value[i];
-                rnode->subtree[j] = node->subtree[i];
-                
-                /*
-                 * Fix parent links in subtrees.
-                 */
-                if (rnode->subtree[j])
-                        rnode->subtree[j]->parent = rnode;
-                        
-        }
-        rnode->subtree[j] = node->subtree[i];
-        if (rnode->subtree[j])
-                rnode->subtree[j]->parent = rnode;
-
-        rnode->keys = j;        /* Set number of keys of the new node. */
-        node->keys /= 2;        /* Shrink the old node. */
-                
-        return rnode;
-}
-
-/** Combine node with any of its siblings.
- *
- * The siblings are required to be below the fill factor.
- *
- * @param node Node to combine with one of its siblings.
- *
- * @return Pointer to the rightmost of the two nodes.
- */
-btree_node_t *node_combine(btree_node_t *node)
-{
-        size_t idx;
-        btree_node_t *rnode;
-        size_t i;
-
-        ASSERT(!ROOT_NODE(node));
-        
-        idx = find_key_by_subtree(node->parent, node, false);
-        if (idx == node->parent->keys) {
-                /*
-                 * Rightmost subtree of its parent, combine with the left sibling.
-                 */
-                idx--;
-                rnode = node;
-                node = node->parent->subtree[idx];
-        } else {
-                rnode = node->parent->subtree[idx + 1];
-        }
-
-        /* Index nodes need to insert parent node key in between left and right node. */
-        if (INDEX_NODE(node))
-                node->key[node->keys++] = node->parent->key[idx];
-        
-        /* Copy the key-value-subtree triplets from the right node. */
-        for (i = 0; i < rnode->keys; i++) {
-                node->key[node->keys + i] = rnode->key[i];
-                node->value[node->keys + i] = rnode->value[i];
-                if (INDEX_NODE(node)) {
-                        node->subtree[node->keys + i] = rnode->subtree[i];
-                        rnode->subtree[i]->parent = node;
-                }
-        }
-        if (INDEX_NODE(node)) {
-                node->subtree[node->keys + i] = rnode->subtree[i];
-                rnode->subtree[i]->parent = node;
-        }
-
-        node->keys += rnode->keys;
-
-        return rnode;
-}
-
-/** Find key by its left or right subtree.
- *
- * @param node B-tree node.
- * @param subtree Left or right subtree of a key found in node.
- * @param right If true, subtree is a right subtree. If false, subtree is a left subtree.
- *
- * @return Index of the key associated with the subtree.
- */ 
-size_t find_key_by_subtree(btree_node_t *node, btree_node_t *subtree, bool right)
-{
-        size_t i;
-        
-        for (i = 0; i < node->keys + 1; i++) {
-                if (subtree == node->subtree[i])
-                        return i - (int) (right != false);
-        }
-        panic("Node %p does not contain subtree %p.", node, subtree);
-}
-
-/** Rotate one key-value-rsubtree triplet from the left sibling to the right sibling.
- *
- * The biggest key and its value and right subtree is rotated from the left node
- * to the right. If the node is an index node, than the parent node key belonging to
- * the left node takes part in the rotation.
- *
- * @param lnode Left sibling.
- * @param rnode Right sibling.
- * @param idx Index of the parent node key that is taking part in the rotation.
- */
-void rotate_from_left(btree_node_t *lnode, btree_node_t *rnode, size_t idx)
-{
-        btree_key_t key;
-
-        key = lnode->key[lnode->keys - 1];
-                
-        if (LEAF_NODE(lnode)) {
-                void *value;
-
-                value = lnode->value[lnode->keys - 1];
-                node_remove_key_and_rsubtree(lnode, key);
-                node_insert_key_and_lsubtree(rnode, key, value, NULL);
-                lnode->parent->key[idx] = key;
-        } else {
-                btree_node_t *rsubtree;
-
-                rsubtree = lnode->subtree[lnode->keys];
-                node_remove_key_and_rsubtree(lnode, key);
-                node_insert_key_and_lsubtree(rnode, lnode->parent->key[idx], NULL, rsubtree);
-                lnode->parent->key[idx] = key;
-
-                /* Fix parent link of the reconnected right subtree. */
-                rsubtree->parent = rnode;
-        }
-
-}
-
-/** Rotate one key-value-lsubtree triplet from the right sibling to the left sibling.
- *
- * The smallest key and its value and left subtree is rotated from the right node
- * to the left. If the node is an index node, than the parent node key belonging to
- * the right node takes part in the rotation.
- *
- * @param lnode Left sibling.
- * @param rnode Right sibling.
- * @param idx Index of the parent node key that is taking part in the rotation.
- */
-void rotate_from_right(btree_node_t *lnode, btree_node_t *rnode, size_t idx)
-{
-        btree_key_t key;
-
-        key = rnode->key[0];
-                
-        if (LEAF_NODE(rnode)) {
-                void *value;
-
-                value = rnode->value[0];
-                node_remove_key_and_lsubtree(rnode, key);
-                node_insert_key_and_rsubtree(lnode, key, value, NULL);
-                rnode->parent->key[idx] = rnode->key[0];
-        } else {
-                btree_node_t *lsubtree;
-
-                lsubtree = rnode->subtree[0];
-                node_remove_key_and_lsubtree(rnode, key);
-                node_insert_key_and_rsubtree(lnode, rnode->parent->key[idx], NULL, lsubtree);
-                rnode->parent->key[idx] = key;
-
-                /* Fix parent link of the reconnected left subtree. */
-                lsubtree->parent = lnode;
-        }
-
-}
-
-/** Insert key-value-rsubtree triplet and rotate the node to the left, if this operation can be done.
- *
- * Left sibling of the node (if it exists) is checked for free space.
- * If there is free space, the key is inserted and the smallest key of
- * the node is moved there. The index node which is the parent of both
- * nodes is fixed.
- *
- * @param node B-tree node.
- * @param inskey Key to be inserted.
- * @param insvalue Value to be inserted.
- * @param rsubtree Right subtree of inskey.
- *
- * @return True if the rotation was performed, false otherwise.
- */
-bool try_insert_by_rotation_to_left(btree_node_t *node, btree_key_t inskey, void *insvalue, btree_node_t *rsubtree)
-{
-        size_t idx;
-        btree_node_t *lnode;
-
-        /*
-         * If this is root node, the rotation can not be done.
-         */
-        if (ROOT_NODE(node))
-                return false;
-        
-        idx = find_key_by_subtree(node->parent, node, true);
-        if ((int) idx == -1) {
-                /*
-                 * If this node is the leftmost subtree of its parent,
-                 * the rotation can not be done.
-                 */
-                return false;
-        }
-                
-        lnode = node->parent->subtree[idx];
-        if (lnode->keys < BTREE_MAX_KEYS) {
-                /*
-                 * The rotaion can be done. The left sibling has free space.
-                 */
-                node_insert_key_and_rsubtree(node, inskey, insvalue, rsubtree);
-                rotate_from_right(lnode, node, idx);
-                return true;
-        }
-
-        return false;
-}
-
-/** Insert key-value-rsubtree triplet and rotate the node to the right, if this operation can be done.
- *
- * Right sibling of the node (if it exists) is checked for free space.
- * If there is free space, the key is inserted and the biggest key of
- * the node is moved there. The index node which is the parent of both
- * nodes is fixed.
- *
- * @param node B-tree node.
- * @param inskey Key to be inserted.
- * @param insvalue Value to be inserted.
- * @param rsubtree Right subtree of inskey.
- *
- * @return True if the rotation was performed, false otherwise.
- */
-bool try_insert_by_rotation_to_right(btree_node_t *node, btree_key_t inskey, void *insvalue, btree_node_t *rsubtree)
-{
-        size_t idx;
-        btree_node_t *rnode;
-
-        /*
-         * If this is root node, the rotation can not be done.
-         */
-        if (ROOT_NODE(node))
-                return false;
-        
-        idx = find_key_by_subtree(node->parent, node, false);
-        if (idx == node->parent->keys) {
-                /*
-                 * If this node is the rightmost subtree of its parent,
-                 * the rotation can not be done.
-                 */
-                return false;
-        }
-                
-        rnode = node->parent->subtree[idx + 1];
-        if (rnode->keys < BTREE_MAX_KEYS) {
-                /*
-                 * The rotaion can be done. The right sibling has free space.
-                 */
-                node_insert_key_and_rsubtree(node, inskey, insvalue, rsubtree);
-                rotate_from_left(node, rnode, idx);
-                return true;
-        }
-
-        return false;
-}
-
-/** Rotate in a key from the left sibling or from the index node, if this operation can be done.
- *
- * @param rnode Node into which to add key from its left sibling or from the index node.
- *
- * @return True if the rotation was performed, false otherwise.
- */
-bool try_rotation_from_left(btree_node_t *rnode)
-{
-        size_t idx;
-        btree_node_t *lnode;
-
-        /*
-         * If this is root node, the rotation can not be done.
-         */
-        if (ROOT_NODE(rnode))
-                return false;
-        
-        idx = find_key_by_subtree(rnode->parent, rnode, true);
-        if ((int) idx == -1) {
-                /*
-                 * If this node is the leftmost subtree of its parent,
-                 * the rotation can not be done.
-                 */
-                return false;
-        }
-                
-        lnode = rnode->parent->subtree[idx];
-        if (lnode->keys > FILL_FACTOR) {
-                rotate_from_left(lnode, rnode, idx);
-                return true;
-        }
-        
-        return false;
-}
-
-/** Rotate in a key from the right sibling or from the index node, if this operation can be done.
- *
- * @param lnode Node into which to add key from its right sibling or from the index node.
- *
- * @return True if the rotation was performed, false otherwise.
- */
-bool try_rotation_from_right(btree_node_t *lnode)
-{
-        size_t idx;
-        btree_node_t *rnode;
-
-        /*
-         * If this is root node, the rotation can not be done.
-         */
-        if (ROOT_NODE(lnode))
-                return false;
-        
-        idx = find_key_by_subtree(lnode->parent, lnode, false);
-        if (idx == lnode->parent->keys) {
-                /*
-                 * If this node is the rightmost subtree of its parent,
-                 * the rotation can not be done.
-                 */
-                return false;
-        }
-                
-        rnode = lnode->parent->subtree[idx + 1];
-        if (rnode->keys > FILL_FACTOR) {
-                rotate_from_right(lnode, rnode, idx);
-                return true;
-        }       
-
-        return false;
-}
-
 /** Print B-tree.
  *
  * @param t Print out B-tree.
+ *
  */
 void btree_print(btree_t *t)
@@ -944 +985 @@
         int depth = t->root->depth;
         link_t head, *cur;
-
+        
         printf("Printing B-tree:\n");
         list_initialize(&head);
         list_append(&t->root->bfs_link, &head);
-
+        
         /*
          * Use BFS search to print out the tree.
          * Levels are distinguished from one another by node->depth.
-         */     
+         */
         while (!list_empty(&head)) {
                 link_t *hlp;
@@ -968 +1009 @@
                         depth = node->depth;
                 }
-
+                
                 printf("(");
+                
                 for (i = 0; i < node->keys; i++) {
                         printf("%" PRIu64 "%s", node->key[i], i < node->keys - 1 ? "," : "");
@@ -976 +1018 @@
                         }
                 }
-                if (node->depth && node->subtree[i]) {
+                
+                if (node->depth && node->subtree[i])
                         list_append(&node->subtree[i]->bfs_link, &head);
-                }
+                
                 printf(")");
         }
+        
         printf("\n");
         
@@ -990 +1034 @@
                 
                 ASSERT(node);
-
+                
                 printf("(");
+                
                 for (i = 0; i < node->keys; i++)
                         printf("%" PRIu64 "%s", node->key[i], i < node->keys - 1 ? "," : "");
+                
                 printf(")");
         }
+        
         printf("\n");
 }