Subversion Repositories HelenOS

Rev

Rev 4490 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
1101 jermar 1
/*
2071 jermar 2
 * Copyright (c) 2006 Jakub Jermar
1101 jermar 3
 * All rights reserved.
4
 *
5
 * Redistribution and use in source and binary forms, with or without
6
 * modification, are permitted provided that the following conditions
7
 * are met:
8
 *
9
 * - Redistributions of source code must retain the above copyright
10
 *   notice, this list of conditions and the following disclaimer.
11
 * - Redistributions in binary form must reproduce the above copyright
12
 *   notice, this list of conditions and the following disclaimer in the
13
 *   documentation and/or other materials provided with the distribution.
14
 * - The name of the author may not be used to endorse or promote products
15
 *   derived from this software without specific prior written permission.
16
 *
17
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27
 */
28
 
1757 jermar 29
/** @addtogroup genericadt
1702 cejka 30
 * @{
31
 */
32
 
1248 jermar 33
/**
1704 cejka 34
 * @file
1248 jermar 35
 * @brief   B+tree implementation.
1101 jermar 36
 *
1248 jermar 37
 * This file implements B+tree type and operations.
38
 *
39
 * The B+tree has the following properties:
40
 * @li it is a ballanced 3-4-5 tree (i.e. BTREE_M = 5)
41
 * @li values (i.e. pointers to values) are stored only in leaves
42
 * @li leaves are linked in a list
43
 *
1134 jermar 44
 * Be carefull when using these trees. They need to allocate
45
 * and deallocate memory for their index nodes and as such
46
 * can sleep.
1101 jermar 47
 */
48
 
49
#include <adt/btree.h>
50
#include <adt/list.h>
51
#include <mm/slab.h>
52
#include <debug.h>
53
#include <panic.h>
54
#include <print.h>
55
 
1483 jermar 56
static void btree_destroy_subtree(btree_node_t *root);
1177 jermar 57
static void _btree_insert(btree_t *t, btree_key_t key, void *value, btree_node_t *rsubtree, btree_node_t *node);
58
static void _btree_remove(btree_t *t, btree_key_t key, btree_node_t *node);
1101 jermar 59
static void node_initialize(btree_node_t *node);
1177 jermar 60
static void node_insert_key_and_lsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *lsubtree);
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);
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);
1142 jermar 65
static btree_node_t *node_combine(btree_node_t *node);
4490 decky 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, size_t idx);
68
static void rotate_from_left(btree_node_t *lnode, btree_node_t *rnode, size_t idx);
1177 jermar 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);
1142 jermar 71
static bool try_rotation_from_left(btree_node_t *rnode);
72
static bool try_rotation_from_right(btree_node_t *lnode);
1101 jermar 73
 
74
#define ROOT_NODE(n)        (!(n)->parent)
75
#define INDEX_NODE(n)       ((n)->subtree[0] != NULL)
76
#define LEAF_NODE(n)        ((n)->subtree[0] == NULL)
77
 
1140 jermar 78
#define FILL_FACTOR     ((BTREE_M-1)/2)
79
 
1101 jermar 80
#define MEDIAN_LOW_INDEX(n) (((n)->keys-1)/2)
81
#define MEDIAN_HIGH_INDEX(n)    ((n)->keys/2)
82
#define MEDIAN_LOW(n)       ((n)->key[MEDIAN_LOW_INDEX((n))]);
83
#define MEDIAN_HIGH(n)      ((n)->key[MEDIAN_HIGH_INDEX((n))]);
84
 
1164 jermar 85
static slab_cache_t *btree_node_slab;
86
 
