Subversion Repositories HelenOS

Rev

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

Rev 2787 Rev 3424
Line 122... Line 122...
122
    ASSERT(value);
122
    ASSERT(value);
123
   
123
   
124
    lnode = leaf_node;
124
    lnode = leaf_node;
125
    if (!lnode) {
125
    if (!lnode) {
126
        if (btree_search(t, key, &lnode)) {
126
        if (btree_search(t, key, &lnode)) {
127
            panic("B-tree %p already contains key %d\n", t, key);
127
            panic("B-tree %p already contains key %" PRIu64 "\n", t, key);
128
        }
128
        }
129
    }
129
    }
130
   
130
   
131
    _btree_insert(t, key, value, NULL, lnode);
131
    _btree_insert(t, key, value, NULL, lnode);
132
}
132
}
Line 222... Line 222...
222
    btree_node_t *lnode;
222
    btree_node_t *lnode;
223
   
223
   
224
    lnode = leaf_node;
224
    lnode = leaf_node;
225
    if (!lnode) {
225
    if (!lnode) {
226
        if (!btree_search(t, key, &lnode)) {
226
        if (!btree_search(t, key, &lnode)) {
227
            panic("B-tree %p does not contain key %d\n", t, key);
227
            panic("B-tree %p does not contain key %" PRIu64 "\n", t, key);
228
        }
228
        }
229
    }
229
    }
230
   
230
   
231
    _btree_remove(t, key, lnode);
231
    _btree_remove(t, key, lnode);
232
}
232
}
Line 522... Line 522...
522
            node->subtree[j - 1] = node->subtree[j];
522
            node->subtree[j - 1] = node->subtree[j];
523
            node->keys--;
523
            node->keys--;
524
            return;
524
            return;
525
        }
525
        }
526
    }
526
    }
527
    panic("node %p does not contain key %d\n", node, key);
527
    panic("node %p does not contain key %" PRIu64 "\n", node, key);
528
}
528
}
529
 
529
 
530
/** Remove key and its right subtree pointer from B-tree node.
530
/** Remove key and its right subtree pointer from B-tree node.
531
 *
531
 *
532
 * Remove the key and eliminate gaps in node->key array.
532
 * Remove the key and eliminate gaps in node->key array.
Line 549... Line 549...
549
            }
549
            }
550
            node->keys--;
550
            node->keys--;
551
            return;
551
            return;
552
        }
552
        }
553
    }
553
    }
554
    panic("node %p does not contain key %d\n", node, key);
554
    panic("node %p does not contain key %" PRIu64 "\n", node, key);
555
}
555
}
556
 
556
 
557
/** Split full B-tree node and insert new key-value-right-subtree triplet.
557
/** Split full B-tree node and insert new key-value-right-subtree triplet.
558
 *
558
 *
559
 * This function will split a node and return a pointer to a newly created
559
 * This function will split a node and return a pointer to a newly created
Line 968... Line 968...
968
            depth = node->depth;
968
            depth = node->depth;
969
        }
969
        }
970
 
970
 
971
        printf("(");
971
        printf("(");
972
        for (i = 0; i < node->keys; i++) {
972
        for (i = 0; i < node->keys; i++) {
973
            printf("%llu%s", node->key[i], i < node->keys - 1 ? "," : "");
973
            printf("%" PRIu64 "%s", node->key[i], i < node->keys - 1 ? "," : "");
974
            if (node->depth && node->subtree[i]) {
974
            if (node->depth && node->subtree[i]) {
975
                list_append(&node->subtree[i]->bfs_link, &head);
975
                list_append(&node->subtree[i]->bfs_link, &head);
976
            }
976
            }
977
        }
977
        }
978
        if (node->depth && node->subtree[i]) {
978
        if (node->depth && node->subtree[i]) {
Line 990... Line 990...
990
       
990
       
991
        ASSERT(node);
991
        ASSERT(node);
992
 
992
 
993
        printf("(");
993
        printf("(");
994
        for (i = 0; i < node->keys; i++)
994
        for (i = 0; i < node->keys; i++)
995
            printf("%llu%s", node->key[i], i < node->keys - 1 ? "," : "");
995
            printf("%" PRIu64 "%s", node->key[i], i < node->keys - 1 ? "," : "");
996
        printf(")");
996
        printf(")");
997
    }
997
    }
998
    printf("\n");
998
    printf("\n");
999
}
999
}
1000
 
1000