Changeset e3ee9b9 in mainline

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)

Location:

kernel/generic/src

Files:

• adt/btree.c (modified) (22 diffs)
• cpu/cpu.c (modified) (1 diff)
• mm/as.c (modified) (9 diffs)
• mm/page.c (modified) (1 diff)
• proc/the.c (modified) (2 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");
 }

kernel/generic/src/cpu/cpu.c

@@ -119 +119 @@
 /** @}
  */
-

kernel/generic/src/mm/as.c

@@ -116 +116 @@
 as_t *AS_KERNEL = NULL;
 
-static unsigned int area_flags_to_page_flags(unsigned int);
-static as_area_t *find_area_and_lock(as_t *, uintptr_t);
-static bool check_area_conflicts(as_t *, uintptr_t, size_t, as_area_t *);
-static void sh_info_remove_reference(share_info_t *);
-
 static int as_constructor(void *obj, unsigned int flags)
 {
@@ -296 +291 @@
         if (atomic_predec(&as->refcount) == 0)
                 as_destroy(as);
+}
+
+/** Check area conflicts with other areas.
+ *
+ * @param as         Address space.
+ * @param va         Starting virtual address of the area being tested.
+ * @param size       Size of the area being tested.
+ * @param avoid_area Do not touch this area.
+ *
+ * @return True if there is no conflict, false otherwise.
+ *
+ */
+static bool check_area_conflicts(as_t *as, uintptr_t va, size_t size,
+    as_area_t *avoid_area)
+{
+        ASSERT(mutex_locked(&as->lock));
+        
+        /*
+         * We don't want any area to have conflicts with NULL page.
+         *
+         */
+        if (overlaps(va, size, NULL, PAGE_SIZE))
+                return false;
+        
+        /*
+         * The leaf node is found in O(log n), where n is proportional to
+         * the number of address space areas belonging to as.
+         * The check for conflicts is then attempted on the rightmost
+         * record in the left neighbour, the leftmost record in the right
+         * neighbour and all records in the leaf node itself.
+         *
+         */
+        btree_node_t *leaf;
+        as_area_t *area =
+            (as_area_t *) btree_search(&as->as_area_btree, va, &leaf);
+        if (area) {
+                if (area != avoid_area)
+                        return false;
+        }
+        
+        /* First, check the two border cases. */
+        btree_node_t *node =
+            btree_leaf_node_left_neighbour(&as->as_area_btree, leaf);
+        if (node) {
+                area = (as_area_t *) node->value[node->keys - 1];
+                
+                mutex_lock(&area->lock);
+                
+                if (overlaps(va, size, area->base, area->pages * PAGE_SIZE)) {
+                        mutex_unlock(&area->lock);
+                        return false;
+                }
+                
+                mutex_unlock(&area->lock);
+        }
+        
+        node = btree_leaf_node_right_neighbour(&as->as_area_btree, leaf);
+        if (node) {
+                area = (as_area_t *) node->value[0];
+                
+                mutex_lock(&area->lock);
+                
+                if (overlaps(va, size, area->base, area->pages * PAGE_SIZE)) {
+                        mutex_unlock(&area->lock);
+                        return false;
+                }
+                
+                mutex_unlock(&area->lock);
+        }
+        
+        /* Second, check the leaf node. */
+        btree_key_t i;
+        for (i = 0; i < leaf->keys; i++) {
+                area = (as_area_t *) leaf->value[i];
+                
+                if (area == avoid_area)
+                        continue;
+                
+                mutex_lock(&area->lock);
+                
+                if (overlaps(va, size, area->base, area->pages * PAGE_SIZE)) {
+                        mutex_unlock(&area->lock);
+                        return false;
+                }
+                
+                mutex_unlock(&area->lock);
+        }
+        
+        /*
+         * So far, the area does not conflict with other areas.
+         * Check if it doesn't conflict with kernel address space.
+         *
+         */
+        if (!KERNEL_ADDRESS_SPACE_SHADOWED) {
+                return !overlaps(va, size,
+                    KERNEL_ADDRESS_SPACE_START,
+                    KERNEL_ADDRESS_SPACE_END - KERNEL_ADDRESS_SPACE_START);
+        }
+        
+        return true;
 }
 
