Rev 1121 | Rev 1136 | Go to most recent revision | Only display areas with differences | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed
Rev 1121 | Rev 1134 | ||
---|---|---|---|
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 |
36 | * Some of the functions below take pointer to the right-hand |
37 | * side subtree pointer as parameter. Note that this is sufficient |
37 | * side subtree pointer as parameter. Note that this is sufficient |
38 | * because: |
38 | * because: |
39 | * - New root node is passed the left-hand side subtree pointer |
39 | * - New root node is passed the left-hand side subtree pointer |
40 | * directly. |
40 | * directly. |
41 | * - node_split() always creates the right sibling and preserves |
41 | * - node_split() always creates the right sibling and preserves |
42 | * the original node (which becomes the left sibling). |
42 | * the original node (which becomes the left sibling). |
43 | * There is always pointer to the left-hand side subtree |
43 | * There is always pointer to the left-hand side subtree |
44 | * (i.e. left sibling) in the parent node. |
44 | * (i.e. left sibling) in the parent node. |
- | 45 | * |
|
- | 46 | * Be carefull when using these trees. They need to allocate |
|
- | 47 | * and deallocate memory for their index nodes and as such |
|
- | 48 | * can sleep. |
|
45 | */ |
49 | */ |
46 | 50 | ||
47 | #include <adt/btree.h> |
51 | #include <adt/btree.h> |
48 | #include <adt/list.h> |
52 | #include <adt/list.h> |
49 | #include <mm/slab.h> |
53 | #include <mm/slab.h> |
50 | #include <debug.h> |
54 | #include <debug.h> |
51 | #include <panic.h> |
55 | #include <panic.h> |
52 | #include <typedefs.h> |
56 | #include <typedefs.h> |
53 | #include <print.h> |
57 | #include <print.h> |
54 | 58 | ||
55 | static void _btree_insert(btree_t *t, __native key, void *value, btree_node_t *rsubtree, btree_node_t *node); |
59 | static void _btree_insert(btree_t *t, __native key, void *value, btree_node_t *rsubtree, btree_node_t *node); |
56 | static void node_initialize(btree_node_t *node); |
60 | static void node_initialize(btree_node_t *node); |
57 | static void node_insert_key(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree); |
61 | static void node_insert_key(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree); |
- | 62 | void node_remove_key(btree_node_t *node, __native key); |
|
58 | static btree_node_t *node_split(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree, __native *median); |
63 | static btree_node_t *node_split(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree, __native *median); |
59 | 64 | ||
60 | #define ROOT_NODE(n) (!(n)->parent) |
65 | #define ROOT_NODE(n) (!(n)->parent) |
61 | #define INDEX_NODE(n) ((n)->subtree[0] != NULL) |
66 | #define INDEX_NODE(n) ((n)->subtree[0] != NULL) |
62 | #define LEAF_NODE(n) ((n)->subtree[0] == NULL) |
67 | #define LEAF_NODE(n) ((n)->subtree[0] == NULL) |
63 | 68 | ||
64 | #define MEDIAN_LOW_INDEX(n) (((n)->keys-1)/2) |
69 | #define MEDIAN_LOW_INDEX(n) (((n)->keys-1)/2) |
65 | #define MEDIAN_HIGH_INDEX(n) ((n)->keys/2) |
70 | #define MEDIAN_HIGH_INDEX(n) ((n)->keys/2) |
66 | #define MEDIAN_LOW(n) ((n)->key[MEDIAN_LOW_INDEX((n))]); |
71 | #define MEDIAN_LOW(n) ((n)->key[MEDIAN_LOW_INDEX((n))]); |
67 | #define MEDIAN_HIGH(n) ((n)->key[MEDIAN_HIGH_INDEX((n))]); |
72 | #define MEDIAN_HIGH(n) ((n)->key[MEDIAN_HIGH_INDEX((n))]); |
68 | 73 | ||
69 | /** Create empty B-tree. |
74 | /** Create empty B-tree. |
70 | * |
75 | * |
71 | * @param t B-tree. |
76 | * @param t B-tree. |
72 | */ |
77 | */ |
73 | void btree_create(btree_t *t) |
78 | void btree_create(btree_t *t) |
74 | { |
79 | { |
75 | list_initialize(&t->leaf_head); |
80 | list_initialize(&t->leaf_head); |
76 | t->root = (btree_node_t *) malloc(sizeof(btree_node_t), 0); |
81 | t->root = (btree_node_t *) malloc(sizeof(btree_node_t), 0); |
77 | node_initialize(t->root); |
82 | node_initialize(t->root); |
78 | list_append(&t->root->leaf_link, &t->leaf_head); |
83 | list_append(&t->root->leaf_link, &t->leaf_head); |
79 | } |
84 | } |
80 | 85 | ||
81 | /** Destroy empty B-tree. */ |
86 | /** Destroy empty B-tree. */ |
82 | void btree_destroy(btree_t *t) |
87 | void btree_destroy(btree_t *t) |
83 | { |
88 | { |
84 | ASSERT(!t->root->keys); |
89 | ASSERT(!t->root->keys); |
85 | free(t->root); |
90 | free(t->root); |
86 | } |
91 | } |
87 | 92 | ||
88 | /** Insert key-value pair into B-tree. |
93 | /** Insert key-value pair into B-tree. |
89 | * |
94 | * |
90 | * @param t B-tree. |
95 | * @param t B-tree. |
91 | * @param key Key to be inserted. |
96 | * @param key Key to be inserted. |
92 | * @param value Value to be inserted. |
97 | * @param value Value to be inserted. |
93 | * @param leaf_node Leaf node where the insertion should begin. |
98 | * @param leaf_node Leaf node where the insertion should begin. |
94 | */ |
99 | */ |
95 | void btree_insert(btree_t *t, __native key, void *value, btree_node_t *leaf_node) |
100 | void btree_insert(btree_t *t, __native key, void *value, btree_node_t *leaf_node) |
96 | { |
101 | { |
97 | btree_node_t *lnode; |
102 | btree_node_t *lnode; |
98 | 103 | ||
99 | ASSERT(value); |
104 | ASSERT(value); |
100 | 105 | ||
101 | lnode = leaf_node; |
106 | lnode = leaf_node; |
102 | if (!lnode) { |
107 | if (!lnode) { |
103 | if (btree_search(t, key, &lnode)) { |
108 | if (btree_search(t, key, &lnode)) { |
104 | panic("B-tree %P already contains key %d\n", t, key); |
109 | panic("B-tree %P already contains key %d\n", t, key); |
105 | } |
110 | } |
106 | } |
111 | } |
107 | 112 | ||
108 | _btree_insert(t, key, value, NULL, lnode); |
113 | _btree_insert(t, key, value, NULL, lnode); |
109 | } |
114 | } |
110 | 115 | ||
111 | /** Recursively insert into B-tree. |
116 | /** Recursively insert into B-tree. |
112 | * |
117 | * |
113 | * @param t B-tree. |
118 | * @param t B-tree. |
114 | * @param key Key to be inserted. |
119 | * @param key Key to be inserted. |
115 | * @param value Value to be inserted. |
120 | * @param value Value to be inserted. |
116 | * @param rsubtree Right subtree of the inserted key. |
121 | * @param rsubtree Right subtree of the inserted key. |
117 | * @param node Start inserting into this node. |
122 | * @param node Start inserting into this node. |
118 | */ |
123 | */ |
119 | void _btree_insert(btree_t *t, __native key, void *value, btree_node_t *rsubtree, btree_node_t *node) |
124 | void _btree_insert(btree_t *t, __native key, void *value, btree_node_t *rsubtree, btree_node_t *node) |
120 | { |
125 | { |
121 | if (node->keys < BTREE_MAX_KEYS) { |
126 | if (node->keys < BTREE_MAX_KEYS) { |
122 | /* |
127 | /* |
123 | * Node conatins enough space, the key can be stored immediately. |
128 | * Node conatins enough space, the key can be stored immediately. |
124 | */ |
129 | */ |
125 | node_insert_key(node, key, value, rsubtree); |
130 | node_insert_key(node, key, value, rsubtree); |
126 | } else { |
131 | } else { |
127 | btree_node_t *rnode; |
132 | btree_node_t *rnode; |
128 | __native median; |
133 | __native median; |
129 | 134 | ||
130 | /* |
135 | /* |
131 | * Node is full. |
136 | * Node is full. |
132 | * Split it and insert the smallest key from the node containing |
137 | * Split it and insert the smallest key from the node containing |
133 | * bigger keys (i.e. the original node) into its parent. |
138 | * bigger keys (i.e. the original node) into its parent. |
134 | */ |
139 | */ |
135 | 140 | ||
136 | rnode = node_split(node, key, value, rsubtree, &median); |
141 | rnode = node_split(node, key, value, rsubtree, &median); |
137 | 142 | ||
138 | if (LEAF_NODE(node)) { |
143 | if (LEAF_NODE(node)) { |
139 | list_append(&rnode->leaf_link, &node->leaf_link); |
144 | list_append(&rnode->leaf_link, &node->leaf_link); |
140 | } |
145 | } |
141 | 146 | ||
142 | if (ROOT_NODE(node)) { |
147 | if (ROOT_NODE(node)) { |
143 | /* |
148 | /* |
144 | * We split the root node. Create new root. |
149 | * We split the root node. Create new root. |
145 | */ |
150 | */ |
146 | 151 | ||
147 | t->root = (btree_node_t *) malloc(sizeof(btree_node_t), 0); |
152 | t->root = (btree_node_t *) malloc(sizeof(btree_node_t), 0); |
148 | node->parent = t->root; |
153 | node->parent = t->root; |
149 | rnode->parent = t->root; |
154 | rnode->parent = t->root; |
150 | node_initialize(t->root); |
155 | node_initialize(t->root); |
151 | 156 | ||
152 | /* |
157 | /* |
153 | * Left-hand side subtree will be the old root (i.e. node). |
158 | * Left-hand side subtree will be the old root (i.e. node). |
154 | * Right-hand side subtree will be rnode. |
159 | * Right-hand side subtree will be rnode. |
155 | */ |
160 | */ |
156 | t->root->subtree[0] = node; |
161 | t->root->subtree[0] = node; |
157 | 162 | ||
158 | t->root->depth = node->depth + 1; |
163 | t->root->depth = node->depth + 1; |
159 | } |
164 | } |
160 | _btree_insert(t, median, NULL, rnode, node->parent); |
165 | _btree_insert(t, median, NULL, rnode, node->parent); |
161 | } |
166 | } |
162 | 167 | ||
163 | } |
168 | } |
164 | 169 | ||
165 | /* TODO */ |
170 | /* TODO */ |
166 | void btree_remove(btree_t *t, __native key) |
171 | void btree_remove(btree_t *t, __native key) |
167 | { |
172 | { |
168 | } |
173 | } |
169 | 174 | ||
170 | /** Search key in a B-tree. |
175 | /** Search key in a B-tree. |
171 | * |
176 | * |
172 | * @param t B-tree. |
177 | * @param t B-tree. |
173 | * @param key Key to be searched. |
178 | * @param key Key to be searched. |
174 | * @param leaf_node Address where to put pointer to visited leaf node. |
179 | * @param leaf_node Address where to put pointer to visited leaf node. |
175 | * |
180 | * |
176 | * @return Pointer to value or NULL if there is no such key. |
181 | * @return Pointer to value or NULL if there is no such key. |
177 | */ |
182 | */ |
178 | void *btree_search(btree_t *t, __native key, btree_node_t **leaf_node) |
183 | void *btree_search(btree_t *t, __native key, btree_node_t **leaf_node) |
179 | { |
184 | { |
180 | btree_node_t *cur, *next; |
185 | btree_node_t *cur, *next; |
181 | void *val = NULL; |
- | |
182 | 186 | ||
183 | /* |
187 | /* |
184 | * Iteratively descend to the leaf that can contain searched key. |
188 | * Iteratively descend to the leaf that can contain the searched key. |
185 | */ |
189 | */ |
186 | for (cur = t->root; cur; cur = next) { |
190 | for (cur = t->root; cur; cur = next) { |
187 | int i; |
- | |
188 | 191 | ||
189 | /* Last iteration will set this with proper leaf node address. */ |
192 | /* Last iteration will set this with proper leaf node address. */ |
190 | *leaf_node = cur; |
193 | *leaf_node = cur; |
- | 194 | ||
- | 195 | /* |
|
191 | for (i = 0; i < cur->keys; i++) { |
196 | * The key can be in the leftmost subtree. |
- | 197 | * Test it separately. |
|
- | 198 | */ |
|
192 | if (key <= cur->key[i]) { |
199 | if (key < cur->key[0]) { |
193 | val = cur->value[i]; |
200 | next = cur->subtree[0]; |
194 | next = cur->subtree[i]; |
201 | continue; |
- | 202 | } else { |
|
- | 203 | void *val; |
|
- | 204 | int i; |
|
195 | 205 | ||
196 | /* |
206 | /* |
197 | * Check if there is anywhere to descend. |
207 | * Now if the key is smaller than cur->key[i] |
- | 208 | * it can only mean that the value is in cur->subtree[i] |
|
- | 209 | * or it is not in the tree at all. |
|
198 | */ |
210 | */ |
- | 211 | for (i = 1; i < cur->keys; i++) { |
|
199 | if (!next) { |
212 | if (key < cur->key[i]) { |
200 | /* |
213 | next = cur->subtree[i]; |
201 | * Leaf-level. |
214 | val = cur->value[i - 1]; |
- | 215 | ||
202 | */ |
216 | if (LEAF_NODE(cur)) |
203 | return (key == cur->key[i]) ? val : NULL; |
217 | return key == cur->key[i - 1] ? val : NULL; |
204 | } |
218 | |
205 | goto descend; |
219 | goto descend; |
- | 220 | } |
|
206 | } |
221 | } |
- | 222 | ||
- | 223 | /* |
|
- | 224 | * Last possibility is that the key is in the rightmost subtree. |
|
- | 225 | */ |
|
- | 226 | next = cur->subtree[i]; |
|
- | 227 | val = cur->value[i - 1]; |
|
- | 228 | if (LEAF_NODE(cur)) |
|
- | 229 | return key == cur->key[i - 1] ? val : NULL; |
|
207 | } |
230 | } |
208 | next = cur->subtree[i]; |
- | |
209 | descend: |
231 | descend: |
210 | ; |
232 | ; |
211 | } |
233 | } |
212 | 234 | ||
213 | /* |
235 | /* |
214 | * The key was not found in the *leaf_node and is greater than any of its keys. |
236 | * The key was not found in the *leaf_node and is smaller than any of its keys. |
215 | */ |
237 | */ |
216 | return NULL; |
238 | return NULL; |
217 | } |
239 | } |
218 | 240 | ||
219 | /** Get pointer to value with the smallest key within the node. |
241 | /** Get pointer to value with the smallest key within the node. |
220 | * |
242 | * |
221 | * Can be only used on leaf-level nodes. |
243 | * Can be only used on leaf-level nodes. |
222 | * |
244 | * |
223 | * @param node B-tree node. |
245 | * @param node B-tree node. |
224 | * |
246 | * |
225 | * @return Pointer to value assiciated with the smallest key. |
247 | * @return Pointer to value assiciated with the smallest key. |
226 | */ |
248 | */ |
227 | void *btree_node_min(btree_node_t *node) |
249 | void *btree_node_min(btree_node_t *node) |
228 | { |
250 | { |
229 | ASSERT(LEAF_NODE(node)); |
251 | ASSERT(LEAF_NODE(node)); |
230 | ASSERT(node->keys); |
252 | ASSERT(node->keys); |
231 | return node->value[0]; |
253 | return node->value[0]; |
232 | } |
254 | } |
233 | 255 | ||
234 | /** Get pointer to value with the biggest key within the node. |
256 | /** Get pointer to value with the biggest key within the node. |
235 | * |
257 | * |
236 | * Can be only used on leaf-level nodes. |
258 | * Can be only used on leaf-level nodes. |
237 | * |
259 | * |
238 | * @param node B-tree node. |
260 | * @param node B-tree node. |
239 | * |
261 | * |
240 | * @return Pointer to value assiciated with the biggest key. |
262 | * @return Pointer to value assiciated with the biggest key. |
241 | */ |
263 | */ |
242 | void *btree_node_max(btree_node_t *node) |
264 | void *btree_node_max(btree_node_t *node) |
243 | { |
265 | { |
244 | ASSERT(LEAF_NODE(node)); |
266 | ASSERT(LEAF_NODE(node)); |
245 | ASSERT(node->keys); |
267 | ASSERT(node->keys); |
246 | return node->value[node->keys - 1]; |
268 | return node->value[node->keys - 1]; |
247 | } |
269 | } |
248 | 270 | ||
249 | /** Initialize B-tree node. |
271 | /** Initialize B-tree node. |
250 | * |
272 | * |
251 | * @param node B-tree node. |
273 | * @param node B-tree node. |
252 | */ |
274 | */ |
253 | void node_initialize(btree_node_t *node) |
275 | void node_initialize(btree_node_t *node) |
254 | { |
276 | { |
255 | int i; |
277 | int i; |
256 | 278 | ||
257 | node->keys = 0; |
279 | node->keys = 0; |
258 | 280 | ||
259 | /* Clean also space for the extra key. */ |
281 | /* Clean also space for the extra key. */ |
260 | for (i = 0; i < BTREE_MAX_KEYS + 1; i++) { |
282 | for (i = 0; i < BTREE_MAX_KEYS + 1; i++) { |
261 | node->key[i] = 0; |
283 | node->key[i] = 0; |
262 | node->value[i] = NULL; |
284 | node->value[i] = NULL; |
263 | node->subtree[i] = NULL; |
285 | node->subtree[i] = NULL; |
264 | } |
286 | } |
265 | node->subtree[i] = NULL; |
287 | node->subtree[i] = NULL; |
266 | 288 | ||
267 | node->parent = NULL; |
289 | node->parent = NULL; |
268 | 290 | ||
269 | link_initialize(&node->leaf_link); |
291 | link_initialize(&node->leaf_link); |
270 | 292 | ||
271 | link_initialize(&node->bfs_link); |
293 | link_initialize(&node->bfs_link); |
272 | node->depth = 0; |
294 | node->depth = 0; |
273 | } |
295 | } |
274 | 296 | ||
275 | /** Insert key-value-left-subtree triplet into B-tree non-full node. |
297 | /** Insert key-value-right-subtree triplet into B-tree non-full node. |
276 | * |
298 | * |
277 | * It is actually possible to have more keys than BTREE_MAX_KEYS. |
299 | * It is actually possible to have more keys than BTREE_MAX_KEYS. |
278 | * This feature is used during splitting the node when the |
300 | * This feature is used during splitting the node when the |
279 | * number of keys is BTREE_MAX_KEYS + 1. |
301 | * number of keys is BTREE_MAX_KEYS + 1. |
280 | * |
302 | * |
281 | * @param node B-tree node into wich the new key is to be inserted. |
303 | * @param node B-tree node into wich the new key is to be inserted. |
282 | * @param key The key to be inserted. |
304 | * @param key The key to be inserted. |
283 | * @param value Pointer to value to be inserted. |
305 | * @param value Pointer to value to be inserted. |
284 | * @param rsubtree Pointer to the right subtree. |
306 | * @param rsubtree Pointer to the right subtree. |
285 | */ |
307 | */ |
286 | void node_insert_key(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree) |
308 | void node_insert_key(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree) |
287 | { |
309 | { |
288 | int i; |
310 | int i; |
289 | 311 | ||
290 | for (i = 0; i < node->keys; i++) { |
312 | for (i = 0; i < node->keys; i++) { |
291 | if (key < node->key[i]) { |
313 | if (key < node->key[i]) { |
292 | int j; |
314 | int j; |
293 | 315 | ||
294 | for (j = node->keys; j > i; j--) { |
316 | for (j = node->keys; j > i; j--) { |
295 | node->key[j] = node->key[j - 1]; |
317 | node->key[j] = node->key[j - 1]; |
296 | node->value[j] = node->value[j - 1]; |
318 | node->value[j] = node->value[j - 1]; |
297 | node->subtree[j + 1] = node->subtree[j]; |
319 | node->subtree[j + 1] = node->subtree[j]; |
298 | } |
320 | } |
299 | break; |
321 | break; |
300 | } |
322 | } |
301 | } |
323 | } |
302 | 324 | ||
303 | node->key[i] = key; |
325 | node->key[i] = key; |
304 | node->value[i] = value; |
326 | node->value[i] = value; |
305 | node->subtree[i + 1] = rsubtree; |
327 | node->subtree[i + 1] = rsubtree; |
306 | 328 | ||
307 | node->keys++; |
329 | node->keys++; |
308 | } |
330 | } |
309 | 331 | ||
310 | /** Split full B-tree node and insert new key-value-left-subtree triplet. |
332 | /** Split full B-tree node and insert new key-value-right-subtree triplet. |
311 | * |
333 | * |
312 | * This function will split a node and return pointer to a newly created |
334 | * This function will split a node and return pointer to a newly created |
313 | * node containing keys greater than the lesser of medians (or median) |
335 | * node containing keys greater than or equal to the greater of medians |
314 | * of the old keys and the newly added key. It will also write the |
336 | * (or median) of the old keys and the newly added key. It will also write |
315 | * median key to a memory address supplied by the caller. |
337 | * the median key to a memory address supplied by the caller. |
316 | * |
338 | * |
317 | * If the node being split is an index node, the median will be |
339 | * If the node being split is an index node, the median will not be |
318 | * removed from the original node. If the node is a leaf node, |
340 | * included in the new node. If the node is a leaf node, |
319 | * the median will be preserved. |
341 | * the median will be copied there. |
320 | * |
342 | * |
321 | * @param node B-tree node wich is going to be split. |
343 | * @param node B-tree node wich is going to be split. |
322 | * @param key The key to be inserted. |
344 | * @param key The key to be inserted. |
323 | * @param value Pointer to the value to be inserted. |
345 | * @param value Pointer to the value to be inserted. |
324 | * @param rsubtree Pointer to the right subtree of the key being added. |
346 | * @param rsubtree Pointer to the right subtree of the key being added. |
325 | * @param median Address in memory, where the median key will be stored. |
347 | * @param median Address in memory, where the median key will be stored. |
326 | * |
348 | * |
327 | * @return Newly created right sibling of node. |
349 | * @return Newly created right sibling of node. |
328 | */ |
350 | */ |
329 | btree_node_t *node_split(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree, __native *median) |
351 | btree_node_t *node_split(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree, __native *median) |
330 | { |
352 | { |
331 | btree_node_t *rnode; |
353 | btree_node_t *rnode; |
332 | int i, j; |
354 | int i, j; |
333 | 355 | ||
334 | ASSERT(median); |
356 | ASSERT(median); |
335 | ASSERT(node->keys == BTREE_MAX_KEYS); |
357 | ASSERT(node->keys == BTREE_MAX_KEYS); |
336 | 358 | ||
337 | /* |
359 | /* |
338 | * Use the extra space to store the extra node. |
360 | * Use the extra space to store the extra node. |
339 | */ |
361 | */ |
340 | node_insert_key(node, key, value, rsubtree); |
362 | node_insert_key(node, key, value, rsubtree); |
341 | 363 | ||
342 | /* |
364 | /* |
343 | * Compute median of keys. |
365 | * Compute median of keys. |
344 | */ |
366 | */ |
345 | *median = MEDIAN_LOW(node); |
367 | *median = MEDIAN_HIGH(node); |
346 | 368 | ||
- | 369 | /* |
|
- | 370 | * Allocate and initialize new right sibling. |
|
- | 371 | */ |
|
347 | rnode = (btree_node_t *) malloc(sizeof(btree_node_t), 0); |
372 | rnode = (btree_node_t *) malloc(sizeof(btree_node_t), 0); |
348 | node_initialize(rnode); |
373 | node_initialize(rnode); |
349 | rnode->parent = node->parent; |
374 | rnode->parent = node->parent; |
350 | rnode->depth = node->depth; |
375 | rnode->depth = node->depth; |
351 | 376 | ||
352 | /* |
377 | /* |
353 | * Copy big keys, values and subtree pointers to the new right sibling. |
378 | * Copy big keys, values and subtree pointers to the new right sibling. |
- | 379 | * If this is an index node, do not copy the median. |
|
354 | */ |
380 | */ |
- | 381 | i = (int) INDEX_NODE(node); |
|
355 | for (i = MEDIAN_LOW_INDEX(node) + 1, j = 0; i < node->keys; i++, j++) { |
382 | for (i += MEDIAN_HIGH_INDEX(node), j = 0; i < node->keys; i++, j++) { |
356 | rnode->key[j] = node->key[i]; |
383 | rnode->key[j] = node->key[i]; |
357 | rnode->value[j] = node->value[i]; |
384 | rnode->value[j] = node->value[i]; |
358 | rnode->subtree[j] = node->subtree[i]; |
385 | rnode->subtree[j] = node->subtree[i]; |
359 | 386 | ||
360 | /* |
387 | /* |
361 | * Fix parent links in subtrees. |
388 | * Fix parent links in subtrees. |
362 | */ |
389 | */ |
363 | if (rnode->subtree[j]) |
390 | if (rnode->subtree[j]) |
364 | rnode->subtree[j]->parent = rnode; |
391 | rnode->subtree[j]->parent = rnode; |
365 | 392 | ||
366 | } |
393 | } |
367 | rnode->subtree[j] = node->subtree[i]; |
394 | rnode->subtree[j] = node->subtree[i]; |
368 | if (rnode->subtree[j]) |
395 | if (rnode->subtree[j]) |
369 | rnode->subtree[j]->parent = rnode; |
396 | rnode->subtree[j]->parent = rnode; |
370 | rnode->keys = j; |
- | |
371 | 397 | ||
372 | /* |
- | |
373 | * Shrink the old node. |
- | |
374 | * If this is an index node, remove the median. |
398 | rnode->keys = j; /* Set number of keys of the new node. */ |
375 | */ |
- | |
376 | node->keys = MEDIAN_LOW_INDEX(node) + 1; |
399 | node->keys /= 2; /* Shrink the old node. */ |
377 | if (INDEX_NODE(node)) |
- | |
378 | node->keys--; |
- | |
379 | 400 | ||
380 | return rnode; |
401 | return rnode; |
381 | } |
402 | } |
- | 403 | ||
- | 404 | /** Remove key from B-tree node. |
|
- | 405 | * |
|
- | 406 | * @param node B-tree node. |
|
- | 407 | * @param key Key to be removed. |
|
- | 408 | */ |
|
- | 409 | void node_remove_key(btree_node_t *node, __native key) |
|
- | 410 | { |
|
- | 411 | } |
|
382 | 412 | ||
383 | /** Print B-tree. |
413 | /** Print B-tree. |
384 | * |
414 | * |
385 | * @param t Print out B-tree. |
415 | * @param t Print out B-tree. |
386 | */ |
416 | */ |
387 | void btree_print(btree_t *t) |
417 | void btree_print(btree_t *t) |
388 | { |
418 | { |
389 | int i, depth = t->root->depth; |
419 | int i, depth = t->root->depth; |
390 | link_t head; |
420 | link_t head; |
391 | 421 | ||
392 | list_initialize(&head); |
422 | list_initialize(&head); |
393 | list_append(&t->root->bfs_link, &head); |
423 | list_append(&t->root->bfs_link, &head); |
394 | 424 | ||
395 | /* |
425 | /* |
396 | * Use BFS search to print out the tree. |
426 | * Use BFS search to print out the tree. |
397 | * Levels are distinguished from one another by node->depth. |
427 | * Levels are distinguished from one another by node->depth. |
398 | */ |
428 | */ |
399 | while (!list_empty(&head)) { |
429 | while (!list_empty(&head)) { |
400 | link_t *hlp; |
430 | link_t *hlp; |
401 | btree_node_t *node; |
431 | btree_node_t *node; |
402 | 432 | ||
403 | hlp = head.next; |
433 | hlp = head.next; |
404 | ASSERT(hlp != &head); |
434 | ASSERT(hlp != &head); |
405 | node = list_get_instance(hlp, btree_node_t, bfs_link); |
435 | node = list_get_instance(hlp, btree_node_t, bfs_link); |
406 | list_remove(hlp); |
436 | list_remove(hlp); |
407 | 437 | ||
408 | ASSERT(node); |
438 | ASSERT(node); |
409 | 439 | ||
410 | if (node->depth != depth) { |
440 | if (node->depth != depth) { |
411 | printf("\n"); |
441 | printf("\n"); |
412 | depth = node->depth; |
442 | depth = node->depth; |
413 | } |
443 | } |
414 | 444 | ||
415 | printf("("); |
445 | printf("("); |
416 | for (i = 0; i < node->keys; i++) { |
446 | for (i = 0; i < node->keys; i++) { |
417 | printf("%d,", node->key[i]); |
447 | printf("%d,", node->key[i]); |
418 | if (node->depth && node->subtree[i]) { |
448 | if (node->depth && node->subtree[i]) { |
419 | list_append(&node->subtree[i]->bfs_link, &head); |
449 | list_append(&node->subtree[i]->bfs_link, &head); |
420 | } |
450 | } |
421 | } |
451 | } |
422 | if (node->depth && node->subtree[i]) { |
452 | if (node->depth && node->subtree[i]) { |
423 | list_append(&node->subtree[i]->bfs_link, &head); |
453 | list_append(&node->subtree[i]->bfs_link, &head); |
424 | } |
454 | } |
425 | printf(")"); |
455 | printf(")"); |
426 | } |
456 | } |
427 | printf("\n"); |
457 | printf("\n"); |
428 | } |
458 | } |
429 | 459 |