Subversion Repositories HelenOS

Rev

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