@@ -357 +452 @@
         
         return area;
+}
+
+/** Find address space area and lock it.
+ *
+ * @param as Address space.
+ * @param va Virtual address.
+ *
+ * @return Locked address space area containing va on success or
+ *         NULL on failure.
+ *
+ */
+static as_area_t *find_area_and_lock(as_t *as, uintptr_t va)
+{
+        ASSERT(mutex_locked(&as->lock));
+        
+        btree_node_t *leaf;
+        as_area_t *area = (as_area_t *) btree_search(&as->as_area_btree, va, &leaf);
+        if (area) {
+                /* va is the base address of an address space area */
+                mutex_lock(&area->lock);
+                return area;
+        }
+        
+        /*
+         * Search the leaf node and the righmost record of its left neighbour
+         * to find out whether this is a miss or va belongs to an address
+         * space area found there.
+         *
+         */
+        
+        /* First, search the leaf node itself. */
+        btree_key_t i;
+        
+        for (i = 0; i < leaf->keys; i++) {
+                area = (as_area_t *) leaf->value[i];
+                
+                mutex_lock(&area->lock);
+                
+                if ((area->base <= va) && (va < area->base + area->pages * PAGE_SIZE))
+                        return area;
+                
+                mutex_unlock(&area->lock);
+        }
+        
+        /*
+         * Second, locate the left neighbour and test its last record.
+         * Because of its position in the B+tree, it must have base < va.
+         *
+         */
+        btree_node_t *lnode = btree_leaf_node_left_neighbour(&as->as_area_btree, leaf);
+        if (lnode) {
+                area = (as_area_t *) lnode->value[lnode->keys - 1];
+                
+                mutex_lock(&area->lock);
+                
+                if (va < area->base + area->pages * PAGE_SIZE)
+                        return area;
+                
+                mutex_unlock(&area->lock);
+        }
+        
+        return NULL;
 }
 
@@ -553 +710 @@
 }
 
+/** Remove reference to address space area share info.
+ *
+ * If the reference count drops to 0, the sh_info is deallocated.
+ *
+ * @param sh_info Pointer to address space area share info.
+ *
+ */
+static void sh_info_remove_reference(share_info_t *sh_info)
+{
+        bool dealloc = false;
+        
+        mutex_lock(&sh_info->lock);
+        ASSERT(sh_info->refcount);
+        
+        if (--sh_info->refcount == 0) {
+                dealloc = true;
+                link_t *cur;
+                
+                /*
+                 * Now walk carefully the pagemap B+tree and free/remove
+                 * reference from all frames found there.
+                 */
+                for (cur = sh_info->pagemap.leaf_head.next;
+                    cur != &sh_info->pagemap.leaf_head; cur = cur->next) {
+                        btree_node_t *node
+                            = list_get_instance(cur, btree_node_t, leaf_link);
+                        btree_key_t i;
+                        
+                        for (i = 0; i < node->keys; i++)
+                                frame_free((uintptr_t) node->value[i]);
+                }
+                
+        }
+        mutex_unlock(&sh_info->lock);
+        
+        if (dealloc) {
+                btree_destroy(&sh_info->pagemap);
+                free(sh_info);
+        }
+}
+
 /** Destroy address space area.
  *
@@ -805 +1003 @@
 }
 
+/** Convert address space area flags to page flags.
+ *
+ * @param aflags Flags of some address space area.
+ *
+ * @return Flags to be passed to page_mapping_insert().
+ *
+ */
+static unsigned int area_flags_to_page_flags(unsigned int aflags)
+{
+        unsigned int flags = PAGE_USER | PAGE_PRESENT;
+        
+        if (aflags & AS_AREA_READ)
+                flags |= PAGE_READ;
+                
+        if (aflags & AS_AREA_WRITE)
+                flags |= PAGE_WRITE;
+        
+        if (aflags & AS_AREA_EXEC)
+                flags |= PAGE_EXEC;
+        
+        if (aflags & AS_AREA_CACHEABLE)
+                flags |= PAGE_CACHEABLE;
+        
+        return flags;
+}
+
 /** Change adress space area flags.
  *
@@ -1161 +1385 @@
 }
 
-/** Convert address space area flags to page flags.
- *
- * @param aflags Flags of some address space area.
- *
- * @return Flags to be passed to page_mapping_insert().
- *
- */
-unsigned int area_flags_to_page_flags(unsigned int aflags)
-{
-        unsigned int flags = PAGE_USER | PAGE_PRESENT;
-        
-        if (aflags & AS_AREA_READ)
-                flags |= PAGE_READ;
-                
-        if (aflags & AS_AREA_WRITE)
-                flags |= PAGE_WRITE;
-        
-        if (aflags & AS_AREA_EXEC)
-                flags |= PAGE_EXEC;
-        
-        if (aflags & AS_AREA_CACHEABLE)
-                flags |= PAGE_CACHEABLE;
-        
-        return flags;
-}
+
 
 /** Compute flags for virtual address translation subsytem.
@@ -1272 +1472 @@
 /** Test whether page tables are locked.
  *
- * @param as            Address space where the page tables belong.
- *
- * @return              True if the page tables belonging to the address soace
- *                      are locked, otherwise false.
+ * @param as Address space where the page tables belong.
+ *
+ * @return True if the page tables belonging to the address soace
+ *         are locked, otherwise false.
  */
 bool page_table_locked(as_t *as)
