Subversion Repositories HelenOS

Rev

Rev 2111 | Go to most recent revision | Only display areas with differences | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

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