Changeset e2ea4ab1 in mainline for kernel/generic/src

Timestamp:

2010-07-02T14:22:35Z (15 years ago)

Author:

Jakub Jermar <jakub@…>

Branches:

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

Children:

09b859c

Parents:

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

Message:

Merge mainline changes.

Location:

kernel/generic/src

Files:

• adt/btree.c (modified) (22 diffs)
• console/console.c (modified) (1 diff)
• cpu/cpu.c (modified) (1 diff)
• debug/debug.c (added)
• debug/stacktrace.c (modified) (1 diff)
• lib/sort.c (modified) (2 diffs)
• main/main.c (modified) (15 diffs)
• 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/console/console.c

@@ -294 +294 @@
                 stdout->op->write(stdout, ch, silent);
         else {
-                /* The character is just in the kernel log */
+                /*
+                 * No standard output routine defined yet.
+                 * The character is still stored in the kernel log
+                 * for possible future output.
+                 *
+                 * The early_putchar() function is used to output
+                 * the character for low-level debugging purposes.
+                 * Note that the early_putc() function might be
+                 * a no-op on certain hardware configurations.
+                 *
+                 */
+                early_putchar(ch);
+                
                 if (klog_stored < klog_len)
                         klog_stored++;

kernel/generic/src/cpu/cpu.c

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

kernel/generic/src/debug/stacktrace.c

@@ -52 +52 @@
                     ops->symbol_resolve(pc, &symbol, &offset)) {
                         if (offset)
-                                printf("%p: %s+%lx()\n", fp, symbol, offset);
+                                printf("%p: %s+%" PRIp "()\n", fp, symbol, offset);
                         else
                                 printf("%p: %s()\n", fp, symbol);

kernel/generic/src/lib/sort.c

@@ -27 +27 @@
  */
 
-/** @addtogroup generic 
+/** @addtogroup generic
  * @{
  */
@@ -33 +33 @@
 /**
  * @file
- * @brief       Sorting functions.
+ * @brief Sorting functions.
  *
  * This files contains functions implementing several sorting
- * algorithms (e.g. quick sort and bubble sort).
- */
- 
+ * algorithms (e.g. quick sort and gnome sort).
+ *
+ */
+
 #include <mm/slab.h>
 #include <memstr.h>
 #include <sort.h>
-#include <panic.h>
-
-#define EBUFSIZE        32
-
-void _qsort(void * data, size_t n, size_t e_size, int (* cmp) (void * a, void * b), void *tmp, void *pivot);
-void _bubblesort(void * data, size_t n, size_t e_size, int (* cmp) (void * a, void * b), void *slot);
-
-/** Quicksort wrapper
- *
- * This is only a wrapper that takes care of memory allocations for storing
- * the pivot and temporary elements for generic quicksort algorithm.
- * 
- * This function _can_ sleep
- *
- * @param data Pointer to data to be sorted.
- * @param n Number of elements to be sorted.
- * @param e_size Size of one element.
- * @param cmp Comparator function.
- * 
- */
-void qsort(void * data, size_t n, size_t e_size, int (* cmp) (void * a, void * b))
-{
-        uint8_t buf_tmp[EBUFSIZE];
-        uint8_t buf_pivot[EBUFSIZE];
-        void * tmp = buf_tmp;
-        void * pivot = buf_pivot;
-
-        if (e_size > EBUFSIZE) {
-                pivot = (void *) malloc(e_size, 0);
-                tmp = (void *) malloc(e_size, 0);
+
+/** Immediate buffer size.
+ *
+ * For small buffer sizes avoid doing malloc()
+ * and use the stack.
+ *
+ */
+#define IBUF_SIZE  32
+
+/** Array accessor.
+ *
+ */
+#define INDEX(buf, i, elem_size)  ((buf) + (i) * (elem_size))
+
+/** Gnome sort
+ *
+ * Apply generic gnome sort algorithm on supplied data,
+ * using pre-allocated buffer.
+ *
+ * @param data      Pointer to data to be sorted.
+ * @param cnt       Number of elements to be sorted.
+ * @param elem_size Size of one element.
+ * @param cmp       Comparator function.
+ * @param arg       3rd argument passed to cmp.
+ * @param slot      Pointer to scratch memory buffer
+ *                  elem_size bytes long.
+ *
+ */
+static void _gsort(void *data, size_t cnt, size_t elem_size, sort_cmp_t cmp,
+    void *arg, void *slot)
+{
+        size_t i = 0;
+        
+        while (i < cnt) {
+                if ((i > 0) &&
+                    (cmp(INDEX(data, i, elem_size),
+                    INDEX(data, i - 1, elem_size), arg) == -1)) {
+                        memcpy(slot, INDEX(data, i, elem_size), elem_size);
+                        memcpy(INDEX(data, i, elem_size), INDEX(data, i - 1, elem_size),
+                            elem_size);
+                        memcpy(INDEX(data, i - 1, elem_size), slot, elem_size);
+                        i--;
+                } else
+                        i++;
         }
-
-        _qsort(data, n, e_size, cmp, tmp, pivot);
-        
-        if (e_size > EBUFSIZE) {
-                free(tmp);
-                free(pivot);
-        }
 }
 
 /** Quicksort
  *
- * Apply generic quicksort algorithm on supplied data, using pre-allocated buffers.
- * 
- * @param data Pointer to data to be sorted.
- * @param n Number of elements to be sorted.
- * @param e_size Size of one element.
- * @param cmp Comparator function.
- * @param tmp Pointer to scratch memory buffer e_size bytes long.
- * @param pivot Pointer to scratch memory buffer e_size bytes long.
- * 
- */
-void _qsort(void * data, size_t n, size_t e_size, int (* cmp) (void * a, void * b), void *tmp, void *pivot)
-{
-        if (n > 4) {
-                unsigned int i = 0, j = n - 1;
-
-                memcpy(pivot, data, e_size);
-
-                while (1) {
-                        while ((cmp(data + i * e_size, pivot) < 0) && (i < n))
+ * Apply generic quicksort algorithm on supplied data,
+ * using pre-allocated buffers.
+ *
+ * @param data      Pointer to data to be sorted.
+ * @param cnt       Number of elements to be sorted.
+ * @param elem_size Size of one element.
+ * @param cmp       Comparator function.
+ * @param arg       3rd argument passed to cmp.
+ * @param slot      Pointer to scratch memory buffer
+ *                  elem_size bytes long.
+ * @param pivot     Pointer to scratch memory buffer
+ *                  elem_size bytes long.
+ *
+ */
+static void _qsort(void *data, size_t cnt, size_t elem_size, sort_cmp_t cmp,
+    void *arg, void *slot, void *pivot)
+{
+        if (cnt > 4) {
+                size_t i = 0;
+                size_t j = cnt - 1;
+                
+                memcpy(pivot, data, elem_size);
+                
+                while (true) {
+                        while ((cmp(INDEX(data, i, elem_size), pivot, arg) < 0) && (i < cnt))
                                 i++;
-                        while ((cmp(data + j * e_size, pivot) >= 0) && (j > 0))
+                        
+                        while ((cmp(INDEX(data, j, elem_size), pivot, arg) >= 0) && (j > 0))
                                 j--;
                         
                         if (i < j) {
-                                memcpy(tmp, data + i * e_size, e_size);
-                                memcpy(data + i * e_size, data + j * e_size, e_size);
-                                memcpy(data + j * e_size, tmp, e_size);
-                        } else {
+                                memcpy(slot, INDEX(data, i, elem_size), elem_size);
+                                memcpy(INDEX(data, i, elem_size), INDEX(data, j, elem_size),
+                                    elem_size);
+                                memcpy(INDEX(data, j, elem_size), slot, elem_size);
+                        } else
                                 break;
-                        }
                 }
-
-                _qsort(data, j + 1, e_size, cmp, tmp, pivot);
-                _qsort(data + (j + 1) * e_size, n - j - 1, e_size, cmp, tmp, pivot);
+                
+                _qsort(data, j + 1, elem_size, cmp, arg, slot, pivot);
+                _qsort(INDEX(data, j + 1, elem_size), cnt - j - 1, elem_size,
+                    cmp, arg, slot, pivot);
+        } else
+                _gsort(data, cnt, elem_size, cmp, arg, slot);
+}
+
+/** Gnome sort wrapper
+ *
+ * This is only a wrapper that takes care of memory
+ * allocations for storing the slot element for generic
+ * gnome sort algorithm.
+ *
+ * This function can sleep.
+ *
+ * @param data      Pointer to data to be sorted.
+ * @param cnt       Number of elements to be sorted.
+ * @param elem_size Size of one element.
+ * @param cmp       Comparator function.
+ * @param arg       3rd argument passed to cmp.
+ *
+ * @return True if sorting succeeded.
+ *
+ */
+bool gsort(void *data, size_t cnt, size_t elem_size, sort_cmp_t cmp, void *arg)
+{
+        uint8_t ibuf_slot[IBUF_SIZE];
+        void *slot;
+        
+        if (elem_size > IBUF_SIZE) {
+                slot = (void *) malloc(elem_size, 0);
+                if (!slot)
+                        return false;
+        } else
+                slot = (void *) ibuf_slot;
+        
+        _gsort(data, cnt, elem_size, cmp, arg, slot);
+        
+        if (elem_size > IBUF_SIZE)
+                free(slot);
+        
+        return true;
+}
+
+/** Quicksort wrapper
+ *
+ * This is only a wrapper that takes care of memory
+ * allocations for storing the pivot and temporary elements
+ * for generic quicksort algorithm.
+ *
+ * This function can sleep.
+ *
+ * @param data      Pointer to data to be sorted.
+ * @param cnt       Number of elements to be sorted.
+ * @param elem_size Size of one element.
+ * @param cmp       Comparator function.
+ * @param arg       3rd argument passed to cmp.
+ *
+ * @return True if sorting succeeded.
+ *
+ */
+bool qsort(void *data, size_t cnt, size_t elem_size, sort_cmp_t cmp, void *arg)
+{
+        uint8_t ibuf_slot[IBUF_SIZE];
+        uint8_t ibuf_pivot[IBUF_SIZE];
+        void *slot;
+        void *pivot;
+        
+        if (elem_size > IBUF_SIZE) {
+                slot = (void *) malloc(elem_size, 0);
+                if (!slot)
+                        return false;
+                
+                pivot = (void *) malloc(elem_size, 0);
+                if (!pivot) {
+                        free(slot);
+                        return false;
+                }
         } else {
-                _bubblesort(data, n, e_size, cmp, tmp);
+                slot = (void *) ibuf_slot;
+                pivot = (void *) ibuf_pivot;
         }
-}
-
-/** Bubblesort wrapper
- *
- * This is only a wrapper that takes care of memory allocation for storing
- * the slot element for generic bubblesort algorithm.
- * 
- * @param data Pointer to data to be sorted.
- * @param n Number of elements to be sorted.
- * @param e_size Size of one element.
- * @param cmp Comparator function.
- * 
- */
-void bubblesort(void * data, size_t n, size_t e_size, int (* cmp) (void * a, void * b))
-{
-        uint8_t buf_slot[EBUFSIZE];
-        void * slot = buf_slot;
-        
-        if (e_size > EBUFSIZE) {
-                slot = (void *) malloc(e_size, 0);
-        }
-
-        _bubblesort(data, n, e_size, cmp, slot);
-        
-        if (e_size > EBUFSIZE) {
+        
+        _qsort(data, cnt, elem_size, cmp, arg, slot, pivot);
+        
+        if (elem_size > IBUF_SIZE) {
+                free(pivot);
                 free(slot);
         }
-}
-
-/** Bubblesort
- *
- * Apply generic bubblesort algorithm on supplied data, using pre-allocated buffer.
- * 
- * @param data Pointer to data to be sorted.
- * @param n Number of elements to be sorted.
- * @param e_size Size of one element.
- * @param cmp Comparator function.
- * @param slot Pointer to scratch memory buffer e_size bytes long.
- * 
- */
-void _bubblesort(void * data, size_t n, size_t e_size, int (* cmp) (void * a, void * b), void *slot)
-{
-        bool done = false;
-        void * p;
-
-        while (!done) {
-                done = true;
-                for (p = data; p < data + e_size * (n - 1); p = p + e_size) {
-                        if (cmp(p, p + e_size) == 1) {
-                                memcpy(slot, p, e_size);
-                                memcpy(p, p + e_size, e_size);
-                                memcpy(p + e_size, slot, e_size);
-                                done = false;
-                        }
-                }
-        }
-
-}
-
-/*
- * Comparator returns 1 if a > b, 0 if a == b, -1 if a < b
- */
-int int_cmp(void * a, void * b)
-{
-        return (* (int *) a > * (int*)b) ? 1 : (*(int *)a < * (int *)b) ? -1 : 0;
-}
-
-int uint8_t_cmp(void * a, void * b)
-{
-        return (* (uint8_t *) a > * (uint8_t *)b) ? 1 : (*(uint8_t *)a < * (uint8_t *)b) ? -1 : 0;
-}
-
-int uint16_t_cmp(void * a, void * b)
-{
-        return (* (uint16_t *) a > * (uint16_t *)b) ? 1 : (*(uint16_t *)a < * (uint16_t *)b) ? -1 : 0;
-}
-
-int uint32_t_cmp(void * a, void * b)
-{
-        return (* (uint32_t *) a > * (uint32_t *)b) ? 1 : (*(uint32_t *)a < * (uint32_t *)b) ? -1 : 0;
+        
+        return true;
 }
 

kernel/generic/src/main/main.c

@@ -104 +104 @@
 
 /** Lowest safe stack virtual address. */
-uintptr_t stack_safe = 0;               
+uintptr_t stack_safe = 0;
 
 /*
@@ -113 +113 @@
  */
 static void main_bsp_separated_stack(void);
+
 #ifdef CONFIG_SMP
 static void main_ap_separated_stack(void);
 #endif
 
-#define CONFIG_STACK_SIZE       ((1 << STACK_FRAMES) * STACK_SIZE)
+#define CONFIG_STACK_SIZE  ((1 << STACK_FRAMES) * STACK_SIZE)
 
 /** Main kernel routine for bootstrap CPU.
@@ -130 +131 @@
  *
  */
-void main_bsp(void)
+void __attribute__((no_instrument_function)) main_bsp(void)
 {
         config.cpu_count = 1;
@@ -151 +152 @@
                             init.tasks[i].size, config.stack_size);
         }
-
+        
         /* Avoid placing stack on top of boot allocations. */
         if (ballocs.size) {
@@ -170 +171 @@
 }
 
-
 /** Main kernel routine for bootstrap CPU using new stack.
  *
@@ -176 +176 @@
  *
  */
-void main_bsp_separated_stack(void) 
+void main_bsp_separated_stack(void)
 {
         /* Keep this the first thing. */
@@ -183 +183 @@
         version_print();
         
-        LOG("\nconfig.base=%#" PRIp " config.kernel_size=%" PRIs
-            "\nconfig.stack_base=%#" PRIp " config.stack_size=%" PRIs,
+        LOG("\nconfig.base=%p config.kernel_size=%" PRIs
+            "\nconfig.stack_base=%p config.stack_size=%" PRIs,
             config.base, config.kernel_size, config.stack_base,
             config.stack_size);
@@ -194 +194 @@
          * commands.
          */
-        LOG_EXEC(kconsole_init());
+        kconsole_init();
 #endif
         
@@ -201 +201 @@
          * starts adding its own handlers
          */
-        LOG_EXEC(exc_init());
+        exc_init();
         
         /*
          * Memory management subsystems initialization.
          */
-        LOG_EXEC(arch_pre_mm_init());
-        LOG_EXEC(frame_init());
+        arch_pre_mm_init();
+        frame_init();
         
         /* Initialize at least 1 memory segment big enough for slab to work. */
-        LOG_EXEC(slab_cache_init());
-        LOG_EXEC(sysinfo_init());
-        LOG_EXEC(btree_init());
-        LOG_EXEC(as_init());
-        LOG_EXEC(page_init());
-        LOG_EXEC(tlb_init());
-        LOG_EXEC(ddi_init());
-        LOG_EXEC(tasklet_init());
-        LOG_EXEC(arch_post_mm_init());
-        LOG_EXEC(arch_pre_smp_init());
-        LOG_EXEC(smp_init());
+        slab_cache_init();
+        sysinfo_init();
+        btree_init();
+        as_init();
+        page_init();
+        tlb_init();
+        ddi_init();
+        tasklet_init();
+        arch_post_mm_init();
+        arch_pre_smp_init();
+        smp_init();
         
         /* Slab must be initialized after we know the number of processors. */
-        LOG_EXEC(slab_enable_cpucache());
+        slab_enable_cpucache();
         
         printf("Detected %" PRIs " CPU(s), %" PRIu64" MiB free memory\n",
             config.cpu_count, SIZE2MB(zones_total_size()));
-
-        LOG_EXEC(cpu_init());
-        
-        LOG_EXEC(calibrate_delay_loop());
-        LOG_EXEC(clock_counter_init());
-        LOG_EXEC(timeout_init());
-        LOG_EXEC(scheduler_init());
-        LOG_EXEC(task_init());
-        LOG_EXEC(thread_init());
-        LOG_EXEC(futex_init());
+        
+        cpu_init();
+        
+        calibrate_delay_loop();
+        clock_counter_init();
+        timeout_init();
+        scheduler_init();
+        task_init();
+        thread_init();
+        futex_init();
         
         if (init.cnt > 0) {
                 size_t i;
                 for (i = 0; i < init.cnt; i++)
-                        LOG("init[%" PRIs "].addr=%#" PRIp ", init[%" PRIs
-                            "].size=%#" PRIs, i, init.tasks[i].addr, i,
+                        LOG("init[%" PRIs "].addr=%p, init[%" PRIs
+                            "].size=%" PRIs, i, init.tasks[i].addr, i,
                             init.tasks[i].size);
         } else
                 printf("No init binaries found.\n");
         
-        LOG_EXEC(ipc_init());
-        LOG_EXEC(event_init());
-        LOG_EXEC(klog_init());
-        LOG_EXEC(stats_init());
+        ipc_init();
+        event_init();
+        klog_init();
+        stats_init();
         
         /*
@@ -266 +266 @@
         if (!kinit_thread)
                 panic("Cannot create kinit thread.");
-        LOG_EXEC(thread_ready(kinit_thread));
+        thread_ready(kinit_thread);
         
         /*
@@ -276 +276 @@
 }
 
-
 #ifdef CONFIG_SMP
+
 /** Main kernel routine for application CPUs.
  *
@@ -296 +296 @@
          */
         config.cpu_active++;
-
+        
         /*
          * The THE structure is well defined because ctx.sp is used as stack.
@@ -311 +311 @@
         calibrate_delay_loop();
         arch_post_cpu_init();
-
+        
         the_copy(THE, (the_t *) CPU->stack);
-
+        
         /*
          * If we woke kmp up before we left the kernel stack, we could
@@ -326 +326 @@
 }
 
-
 /** Main kernel routine for application CPUs using new stack.
  *
@@ -338 +337 @@
          */
         timeout_init();
-
+        
         waitq_wakeup(&ap_completion_wq, WAKEUP_FIRST);
         scheduler();
         /* not reached */
 }
+
 #endif /* CONFIG_SMP */
 

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