87
/** Initialize B-trees. */
88
void btree_init(void)
89
{
90
    btree_node_slab = slab_cache_create("btree_node_slab", sizeof(btree_node_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED);
91
}
92
 
1101 jermar 93
/** Create empty B-tree.
94
 *
95
 * @param t B-tree.
96
 */
97
void btree_create(btree_t *t)
98
{
99
    list_initialize(&t->leaf_head);
1164 jermar 100
    t->root = (btree_node_t *) slab_alloc(btree_node_slab, 0);
1101 jermar 101
    node_initialize(t->root);
102
    list_append(&t->root->leaf_link, &t->leaf_head);
103
}
104
 
105
/** Destroy empty B-tree. */
106
void btree_destroy(btree_t *t)
107
{
1483 jermar 108
    btree_destroy_subtree(t->root);
1101 jermar 109
}
110
 
111
/** Insert key-value pair into B-tree.
112
 *
113
 * @param t B-tree.
114
 * @param key Key to be inserted.
115
 * @param value Value to be inserted.
116
 * @param leaf_node Leaf node where the insertion should begin.
117
 */
1177 jermar 118
void btree_insert(btree_t *t, btree_key_t key, void *value, btree_node_t *leaf_node)
1101 jermar 119
{
120
    btree_node_t *lnode;
121
 
122
    ASSERT(value);
123
 
124
    lnode = leaf_node;
125
    if (!lnode) {
126
        if (btree_search(t, key, &lnode)) {
3790 svoboda 127
            panic("B-tree %p already contains key %" PRIu64 ".", t, key);
1101 jermar 128
        }
129
    }
130
 
131
    _btree_insert(t, key, value, NULL, lnode);
132
}
133
 
1483 jermar 134
/** Destroy subtree rooted in a node.
135
 *
136
 * @param root Root of the subtree.
137
 */
138
void btree_destroy_subtree(btree_node_t *root)
139
{
4490 decky 140
    size_t i;
1483 jermar 141
 
142
    if (root->keys) {
143
        for (i = 0; i < root->keys + 1; i++) {
144
            if (root->subtree[i])
145
                btree_destroy_subtree(root->subtree[i]);
146
        }
147
    }
148
    slab_free(btree_node_slab, root);
149
}
150
 
1101 jermar 151
/** Recursively insert into B-tree.
152
 *
153
 * @param t B-tree.
154
 * @param key Key to be inserted.
155
 * @param value Value to be inserted.
156
 * @param rsubtree Right subtree of the inserted key.
157
 * @param node Start inserting into this node.
158
 */
1177 jermar 159
void _btree_insert(btree_t *t, btree_key_t key, void *value, btree_node_t *rsubtree, btree_node_t *node)
1101 jermar 160
{
161
    if (node->keys < BTREE_MAX_KEYS) {
162
        /*
163
         * Node conatins enough space, the key can be stored immediately.
164
         */
1142 jermar 165
        node_insert_key_and_rsubtree(node, key, value, rsubtree);
166
    } else if (try_insert_by_rotation_to_left(node, key, value, rsubtree)) {
1136 jermar 167
        /*
168
         * The key-value-rsubtree triplet has been inserted because
169
         * some keys could have been moved to the left sibling.
170
         */
1142 jermar 171
    } else if (try_insert_by_rotation_to_right(node, key, value, rsubtree)) {
1136 jermar 172
        /*
173
         * The key-value-rsubtree triplet has been inserted because
174
         * some keys could have been moved to the right sibling.
175
         */
1101 jermar 176
    } else {
177
        btree_node_t *rnode;
1177 jermar 178
        btree_key_t median;
1101 jermar 179
 
180
        /*
1136 jermar 181
         * Node is full and both siblings (if both exist) are full too.
182
         * Split the node and insert the smallest key from the node containing
183
         * bigger keys (i.e. the new node) into its parent.
1101 jermar 184
         */
185
 
186
        rnode = node_split(node, key, value, rsubtree, &median);
187
 
188
        if (LEAF_NODE(node)) {
1144 jermar 189
            list_prepend(&rnode->leaf_link, &node->leaf_link);
1101 jermar 190
        }
191
 
192
        if (ROOT_NODE(node)) {
193
            /*
194
             * We split the root node. Create new root.
195
             */
1164 jermar 196
            t->root = (btree_node_t *) slab_alloc(btree_node_slab, 0);
1101 jermar 197
            node->parent = t->root;
198
            rnode->parent = t->root;
199
            node_initialize(t->root);
200
 
201
            /*
202
             * Left-hand side subtree will be the old root (i.e. node).
203
             * Right-hand side subtree will be rnode.
204
             */        
205
            t->root->subtree[0] = node;
206
 
207
            t->root->depth = node->depth + 1;
208
        }
209
        _btree_insert(t, median, NULL, rnode, node->parent);
210
    }  
211
 
212
}
213
 
1140 jermar 214
/** Remove B-tree node.
215
 *
1708 jermar 216
 * @param t B-tree.
1140 jermar 217
 * @param key Key to be removed from the B-tree along with its associated value.
218
 * @param leaf_node If not NULL, pointer to the leaf node where the key is found.
219
 */
1177 jermar 220
void btree_remove(btree_t *t, btree_key_t key, btree_node_t *leaf_node)
1101 jermar 221
{
1140 jermar 222
    btree_node_t *lnode;
223
 
224
    lnode = leaf_node;
225
    if (!lnode) {
226
        if (!btree_search(t, key, &lnode)) {
3790 svoboda 227
            panic("B-tree %p does not contain key %" PRIu64 ".", t, key);
1140 jermar 228
        }
229
    }
230
 
1142 jermar 231
    _btree_remove(t, key, lnode);
232
}
1140 jermar 233
 
1142 jermar 234
/** Recursively remove B-tree node.
235
 *
1708 jermar 236
 * @param t B-tree.
1142 jermar 237
 * @param key Key to be removed from the B-tree along with its associated value.
238
 * @param node Node where the key being removed resides.
239
 */
1177 jermar 240
void _btree_remove(btree_t *t, btree_key_t key, btree_node_t *node)
1142 jermar 241
{
242
    if (ROOT_NODE(node)) {
243
        if (node->keys == 1 && node->subtree[0]) {
244
            /*
245
             * Free the current root and set new root.
246
             */
247
            t->root = node->subtree[0];
248
            t->root->parent = NULL;
1164 jermar 249
            slab_free(btree_node_slab, node);
1142 jermar 250
        } else {
251
            /*
252
             * Remove the key from the root node.
253
             * Note that the right subtree is removed because when
254
             * combining two nodes, the left-side sibling is preserved
255
             * and the right-side sibling is freed.
256
             */
257
            node_remove_key_and_rsubtree(node, key);
258
        }
259
        return;
260
    }
261
 
262
    if (node->keys <= FILL_FACTOR) {
263
        /*
264
         * If the node is below the fill factor,
265
         * try to borrow keys from left or right sibling.
266
         */
267
        if (!try_rotation_from_left(node))
268
            try_rotation_from_right(node);
269
    }
270
 
271
    if (node->keys > FILL_FACTOR) {
4490 decky 272
        size_t i;
1142 jermar 273
 
274
        /*
275
         * The key can be immediatelly removed.
276
         *
277
         * Note that the right subtree is removed because when
278
         * combining two nodes, the left-side sibling is preserved
279
         * and the right-side sibling is freed.
280
         */
281
        node_remove_key_and_rsubtree(node, key);
282
        for (i = 0; i < node->parent->keys; i++) {
283
            if (node->parent->key[i] == key)
284
                node->parent->key[i] = node->key[0];
285
        }
286
 
287
    } else {
4490 decky 288
        size_t idx;
1142 jermar 289
        btree_node_t *rnode, *parent;
290
 
291
        /*
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.
294
         * The node which is on the left is preserved and the node on the right is
295
         * freed.
296
         */
297
        parent = node->parent;
298
        node_remove_key_and_rsubtree(node, key);
299
        rnode = node_combine(node);
300
        if (LEAF_NODE(rnode))
301
            list_remove(&rnode->leaf_link);
302
        idx = find_key_by_subtree(parent, rnode, true);
303
        ASSERT((int) idx != -1);
1164 jermar 304
        slab_free(btree_node_slab, rnode);
1142 jermar 305
        _btree_remove(t, parent->key[idx], parent);
306
    }
1101 jermar 307
}
308
 
309
/** Search key in a B-tree.
310
 *
311
 * @param t B-tree.
312
 * @param key Key to be searched.
313
 * @param leaf_node Address where to put pointer to visited leaf node.
314
 *
315
 * @return Pointer to value or NULL if there is no such key.
316
 */
1177 jermar 317
void *btree_search(btree_t *t, btree_key_t key, btree_node_t **leaf_node)
1101 jermar 318
{
319
    btree_node_t *cur, *next;
320
 
321
    /*
1134 jermar 322
     * Iteratively descend to the leaf that can contain the searched key.
1101 jermar 323
     */
324
    for (cur = t->root; cur; cur = next) {
1134 jermar 325
 
1101 jermar 326
        /* Last iteration will set this with proper leaf node address. */
327
        *leaf_node = cur;
1134 jermar 328
 
329
        /*
330
         * The key can be in the leftmost subtree.
331
         * Test it separately.
332
         */
333
        if (key < cur->key[0]) {
334
            next = cur->subtree[0];
335
            continue;
336
        } else {
337
            void *val;
4490 decky 338
            size_t i;
1134 jermar 339
 
340
            /*
341
             * Now if the key is smaller than cur->key[i]
342
             * it can only mean that the value is in cur->subtree[i]
343
             * or it is not in the tree at all.
344
             */
345
            for (i = 1; i < cur->keys; i++) {
346
                if (key < cur->key[i]) {
347
                    next = cur->subtree[i];
348
                    val = cur->value[i - 1];
349
 
350
                    if (LEAF_NODE(cur))
351
                        return key == cur->key[i - 1] ? val : NULL;
352
 
353
                    goto descend;
354
                }
1101 jermar 355
            }
1134 jermar 356
 
357
            /*
358
             * Last possibility is that the key is in the rightmost subtree.
359
             */
360
            next = cur->subtree[i];
361
            val = cur->value[i - 1];
362
            if (LEAF_NODE(cur))
363
                return key == cur->key[i - 1] ? val : NULL;
1101 jermar 364
        }
1134 jermar 365
        descend:
366
            ;
1101 jermar 367
    }
368
 
369
    /*
1134 jermar 370
     * The key was not found in the *leaf_node and is smaller than any of its keys.
1101 jermar 371
     */
372
    return NULL;
373
}
374
 
1150 jermar 375
/** Return pointer to B-tree leaf node's left neighbour.
1147 jermar 376
 *
377
 * @param t B-tree.
1150 jermar 378
 * @param node Node whose left neighbour will be returned.
1147 jermar 379
 *
1150 jermar 380
 * @return Left neighbour of the node or NULL if the node does not have the left neighbour.
1147 jermar 381
 */
1150 jermar 382
btree_node_t *btree_leaf_node_left_neighbour(btree_t *t, btree_node_t *node)
1147 jermar 383
{
384
    ASSERT(LEAF_NODE(node));
385
    if (node->leaf_link.prev != &t->leaf_head)
386
        return list_get_instance(node->leaf_link.prev, btree_node_t, leaf_link);
387
    else
388
        return NULL;
389
}
390
 
1150 jermar 391
/** Return pointer to B-tree leaf node's right neighbour.
1147 jermar 392
 *
393
 * @param t B-tree.
1150 jermar 394
 * @param node Node whose right neighbour will be returned.
1147 jermar 395
 *
1150 jermar 396
 * @return Right neighbour of the node or NULL if the node does not have the right neighbour.
1147 jermar 397
 */
1150 jermar 398
btree_node_t *btree_leaf_node_right_neighbour(btree_t *t, btree_node_t *node)
1147 jermar 399
{
400
    ASSERT(LEAF_NODE(node));
401
    if (node->leaf_link.next != &t->leaf_head)
402
        return list_get_instance(node->leaf_link.next, btree_node_t, leaf_link);
403
    else
404
        return NULL;
405
}
406
 
1101 jermar 407
/** Initialize B-tree node.
408
 *
409
 * @param node B-tree node.
410
 */
411
void node_initialize(btree_node_t *node)
412
{
413
    int i;
414
 
415
    node->keys = 0;
416
 
417
    /* Clean also space for the extra key. */
418
    for (i = 0; i < BTREE_MAX_KEYS + 1; i++) {
419
        node->key[i] = 0;
420
        node->value[i] = NULL;
421
        node->subtree[i] = NULL;
422
    }
423
    node->subtree[i] = NULL;
424
 
425
    node->parent = NULL;
426
 
427
    link_initialize(&node->leaf_link);
428
 
429
    link_initialize(&node->bfs_link);
430
    node->depth = 0;
431
}
432
 
1136 jermar 433
/** Insert key-value-lsubtree triplet into B-tree node.
1101 jermar 434
 *
435
 * It is actually possible to have more keys than BTREE_MAX_KEYS.
1136 jermar 436
 * This feature is used during insert by right rotation.
437
 *
438
 * @param node B-tree node into wich the new key is to be inserted.
439
 * @param key The key to be inserted.
440
 * @param value Pointer to value to be inserted.
441
 * @param lsubtree Pointer to the left subtree.
442
 */
1177 jermar 443
void node_insert_key_and_lsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *lsubtree)
1136 jermar 444
{
4490 decky 445
    size_t i;
1136 jermar 446
 
447
    for (i = 0; i < node->keys; i++) {
448
        if (key < node->key[i]) {
4490 decky 449
            size_t j;
1136 jermar 450
 
451
            for (j = node->keys; j > i; j--) {
452
                node->key[j] = node->key[j - 1];
453
                node->value[j] = node->value[j - 1];
454
                node->subtree[j + 1] = node->subtree[j];
455
            }
456
            node->subtree[j + 1] = node->subtree[j];
457
            break; 
458
        }
459
    }
460
    node->key[i] = key;
461
    node->value[i] = value;
462
    node->subtree[i] = lsubtree;
463
 
464
    node->keys++;
465
}
466
 
