git.ozlabs.org Git - ccan/blob - ccan/btree/btree.c

   1 /*
   2         Copyright (c) 2010  Joseph A. Adams
   3         All rights reserved.
   4
   5         Redistribution and use in source and binary forms, with or without
   6         modification, are permitted provided that the following conditions
   7         are met:
   8         1. Redistributions of source code must retain the above copyright
   9            notice, this list of conditions and the following disclaimer.
  10         2. Redistributions in binary form must reproduce the above copyright
  11            notice, this list of conditions and the following disclaimer in the
  12            documentation and/or other materials provided with the distribution.
  13         3. The name of the author may not be used to endorse or promote products
  14            derived from this software without specific prior written permission.
  15
  16         THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  17         IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  18         OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  19         IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  20         INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  21         NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  22         DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  23         THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  24         (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  25         THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  26 */
  27
  28 #include "btree.h"
  29
  30 #include <assert.h>
  31 #include <stdlib.h>
  32 #include <stdio.h>
  33
  34 #define MAX (BTREE_ITEM_MAX)
  35 #define MIN (BTREE_ITEM_MAX >> 1)
  36
  37 static struct btree_node *node_alloc(int internal);
  38 static void node_delete(struct btree_node *node, struct btree *btree);
  39
  40 static void branch_begin(btree_iterator iter);
  41 static void branch_end(btree_iterator iter);
  42 static void begin_end_lr(btree_iterator iter, struct btree_node *node, int lr);
  43
  44 /*
  45  * If iter->node has parent, returns 1 and ascends the iterator such that
  46  * iter->node->branch[iter->k] will be what iter->node was.
  47  *
  48  * If iter->node does not have a parent (is a root), returns 0 and leaves the
  49  * iterator untouched.
  50  */
  51 #define ascend(iter) ((iter)->node->parent \
  52         ? (iter)->k = (iter)->node->k, (iter)->node = (iter)->node->parent, 1 \
  53         : 0)
  54
  55 static void node_insert(const void *x, struct btree_node *xr,
  56                                 struct btree_node *p, unsigned int k);
  57 static void node_split(const void **x, struct btree_node **xr,
  58                                 struct btree_node *p, unsigned int k);
  59
  60 static void node_remove_leaf_item(struct btree_node *node, unsigned int k);
  61 void node_restore(struct btree_node *node, unsigned int k);
  62
  63 static int node_walk_backward(const struct btree_node *node,
  64                                 btree_action_t action, void *ctx);
  65 static int node_walk_forward(const struct btree_node *node,
  66                                 btree_action_t action, void *ctx);
  67
  68
  69 /************************* Public functions *************************/
  70
  71 struct btree *btree_new(btree_search_t search)
  72 {
  73         struct btree *btree = calloc(1, sizeof(struct btree));
  74         struct btree_node *node = node_alloc(0);
  75                 node->parent = NULL;
  76                 node->count = 0;
  77                 node->depth = 0;
  78         btree->root = node;
  79         btree->search = search;
  80         btree->multi = false;
  81         return btree;
  82 }
  83
  84 void btree_delete(struct btree *btree)
  85 {
  86         node_delete(btree->root, btree);
  87         free(btree);
  88 }
  89
  90 bool btree_insert(struct btree *btree, const void *item)
  91 {
  92         btree_iterator iter;
  93
  94         if (btree_find_last(btree, item, iter) && !btree->multi)
  95                 return false;
  96
  97         btree_insert_at(iter, item);
  98         return true;
  99 }
 100
 101 bool btree_remove(struct btree *btree, const void *key)
 102 {
 103         btree_iterator iter;
 104         bool success = false;
 105         bool multi = btree->multi;
 106
 107         do {
 108                 if (btree_find_first(btree, key, iter)) {
 109                         btree_remove_at(iter);
 110                         success = true;
 111                 }
 112         } while (multi);
 113
 114         return success;
 115 }
 116
 117 void *btree_lookup(struct btree *btree, const void *key)
 118 {
 119         btree_iterator iter;
 120
 121         if (btree_find_first(btree, key, iter))
 122                 return iter->item;
 123
 124         return NULL;
 125 }
 126
 127 int btree_begin_end_lr(const struct btree *btree, btree_iterator iter, int lr)
 128 {
 129         struct btree_node *node;
 130
 131         iter->btree = (struct btree *)btree;
 132         begin_end_lr(iter, btree->root, lr);
 133
 134         /* Set iter->item if any items exist. */
 135         node = iter->node;
 136         if (node->count) {
 137                 iter->item = (void*)node->item[iter->k - lr];
 138                 return 1;
 139         }
 140
 141         return 0;
 142 }
 143
 144 int btree_deref(btree_iterator iter)
 145 {
 146         if (iter->k >= iter->node->count) {
 147                 struct btree_iterator_s tmp = *iter;
 148                 do {
 149                         if (!ascend(iter)) {
 150                                 *iter = tmp;
 151                                 return 0;
 152                         }
 153                 } while (iter->k >= iter->node->count);
 154         }
 155
 156         iter->item = (void*)iter->node->item[iter->k];
 157         return 1;
 158 }
 159
 160 int btree_prev(btree_iterator iter)
 161 {
 162         if (iter->node->depth) {
 163                 branch_end(iter);
 164         } else if (iter->k == 0) {
 165                 struct btree_iterator_s tmp = *iter;
 166                 do {
 167                         if (!ascend(iter)) {
 168                                 *iter = tmp;
 169                                 return 0;
 170                         }
 171                 } while (iter->k == 0);
 172         }
 173
 174         iter->item = (void*)iter->node->item[--iter->k];
 175         return 1;
 176 }
 177
 178 int btree_next(btree_iterator iter)
 179 {
 180         int ret = btree_deref(iter);
 181         if (ret) {
 182                 iter->k++;
 183                 if (iter->node->depth)
 184                         branch_begin(iter);
 185         }
 186         return ret;
 187 }
 188
 189 int btree_find_lr(const struct btree *btree, const void *key,
 190                                 btree_iterator iter, int lr)
 191 {
 192         struct btree_node *node = btree->root;
 193         unsigned int k;
 194         unsigned int depth;
 195         int found = 0;
 196
 197         iter->btree = (struct btree *)btree;
 198         iter->item = NULL;
 199
 200         depth = node->depth;
 201         for (;;) {
 202                 int f = 0;
 203                 k = btree->search(key, node->item, node->count, lr, &f);
 204
 205                 if (f) {
 206                         iter->item = (void*)node->item[k - lr];
 207                         found = 1;
 208                 }
 209                 if (!depth--)
 210                         break;
 211
 212                 node = node->branch[k];
 213         }
 214
 215         iter->node = node;
 216         iter->k = k;
 217
 218         return found;
 219 }
 220
 221 int btree_walk_backward(const struct btree *btree,
 222                                 btree_action_t action, void *ctx)
 223 {
 224         return node_walk_backward(btree->root, action, ctx);
 225 }
 226
 227 int btree_walk_forward(const struct btree *btree,
 228                                 btree_action_t action, void *ctx)
 229 {
 230         return node_walk_forward(btree->root, action, ctx);
 231 }
 232
 233 void btree_insert_at(btree_iterator iter, const void *item)
 234 {
 235         const void *x = item;
 236         struct btree_node *xr = NULL;
 237         struct btree_node *p;
 238         struct btree *btree = iter->btree;
 239
 240         /* btree_insert_at always sets iter->item to item. */
 241         iter->item = (void*)item;
 242
 243         /*
 244          * If node is not a leaf, fall to the end of the left branch of item[k]
 245          * so that it will be a leaf. This does not modify the iterator's logical
 246          * position.
 247          */
 248         if (iter->node->depth)
 249                 branch_end(iter);
 250
 251         /*
 252          * First try inserting item into this node.
 253          * If it's too big, split it, and repeat by
 254          * trying to insert the median and right subtree into parent.
 255          */
 256         if (iter->node->count < MAX) {
 257                 node_insert(x, xr, iter->node, iter->k);
 258                 goto finished;
 259         } else {
 260                 for (;;) {
 261                         node_split(&x, &xr, iter->node, iter->k);
 262
 263                         if (!ascend(iter))
 264                                 break;
 265
 266                         if (iter->node->count < MAX) {
 267                                 node_insert(x, xr, iter->node, iter->k);
 268                                 goto finished;
 269                         }
 270                 }
 271
 272                 /*
 273                  * If splitting came all the way up to the root, create a new root whose
 274                  * left branch is the current root, median is x, and right branch is the
 275                  * half split off from the root.
 276                  */
 277                 assert(iter->node == btree->root);
 278                 p = node_alloc(1);
 279                 p->parent = NULL;
 280                 p->count = 1;
 281                 p->depth = btree->root->depth + 1;
 282                 p->item[0] = x;
 283                 p->branch[0] = btree->root;
 284                         btree->root->parent = p;
 285                         btree->root->k = 0;
 286                 p->branch[1] = xr;
 287                         xr->parent = p;
 288                         xr->k = 1;
 289                 btree->root = p;
 290         }
 291
 292 finished:
 293         btree->count++;
 294         iter->node = NULL;
 295 }
 296
 297 int btree_remove_at(btree_iterator iter)
 298 {
 299         struct btree *btree = iter->btree;
 300         struct btree_node *root;
 301
 302         if (!btree_deref(iter))
 303                 return 0;
 304
 305         if (!iter->node->depth) {
 306                 node_remove_leaf_item(iter->node, iter->k);
 307                 if (iter->node->count >= MIN || !iter->node->parent)
 308                         goto finished;
 309         } else {
 310                 /*
 311                  * We can't remove an item from an internal node, so we'll replace it
 312                  * with its successor (which will always be in a leaf), then remove
 313                  * the original copy of the successor.
 314                  */
 315
 316                 /* Save pointer to condemned item. */
 317                 const void **x = &iter->node->item[iter->k];
 318
 319                 /* Descend to successor. */
 320                 iter->k++;
 321                 branch_begin(iter);
 322
 323                 /* Replace condemned item with successor. */
 324                 *x = iter->node->item[0];
 325
 326                 /* Remove successor. */
 327                 node_remove_leaf_item(iter->node, 0);
 328         }
 329
 330         /*
 331          * Restore nodes that fall under their minimum count.  This may
 332          * propagate all the way up to the root.
 333          */
 334         for (;;) {
 335                 if (iter->node->count >= MIN)
 336                         goto finished;
 337                 if (!ascend(iter))
 338                         break;
 339                 node_restore(iter->node, iter->k);
 340         }
 341
 342         /*
 343          * If combining came all the way up to the root, and it has no more
 344          * dividers, delete it and make its only branch the root.
 345          */
 346         root = iter->node;
 347         assert(root == btree->root);
 348         assert(root->depth > 0);
 349         if (root->count == 0) {
 350                 btree->root = root->branch[0];
 351                 btree->root->parent = NULL;
 352                 free(root);
 353         }
 354
 355 finished:
 356         btree->count--;
 357         iter->node = NULL;
 358         return 1;
 359 }
 360
 361 /*
 362  * ascends iterator a until it matches iterator b's depth.
 363  *
 364  * Returns -1 if they end up on the same k (meaning a < b).
 365  * Returns 0 otherwise.
 366  */
 367 static int elevate(btree_iterator a, btree_iterator b)
 368 {
 369         while (a->node->depth < b->node->depth)
 370                 ascend(a);
 371
 372         if (a->k == b->k)
 373                 return -1;
 374         return 0;
 375 }
 376
 377 int btree_cmp_iters(const btree_iterator iter_a, const btree_iterator iter_b)
 378 {
 379         btree_iterator a = {*iter_a}, b = {*iter_b};
 380         int ad, bd;
 381
 382         ad = btree_deref(a);
 383         bd = btree_deref(b);
 384
 385         /* Check cases where one or both iterators are at the end. */
 386         if (!ad)
 387                 return bd ? 1 : 0;
 388         if (!bd)
 389                 return ad ? -1 : 0;
 390
 391         /* Bring iterators to the same depth. */
 392         if (a->node->depth < b->node->depth) {
 393                 if (elevate(a, b))
 394                         return -1;
 395         } else if (a->node->depth > b->node->depth) {
 396                 if (elevate(b, a))
 397                         return 1;
 398         }
 399
 400         /* Bring iterators to the same node. */
 401         while (a->node != b->node) {
 402                 ascend(a);
 403                 ascend(b);
 404         }
 405
 406         /* Now we can compare by k directly. */
 407         if (a->k < b->k)
 408                 return -1;
 409         if (a->k > b->k)
 410                 return 1;
 411
 412         return 0;
 413 }
 414
 415 /********************* Built-in ordering functions *******************/
 416
 417 btree_search_implement
 418 (
 419         btree_strcmp,
 420         char*,
 421         int c = strcmp(a, b),
 422         c == 0,
 423         c < 0
 424 )
 425
 426
 427 /************************* Private functions *************************/
 428
 429 static struct btree_node *node_alloc(int internal)
 430 {
 431         struct btree_node *node;
 432         size_t isize = internal
 433                 ? sizeof(struct btree_node*) * (BTREE_ITEM_MAX+1)
 434                 : 0;
 435         node = malloc(sizeof(struct btree_node) + isize);
 436         return node;
 437 }
 438
 439 static void node_delete(struct btree_node *node, struct btree *btree)
 440 {
 441         unsigned int i, count = node->count;
 442
 443         if (!node->depth) {
 444                 if (btree->destroy) {
 445                         for (i=0; i<count; i++)
 446                                 btree->destroy((void*)node->item[i], btree->destroy_ctx);
 447                 }
 448         } else {
 449                 for (i=0; i<count; i++) {
 450                         node_delete(node->branch[i], btree);
 451                         if (btree->destroy)
 452                                 btree->destroy((void*)node->item[i], btree->destroy_ctx);
 453                 }
 454                 node_delete(node->branch[count], btree);
 455         }
 456
 457         free(node);
 458 }
 459
 460 /* Set iter to beginning of branch pointed to by iter. */
 461 static void branch_begin(btree_iterator iter)
 462 {
 463         struct btree_node *node = iter->node->branch[iter->k];
 464         unsigned int depth = node->depth;
 465         while (depth--)
 466                 node = node->branch[0];
 467         iter->node = node;
 468         iter->k = 0;
 469 }
 470
 471 /* Set iter to end of branch pointed to by iter. */
 472 static void branch_end(btree_iterator iter)
 473 {
 474         struct btree_node *node = iter->node->branch[iter->k];
 475         unsigned int depth = node->depth;
 476         while (depth--)
 477                 node = node->branch[node->count];
 478         iter->node = node;
 479         iter->k = node->count;
 480 }
 481
 482 /* Traverse to the beginning or end of node, depending on lr. */
 483 static void begin_end_lr(btree_iterator iter, struct btree_node *node, int lr)
 484 {
 485         iter->node = node;
 486         iter->k = lr ? node->count : 0;
 487         if (node->depth)
 488                 (lr ? branch_end : branch_begin)(iter);
 489 }
 490
 491 /*
 492  * Inserts item x and right branch xr into node p at position k.
 493  *
 494  * Assumes p exists and has enough room.
 495  * Ignores xr if p is a leaf.
 496  */
 497 static void node_insert(const void *x, struct btree_node *xr,
 498                                 struct btree_node *p, unsigned int k)
 499 {
 500         unsigned int i;
 501
 502         for (i = p->count; i-- > k;)
 503                 p->item[i+1] = p->item[i];
 504         p->item[k] = x;
 505
 506         if (p->depth) {
 507                 k++;
 508                 for (i = p->count+1; i-- > k;) {
 509                         p->branch[i+1] = p->branch[i];
 510                         p->branch[i+1]->k = i+1;
 511                 }
 512                 p->branch[k] = xr;
 513                 xr->parent = p;
 514                 xr->k = k;
 515         }
 516
 517         p->count++;
 518 }
 519
 520 /*
 521  * Inserts item *x and subtree *xr into node p at position k, splitting it into
 522  * nodes p and *xr with median item *x.
 523  *
 524  * Assumes p->count == MAX.
 525  * Ignores original *xr if p is a leaf, but always sets it.
 526  */
 527 static void node_split(const void **x, struct btree_node **xr,
 528                                 struct btree_node *p, unsigned int k)
 529 {
 530         unsigned int i, split;
 531         struct btree_node *l = p, *r;
 532
 533         /*
 534          * If k <= MIN, item will be inserted into left subtree, so give l
 535          * fewer items initially.
 536          * Otherwise, item will be inserted into right subtree, so give r
 537          * fewer items initially.
 538          */
 539         if (k <= MIN)
 540                 split = MIN;
 541         else
 542                 split = MIN + 1;
 543
 544         /*
 545          * If l->depth is 0, allocate a leaf node.
 546          * Otherwise, allocate an internal node.
 547          */
 548         r = node_alloc(l->depth);
 549
 550         /* l and r will be siblings, so they will have the same parent and depth. */
 551         r->parent = l->parent;
 552         r->depth = l->depth;
 553
 554         /*
 555          * Initialize items/branches of right side.
 556          * Do not initialize r's leftmost branch yet because we don't know
 557          * whether it will be l's current rightmost branch or if *xr will
 558          * take its place.
 559          */
 560         for (i = split; i < MAX; i++)
 561                 r->item[i-split] = l->item[i];
 562         if (r->depth) {
 563                 for (i = split+1; i <= MAX; i++) {
 564                         r->branch[i-split] = l->branch[i];
 565                         r->branch[i-split]->parent = r;
 566                         r->branch[i-split]->k = i-split;
 567                 }
 568         }
 569
 570         /* Update counts. */
 571         l->count = split;
 572         r->count = MAX - split;
 573
 574         /*
 575          * The nodes are now split, but the key isn't inserted yet.
 576          *
 577          * Insert key into left or right half,
 578          * depending on which side it fell on.
 579          */
 580         if (k <= MIN)
 581                 node_insert(*x, *xr, l, k);
 582         else
 583                 node_insert(*x, *xr, r, k - split);
 584
 585         /*
 586          * Give l's rightmost branch to r because l's rightmost item
 587          * is going up to become the median.
 588          */
 589         if (r->depth) {
 590                 r->branch[0] = l->branch[l->count];
 591                 r->branch[0]->parent = r;
 592                 r->branch[0]->k = 0;
 593         }
 594
 595         /*
 596          * Take up l's rightmost item to make it the median.
 597          * That item's right branch is now r.
 598          */
 599         *x = l->item[--l->count];
 600         *xr = r;
 601 }
 602
 603 /*
 604  * Removes item k from node p, shifting successor items back and
 605  * decrementing the count.
 606  *
 607  * Assumes node p has the item k and is a leaf.
 608  */
 609 static void node_remove_leaf_item(struct btree_node *node, unsigned int k)
 610 {
 611         unsigned int i;
 612         for (i = k+1; i < node->count; i++)
 613                 node->item[i-1] = node->item[i];
 614         node->count--;
 615 }
 616
 617 static void move_left(struct btree_node *node, unsigned int k);
 618 static void move_right(struct btree_node *node, unsigned int k);
 619 static void combine(struct btree_node *node, unsigned int k);
 620
 621 /*
 622  * Fixes node->branch[k]'s problem of having one less than MIN items.
 623  * May or may not cause node to fall below MIN items, depending on whether
 624  * two branches are combined or not.
 625  */
 626 void node_restore(struct btree_node *node, unsigned int k)
 627 {
 628         if (k == 0) {
 629                 if (node->branch[1]->count > MIN)
 630                         move_left(node, 0);
 631                 else
 632                         combine(node, 0);
 633         } else if (k == node->count) {
 634                 if (node->branch[k-1]->count > MIN)
 635                         move_right(node, k-1);
 636                 else
 637                         combine(node, k-1);
 638         } else if (node->branch[k-1]->count > MIN) {
 639                 move_right(node, k-1);
 640         } else if (node->branch[k+1]->count > MIN) {
 641                 move_left(node, k);
 642         } else {
 643                 combine(node, k-1);
 644         }
 645 }
 646
 647 static void move_left(struct btree_node *node, unsigned int k)
 648 {
 649         struct btree_node *l = node->branch[k], *r = node->branch[k+1], *mv;
 650         unsigned int i;
 651
 652         l->item[l->count] = node->item[k];
 653         node->item[k] = r->item[0];
 654         for (i = 1; i < r->count; i++)
 655                 r->item[i-1] = r->item[i];
 656
 657         if (r->depth) {
 658                 mv = r->branch[0];
 659                 l->branch[l->count+1] = mv;
 660                 mv->parent = l;
 661                 mv->k = l->count+1;
 662
 663                 for (i = 1; i <= r->count; i++) {
 664                         r->branch[i-1] = r->branch[i];
 665                         r->branch[i-1]->k = i-1;
 666                 }
 667         }
 668
 669         l->count++;
 670         r->count--;
 671 }
 672
 673 static void move_right(struct btree_node *node, unsigned int k)
 674 {
 675         struct btree_node *l = node->branch[k], *r = node->branch[k+1];
 676         unsigned int i;
 677
 678         for (i = r->count; i--;)
 679                 r->item[i+1] = r->item[i];
 680         r->item[0] = node->item[k];
 681         node->item[k] = l->item[l->count-1];
 682
 683         if (r->depth) {
 684                 for (i = r->count+1; i--;) {
 685                         r->branch[i+1] = r->branch[i];
 686                         r->branch[i+1]->k = i+1;
 687                 }
 688                 r->branch[0] = l->branch[l->count];
 689                 r->branch[0]->parent = r;
 690                 r->branch[0]->k = 0;
 691         }
 692
 693         l->count--;
 694         r->count++;
 695 }
 696
 697 /* Combine node->branch[k] and node->branch[k+1]. */
 698 static void combine(struct btree_node *node, unsigned int k)
 699 {
 700         struct btree_node *l = node->branch[k], *r = node->branch[k+1], *mv;
 701         const void **o = &l->item[l->count];
 702         unsigned int i;
 703
 704         //append node->item[k] followed by right node's items to left node
 705         *o++ = node->item[k];
 706         for (i=0; i<r->count; i++)
 707                 *o++ = r->item[i];
 708
 709         //if applicable, append right node's branches to left node
 710         if (r->depth) {
 711                 for (i=0; i<=r->count; i++) {
 712                         mv = r->branch[i];
 713                         l->branch[l->count + i + 1] = mv;
 714                         mv->parent = l;
 715                         mv->k = l->count + i + 1;
 716                 }
 717         }
 718
 719         //remove k and its right branch from parent node
 720         for (i = k+1; i < node->count; i++) {
 721                 node->item[i-1] = node->item[i];
 722                 node->branch[i] = node->branch[i+1];
 723                 node->branch[i]->k = i;
 724         }
 725
 726         //don't forget to update the left and parent node's counts and to free the right node
 727         l->count += r->count + 1;
 728         node->count--;
 729         free(r);
 730 }
 731
 732 static int node_walk_backward(const struct btree_node *node,
 733                                 btree_action_t action, void *ctx)
 734 {
 735         unsigned int i, count = node->count;
 736
 737         if (!node->depth) {
 738                 for (i=count; i--;)
 739                         if (!action((void*)node->item[i], ctx))
 740                                 return 0;
 741         } else {
 742                 if (!node_walk_backward(node->branch[count], action, ctx))
 743                         return 0;
 744                 for (i=count; i--;) {
 745                         if (!action((void*)node->item[i], ctx))
 746                                 return 0;
 747                         if (!node_walk_backward(node->branch[i], action, ctx))
 748                                 return 0;
 749                 }
 750         }
 751
 752         return 1;
 753 }
 754
 755 static int node_walk_forward(const struct btree_node *node,
 756                                 btree_action_t action, void *ctx)
 757 {
 758         unsigned int i, count = node->count;
 759
 760         if (!node->depth) {
 761                 for (i=0; i<count; i++)
 762                         if (!action((void*)node->item[i], ctx))
 763                                 return 0;
 764         } else {
 765                 for (i=0; i<count; i++) {
 766                         if (!node_walk_forward(node->branch[i], action, ctx))
 767                                 return 0;
 768                         if (!action((void*)node->item[i], ctx))
 769                                 return 0;
 770                 }
 771                 if (!node_walk_forward(node->branch[count], action, ctx))
 772                         return 0;
 773         }
 774
 775         return 1;
 776 }