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