467
/** Insert key-value-rsubtree triplet into B-tree node.
468
 *
469
 * It is actually possible to have more keys than BTREE_MAX_KEYS.
1101 jermar 470
 * This feature is used during splitting the node when the
1136 jermar 471
 * number of keys is BTREE_MAX_KEYS + 1. Insert by left rotation
472
 * also makes use of this feature.
1101 jermar 473
 *
474
 * @param node B-tree node into wich the new key is to be inserted.
475
 * @param key The key to be inserted.
476
 * @param value Pointer to value to be inserted.
477
 * @param rsubtree Pointer to the right subtree.
478
 */
1177 jermar 479
void node_insert_key_and_rsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree)
1101 jermar 480
{
4490 decky 481
    size_t i;
1101 jermar 482
 
483
    for (i = 0; i < node->keys; i++) {
484
        if (key < node->key[i]) {
4490 decky 485
            size_t j;
1101 jermar 486
 
487
            for (j = node->keys; j > i; j--) {
488
                node->key[j] = node->key[j - 1];
489
                node->value[j] = node->value[j - 1];
490
                node->subtree[j + 1] = node->subtree[j];
491
            }
492
            break; 
493
        }
494
    }
495
    node->key[i] = key;
496
    node->value[i] = value;
497
    node->subtree[i + 1] = rsubtree;
498
 
499
    node->keys++;
500
}
501
 
