Subversion Repositories HelenOS

Rev

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

Rev 1142 Rev 1144
Line 47... Line 47...
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, __native 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, __native 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 *rsubtree);
52
static void node_insert_key_and_lsubtree(btree_node_t *node, __native 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, __native key, void *value, btree_node_t *rsubtree);
54
static btree_node_t *node_split(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree, __native *median);
-
 
55
static btree_node_t *node_combine(btree_node_t *node);
-
 
56
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, __native key);
57
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, __native key);
-
 
56
static btree_node_t *node_split(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree, __native *median);
-
 
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, __native 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, __native key, void *value, btree_node_t *rsubtree);
Line 152... Line 152...
152
         */
152
         */
153
 
153
 
154
        rnode = node_split(node, key, value, rsubtree, &median);
154
        rnode = node_split(node, key, value, rsubtree, &median);
155
 
155
 
156
        if (LEAF_NODE(node)) {
156
        if (LEAF_NODE(node)) {
157
            list_append(&rnode->leaf_link, &node->leaf_link);
157
            list_prepend(&rnode->leaf_link, &node->leaf_link);
158
        }
158
        }
159
       
159
       
160
        if (ROOT_NODE(node)) {
160
        if (ROOT_NODE(node)) {
161
            /*
161
            /*
162
             * We split the root node. Create new root.
162
             * We split the root node. Create new root.
Line 187... Line 187...
187
 */
187
 */
188
void btree_remove(btree_t *t, __native key, btree_node_t *leaf_node)
188
void btree_remove(btree_t *t, __native key, btree_node_t *leaf_node)
189
{
189
{
190
    btree_node_t *lnode;
190
    btree_node_t *lnode;
191
   
191
   
192
    panic("%s needs testing and is disabled in revision %s\n", __FUNCTION__, REVISION);
-
 
193
    lnode = leaf_node;
192
    lnode = leaf_node;
194
    if (!lnode) {
193
    if (!lnode) {
195
        if (!btree_search(t, key, &lnode)) {
194
        if (!btree_search(t, key, &lnode)) {
196
            panic("B-tree %P does not contain key %d\n", t, key);
195
            panic("B-tree %P does not contain key %d\n", t, key);
197
        }
196
        }
Line 434... Line 433...
434
    node->subtree[i + 1] = rsubtree;
433
    node->subtree[i + 1] = rsubtree;
435
           
434
           
436
    node->keys++;
435
    node->keys++;
437
}
436
}
438
 
437
 
-
 
438
/** Remove key and its left subtree pointer from B-tree node.
-
 
439
 *
-
 
440
 * Remove the key and eliminate gaps in node->key array.
-
 
441
 * Note that the value pointer and the left subtree pointer
-
 
442
 * is removed from the node as well.
-
 
443
 *
-
 
444
 * @param node B-tree node.
-
 
445
 * @param key Key to be removed.
-
 
446
 */
-
 
447
void node_remove_key_and_lsubtree(btree_node_t *node, __native key)
-
 
448
{
-
 
449
    int i, j;
-
 
450
   
-
 
451
    for (i = 0; i < node->keys; i++) {
-
 
452
        if (key == node->key[i]) {
-
 
453
            for (j = i + 1; j < node->keys; j++) {
-
 
454
                node->key[j - 1] = node->key[j];
-
 
455
                node->value[j - 1] = node->value[j];
-
 
456
                node->subtree[j - 1] = node->subtree[j];
-
 
457
            }
-
 
458
            node->subtree[j - 1] = node->subtree[j];
-
 
459
            node->keys--;
-
 
460
            return;
-
 
461
        }
-
 
462
    }
-
 
463
    panic("node %P does not contain key %d\n", node, key);
-
 
464
}
-
 
465
 
-
 
466
/** Remove key and its right subtree pointer from B-tree node.
-
 
467
 *
-
 
468
 * Remove the key and eliminate gaps in node->key array.
-
 
469
 * Note that the value pointer and the right subtree pointer
-
 
470
 * is removed from the node as well.
-
 
471
 *
-
 
472
 * @param node B-tree node.
-
 
473
 * @param key Key to be removed.
-
 
474
 */
-
 
475
void node_remove_key_and_rsubtree(btree_node_t *node, __native key)
-
 
476
{
-
 
477
    int i, j;
-
 
478
   
-
 
479
    for (i = 0; i < node->keys; i++) {
-
 
480
        if (key == node->key[i]) {
-
 
481
            for (j = i + 1; j < node->keys; j++) {
-
 
482
                node->key[j - 1] = node->key[j];
-
 
483
                node->value[j - 1] = node->value[j];
-
 
484
                node->subtree[j] = node->subtree[j + 1];
-
 
485
            }
-
 
486
            node->keys--;
-
 
487
            return;
-
 
488
        }
-
 
489
    }
-
 
490
    panic("node %P does not contain key %d\n", node, key);
-
 
491
}
-
 
492
 
439
/** Split full B-tree node and insert new key-value-right-subtree triplet.
493
/** Split full B-tree node and insert new key-value-right-subtree triplet.
440
 *
494
 *
441
 * This function will split a node and return pointer to a newly created
495
 * This function will split a node and return pointer to a newly created
442
 * node containing keys greater than or equal to the greater of medians
496
 * node containing keys greater than or equal to the greater of medians
443
 * (or median) of the old keys and the newly added key. It will also write
497
 * (or median) of the old keys and the newly added key. It will also write
Line 557... Line 611...
557
    node->keys += rnode->keys;
611
    node->keys += rnode->keys;
558
 
612
 
559
    return rnode;
613
    return rnode;
560
}
614
}
561
 
615
 
562
/** Remove key and its left subtree pointer from B-tree node.
-
 
563
 *
-
 
564
 * Remove the key and eliminate gaps in node->key array.
-
 
565
 * Note that the value pointer and the left subtree pointer
-
 
566
 * is removed from the node as well.
-
 
567
 *
-
 
568
 * @param node B-tree node.
-
 
569
 * @param key Key to be removed.
-
 
570
 */
-
 
571
void node_remove_key_and_lsubtree(btree_node_t *node, __native key)
-
 
572
{
-
 
573
    int i, j;
-
 
574
   
-
 
575
    for (i = 0; i < node->keys; i++) {
-
 
576
        if (key == node->key[i]) {
-
 
577
            for (j = i + 1; j < node->keys; j++) {
-
 
578
                node->key[j - 1] = node->key[j];
-
 
579
                node->value[j - 1] = node->value[j];
-
 
580
                node->subtree[j - 1] = node->subtree[j];
-
 
581
            }
-
 
582
            node->subtree[j - 1] = node->subtree[j];
-
 
583
            node->keys--;
-
 
584
            return;
-
 
585
        }
-
 
586
    }
-
 
587
    panic("node %P does not contain key %d\n", node, key);
-
 
588
}
-
 
589
 
-
 
590
/** Remove key and its right subtree pointer from B-tree node.
-
 
591
 *
-
 
592
 * Remove the key and eliminate gaps in node->key array.
-
 
593
 * Note that the value pointer and the right subtree pointer
-
 
594
 * is removed from the node as well.
-
 
595
 *
-
 
596
 * @param node B-tree node.
-
 
597
 * @param key Key to be removed.
-
 
598
 */
-
 
599
void node_remove_key_and_rsubtree(btree_node_t *node, __native key)
-
 
600
{
-
 
601
    int i, j;
-
 
602
   
-
 
603
    for (i = 0; i < node->keys; i++) {
-
 
604
        if (key == node->key[i]) {
-
 
605
            for (j = i + 1; j < node->keys; j++) {
-
 
606
                node->key[j - 1] = node->key[j];
-
 
607
                node->value[j - 1] = node->value[j];
-
 
608
                node->subtree[j] = node->subtree[j + 1];
-
 
609
            }
-
 
610
            node->keys--;
-
 
611
            return;
-
 
612
        }
-
 
613
    }
-
 
614
    panic("node %P does not contain key %d\n", node, key);
-
 
615
}
-
 
616
 
-
 
617
/** Find key by its left or right subtree.
616
/** Find key by its left or right subtree.
618
 *
617
 *
619
 * @param node B-tree node.
618
 * @param node B-tree node.
620
 * @param subtree Left or right subtree of a key found in node.
619
 * @param subtree Left or right subtree of a key found in node.
621
 * @param right If true, subtree is a right subtree. If false, subtree is a left subtree.
620
 * @param right If true, subtree is a right subtree. If false, subtree is a left subtree.
Line 876... Line 875...
876
 * @param t Print out B-tree.
875
 * @param t Print out B-tree.
877
 */
876
 */
878
void btree_print(btree_t *t)
877
void btree_print(btree_t *t)
879
{
878
{
880
    int i, depth = t->root->depth;
879
    int i, depth = t->root->depth;
881
    link_t head;
880
    link_t head, *cur;
882
   
881
 
-
 
882
    printf("Printing B-tree:\n");
883
    list_initialize(&head);
883
    list_initialize(&head);
884
    list_append(&t->root->bfs_link, &head);
884
    list_append(&t->root->bfs_link, &head);
885
 
885
 
886
    /*
886
    /*
887
     * Use BFS search to print out the tree.
887
     * Use BFS search to print out the tree.
Line 903... Line 903...
903
            depth = node->depth;
903
            depth = node->depth;
904
        }
904
        }
905
 
905
 
906
        printf("(");
906
        printf("(");
907
        for (i = 0; i < node->keys; i++) {
907
        for (i = 0; i < node->keys; i++) {
908
            printf("%d,", node->key[i]);
908
            printf("%d%s", node->key[i], i < node->keys - 1 ? "," : "");
909
            if (node->depth && node->subtree[i]) {
909
            if (node->depth && node->subtree[i]) {
910
                list_append(&node->subtree[i]->bfs_link, &head);
910
                list_append(&node->subtree[i]->bfs_link, &head);
911
            }
911
            }
912
        }
912
        }
913
        if (node->depth && node->subtree[i]) {
913
        if (node->depth && node->subtree[i]) {
914
            list_append(&node->subtree[i]->bfs_link, &head);
914
            list_append(&node->subtree[i]->bfs_link, &head);
915
        }
915
        }
916
        printf(")");
916
        printf(")");
917
    }
917
    }
918
    printf("\n");
918
    printf("\n");
-
 
919
   
-
 
920
    printf("Printing list of leaves:\n");
-
 
921
    for (cur = t->leaf_head.next; cur != &t->leaf_head; cur = cur->next) {
-
 
922
        btree_node_t *node;
-
 
923
       
-
 
924
        node = list_get_instance(cur, btree_node_t, leaf_link);
-
 
925
       
-
 
926
        ASSERT(node);
-
 
927
 
-
 
928
        printf("(");
-
 
929
        for (i = 0; i < node->keys; i++)
-
 
930
            printf("%d%s", node->key[i], i < node->keys - 1 ? "," : "");
-
 
931
        printf(")");
-
 
932
    }
-
 
933
    printf("\n");
919
}
934
}