Subversion Repositories HelenOS-historic

Rev

Rev 1164 | Rev 1221 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 1164 Rev 1177
Line 44... Line 44...
44
#include <debug.h>
44
#include <debug.h>
45
#include <panic.h>
45
#include <panic.h>
46
#include <typedefs.h>
46
#include <typedefs.h>
47
#include <print.h>
47
#include <print.h>
48
 
48
 
49
static void _btree_insert(btree_t *t, __native key, void *value, btree_node_t *rsubtree, btree_node_t *node);
49
static void _btree_insert(btree_t *t, btree_key_t key, void *value, btree_node_t *rsubtree, btree_node_t *node);
50
static void _btree_remove(btree_t *t, __native key, btree_node_t *node);
50
static void _btree_remove(btree_t *t, btree_key_t key, btree_node_t *node);
51
static void node_initialize(btree_node_t *node);
51
static void node_initialize(btree_node_t *node);
52
static void node_insert_key_and_lsubtree(btree_node_t *node, __native key, void *value, btree_node_t *lsubtree);
52
static void node_insert_key_and_lsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *lsubtree);
53
static void node_insert_key_and_rsubtree(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree);
53
static void node_insert_key_and_rsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree);
54
static void node_remove_key_and_lsubtree(btree_node_t *node, __native key);
54
static void node_remove_key_and_lsubtree(btree_node_t *node, btree_key_t key);
55
static void node_remove_key_and_rsubtree(btree_node_t *node, __native key);
55
static void node_remove_key_and_rsubtree(btree_node_t *node, btree_key_t key);
56
static btree_node_t *node_split(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree, __native *median);
56
static btree_node_t *node_split(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree, btree_key_t *median);
57
static btree_node_t *node_combine(btree_node_t *node);
57
static btree_node_t *node_combine(btree_node_t *node);
58
static index_t find_key_by_subtree(btree_node_t *node, btree_node_t *subtree, bool right);
58
static index_t find_key_by_subtree(btree_node_t *node, btree_node_t *subtree, bool right);
59
static void rotate_from_right(btree_node_t *lnode, btree_node_t *rnode, index_t idx);
59
static void rotate_from_right(btree_node_t *lnode, btree_node_t *rnode, index_t idx);
60
static void rotate_from_left(btree_node_t *lnode, btree_node_t *rnode, index_t idx);
60
static void rotate_from_left(btree_node_t *lnode, btree_node_t *rnode, index_t idx);
61
static bool try_insert_by_rotation_to_left(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree);
61
static bool try_insert_by_rotation_to_left(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree);
62
static bool try_insert_by_rotation_to_right(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree);
62
static bool try_insert_by_rotation_to_right(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree);
63
static bool try_rotation_from_left(btree_node_t *rnode);
63
static bool try_rotation_from_left(btree_node_t *rnode);
64
static bool try_rotation_from_right(btree_node_t *lnode);
64
static bool try_rotation_from_right(btree_node_t *lnode);
65
 
65
 
66
#define ROOT_NODE(n)        (!(n)->parent)
66
#define ROOT_NODE(n)        (!(n)->parent)
67
#define INDEX_NODE(n)       ((n)->subtree[0] != NULL)
67
#define INDEX_NODE(n)       ((n)->subtree[0] != NULL)
Line 106... Line 106...
106
 * @param t B-tree.
106
 * @param t B-tree.
107
 * @param key Key to be inserted.
107
 * @param key Key to be inserted.
108
 * @param value Value to be inserted.
108
 * @param value Value to be inserted.
109
 * @param leaf_node Leaf node where the insertion should begin.
109
 * @param leaf_node Leaf node where the insertion should begin.
110
 */
110
 */