1144 jermar 502
/** Remove key and its left subtree pointer from B-tree node.
503
 *
504
 * Remove the key and eliminate gaps in node->key array.
505
 * Note that the value pointer and the left subtree pointer
506
 * is removed from the node as well.
507
 *
508
 * @param node B-tree node.
509
 * @param key Key to be removed.
510
 */
1177 jermar 511
void node_remove_key_and_lsubtree(btree_node_t *node, btree_key_t key)
1144 jermar 512
{
4490 decky 513
    size_t i, j;
1144 jermar 514
 
515
    for (i = 0; i < node->keys; i++) {
516
        if (key == node->key[i]) {
517
            for (j = i + 1; j < node->keys; j++) {
518
                node->key[j - 1] = node->key[j];
519
                node->value[j - 1] = node->value[j];
520
                node->subtree[j - 1] = node->subtree[j];
521
            }
522
            node->subtree[j - 1] = node->subtree[j];
523
            node->keys--;
524
            return;
525
        }
526
    }
3790 svoboda 527
    panic("Node %p does not contain key %" PRIu64 ".", node, key);
1144 jermar 528
}
529
 
530
/** Remove key and its right subtree pointer from B-tree node.
531
 *
532
 * Remove the key and eliminate gaps in node->key array.
533
 * Note that the value pointer and the right subtree pointer
534
 * is removed from the node as well.
535
 *
536
 * @param node B-tree node.
537
 * @param key Key to be removed.
538
 */
