Subversion Repositories HelenOS

Rev

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

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