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

Timestamp:

2010-07-02T12:44:00Z (14 years ago)

Author:

Martin Decky <martin@…>

Branches:

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

Children:

7a0359b, cefb126, e2ea4ab1

Parents:

b5382d4f

Message:

remove forward static function declarations and reorder functions
(if not needed for recursion, forward static function declaration only increases source code size and makes it much harder to instantly tell whether a function is actually static or not)

coding style changes
(no change in functionality)

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.
@@ -54 +54 @@
 #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))]);
-
 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.
+ *
+ */
+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 +103 @@
  *
  * @param t B-tree.
+ *
  */
 void btree_create(btree_t *t)
@@ -103 +113 @@
 }
 
-/** 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)
+ *
+ */
+static void btree_destroy_subtree(btree_node_t *root)
 {
         size_t i;
-
+        
         if (root->keys) {
                 for (i = 0; i < root->keys + 1; i++) { 
@@ -146 +128 @@
                 }
         }
+        
         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.
+ *
+ */
+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.
+ *
+ */
+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.
+ *
+ */
+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.
+ *
+ */
+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.
+ *
+ */
+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.
+ *
+ */
+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.
+ *
+ */
+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.
+ *
+ */
+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.
+ *
+ */
+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.
+ *
+ */
+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.
+ *
+ */
+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 +579 @@
                  * 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 +598 @@
                          * 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.
+ *
+ */
+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.
+ *
+ */
+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.
+ *
+ */
+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)
+ *
+ */
+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 +783 @@
                         node_remove_key_and_rsubtree(node, key);
                 }
+                
                 return;
         }
@@ -271 +798 @@
         if (node->keys > FILL_FACTOR) {
                 size_t i;
-
+                
                 /*
                  * The key can be immediatelly removed.
@@ -280 +807 @@
                  */
                 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 +826 @@
                 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 +837 @@
 }
 
+/** 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 +876 @@
          */
         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 +892 @@
                         void *val;
                         size_t i;
-                
+                        
                         /*
                          * Now if the key is smaller than cur->key[i]
@@ -347 +902 @@
                                         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 +933 @@
 /** 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 +952 @@
 /** 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 +969 @@
 }
 
-/** 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 +979 @@
         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 +1003 @@
                         depth = node->depth;
                 }
-
+                
                 printf("(");
+                
                 for (i = 0; i < node->keys; i++) {
                         printf("%" PRIu64 "%s", node->key[i], i < node->keys - 1 ? "," : "");
@@ -976 +1012 @@
                         }
                 }
-                if (node->depth && node->subtree[i]) {
+                
+                if (node->depth && node->subtree[i])
                         list_append(&node->subtree[i]->bfs_link, &head);
-                }
+                
                 printf(")");
         }
+        
         printf("\n");
         
@@ -990 +1028 @@
                 
                 ASSERT(node);
-
+                
                 printf("(");
+                
                 for (i = 0; i < node->keys; i++)
                         printf("%" PRIu64 "%s", node->key[i], i < node->keys - 1 ? "," : "");
+                
                 printf(")");
         }
+        
         printf("\n");
 }