1177 jermar 539
void node_remove_key_and_rsubtree(btree_node_t *node, btree_key_t key)
1144 jermar 540
{
4490 decky 541
    size_t i, j;
1144 jermar 542
 
543
    for (i = 0; i < node->keys; i++) {
544
        if (key == node->key[i]) {
545
            for (j = i + 1; j < node->keys; j++) {
546
                node->key[j - 1] = node->key[j];
547
                node->value[j - 1] = node->value[j];
548
                node->subtree[j] = node->subtree[j + 1];
549
            }
550
            node->keys--;
551
            return;
552
        }
553
    }
3790 svoboda 554
    panic("Node %p does not contain key %" PRIu64 ".", node, key);
1144 jermar 555
}
556
 
1134 jermar 557
/** Split full B-tree node and insert new key-value-right-subtree triplet.
1101 jermar 558
 *
1757 jermar 559
 * This function will split a node and return a pointer to a newly created
1134 jermar 560
 * node containing keys greater than or equal to the greater of medians
561
 * (or median) of the old keys and the newly added key. It will also write
562
 * the median key to a memory address supplied by the caller.
1101 jermar 563
 *
1134 jermar 564
 * If the node being split is an index node, the median will not be
565
 * included in the new node. If the node is a leaf node,
566
 * the median will be copied there.
1101 jermar 567
 *
568
 * @param node B-tree node wich is going to be split.
569
 * @param key The key to be inserted.
570
 * @param value Pointer to the value to be inserted.
571
 * @param rsubtree Pointer to the right subtree of the key being added.
572
 * @param median Address in memory, where the median key will be stored.
573
 *
574
 * @return Newly created right sibling of node.
575
 */
1177 jermar 576
btree_node_t *node_split(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree, btree_key_t *median)
1101 jermar 577
{
578
    btree_node_t *rnode;
4490 decky 579
    size_t i, j;
1101 jermar 580
 
581
    ASSERT(median);
582
    ASSERT(node->keys == BTREE_MAX_KEYS);
1136 jermar 583
 
1101 jermar 584
    /*
585
     * Use the extra space to store the extra node.
586
     */
1142 jermar 587
    node_insert_key_and_rsubtree(node, key, value, rsubtree);
1101 jermar 588
 
589
    /*
590
     * Compute median of keys.
591
     */
1134 jermar 592
    *median = MEDIAN_HIGH(node);
1101 jermar 593
 
1134 jermar 594
    /*
595
     * Allocate and initialize new right sibling.
596
     */
1164 jermar 597
    rnode = (btree_node_t *) slab_alloc(btree_node_slab, 0);
1101 jermar 598
    node_initialize(rnode);
599
    rnode->parent = node->parent;
600
    rnode->depth = node->depth;
601
 
602
    /*
603
     * Copy big keys, values and subtree pointers to the new right sibling.
1134 jermar 604
     * If this is an index node, do not copy the median.
1101 jermar 605
     */
4490 decky 606
    i = (size_t) INDEX_NODE(node);
1134 jermar 607
    for (i += MEDIAN_HIGH_INDEX(node), j = 0; i < node->keys; i++, j++) {
1101 jermar 608
        rnode->key[j] = node->key[i];
609
        rnode->value[j] = node->value[i];
610
        rnode->subtree[j] = node->subtree[i];
611
 
612
        /*
613
         * Fix parent links in subtrees.
614
         */
615
        if (rnode->subtree[j])
616
            rnode->subtree[j]->parent = rnode;
617
 
618
    }
619
    rnode->subtree[j] = node->subtree[i];
620
    if (rnode->subtree[j])
621
        rnode->subtree[j]->parent = rnode;
1134 jermar 622
 
623
    rnode->keys = j;    /* Set number of keys of the new node. */
624
    node->keys /= 2;    /* Shrink the old node. */
1101 jermar 625
 
626
    return rnode;
627
}
628
 
