aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--fs/btrfs/ctree.c810
1 files changed, 810 insertions, 0 deletions
diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c
new file mode 100644
index 000000000000..893fd56960a0
--- /dev/null
+++ b/fs/btrfs/ctree.c
@@ -0,0 +1,810 @@
1#include <stdio.h>
2#include <stdlib.h>
3#include "kerncompat.h"
4
5#define BLOCKSIZE 4096
6
7struct key {
8 u64 objectid;
9 u32 flags;
10 u64 offset;
11} __attribute__ ((__packed__));
12
13struct 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
31struct ctree_root {
32 struct node *node;
33};
34
35struct item {
36 struct key key;
37 u16 offset;
38 u16 size;
39} __attribute__ ((__packed__));
40
41#define LEAF_DATA_SIZE (BLOCKSIZE - sizeof(struct header))
42struct 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
50struct node {
51 struct header header;
52 struct key keys[NODEPTRS_PER_BLOCK];
53 u64 blockptrs[NODEPTRS_PER_BLOCK];
54} __attribute__ ((__packed__));
55
56struct ctree_path {
57 struct node *nodes[MAX_LEVEL];
58 int slots[MAX_LEVEL];
59};
60
61static inline void init_path(struct ctree_path *p)
62{
63 memset(p, 0, sizeof(*p));
64}
65
66static 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
74static 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
82int 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}
98int 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
125int 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
138void *read_block(u64 blocknum)
139{
140 return (void *)blocknum;
141}
142
143int 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
167static 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
183int __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
233int 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
283int 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
336int 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
391int 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
404int 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
480int 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
530int 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
588int 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 }
618 path->slots[level+1] = tslot;
619 if (node->header.nritems)
620 break;
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
635int del_item(struct ctree_root *root, struct key *key)
636{
637 int ret;
638 int slot;
639 struct leaf *leaf;
640 struct ctree_path path;
641 int doff;
642 int dsize;
643
644 init_path(&path);
645 ret = search_slot(root, key, &path);
646 if (ret != 0)
647 return -1;
648
649 leaf = (struct leaf *)path.nodes[0];
650 slot = path.slots[0];
651 doff = leaf->items[slot].offset;
652 dsize = leaf->items[slot].size;
653
654 if (slot != leaf->header.nritems - 1) {
655 int i;
656 int data_end = leaf_data_end(leaf);
657 memmove(leaf->data + data_end + dsize,
658 leaf->data + data_end,
659 doff - data_end);
660 for (i = slot + 1; i < leaf->header.nritems; i++)
661 leaf->items[i].offset += dsize;
662 memmove(leaf->items + slot, leaf->items + slot + 1,
663 sizeof(struct item) *
664 (leaf->header.nritems - slot - 1));
665 }
666 leaf->header.nritems -= 1;
667 if (leaf->header.nritems == 0) {
668 free(leaf);
669 del_ptr(root, &path, 1);
670 } else {
671 if (slot == 0)
672 fixup_low_keys(&path, &leaf->items[0].key, 1);
673 if (leaf_space_used(leaf, 0, leaf->header.nritems) <
674 LEAF_DATA_SIZE / 4) {
675 /* push_leaf_left fixes the path.
676 * make sure the path still points to our leaf
677 * for possible call to del_ptr below
678 */
679 slot = path.slots[1];
680 push_leaf_left(root, &path, 1);
681 path.slots[1] = slot;
682 if (leaf->header.nritems == 0) {
683 free(leaf);
684 del_ptr(root, &path, 1);
685 }
686 }
687 }
688 return 0;
689}
690
691void print_leaf(struct leaf *l)
692{
693 int i;
694 int nr = l->header.nritems;
695 struct item *item;
696 printf("leaf %p total ptrs %d free space %d\n", l, nr,
697 leaf_free_space(l));
698 fflush(stdout);
699 for (i = 0 ; i < nr ; i++) {
700 item = l->items + i;
701 printf("\titem %d key (%lu %u %lu) itemoff %d itemsize %d\n",
702 i,
703 item->key.objectid, item->key.flags, item->key.offset,
704 item->offset, item->size);
705 fflush(stdout);
706 printf("\t\titem data %.*s\n", item->size, l->data+item->offset);
707 fflush(stdout);
708 }
709}
710void print_tree(struct node *c)
711{
712 int i;
713 int nr;
714
715 if (!c)
716 return;
717 nr = c->header.nritems;
718 if (is_leaf(c->header.flags)) {
719 print_leaf((struct leaf *)c);
720 return;
721 }
722 printf("node %p level %d total ptrs %d free spc %lu\n", c,
723 node_level(c->header.flags), c->header.nritems,
724 NODEPTRS_PER_BLOCK - c->header.nritems);
725 fflush(stdout);
726 for (i = 0; i < nr; i++) {
727 printf("\tkey %d (%lu %u %lu) block %lx\n",
728 i,
729 c->keys[i].objectid, c->keys[i].flags, c->keys[i].offset,
730 c->blockptrs[i]);
731 fflush(stdout);
732 }
733 for (i = 0; i < nr; i++) {
734 struct node *next = read_block(c->blockptrs[i]);
735 if (is_leaf(next->header.flags) &&
736 node_level(c->header.flags) != 1)
737 BUG();
738 if (node_level(next->header.flags) !=
739 node_level(c->header.flags) - 1)
740 BUG();
741 print_tree(next);
742 }
743
744}
745
746/* for testing only */
747int next_key(int i, int max_key) {
748 return rand() % max_key;
749 // return i;
750}
751
752int main() {
753 struct leaf *first_node = malloc(sizeof(struct leaf));
754 struct ctree_root root;
755 struct key ins;
756 char *buf;
757 int i;
758 int num;
759 int ret;
760 int run_size = 10000000;
761 int max_key = 100000000;
762 int tree_size = 0;
763 struct ctree_path path;
764
765
766 srand(55);
767 root.node = (struct node *)first_node;
768 memset(first_node, 0, sizeof(*first_node));
769 for (i = 0; i < run_size; i++) {
770 buf = malloc(64);
771 num = next_key(i, max_key);
772 // num = i;
773 sprintf(buf, "string-%d", num);
774 // printf("insert %d\n", num);
775 ins.objectid = num;
776 ins.offset = 0;
777 ins.flags = 0;
778 ret = insert_item(&root, &ins, buf, strlen(buf));
779 if (!ret)
780 tree_size++;
781 }
782 srand(55);
783 for (i = 0; i < run_size; i++) {
784 num = next_key(i, max_key);
785 ins.objectid = num;
786 ins.offset = 0;
787 ins.flags = 0;
788 init_path(&path);
789 ret = search_slot(&root, &ins, &path);
790 if (ret) {
791 print_tree(root.node);
792 printf("unable to find %d\n", num);
793 exit(1);
794 }
795 }
796 printf("node %p level %d total ptrs %d free spc %lu\n", root.node,
797 node_level(root.node->header.flags), root.node->header.nritems,
798 NODEPTRS_PER_BLOCK - root.node->header.nritems);
799 // print_tree(root.node);
800 printf("all searches good\n");
801 i = 0;
802 srand(55);
803 for (i = 0; i < run_size; i++) {
804 num = next_key(i, max_key);
805 ins.objectid = num;
806 del_item(&root, &ins);
807 }
808 print_tree(root.node);
809 return 0;
810}
generated by cgit v1.2.2 (git 2.25.0) at 2024-12-04 12:30:23 -0500