Subversion Repositories HelenOS-historic

Rev

Rev 1140 | Rev 1147 | Go to most recent revision | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 1140 Rev 1142
Line 45... Line 45...
45
#include <panic.h>
45
#include <panic.h>
46
#include <typedefs.h>
46
#include <typedefs.h>
47
#include <print.h>
47
#include <print.h>
48
 
48
 
49
static void _btree_insert(btree_t *t, __native key, void *value, btree_node_t *rsubtree, btree_node_t *node);
49
static void _btree_insert(btree_t *t, __native key, void *value, btree_node_t *rsubtree, btree_node_t *node);
-
 
50
static void _btree_remove(btree_t *t, __native key, btree_node_t *node);
50
static void node_initialize(btree_node_t *node);
51
static void node_initialize(btree_node_t *node);
51
static void node_insert_key_left(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree);
52
static void node_insert_key_and_lsubtree(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree);
52
static void node_insert_key_right(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);
53
static btree_node_t *node_split(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree, __native *median);
54
static btree_node_t *node_split(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree, __native *median);
-
 
55
static btree_node_t *node_combine(btree_node_t *node);
54
static void node_remove_key_left(btree_node_t *node, __native key);
56
static void node_remove_key_and_lsubtree(btree_node_t *node, __native key);
55
static void node_remove_key_right(btree_node_t *node, __native key);
57
static void node_remove_key_and_rsubtree(btree_node_t *node, __native key);
56
static index_t find_key_by_subtree(btree_node_t *node, btree_node_t *subtree, bool right);
58
static index_t find_key_by_subtree(btree_node_t *node, btree_node_t *subtree, bool right);
-
 
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);
57
static bool try_insert_by_left_rotation(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree);
61
static bool try_insert_by_rotation_to_left(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree);
58
static bool try_insert_by_right_rotation(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);
59
 
65
 
60
#define ROOT_NODE(n)        (!(n)->parent)
66
#define ROOT_NODE(n)        (!(n)->parent)
61
#define INDEX_NODE(n)       ((n)->subtree[0] != NULL)
67
#define INDEX_NODE(n)       ((n)->subtree[0] != NULL)
62
#define LEAF_NODE(n)        ((n)->subtree[0] == NULL)
68
#define LEAF_NODE(n)        ((n)->subtree[0] == NULL)
63
 
69
 
Line 122... Line 128...
122
{
128
{
123
    if (node->keys < BTREE_MAX_KEYS) {
129
    if (node->keys < BTREE_MAX_KEYS) {
124
        /*
130
        /*
125
         * Node conatins enough space, the key can be stored immediately.
131
         * Node conatins enough space, the key can be stored immediately.
126
         */
132
         */
127
        node_insert_key_right(node, key, value, rsubtree);
133
        node_insert_key_and_rsubtree(node, key, value, rsubtree);
128
    } else if (try_insert_by_left_rotation(node, key, value, rsubtree)) {
134
    } else if (try_insert_by_rotation_to_left(node, key, value, rsubtree)) {
129
        /*
135
        /*
130
         * The key-value-rsubtree triplet has been inserted because
136
         * The key-value-rsubtree triplet has been inserted because
131
         * some keys could have been moved to the left sibling.
137
         * some keys could have been moved to the left sibling.
132
         */
138
         */
133
    } else if (try_insert_by_right_rotation(node, key, value, rsubtree)) {
139
    } else if (try_insert_by_rotation_to_right(node, key, value, rsubtree)) {
134
        /*
140
        /*
135
         * The key-value-rsubtree triplet has been inserted because
141
         * The key-value-rsubtree triplet has been inserted because
136
         * some keys could have been moved to the right sibling.
142
         * some keys could have been moved to the right sibling.
137
         */
143
         */
138
    } else {
144
    } else {
Line 181... Line 187...
181
 */
187
 */
182
void btree_remove(btree_t *t, __native key, btree_node_t *leaf_node)
188
void btree_remove(btree_t *t, __native key, btree_node_t *leaf_node)
183
{
189
{
184
    btree_node_t *lnode;
190
    btree_node_t *lnode;
185
   
191
   
-
 
192
    panic("%s needs testing and is disabled in revision %s\n", __FUNCTION__, REVISION);
186
    lnode = leaf_node;
193
    lnode = leaf_node;
187
    if (!lnode) {
194
    if (!lnode) {
188
        if (!btree_search(t, key, &lnode)) {
195
        if (!btree_search(t, key, &lnode)) {
189
            panic("B-tree %P does not contain key %d\n", t, key);
196
            panic("B-tree %P does not contain key %d\n", t, key);
190
        }
197
        }
191
    }
198
    }
192
   
199
   
-
 
200
    _btree_remove(t, key, lnode);
-
 
201
}
-
 
202
 
-
 
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);
193
    /* TODO */
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;
194
 
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
    }
195
}
276
}
196
 
277
 
197
/** Search key in a B-tree.
278
/** Search key in a B-tree.
198
 *
279
 *
199
 * @param t B-tree.
280
 * @param t B-tree.
Line 258... Line 339...
258
     * The key was not found in the *leaf_node and is smaller than any of its keys.
339
     * The key was not found in the *leaf_node and is smaller than any of its keys.
259
     */
340
     */
260
    return NULL;
341
    return NULL;
261
}
342
}
262
 