1142 jermar 629
/** Combine node with any of its siblings.
630
 *
631
 * The siblings are required to be below the fill factor.
632
 *
633
 * @param node Node to combine with one of its siblings.
634
 *
635
 * @return Pointer to the rightmost of the two nodes.
636
 */
637
btree_node_t *node_combine(btree_node_t *node)
638
{
4490 decky 639
    size_t idx;
1142 jermar 640
    btree_node_t *rnode;
4490 decky 641
    size_t i;
1142 jermar 642
 
643
    ASSERT(!ROOT_NODE(node));
644
 
645
    idx = find_key_by_subtree(node->parent, node, false);
646
    if (idx == node->parent->keys) {
647
        /*
648
         * Rightmost subtree of its parent, combine with the left sibling.
649
         */
650
        idx--;
651
        rnode = node;
652
        node = node->parent->subtree[idx];
653
    } else {
654
        rnode = node->parent->subtree[idx + 1];
655
    }
656
 
657
    /* Index nodes need to insert parent node key in between left and right node. */
658
    if (INDEX_NODE(node))
659
        node->key[node->keys++] = node->parent->key[idx];
660
 
661
    /* Copy the key-value-subtree triplets from the right node. */
662
    for (i = 0; i < rnode->keys; i++) {
663
        node->key[node->keys + i] = rnode->key[i];
664
        node->value[node->keys + i] = rnode->value[i];
665
        if (INDEX_NODE(node)) {
666
            node->subtree[node->keys + i] = rnode->subtree[i];
667
            rnode->subtree[i]->parent = node;
668
        }
669
    }
670
    if (INDEX_NODE(node)) {
671
        node->subtree[node->keys + i] = rnode->subtree[i];
672
        rnode->subtree[i]->parent = node;
673
    }
674
 
675
    node->keys += rnode->keys;
676
 
677
    return rnode;
678
}
679
 
1136 jermar 680
/** Find key by its left or right subtree.
681
 *
682
 * @param node B-tree 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.
685
 *
686
 * @return Index of the key associated with the subtree.
687
 */
4490 decky 688
size_t find_key_by_subtree(btree_node_t *node, btree_node_t *subtree, bool right)
1136 jermar 689
{
4490 decky 690
    size_t i;
1136 jermar 691
 
692
    for (i = 0; i < node->keys + 1; i++) {
693
        if (subtree == node->subtree[i])
694
            return i - (int) (right != false);
695
    }
3790 svoboda 696
    panic("Node %p does not contain subtree %p.", node, subtree);
1136 jermar 697
}
698
 
1142 jermar 699
/** Rotate one key-value-rsubtree triplet from the left sibling to the right sibling.
700
 *
701
 * The biggest key and its value and right subtree is rotated from the left node
702
 * to the right. If the node is an index node, than the parent node key belonging to
703
 * the left node takes part in the rotation.
704
 *
705
 * @param lnode Left sibling.
706
 * @param rnode Right sibling.
707
 * @param idx Index of the parent node key that is taking part in the rotation.
708
 */
4490 decky 709
void rotate_from_left(btree_node_t *lnode, btree_node_t *rnode, size_t idx)
1142 jermar 710
{
1177 jermar 711
    btree_key_t key;
1142 jermar 712
 
713
    key = lnode->key[lnode->keys - 1];
714
 
715
    if (LEAF_NODE(lnode)) {
716
        void *value;
717
 
718
        value = lnode->value[lnode->keys - 1];
719
        node_remove_key_and_rsubtree(lnode, key);
720
        node_insert_key_and_lsubtree(rnode, key, value, NULL);
721
        lnode->parent->key[idx] = key;
722
    } else {
723
        btree_node_t *rsubtree;
724
 
725
        rsubtree = lnode->subtree[lnode->keys];
726
        node_remove_key_and_rsubtree(lnode, key);
727
        node_insert_key_and_lsubtree(rnode, lnode->parent->key[idx], NULL, rsubtree);
728
        lnode->parent->key[idx] = key;
729
 
730
        /* Fix parent link of the reconnected right subtree. */
731
        rsubtree->parent = rnode;
732
    }
733
 
734
}
735
 
