Subversion Repositories HelenOS

Rev

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