← Back to branch summary

~vojtech-horky/helenos/helenos-qemu

« back to all changes in this revision

Viewing changes to kernel/generic/src/adt/btree.c

  • Committer: Martin Decky
  • Date: 2009-08-04 11:19:19 UTC
  • Revision ID: martin@uranus.dsrg.hide.ms.mff.cuni.cz-20090804111919-evyclddlr3v5lhmp
Initial import

Show diffs side-by-side

added added

removed removed

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