343
 
263
/** Get pointer to value with the smallest key within the node.
-
 
264
 *
-
 
265
 * Can be only used on leaf-level nodes.
-
 
266
 *
-
 
267
 * @param node B-tree node.
-
 
268
 *
-
 
269
 * @return Pointer to value assiciated with the smallest key.
-
 
270
 */
-
 
271
void *btree_node_min(btree_node_t *node)
-
 
272
{
-
 
273
    ASSERT(LEAF_NODE(node));
-
 
274
    ASSERT(node->keys);
-
 
275
    return node->value[0];
-
 
276
}
-
 
277
 
-
 
278
/** Get pointer to value with the biggest key within the node.
-
 
279
 *
-
 
280
 * Can be only used on leaf-level nodes.
-
 
281
 *
-
 
282
 * @param node B-tree node.
-
 
283
 *
-
 
284
 * @return Pointer to value assiciated with the biggest key.
-
 
285
 */
-
 
286
void *btree_node_max(btree_node_t *node)
-
 
287
{
-
 
288
    ASSERT(LEAF_NODE(node));
-
 
289
    ASSERT(node->keys);
-
 
290
    return node->value[node->keys - 1];
-
 
291
}
-
 
292
 
-
 
293
/** Initialize B-tree node.
344
/** Initialize B-tree node.
294
 *
345
 *
295
 * @param node B-tree node.
346
 * @param node B-tree node.
296
 */
347
 */
297
void node_initialize(btree_node_t *node)
348
void node_initialize(btree_node_t *node)
Line 324... Line 375...
324
 * @param node B-tree node into wich the new key is to be inserted.
375
 * @param node B-tree node into wich the new key is to be inserted.
325
 * @param key The key to be inserted.
376
 * @param key The key to be inserted.
326
 * @param value Pointer to value to be inserted.
377
 * @param value Pointer to value to be inserted.
327
 * @param lsubtree Pointer to the left subtree.
378
 * @param lsubtree Pointer to the left subtree.
328
 */
379
 */
