Subversion Repositories HelenOS-historic

Rev

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