Fork us on GitHub Follow us on Facebook Follow us on Twitter

Changeset e3ee9b9 in mainline


Ignore:
Timestamp:
2010-07-02T12:44:00Z (11 years ago)
Author:
Martin Decky <martin@…>
Branches:
master
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:
5 edited

Legend:

Unmodified
Added
Removed
  • kernel/generic/src/adt/btree.c

    rb5382d4f re3ee9b9  
    3333/**
    3434 * @file
    35  * @brief       B+tree implementation.
     35 * @brief B+tree implementation.
    3636 *
    3737 * This file implements B+tree type and operations.
     
    5454#include <print.h>
    5555
    56 static void btree_destroy_subtree(btree_node_t *root);
    57 static void _btree_insert(btree_t *t, btree_key_t key, void *value, btree_node_t *rsubtree, btree_node_t *node);
    58 static void _btree_remove(btree_t *t, btree_key_t key, btree_node_t *node);
    59 static void node_initialize(btree_node_t *node);
    60 static void node_insert_key_and_lsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *lsubtree);
    61 static void node_insert_key_and_rsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree);
    62 static void node_remove_key_and_lsubtree(btree_node_t *node, btree_key_t key);
    63 static void node_remove_key_and_rsubtree(btree_node_t *node, btree_key_t key);
    64 static btree_node_t *node_split(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree, btree_key_t *median);
    65 static btree_node_t *node_combine(btree_node_t *node);
    66 static size_t find_key_by_subtree(btree_node_t *node, btree_node_t *subtree, bool right);
    67 static void rotate_from_right(btree_node_t *lnode, btree_node_t *rnode, size_t idx);
    68 static void rotate_from_left(btree_node_t *lnode, btree_node_t *rnode, size_t idx);
    69 static bool try_insert_by_rotation_to_left(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree);
    70 static bool try_insert_by_rotation_to_right(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree);
    71 static bool try_rotation_from_left(btree_node_t *rnode);
    72 static bool try_rotation_from_right(btree_node_t *lnode);
    73 
    74 #define ROOT_NODE(n)            (!(n)->parent)
    75 #define INDEX_NODE(n)           ((n)->subtree[0] != NULL)
    76 #define LEAF_NODE(n)            ((n)->subtree[0] == NULL)
    77 
    78 #define FILL_FACTOR             ((BTREE_M-1)/2)
    79 
    80 #define MEDIAN_LOW_INDEX(n)     (((n)->keys-1)/2)
    81 #define MEDIAN_HIGH_INDEX(n)    ((n)->keys/2)
    82 #define MEDIAN_LOW(n)           ((n)->key[MEDIAN_LOW_INDEX((n))]);
    83 #define MEDIAN_HIGH(n)          ((n)->key[MEDIAN_HIGH_INDEX((n))]);
    84 
    8556static slab_cache_t *btree_node_slab;
     57
     58#define ROOT_NODE(n)   (!(n)->parent)
     59#define INDEX_NODE(n)  ((n)->subtree[0] != NULL)
     60#define LEAF_NODE(n)   ((n)->subtree[0] == NULL)
     61
     62#define FILL_FACTOR  ((BTREE_M - 1) / 2)
     63
     64#define MEDIAN_LOW_INDEX(n)   (((n)->keys-1) / 2)
     65#define MEDIAN_HIGH_INDEX(n)  ((n)->keys / 2)
     66#define MEDIAN_LOW(n)         ((n)->key[MEDIAN_LOW_INDEX((n))]);
     67#define MEDIAN_HIGH(n)        ((n)->key[MEDIAN_HIGH_INDEX((n))]);
    8668
    8769/** Initialize B-trees. */
    8870void btree_init(void)
    8971{
    90         btree_node_slab = slab_cache_create("btree_node_slab", sizeof(btree_node_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED);
     72        btree_node_slab = slab_cache_create("btree_node_slab",
     73            sizeof(btree_node_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED);
     74}
     75
     76/** Initialize B-tree node.
     77 *
     78 * @param node B-tree node.
     79 *
     80 */
     81static void node_initialize(btree_node_t *node)
     82{
     83        unsigned int i;
     84       
     85        node->keys = 0;
     86       
     87        /* Clean also space for the extra key. */
     88        for (i = 0; i < BTREE_MAX_KEYS + 1; i++) {
     89                node->key[i] = 0;
     90                node->value[i] = NULL;
     91                node->subtree[i] = NULL;
     92        }
     93       
     94        node->subtree[i] = NULL;
     95        node->parent = NULL;
     96       
     97        link_initialize(&node->leaf_link);
     98        link_initialize(&node->bfs_link);
     99        node->depth = 0;
    91100}
    92101
     
    94103 *
    95104 * @param t B-tree.
     105 *
    96106 */
    97107void btree_create(btree_t *t)
     
    103113}
    104114
    105 /** Destroy empty B-tree. */
    106 void btree_destroy(btree_t *t)
    107 {
    108         btree_destroy_subtree(t->root);
    109 }
    110 
    111 /** Insert key-value pair into B-tree.
    112  *
    113  * @param t B-tree.
    114  * @param key Key to be inserted.
    115  * @param value Value to be inserted.
    116  * @param leaf_node Leaf node where the insertion should begin.
    117  */
    118 void btree_insert(btree_t *t, btree_key_t key, void *value, btree_node_t *leaf_node)
    119 {
    120         btree_node_t *lnode;
    121        
    122         ASSERT(value);
    123        
    124         lnode = leaf_node;
    125         if (!lnode) {
    126                 if (btree_search(t, key, &lnode)) {
    127                         panic("B-tree %p already contains key %" PRIu64 ".", t, key);
    128                 }
    129         }
    130        
    131         _btree_insert(t, key, value, NULL, lnode);
    132 }
    133 
    134115/** Destroy subtree rooted in a node.
    135116 *
    136117 * @param root Root of the subtree.
    137  */
    138 void btree_destroy_subtree(btree_node_t *root)
     118 *
     119 */
     120static void btree_destroy_subtree(btree_node_t *root)
    139121{
    140122        size_t i;
    141 
     123       
    142124        if (root->keys) {
    143125                for (i = 0; i < root->keys + 1; i++) {
     
    146128                }
    147129        }
     130       
    148131        slab_free(btree_node_slab, root);
    149132}
    150133
     134/** Destroy empty B-tree. */
     135void btree_destroy(btree_t *t)
     136{
     137        btree_destroy_subtree(t->root);
     138}
     139
     140/** Insert key-value-rsubtree triplet into B-tree node.
     141 *
     142 * It is actually possible to have more keys than BTREE_MAX_KEYS.
     143 * This feature is used during splitting the node when the
     144 * number of keys is BTREE_MAX_KEYS + 1. Insert by left rotation
     145 * also makes use of this feature.
     146 *
     147 * @param node     B-tree node into wich the new key is to be inserted.
     148 * @param key      The key to be inserted.
     149 * @param value    Pointer to value to be inserted.
     150 * @param rsubtree Pointer to the right subtree.
     151 *
     152 */
     153static void node_insert_key_and_rsubtree(btree_node_t *node, btree_key_t key,
     154    void *value, btree_node_t *rsubtree)
     155{
     156        size_t i;
     157       
     158        for (i = 0; i < node->keys; i++) {
     159                if (key < node->key[i]) {
     160                        size_t j;
     161                       
     162                        for (j = node->keys; j > i; j--) {
     163                                node->key[j] = node->key[j - 1];
     164                                node->value[j] = node->value[j - 1];
     165                                node->subtree[j + 1] = node->subtree[j];
     166                        }
     167                       
     168                        break;
     169                }
     170        }
     171       
     172        node->key[i] = key;
     173        node->value[i] = value;
     174        node->subtree[i + 1] = rsubtree;
     175        node->keys++;
     176}
     177
     178/** Find key by its left or right subtree.
     179 *
     180 * @param node    B-tree node.
     181 * @param subtree Left or right subtree of a key found in node.
     182 * @param right   If true, subtree is a right subtree. If false,
     183 *                subtree is a left subtree.
     184 *
     185 * @return Index of the key associated with the subtree.
     186 *
     187 */
     188static size_t find_key_by_subtree(btree_node_t *node, btree_node_t *subtree,
     189    bool right)
     190{
     191        size_t i;
     192       
     193        for (i = 0; i < node->keys + 1; i++) {
     194                if (subtree == node->subtree[i])
     195                        return i - (int) (right != false);
     196        }
     197       
     198        panic("Node %p does not contain subtree %p.", node, subtree);
     199}
     200
     201/** Remove key and its left subtree pointer from B-tree node.
     202 *
     203 * Remove the key and eliminate gaps in node->key array.
     204 * Note that the value pointer and the left subtree pointer
     205 * is removed from the node as well.
     206 *
     207 * @param node B-tree node.
     208 * @param key  Key to be removed.
     209 *
     210 */
     211static void node_remove_key_and_lsubtree(btree_node_t *node, btree_key_t key)
     212{
     213        size_t i;
     214        size_t j;
     215       
     216        for (i = 0; i < node->keys; i++) {
     217                if (key == node->key[i]) {
     218                        for (j = i + 1; j < node->keys; j++) {
     219                                node->key[j - 1] = node->key[j];
     220                                node->value[j - 1] = node->value[j];
     221                                node->subtree[j - 1] = node->subtree[j];
     222                        }
     223                       
     224                        node->subtree[j - 1] = node->subtree[j];
     225                        node->keys--;
     226                       
     227                        return;
     228                }
     229        }
     230       
     231        panic("Node %p does not contain key %" PRIu64 ".", node, key);
     232}
     233
     234/** Remove key and its right subtree pointer from B-tree node.
     235 *
     236 * Remove the key and eliminate gaps in node->key array.
     237 * Note that the value pointer and the right subtree pointer
     238 * is removed from the node as well.
     239 *
     240 * @param node B-tree node.
     241 * @param key  Key to be removed.
     242 *
     243 */
     244static void node_remove_key_and_rsubtree(btree_node_t *node, btree_key_t key)
     245{
     246        size_t i, j;
     247       
     248        for (i = 0; i < node->keys; i++) {
     249                if (key == node->key[i]) {
     250                        for (j = i + 1; j < node->keys; j++) {
     251                                node->key[j - 1] = node->key[j];
     252                                node->value[j - 1] = node->value[j];
     253                                node->subtree[j] = node->subtree[j + 1];
     254                        }
     255                       
     256                        node->keys--;
     257                        return;
     258                }
     259        }
     260       
     261        panic("Node %p does not contain key %" PRIu64 ".", node, key);
     262}
     263
     264/** Insert key-value-lsubtree triplet into B-tree node.
     265 *
     266 * It is actually possible to have more keys than BTREE_MAX_KEYS.
     267 * This feature is used during insert by right rotation.
     268 *
     269 * @param node     B-tree node into wich the new key is to be inserted.
     270 * @param key      The key to be inserted.
     271 * @param value    Pointer to value to be inserted.
     272 * @param lsubtree Pointer to the left subtree.
     273 *
     274 */
     275static void node_insert_key_and_lsubtree(btree_node_t *node, btree_key_t key,
     276    void *value, btree_node_t *lsubtree)
     277{
     278        size_t i;
     279       
     280        for (i = 0; i < node->keys; i++) {
     281                if (key < node->key[i]) {
     282                        size_t j;
     283                       
     284                        for (j = node->keys; j > i; j--) {
     285                                node->key[j] = node->key[j - 1];
     286                                node->value[j] = node->value[j - 1];
     287                                node->subtree[j + 1] = node->subtree[j];
     288                        }
     289                       
     290                        node->subtree[j + 1] = node->subtree[j];
     291                        break;
     292                }
     293        }
     294       
     295        node->key[i] = key;
     296        node->value[i] = value;
     297        node->subtree[i] = lsubtree;
     298       
     299        node->keys++;
     300}
     301
     302/** Rotate one key-value-rsubtree triplet from the left sibling to the right sibling.
     303 *
     304 * The biggest key and its value and right subtree is rotated
     305 * from the left node to the right. If the node is an index node,
     306 * than the parent node key belonging to the left node takes part
     307 * in the rotation.
     308 *
     309 * @param lnode Left sibling.
     310 * @param rnode Right sibling.
     311 * @param idx   Index of the parent node key that is taking part
     312 *              in the rotation.
     313 *
     314 */
     315static void rotate_from_left(btree_node_t *lnode, btree_node_t *rnode, size_t idx)
     316{
     317        btree_key_t key = lnode->key[lnode->keys - 1];
     318       
     319        if (LEAF_NODE(lnode)) {
     320                void *value = lnode->value[lnode->keys - 1];
     321               
     322                node_remove_key_and_rsubtree(lnode, key);
     323                node_insert_key_and_lsubtree(rnode, key, value, NULL);
     324                lnode->parent->key[idx] = key;
     325        } else {
     326                btree_node_t *rsubtree = lnode->subtree[lnode->keys];
     327               
     328                node_remove_key_and_rsubtree(lnode, key);
     329                node_insert_key_and_lsubtree(rnode, lnode->parent->key[idx], NULL, rsubtree);
     330                lnode->parent->key[idx] = key;
     331               
     332                /* Fix parent link of the reconnected right subtree. */
     333                rsubtree->parent = rnode;
     334        }
     335}
     336
     337/** Rotate one key-value-lsubtree triplet from the right sibling to the left sibling.
     338 *
     339 * The smallest key and its value and left subtree is rotated
     340 * from the right node to the left. If the node is an index node,
     341 * than the parent node key belonging to the right node takes part
     342 * in the rotation.
     343 *
     344 * @param lnode Left sibling.
     345 * @param rnode Right sibling.
     346 * @param idx   Index of the parent node key that is taking part
     347 *              in the rotation.
     348 *
     349 */
     350static void rotate_from_right(btree_node_t *lnode, btree_node_t *rnode, size_t idx)
     351{
     352        btree_key_t key = rnode->key[0];
     353       
     354        if (LEAF_NODE(rnode)) {
     355                void *value = rnode->value[0];
     356               
     357                node_remove_key_and_lsubtree(rnode, key);
     358                node_insert_key_and_rsubtree(lnode, key, value, NULL);
     359                rnode->parent->key[idx] = rnode->key[0];
     360        } else {
     361                btree_node_t *lsubtree = rnode->subtree[0];
     362               
     363                node_remove_key_and_lsubtree(rnode, key);
     364                node_insert_key_and_rsubtree(lnode, rnode->parent->key[idx], NULL, lsubtree);
     365                rnode->parent->key[idx] = key;
     366               
     367                /* Fix parent link of the reconnected left subtree. */
     368                lsubtree->parent = lnode;
     369        }
     370}
     371
     372/** Insert key-value-rsubtree triplet and rotate the node to the left, if this operation can be done.
     373 *
     374 * Left sibling of the node (if it exists) is checked for free space.
     375 * If there is free space, the key is inserted and the smallest key of
     376 * the node is moved there. The index node which is the parent of both
     377 * nodes is fixed.
     378 *
     379 * @param node     B-tree node.
     380 * @param inskey   Key to be inserted.
     381 * @param insvalue Value to be inserted.
     382 * @param rsubtree Right subtree of inskey.
     383 *
     384 * @return True if the rotation was performed, false otherwise.
     385 *
     386 */
     387static bool try_insert_by_rotation_to_left(btree_node_t *node,
     388    btree_key_t inskey, void *insvalue, btree_node_t *rsubtree)
     389{
     390        size_t idx;
     391        btree_node_t *lnode;
     392       
     393        /*
     394         * If this is root node, the rotation can not be done.
     395         */
     396        if (ROOT_NODE(node))
     397                return false;
     398       
     399        idx = find_key_by_subtree(node->parent, node, true);
     400        if ((int) idx == -1) {
     401                /*
     402                 * If this node is the leftmost subtree of its parent,
     403                 * the rotation can not be done.
     404                 */
     405                return false;
     406        }
     407       
     408        lnode = node->parent->subtree[idx];
     409        if (lnode->keys < BTREE_MAX_KEYS) {
     410                /*
     411                 * The rotaion can be done. The left sibling has free space.
     412                 */
     413                node_insert_key_and_rsubtree(node, inskey, insvalue, rsubtree);
     414                rotate_from_right(lnode, node, idx);
     415                return true;
     416        }
     417       
     418        return false;
     419}
     420
     421/** Insert key-value-rsubtree triplet and rotate the node to the right, if this operation can be done.
     422 *
     423 * Right sibling of the node (if it exists) is checked for free space.
     424 * If there is free space, the key is inserted and the biggest key of
     425 * the node is moved there. The index node which is the parent of both
     426 * nodes is fixed.
     427 *
     428 * @param node     B-tree node.
     429 * @param inskey   Key to be inserted.
     430 * @param insvalue Value to be inserted.
     431 * @param rsubtree Right subtree of inskey.
     432 *
     433 * @return True if the rotation was performed, false otherwise.
     434 *
     435 */
     436static bool try_insert_by_rotation_to_right(btree_node_t *node,
     437    btree_key_t inskey, void *insvalue, btree_node_t *rsubtree)
     438{
     439        size_t idx;
     440        btree_node_t *rnode;
     441       
     442        /*
     443         * If this is root node, the rotation can not be done.
     444         */
     445        if (ROOT_NODE(node))
     446                return false;
     447       
     448        idx = find_key_by_subtree(node->parent, node, false);
     449        if (idx == node->parent->keys) {
     450                /*
     451                 * If this node is the rightmost subtree of its parent,
     452                 * the rotation can not be done.
     453                 */
     454                return false;
     455        }
     456       
     457        rnode = node->parent->subtree[idx + 1];
     458        if (rnode->keys < BTREE_MAX_KEYS) {
     459                /*
     460                 * The rotaion can be done. The right sibling has free space.
     461                 */
     462                node_insert_key_and_rsubtree(node, inskey, insvalue, rsubtree);
     463                rotate_from_left(node, rnode, idx);
     464                return true;
     465        }
     466       
     467        return false;
     468}
     469
     470/** Split full B-tree node and insert new key-value-right-subtree triplet.
     471 *
     472 * This function will split a node and return a pointer to a newly created
     473 * node containing keys greater than or equal to the greater of medians
     474 * (or median) of the old keys and the newly added key. It will also write
     475 * the median key to a memory address supplied by the caller.
     476 *
     477 * If the node being split is an index node, the median will not be
     478 * included in the new node. If the node is a leaf node,
     479 * the median will be copied there.
     480 *
     481 * @param node     B-tree node wich is going to be split.
     482 * @param key      The key to be inserted.
     483 * @param value    Pointer to the value to be inserted.
     484 * @param rsubtree Pointer to the right subtree of the key being added.
     485 * @param median   Address in memory, where the median key will be stored.
     486 *
     487 * @return Newly created right sibling of node.
     488 *
     489 */
     490static btree_node_t *node_split(btree_node_t *node, btree_key_t key,
     491    void *value, btree_node_t *rsubtree, btree_key_t *median)
     492{
     493        btree_node_t *rnode;
     494        size_t i;
     495        size_t j;
     496       
     497        ASSERT(median);
     498        ASSERT(node->keys == BTREE_MAX_KEYS);
     499       
     500        /*
     501         * Use the extra space to store the extra node.
     502         */
     503        node_insert_key_and_rsubtree(node, key, value, rsubtree);
     504       
     505        /*
     506         * Compute median of keys.
     507         */
     508        *median = MEDIAN_HIGH(node);
     509       
     510        /*
     511         * Allocate and initialize new right sibling.
     512         */
     513        rnode = (btree_node_t *) slab_alloc(btree_node_slab, 0);
     514        node_initialize(rnode);
     515        rnode->parent = node->parent;
     516        rnode->depth = node->depth;
     517       
     518        /*
     519         * Copy big keys, values and subtree pointers to the new right sibling.
     520         * If this is an index node, do not copy the median.
     521         */
     522        i = (size_t) INDEX_NODE(node);
     523        for (i += MEDIAN_HIGH_INDEX(node), j = 0; i < node->keys; i++, j++) {
     524                rnode->key[j] = node->key[i];
     525                rnode->value[j] = node->value[i];
     526                rnode->subtree[j] = node->subtree[i];
     527               
     528                /*
     529                 * Fix parent links in subtrees.
     530                 */
     531                if (rnode->subtree[j])
     532                        rnode->subtree[j]->parent = rnode;
     533        }
     534       
     535        rnode->subtree[j] = node->subtree[i];
     536        if (rnode->subtree[j])
     537                rnode->subtree[j]->parent = rnode;
     538       
     539        rnode->keys = j;  /* Set number of keys of the new node. */
     540        node->keys /= 2;  /* Shrink the old node. */
     541       
     542        return rnode;
     543}
     544
    151545/** Recursively insert into B-tree.
    152546 *
    153  * @param t B-tree.
    154  * @param key Key to be inserted.
    155  * @param value Value to be inserted.
     547 * @param t        B-tree.
     548 * @param key      Key to be inserted.
     549 * @param value    Value to be inserted.
    156550 * @param rsubtree Right subtree of the inserted key.
    157  * @param node Start inserting into this node.
    158  */
    159 void _btree_insert(btree_t *t, btree_key_t key, void *value, btree_node_t *rsubtree, btree_node_t *node)
     551 * @param node     Start inserting into this node.
     552 *
     553 */
     554static void _btree_insert(btree_t *t, btree_key_t key, void *value,
     555    btree_node_t *rsubtree, btree_node_t *node)
    160556{
    161557        if (node->keys < BTREE_MAX_KEYS) {
     
    183579                 * bigger keys (i.e. the new node) into its parent.
    184580                 */
    185 
     581               
    186582                rnode = node_split(node, key, value, rsubtree, &median);
    187 
     583               
    188584                if (LEAF_NODE(node)) {
    189585                        list_prepend(&rnode->leaf_link, &node->leaf_link);
     
    202598                         * Left-hand side subtree will be the old root (i.e. node).
    203599                         * Right-hand side subtree will be rnode.
    204                          */                     
     600                         */
    205601                        t->root->subtree[0] = node;
    206 
     602                       
    207603                        t->root->depth = node->depth + 1;
    208604                }
    209605                _btree_insert(t, median, NULL, rnode, node->parent);
    210         }       
    211                
    212 }
    213 
    214 /** Remove B-tree node.
    215  *
    216  * @param t B-tree.
    217  * @param key Key to be removed from the B-tree along with its associated value.
    218  * @param leaf_node If not NULL, pointer to the leaf node where the key is found.
    219  */
    220 void btree_remove(btree_t *t, btree_key_t key, btree_node_t *leaf_node)
     606        }
     607}
     608
     609/** Insert key-value pair into B-tree.
     610 *
     611 * @param t         B-tree.
     612 * @param key       Key to be inserted.
     613 * @param value     Value to be inserted.
     614 * @param leaf_node Leaf node where the insertion should begin.
     615 *
     616 */
     617void btree_insert(btree_t *t, btree_key_t key, void *value,
     618    btree_node_t *leaf_node)
    221619{
    222620        btree_node_t *lnode;
     621       
     622        ASSERT(value);
    223623       
    224624        lnode = leaf_node;
    225625        if (!lnode) {
    226                 if (!btree_search(t, key, &lnode)) {
    227                         panic("B-tree %p does not contain key %" PRIu64 ".", t, key);
    228                 }
    229         }
    230        
    231         _btree_remove(t, key, lnode);
     626                if (btree_search(t, key, &lnode))
     627                        panic("B-tree %p already contains key %" PRIu64 ".", t, key);
     628        }
     629       
     630        _btree_insert(t, key, value, NULL, lnode);
     631}
     632
     633/** Rotate in a key from the left sibling or from the index node, if this operation can be done.
     634 *
     635 * @param rnode Node into which to add key from its left sibling
     636 *              or from the index node.
     637 *
     638 * @return True if the rotation was performed, false otherwise.
     639 *
     640 */
     641static bool try_rotation_from_left(btree_node_t *rnode)
     642{
     643        size_t idx;
     644        btree_node_t *lnode;
     645       
     646        /*
     647         * If this is root node, the rotation can not be done.
     648         */
     649        if (ROOT_NODE(rnode))
     650                return false;
     651       
     652        idx = find_key_by_subtree(rnode->parent, rnode, true);
     653        if ((int) idx == -1) {
     654                /*
     655                 * If this node is the leftmost subtree of its parent,
     656                 * the rotation can not be done.
     657                 */
     658                return false;
     659        }
     660       
     661        lnode = rnode->parent->subtree[idx];
     662        if (lnode->keys > FILL_FACTOR) {
     663                rotate_from_left(lnode, rnode, idx);
     664                return true;
     665        }
     666       
     667        return false;
     668}
     669
     670/** Rotate in a key from the right sibling or from the index node, if this operation can be done.
     671 *
     672 * @param lnode Node into which to add key from its right sibling
     673 *              or from the index node.
     674 *
     675 * @return True if the rotation was performed, false otherwise.
     676 *
     677 */
     678static bool try_rotation_from_right(btree_node_t *lnode)
     679{
     680        size_t idx;
     681        btree_node_t *rnode;
     682       
     683        /*
     684         * If this is root node, the rotation can not be done.
     685         */
     686        if (ROOT_NODE(lnode))
     687                return false;
     688       
     689        idx = find_key_by_subtree(lnode->parent, lnode, false);
     690        if (idx == lnode->parent->keys) {
     691                /*
     692                 * If this node is the rightmost subtree of its parent,
     693                 * the rotation can not be done.
     694                 */
     695                return false;
     696        }
     697       
     698        rnode = lnode->parent->subtree[idx + 1];
     699        if (rnode->keys > FILL_FACTOR) {
     700                rotate_from_right(lnode, rnode, idx);
     701                return true;
     702        }
     703       
     704        return false;
     705}
     706
     707/** Combine node with any of its siblings.
     708 *
     709 * The siblings are required to be below the fill factor.
     710 *
     711 * @param node Node to combine with one of its siblings.
     712 *
     713 * @return Pointer to the rightmost of the two nodes.
     714 *
     715 */
     716static btree_node_t *node_combine(btree_node_t *node)
     717{
     718        size_t idx;
     719        btree_node_t *rnode;
     720        size_t i;
     721       
     722        ASSERT(!ROOT_NODE(node));
     723       
     724        idx = find_key_by_subtree(node->parent, node, false);
     725        if (idx == node->parent->keys) {
     726                /*
     727                 * Rightmost subtree of its parent, combine with the left sibling.
     728                 */
     729                idx--;
     730                rnode = node;
     731                node = node->parent->subtree[idx];
     732        } else
     733                rnode = node->parent->subtree[idx + 1];
     734       
     735        /* Index nodes need to insert parent node key in between left and right node. */
     736        if (INDEX_NODE(node))
     737                node->key[node->keys++] = node->parent->key[idx];
     738       
     739        /* Copy the key-value-subtree triplets from the right node. */
     740        for (i = 0; i < rnode->keys; i++) {
     741                node->key[node->keys + i] = rnode->key[i];
     742                node->value[node->keys + i] = rnode->value[i];
     743               
     744                if (INDEX_NODE(node)) {
     745                        node->subtree[node->keys + i] = rnode->subtree[i];
     746                        rnode->subtree[i]->parent = node;
     747                }
     748        }
     749       
     750        if (INDEX_NODE(node)) {
     751                node->subtree[node->keys + i] = rnode->subtree[i];
     752                rnode->subtree[i]->parent = node;
     753        }
     754       
     755        node->keys += rnode->keys;
     756        return rnode;
    232757}
    233758
    234759/** Recursively remove B-tree node.
    235760 *
    236  * @param t B-tree.
    237  * @param key Key to be removed from the B-tree along with its associated value.
     761 * @param t    B-tree.
     762 * @param key  Key to be removed from the B-tree along with its associated value.
    238763 * @param node Node where the key being removed resides.
    239  */
    240 void _btree_remove(btree_t *t, btree_key_t key, btree_node_t *node)
     764 *
     765 */
     766static void _btree_remove(btree_t *t, btree_key_t key, btree_node_t *node)
    241767{
    242768        if (ROOT_NODE(node)) {
    243                 if (node->keys == 1 && node->subtree[0]) {
     769                if ((node->keys == 1) && (node->subtree[0])) {
    244770                        /*
    245771                         * Free the current root and set new root.
     
    257783                        node_remove_key_and_rsubtree(node, key);
    258784                }
     785               
    259786                return;
    260787        }
     
    271798        if (node->keys > FILL_FACTOR) {
    272799                size_t i;
    273 
     800               
    274801                /*
    275802                 * The key can be immediatelly removed.
     
    280807                 */
    281808                node_remove_key_and_rsubtree(node, key);
     809               
    282810                for (i = 0; i < node->parent->keys; i++) {
    283811                        if (node->parent->key[i] == key)
    284812                                node->parent->key[i] = node->key[0];
    285813                }
    286                
    287814        } else {
    288815                size_t idx;
    289                 btree_node_t *rnode, *parent;
    290 
     816                btree_node_t *rnode;
     817                btree_node_t *parent;
     818               
    291819                /*
    292820                 * The node is below the fill factor as well as its left and right sibling.
     
    298826                node_remove_key_and_rsubtree(node, key);
    299827                rnode = node_combine(node);
     828               
    300829                if (LEAF_NODE(rnode))
    301830                        list_remove(&rnode->leaf_link);
     831               
    302832                idx = find_key_by_subtree(parent, rnode, true);
    303833                ASSERT((int) idx != -1);
     
    307837}
    308838
     839/** Remove B-tree node.
     840 *
     841 * @param t         B-tree.
     842 * @param key       Key to be removed from the B-tree along
     843 *                  with its associated value.
     844 * @param leaf_node If not NULL, pointer to the leaf node where
     845 *                  the key is found.
     846 *
     847 */
     848void btree_remove(btree_t *t, btree_key_t key, btree_node_t *leaf_node)
     849{
     850        btree_node_t *lnode;
     851       
     852        lnode = leaf_node;
     853        if (!lnode) {
     854                if (!btree_search(t, key, &lnode))
     855                        panic("B-tree %p does not contain key %" PRIu64 ".", t, key);
     856        }
     857       
     858        _btree_remove(t, key, lnode);
     859}
     860
    309861/** Search key in a B-tree.
    310862 *
    311  * @param t B-tree.
    312  * @param key Key to be searched.
     863 * @param t         B-tree.
     864 * @param key       Key to be searched.
    313865 * @param leaf_node Address where to put pointer to visited leaf node.
    314866 *
    315867 * @return Pointer to value or NULL if there is no such key.
     868 *
    316869 */
    317870void *btree_search(btree_t *t, btree_key_t key, btree_node_t **leaf_node)
     
    323876         */
    324877        for (cur = t->root; cur; cur = next) {
    325 
    326                 /* Last iteration will set this with proper leaf node address. */
     878                /*
     879                 * Last iteration will set this with proper
     880                 * leaf node address.
     881                 */
    327882                *leaf_node = cur;
    328883               
     
    337892                        void *val;
    338893                        size_t i;
    339                
     894                       
    340895                        /*
    341896                         * Now if the key is smaller than cur->key[i]
     
    347902                                        next = cur->subtree[i];
    348903                                        val = cur->value[i - 1];
    349 
     904                                       
    350905                                        if (LEAF_NODE(cur))
    351906                                                return key == cur->key[i - 1] ? val : NULL;
    352 
     907                                       
    353908                                        goto descend;
    354                                 } 
     909                                }
    355910                        }
    356911                       
    357912                        /*
    358                          * Last possibility is that the key is in the rightmost subtree.
     913                         * Last possibility is that the key is
     914                         * in the rightmost subtree.
    359915                         */
    360916                        next = cur->subtree[i];
    361917                        val = cur->value[i - 1];
     918                       
    362919                        if (LEAF_NODE(cur))
    363920                                return key == cur->key[i - 1] ? val : NULL;
    364921                }
    365922                descend:
    366                         ;
    367         }
    368 
     923                ;
     924        }
     925       
    369926        /*
    370          * The key was not found in the *leaf_node and is smaller than any of its keys.
     927         * The key was not found in the *leaf_node and
     928         * is smaller than any of its keys.
    371929         */
    372930        return NULL;
     
    375933/** Return pointer to B-tree leaf node's left neighbour.
    376934 *
    377  * @param t B-tree.
     935 * @param t    B-tree.
    378936 * @param node Node whose left neighbour will be returned.
    379937 *
    380  * @return Left neighbour of the node or NULL if the node does not have the left neighbour.
     938 * @return Left neighbour of the node or NULL if the node
     939 *         does not have the left neighbour.
     940 *
    381941 */
    382942btree_node_t *btree_leaf_node_left_neighbour(btree_t *t, btree_node_t *node)
    383943{
    384944        ASSERT(LEAF_NODE(node));
     945       
    385946        if (node->leaf_link.prev != &t->leaf_head)
    386947                return list_get_instance(node->leaf_link.prev, btree_node_t, leaf_link);
     
    391952/** Return pointer to B-tree leaf node's right neighbour.
    392953 *
    393  * @param t B-tree.
     954 * @param t    B-tree.
    394955 * @param node Node whose right neighbour will be returned.
    395956 *
    396  * @return Right neighbour of the node or NULL if the node does not have the right neighbour.
     957 * @return Right neighbour of the node or NULL if the node
     958 *         does not have the right neighbour.
     959 *
    397960 */
    398961btree_node_t *btree_leaf_node_right_neighbour(btree_t *t, btree_node_t *node)
    399962{
    400963        ASSERT(LEAF_NODE(node));
     964       
    401965        if (node->leaf_link.next != &t->leaf_head)
    402966                return list_get_instance(node->leaf_link.next, btree_node_t, leaf_link);
     
    405969}
    406970
    407 /** Initialize B-tree node.
    408  *
    409  * @param node B-tree node.
    410  */
    411 void node_initialize(btree_node_t *node)
    412 {
    413         int i;
    414 
    415         node->keys = 0;
    416        
    417         /* Clean also space for the extra key. */
    418         for (i = 0; i < BTREE_MAX_KEYS + 1; i++) {
    419                 node->key[i] = 0;
    420                 node->value[i] = NULL;
    421                 node->subtree[i] = NULL;
    422         }
    423         node->subtree[i] = NULL;
    424        
    425         node->parent = NULL;
    426        
    427         link_initialize(&node->leaf_link);
    428 
    429         link_initialize(&node->bfs_link);
    430         node->depth = 0;
    431 }
    432 
    433 /** Insert key-value-lsubtree triplet into B-tree node.
    434  *
    435  * It is actually possible to have more keys than BTREE_MAX_KEYS.
    436  * This feature is used during insert by right rotation.
    437  *
    438  * @param node B-tree node into wich the new key is to be inserted.
    439  * @param key The key to be inserted.
    440  * @param value Pointer to value to be inserted.
    441  * @param lsubtree Pointer to the left subtree.
    442  */
    443 void node_insert_key_and_lsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *lsubtree)
    444 {
    445         size_t i;
    446 
    447         for (i = 0; i < node->keys; i++) {
    448                 if (key < node->key[i]) {
    449                         size_t j;
    450                
    451                         for (j = node->keys; j > i; j--) {
    452                                 node->key[j] = node->key[j - 1];
    453                                 node->value[j] = node->value[j - 1];
    454                                 node->subtree[j + 1] = node->subtree[j];
    455                         }
    456                         node->subtree[j + 1] = node->subtree[j];
    457                         break; 
    458                 }
    459         }
    460         node->key[i] = key;
    461         node->value[i] = value;
    462         node->subtree[i] = lsubtree;
    463                        
    464         node->keys++;
    465 }
    466 
    467 /** Insert key-value-rsubtree triplet into B-tree node.
    468  *
    469  * It is actually possible to have more keys than BTREE_MAX_KEYS.
    470  * This feature is used during splitting the node when the
    471  * number of keys is BTREE_MAX_KEYS + 1. Insert by left rotation
    472  * also makes use of this feature.
    473  *
    474  * @param node B-tree node into wich the new key is to be inserted.
    475  * @param key The key to be inserted.
    476  * @param value Pointer to value to be inserted.
    477  * @param rsubtree Pointer to the right subtree.
    478  */
    479 void node_insert_key_and_rsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree)
    480 {
    481         size_t i;
    482 
    483         for (i = 0; i < node->keys; i++) {
    484                 if (key < node->key[i]) {
    485                         size_t j;
    486                
    487                         for (j = node->keys; j > i; j--) {
    488                                 node->key[j] = node->key[j - 1];
    489                                 node->value[j] = node->value[j - 1];
    490                                 node->subtree[j + 1] = node->subtree[j];
    491                         }
    492                         break; 
    493                 }
    494         }
    495         node->key[i] = key;
    496         node->value[i] = value;
    497         node->subtree[i + 1] = rsubtree;
    498                        
    499         node->keys++;
    500 }
    501 
    502 /** Remove key and its left subtree pointer from B-tree node.
    503  *
    504  * Remove the key and eliminate gaps in node->key array.
    505  * Note that the value pointer and the left subtree pointer
    506  * is removed from the node as well.
    507  *
    508  * @param node B-tree node.
    509  * @param key Key to be removed.
    510  */
    511 void node_remove_key_and_lsubtree(btree_node_t *node, btree_key_t key)
    512 {
    513         size_t i, j;
    514        
    515         for (i = 0; i < node->keys; i++) {
    516                 if (key == node->key[i]) {
    517                         for (j = i + 1; j < node->keys; j++) {
    518                                 node->key[j - 1] = node->key[j];
    519                                 node->value[j - 1] = node->value[j];
    520                                 node->subtree[j - 1] = node->subtree[j];
    521                         }
    522                         node->subtree[j - 1] = node->subtree[j];
    523                         node->keys--;
    524                         return;
    525                 }
    526         }
    527         panic("Node %p does not contain key %" PRIu64 ".", node, key);
    528 }
    529 
    530 /** Remove key and its right subtree pointer from B-tree node.
    531  *
    532  * Remove the key and eliminate gaps in node->key array.
    533  * Note that the value pointer and the right subtree pointer
    534  * is removed from the node as well.
    535  *
    536  * @param node B-tree node.
    537  * @param key Key to be removed.
    538  */
    539 void node_remove_key_and_rsubtree(btree_node_t *node, btree_key_t key)
    540 {
    541         size_t i, j;
    542        
    543         for (i = 0; i < node->keys; i++) {
    544                 if (key == node->key[i]) {
    545                         for (j = i + 1; j < node->keys; j++) {
    546                                 node->key[j - 1] = node->key[j];
    547                                 node->value[j - 1] = node->value[j];
    548                                 node->subtree[j] = node->subtree[j + 1];
    549                         }
    550                         node->keys--;
    551                         return;
    552                 }
    553         }
    554         panic("Node %p does not contain key %" PRIu64 ".", node, key);
    555 }
    556 
    557 /** Split full B-tree node and insert new key-value-right-subtree triplet.
    558  *
    559  * This function will split a node and return a pointer to a newly created
    560  * node containing keys greater than or equal to the greater of medians
    561  * (or median) of the old keys and the newly added key. It will also write
    562  * the median key to a memory address supplied by the caller.
    563  *
    564  * If the node being split is an index node, the median will not be
    565  * included in the new node. If the node is a leaf node,
    566  * the median will be copied there.
    567  *
    568  * @param node B-tree node wich is going to be split.
    569  * @param key The key to be inserted.
    570  * @param value Pointer to the value to be inserted.
    571  * @param rsubtree Pointer to the right subtree of the key being added.
    572  * @param median Address in memory, where the median key will be stored.
    573  *
    574  * @return Newly created right sibling of node.
    575  */
    576 btree_node_t *node_split(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree, btree_key_t *median)
    577 {
    578         btree_node_t *rnode;
    579         size_t i, j;
    580 
    581         ASSERT(median);
    582         ASSERT(node->keys == BTREE_MAX_KEYS);
    583 
    584         /*
    585          * Use the extra space to store the extra node.
    586          */
    587         node_insert_key_and_rsubtree(node, key, value, rsubtree);
    588 
    589         /*
    590          * Compute median of keys.
    591          */
    592         *median = MEDIAN_HIGH(node);
    593                
    594         /*
    595          * Allocate and initialize new right sibling.
    596          */
    597         rnode = (btree_node_t *) slab_alloc(btree_node_slab, 0);
    598         node_initialize(rnode);
    599         rnode->parent = node->parent;
    600         rnode->depth = node->depth;
    601        
    602         /*
    603          * Copy big keys, values and subtree pointers to the new right sibling.
    604          * If this is an index node, do not copy the median.
    605          */
    606         i = (size_t) INDEX_NODE(node);
    607         for (i += MEDIAN_HIGH_INDEX(node), j = 0; i < node->keys; i++, j++) {
    608                 rnode->key[j] = node->key[i];
    609                 rnode->value[j] = node->value[i];
    610                 rnode->subtree[j] = node->subtree[i];
    611                
    612                 /*
    613                  * Fix parent links in subtrees.
    614                  */
    615                 if (rnode->subtree[j])
    616                         rnode->subtree[j]->parent = rnode;
    617                        
    618         }
    619         rnode->subtree[j] = node->subtree[i];
    620         if (rnode->subtree[j])
    621                 rnode->subtree[j]->parent = rnode;
    622 
    623         rnode->keys = j;        /* Set number of keys of the new node. */
    624         node->keys /= 2;        /* Shrink the old node. */
    625                
    626         return rnode;
    627 }
    628 
    629 /** Combine node with any of its siblings.
    630  *
    631  * The siblings are required to be below the fill factor.
    632  *
    633  * @param node Node to combine with one of its siblings.
    634  *
    635  * @return Pointer to the rightmost of the two nodes.
    636  */
    637 btree_node_t *node_combine(btree_node_t *node)
    638 {
    639         size_t idx;
    640         btree_node_t *rnode;
    641         size_t i;
    642 
    643         ASSERT(!ROOT_NODE(node));
    644        
    645         idx = find_key_by_subtree(node->parent, node, false);
    646         if (idx == node->parent->keys) {
    647                 /*
    648                  * Rightmost subtree of its parent, combine with the left sibling.
    649                  */
    650                 idx--;
    651                 rnode = node;
    652                 node = node->parent->subtree[idx];
    653         } else {
    654                 rnode = node->parent->subtree[idx + 1];
    655         }
    656 
    657         /* Index nodes need to insert parent node key in between left and right node. */
    658         if (INDEX_NODE(node))
    659                 node->key[node->keys++] = node->parent->key[idx];
    660        
    661         /* Copy the key-value-subtree triplets from the right node. */
    662         for (i = 0; i < rnode->keys; i++) {
    663                 node->key[node->keys + i] = rnode->key[i];
    664                 node->value[node->keys + i] = rnode->value[i];
    665                 if (INDEX_NODE(node)) {
    666                         node->subtree[node->keys + i] = rnode->subtree[i];
    667                         rnode->subtree[i]->parent = node;
    668                 }
    669         }
    670         if (INDEX_NODE(node)) {
    671                 node->subtree[node->keys + i] = rnode->subtree[i];
    672                 rnode->subtree[i]->parent = node;
    673         }
    674 
    675         node->keys += rnode->keys;
    676 
    677         return rnode;
    678 }
    679 
    680 /** Find key by its left or right subtree.
    681  *
    682  * @param node B-tree node.
    683  * @param subtree Left or right subtree of a key found in node.
    684  * @param right If true, subtree is a right subtree. If false, subtree is a left subtree.
    685  *
    686  * @return Index of the key associated with the subtree.
    687  */
    688 size_t find_key_by_subtree(btree_node_t *node, btree_node_t *subtree, bool right)
    689 {
    690         size_t i;
    691        
    692         for (i = 0; i < node->keys + 1; i++) {
    693                 if (subtree == node->subtree[i])
    694                         return i - (int) (right != false);
    695         }
    696         panic("Node %p does not contain subtree %p.", node, subtree);
    697 }
    698 
    699 /** Rotate one key-value-rsubtree triplet from the left sibling to the right sibling.
    700  *
    701  * The biggest key and its value and right subtree is rotated from the left node
    702  * to the right. If the node is an index node, than the parent node key belonging to
    703  * the left node takes part in the rotation.
    704  *
    705  * @param lnode Left sibling.
    706  * @param rnode Right sibling.
    707  * @param idx Index of the parent node key that is taking part in the rotation.
    708  */
    709 void rotate_from_left(btree_node_t *lnode, btree_node_t *rnode, size_t idx)
    710 {
    711         btree_key_t key;
    712 
    713         key = lnode->key[lnode->keys - 1];
    714                
    715         if (LEAF_NODE(lnode)) {
    716                 void *value;
    717 
    718                 value = lnode->value[lnode->keys - 1];
    719                 node_remove_key_and_rsubtree(lnode, key);
    720                 node_insert_key_and_lsubtree(rnode, key, value, NULL);
    721                 lnode->parent->key[idx] = key;
    722         } else {
    723                 btree_node_t *rsubtree;
    724 
    725                 rsubtree = lnode->subtree[lnode->keys];
    726                 node_remove_key_and_rsubtree(lnode, key);
    727                 node_insert_key_and_lsubtree(rnode, lnode->parent->key[idx], NULL, rsubtree);
    728                 lnode->parent->key[idx] = key;
    729 
    730                 /* Fix parent link of the reconnected right subtree. */
    731                 rsubtree->parent = rnode;
    732         }
    733 
    734 }
    735 
    736 /** Rotate one key-value-lsubtree triplet from the right sibling to the left sibling.
    737  *
    738  * The smallest key and its value and left subtree is rotated from the right node
    739  * to the left. If the node is an index node, than the parent node key belonging to
    740  * the right node takes part in the rotation.
    741  *
    742  * @param lnode Left sibling.
    743  * @param rnode Right sibling.
    744  * @param idx Index of the parent node key that is taking part in the rotation.
    745  */
    746 void rotate_from_right(btree_node_t *lnode, btree_node_t *rnode, size_t idx)
    747 {
    748         btree_key_t key;
    749 
    750         key = rnode->key[0];
    751                
    752         if (LEAF_NODE(rnode)) {
    753                 void *value;
    754 
    755                 value = rnode->value[0];
    756                 node_remove_key_and_lsubtree(rnode, key);
    757                 node_insert_key_and_rsubtree(lnode, key, value, NULL);
    758                 rnode->parent->key[idx] = rnode->key[0];
    759         } else {
    760                 btree_node_t *lsubtree;
    761 
    762                 lsubtree = rnode->subtree[0];
    763                 node_remove_key_and_lsubtree(rnode, key);
    764                 node_insert_key_and_rsubtree(lnode, rnode->parent->key[idx], NULL, lsubtree);
    765                 rnode->parent->key[idx] = key;
    766 
    767                 /* Fix parent link of the reconnected left subtree. */
    768                 lsubtree->parent = lnode;
    769         }
    770 
    771 }
    772 
    773 /** Insert key-value-rsubtree triplet and rotate the node to the left, if this operation can be done.
    774  *
    775  * Left sibling of the node (if it exists) is checked for free space.
    776  * If there is free space, the key is inserted and the smallest key of
    777  * the node is moved there. The index node which is the parent of both
    778  * nodes is fixed.
    779  *
    780  * @param node B-tree node.
    781  * @param inskey Key to be inserted.
    782  * @param insvalue Value to be inserted.
    783  * @param rsubtree Right subtree of inskey.
    784  *
    785  * @return True if the rotation was performed, false otherwise.
    786  */
    787 bool try_insert_by_rotation_to_left(btree_node_t *node, btree_key_t inskey, void *insvalue, btree_node_t *rsubtree)
    788 {
    789         size_t idx;
    790         btree_node_t *lnode;
    791 
    792         /*
    793          * If this is root node, the rotation can not be done.
    794          */
    795         if (ROOT_NODE(node))
    796                 return false;
    797        
    798         idx = find_key_by_subtree(node->parent, node, true);
    799         if ((int) idx == -1) {
    800                 /*
    801                  * If this node is the leftmost subtree of its parent,
    802                  * the rotation can not be done.
    803                  */
    804                 return false;
    805         }
    806                
    807         lnode = node->parent->subtree[idx];
    808         if (lnode->keys < BTREE_MAX_KEYS) {
    809                 /*
    810                  * The rotaion can be done. The left sibling has free space.
    811                  */
    812                 node_insert_key_and_rsubtree(node, inskey, insvalue, rsubtree);
    813                 rotate_from_right(lnode, node, idx);
    814                 return true;
    815         }
    816 
    817         return false;
    818 }
    819 
    820 /** Insert key-value-rsubtree triplet and rotate the node to the right, if this operation can be done.
    821  *
    822  * Right sibling of the node (if it exists) is checked for free space.
    823  * If there is free space, the key is inserted and the biggest key of
    824  * the node is moved there. The index node which is the parent of both
    825  * nodes is fixed.
    826  *
    827  * @param node B-tree node.
    828  * @param inskey Key to be inserted.
    829  * @param insvalue Value to be inserted.
    830  * @param rsubtree Right subtree of inskey.
    831  *
    832  * @return True if the rotation was performed, false otherwise.
    833  */
    834 bool try_insert_by_rotation_to_right(btree_node_t *node, btree_key_t inskey, void *insvalue, btree_node_t *rsubtree)
    835 {
    836         size_t idx;
    837         btree_node_t *rnode;
    838 
    839         /*
    840          * If this is root node, the rotation can not be done.
    841          */
    842         if (ROOT_NODE(node))
    843                 return false;
    844        
    845         idx = find_key_by_subtree(node->parent, node, false);
    846         if (idx == node->parent->keys) {
    847                 /*
    848                  * If this node is the rightmost subtree of its parent,
    849                  * the rotation can not be done.
    850                  */
    851                 return false;
    852         }
    853                
    854         rnode = node->parent->subtree[idx + 1];
    855         if (rnode->keys < BTREE_MAX_KEYS) {
    856                 /*
    857                  * The rotaion can be done. The right sibling has free space.
    858                  */
    859                 node_insert_key_and_rsubtree(node, inskey, insvalue, rsubtree);
    860                 rotate_from_left(node, rnode, idx);
    861                 return true;
    862         }
    863 
    864         return false;
    865 }
    866 
    867 /** Rotate in a key from the left sibling or from the index node, if this operation can be done.
    868  *
    869  * @param rnode Node into which to add key from its left sibling or from the index node.
    870  *
    871  * @return True if the rotation was performed, false otherwise.
    872  */
    873 bool try_rotation_from_left(btree_node_t *rnode)
    874 {
    875         size_t idx;
    876         btree_node_t *lnode;
    877 
    878         /*
    879          * If this is root node, the rotation can not be done.
    880          */
    881         if (ROOT_NODE(rnode))
    882                 return false;
    883        
    884         idx = find_key_by_subtree(rnode->parent, rnode, true);
    885         if ((int) idx == -1) {
    886                 /*
    887                  * If this node is the leftmost subtree of its parent,
    888                  * the rotation can not be done.
    889                  */
    890                 return false;
    891         }
    892                
    893         lnode = rnode->parent->subtree[idx];
    894         if (lnode->keys > FILL_FACTOR) {
    895                 rotate_from_left(lnode, rnode, idx);
    896                 return true;
    897         }
    898        
    899         return false;
    900 }
    901 
    902 /** Rotate in a key from the right sibling or from the index node, if this operation can be done.
    903  *
    904  * @param lnode Node into which to add key from its right sibling or from the index node.
    905  *
    906  * @return True if the rotation was performed, false otherwise.
    907  */
    908 bool try_rotation_from_right(btree_node_t *lnode)
    909 {
    910         size_t idx;
    911         btree_node_t *rnode;
    912 
    913         /*
    914          * If this is root node, the rotation can not be done.
    915          */
    916         if (ROOT_NODE(lnode))
    917                 return false;
    918        
    919         idx = find_key_by_subtree(lnode->parent, lnode, false);
    920         if (idx == lnode->parent->keys) {
    921                 /*
    922                  * If this node is the rightmost subtree of its parent,
    923                  * the rotation can not be done.
    924                  */
    925                 return false;
    926         }
    927                
    928         rnode = lnode->parent->subtree[idx + 1];
    929         if (rnode->keys > FILL_FACTOR) {
    930                 rotate_from_right(lnode, rnode, idx);
    931                 return true;
    932         }       
    933 
    934         return false;
    935 }
    936 
    937971/** Print B-tree.
    938972 *
    939973 * @param t Print out B-tree.
     974 *
    940975 */
    941976void btree_print(btree_t *t)
     
    944979        int depth = t->root->depth;
    945980        link_t head, *cur;
    946 
     981       
    947982        printf("Printing B-tree:\n");
    948983        list_initialize(&head);
    949984        list_append(&t->root->bfs_link, &head);
    950 
     985       
    951986        /*
    952987         * Use BFS search to print out the tree.
    953988         * Levels are distinguished from one another by node->depth.
    954          */     
     989         */
    955990        while (!list_empty(&head)) {
    956991                link_t *hlp;
     
    9681003                        depth = node->depth;
    9691004                }
    970 
     1005               
    9711006                printf("(");
     1007               
    9721008                for (i = 0; i < node->keys; i++) {
    9731009                        printf("%" PRIu64 "%s", node->key[i], i < node->keys - 1 ? "," : "");
     
    9761012                        }
    9771013                }
    978                 if (node->depth && node->subtree[i]) {
     1014               
     1015                if (node->depth && node->subtree[i])
    9791016                        list_append(&node->subtree[i]->bfs_link, &head);
    980                 }
     1017               
    9811018                printf(")");
    9821019        }
     1020       
    9831021        printf("\n");
    9841022       
     
    9901028               
    9911029                ASSERT(node);
    992 
     1030               
    9931031                printf("(");
     1032               
    9941033                for (i = 0; i < node->keys; i++)
    9951034                        printf("%" PRIu64 "%s", node->key[i], i < node->keys - 1 ? "," : "");
     1035               
    9961036                printf(")");
    9971037        }
     1038       
    9981039        printf("\n");
    9991040}
  • kernel/generic/src/cpu/cpu.c

    rb5382d4f re3ee9b9  
    119119/** @}
    120120 */
    121 
  • kernel/generic/src/mm/as.c

    rb5382d4f re3ee9b9  
    116116as_t *AS_KERNEL = NULL;
    117117
    118 static unsigned int area_flags_to_page_flags(unsigned int);
    119 static as_area_t *find_area_and_lock(as_t *, uintptr_t);
    120 static bool check_area_conflicts(as_t *, uintptr_t, size_t, as_area_t *);
    121 static void sh_info_remove_reference(share_info_t *);
    122 
    123118static int as_constructor(void *obj, unsigned int flags)
    124119{
     
    296291        if (atomic_predec(&as->refcount) == 0)
    297292                as_destroy(as);
     293}
     294
     295/** Check area conflicts with other areas.
     296 *
     297 * @param as         Address space.
     298 * @param va         Starting virtual address of the area being tested.
     299 * @param size       Size of the area being tested.
     300 * @param avoid_area Do not touch this area.
     301 *
     302 * @return True if there is no conflict, false otherwise.
     303 *
     304 */
     305static bool check_area_conflicts(as_t *as, uintptr_t va, size_t size,
     306    as_area_t *avoid_area)
     307{
     308        ASSERT(mutex_locked(&as->lock));
     309       
     310        /*
     311         * We don't want any area to have conflicts with NULL page.
     312         *
     313         */
     314        if (overlaps(va, size, NULL, PAGE_SIZE))
     315                return false;
     316       
     317        /*
     318         * The leaf node is found in O(log n), where n is proportional to
     319         * the number of address space areas belonging to as.
     320         * The check for conflicts is then attempted on the rightmost
     321         * record in the left neighbour, the leftmost record in the right
     322         * neighbour and all records in the leaf node itself.
     323         *
     324         */
     325        btree_node_t *leaf;
     326        as_area_t *area =
     327            (as_area_t *) btree_search(&as->as_area_btree, va, &leaf);
     328        if (area) {
     329                if (area != avoid_area)
     330                        return false;
     331        }
     332       
     333        /* First, check the two border cases. */
     334        btree_node_t *node =
     335            btree_leaf_node_left_neighbour(&as->as_area_btree, leaf);
     336        if (node) {
     337                area = (as_area_t *) node->value[node->keys - 1];
     338               
     339                mutex_lock(&area->lock);
     340               
     341                if (overlaps(va, size, area->base, area->pages * PAGE_SIZE)) {
     342                        mutex_unlock(&area->lock);
     343                        return false;
     344                }
     345               
     346                mutex_unlock(&area->lock);
     347        }
     348       
     349        node = btree_leaf_node_right_neighbour(&as->as_area_btree, leaf);
     350        if (node) {
     351                area = (as_area_t *) node->value[0];
     352               
     353                mutex_lock(&area->lock);
     354               
     355                if (overlaps(va, size, area->base, area->pages * PAGE_SIZE)) {
     356                        mutex_unlock(&area->lock);
     357                        return false;
     358                }
     359               
     360                mutex_unlock(&area->lock);
     361        }
     362       
     363        /* Second, check the leaf node. */
     364        btree_key_t i;
     365        for (i = 0; i < leaf->keys; i++) {
     366                area = (as_area_t *) leaf->value[i];
     367               
     368                if (area == avoid_area)
     369                        continue;
     370               
     371                mutex_lock(&area->lock);
     372               
     373                if (overlaps(va, size, area->base, area->pages * PAGE_SIZE)) {
     374                        mutex_unlock(&area->lock);
     375                        return false;
     376                }
     377               
     378                mutex_unlock(&area->lock);
     379        }
     380       
     381        /*
     382         * So far, the area does not conflict with other areas.
     383         * Check if it doesn't conflict with kernel address space.
     384         *
     385         */
     386        if (!KERNEL_ADDRESS_SPACE_SHADOWED) {
     387                return !overlaps(va, size,
     388                    KERNEL_ADDRESS_SPACE_START,
     389                    KERNEL_ADDRESS_SPACE_END - KERNEL_ADDRESS_SPACE_START);
     390        }
     391       
     392        return true;
    298393}
    299394
     
    357452       
    358453        return area;
     454}
     455
     456/** Find address space area and lock it.
     457 *
     458 * @param as Address space.
     459 * @param va Virtual address.
     460 *
     461 * @return Locked address space area containing va on success or
     462 *         NULL on failure.
     463 *
     464 */
     465static as_area_t *find_area_and_lock(as_t *as, uintptr_t va)
     466{
     467        ASSERT(mutex_locked(&as->lock));
     468       
     469        btree_node_t *leaf;
     470        as_area_t *area = (as_area_t *) btree_search(&as->as_area_btree, va, &leaf);
     471        if (area) {
     472                /* va is the base address of an address space area */
     473                mutex_lock(&area->lock);
     474                return area;
     475        }
     476       
     477        /*
     478         * Search the leaf node and the righmost record of its left neighbour
     479         * to find out whether this is a miss or va belongs to an address
     480         * space area found there.
     481         *
     482         */
     483       
     484        /* First, search the leaf node itself. */
     485        btree_key_t i;
     486       
     487        for (i = 0; i < leaf->keys; i++) {
     488                area = (as_area_t *) leaf->value[i];
     489               
     490                mutex_lock(&area->lock);
     491               
     492                if ((area->base <= va) && (va < area->base + area->pages * PAGE_SIZE))
     493                        return area;
     494               
     495                mutex_unlock(&area->lock);
     496        }
     497       
     498        /*
     499         * Second, locate the left neighbour and test its last record.
     500         * Because of its position in the B+tree, it must have base < va.
     501         *
     502         */
     503        btree_node_t *lnode = btree_leaf_node_left_neighbour(&as->as_area_btree, leaf);
     504        if (lnode) {
     505                area = (as_area_t *) lnode->value[lnode->keys - 1];
     506               
     507                mutex_lock(&area->lock);
     508               
     509                if (va < area->base + area->pages * PAGE_SIZE)
     510                        return area;
     511               
     512                mutex_unlock(&area->lock);
     513        }
     514       
     515        return NULL;
    359516}
    360517
     
    553710}
    554711
     712/** Remove reference to address space area share info.
     713 *
     714 * If the reference count drops to 0, the sh_info is deallocated.
     715 *
     716 * @param sh_info Pointer to address space area share info.
     717 *
     718 */
     719static void sh_info_remove_reference(share_info_t *sh_info)
     720{
     721        bool dealloc = false;
     722       
     723        mutex_lock(&sh_info->lock);
     724        ASSERT(sh_info->refcount);
     725       
     726        if (--sh_info->refcount == 0) {
     727                dealloc = true;
     728                link_t *cur;
     729               
     730                /*
     731                 * Now walk carefully the pagemap B+tree and free/remove
     732                 * reference from all frames found there.
     733                 */
     734                for (cur = sh_info->pagemap.leaf_head.next;
     735                    cur != &sh_info->pagemap.leaf_head; cur = cur->next) {
     736                        btree_node_t *node
     737                            = list_get_instance(cur, btree_node_t, leaf_link);
     738                        btree_key_t i;
     739                       
     740                        for (i = 0; i < node->keys; i++)
     741                                frame_free((uintptr_t) node->value[i]);
     742                }
     743               
     744        }
     745        mutex_unlock(&sh_info->lock);
     746       
     747        if (dealloc) {
     748                btree_destroy(&sh_info->pagemap);
     749                free(sh_info);
     750        }
     751}
     752
    555753/** Destroy address space area.
    556754 *
     
    8051003}
    8061004
     1005/** Convert address space area flags to page flags.
     1006 *
     1007 * @param aflags Flags of some address space area.
     1008 *
     1009 * @return Flags to be passed to page_mapping_insert().
     1010 *
     1011 */
     1012static unsigned int area_flags_to_page_flags(unsigned int aflags)
     1013{
     1014        unsigned int flags = PAGE_USER | PAGE_PRESENT;
     1015       
     1016        if (aflags & AS_AREA_READ)
     1017                flags |= PAGE_READ;
     1018               
     1019        if (aflags & AS_AREA_WRITE)
     1020                flags |= PAGE_WRITE;
     1021       
     1022        if (aflags & AS_AREA_EXEC)
     1023                flags |= PAGE_EXEC;
     1024       
     1025        if (aflags & AS_AREA_CACHEABLE)
     1026                flags |= PAGE_CACHEABLE;
     1027       
     1028        return flags;
     1029}
     1030
    8071031/** Change adress space area flags.
    8081032 *
     
    11611385}
    11621386
    1163 /** Convert address space area flags to page flags.
    1164  *
    1165  * @param aflags Flags of some address space area.
    1166  *
    1167  * @return Flags to be passed to page_mapping_insert().
    1168  *
    1169  */
    1170 unsigned int area_flags_to_page_flags(unsigned int aflags)
    1171 {
    1172         unsigned int flags = PAGE_USER | PAGE_PRESENT;
    1173        
    1174         if (aflags & AS_AREA_READ)
    1175                 flags |= PAGE_READ;
    1176                
    1177         if (aflags & AS_AREA_WRITE)
    1178                 flags |= PAGE_WRITE;
    1179        
    1180         if (aflags & AS_AREA_EXEC)
    1181                 flags |= PAGE_EXEC;
    1182        
    1183         if (aflags & AS_AREA_CACHEABLE)
    1184                 flags |= PAGE_CACHEABLE;
    1185        
    1186         return flags;
    1187 }
     1387
    11881388
    11891389/** Compute flags for virtual address translation subsytem.
     
    12721472/** Test whether page tables are locked.
    12731473 *
    1274  * @param as            Address space where the page tables belong.
    1275  *
    1276  * @return              True if the page tables belonging to the address soace
    1277  *                      are locked, otherwise false.
     1474 * @param as Address space where the page tables belong.
     1475 *
     1476 * @return True if the page tables belonging to the address soace
     1477 *         are locked, otherwise false.
    12781478 */
    12791479bool page_table_locked(as_t *as)
     
    12831483
    12841484        return as_operations->page_table_locked(as);
    1285 }
    1286 
    1287 
    1288 /** Find address space area and lock it.
    1289  *
    1290  * @param as Address space.
    1291  * @param va Virtual address.
    1292  *
    1293  * @return Locked address space area containing va on success or
    1294  *         NULL on failure.
    1295  *
    1296  */
    1297 as_area_t *find_area_and_lock(as_t *as, uintptr_t va)
    1298 {
    1299         ASSERT(mutex_locked(&as->lock));
    1300 
    1301         btree_node_t *leaf;
    1302         as_area_t *area = (as_area_t *) btree_search(&as->as_area_btree, va, &leaf);
    1303         if (area) {
    1304                 /* va is the base address of an address space area */
    1305                 mutex_lock(&area->lock);
    1306                 return area;
    1307         }
    1308        
    1309         /*
    1310          * Search the leaf node and the righmost record of its left neighbour
    1311          * to find out whether this is a miss or va belongs to an address
    1312          * space area found there.
    1313          *
    1314          */
    1315        
    1316         /* First, search the leaf node itself. */
    1317         btree_key_t i;
    1318        
    1319         for (i = 0; i < leaf->keys; i++) {
    1320                 area = (as_area_t *) leaf->value[i];
    1321                
    1322                 mutex_lock(&area->lock);
    1323                
    1324                 if ((area->base <= va) && (va < area->base + area->pages * PAGE_SIZE))
    1325                         return area;
    1326                
    1327                 mutex_unlock(&area->lock);
    1328         }
    1329        
    1330         /*
    1331          * Second, locate the left neighbour and test its last record.
    1332          * Because of its position in the B+tree, it must have base < va.
    1333          *
    1334          */
    1335         btree_node_t *lnode = btree_leaf_node_left_neighbour(&as->as_area_btree, leaf);
    1336         if (lnode) {
    1337                 area = (as_area_t *) lnode->value[lnode->keys - 1];
    1338                
    1339                 mutex_lock(&area->lock);
    1340                
    1341                 if (va < area->base + area->pages * PAGE_SIZE)
    1342                         return area;
    1343                
    1344                 mutex_unlock(&area->lock);
    1345         }
    1346        
    1347         return NULL;
    1348 }
    1349 
    1350 /** Check area conflicts with other areas.
    1351  *
    1352  * @param as         Address space.
    1353  * @param va         Starting virtual address of the area being tested.
    1354  * @param size       Size of the area being tested.
    1355  * @param avoid_area Do not touch this area.
    1356  *
    1357  * @return True if there is no conflict, false otherwise.
    1358  *
    1359  */
    1360 bool check_area_conflicts(as_t *as, uintptr_t va, size_t size,
    1361     as_area_t *avoid_area)
    1362 {
    1363         ASSERT(mutex_locked(&as->lock));
    1364 
    1365         /*
    1366          * We don't want any area to have conflicts with NULL page.
    1367          *
    1368          */
    1369         if (overlaps(va, size, NULL, PAGE_SIZE))
    1370                 return false;
    1371        
    1372         /*
    1373          * The leaf node is found in O(log n), where n is proportional to
    1374          * the number of address space areas belonging to as.
    1375          * The check for conflicts is then attempted on the rightmost
    1376          * record in the left neighbour, the leftmost record in the right
    1377          * neighbour and all records in the leaf node itself.
    1378          *
    1379          */
    1380         btree_node_t *leaf;
    1381         as_area_t *area =
    1382             (as_area_t *) btree_search(&as->as_area_btree, va, &leaf);
    1383         if (area) {
    1384                 if (area != avoid_area)
    1385                         return false;
    1386         }
    1387        
    1388         /* First, check the two border cases. */
    1389         btree_node_t *node =
    1390             btree_leaf_node_left_neighbour(&as->as_area_btree, leaf);
    1391         if (node) {
    1392                 area = (as_area_t *) node->value[node->keys - 1];
    1393                
    1394                 mutex_lock(&area->lock);
    1395                
    1396                 if (overlaps(va, size, area->base, area->pages * PAGE_SIZE)) {
    1397                         mutex_unlock(&area->lock);
    1398                         return false;
    1399                 }
    1400                
    1401                 mutex_unlock(&area->lock);
    1402         }
    1403        
    1404         node = btree_leaf_node_right_neighbour(&as->as_area_btree, leaf);
    1405         if (node) {
    1406                 area = (as_area_t *) node->value[0];
    1407                
    1408                 mutex_lock(&area->lock);
    1409                
    1410                 if (overlaps(va, size, area->base, area->pages * PAGE_SIZE)) {
    1411                         mutex_unlock(&area->lock);
    1412                         return false;
    1413                 }
    1414                
    1415                 mutex_unlock(&area->lock);
    1416         }
    1417        
    1418         /* Second, check the leaf node. */
    1419         btree_key_t i;
    1420         for (i = 0; i < leaf->keys; i++) {
    1421                 area = (as_area_t *) leaf->value[i];
    1422                
    1423                 if (area == avoid_area)
    1424                         continue;
    1425                
    1426                 mutex_lock(&area->lock);
    1427                
    1428                 if (overlaps(va, size, area->base, area->pages * PAGE_SIZE)) {
    1429                         mutex_unlock(&area->lock);
    1430                         return false;
    1431                 }
    1432                
    1433                 mutex_unlock(&area->lock);
    1434         }
    1435        
    1436         /*
    1437          * So far, the area does not conflict with other areas.
    1438          * Check if it doesn't conflict with kernel address space.
    1439          *
    1440          */
    1441         if (!KERNEL_ADDRESS_SPACE_SHADOWED) {
    1442                 return !overlaps(va, size,
    1443                     KERNEL_ADDRESS_SPACE_START,
    1444                     KERNEL_ADDRESS_SPACE_END - KERNEL_ADDRESS_SPACE_START);
    1445         }
    1446        
    1447         return true;
    14481485}
    14491486
     
    19601997}
    19611998
    1962 /** Remove reference to address space area share info.
    1963  *
    1964  * If the reference count drops to 0, the sh_info is deallocated.
    1965  *
    1966  * @param sh_info Pointer to address space area share info.
    1967  *
    1968  */
    1969 void sh_info_remove_reference(share_info_t *sh_info)
    1970 {
    1971         bool dealloc = false;
    1972        
    1973         mutex_lock(&sh_info->lock);
    1974         ASSERT(sh_info->refcount);
    1975        
    1976         if (--sh_info->refcount == 0) {
    1977                 dealloc = true;
    1978                 link_t *cur;
    1979                
    1980                 /*
    1981                  * Now walk carefully the pagemap B+tree and free/remove
    1982                  * reference from all frames found there.
    1983                  */
    1984                 for (cur = sh_info->pagemap.leaf_head.next;
    1985                     cur != &sh_info->pagemap.leaf_head; cur = cur->next) {
    1986                         btree_node_t *node
    1987                             = list_get_instance(cur, btree_node_t, leaf_link);
    1988                         btree_key_t i;
    1989                        
    1990                         for (i = 0; i < node->keys; i++)
    1991                                 frame_free((uintptr_t) node->value[i]);
    1992                 }
    1993                
    1994         }
    1995         mutex_unlock(&sh_info->lock);
    1996        
    1997         if (dealloc) {
    1998                 btree_destroy(&sh_info->pagemap);
    1999                 free(sh_info);
    2000         }
    2001 }
    2002 
    20031999/*
    20042000 * Address space related syscalls.
  • kernel/generic/src/mm/page.c

    rb5382d4f re3ee9b9  
    3838 * mappings between virtual addresses and physical addresses.
    3939 * Functions here are mere wrappers that call the real implementation.
    40  * They however, define the single interface. 
     40 * They however, define the single interface.
    4141 *
    4242 */
  • kernel/generic/src/proc/the.c

    rb5382d4f re3ee9b9  
    3333/**
    3434 * @file
    35  * @brief       THE structure functions.
     35 * @brief THE structure functions.
    3636 *
    3737 * This file contains functions to manage the THE structure.
     
    4343
    4444#include <arch.h>
    45 
    4645
    4746/** Initialize THE structure
Note: See TracChangeset for help on using the changeset viewer.