736
/** Rotate one key-value-lsubtree triplet from the right sibling to the left sibling.
737
 *
738
 * The smallest key and its value and left subtree is rotated from the right node
739
 * to the left. If the node is an index node, than the parent node key belonging to
740
 * the right node takes part in the rotation.
741
 *
742
 * @param lnode Left sibling.
743
 * @param rnode Right sibling.
744
 * @param idx Index of the parent node key that is taking part in the rotation.
745
 */
4490 decky 746
void rotate_from_right(btree_node_t *lnode, btree_node_t *rnode, size_t idx)
1142 jermar 747
{
1177 jermar 748
    btree_key_t key;
1142 jermar 749
 
750
    key = rnode->key[0];
751
 
752
    if (LEAF_NODE(rnode)) {
753
        void *value;
754
 
755
        value = rnode->value[0];
756
        node_remove_key_and_lsubtree(rnode, key);
757
        node_insert_key_and_rsubtree(lnode, key, value, NULL);
758
        rnode->parent->key[idx] = rnode->key[0];
759
    } else {
760
        btree_node_t *lsubtree;
761
 
762
        lsubtree = rnode->subtree[0];
763
        node_remove_key_and_lsubtree(rnode, key);
764
        node_insert_key_and_rsubtree(lnode, rnode->parent->key[idx], NULL, lsubtree);
765
        rnode->parent->key[idx] = key;
766
 
767
        /* Fix parent link of the reconnected left subtree. */
768
        lsubtree->parent = lnode;
769
    }
770
 
771
}
772
 
1136 jermar 773
/** Insert key-value-rsubtree triplet and rotate the node to the left, if this operation can be done.
774
 *
775
 * Left sibling of the node (if it exists) is checked for free space.
776
 * If there is free space, the key is inserted and the smallest key of
777
 * the node is moved there. The index node which is the parent of both
778
 * nodes is fixed.
779
 *
780
 * @param node B-tree node.
781
 * @param inskey Key to be inserted.
782
 * @param insvalue Value to be inserted.
783
 * @param rsubtree Right subtree of inskey.
784
 *
785
 * @return True if the rotation was performed, false otherwise.
786
 */
1177 jermar 787
bool try_insert_by_rotation_to_left(btree_node_t *node, btree_key_t inskey, void *insvalue, btree_node_t *rsubtree)
1136 jermar 788
{
4490 decky 789
    size_t idx;
1136 jermar 790
    btree_node_t *lnode;
791
 
792
    /*
793
     * If this is root node, the rotation can not be done.
794
     */
795
    if (ROOT_NODE(node))
796
        return false;
797
 
798
    idx = find_key_by_subtree(node->parent, node, true);
799
    if ((int) idx == -1) {
800
        /*
801
         * If this node is the leftmost subtree of its parent,
802
         * the rotation can not be done.
803
         */
804
        return false;
805
    }
806
 
807
    lnode = node->parent->subtree[idx];
808
    if (lnode->keys < BTREE_MAX_KEYS) {
809
        /*
810
         * The rotaion can be done. The left sibling has free space.
811
         */
1142 jermar 812
        node_insert_key_and_rsubtree(node, inskey, insvalue, rsubtree);
813
        rotate_from_right(lnode, node, idx);
1136 jermar 814
        return true;
815
    }
816
 
817
    return false;
818
}
819
 
820
/** Insert key-value-rsubtree triplet and rotate the node to the right, if this operation can be done.
821
 *
822
 * Right sibling of the node (if it exists) is checked for free space.
823
 * If there is free space, the key is inserted and the biggest key of
824
 * the node is moved there. The index node which is the parent of both
825
 * nodes is fixed.
826
 *
827
 * @param node B-tree node.
828
 * @param inskey Key to be inserted.
829
 * @param insvalue Value to be inserted.
830
 * @param rsubtree Right subtree of inskey.
831
 *
832
 * @return True if the rotation was performed, false otherwise.
833
 */
1177 jermar 834
bool try_insert_by_rotation_to_right(btree_node_t *node, btree_key_t inskey, void *insvalue, btree_node_t *rsubtree)
1136 jermar 835
{
4490 decky 836
    size_t idx;
1136 jermar 837
    btree_node_t *rnode;
838
 
839
    /*
840
     * If this is root node, the rotation can not be done.
841
     */
842
    if (ROOT_NODE(node))
843
        return false;
844
 
845
    idx = find_key_by_subtree(node->parent, node, false);
846
    if (idx == node->parent->keys) {
847
        /*
848
         * If this node is the rightmost subtree of its parent,
849
         * the rotation can not be done.
850
         */
851
        return false;
852
    }
853
 
854
    rnode = node->parent->subtree[idx + 1];
855
    if (rnode->keys < BTREE_MAX_KEYS) {
856
        /*
857
         * The rotaion can be done. The right sibling has free space.
858
         */
1142 jermar 859
        node_insert_key_and_rsubtree(node, inskey, insvalue, rsubtree);
860
        rotate_from_left(node, rnode, idx);
861
        return true;
862
    }
1136 jermar 863
 
1142 jermar 864
    return false;
865
}
1136 jermar 866
 