111
void btree_insert(btree_t *t, __native key, void *value, btree_node_t *leaf_node)
111
void btree_insert(btree_t *t, btree_key_t key, void *value, btree_node_t *leaf_node)
112
{
112
{
113
    btree_node_t *lnode;
113
    btree_node_t *lnode;
114
   
114
   
115
    ASSERT(value);
115
    ASSERT(value);
116
   
116
   
Line 130... Line 130...
130
 * @param key Key to be inserted.
130
 * @param key Key to be inserted.
131
 * @param value Value to be inserted.
131
 * @param value Value to be inserted.
132
 * @param rsubtree Right subtree of the inserted key.
132
 * @param rsubtree Right subtree of the inserted key.
133
 * @param node Start inserting into this node.
133
 * @param node Start inserting into this node.
134
 */
134
 */
135
void _btree_insert(btree_t *t, __native key, void *value, btree_node_t *rsubtree, btree_node_t *node)
135
void _btree_insert(btree_t *t, btree_key_t key, void *value, btree_node_t *rsubtree, btree_node_t *node)
136
{
136
{
137
    if (node->keys < BTREE_MAX_KEYS) {
137
    if (node->keys < BTREE_MAX_KEYS) {
138
        /*
138
        /*
139
         * Node conatins enough space, the key can be stored immediately.
139
         * Node conatins enough space, the key can be stored immediately.
140
         */
140
         */
Line 149... Line 149...
149
         * The key-value-rsubtree triplet has been inserted because
149
         * The key-value-rsubtree triplet has been inserted because
150
         * some keys could have been moved to the right sibling.
150
         * some keys could have been moved to the right sibling.
151
         */
151
         */
152
    } else {
152
    } else {
153
        btree_node_t *rnode;
153
        btree_node_t *rnode;
154
        __native median;
154
        btree_key_t median;
155
       
155
       
156
        /*
156
        /*
157
         * Node is full and both siblings (if both exist) are full too.
157
         * Node is full and both siblings (if both exist) are full too.
158
         * Split the node and insert the smallest key from the node containing
158
         * Split the node and insert the smallest key from the node containing
159
         * bigger keys (i.e. the new node) into its parent.
159
         * bigger keys (i.e. the new node) into its parent.
Line 191... Line 191...
191
 *
191
 *
192
 * @param B-tree.
192
 * @param B-tree.
193
 * @param key Key to be removed from the B-tree along with its associated value.
193
 * @param key Key to be removed from the B-tree along with its associated value.
194
 * @param leaf_node If not NULL, pointer to the leaf node where the key is found.
194
 * @param leaf_node If not NULL, pointer to the leaf node where the key is found.
195
 */
195
 */
196
void btree_remove(btree_t *t, __native key, btree_node_t *leaf_node)
196
void btree_remove(btree_t *t, btree_key_t key, btree_node_t *leaf_node)
197
{
197
{
198
    btree_node_t *lnode;
198
    btree_node_t *lnode;
199
   
199
   
200
    lnode = leaf_node;
200
    lnode = leaf_node;
201
    if (!lnode) {
201
    if (!lnode) {
Line 211... Line 211...
211
 *
211
 *
212
 * @param B-tree.
212
 * @param B-tree.
213
 * @param key Key to be removed from the B-tree along with its associated value.
213
 * @param key Key to be removed from the B-tree along with its associated value.
214
 * @param node Node where the key being removed resides.
214
 * @param node Node where the key being removed resides.
215
 */
215
 */
216
void _btree_remove(btree_t *t, __native key, btree_node_t *node)
216
void _btree_remove(btree_t *t, btree_key_t key, btree_node_t *node)
217
{
217
{
218
    if (ROOT_NODE(node)) {
218
    if (ROOT_NODE(node)) {
219
        if (node->keys == 1 && node->subtree[0]) {
219
        if (node->keys == 1 && node->subtree[0]) {
220
            /*
220
            /*
221
             * Free the current root and set new root.
221
             * Free the current root and set new root.
Line 288... Line 288...
288
 * @param key Key to be searched.
288
 * @param key Key to be searched.
289
 * @param leaf_node Address where to put pointer to visited leaf node.
289
 * @param leaf_node Address where to put pointer to visited leaf node.
290
 *
290
 *
291
 * @return Pointer to value or NULL if there is no such key.
291
 * @return Pointer to value or NULL if there is no such key.
292
 */
292
 */
293
void *btree_search(btree_t *t, __native key, btree_node_t **leaf_node)
293
void *btree_search(btree_t *t, btree_key_t key, btree_node_t **leaf_node)
294
{
294
{
295
    btree_node_t *cur, *next;
295
    btree_node_t *cur, *next;
296
   
296
   
297
    /*
297
    /*
298
     * Iteratively descend to the leaf that can contain the searched key.
298
     * Iteratively descend to the leaf that can contain the searched key.
Line 414... Line 414...
414
 * @param node B-tree node into wich the new key is to be inserted.
414
 * @param node B-tree node into wich the new key is to be inserted.
415
 * @param key The key to be inserted.
415
 * @param key The key to be inserted.
416
 * @param value Pointer to value to be inserted.
416
 * @param value Pointer to value to be inserted.
417
 * @param lsubtree Pointer to the left subtree.
417
 * @param lsubtree Pointer to the left subtree.
418
 */
418
 */
419
void node_insert_key_and_lsubtree(btree_node_t *node, __native key, void *value, btree_node_t *lsubtree)
419
void node_insert_key_and_lsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *lsubtree)
420
{
420
{
421
    int i;
421
    int i;
422
 
422
 
423
    for (i = 0; i < node->keys; i++) {
423
    for (i = 0; i < node->keys; i++) {
424
        if (key < node->key[i]) {
424
        if (key < node->key[i]) {
Line 450... Line 450...
450
 * @param node B-tree node into wich the new key is to be inserted.
450
 * @param node B-tree node into wich the new key is to be inserted.
451
 * @param key The key to be inserted.
451
 * @param key The key to be inserted.
452
 * @param value Pointer to value to be inserted.
452
 * @param value Pointer to value to be inserted.
453
 * @param rsubtree Pointer to the right subtree.
453
 * @param rsubtree Pointer to the right subtree.
454
 */
454
 */
455
void node_insert_key_and_rsubtree(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree)
455
void node_insert_key_and_rsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree)
456
{
456
{
457
    int i;
457
    int i;
458
 
458
 
459
    for (i = 0; i < node->keys; i++) {
459
    for (i = 0; i < node->keys; i++) {
460
        if (key < node->key[i]) {
460
        if (key < node->key[i]) {
Line 482... Line 482...
482
 * is removed from the node as well.
482
 * is removed from the node as well.
483
 *
483
 *
484
 * @param node B-tree node.
484
 * @param node B-tree node.
485
 * @param key Key to be removed.
485
 * @param key Key to be removed.
486
 */
486
 */
487
void node_remove_key_and_lsubtree(btree_node_t *node, __native key)
487
void node_remove_key_and_lsubtree(btree_node_t *node, btree_key_t key)
488
{
488
{
489
    int i, j;
489
    int i, j;
490
   
490
   
491
    for (i = 0; i < node->keys; i++) {
491
    for (i = 0; i < node->keys; i++) {
492
        if (key == node->key[i]) {
492
        if (key == node->key[i]) {
Line 510... Line 510...
510
 * is removed from the node as well.
510
 * is removed from the node as well.
511
 *
511
 *
512
 * @param node B-tree node.
512
 * @param node B-tree node.
513
 * @param key Key to be removed.
513
 * @param key Key to be removed.
514
 */
514
 */
515
void node_remove_key_and_rsubtree(btree_node_t *node, __native key)
515
void node_remove_key_and_rsubtree(btree_node_t *node, btree_key_t key)
516
{
516
{
517
    int i, j;
517
    int i, j;
518
   
518
   
519
    for (i = 0; i < node->keys; i++) {
519
    for (i = 0; i < node->keys; i++) {
520
        if (key == node->key[i]) {
520
        if (key == node->key[i]) {
Line 547... Line 547...
547
 * @param rsubtree Pointer to the right subtree of the key being added.
547
 * @param rsubtree Pointer to the right subtree of the key being added.
548
 * @param median Address in memory, where the median key will be stored.
548
 * @param median Address in memory, where the median key will be stored.
549
 *
549
 *
550
 * @return Newly created right sibling of node.
550
 * @return Newly created right sibling of node.
551
 */
551
 */
552
btree_node_t *node_split(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree, __native *median)
552
btree_node_t *node_split(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree, btree_key_t *median)
553
{
553
{
554
    btree_node_t *rnode;
554
    btree_node_t *rnode;
555
    int i, j;
555
    int i, j;
556
 
556
 
557
    ASSERT(median);
557
    ASSERT(median);
Line 682... Line 682...
682
 * @param rnode Right sibling.
682
 * @param rnode Right sibling.
683
 * @param idx Index of the parent node key that is taking part in the rotation.
683
 * @param idx Index of the parent node key that is taking part in the rotation.
684
 */
684
 */
685
void rotate_from_left(btree_node_t *lnode, btree_node_t *rnode, index_t idx)
685
void rotate_from_left(btree_node_t *lnode, btree_node_t *rnode, index_t idx)
686
{
686
{
687
    __native key;
687
    btree_key_t key;
688
 
688
 
689
    key = lnode->key[lnode->keys - 1];
689
    key = lnode->key[lnode->keys - 1];
690
       
690
       
691
    if (LEAF_NODE(lnode)) {
691
    if (LEAF_NODE(lnode)) {
692
        void *value;
692
        void *value;
Line 719... Line 719...
719
 * @param rnode Right sibling.
719
 * @param rnode Right sibling.
720
 * @param idx Index of the parent node key that is taking part in the rotation.
720
 * @param idx Index of the parent node key that is taking part in the rotation.
721
 */
721
 */
722
void rotate_from_right(btree_node_t *lnode, btree_node_t *rnode, index_t idx)
722
void rotate_from_right(btree_node_t *lnode, btree_node_t *rnode, index_t idx)
723
{
723
{
724
    __native key;
724
    btree_key_t key;
725
 
725
 
726
    key = rnode->key[0];
726
    key = rnode->key[0];
727
       
727
       
728
    if (LEAF_NODE(rnode)) {
728
    if (LEAF_NODE(rnode)) {
729
        void *value;
729
        void *value;
Line 758... Line 758...
758
 * @param insvalue Value to be inserted.
758
 * @param insvalue Value to be inserted.
759
 * @param rsubtree Right subtree of inskey.
759
 * @param rsubtree Right subtree of inskey.
760
 *
760
 *
761
 * @return True if the rotation was performed, false otherwise.
761
 * @return True if the rotation was performed, false otherwise.
762
 */
762
 */
763
bool try_insert_by_rotation_to_left(btree_node_t *node, __native inskey, void *insvalue, btree_node_t *rsubtree)
763
bool try_insert_by_rotation_to_left(btree_node_t *node, btree_key_t inskey, void *insvalue, btree_node_t *rsubtree)
764
{
764
{
765
    index_t idx;
765
    index_t idx;
766
    btree_node_t *lnode;
766
    btree_node_t *lnode;
767
 
767
 
768
    /*
768
    /*
Line 805... Line 805...
805
 * @param insvalue Value to be inserted.
805
 * @param insvalue Value to be inserted.
806
 * @param rsubtree Right subtree of inskey.
806
 * @param rsubtree Right subtree of inskey.
807
 *
807
 *
808
 * @return True if the rotation was performed, false otherwise.
808
 * @return True if the rotation was performed, false otherwise.
809
 */
809
 */
810
bool try_insert_by_rotation_to_right(btree_node_t *node, __native inskey, void *insvalue, btree_node_t *rsubtree)
810
bool try_insert_by_rotation_to_right(btree_node_t *node, btree_key_t inskey, void *insvalue, btree_node_t *rsubtree)
811
{
811
{
812
    index_t idx;
812
    index_t idx;
813
    btree_node_t *rnode;
813
    btree_node_t *rnode;
814
 
814
 
815
    /*
815
    /*