Subversion Repositories HelenOS

Rev

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

Rev 1136 Rev 1140
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
/*
29
/*
30
 * This B-tree has the following properties:
30
 * This B-tree has the following properties:
31
 * - it is a ballanced 2-3-4 tree (i.e. BTREE_M = 4)
31
 * - it is a ballanced 2-3-4-5 tree (i.e. BTREE_M = 5)
32
 * - values (i.e. pointers to values) are stored only in leaves
32
 * - values (i.e. pointers to values) are stored only in leaves
33
 * - leaves are linked in a list
33
 * - leaves are linked in a list
34
 * - technically, it is a B+-tree (because of the previous properties)
34
 * - technically, it is a B+-tree (because of the previous properties)
35
 *
35
 *
36
 * Be carefull when using these trees. They need to allocate
36
 * Be carefull when using these trees. They need to allocate
37
 * and deallocate memory for their index nodes and as such
37
 * and deallocate memory for their index nodes and as such
38
 * can sleep.
38
 * can sleep.
39
 */
39
 */
40
 
40
 
41
#include <adt/btree.h>
41
#include <adt/btree.h>
42
#include <adt/list.h>
42
#include <adt/list.h>
43
#include <mm/slab.h>
43
#include <mm/slab.h>
44
#include <debug.h>
44
#include <debug.h>
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 node_initialize(btree_node_t *node);
50
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);
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_right(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 btree_node_t *node_split(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree, __native *median);
53
static btree_node_t *node_split(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree, __native *median);
54
static void node_remove_key_left(btree_node_t *node, __native key);
54
static void node_remove_key_left(btree_node_t *node, __native key);
55
static void node_remove_key_right(btree_node_t *node, __native key);
55
static void node_remove_key_right(btree_node_t *node, __native key);
56
static index_t find_key_by_subtree(btree_node_t *node, btree_node_t *subtree, bool right);
56
static index_t find_key_by_subtree(btree_node_t *node, btree_node_t *subtree, bool right);
57
static bool try_insert_by_left_rotation(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree);
57
static bool try_insert_by_left_rotation(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);
58
static bool try_insert_by_right_rotation(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree);
59
 
59
 
60
#define ROOT_NODE(n)        (!(n)->parent)
60
#define ROOT_NODE(n)        (!(n)->parent)
61
#define INDEX_NODE(n)       ((n)->subtree[0] != NULL)
61
#define INDEX_NODE(n)       ((n)->subtree[0] != NULL)
62
#define LEAF_NODE(n)        ((n)->subtree[0] == NULL)
62
#define LEAF_NODE(n)        ((n)->subtree[0] == NULL)
63
 
63
 
-
 
64
#define FILL_FACTOR     ((BTREE_M-1)/2)
-
 
65
 
64
#define MEDIAN_LOW_INDEX(n) (((n)->keys-1)/2)
66
#define MEDIAN_LOW_INDEX(n) (((n)->keys-1)/2)
65
#define MEDIAN_HIGH_INDEX(n)    ((n)->keys/2)
67
#define MEDIAN_HIGH_INDEX(n)    ((n)->keys/2)
66
#define MEDIAN_LOW(n)       ((n)->key[MEDIAN_LOW_INDEX((n))]);
68
#define MEDIAN_LOW(n)       ((n)->key[MEDIAN_LOW_INDEX((n))]);
67
#define MEDIAN_HIGH(n)      ((n)->key[MEDIAN_HIGH_INDEX((n))]);
69
#define MEDIAN_HIGH(n)      ((n)->key[MEDIAN_HIGH_INDEX((n))]);
68
 
70
 
69
/** Create empty B-tree.
71
/** Create empty B-tree.
70
 *
72
 *
71
 * @param t B-tree.
73
 * @param t B-tree.
72
 */
74
 */
73
void btree_create(btree_t *t)
75
void btree_create(btree_t *t)
74
{
76
{
75
    list_initialize(&t->leaf_head);
77
    list_initialize(&t->leaf_head);
76
    t->root = (btree_node_t *) malloc(sizeof(btree_node_t), 0);
78
    t->root = (btree_node_t *) malloc(sizeof(btree_node_t), 0);
77
    node_initialize(t->root);
79
    node_initialize(t->root);
78
    list_append(&t->root->leaf_link, &t->leaf_head);
80
    list_append(&t->root->leaf_link, &t->leaf_head);
79
}
81
}
80
 
82
 
81
/** Destroy empty B-tree. */
83
/** Destroy empty B-tree. */
82
void btree_destroy(btree_t *t)
84
void btree_destroy(btree_t *t)
83
{
85
{
84
    ASSERT(!t->root->keys);
86
    ASSERT(!t->root->keys);
85
    free(t->root);
87
    free(t->root);
86
}
88
}
87
 
89
 
88
/** Insert key-value pair into B-tree.
90
/** Insert key-value pair into B-tree.
89
 *
91
 *
90
 * @param t B-tree.
92
 * @param t B-tree.
91
 * @param key Key to be inserted.
93
 * @param key Key to be inserted.
92
 * @param value Value to be inserted.
94
 * @param value Value to be inserted.
93
 * @param leaf_node Leaf node where the insertion should begin.
95
 * @param leaf_node Leaf node where the insertion should begin.
94
 */
96
 */
95
void btree_insert(btree_t *t, __native key, void *value, btree_node_t *leaf_node)
97
void btree_insert(btree_t *t, __native key, void *value, btree_node_t *leaf_node)
96
{
98
{
97
    btree_node_t *lnode;
99
    btree_node_t *lnode;
98
   
100
   
99
    ASSERT(value);
101
    ASSERT(value);
100
   
102
   
101
    lnode = leaf_node;
103
    lnode = leaf_node;
102
    if (!lnode) {
104
    if (!lnode) {
103
        if (btree_search(t, key, &lnode)) {
105
        if (btree_search(t, key, &lnode)) {
104
            panic("B-tree %P already contains key %d\n", t, key);
106
            panic("B-tree %P already contains key %d\n", t, key);
105
        }
107
        }
106
    }
108
    }
107
   
109
   
108
    _btree_insert(t, key, value, NULL, lnode);
110
    _btree_insert(t, key, value, NULL, lnode);
109
}
111
}
110
 
112
 
111
/** Recursively insert into B-tree.
113
/** Recursively insert into B-tree.
112
 *
114
 *
113
 * @param t B-tree.
115
 * @param t B-tree.
114
 * @param key Key to be inserted.
116
 * @param key Key to be inserted.
115
 * @param value Value to be inserted.
117
 * @param value Value to be inserted.
116
 * @param rsubtree Right subtree of the inserted key.
118
 * @param rsubtree Right subtree of the inserted key.
117
 * @param node Start inserting into this node.
119
 * @param node Start inserting into this node.
118
 */
120
 */
119
void _btree_insert(btree_t *t, __native key, void *value, btree_node_t *rsubtree, btree_node_t *node)
121
void _btree_insert(btree_t *t, __native key, void *value, btree_node_t *rsubtree, btree_node_t *node)
120
{
122
{
121
    if (node->keys < BTREE_MAX_KEYS) {
123
    if (node->keys < BTREE_MAX_KEYS) {
122
        /*
124
        /*
123
         * Node conatins enough space, the key can be stored immediately.
125
         * Node conatins enough space, the key can be stored immediately.
124
         */
126
         */
125
        node_insert_key_right(node, key, value, rsubtree);
127
        node_insert_key_right(node, key, value, rsubtree);
126
    } else if (try_insert_by_left_rotation(node, key, value, rsubtree)) {
128
    } else if (try_insert_by_left_rotation(node, key, value, rsubtree)) {
127
        /*
129
        /*
128
         * The key-value-rsubtree triplet has been inserted because
130
         * The key-value-rsubtree triplet has been inserted because
129
         * some keys could have been moved to the left sibling.
131
         * some keys could have been moved to the left sibling.
130
         */
132
         */
131
    } else if (try_insert_by_right_rotation(node, key, value, rsubtree)) {
133
    } else if (try_insert_by_right_rotation(node, key, value, rsubtree)) {
132
        /*
134
        /*
133
         * The key-value-rsubtree triplet has been inserted because
135
         * The key-value-rsubtree triplet has been inserted because
134
         * some keys could have been moved to the right sibling.
136
         * some keys could have been moved to the right sibling.
135
         */
137
         */
136
    } else {
138
    } else {
137
        btree_node_t *rnode;
139
        btree_node_t *rnode;
138
        __native median;
140
        __native median;
139
       
141
       
140
        /*
142
        /*
141
         * Node is full and both siblings (if both exist) are full too.
143
         * Node is full and both siblings (if both exist) are full too.
142
         * Split the node and insert the smallest key from the node containing
144
         * Split the node and insert the smallest key from the node containing
143
         * bigger keys (i.e. the new node) into its parent.
145
         * bigger keys (i.e. the new node) into its parent.
144
         */
146
         */
145
 
147
 
146
        rnode = node_split(node, key, value, rsubtree, &median);
148
        rnode = node_split(node, key, value, rsubtree, &median);
147
 
149
 
148
        if (LEAF_NODE(node)) {
150
        if (LEAF_NODE(node)) {
149
            list_append(&rnode->leaf_link, &node->leaf_link);
151
            list_append(&rnode->leaf_link, &node->leaf_link);
150
        }
152
        }
151
       
153
       
152
        if (ROOT_NODE(node)) {
154
        if (ROOT_NODE(node)) {
153
            /*
155
            /*
154
             * We split the root node. Create new root.
156
             * We split the root node. Create new root.
155
             */
157
             */
156
            t->root = (btree_node_t *) malloc(sizeof(btree_node_t), 0);
158
            t->root = (btree_node_t *) malloc(sizeof(btree_node_t), 0);
157
            node->parent = t->root;
159
            node->parent = t->root;
158
            rnode->parent = t->root;
160
            rnode->parent = t->root;
159
            node_initialize(t->root);
161
            node_initialize(t->root);
160
           
162
           
161
            /*
163
            /*
162
             * Left-hand side subtree will be the old root (i.e. node).
164
             * Left-hand side subtree will be the old root (i.e. node).
163
             * Right-hand side subtree will be rnode.
165
             * Right-hand side subtree will be rnode.
164
             */        
166
             */        
165
            t->root->subtree[0] = node;
167
            t->root->subtree[0] = node;
166
 
168
 
167
            t->root->depth = node->depth + 1;
169
            t->root->depth = node->depth + 1;
168
        }
170
        }
169
        _btree_insert(t, median, NULL, rnode, node->parent);
171
        _btree_insert(t, median, NULL, rnode, node->parent);
170
    }  
172
    }  
171
       
173
       
172
}
174
}
173
 
175
 
-
 
176
/** Remove B-tree node.
-
 
177
 *
-
 
178
 * @param B-tree.
-
 
179
 * @param key Key to be removed from the B-tree along with its associated value.
-
 
180
 * @param leaf_node If not NULL, pointer to the leaf node where the key is found.
174
/* TODO */
181
 */
175
void btree_remove(btree_t *t, __native key)
182
void btree_remove(btree_t *t, __native key, btree_node_t *leaf_node)
176
{
183
{
-
 
184
    btree_node_t *lnode;
-
 
185
   
-
 
186
    lnode = leaf_node;
-
 
187
    if (!lnode) {
-
 
188
        if (!btree_search(t, key, &lnode)) {
-
 
189
            panic("B-tree %P does not contain key %d\n", t, key);
-
 
190
        }
-
 
191
    }
-
 
192
   
-
 
193
    /* TODO */
-
 
194
 
177
}
195
}
178
 
196
 
179
/** Search key in a B-tree.
197
/** Search key in a B-tree.
180
 *
198
 *
181
 * @param t B-tree.
199
 * @param t B-tree.
182
 * @param key Key to be searched.
200
 * @param key Key to be searched.
183
 * @param leaf_node Address where to put pointer to visited leaf node.
201
 * @param leaf_node Address where to put pointer to visited leaf node.
184
 *
202
 *
185
 * @return Pointer to value or NULL if there is no such key.
203
 * @return Pointer to value or NULL if there is no such key.
186
 */
204
 */
187
void *btree_search(btree_t *t, __native key, btree_node_t **leaf_node)
205
void *btree_search(btree_t *t, __native key, btree_node_t **leaf_node)
188
{
206
{
189
    btree_node_t *cur, *next;
207
    btree_node_t *cur, *next;
190
   
208
   
191
    /*
209
    /*
192
     * Iteratively descend to the leaf that can contain the searched key.
210
     * Iteratively descend to the leaf that can contain the searched key.
193
     */
211
     */
194
    for (cur = t->root; cur; cur = next) {
212
    for (cur = t->root; cur; cur = next) {
195
 
213
 
196
        /* Last iteration will set this with proper leaf node address. */
214
        /* Last iteration will set this with proper leaf node address. */
197
        *leaf_node = cur;
215
        *leaf_node = cur;
198
       
216
       
199
        /*
217
        /*
200
         * The key can be in the leftmost subtree.
218
         * The key can be in the leftmost subtree.
201
         * Test it separately.
219
         * Test it separately.
202
         */
220
         */
203
        if (key < cur->key[0]) {
221
        if (key < cur->key[0]) {
204
            next = cur->subtree[0];
222
            next = cur->subtree[0];
205
            continue;
223
            continue;
206
        } else {
224
        } else {
207
            void *val;
225
            void *val;
208
            int i;
226
            int i;
209
       
227
       
210
            /*
228
            /*
211
             * Now if the key is smaller than cur->key[i]
229
             * Now if the key is smaller than cur->key[i]
212
             * it can only mean that the value is in cur->subtree[i]
230
             * it can only mean that the value is in cur->subtree[i]
213
             * or it is not in the tree at all.
231
             * or it is not in the tree at all.
214
             */
232
             */
215
            for (i = 1; i < cur->keys; i++) {
233
            for (i = 1; i < cur->keys; i++) {
216
                if (key < cur->key[i]) {
234
                if (key < cur->key[i]) {
217
                    next = cur->subtree[i];
235
                    next = cur->subtree[i];
218
                    val = cur->value[i - 1];
236
                    val = cur->value[i - 1];
219
 
237
 
220
                    if (LEAF_NODE(cur))
238
                    if (LEAF_NODE(cur))
221
                        return key == cur->key[i - 1] ? val : NULL;
239
                        return key == cur->key[i - 1] ? val : NULL;
222
 
240
 
223
                    goto descend;
241
                    goto descend;
224
                }
242
                }
225
            }
243
            }
226
           
244
           
227
            /*
245
            /*
228
             * Last possibility is that the key is in the rightmost subtree.
246
             * Last possibility is that the key is in the rightmost subtree.
229
             */
247
             */
230
            next = cur->subtree[i];
248
            next = cur->subtree[i];
231
            val = cur->value[i - 1];
249
            val = cur->value[i - 1];
232
            if (LEAF_NODE(cur))
250
            if (LEAF_NODE(cur))
233
                return key == cur->key[i - 1] ? val : NULL;
251
                return key == cur->key[i - 1] ? val : NULL;
234
        }
252
        }
235
        descend:
253
        descend:
236
            ;
254
            ;
237
    }
255
    }
238
 
256
 
239
    /*
257
    /*
240
     * The key was not found in the *leaf_node and is smaller than any of its keys.
258
     * The key was not found in the *leaf_node and is smaller than any of its keys.
241
     */
259
     */
242
    return NULL;
260
    return NULL;
243
}
261
}
244
 
262
 
245
/** Get pointer to value with the smallest key within the node.
263
/** Get pointer to value with the smallest key within the node.
246
 *
264
 *
247
 * Can be only used on leaf-level nodes.
265
 * Can be only used on leaf-level nodes.
248
 *
266
 *
249
 * @param node B-tree node.
267
 * @param node B-tree node.
250
 *
268
 *
251
 * @return Pointer to value assiciated with the smallest key.
269
 * @return Pointer to value assiciated with the smallest key.
252
 */
270
 */
253
void *btree_node_min(btree_node_t *node)
271
void *btree_node_min(btree_node_t *node)
254
{
272
{
255
    ASSERT(LEAF_NODE(node));
273
    ASSERT(LEAF_NODE(node));
256
    ASSERT(node->keys);
274
    ASSERT(node->keys);
257
    return node->value[0];
275
    return node->value[0];
258
}
276
}
259
 
277
 
260
/** Get pointer to value with the biggest key within the node.
278
/** Get pointer to value with the biggest key within the node.
261
 *
279
 *
262
 * Can be only used on leaf-level nodes.
280
 * Can be only used on leaf-level nodes.
263
 *
281
 *
264
 * @param node B-tree node.
282
 * @param node B-tree node.
265
 *
283
 *
266
 * @return Pointer to value assiciated with the biggest key.
284
 * @return Pointer to value assiciated with the biggest key.
267
 */
285
 */
268
void *btree_node_max(btree_node_t *node)
286
void *btree_node_max(btree_node_t *node)
269
{
287
{
270
    ASSERT(LEAF_NODE(node));
288
    ASSERT(LEAF_NODE(node));
271
    ASSERT(node->keys);
289
    ASSERT(node->keys);
272
    return node->value[node->keys - 1];
290
    return node->value[node->keys - 1];
273
}
291
}
274
 
292
 
275
/** Initialize B-tree node.
293
/** Initialize B-tree node.
276
 *
294
 *
277
 * @param node B-tree node.
295
 * @param node B-tree node.
278
 */
296
 */
279
void node_initialize(btree_node_t *node)
297
void node_initialize(btree_node_t *node)
280
{
298
{
281
    int i;
299
    int i;
282
 
300
 
283
    node->keys = 0;
301
    node->keys = 0;
284
   
302
   
285
    /* Clean also space for the extra key. */
303
    /* Clean also space for the extra key. */
286
    for (i = 0; i < BTREE_MAX_KEYS + 1; i++) {
304
    for (i = 0; i < BTREE_MAX_KEYS + 1; i++) {
287
        node->key[i] = 0;
305
        node->key[i] = 0;
288
        node->value[i] = NULL;
306
        node->value[i] = NULL;
289
        node->subtree[i] = NULL;
307
        node->subtree[i] = NULL;
290
    }
308
    }
291
    node->subtree[i] = NULL;
309
    node->subtree[i] = NULL;
292
   
310
   
293
    node->parent = NULL;
311
    node->parent = NULL;
294
   
312
   
295
    link_initialize(&node->leaf_link);
313
    link_initialize(&node->leaf_link);
296
 
314
 
297
    link_initialize(&node->bfs_link);
315
    link_initialize(&node->bfs_link);
298
    node->depth = 0;
316
    node->depth = 0;
299
}
317
}
300
 
318
 
301
/** Insert key-value-lsubtree triplet into B-tree node.
319
/** Insert key-value-lsubtree triplet into B-tree node.
302
 *
320
 *
303
 * It is actually possible to have more keys than BTREE_MAX_KEYS.
321
 * It is actually possible to have more keys than BTREE_MAX_KEYS.
304
 * This feature is used during insert by right rotation.
322
 * This feature is used during insert by right rotation.
305
 *
323
 *
306
 * @param node B-tree node into wich the new key is to be inserted.
324
 * @param node B-tree node into wich the new key is to be inserted.
307
 * @param key The key to be inserted.
325
 * @param key The key to be inserted.
308
 * @param value Pointer to value to be inserted.
326
 * @param value Pointer to value to be inserted.
309
 * @param lsubtree Pointer to the left subtree.
327
 * @param lsubtree Pointer to the left subtree.
310
 */
328
 */
311
void node_insert_key_left(btree_node_t *node, __native key, void *value, btree_node_t *lsubtree)
329
void node_insert_key_left(btree_node_t *node, __native key, void *value, btree_node_t *lsubtree)
312
{
330
{
313
    int i;
331
    int i;
314
 
332
 
315
    for (i = 0; i < node->keys; i++) {
333
    for (i = 0; i < node->keys; i++) {
316
        if (key < node->key[i]) {
334
        if (key < node->key[i]) {
317
            int j;
335
            int j;
318
       
336
       
319
            for (j = node->keys; j > i; j--) {
337
            for (j = node->keys; j > i; j--) {
320
                node->key[j] = node->key[j - 1];
338
                node->key[j] = node->key[j - 1];
321
                node->value[j] = node->value[j - 1];
339
                node->value[j] = node->value[j - 1];
322
                node->subtree[j + 1] = node->subtree[j];
340
                node->subtree[j + 1] = node->subtree[j];
323
            }
341
            }
324
            node->subtree[j + 1] = node->subtree[j];
342
            node->subtree[j + 1] = node->subtree[j];
325
            break; 
343
            break; 
326
        }
344
        }
327
    }
345
    }
328
    node->key[i] = key;
346
    node->key[i] = key;
329
    node->value[i] = value;
347
    node->value[i] = value;
330
    node->subtree[i] = lsubtree;
348
    node->subtree[i] = lsubtree;
331
           
349
           
332
    node->keys++;
350
    node->keys++;
333
}
351
}
334
 
352
 
335
 
353
 
336
/** Insert key-value-rsubtree triplet into B-tree node.
354
/** Insert key-value-rsubtree triplet into B-tree node.
337
 *
355
 *
338
 * It is actually possible to have more keys than BTREE_MAX_KEYS.
356
 * It is actually possible to have more keys than BTREE_MAX_KEYS.
339
 * This feature is used during splitting the node when the
357
 * This feature is used during splitting the node when the
340
 * number of keys is BTREE_MAX_KEYS + 1. Insert by left rotation
358
 * number of keys is BTREE_MAX_KEYS + 1. Insert by left rotation
341
 * also makes use of this feature.
359
 * also makes use of this feature.
342
 *
360
 *
343
 * @param node B-tree node into wich the new key is to be inserted.
361
 * @param node B-tree node into wich the new key is to be inserted.
344
 * @param key The key to be inserted.
362
 * @param key The key to be inserted.
345
 * @param value Pointer to value to be inserted.
363
 * @param value Pointer to value to be inserted.
346
 * @param rsubtree Pointer to the right subtree.
364
 * @param rsubtree Pointer to the right subtree.
347
 */
365
 */
348
void node_insert_key_right(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree)
366
void node_insert_key_right(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree)
349
{
367
{
350
    int i;
368
    int i;
351
 
369
 
352
    for (i = 0; i < node->keys; i++) {
370
    for (i = 0; i < node->keys; i++) {
353
        if (key < node->key[i]) {
371
        if (key < node->key[i]) {
354
            int j;
372
            int j;
355
       
373
       
356
            for (j = node->keys; j > i; j--) {
374
            for (j = node->keys; j > i; j--) {
357
                node->key[j] = node->key[j - 1];
375
                node->key[j] = node->key[j - 1];
358
                node->value[j] = node->value[j - 1];
376
                node->value[j] = node->value[j - 1];
359
                node->subtree[j + 1] = node->subtree[j];
377
                node->subtree[j + 1] = node->subtree[j];
360
            }
378
            }
361
            break; 
379
            break; 
362
        }
380
        }
363
    }
381
    }
364
    node->key[i] = key;
382
    node->key[i] = key;
365
    node->value[i] = value;
383
    node->value[i] = value;
366
    node->subtree[i + 1] = rsubtree;
384
    node->subtree[i + 1] = rsubtree;
367
           
385
           
368
    node->keys++;
386
    node->keys++;
369
}
387
}
370
 
388
 
371
/** Split full B-tree node and insert new key-value-right-subtree triplet.
389
/** Split full B-tree node and insert new key-value-right-subtree triplet.
372
 *
390
 *
373
 * This function will split a node and return pointer to a newly created
391
 * This function will split a node and return pointer to a newly created
374
 * node containing keys greater than or equal to the greater of medians
392
 * node containing keys greater than or equal to the greater of medians
375
 * (or median) of the old keys and the newly added key. It will also write
393
 * (or median) of the old keys and the newly added key. It will also write
376
 * the median key to a memory address supplied by the caller.
394
 * the median key to a memory address supplied by the caller.
377
 *
395
 *
378
 * If the node being split is an index node, the median will not be
396
 * If the node being split is an index node, the median will not be
379
 * included in the new node. If the node is a leaf node,
397
 * included in the new node. If the node is a leaf node,
380
 * the median will be copied there.
398
 * the median will be copied there.
381
 *
399
 *
382
 * @param node B-tree node wich is going to be split.
400
 * @param node B-tree node wich is going to be split.
383
 * @param key The key to be inserted.
401
 * @param key The key to be inserted.
384
 * @param value Pointer to the value to be inserted.
402
 * @param value Pointer to the value to be inserted.
385
 * @param rsubtree Pointer to the right subtree of the key being added.
403
 * @param rsubtree Pointer to the right subtree of the key being added.
386
 * @param median Address in memory, where the median key will be stored.
404
 * @param median Address in memory, where the median key will be stored.
387
 *
405
 *
388
 * @return Newly created right sibling of node.
406
 * @return Newly created right sibling of node.
389
 */
407
 */
390
btree_node_t *node_split(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree, __native *median)
408
btree_node_t *node_split(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree, __native *median)
391
{
409
{
392
    btree_node_t *rnode;
410
    btree_node_t *rnode;
393
    int i, j;
411
    int i, j;
394
 
412
 
395
    ASSERT(median);
413
    ASSERT(median);
396
    ASSERT(node->keys == BTREE_MAX_KEYS);
414
    ASSERT(node->keys == BTREE_MAX_KEYS);
397
 
415
 
398
    /*
416
    /*
399
     * Use the extra space to store the extra node.
417
     * Use the extra space to store the extra node.
400
     */
418
     */
401
    node_insert_key_right(node, key, value, rsubtree);
419
    node_insert_key_right(node, key, value, rsubtree);
402
 
420
 
403
    /*
421
    /*
404
     * Compute median of keys.
422
     * Compute median of keys.
405
     */
423
     */
406
    *median = MEDIAN_HIGH(node);
424
    *median = MEDIAN_HIGH(node);
407
       
425
       
408
    /*
426
    /*
409
     * Allocate and initialize new right sibling.
427
     * Allocate and initialize new right sibling.
410
     */
428
     */
411
    rnode = (btree_node_t *) malloc(sizeof(btree_node_t), 0);
429
    rnode = (btree_node_t *) malloc(sizeof(btree_node_t), 0);
412
    node_initialize(rnode);
430
    node_initialize(rnode);
413
    rnode->parent = node->parent;
431
    rnode->parent = node->parent;
414
    rnode->depth = node->depth;
432
    rnode->depth = node->depth;
415
   
433
   
416
    /*
434
    /*
417
     * Copy big keys, values and subtree pointers to the new right sibling.
435
     * Copy big keys, values and subtree pointers to the new right sibling.
418
     * If this is an index node, do not copy the median.
436
     * If this is an index node, do not copy the median.
419
     */
437
     */
420
    i = (int) INDEX_NODE(node);
438
    i = (int) INDEX_NODE(node);
421
    for (i += MEDIAN_HIGH_INDEX(node), j = 0; i < node->keys; i++, j++) {
439
    for (i += MEDIAN_HIGH_INDEX(node), j = 0; i < node->keys; i++, j++) {
422
        rnode->key[j] = node->key[i];
440
        rnode->key[j] = node->key[i];
423
        rnode->value[j] = node->value[i];
441
        rnode->value[j] = node->value[i];
424
        rnode->subtree[j] = node->subtree[i];
442
        rnode->subtree[j] = node->subtree[i];
425
       
443
       
426
        /*
444
        /*
427
         * Fix parent links in subtrees.
445
         * Fix parent links in subtrees.
428
         */
446
         */
429
        if (rnode->subtree[j])
447
        if (rnode->subtree[j])
430
            rnode->subtree[j]->parent = rnode;
448
            rnode->subtree[j]->parent = rnode;
431
           
449
           
432
    }
450
    }
433
    rnode->subtree[j] = node->subtree[i];
451
    rnode->subtree[j] = node->subtree[i];
434
    if (rnode->subtree[j])
452
    if (rnode->subtree[j])
435
        rnode->subtree[j]->parent = rnode;
453
        rnode->subtree[j]->parent = rnode;
436
 
454
 
437
    rnode->keys = j;    /* Set number of keys of the new node. */
455
    rnode->keys = j;    /* Set number of keys of the new node. */
438
    node->keys /= 2;    /* Shrink the old node. */
456
    node->keys /= 2;    /* Shrink the old node. */
439
       
457
       
440
    return rnode;
458
    return rnode;
441
}
459
}
442
 
460
 
443
/** Remove key and its left subtree pointer from B-tree node.
461
/** Remove key and its left subtree pointer from B-tree node.
444
 *
462
 *
445
 * Remove the key and eliminate gaps in node->key array.
463
 * Remove the key and eliminate gaps in node->key array.
446
 * Note that the value pointer and the left subtree pointer
464
 * Note that the value pointer and the left subtree pointer
447
 * is removed from the node as well.
465
 * is removed from the node as well.
448
 *
466
 *
449
 * @param node B-tree node.
467
 * @param node B-tree node.
450
 * @param key Key to be removed.
468
 * @param key Key to be removed.
451
 */
469
 */
452
void node_remove_key_left(btree_node_t *node, __native key)
470
void node_remove_key_left(btree_node_t *node, __native key)
453
{
471
{
454
    int i, j;
472
    int i, j;
455
   
473
   
456
    for (i = 0; i < node->keys; i++) {
474
    for (i = 0; i < node->keys; i++) {
457
        if (key == node->key[i]) {
475
        if (key == node->key[i]) {
458
            for (j = i + 1; j < node->keys; j++) {
476
            for (j = i + 1; j < node->keys; j++) {
459
                node->key[j - 1] = node->key[j];
477
                node->key[j - 1] = node->key[j];
460
                node->value[j - 1] = node->value[j];
478
                node->value[j - 1] = node->value[j];
461
                node->subtree[j - 1] = node->subtree[j];
479
                node->subtree[j - 1] = node->subtree[j];
462
            }
480
            }
463
            node->subtree[j - 1] = node->subtree[j];
481
            node->subtree[j - 1] = node->subtree[j];
464
            node->keys--;
482
            node->keys--;
465
            return;
483
            return;
466
        }
484
        }
467
    }
485
    }
468
    panic("node %P does not contain key %d\n", node, key);
486
    panic("node %P does not contain key %d\n", node, key);
469
}
487
}
470
 
488
 
471
/** Remove key and its right subtree pointer from B-tree node.
489
/** Remove key and its right subtree pointer from B-tree node.
472
 *
490
 *
473
 * Remove the key and eliminate gaps in node->key array.
491
 * Remove the key and eliminate gaps in node->key array.
474
 * Note that the value pointer and the right subtree pointer
492
 * Note that the value pointer and the right subtree pointer
475
 * is removed from the node as well.
493
 * is removed from the node as well.
476
 *
494
 *
477
 * @param node B-tree node.
495
 * @param node B-tree node.
478
 * @param key Key to be removed.
496
 * @param key Key to be removed.
479
 */
497
 */
480
void node_remove_key_right(btree_node_t *node, __native key)
498
void node_remove_key_right(btree_node_t *node, __native key)
481
{
499
{
482
    int i, j;
500
    int i, j;
483
   
501
   
484
    for (i = 0; i < node->keys; i++) {
502
    for (i = 0; i < node->keys; i++) {
485
        if (key == node->key[i]) {
503
        if (key == node->key[i]) {
486
            for (j = i + 1; j < node->keys; j++) {
504
            for (j = i + 1; j < node->keys; j++) {
487
                node->key[j - 1] = node->key[j];
505
                node->key[j - 1] = node->key[j];
488
                node->value[j - 1] = node->value[j];
506
                node->value[j - 1] = node->value[j];
489
                node->subtree[j] = node->subtree[j + 1];
507
                node->subtree[j] = node->subtree[j + 1];
490
            }
508
            }
491
            node->keys--;
509
            node->keys--;
492
            return;
510
            return;
493
        }
511
        }
494
    }
512
    }
495
    panic("node %P does not contain key %d\n", node, key);
513
    panic("node %P does not contain key %d\n", node, key);
496
}
514
}
497
 
515
 
498
/** Find key by its left or right subtree.
516
/** Find key by its left or right subtree.
499
 *
517
 *
500
 * @param node B-tree node.
518
 * @param node B-tree node.
501
 * @param subtree Left or right subtree of a key found in node.
519
 * @param subtree Left or right subtree of a key found in node.
502
 * @param right If true, subtree is a right subtree. If false, subtree is a left subtree.
520
 * @param right If true, subtree is a right subtree. If false, subtree is a left subtree.
503
 *
521
 *
504
 * @return Index of the key associated with the subtree.
522
 * @return Index of the key associated with the subtree.
505
 */
523
 */
506
index_t find_key_by_subtree(btree_node_t *node, btree_node_t *subtree, bool right)
524
index_t find_key_by_subtree(btree_node_t *node, btree_node_t *subtree, bool right)
507
{
525
{
508
    int i;
526
    int i;
509
   
527
   
510
    for (i = 0; i < node->keys + 1; i++) {
528
    for (i = 0; i < node->keys + 1; i++) {
511
        if (subtree == node->subtree[i])
529
        if (subtree == node->subtree[i])
512
            return i - (int) (right != false);
530
            return i - (int) (right != false);
513
    }
531
    }
514
    panic("node %P does not contain subtree %P\n", node, subtree);
532
    panic("node %P does not contain subtree %P\n", node, subtree);
515
}
533
}
516
 
534
 
517
/** Insert key-value-rsubtree triplet and rotate the node to the left, if this operation can be done.
535
/** Insert key-value-rsubtree triplet and rotate the node to the left, if this operation can be done.
518
 *
536
 *
519
 * Left sibling of the node (if it exists) is checked for free space.
537
 * Left sibling of the node (if it exists) is checked for free space.
520
 * If there is free space, the key is inserted and the smallest key of
538
 * If there is free space, the key is inserted and the smallest key of
521
 * the node is moved there. The index node which is the parent of both
539
 * the node is moved there. The index node which is the parent of both
522
 * nodes is fixed.
540
 * nodes is fixed.
523
 *
541
 *
524
 * @param node B-tree node.
542
 * @param node B-tree node.
525
 * @param inskey Key to be inserted.
543
 * @param inskey Key to be inserted.
526
 * @param insvalue Value to be inserted.
544
 * @param insvalue Value to be inserted.
527
 * @param rsubtree Right subtree of inskey.
545
 * @param rsubtree Right subtree of inskey.
528
 *
546
 *
529
 * @return True if the rotation was performed, false otherwise.
547
 * @return True if the rotation was performed, false otherwise.
530
 */
548
 */
531
bool try_insert_by_left_rotation(btree_node_t *node, __native inskey, void *insvalue, btree_node_t *rsubtree)
549
bool try_insert_by_left_rotation(btree_node_t *node, __native inskey, void *insvalue, btree_node_t *rsubtree)
532
{
550
{
533
    index_t idx;
551
    index_t idx;
534
    btree_node_t *lnode;
552
    btree_node_t *lnode;
535
 
553
 
536
    /*
554
    /*
537
     * If this is root node, the rotation can not be done.
555
     * If this is root node, the rotation can not be done.
538
     */
556
     */
539
    if (ROOT_NODE(node))
557
    if (ROOT_NODE(node))
540
        return false;
558
        return false;
541
   
559
   
542
    idx = find_key_by_subtree(node->parent, node, true);
560
    idx = find_key_by_subtree(node->parent, node, true);
543
    if ((int) idx == -1) {
561
    if ((int) idx == -1) {
544
        /*
562
        /*
545
         * If this node is the leftmost subtree of its parent,
563
         * If this node is the leftmost subtree of its parent,
546
         * the rotation can not be done.
564
         * the rotation can not be done.
547
         */
565
         */
548
        return false;
566
        return false;
549
    }
567
    }
550
       
568
       
551
    lnode = node->parent->subtree[idx];
569
    lnode = node->parent->subtree[idx];
552
 
570
 
553
    if (lnode->keys < BTREE_MAX_KEYS) {
571
    if (lnode->keys < BTREE_MAX_KEYS) {
554
        __native key;
572
        __native key;
555
 
573
 
556
        /*
574
        /*
557
         * The rotaion can be done. The left sibling has free space.
575
         * The rotaion can be done. The left sibling has free space.
558
         */
576
         */
559
 
577
 
560
        node_insert_key_right(node, inskey, insvalue, rsubtree);
578
        node_insert_key_right(node, inskey, insvalue, rsubtree);
561
        key = node->key[0];
579
        key = node->key[0];
562
       
580
       
563
        if (LEAF_NODE(node)) {
581
        if (LEAF_NODE(node)) {
564
            void *value;
582
            void *value;
565
 
583
 
566
            value = node->value[0];
584
            value = node->value[0];
567
            node_remove_key_left(node, key);
585
            node_remove_key_left(node, key);
568
            node_insert_key_right(lnode, key, value, NULL);
586
            node_insert_key_right(lnode, key, value, NULL);
569
            node->parent->key[idx] = node->key[0];
587
            node->parent->key[idx] = node->key[0];
570
        } else {
588
        } else {
571
            btree_node_t *lsubtree;
589
            btree_node_t *lsubtree;
572
 
590
 
573
            lsubtree = node->subtree[0];
591
            lsubtree = node->subtree[0];
574
            node_remove_key_left(node, key);
592
            node_remove_key_left(node, key);
575
            node_insert_key_right(lnode, node->parent->key[idx], NULL, lsubtree);
593
            node_insert_key_right(lnode, node->parent->key[idx], NULL, lsubtree);
576
            node->parent->key[idx] = key;
594
            node->parent->key[idx] = key;
577
 
595
 
578
            /* Fix parent link of the reconnected left subtree. */
596
            /* Fix parent link of the reconnected left subtree. */
579
            lsubtree->parent = lnode;
597
            lsubtree->parent = lnode;
580
        }
598
        }
581
        return true;
599
        return true;
582
    }
600
    }
583
 
601
 
584
    return false;
602
    return false;
585
}
603
}
586
 
604
 
587
/** Insert key-value-rsubtree triplet and rotate the node to the right, if this operation can be done.
605
/** Insert key-value-rsubtree triplet and rotate the node to the right, if this operation can be done.
588
 *
606
 *
589
 * Right sibling of the node (if it exists) is checked for free space.
607
 * Right sibling of the node (if it exists) is checked for free space.
590
 * If there is free space, the key is inserted and the biggest key of
608
 * If there is free space, the key is inserted and the biggest key of
591
 * the node is moved there. The index node which is the parent of both
609
 * the node is moved there. The index node which is the parent of both
592
 * nodes is fixed.
610
 * nodes is fixed.
593
 *
611
 *
594
 * @param node B-tree node.
612
 * @param node B-tree node.
595
 * @param inskey Key to be inserted.
613
 * @param inskey Key to be inserted.
596
 * @param insvalue Value to be inserted.
614
 * @param insvalue Value to be inserted.
597
 * @param rsubtree Right subtree of inskey.
615
 * @param rsubtree Right subtree of inskey.
598
 *
616
 *
599
 * @return True if the rotation was performed, false otherwise.
617
 * @return True if the rotation was performed, false otherwise.
600
 */
618
 */
601
bool try_insert_by_right_rotation(btree_node_t *node, __native inskey, void *insvalue, btree_node_t *rsubtree)
619
bool try_insert_by_right_rotation(btree_node_t *node, __native inskey, void *insvalue, btree_node_t *rsubtree)
602
{
620
{
603
    index_t idx;
621
    index_t idx;
604
    btree_node_t *rnode;
622
    btree_node_t *rnode;
605
 
623
 
606
    /*
624
    /*
607
     * If this is root node, the rotation can not be done.
625
     * If this is root node, the rotation can not be done.
608
     */
626
     */
609
    if (ROOT_NODE(node))
627
    if (ROOT_NODE(node))
610
        return false;
628
        return false;
611
   
629
   
612
    idx = find_key_by_subtree(node->parent, node, false);
630
    idx = find_key_by_subtree(node->parent, node, false);
613
    if (idx == node->parent->keys) {
631
    if (idx == node->parent->keys) {
614
        /*
632
        /*
615
         * If this node is the rightmost subtree of its parent,
633
         * If this node is the rightmost subtree of its parent,
616
         * the rotation can not be done.
634
         * the rotation can not be done.
617
         */
635
         */
618
        return false;
636
        return false;
619
    }
637
    }
620
       
638
       
621
    rnode = node->parent->subtree[idx + 1];
639
    rnode = node->parent->subtree[idx + 1];
622
 
640
 
623
    if (rnode->keys < BTREE_MAX_KEYS) {
641
    if (rnode->keys < BTREE_MAX_KEYS) {
624
        __native key;
642
        __native key;
625
 
643
 
626
        /*
644
        /*
627
         * The rotaion can be done. The right sibling has free space.
645
         * The rotaion can be done. The right sibling has free space.
628
         */
646
         */
629
 
647
 
630
        node_insert_key_right(node, inskey, insvalue, rsubtree);
648
        node_insert_key_right(node, inskey, insvalue, rsubtree);
631
        key = node->key[node->keys - 1];
649
        key = node->key[node->keys - 1];
632
       
650
       
633
        if (LEAF_NODE(node)) {
651
        if (LEAF_NODE(node)) {
634
            void *value;
652
            void *value;
635
 
653
 
636
            value = node->value[node->keys - 1];
654
            value = node->value[node->keys - 1];
637
            node_remove_key_right(node, key);
655
            node_remove_key_right(node, key);
638
            node_insert_key_left(rnode, key, value, NULL);
656
            node_insert_key_left(rnode, key, value, NULL);
639
            node->parent->key[idx] = key;
657
            node->parent->key[idx] = key;
640
        } else {
658
        } else {
641
            btree_node_t *rsubt;
659
            btree_node_t *rsubt;
642
 
660
 
643
            rsubt = node->subtree[node->keys];
661
            rsubt = node->subtree[node->keys];
644
            node_remove_key_right(node, key);
662
            node_remove_key_right(node, key);
645
            node_insert_key_left(rnode, node->parent->key[idx], NULL, rsubt);
663
            node_insert_key_left(rnode, node->parent->key[idx], NULL, rsubt);
646
            node->parent->key[idx] = key;
664
            node->parent->key[idx] = key;
647
 
665
 
648
            /* Fix parent link of the reconnected right subtree. */
666
            /* Fix parent link of the reconnected right subtree. */
649
            rsubt->parent = rnode;
667
            rsubt->parent = rnode;
650
        }
668
        }
651
        return true;
669
        return true;
652
    }
670
    }
653
 
671
 
654
    return false;
672
    return false;
655
}
673
}
656
 
674
 
657
/** Print B-tree.
675
/** Print B-tree.
658
 *
676
 *
659
 * @param t Print out B-tree.
677
 * @param t Print out B-tree.
660
 */
678
 */
661
void btree_print(btree_t *t)
679
void btree_print(btree_t *t)
662
{
680
{
663
    int i, depth = t->root->depth;
681
    int i, depth = t->root->depth;
664
    link_t head;
682
    link_t head;
665
   
683
   
666
    list_initialize(&head);
684
    list_initialize(&head);
667
    list_append(&t->root->bfs_link, &head);
685
    list_append(&t->root->bfs_link, &head);
668
 
686
 
669
    /*
687
    /*
670
     * Use BFS search to print out the tree.
688
     * Use BFS search to print out the tree.
671
     * Levels are distinguished from one another by node->depth.
689
     * Levels are distinguished from one another by node->depth.
672
     */
690
     */
673
    while (!list_empty(&head)) {
691
    while (!list_empty(&head)) {
674
        link_t *hlp;
692
        link_t *hlp;
675
        btree_node_t *node;
693
        btree_node_t *node;
676
       
694
       
677
        hlp = head.next;
695
        hlp = head.next;
678
        ASSERT(hlp != &head);
696
        ASSERT(hlp != &head);
679
        node = list_get_instance(hlp, btree_node_t, bfs_link);
697
        node = list_get_instance(hlp, btree_node_t, bfs_link);
680
        list_remove(hlp);
698
        list_remove(hlp);
681
       
699
       
682
        ASSERT(node);
700
        ASSERT(node);
683
       
701
       
684
        if (node->depth != depth) {
702
        if (node->depth != depth) {
685
            printf("\n");
703
            printf("\n");
686
            depth = node->depth;
704
            depth = node->depth;
687
        }
705
        }
688
 
706
 
689
        printf("(");
707
        printf("(");
690
        for (i = 0; i < node->keys; i++) {
708
        for (i = 0; i < node->keys; i++) {
691
            printf("%d,", node->key[i]);
709
            printf("%d,", node->key[i]);
692
            if (node->depth && node->subtree[i]) {
710
            if (node->depth && node->subtree[i]) {
693
                list_append(&node->subtree[i]->bfs_link, &head);
711
                list_append(&node->subtree[i]->bfs_link, &head);
694
            }
712
            }
695
        }
713
        }
696
        if (node->depth && node->subtree[i]) {
714
        if (node->depth && node->subtree[i]) {
697
            list_append(&node->subtree[i]->bfs_link, &head);
715
            list_append(&node->subtree[i]->bfs_link, &head);
698
        }
716
        }
699
        printf(")");
717
        printf(")");
700
    }
718
    }
701
    printf("\n");
719
    printf("\n");
702
}
720
}
703
 
721