1142 jermar 867
/** Rotate in a key from the left sibling or from the index node, if this operation can be done.
868
 *
869
 * @param rnode Node into which to add key from its left sibling or from the index node.
870
 *
871
 * @return True if the rotation was performed, false otherwise.
872
 */
873
bool try_rotation_from_left(btree_node_t *rnode)
874
{
4490 decky 875
    size_t idx;
1142 jermar 876
    btree_node_t *lnode;
1136 jermar 877
 
1142 jermar 878
    /*
879
     * If this is root node, the rotation can not be done.
880
     */
881
    if (ROOT_NODE(rnode))
882
        return false;
883
 
884
    idx = find_key_by_subtree(rnode->parent, rnode, true);
885
    if ((int) idx == -1) {
886
        /*
887
         * If this node is the leftmost subtree of its parent,
888
         * the rotation can not be done.
889
         */
890
        return false;
891
    }
892
 
893
    lnode = rnode->parent->subtree[idx];
894
    if (lnode->keys > FILL_FACTOR) {
895
        rotate_from_left(lnode, rnode, idx);
1136 jermar 896
        return true;
897
    }
1142 jermar 898
 
899
    return false;
900
}
1136 jermar 901
 
1142 jermar 902
/** Rotate in a key from the right sibling or from the index node, if this operation can be done.
903
 *
1708 jermar 904
 * @param lnode Node into which to add key from its right sibling or from the index node.
1142 jermar 905
 *
906
 * @return True if the rotation was performed, false otherwise.
907
 */
908
bool try_rotation_from_right(btree_node_t *lnode)
909
{
4490 decky 910
    size_t idx;
1142 jermar 911
    btree_node_t *rnode;
912
 
913
    /*
914
     * If this is root node, the rotation can not be done.
915
     */
916
    if (ROOT_NODE(lnode))
917
        return false;
918
 
919
    idx = find_key_by_subtree(lnode->parent, lnode, false);
920
    if (idx == lnode->parent->keys) {
921
        /*
922
         * If this node is the rightmost subtree of its parent,
923
         * the rotation can not be done.
924
         */
925
        return false;
926
    }
927
 
928
    rnode = lnode->parent->subtree[idx + 1];
929
    if (rnode->keys > FILL_FACTOR) {
930
        rotate_from_right(lnode, rnode, idx);
931
        return true;
932
    }  
933
 
1136 jermar 934
    return false;
935
}
936
 
1101 jermar 937
/** Print B-tree.
938
 *
939
 * @param t Print out B-tree.
940
 */
941
void btree_print(btree_t *t)
942
{
4490 decky 943
    size_t i;
2111 decky 944
    int depth = t->root->depth;
1144 jermar 945
    link_t head, *cur;
946
 
947
    printf("Printing B-tree:\n");
1101 jermar 948
    list_initialize(&head);
949
    list_append(&t->root->bfs_link, &head);
950
 
951
    /*
952
     * Use BFS search to print out the tree.
953
     * Levels are distinguished from one another by node->depth.
954
     */
955
    while (!list_empty(&head)) {
956
        link_t *hlp;
957
        btree_node_t *node;
958
 
959
        hlp = head.next;
960
        ASSERT(hlp != &head);
961
        node = list_get_instance(hlp, btree_node_t, bfs_link);
962
        list_remove(hlp);
963
 
964
        ASSERT(node);
965
 
966
        if (node->depth != depth) {
967
            printf("\n");
968
            depth = node->depth;
969
        }
970
 
971
        printf("(");
972
        for (i = 0; i < node->keys; i++) {
3058 decky 973
            printf("%" PRIu64 "%s", node->key[i], i < node->keys - 1 ? "," : "");
1101 jermar 974
            if (node->depth && node->subtree[i]) {
975
                list_append(&node->subtree[i]->bfs_link, &head);
976
            }
977
        }
978
        if (node->depth && node->subtree[i]) {
979
            list_append(&node->subtree[i]->bfs_link, &head);
980
        }
981
        printf(")");
982
    }
983
    printf("\n");
1144 jermar 984
 
985
    printf("Printing list of leaves:\n");
986
    for (cur = t->leaf_head.next; cur != &t->leaf_head; cur = cur->next) {
987
        btree_node_t *node;
988
 
989
        node = list_get_instance(cur, btree_node_t, leaf_link);
990
 
991
        ASSERT(node);
992
 
993
        printf("(");
994
        for (i = 0; i < node->keys; i++)
3058 decky 995
            printf("%" PRIu64 "%s", node->key[i], i < node->keys - 1 ? "," : "");
1144 jermar 996
        printf(")");
997
    }
998
    printf("\n");
1101 jermar 999
}
1702 cejka 1000
 
1757 jermar 1001
/** @}
1702 cejka 1002
 */