Commit | Line | Data |
---|---|---|
be0e5c09 CM |
1 | #include <stdio.h> |
2 | #include <stdlib.h> | |
3 | #include "kerncompat.h" | |
4 | ||
5 | #define BLOCKSIZE 4096 | |
6 | ||
7 | struct key { | |
8 | u64 objectid; | |
9 | u32 flags; | |
10 | u64 offset; | |
11 | } __attribute__ ((__packed__)); | |
12 | ||
13 | struct header { | |
14 | u64 fsid[2]; /* FS specific uuid */ | |
15 | u64 blocknum; | |
16 | u64 parentid; | |
17 | u32 csum; | |
18 | u32 ham; | |
19 | u16 nritems; | |
20 | u16 flags; | |
21 | } __attribute__ ((__packed__)); | |
22 | ||
23 | #define NODEPTRS_PER_BLOCK ((BLOCKSIZE - sizeof(struct header)) / \ | |
24 | (sizeof(struct key) + sizeof(u64))) | |
25 | ||
26 | #define LEVEL_BITS 3 | |
27 | #define MAX_LEVEL (1 << LEVEL_BITS) | |
28 | #define node_level(f) ((f) & (MAX_LEVEL-1)) | |
29 | #define is_leaf(f) (node_level(f) == 0) | |
30 | ||
31 | struct ctree_root { | |
32 | struct node *node; | |
33 | }; | |
34 | ||
35 | struct item { | |
36 | struct key key; | |
37 | u16 offset; | |
38 | u16 size; | |
39 | } __attribute__ ((__packed__)); | |
40 | ||
41 | #define LEAF_DATA_SIZE (BLOCKSIZE - sizeof(struct header)) | |
42 | struct leaf { | |
43 | struct header header; | |
44 | union { | |
45 | struct item items[LEAF_DATA_SIZE/sizeof(struct item)]; | |
46 | u8 data[BLOCKSIZE-sizeof(struct header)]; | |
47 | }; | |
48 | } __attribute__ ((__packed__)); | |
49 | ||
50 | struct node { | |
51 | struct header header; | |
52 | struct key keys[NODEPTRS_PER_BLOCK]; | |
53 | u64 blockptrs[NODEPTRS_PER_BLOCK]; | |
54 | } __attribute__ ((__packed__)); | |
55 | ||
56 | struct ctree_path { | |
57 | struct node *nodes[MAX_LEVEL]; | |
58 | int slots[MAX_LEVEL]; | |
59 | }; | |
60 | ||
61 | static inline void init_path(struct ctree_path *p) | |
62 | { | |
63 | memset(p, 0, sizeof(*p)); | |
64 | } | |
65 | ||
66 | static inline unsigned int leaf_data_end(struct leaf *leaf) | |
67 | { | |
68 | unsigned int nr = leaf->header.nritems; | |
69 | if (nr == 0) | |
70 | return ARRAY_SIZE(leaf->data); | |
71 | return leaf->items[nr-1].offset; | |
72 | } | |
73 | ||
74 | static inline int leaf_free_space(struct leaf *leaf) | |
75 | { | |
76 | int data_end = leaf_data_end(leaf); | |
77 | int nritems = leaf->header.nritems; | |
78 | char *items_end = (char *)(leaf->items + nritems + 1); | |
79 | return (char *)(leaf->data + data_end) - (char *)items_end; | |
80 | } | |
81 | ||
82 | int comp_keys(struct key *k1, struct key *k2) | |
83 | { | |
84 | if (k1->objectid > k2->objectid) | |
85 | return 1; | |
86 | if (k1->objectid < k2->objectid) | |
87 | return -1; | |
88 | if (k1->flags > k2->flags) | |
89 | return 1; | |
90 | if (k1->flags < k2->flags) | |
91 | return -1; | |
92 | if (k1->offset > k2->offset) | |
93 | return 1; | |
94 | if (k1->offset < k2->offset) | |
95 | return -1; | |
96 | return 0; | |
97 | } | |
98 | int generic_bin_search(char *p, int item_size, struct key *key, | |
99 | int max, int *slot) | |
100 | { | |
101 | int low = 0; | |
102 | int high = max; | |
103 | int mid; | |
104 | int ret; | |
105 | struct key *tmp; | |
106 | ||
107 | while(low < high) { | |
108 | mid = (low + high) / 2; | |
109 | tmp = (struct key *)(p + mid * item_size); | |
110 | ret = comp_keys(tmp, key); | |
111 | ||
112 | if (ret < 0) | |
113 | low = mid + 1; | |
114 | else if (ret > 0) | |
115 | high = mid; | |
116 | else { | |
117 | *slot = mid; | |
118 | return 0; | |
119 | } | |
120 | } | |
121 | *slot = low; | |
122 | return 1; | |
123 | } | |
124 | ||
125 | int bin_search(struct node *c, struct key *key, int *slot) | |
126 | { | |
127 | if (is_leaf(c->header.flags)) { | |
128 | struct leaf *l = (struct leaf *)c; | |
129 | return generic_bin_search((void *)l->items, sizeof(struct item), | |
130 | key, c->header.nritems, slot); | |
131 | } else { | |
132 | return generic_bin_search((void *)c->keys, sizeof(struct key), | |
133 | key, c->header.nritems, slot); | |
134 | } | |
135 | return -1; | |
136 | } | |
137 | ||
138 | void *read_block(u64 blocknum) | |
139 | { | |
140 | return (void *)blocknum; | |
141 | } | |
142 | ||
143 | int search_slot(struct ctree_root *root, struct key *key, struct ctree_path *p) | |
144 | { | |
145 | struct node *c = root->node; | |
146 | int slot; | |
147 | int ret; | |
148 | int level; | |
149 | while (c) { | |
150 | level = node_level(c->header.flags); | |
151 | p->nodes[level] = c; | |
152 | ret = bin_search(c, key, &slot); | |
153 | if (!is_leaf(c->header.flags)) { | |
154 | if (ret && slot > 0) | |
155 | slot -= 1; | |
156 | p->slots[level] = slot; | |
157 | c = read_block(c->blockptrs[slot]); | |
158 | continue; | |
159 | } else { | |
160 | p->slots[level] = slot; | |
161 | return ret; | |
162 | } | |
163 | } | |
164 | return -1; | |
165 | } | |
166 | ||
167 | static void fixup_low_keys(struct ctree_path *path, struct key *key, | |
168 | int level) | |
169 | { | |
170 | int i; | |
171 | /* adjust the pointers going up the tree */ | |
172 | for (i = level; i < MAX_LEVEL; i++) { | |
173 | struct node *t = path->nodes[i]; | |
174 | int tslot = path->slots[i]; | |
175 | if (!t) | |
176 | break; | |
177 | memcpy(t->keys + tslot, key, sizeof(*key)); | |
178 | if (tslot != 0) | |
179 | break; | |
180 | } | |
181 | } | |
182 | ||
183 | int __insert_ptr(struct ctree_root *root, | |
184 | struct ctree_path *path, struct key *key, | |
185 | u64 blocknr, int slot, int level) | |
186 | { | |
187 | struct node *c; | |
188 | struct node *lower; | |
189 | struct key *lower_key; | |
190 | int nritems; | |
191 | /* need a new root */ | |
192 | if (!path->nodes[level]) { | |
193 | c = malloc(sizeof(struct node)); | |
194 | memset(c, 0, sizeof(c)); | |
195 | c->header.nritems = 2; | |
196 | c->header.flags = node_level(level); | |
197 | lower = path->nodes[level-1]; | |
198 | if (is_leaf(lower->header.flags)) | |
199 | lower_key = &((struct leaf *)lower)->items[0].key; | |
200 | else | |
201 | lower_key = lower->keys; | |
202 | memcpy(c->keys, lower_key, sizeof(struct key)); | |
203 | memcpy(c->keys + 1, key, sizeof(struct key)); | |
204 | c->blockptrs[0] = (u64)lower; | |
205 | c->blockptrs[1] = blocknr; | |
206 | root->node = c; | |
207 | path->nodes[level] = c; | |
208 | path->slots[level] = 0; | |
209 | if (c->keys[1].objectid == 0) | |
210 | BUG(); | |
211 | return 0; | |
212 | } | |
213 | lower = path->nodes[level]; | |
214 | nritems = lower->header.nritems; | |
215 | if (slot > nritems) | |
216 | BUG(); | |
217 | if (nritems == NODEPTRS_PER_BLOCK) | |
218 | BUG(); | |
219 | if (slot != nritems) { | |
220 | memmove(lower->keys + slot + 1, lower->keys + slot, | |
221 | (nritems - slot) * sizeof(struct key)); | |
222 | memmove(lower->blockptrs + slot + 1, lower->blockptrs + slot, | |
223 | (nritems - slot) * sizeof(u64)); | |
224 | } | |
225 | memcpy(lower->keys + slot, key, sizeof(struct key)); | |
226 | lower->blockptrs[slot] = blocknr; | |
227 | lower->header.nritems++; | |
228 | if (lower->keys[1].objectid == 0) | |
229 | BUG(); | |
230 | return 0; | |
231 | } | |
232 | ||
233 | int push_node_left(struct ctree_root *root, struct ctree_path *path, int level) | |
234 | { | |
235 | int slot; | |
236 | struct node *left; | |
237 | struct node *right; | |
238 | int push_items = 0; | |
239 | int left_nritems; | |
240 | int right_nritems; | |
241 | ||
242 | if (level == MAX_LEVEL - 1 || path->nodes[level + 1] == 0) | |
243 | return 1; | |
244 | slot = path->slots[level + 1]; | |
245 | if (slot == 0) | |
246 | return 1; | |
247 | ||
248 | left = read_block(path->nodes[level + 1]->blockptrs[slot - 1]); | |
249 | right = path->nodes[level]; | |
250 | left_nritems = left->header.nritems; | |
251 | right_nritems = right->header.nritems; | |
252 | push_items = NODEPTRS_PER_BLOCK - (left_nritems + 1); | |
253 | if (push_items <= 0) | |
254 | return 1; | |
255 | ||
256 | if (right_nritems < push_items) | |
257 | push_items = right_nritems; | |
258 | memcpy(left->keys + left_nritems, right->keys, | |
259 | push_items * sizeof(struct key)); | |
260 | memcpy(left->blockptrs + left_nritems, right->blockptrs, | |
261 | push_items * sizeof(u64)); | |
262 | memmove(right->keys, right->keys + push_items, | |
263 | (right_nritems - push_items) * sizeof(struct key)); | |
264 | memmove(right->blockptrs, right->blockptrs + push_items, | |
265 | (right_nritems - push_items) * sizeof(u64)); | |
266 | right->header.nritems -= push_items; | |
267 | left->header.nritems += push_items; | |
268 | ||
269 | /* adjust the pointers going up the tree */ | |
270 | fixup_low_keys(path, right->keys, level + 1); | |
271 | ||
272 | /* then fixup the leaf pointer in the path */ | |
273 | if (path->slots[level] < push_items) { | |
274 | path->slots[level] += left_nritems; | |
275 | path->nodes[level] = (struct node*)left; | |
276 | path->slots[level + 1] -= 1; | |
277 | } else { | |
278 | path->slots[level] -= push_items; | |
279 | } | |
280 | return 0; | |
281 | } | |
282 | ||
283 | int push_node_right(struct ctree_root *root, struct ctree_path *path, int level) | |
284 | { | |
285 | int slot; | |
286 | struct node *dst; | |
287 | struct node *src; | |
288 | int push_items = 0; | |
289 | int dst_nritems; | |
290 | int src_nritems; | |
291 | ||
292 | if (level == MAX_LEVEL - 1 || path->nodes[level + 1] == 0) | |
293 | return 1; | |
294 | slot = path->slots[level + 1]; | |
295 | if (slot == NODEPTRS_PER_BLOCK - 1) | |
296 | return 1; | |
297 | ||
298 | if (slot >= path->nodes[level + 1]->header.nritems -1) | |
299 | return 1; | |
300 | ||
301 | dst = read_block(path->nodes[level + 1]->blockptrs[slot + 1]); | |
302 | src = path->nodes[level]; | |
303 | dst_nritems = dst->header.nritems; | |
304 | src_nritems = src->header.nritems; | |
305 | push_items = NODEPTRS_PER_BLOCK - (dst_nritems + 1); | |
306 | if (push_items <= 0) | |
307 | return 1; | |
308 | ||
309 | if (src_nritems < push_items) | |
310 | push_items = src_nritems; | |
311 | memmove(dst->keys + push_items, dst->keys, | |
312 | dst_nritems * sizeof(struct key)); | |
313 | memcpy(dst->keys, src->keys + src_nritems - push_items, | |
314 | push_items * sizeof(struct key)); | |
315 | ||
316 | memmove(dst->blockptrs + push_items, dst->blockptrs, | |
317 | dst_nritems * sizeof(u64)); | |
318 | memcpy(dst->blockptrs, src->blockptrs + src_nritems - push_items, | |
319 | push_items * sizeof(u64)); | |
320 | ||
321 | src->header.nritems -= push_items; | |
322 | dst->header.nritems += push_items; | |
323 | ||
324 | /* adjust the pointers going up the tree */ | |
325 | memcpy(path->nodes[level + 1]->keys + path->slots[level + 1] + 1, | |
326 | dst->keys, sizeof(struct key)); | |
327 | /* then fixup the leaf pointer in the path */ | |
328 | if (path->slots[level] >= src->header.nritems) { | |
329 | path->slots[level] -= src->header.nritems; | |
330 | path->nodes[level] = (struct node*)dst; | |
331 | path->slots[level + 1] += 1; | |
332 | } | |
333 | return 0; | |
334 | } | |
335 | ||
336 | int insert_ptr(struct ctree_root *root, | |
337 | struct ctree_path *path, struct key *key, | |
338 | u64 blocknr, int level) | |
339 | { | |
340 | struct node *c = path->nodes[level]; | |
341 | struct node *b; | |
342 | struct node *bal[MAX_LEVEL]; | |
343 | int bal_level = level; | |
344 | int mid; | |
345 | int bal_start = -1; | |
346 | ||
347 | memset(bal, 0, ARRAY_SIZE(bal)); | |
348 | while(c && c->header.nritems == NODEPTRS_PER_BLOCK) { | |
349 | if (push_node_left(root, path, | |
350 | node_level(c->header.flags)) == 0) | |
351 | break; | |
352 | if (push_node_right(root, path, | |
353 | node_level(c->header.flags)) == 0) | |
354 | break; | |
355 | bal_start = bal_level; | |
356 | if (bal_level == MAX_LEVEL - 1) | |
357 | BUG(); | |
358 | b = malloc(sizeof(struct node)); | |
359 | b->header.flags = c->header.flags; | |
360 | mid = (c->header.nritems + 1) / 2; | |
361 | memcpy(b->keys, c->keys + mid, | |
362 | (c->header.nritems - mid) * sizeof(struct key)); | |
363 | memcpy(b->blockptrs, c->blockptrs + mid, | |
364 | (c->header.nritems - mid) * sizeof(u64)); | |
365 | b->header.nritems = c->header.nritems - mid; | |
366 | c->header.nritems = mid; | |
367 | bal[bal_level] = b; | |
368 | if (bal_level == MAX_LEVEL - 1) | |
369 | break; | |
370 | bal_level += 1; | |
371 | c = path->nodes[bal_level]; | |
372 | } | |
373 | while(bal_start > 0) { | |
374 | b = bal[bal_start]; | |
375 | c = path->nodes[bal_start]; | |
376 | __insert_ptr(root, path, b->keys, (u64)b, | |
377 | path->slots[bal_start + 1] + 1, bal_start + 1); | |
378 | if (path->slots[bal_start] >= c->header.nritems) { | |
379 | path->slots[bal_start] -= c->header.nritems; | |
380 | path->nodes[bal_start] = b; | |
381 | path->slots[bal_start + 1] += 1; | |
382 | } | |
383 | bal_start--; | |
384 | if (!bal[bal_start]) | |
385 | break; | |
386 | } | |
387 | return __insert_ptr(root, path, key, blocknr, path->slots[level] + 1, | |
388 | level); | |
389 | } | |
390 | ||
391 | int leaf_space_used(struct leaf *l, int start, int nr) | |
392 | { | |
393 | int data_len; | |
394 | int end = start + nr - 1; | |
395 | ||
396 | if (!nr) | |
397 | return 0; | |
398 | data_len = l->items[start].offset + l->items[start].size; | |
399 | data_len = data_len - l->items[end].offset; | |
400 | data_len += sizeof(struct item) * nr; | |
401 | return data_len; | |
402 | } | |
403 | ||
404 | int push_leaf_left(struct ctree_root *root, struct ctree_path *path, | |
405 | int data_size) | |
406 | { | |
407 | struct leaf *right = (struct leaf *)path->nodes[0]; | |
408 | struct leaf *left; | |
409 | int slot; | |
410 | int i; | |
411 | int free_space; | |
412 | int push_space = 0; | |
413 | int push_items = 0; | |
414 | struct item *item; | |
415 | int old_left_nritems; | |
416 | ||
417 | slot = path->slots[1]; | |
418 | if (slot == 0) { | |
419 | return 1; | |
420 | } | |
421 | if (!path->nodes[1]) { | |
422 | return 1; | |
423 | } | |
424 | left = read_block(path->nodes[1]->blockptrs[slot - 1]); | |
425 | free_space = leaf_free_space(left); | |
426 | if (free_space < data_size + sizeof(struct item)) { | |
427 | return 1; | |
428 | } | |
429 | for (i = 0; i < right->header.nritems; i++) { | |
430 | item = right->items + i; | |
431 | if (path->slots[0] == i) | |
432 | push_space += data_size + sizeof(*item); | |
433 | if (item->size + sizeof(*item) + push_space > free_space) | |
434 | break; | |
435 | push_items++; | |
436 | push_space += item->size + sizeof(*item); | |
437 | } | |
438 | if (push_items == 0) { | |
439 | return 1; | |
440 | } | |
441 | /* push data from right to left */ | |
442 | memcpy(left->items + left->header.nritems, | |
443 | right->items, push_items * sizeof(struct item)); | |
444 | push_space = LEAF_DATA_SIZE - right->items[push_items -1].offset; | |
445 | memcpy(left->data + leaf_data_end(left) - push_space, | |
446 | right->data + right->items[push_items - 1].offset, | |
447 | push_space); | |
448 | old_left_nritems = left->header.nritems; | |
449 | for(i = old_left_nritems; i < old_left_nritems + push_items; i++) { | |
450 | left->items[i].offset -= LEAF_DATA_SIZE - | |
451 | left->items[old_left_nritems -1].offset; | |
452 | } | |
453 | left->header.nritems += push_items; | |
454 | ||
455 | /* fixup right node */ | |
456 | push_space = right->items[push_items-1].offset - leaf_data_end(right); | |
457 | memmove(right->data + LEAF_DATA_SIZE - push_space, right->data + | |
458 | leaf_data_end(right), push_space); | |
459 | memmove(right->items, right->items + push_items, | |
460 | (right->header.nritems - push_items) * sizeof(struct item)); | |
461 | right->header.nritems -= push_items; | |
462 | push_space = LEAF_DATA_SIZE; | |
463 | for (i = 0; i < right->header.nritems; i++) { | |
464 | right->items[i].offset = push_space - right->items[i].size; | |
465 | push_space = right->items[i].offset; | |
466 | } | |
467 | fixup_low_keys(path, &right->items[0].key, 1); | |
468 | ||
469 | /* then fixup the leaf pointer in the path */ | |
470 | if (path->slots[0] < push_items) { | |
471 | path->slots[0] += old_left_nritems; | |
472 | path->nodes[0] = (struct node*)left; | |
473 | path->slots[1] -= 1; | |
474 | } else { | |
475 | path->slots[0] -= push_items; | |
476 | } | |
477 | return 0; | |
478 | } | |
479 | ||
480 | int split_leaf(struct ctree_root *root, struct ctree_path *path, int data_size) | |
481 | { | |
482 | struct leaf *l = (struct leaf *)path->nodes[0]; | |
483 | int nritems = l->header.nritems; | |
484 | int mid = (nritems + 1)/ 2; | |
485 | int slot = path->slots[0]; | |
486 | struct leaf *right; | |
487 | int space_needed = data_size + sizeof(struct item); | |
488 | int data_copy_size; | |
489 | int rt_data_off; | |
490 | int i; | |
491 | int ret; | |
492 | ||
493 | if (push_leaf_left(root, path, data_size) == 0) { | |
494 | return 0; | |
495 | } | |
496 | right = malloc(sizeof(struct leaf)); | |
497 | memset(right, 0, sizeof(*right)); | |
498 | if (mid <= slot) { | |
499 | if (leaf_space_used(l, mid, nritems - mid) + space_needed > | |
500 | LEAF_DATA_SIZE) | |
501 | BUG(); | |
502 | } else { | |
503 | if (leaf_space_used(l, 0, mid + 1) + space_needed > | |
504 | LEAF_DATA_SIZE) | |
505 | BUG(); | |
506 | } | |
507 | right->header.nritems = nritems - mid; | |
508 | data_copy_size = l->items[mid].offset + l->items[mid].size - | |
509 | leaf_data_end(l); | |
510 | memcpy(right->items, l->items + mid, | |
511 | (nritems - mid) * sizeof(struct item)); | |
512 | memcpy(right->data + LEAF_DATA_SIZE - data_copy_size, | |
513 | l->data + leaf_data_end(l), data_copy_size); | |
514 | rt_data_off = LEAF_DATA_SIZE - | |
515 | (l->items[mid].offset + l->items[mid].size); | |
516 | for (i = 0; i < right->header.nritems; i++) { | |
517 | right->items[i].offset += rt_data_off; | |
518 | } | |
519 | l->header.nritems = mid; | |
520 | ret = insert_ptr(root, path, &right->items[0].key, | |
521 | (u64)right, 1); | |
522 | if (mid <= slot) { | |
523 | path->nodes[0] = (struct node *)right; | |
524 | path->slots[0] -= mid; | |
525 | path->slots[1] += 1; | |
526 | } | |
527 | return ret; | |
528 | } | |
529 | ||
530 | int insert_item(struct ctree_root *root, struct key *key, | |
531 | void *data, int data_size) | |
532 | { | |
533 | int ret; | |
534 | int slot; | |
535 | struct leaf *leaf; | |
536 | unsigned int nritems; | |
537 | unsigned int data_end; | |
538 | struct ctree_path path; | |
539 | ||
540 | init_path(&path); | |
541 | ret = search_slot(root, key, &path); | |
542 | if (ret == 0) | |
543 | return -EEXIST; | |
544 | ||
545 | leaf = (struct leaf *)path.nodes[0]; | |
546 | if (leaf_free_space(leaf) < sizeof(struct item) + data_size) | |
547 | split_leaf(root, &path, data_size); | |
548 | leaf = (struct leaf *)path.nodes[0]; | |
549 | nritems = leaf->header.nritems; | |
550 | data_end = leaf_data_end(leaf); | |
551 | if (leaf_free_space(leaf) < sizeof(struct item) + data_size) | |
552 | BUG(); | |
553 | ||
554 | slot = path.slots[0]; | |
555 | if (slot == 0) | |
556 | fixup_low_keys(&path, key, 1); | |
557 | if (slot != nritems) { | |
558 | int i; | |
559 | unsigned int old_data = leaf->items[slot].offset + | |
560 | leaf->items[slot].size; | |
561 | ||
562 | /* | |
563 | * item0..itemN ... dataN.offset..dataN.size .. data0.size | |
564 | */ | |
565 | /* first correct the data pointers */ | |
566 | for (i = slot; i < nritems; i++) | |
567 | leaf->items[i].offset -= data_size; | |
568 | ||
569 | /* shift the items */ | |
570 | memmove(leaf->items + slot + 1, leaf->items + slot, | |
571 | (nritems - slot) * sizeof(struct item)); | |
572 | ||
573 | /* shift the data */ | |
574 | memmove(leaf->data + data_end - data_size, leaf->data + | |
575 | data_end, old_data - data_end); | |
576 | data_end = old_data; | |
577 | } | |
578 | memcpy(&leaf->items[slot].key, key, sizeof(struct key)); | |
579 | leaf->items[slot].offset = data_end - data_size; | |
580 | leaf->items[slot].size = data_size; | |
581 | memcpy(leaf->data + data_end - data_size, data, data_size); | |
582 | leaf->header.nritems += 1; | |
583 | if (leaf_free_space(leaf) < 0) | |
584 | BUG(); | |
585 | return 0; | |
586 | } | |
587 | ||
588 | int del_ptr(struct ctree_root *root, struct ctree_path *path, int level) | |
589 | { | |
590 | int slot; | |
591 | struct node *node; | |
592 | int nritems; | |
593 | ||
594 | while(1) { | |
595 | node = path->nodes[level]; | |
596 | if (!node) | |
597 | break; | |
598 | slot = path->slots[level]; | |
599 | nritems = node->header.nritems; | |
600 | ||
601 | if (slot != nritems -1) { | |
602 | memmove(node->keys + slot, node->keys + slot + 1, | |
603 | sizeof(struct key) * (nritems - slot - 1)); | |
604 | memmove(node->blockptrs + slot, | |
605 | node->blockptrs + slot + 1, | |
606 | sizeof(u64) * (nritems - slot - 1)); | |
607 | } | |
608 | node->header.nritems--; | |
609 | if (node->header.nritems != 0) { | |
610 | int tslot; | |
611 | if (slot == 0) | |
612 | fixup_low_keys(path, node->keys, level + 1); | |
613 | tslot = path->slots[level+1]; | |
614 | push_node_left(root, path, level); | |
615 | if (node->header.nritems) { | |
616 | push_node_right(root, path, level); | |
617 | } | |
be0e5c09 CM |
618 | if (node->header.nritems) |
619 | break; | |
4920c9ac | 620 | path->slots[level+1] = tslot; |
be0e5c09 CM |
621 | } |
622 | if (node == root->node) { | |
623 | printf("root is now null!\n"); | |
624 | root->node = NULL; | |
625 | break; | |
626 | } | |
627 | level++; | |
628 | if (!path->nodes[level]) | |
629 | BUG(); | |
630 | free(node); | |
631 | } | |
632 | return 0; | |
633 | } | |
634 | ||
4920c9ac | 635 | int del_item(struct ctree_root *root, struct ctree_path *path) |
be0e5c09 | 636 | { |
be0e5c09 CM |
637 | int slot; |
638 | struct leaf *leaf; | |
be0e5c09 CM |
639 | int doff; |
640 | int dsize; | |
641 | ||
4920c9ac CM |
642 | leaf = (struct leaf *)path->nodes[0]; |
643 | slot = path->slots[0]; | |
be0e5c09 CM |
644 | doff = leaf->items[slot].offset; |
645 | dsize = leaf->items[slot].size; | |
646 | ||
647 | if (slot != leaf->header.nritems - 1) { | |
648 | int i; | |
649 | int data_end = leaf_data_end(leaf); | |
650 | memmove(leaf->data + data_end + dsize, | |
651 | leaf->data + data_end, | |
652 | doff - data_end); | |
653 | for (i = slot + 1; i < leaf->header.nritems; i++) | |
654 | leaf->items[i].offset += dsize; | |
655 | memmove(leaf->items + slot, leaf->items + slot + 1, | |
656 | sizeof(struct item) * | |
657 | (leaf->header.nritems - slot - 1)); | |
658 | } | |
659 | leaf->header.nritems -= 1; | |
660 | if (leaf->header.nritems == 0) { | |
4920c9ac CM |
661 | if (leaf == (struct leaf *)root->node) |
662 | root->node = NULL; | |
663 | else | |
664 | del_ptr(root, path, 1); | |
be0e5c09 | 665 | free(leaf); |
be0e5c09 CM |
666 | } else { |
667 | if (slot == 0) | |
4920c9ac | 668 | fixup_low_keys(path, &leaf->items[0].key, 1); |
be0e5c09 CM |
669 | if (leaf_space_used(leaf, 0, leaf->header.nritems) < |
670 | LEAF_DATA_SIZE / 4) { | |
671 | /* push_leaf_left fixes the path. | |
672 | * make sure the path still points to our leaf | |
673 | * for possible call to del_ptr below | |
674 | */ | |
4920c9ac CM |
675 | slot = path->slots[1]; |
676 | push_leaf_left(root, path, 1); | |
be0e5c09 CM |
677 | if (leaf->header.nritems == 0) { |
678 | free(leaf); | |
4920c9ac CM |
679 | path->slots[1] = slot; |
680 | del_ptr(root, path, 1); | |
be0e5c09 CM |
681 | } |
682 | } | |
683 | } | |
684 | return 0; | |
685 | } | |
686 | ||
687 | void print_leaf(struct leaf *l) | |
688 | { | |
689 | int i; | |
690 | int nr = l->header.nritems; | |
691 | struct item *item; | |
692 | printf("leaf %p total ptrs %d free space %d\n", l, nr, | |
693 | leaf_free_space(l)); | |
694 | fflush(stdout); | |
695 | for (i = 0 ; i < nr ; i++) { | |
696 | item = l->items + i; | |
697 | printf("\titem %d key (%lu %u %lu) itemoff %d itemsize %d\n", | |
698 | i, | |
699 | item->key.objectid, item->key.flags, item->key.offset, | |
700 | item->offset, item->size); | |
701 | fflush(stdout); | |
702 | printf("\t\titem data %.*s\n", item->size, l->data+item->offset); | |
703 | fflush(stdout); | |
704 | } | |
705 | } | |
706 | void print_tree(struct node *c) | |
707 | { | |
708 | int i; | |
709 | int nr; | |
710 | ||
711 | if (!c) | |
712 | return; | |
713 | nr = c->header.nritems; | |
714 | if (is_leaf(c->header.flags)) { | |
715 | print_leaf((struct leaf *)c); | |
716 | return; | |
717 | } | |
718 | printf("node %p level %d total ptrs %d free spc %lu\n", c, | |
719 | node_level(c->header.flags), c->header.nritems, | |
720 | NODEPTRS_PER_BLOCK - c->header.nritems); | |
721 | fflush(stdout); | |
722 | for (i = 0; i < nr; i++) { | |
723 | printf("\tkey %d (%lu %u %lu) block %lx\n", | |
724 | i, | |
725 | c->keys[i].objectid, c->keys[i].flags, c->keys[i].offset, | |
726 | c->blockptrs[i]); | |
727 | fflush(stdout); | |
728 | } | |
729 | for (i = 0; i < nr; i++) { | |
730 | struct node *next = read_block(c->blockptrs[i]); | |
731 | if (is_leaf(next->header.flags) && | |
732 | node_level(c->header.flags) != 1) | |
733 | BUG(); | |
734 | if (node_level(next->header.flags) != | |
735 | node_level(c->header.flags) - 1) | |
736 | BUG(); | |
737 | print_tree(next); | |
738 | } | |
739 | ||
740 | } | |
741 | ||
742 | /* for testing only */ | |
743 | int next_key(int i, int max_key) { | |
744 | return rand() % max_key; | |
745 | // return i; | |
746 | } | |
747 | ||
748 | int main() { | |
749 | struct leaf *first_node = malloc(sizeof(struct leaf)); | |
750 | struct ctree_root root; | |
751 | struct key ins; | |
4920c9ac | 752 | struct key last = { (u64)-1, 0, 0}; |
be0e5c09 CM |
753 | char *buf; |
754 | int i; | |
755 | int num; | |
756 | int ret; | |
4920c9ac | 757 | int run_size = 100000; |
be0e5c09 CM |
758 | int max_key = 100000000; |
759 | int tree_size = 0; | |
760 | struct ctree_path path; | |
761 | ||
762 | ||
763 | srand(55); | |
764 | root.node = (struct node *)first_node; | |
765 | memset(first_node, 0, sizeof(*first_node)); | |
766 | for (i = 0; i < run_size; i++) { | |
767 | buf = malloc(64); | |
768 | num = next_key(i, max_key); | |
769 | // num = i; | |
770 | sprintf(buf, "string-%d", num); | |
771 | // printf("insert %d\n", num); | |
772 | ins.objectid = num; | |
773 | ins.offset = 0; | |
774 | ins.flags = 0; | |
775 | ret = insert_item(&root, &ins, buf, strlen(buf)); | |
776 | if (!ret) | |
777 | tree_size++; | |
778 | } | |
779 | srand(55); | |
780 | for (i = 0; i < run_size; i++) { | |
781 | num = next_key(i, max_key); | |
782 | ins.objectid = num; | |
be0e5c09 CM |
783 | init_path(&path); |
784 | ret = search_slot(&root, &ins, &path); | |
785 | if (ret) { | |
786 | print_tree(root.node); | |
787 | printf("unable to find %d\n", num); | |
788 | exit(1); | |
789 | } | |
790 | } | |
791 | printf("node %p level %d total ptrs %d free spc %lu\n", root.node, | |
792 | node_level(root.node->header.flags), root.node->header.nritems, | |
793 | NODEPTRS_PER_BLOCK - root.node->header.nritems); | |
794 | // print_tree(root.node); | |
795 | printf("all searches good\n"); | |
796 | i = 0; | |
797 | srand(55); | |
4920c9ac CM |
798 | for (i = 0 ; i < run_size/4; i++) { |
799 | num = next_key(i, max_key); | |
800 | ins.objectid = num; | |
801 | init_path(&path); | |
802 | ret = search_slot(&root, &ins, &path); | |
803 | if (ret) | |
804 | continue; | |
805 | ret = del_item(&root, &path); | |
806 | if (ret != 0) | |
807 | BUG(); | |
808 | tree_size--; | |
809 | } | |
810 | srand(128); | |
be0e5c09 | 811 | for (i = 0; i < run_size; i++) { |
4920c9ac | 812 | buf = malloc(64); |
be0e5c09 | 813 | num = next_key(i, max_key); |
4920c9ac | 814 | sprintf(buf, "string-%d", num); |
be0e5c09 | 815 | ins.objectid = num; |
4920c9ac CM |
816 | ret = insert_item(&root, &ins, buf, strlen(buf)); |
817 | if (!ret) | |
818 | tree_size++; | |
819 | } | |
820 | while(root.node) { | |
821 | struct leaf *leaf; | |
822 | int slot; | |
823 | ins.objectid = (u64)-1; | |
824 | init_path(&path); | |
825 | ret = search_slot(&root, &ins, &path); | |
826 | if (ret == 0) | |
827 | BUG(); | |
828 | ||
829 | leaf = (struct leaf *)(path.nodes[0]); | |
830 | slot = path.slots[0]; | |
831 | if (slot != leaf->header.nritems) | |
832 | BUG(); | |
833 | while(path.slots[0] > 0) { | |
834 | path.slots[0] -= 1; | |
835 | slot = path.slots[0]; | |
836 | leaf = (struct leaf *)(path.nodes[0]); | |
837 | ||
838 | if (comp_keys(&last, &leaf->items[slot].key) <= 0) | |
839 | BUG(); | |
840 | memcpy(&last, &leaf->items[slot].key, sizeof(last)); | |
841 | ret = del_item(&root, &path); | |
842 | if (ret != 0) | |
843 | BUG(); | |
844 | tree_size--; | |
845 | } | |
be0e5c09 CM |
846 | } |
847 | print_tree(root.node); | |
4920c9ac | 848 | printf("tree size is now %d\n", tree_size); |
be0e5c09 CM |
849 | return 0; |
850 | } |