Subversion Repositories HelenOS

Rev

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

Rev 2089 Rev 2111
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
    int i;
140
    count_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
        int i;
272
        count_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 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
            int i;
338
            count_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
    int i;
445
    count_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
            int j;
449
            count_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
    int i;
481
    count_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
            int j;
485
            count_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
    int i, j;
513
    count_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
    int i, j;
541
    count_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
    int i, j;
579
    count_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 = (int) INDEX_NODE(node);
606
    i = (count_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 636... Line 636...
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
    index_t idx;
640
    btree_node_t *rnode;
640
    btree_node_t *rnode;
641
    int i;
641
    count_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 685... Line 685...
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
index_t find_key_by_subtree(btree_node_t *node, btree_node_t *subtree, bool right)
689
{
689
{
690
    int i;
690
    count_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 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
    int i, depth = t->root->depth;
944
    int depth = t->root->depth;
944
    link_t head, *cur;
945
    link_t head, *cur;
945
 
946
 
946
    printf("Printing B-tree:\n");
947
    printf("Printing B-tree:\n");
947
    list_initialize(&head);
948
    list_initialize(&head);
948
    list_append(&t->root->bfs_link, &head);
949
    list_append(&t->root->bfs_link, &head);