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