Subversion Repositories HelenOS-historic

Rev

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