Subversion Repositories HelenOS-historic

Rev

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