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