329
void node_insert_key_left(btree_node_t *node, __native key, void *value, btree_node_t *lsubtree)
380
void node_insert_key_and_lsubtree(btree_node_t *node, __native key, void *value, btree_node_t *lsubtree)
330
{
381
{
331
    int i;
382
    int i;
332
 
383
 
333
    for (i = 0; i < node->keys; i++) {
384
    for (i = 0; i < node->keys; i++) {
334
        if (key < node->key[i]) {
385
        if (key < node->key[i]) {
Line 348... Line 399...
348
    node->subtree[i] = lsubtree;
399
    node->subtree[i] = lsubtree;
349
           
400
           
350
    node->keys++;
401
    node->keys++;
351
}
402
}
352
 
403
 
353
 
-
 
354
/** Insert key-value-rsubtree triplet into B-tree node.
404
/** Insert key-value-rsubtree triplet into B-tree node.
355
 *
405
 *
356
 * It is actually possible to have more keys than BTREE_MAX_KEYS.
406
 * It is actually possible to have more keys than BTREE_MAX_KEYS.
357
 * This feature is used during splitting the node when the
407
 * This feature is used during splitting the node when the
358
 * number of keys is BTREE_MAX_KEYS + 1. Insert by left rotation
408
 * number of keys is BTREE_MAX_KEYS + 1. Insert by left rotation
Line 361... Line 411...
361
 * @param node B-tree node into wich the new key is to be inserted.
411
 * @param node B-tree node into wich the new key is to be inserted.
362
 * @param key The key to be inserted.
412
 * @param key The key to be inserted.
363
 * @param value Pointer to value to be inserted.
413
 * @param value Pointer to value to be inserted.
364
 * @param rsubtree Pointer to the right subtree.
414
 * @param rsubtree Pointer to the right subtree.
365
 */
415
 */
366
void node_insert_key_right(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree)
416
void node_insert_key_and_rsubtree(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree)
367
{
417
{
368
    int i;
418
    int i;
369
 
419
 
370
    for (i = 0; i < node->keys; i++) {
420
    for (i = 0; i < node->keys; i++) {
371
        if (key < node->key[i]) {
421
        if (key < node->key[i]) {
Line 414... Line 464...
414
    ASSERT(node->keys == BTREE_MAX_KEYS);
464
    ASSERT(node->keys == BTREE_MAX_KEYS);
415
 
465
 
416
    /*
466
    /*
417
     * Use the extra space to store the extra node.
467
     * Use the extra space to store the extra node.
418
     */
468
     */
419
    node_insert_key_right(node, key, value, rsubtree);
469
    node_insert_key_and_rsubtree(node, key, value, rsubtree);
420
 
470
 
421
    /*
471
    /*
422
     * Compute median of keys.
472
     * Compute median of keys.
423
     */
473
     */
424
    *median = MEDIAN_HIGH(node);
474
    *median = MEDIAN_HIGH(node);
Line 456... Line 506...
456
    node->keys /= 2;    /* Shrink the old node. */
506
    node->keys /= 2;    /* Shrink the old node. */
457
       
507
       
458
    return rnode;
508
    return rnode;
459
}
509
}
460
 
510
 
-
 
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
 
461
/** Remove key and its left subtree pointer from B-tree node.
562
/** Remove key and its left subtree pointer from B-tree node.
462
 *
563
 *
463
 * Remove the key and eliminate gaps in node->key array.
564
 * Remove the key and eliminate gaps in node->key array.
464
 * Note that the value pointer and the left subtree pointer
565
 * Note that the value pointer and the left subtree pointer
465
 * is removed from the node as well.
566
 * is removed from the node as well.
466
 *
567
 *
467
 * @param node B-tree node.
568
 * @param node B-tree node.
468
 * @param key Key to be removed.
569
 * @param key Key to be removed.
469
 */
570
 */
470
void node_remove_key_left(btree_node_t *node, __native key)
571
void node_remove_key_and_lsubtree(btree_node_t *node, __native key)
471
{
572
{
472
    int i, j;
573
    int i, j;
473
   
574
   
474
    for (i = 0; i < node->keys; i++) {
575
    for (i = 0; i < node->keys; i++) {
475
        if (key == node->key[i]) {
576
        if (key == node->key[i]) {
Line 493... Line 594...
493
 * is removed from the node as well.
594
 * is removed from the node as well.
494
 *
595
 *
495
 * @param node B-tree node.
596
 * @param node B-tree node.
496
 * @param key Key to be removed.
597
 * @param key Key to be removed.
497
 */
598
 */
498
void node_remove_key_right(btree_node_t *node, __native key)
599
void node_remove_key_and_rsubtree(btree_node_t *node, __native key)
499
{
600
{
500
    int i, j;
601
    int i, j;
501
   
602
   
502
    for (i = 0; i < node->keys; i++) {
603
    for (i = 0; i < node->keys; i++) {
503
        if (key == node->key[i]) {
604
        if (key == node->key[i]) {
Line 530... Line 631...
530
            return i - (int) (right != false);
631
            return i - (int) (right != false);
531
    }
632
    }
532
    panic("node %P does not contain subtree %P\n", node, subtree);
633
    panic("node %P does not contain subtree %P\n", node, subtree);
533
}
634
}
534
 
635
 
-
 
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
 
535
/** Insert key-value-rsubtree triplet and rotate the node to the left, if this operation can be done.
710
/** Insert key-value-rsubtree triplet and rotate the node to the left, if this operation can be done.
536
 *
711
 *
537
 * Left sibling of the node (if it exists) is checked for free space.
712
 * Left sibling of the node (if it exists) is checked for free space.
538
 * If there is free space, the key is inserted and the smallest key of
713
 * If there is free space, the key is inserted and the smallest key of
539
 * the node is moved there. The index node which is the parent of both
714
 * the node is moved there. The index node which is the parent of both
Line 544... Line 719...
544
 * @param insvalue Value to be inserted.
719
 * @param insvalue Value to be inserted.
545
 * @param rsubtree Right subtree of inskey.
720
 * @param rsubtree Right subtree of inskey.
546
 *
721
 *
547
 * @return True if the rotation was performed, false otherwise.
722
 * @return True if the rotation was performed, false otherwise.
548
 */
723
 */
549
bool try_insert_by_left_rotation(btree_node_t *node, __native inskey, void *insvalue, btree_node_t *rsubtree)
724
bool try_insert_by_rotation_to_left(btree_node_t *node, __native inskey, void *insvalue, btree_node_t *rsubtree)
550
{
725
{
551
    index_t idx;
726
    index_t idx;
552
    btree_node_t *lnode;
727
    btree_node_t *lnode;
553
 
728
 
554
    /*
729
    /*
Line 565... Line 740...
565
         */
740
         */
566
        return false;
741
        return false;
567
    }
742
    }
568
       
743
       
569
    lnode = node->parent->subtree[idx];
744
    lnode = node->parent->subtree[idx];
570
 
-
 
571
    if (lnode->keys < BTREE_MAX_KEYS) {
745
    if (lnode->keys < BTREE_MAX_KEYS) {
572
        __native key;
-
 
573
 
-
 
574
        /*
746
        /*
575
         * The rotaion can be done. The left sibling has free space.
747
         * The rotaion can be done. The left sibling has free space.
576
         */
748
         */
577
 
-
 
578
        node_insert_key_right(node, inskey, insvalue, rsubtree);
749
        node_insert_key_and_rsubtree(node, inskey, insvalue, rsubtree);
579
        key = node->key[0];
-
 
580
       
-
 
581
        if (LEAF_NODE(node)) {
-
 
582
            void *value;
-
 
583
 
-
 
584
            value = node->value[0];
-
 
585
            node_remove_key_left(node, key);
-
 
586
            node_insert_key_right(lnode, key, value, NULL);
750
        rotate_from_right(lnode, node, idx);
587
            node->parent->key[idx] = node->key[0];
-
 
588
        } else {
-
 
589
            btree_node_t *lsubtree;
-
 
590
 
-
 
591
            lsubtree = node->subtree[0];
-
 
592
            node_remove_key_left(node, key);
-
 
593
            node_insert_key_right(lnode, node->parent->key[idx], NULL, lsubtree);
-
 
594
            node->parent->key[idx] = key;
-
 
595
 
-
 
596
            /* Fix parent link of the reconnected left subtree. */
-
 
597
            lsubtree->parent = lnode;
-
 
598
        }
-
 
599
        return true;
751
        return true;
600
    }
752
    }
601
 
753
 
602
    return false;
754
    return false;
603
}
755
}
Line 614... Line 766...
614
 * @param insvalue Value to be inserted.
766
 * @param insvalue Value to be inserted.
615
 * @param rsubtree Right subtree of inskey.
767
 * @param rsubtree Right subtree of inskey.
616
 *
768
 *
617
 * @return True if the rotation was performed, false otherwise.
769
 * @return True if the rotation was performed, false otherwise.
618
 */
770
 */
619
bool try_insert_by_right_rotation(btree_node_t *node, __native inskey, void *insvalue, btree_node_t *rsubtree)
771
bool try_insert_by_rotation_to_right(btree_node_t *node, __native inskey, void *insvalue, btree_node_t *rsubtree)
620
{
772
{
621
    index_t idx;
773
    index_t idx;
622
    btree_node_t *rnode;
774
    btree_node_t *rnode;
623
 
775
 
624
    /*
776
    /*
Line 635... Line 787...
635
         */
787
         */
636
        return false;
788
        return false;
637
    }
789
    }
638
       
790
       
639
    rnode = node->parent->subtree[idx + 1];
791
    rnode = node->parent->subtree[idx + 1];
640
 
-
 
641
    if (rnode->keys < BTREE_MAX_KEYS) {
792
    if (rnode->keys < BTREE_MAX_KEYS) {
642
        __native key;
-
 
643
 
-
 
644
        /*
793
        /*
645
         * The rotaion can be done. The right sibling has free space.
794
         * The rotaion can be done. The right sibling has free space.
646
         */
795
         */
-
 
796
        node_insert_key_and_rsubtree(node, inskey, insvalue, rsubtree);
-
 
797
        rotate_from_left(node, rnode, idx);
-
 
798
        return true;
-
 
799
    }
647
 
800
 
648
        node_insert_key_right(node, inskey, insvalue, rsubtree);
-
 
649
        key = node->key[node->keys - 1];
-
 
650
       
-
 
651
        if (LEAF_NODE(node)) {
-
 
652
            void *value;
801
    return false;
653
 
802
}
654
            value = node->value[node->keys - 1];
-
 
655
            node_remove_key_right(node, key);
-
 
656
            node_insert_key_left(rnode, key, value, NULL);
-
 
657
            node->parent->key[idx] = key;
-
 
658
        } else {
-
 
659
            btree_node_t *rsubt;
-
 
660
 
803
 
-
 
804
/** Rotate in a key from the left sibling or from the index node, if this operation can be done.
-
 
805
 *
661
            rsubt = node->subtree[node->keys];
806
 * @param rnode Node into which to add key from its left sibling or from the index node.
-
 
807
 *
662
            node_remove_key_right(node, key);
808
 * @return True if the rotation was performed, false otherwise.
-
 
809
 */
663
            node_insert_key_left(rnode, node->parent->key[idx], NULL, rsubt);
810
bool try_rotation_from_left(btree_node_t *rnode)
-
 
811
{
-
 
812
    index_t idx;
664
            node->parent->key[idx] = key;
813
    btree_node_t *lnode;
665
 
814
 
-
 
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
        /*
666
            /* Fix parent link of the reconnected right subtree. */
824
         * If this node is the leftmost subtree of its parent,
-
 
825
         * the rotation can not be done.
-
 
826
         */
667
            rsubt->parent = rnode;
827
        return false;
-
 
828
    }
668
        }
829
       
-
 
830
    lnode = rnode->parent->subtree[idx];
-
 
831
    if (lnode->keys > FILL_FACTOR) {
-
 
832
        rotate_from_left(lnode, rnode, idx);
669
        return true;
833
        return true;
670
    }
834
    }
-
 
835
   
-
 
836
    return false;
-
 
837
}
-
 
838
 
-
 
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
    }  
671
 
870
 
672
    return false;
871
    return false;
673
}
872
}
674
 
873
 
675
/** Print B-tree.
874
/** Print B-tree.