@@ -1283 +1483 @@
 
         return as_operations->page_table_locked(as);
-}
-
-
-/** Find address space area and lock it.
- *
- * @param as Address space.
- * @param va Virtual address.
- *
- * @return Locked address space area containing va on success or
- *         NULL on failure.
- *
- */
-as_area_t *find_area_and_lock(as_t *as, uintptr_t va)
-{
-        ASSERT(mutex_locked(&as->lock));
-
-        btree_node_t *leaf;
-        as_area_t *area = (as_area_t *) btree_search(&as->as_area_btree, va, &leaf);
-        if (area) {
-                /* va is the base address of an address space area */
-                mutex_lock(&area->lock);
-                return area;
-        }
-        
-        /*
-         * Search the leaf node and the righmost record of its left neighbour
-         * to find out whether this is a miss or va belongs to an address
-         * space area found there.
-         *
-         */
-        
-        /* First, search the leaf node itself. */
-        btree_key_t i;
-        
-        for (i = 0; i < leaf->keys; i++) {
-                area = (as_area_t *) leaf->value[i];
-                
-                mutex_lock(&area->lock);
-                
-                if ((area->base <= va) && (va < area->base + area->pages * PAGE_SIZE))
-                        return area;
-                
-                mutex_unlock(&area->lock);
-        }
-        
-        /*
-         * Second, locate the left neighbour and test its last record.
-         * Because of its position in the B+tree, it must have base < va.
-         *
-         */
-        btree_node_t *lnode = btree_leaf_node_left_neighbour(&as->as_area_btree, leaf);
-        if (lnode) {
-                area = (as_area_t *) lnode->value[lnode->keys - 1];
-                
-                mutex_lock(&area->lock);
-                
-                if (va < area->base + area->pages * PAGE_SIZE)
-                        return area;
-                
-                mutex_unlock(&area->lock);
-        }
-        
-        return NULL;
-}
-
-/** Check area conflicts with other areas.
- *
- * @param as         Address space.
- * @param va         Starting virtual address of the area being tested.
- * @param size       Size of the area being tested.
- * @param avoid_area Do not touch this area.
- *
- * @return True if there is no conflict, false otherwise.
- *
- */
-bool check_area_conflicts(as_t *as, uintptr_t va, size_t size,
-    as_area_t *avoid_area)
-{
-        ASSERT(mutex_locked(&as->lock));
-
-        /*
-         * We don't want any area to have conflicts with NULL page.
-         *
-         */
-        if (overlaps(va, size, NULL, PAGE_SIZE))
-                return false;
-        
-        /*
-         * The leaf node is found in O(log n), where n is proportional to
-         * the number of address space areas belonging to as.
-         * The check for conflicts is then attempted on the rightmost
-         * record in the left neighbour, the leftmost record in the right
-         * neighbour and all records in the leaf node itself.
-         *
-         */
-        btree_node_t *leaf;
-        as_area_t *area =
-            (as_area_t *) btree_search(&as->as_area_btree, va, &leaf);
-        if (area) {
-                if (area != avoid_area)
-                        return false;
-        }
-        
-        /* First, check the two border cases. */
-        btree_node_t *node =
-            btree_leaf_node_left_neighbour(&as->as_area_btree, leaf);
-        if (node) {
-                area = (as_area_t *) node->value[node->keys - 1];
-                
-                mutex_lock(&area->lock);
-                
-                if (overlaps(va, size, area->base, area->pages * PAGE_SIZE)) {
-                        mutex_unlock(&area->lock);
-                        return false;
-                }
-                
-                mutex_unlock(&area->lock);
-        }
-        
-        node = btree_leaf_node_right_neighbour(&as->as_area_btree, leaf);
-        if (node) {
-                area = (as_area_t *) node->value[0];
-                
-                mutex_lock(&area->lock);
-                
-                if (overlaps(va, size, area->base, area->pages * PAGE_SIZE)) {
-                        mutex_unlock(&area->lock);
-                        return false;
-                }
-                
-                mutex_unlock(&area->lock);
-        }
-        
-        /* Second, check the leaf node. */
-        btree_key_t i;
-        for (i = 0; i < leaf->keys; i++) {
-                area = (as_area_t *) leaf->value[i];
-                
-                if (area == avoid_area)
-                        continue;
-                
-                mutex_lock(&area->lock);
-                
-                if (overlaps(va, size, area->base, area->pages * PAGE_SIZE)) {
-                        mutex_unlock(&area->lock);
-                        return false;
-                }
-                
-                mutex_unlock(&area->lock);
-        }
-        
-        /*
-         * So far, the area does not conflict with other areas.
-         * Check if it doesn't conflict with kernel address space.
-         *
-         */
-        if (!KERNEL_ADDRESS_SPACE_SHADOWED) {
-                return !overlaps(va, size,
-                    KERNEL_ADDRESS_SPACE_START,
-                    KERNEL_ADDRESS_SPACE_END - KERNEL_ADDRESS_SPACE_START);
-        }
-        
-        return true;
 }
 
