fs/btrfs/ctree.c

   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                         }
 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
 635 int 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
 691 void 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 }
 710 void 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 */
 747 int next_key(int i, int max_key) {
 748         return rand() % max_key;
 749         // return i;
 750 }
 751
 752 int 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 }