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