Subversion Repositories HelenOS

Rev

Rev 4153 | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 4153 Rev 4581
Line 61... Line 61...
61
static void node_insert_key_and_rsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree);
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);
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);
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);
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);
65
static btree_node_t *node_combine(btree_node_t *node);
66
static index_t find_key_by_subtree(btree_node_t *node, btree_node_t *subtree, bool right);
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, index_t idx);
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, index_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);
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);
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);
71
static bool try_rotation_from_left(btree_node_t *rnode);
72
static bool try_rotation_from_right(btree_node_t *lnode);
72
static bool try_rotation_from_right(btree_node_t *lnode);
73
 
73
 
Line 135... Line 135...
135
 *
135
 *
136
 * @param root Root of the subtree.
136
 * @param root Root of the subtree.
137
 */
137
 */
138
void btree_destroy_subtree(btree_node_t *root)
138
void btree_destroy_subtree(btree_node_t *root)
139
{
139
{
140
    count_t i;
140
    size_t i;
141
 
141
 
142
    if (root->keys) {
142
    if (root->keys) {
143
        for (i = 0; i < root->keys + 1; i++) {
143
        for (i = 0; i < root->keys + 1; i++) {
144
            if (root->subtree[i])
144
            if (root->subtree[i])
145
                btree_destroy_subtree(root->subtree[i]);
145
                btree_destroy_subtree(root->subtree[i]);
Line 267... Line 267...
267
        if (!try_rotation_from_left(node))
267
        if (!try_rotation_from_left(node))
268
            try_rotation_from_right(node);
268
            try_rotation_from_right(node);
269
    }
269
    }
270
   
270
   
271
    if (node->keys > FILL_FACTOR) {
271
    if (node->keys > FILL_FACTOR) {
272
        count_t i;
272
        size_t i;
273
 
273
 
274
        /*
274
        /*
275
         * The key can be immediatelly removed.
275
         * The key can be immediatelly removed.
276
         *
276
         *
277
         * Note that the right subtree is removed because when
277
         * Note that the right subtree is removed because when
Line 283... Line 283...
283
            if (node->parent->key[i] == key)
283
            if (node->parent->key[i] == key)
284
                node->parent->key[i] = node->key[0];
284
                node->parent->key[i] = node->key[0];
285
        }
285
        }
286
       
286
       
287
    } else {
287
    } else {
288
        index_t idx;
288
        size_t idx;
289
        btree_node_t *rnode, *parent;
289
        btree_node_t *rnode, *parent;
290
 
290
 
291
        /*
291
        /*
292
         * The node is below the fill factor as well as its left and right sibling.
292
         * The node is below the fill factor as well as its left and right sibling.
293
         * Resort to combining the node with one of its siblings.
293
         * Resort to combining the node with one of its siblings.
Line 333... Line 333...
333
        if (key < cur->key[0]) {
333
        if (key < cur->key[0]) {
334
            next = cur->subtree[0];
334
            next = cur->subtree[0];
335
            continue;
335
            continue;
336
        } else {
336
        } else {
337
            void *val;
337
            void *val;
338
            count_t i;
338
            size_t i;
339
       
339
       
340
            /*
340
            /*
341
             * Now if the key is smaller than cur->key[i]
341
             * Now if the key is smaller than cur->key[i]
342
             * it can only mean that the value is in cur->subtree[i]
342
             * it can only mean that the value is in cur->subtree[i]
343
             * or it is not in the tree at all.
343
             * or it is not in the tree at all.
Line 440... Line 440...
440
 * @param value Pointer to value to be inserted.
440
 * @param value Pointer to value to be inserted.
441
 * @param lsubtree Pointer to the left subtree.
441
 * @param lsubtree Pointer to the left subtree.
442
 */
442
 */
443
void node_insert_key_and_lsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *lsubtree)
443
void node_insert_key_and_lsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *lsubtree)
444
{
444
{
445
    count_t i;
445
    size_t i;
446
 
446
 
447
    for (i = 0; i < node->keys; i++) {
447
    for (i = 0; i < node->keys; i++) {
448
        if (key < node->key[i]) {
448
        if (key < node->key[i]) {
449
            count_t j;
449
            size_t j;
450
       
450
       
451
            for (j = node->keys; j > i; j--) {
451
            for (j = node->keys; j > i; j--) {
452
                node->key[j] = node->key[j - 1];
452
                node->key[j] = node->key[j - 1];
453
                node->value[j] = node->value[j - 1];
453
                node->value[j] = node->value[j - 1];
454
                node->subtree[j + 1] = node->subtree[j];
454
                node->subtree[j + 1] = node->subtree[j];
Line 476... Line 476...
476
 * @param value Pointer to value to be inserted.
476
 * @param value Pointer to value to be inserted.
477
 * @param rsubtree Pointer to the right subtree.
477
 * @param rsubtree Pointer to the right subtree.
478
 */
478
 */
479
void node_insert_key_and_rsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree)
479
void node_insert_key_and_rsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree)
480
{
480
{
481
    count_t i;
481
    size_t i;
482
 
482
 
483
    for (i = 0; i < node->keys; i++) {
483
    for (i = 0; i < node->keys; i++) {
484
        if (key < node->key[i]) {
484
        if (key < node->key[i]) {
485
            count_t j;
485
            size_t j;
486
       
486
       
487
            for (j = node->keys; j > i; j--) {
487
            for (j = node->keys; j > i; j--) {
488
                node->key[j] = node->key[j - 1];
488
                node->key[j] = node->key[j - 1];
489
                node->value[j] = node->value[j - 1];
489
                node->value[j] = node->value[j - 1];
490
                node->subtree[j + 1] = node->subtree[j];
490
                node->subtree[j + 1] = node->subtree[j];
Line 508... Line 508...
508
 * @param node B-tree node.
508
 * @param node B-tree node.
509
 * @param key Key to be removed.
509
 * @param key Key to be removed.
510
 */
510
 */
511
void node_remove_key_and_lsubtree(btree_node_t *node, btree_key_t key)
511
void node_remove_key_and_lsubtree(btree_node_t *node, btree_key_t key)
512
{
512
{
513
    count_t i, j;
513
    size_t i, j;
514
   
514
   
515
    for (i = 0; i < node->keys; i++) {
515
    for (i = 0; i < node->keys; i++) {
516
        if (key == node->key[i]) {
516
        if (key == node->key[i]) {
517
            for (j = i + 1; j < node->keys; j++) {
517
            for (j = i + 1; j < node->keys; j++) {
518
                node->key[j - 1] = node->key[j];
518
                node->key[j - 1] = node->key[j];
Line 536... Line 536...
536
 * @param node B-tree node.
536
 * @param node B-tree node.
537
 * @param key Key to be removed.
537
 * @param key Key to be removed.
538
 */
538
 */
539
void node_remove_key_and_rsubtree(btree_node_t *node, btree_key_t key)
539
void node_remove_key_and_rsubtree(btree_node_t *node, btree_key_t key)
540
{
540
{
541
    count_t i, j;
541
    size_t i, j;
542
   
542
   
543
    for (i = 0; i < node->keys; i++) {
543
    for (i = 0; i < node->keys; i++) {
544
        if (key == node->key[i]) {
544
        if (key == node->key[i]) {
545
            for (j = i + 1; j < node->keys; j++) {
545
            for (j = i + 1; j < node->keys; j++) {
546
                node->key[j - 1] = node->key[j];
546
                node->key[j - 1] = node->key[j];
Line 574... Line 574...
574
 * @return Newly created right sibling of node.
574
 * @return Newly created right sibling of node.
575
 */
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)
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
{
577
{
578
    btree_node_t *rnode;
578
    btree_node_t *rnode;
579
    count_t i, j;
579
    size_t i, j;
580
 
580
 
581
    ASSERT(median);
581
    ASSERT(median);
582
    ASSERT(node->keys == BTREE_MAX_KEYS);
582
    ASSERT(node->keys == BTREE_MAX_KEYS);
583
 
583
 
584
    /*
584
    /*
Line 601... Line 601...
601
   
601
   
602
    /*
602
    /*
603
     * Copy big keys, values and subtree pointers to the new right sibling.
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.
604
     * If this is an index node, do not copy the median.
605
     */
605
     */
606
    i = (count_t) INDEX_NODE(node);
606
    i = (size_t) INDEX_NODE(node);
607
    for (i += MEDIAN_HIGH_INDEX(node), j = 0; i < node->keys; i++, j++) {
607
    for (i += MEDIAN_HIGH_INDEX(node), j = 0; i < node->keys; i++, j++) {
608
        rnode->key[j] = node->key[i];
608
        rnode->key[j] = node->key[i];
609
        rnode->value[j] = node->value[i];
609
        rnode->value[j] = node->value[i];
610
        rnode->subtree[j] = node->subtree[i];
610
        rnode->subtree[j] = node->subtree[i];
611
       
611
       
Line 634... Line 634...
634
 *
634
 *
635
 * @return Pointer to the rightmost of the two nodes.
635
 * @return Pointer to the rightmost of the two nodes.
636
 */
636
 */
637
btree_node_t *node_combine(btree_node_t *node)
637
btree_node_t *node_combine(btree_node_t *node)
638
{
638
{
639
    index_t idx;
639
    size_t idx;
640
    btree_node_t *rnode;
640
    btree_node_t *rnode;
641
    count_t i;
641
    size_t i;
642
 
642
 
643
    ASSERT(!ROOT_NODE(node));
643
    ASSERT(!ROOT_NODE(node));
644
   
644
   
645
    idx = find_key_by_subtree(node->parent, node, false);
645
    idx = find_key_by_subtree(node->parent, node, false);
646
    if (idx == node->parent->keys) {
646
    if (idx == node->parent->keys) {
Line 683... Line 683...
683
 * @param subtree Left or right subtree of a key found in 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.
684
 * @param right If true, subtree is a right subtree. If false, subtree is a left subtree.
685
 *
685
 *
686
 * @return Index of the key associated with the subtree.
686
 * @return Index of the key associated with the subtree.
687
 */
687
 */
688
index_t find_key_by_subtree(btree_node_t *node, btree_node_t *subtree, bool right)
688
size_t find_key_by_subtree(btree_node_t *node, btree_node_t *subtree, bool right)
689
{
689
{
690
    count_t i;
690
    size_t i;
691
   
691
   
692
    for (i = 0; i < node->keys + 1; i++) {
692
    for (i = 0; i < node->keys + 1; i++) {
693
        if (subtree == node->subtree[i])
693
        if (subtree == node->subtree[i])
694
            return i - (int) (right != false);
694
            return i - (int) (right != false);
695
    }
695
    }
Line 704... Line 704...
704
 *
704
 *
705
 * @param lnode Left sibling.
705
 * @param lnode Left sibling.
706
 * @param rnode Right sibling.
706
 * @param rnode Right sibling.
707
 * @param idx Index of the parent node key that is taking part in the rotation.
707
 * @param idx Index of the parent node key that is taking part in the rotation.
708
 */
708
 */
709
void rotate_from_left(btree_node_t *lnode, btree_node_t *rnode, index_t idx)
709
void rotate_from_left(btree_node_t *lnode, btree_node_t *rnode, size_t idx)
710
{
710
{
711
    btree_key_t key;
711
    btree_key_t key;
712
 
712
 
713
    key = lnode->key[lnode->keys - 1];
713
    key = lnode->key[lnode->keys - 1];
714
       
714
       
Line 741... Line 741...
741
 *
741
 *
742
 * @param lnode Left sibling.
742
 * @param lnode Left sibling.
743
 * @param rnode Right sibling.
743
 * @param rnode Right sibling.
744
 * @param idx Index of the parent node key that is taking part in the rotation.
744
 * @param idx Index of the parent node key that is taking part in the rotation.
745
 */
745
 */
746
void rotate_from_right(btree_node_t *lnode, btree_node_t *rnode, index_t idx)
746
void rotate_from_right(btree_node_t *lnode, btree_node_t *rnode, size_t idx)
747
{
747
{
748
    btree_key_t key;
748
    btree_key_t key;
749
 
749
 
750
    key = rnode->key[0];
750
    key = rnode->key[0];
751
       
751
       
Line 784... Line 784...
784
 *
784
 *
785
 * @return True if the rotation was performed, false otherwise.
785
 * @return True if the rotation was performed, false otherwise.
786
 */
786
 */
787
bool try_insert_by_rotation_to_left(btree_node_t *node, btree_key_t inskey, void *insvalue, btree_node_t *rsubtree)
787
bool try_insert_by_rotation_to_left(btree_node_t *node, btree_key_t inskey, void *insvalue, btree_node_t *rsubtree)
788
{
788
{
789
    index_t idx;
789
    size_t idx;
790
    btree_node_t *lnode;
790
    btree_node_t *lnode;
791
 
791
 
792
    /*
792
    /*
793
     * If this is root node, the rotation can not be done.
793
     * If this is root node, the rotation can not be done.
794
     */
794
     */
Line 831... Line 831...
831
 *
831
 *
832
 * @return True if the rotation was performed, false otherwise.
832
 * @return True if the rotation was performed, false otherwise.
833
 */
833
 */
834
bool try_insert_by_rotation_to_right(btree_node_t *node, btree_key_t inskey, void *insvalue, btree_node_t *rsubtree)
834
bool try_insert_by_rotation_to_right(btree_node_t *node, btree_key_t inskey, void *insvalue, btree_node_t *rsubtree)
835
{
835
{
836
    index_t idx;
836
    size_t idx;
837
    btree_node_t *rnode;
837
    btree_node_t *rnode;
838
 
838
 
839
    /*
839
    /*
840
     * If this is root node, the rotation can not be done.
840
     * If this is root node, the rotation can not be done.
841
     */
841
     */
Line 870... Line 870...
870
 *
870
 *
871
 * @return True if the rotation was performed, false otherwise.
871
 * @return True if the rotation was performed, false otherwise.
872
 */
872
 */
873
bool try_rotation_from_left(btree_node_t *rnode)
873
bool try_rotation_from_left(btree_node_t *rnode)
874
{
874
{
875
    index_t idx;
875
    size_t idx;
876
    btree_node_t *lnode;
876
    btree_node_t *lnode;
877
 
877
 
878
    /*
878
    /*
879
     * If this is root node, the rotation can not be done.
879
     * If this is root node, the rotation can not be done.
880
     */
880
     */
Line 905... Line 905...
905
 *
905
 *
906
 * @return True if the rotation was performed, false otherwise.
906
 * @return True if the rotation was performed, false otherwise.
907
 */
907
 */
908
bool try_rotation_from_right(btree_node_t *lnode)
908
bool try_rotation_from_right(btree_node_t *lnode)
909
{
909
{
910
    index_t idx;
910
    size_t idx;
911
    btree_node_t *rnode;
911
    btree_node_t *rnode;
912
 
912
 
913
    /*
913
    /*
914
     * If this is root node, the rotation can not be done.
914
     * If this is root node, the rotation can not be done.
915
     */
915
     */
Line 938... Line 938...
938
 *
938
 *
939
 * @param t Print out B-tree.
939
 * @param t Print out B-tree.
940
 */
940
 */
941
void btree_print(btree_t *t)
941
void btree_print(btree_t *t)
942
{
942
{
943
    count_t i;
943
    size_t i;
944
    int depth = t->root->depth;
944
    int depth = t->root->depth;
945
    link_t head, *cur;
945
    link_t head, *cur;
946
 
946
 
947
    printf("Printing B-tree:\n");
947
    printf("Printing B-tree:\n");
948
    list_initialize(&head);
948
    list_initialize(&head);