@@ -1960 +1997 @@
 }
 
-/** Remove reference to address space area share info.
- *
- * If the reference count drops to 0, the sh_info is deallocated.
- *
- * @param sh_info Pointer to address space area share info.
- *
- */
-void sh_info_remove_reference(share_info_t *sh_info)
-{
-        bool dealloc = false;
-        
-        mutex_lock(&sh_info->lock);
-        ASSERT(sh_info->refcount);
-        
-        if (--sh_info->refcount == 0) {
-                dealloc = true;
-                link_t *cur;
-                
-                /*
-                 * Now walk carefully the pagemap B+tree and free/remove
-                 * reference from all frames found there.
-                 */
-                for (cur = sh_info->pagemap.leaf_head.next;
-                    cur != &sh_info->pagemap.leaf_head; cur = cur->next) {
-                        btree_node_t *node
-                            = list_get_instance(cur, btree_node_t, leaf_link);
-                        btree_key_t i;
-                        
-                        for (i = 0; i < node->keys; i++)
-                                frame_free((uintptr_t) node->value[i]);
-                }
-                
-        }
-        mutex_unlock(&sh_info->lock);
-        
-        if (dealloc) {
-                btree_destroy(&sh_info->pagemap);
-                free(sh_info);
-        }
-}
-
 /*
  * Address space related syscalls.

kernel/generic/src/mm/page.c

@@ -38 +38 @@
  * mappings between virtual addresses and physical addresses.
  * Functions here are mere wrappers that call the real implementation.
- * They however, define the single interface. 
+ * They however, define the single interface.
  *
  */

kernel/generic/src/proc/the.c

@@ -33 +33 @@
 /**
  * @file
- * @brief       THE structure functions.
+ * @brief THE structure functions.
  *
  * This file contains functions to manage the THE structure.
@@ -43 +43 @@
 
 #include <arch.h>
-
 
 /** Initialize THE structure