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