root/lib/btree.c

DEFINITIONS

1. btree_alloc
2. btree_free
3. btree_node_alloc
4. longcmp
5. longcpy
6. longset
7. dec_key
8. bkey
9. bval
10. setkey
11. setval
12. clearpair
13. __btree_init
14. btree_init_mempool
15. btree_init
16. btree_destroy
17. btree_last
18. keycmp
19. keyzero
20. btree_lookup
21. btree_update
22. btree_get_prev
23. getpos
24. getfill
25. find_level
26. btree_grow
27. btree_shrink
28. btree_insert_level
29. btree_insert
30. merge
31. rebalance
32. btree_remove_level
33. btree_remove
34. btree_merge
35. __btree_for_each
36. empty
37. visitorl
38. visitor32
39. visitor64
40. visitor128
41. btree_visitor
42. btree_grim_visitor
43. btree_module_init
44. btree_module_exit

   1 // SPDX-License-Identifier: GPL-2.0-only
   2 /*
   3  * lib/btree.c  - Simple In-memory B+Tree
   4  *
   5  * Copyright (c) 2007-2008 Joern Engel <joern@purestorage.com>
   6  * Bits and pieces stolen from Peter Zijlstra's code, which is
   7  * Copyright 2007, Red Hat Inc. Peter Zijlstra
   8  *
   9  * see http://programming.kicks-ass.net/kernel-patches/vma_lookup/btree.patch
  10  *
  11  * A relatively simple B+Tree implementation.  I have written it as a learning
  12  * exercise to understand how B+Trees work.  Turned out to be useful as well.
  13  *
  14  * B+Trees can be used similar to Linux radix trees (which don't have anything
  15  * in common with textbook radix trees, beware).  Prerequisite for them working
  16  * well is that access to a random tree node is much faster than a large number
  17  * of operations within each node.
  18  *
  19  * Disks have fulfilled the prerequisite for a long time.  More recently DRAM
  20  * has gained similar properties, as memory access times, when measured in cpu
  21  * cycles, have increased.  Cacheline sizes have increased as well, which also
  22  * helps B+Trees.
  23  *
  24  * Compared to radix trees, B+Trees are more efficient when dealing with a
  25  * sparsely populated address space.  Between 25% and 50% of the memory is
  26  * occupied with valid pointers.  When densely populated, radix trees contain
  27  * ~98% pointers - hard to beat.  Very sparse radix trees contain only ~2%
  28  * pointers.
  29  *
  30  * This particular implementation stores pointers identified by a long value.
  31  * Storing NULL pointers is illegal, lookup will return NULL when no entry
  32  * was found.
  33  *
  34  * A tricks was used that is not commonly found in textbooks.  The lowest
  35  * values are to the right, not to the left.  All used slots within a node
  36  * are on the left, all unused slots contain NUL values.  Most operations
  37  * simply loop once over all slots and terminate on the first NUL.
  38  */
  39 
  40 #include <linux/btree.h>
  41 #include <linux/cache.h>
  42 #include <linux/kernel.h>
  43 #include <linux/slab.h>
  44 #include <linux/module.h>
  45 
  46 #define MAX(a, b) ((a) > (b) ? (a) : (b))
  47 #define NODESIZE MAX(L1_CACHE_BYTES, 128)
  48 
  49 struct btree_geo {
  50         int keylen;
  51         int no_pairs;
  52         int no_longs;
  53 };
  54 
  55 struct btree_geo btree_geo32 = {
  56         .keylen = 1,
  57         .no_pairs = NODESIZE / sizeof(long) / 2,
  58         .no_longs = NODESIZE / sizeof(long) / 2,
  59 };
  60 EXPORT_SYMBOL_GPL(btree_geo32);
  61 
  62 #define LONG_PER_U64 (64 / BITS_PER_LONG)
  63 struct btree_geo btree_geo64 = {
  64         .keylen = LONG_PER_U64,
  65         .no_pairs = NODESIZE / sizeof(long) / (1 + LONG_PER_U64),
  66         .no_longs = LONG_PER_U64 * (NODESIZE / sizeof(long) / (1 + LONG_PER_U64)),
  67 };
  68 EXPORT_SYMBOL_GPL(btree_geo64);
  69 
  70 struct btree_geo btree_geo128 = {
  71         .keylen = 2 * LONG_PER_U64,
  72         .no_pairs = NODESIZE / sizeof(long) / (1 + 2 * LONG_PER_U64),
  73         .no_longs = 2 * LONG_PER_U64 * (NODESIZE / sizeof(long) / (1 + 2 * LONG_PER_U64)),
  74 };
  75 EXPORT_SYMBOL_GPL(btree_geo128);
  76 
  77 #define MAX_KEYLEN      (2 * LONG_PER_U64)
  78 
  79 static struct kmem_cache *btree_cachep;
  80 
  81 void *btree_alloc(gfp_t gfp_mask, void *pool_data)
  82 {
  83         return kmem_cache_alloc(btree_cachep, gfp_mask);
  84 }
  85 EXPORT_SYMBOL_GPL(btree_alloc);
  86 
  87 void btree_free(void *element, void *pool_data)
  88 {
  89         kmem_cache_free(btree_cachep, element);
  90 }
  91 EXPORT_SYMBOL_GPL(btree_free);
  92 
  93 static unsigned long *btree_node_alloc(struct btree_head *head, gfp_t gfp)
  94 {
  95         unsigned long *node;
  96 
  97         node = mempool_alloc(head->mempool, gfp);
  98         if (likely(node))
  99                 memset(node, 0, NODESIZE);
 100         return node;
 101 }
 102 
 103 static int longcmp(const unsigned long *l1, const unsigned long *l2, size_t n)
 104 {
 105         size_t i;
 106 
 107         for (i = 0; i < n; i++) {
 108                 if (l1[i] < l2[i])
 109                         return -1;
 110                 if (l1[i] > l2[i])
 111                         return 1;
 112         }
 113         return 0;
 114 }
 115 
 116 static unsigned long *longcpy(unsigned long *dest, const unsigned long *src,
 117                 size_t n)
 118 {
 119         size_t i;
 120 
 121         for (i = 0; i < n; i++)
 122                 dest[i] = src[i];
 123         return dest;
 124 }
 125 
 126 static unsigned long *longset(unsigned long *s, unsigned long c, size_t n)
 127 {
 128         size_t i;
 129 
 130         for (i = 0; i < n; i++)
 131                 s[i] = c;
 132         return s;
 133 }
 134 
 135 static void dec_key(struct btree_geo *geo, unsigned long *key)
 136 {
 137         unsigned long val;
 138         int i;
 139 
 140         for (i = geo->keylen - 1; i >= 0; i--) {
 141                 val = key[i];
 142                 key[i] = val - 1;
 143                 if (val)
 144                         break;
 145         }
 146 }
 147 
 148 static unsigned long *bkey(struct btree_geo *geo, unsigned long *node, int n)
 149 {
 150         return &node[n * geo->keylen];
 151 }
 152 
 153 static void *bval(struct btree_geo *geo, unsigned long *node, int n)
 154 {
 155         return (void *)node[geo->no_longs + n];
 156 }
 157 
 158 static void setkey(struct btree_geo *geo, unsigned long *node, int n,
 159                    unsigned long *key)
 160 {
 161         longcpy(bkey(geo, node, n), key, geo->keylen);
 162 }
 163 
 164 static void setval(struct btree_geo *geo, unsigned long *node, int n,
 165                    void *val)
 166 {
 167         node[geo->no_longs + n] = (unsigned long) val;
 168 }
 169 
 170 static void clearpair(struct btree_geo *geo, unsigned long *node, int n)
 171 {
 172         longset(bkey(geo, node, n), 0, geo->keylen);
 173         node[geo->no_longs + n] = 0;
 174 }
 175 
 176 static inline void __btree_init(struct btree_head *head)
 177 {
 178         head->node = NULL;
 179         head->height = 0;
 180 }
 181 
 182 void btree_init_mempool(struct btree_head *head, mempool_t *mempool)
 183 {
 184         __btree_init(head);
 185         head->mempool = mempool;
 186 }
 187 EXPORT_SYMBOL_GPL(btree_init_mempool);
 188 
 189 int btree_init(struct btree_head *head)
 190 {
 191         __btree_init(head);
 192         head->mempool = mempool_create(0, btree_alloc, btree_free, NULL);
 193         if (!head->mempool)
 194                 return -ENOMEM;
 195         return 0;
 196 }
 197 EXPORT_SYMBOL_GPL(btree_init);
 198 
 199 void btree_destroy(struct btree_head *head)
 200 {
 201         mempool_free(head->node, head->mempool);
 202         mempool_destroy(head->mempool);
 203         head->mempool = NULL;
 204 }
 205 EXPORT_SYMBOL_GPL(btree_destroy);
 206 
 207 void *btree_last(struct btree_head *head, struct btree_geo *geo,
 208                  unsigned long *key)
 209 {
 210         int height = head->height;
 211         unsigned long *node = head->node;
 212 
 213         if (height == 0)
 214                 return NULL;
 215 
 216         for ( ; height > 1; height--)
 217                 node = bval(geo, node, 0);
 218 
 219         longcpy(key, bkey(geo, node, 0), geo->keylen);
 220         return bval(geo, node, 0);
 221 }
 222 EXPORT_SYMBOL_GPL(btree_last);
 223 
 224 static int keycmp(struct btree_geo *geo, unsigned long *node, int pos,
 225                   unsigned long *key)
 226 {
 227         return longcmp(bkey(geo, node, pos), key, geo->keylen);
 228 }
 229 
 230 static int keyzero(struct btree_geo *geo, unsigned long *key)
 231 {
 232         int i;
 233 
 234         for (i = 0; i < geo->keylen; i++)
 235                 if (key[i])
 236                         return 0;
 237 
 238         return 1;
 239 }
 240 
 241 void *btree_lookup(struct btree_head *head, struct btree_geo *geo,
 242                 unsigned long *key)
 243 {
 244         int i, height = head->height;
 245         unsigned long *node = head->node;
 246 
 247         if (height == 0)
 248                 return NULL;
 249 
 250         for ( ; height > 1; height--) {
 251                 for (i = 0; i < geo->no_pairs; i++)
 252                         if (keycmp(geo, node, i, key) <= 0)
 253                                 break;
 254                 if (i == geo->no_pairs)
 255                         return NULL;
 256                 node = bval(geo, node, i);
 257                 if (!node)
 258                         return NULL;
 259         }
 260 
 261         if (!node)
 262                 return NULL;
 263 
 264         for (i = 0; i < geo->no_pairs; i++)
 265                 if (keycmp(geo, node, i, key) == 0)
 266                         return bval(geo, node, i);
 267         return NULL;
 268 }
 269 EXPORT_SYMBOL_GPL(btree_lookup);
 270 
 271 int btree_update(struct btree_head *head, struct btree_geo *geo,
 272                  unsigned long *key, void *val)
 273 {
 274         int i, height = head->height;
 275         unsigned long *node = head->node;
 276 
 277         if (height == 0)
 278                 return -ENOENT;
 279 
 280         for ( ; height > 1; height--) {
 281                 for (i = 0; i < geo->no_pairs; i++)
 282                         if (keycmp(geo, node, i, key) <= 0)
 283                                 break;
 284                 if (i == geo->no_pairs)
 285                         return -ENOENT;
 286                 node = bval(geo, node, i);
 287                 if (!node)
 288                         return -ENOENT;
 289         }
 290 
 291         if (!node)
 292                 return -ENOENT;
 293 
 294         for (i = 0; i < geo->no_pairs; i++)
 295                 if (keycmp(geo, node, i, key) == 0) {
 296                         setval(geo, node, i, val);
 297                         return 0;
 298                 }
 299         return -ENOENT;
 300 }
 301 EXPORT_SYMBOL_GPL(btree_update);
 302 
 303 /*
 304  * Usually this function is quite similar to normal lookup.  But the key of
 305  * a parent node may be smaller than the smallest key of all its siblings.
 306  * In such a case we cannot just return NULL, as we have only proven that no
 307  * key smaller than __key, but larger than this parent key exists.
 308  * So we set __key to the parent key and retry.  We have to use the smallest
 309  * such parent key, which is the last parent key we encountered.
 310  */
 311 void *btree_get_prev(struct btree_head *head, struct btree_geo *geo,
 312                      unsigned long *__key)
 313 {
 314         int i, height;
 315         unsigned long *node, *oldnode;
 316         unsigned long *retry_key = NULL, key[MAX_KEYLEN];
 317 
 318         if (keyzero(geo, __key))
 319                 return NULL;
 320 
 321         if (head->height == 0)
 322                 return NULL;
 323         longcpy(key, __key, geo->keylen);
 324 retry:
 325         dec_key(geo, key);
 326 
 327         node = head->node;
 328         for (height = head->height ; height > 1; height--) {
 329                 for (i = 0; i < geo->no_pairs; i++)
 330                         if (keycmp(geo, node, i, key) <= 0)
 331                                 break;
 332                 if (i == geo->no_pairs)
 333                         goto miss;
 334                 oldnode = node;
 335                 node = bval(geo, node, i);
 336                 if (!node)
 337                         goto miss;
 338                 retry_key = bkey(geo, oldnode, i);
 339         }
 340 
 341         if (!node)
 342                 goto miss;
 343 
 344         for (i = 0; i < geo->no_pairs; i++) {
 345                 if (keycmp(geo, node, i, key) <= 0) {
 346                         if (bval(geo, node, i)) {
 347                                 longcpy(__key, bkey(geo, node, i), geo->keylen);
 348                                 return bval(geo, node, i);
 349                         } else
 350                                 goto miss;
 351                 }
 352         }
 353 miss:
 354         if (retry_key) {
 355                 longcpy(key, retry_key, geo->keylen);
 356                 retry_key = NULL;
 357                 goto retry;
 358         }
 359         return NULL;
 360 }
 361 EXPORT_SYMBOL_GPL(btree_get_prev);
 362 
 363 static int getpos(struct btree_geo *geo, unsigned long *node,
 364                 unsigned long *key)
 365 {
 366         int i;
 367 
 368         for (i = 0; i < geo->no_pairs; i++) {
 369                 if (keycmp(geo, node, i, key) <= 0)
 370                         break;
 371         }
 372         return i;
 373 }
 374 
 375 static int getfill(struct btree_geo *geo, unsigned long *node, int start)
 376 {
 377         int i;
 378 
 379         for (i = start; i < geo->no_pairs; i++)
 380                 if (!bval(geo, node, i))
 381                         break;
 382         return i;
 383 }
 384 
 385 /*
 386  * locate the correct leaf node in the btree
 387  */
 388 static unsigned long *find_level(struct btree_head *head, struct btree_geo *geo,
 389                 unsigned long *key, int level)
 390 {
 391         unsigned long *node = head->node;
 392         int i, height;
 393 
 394         for (height = head->height; height > level; height--) {
 395                 for (i = 0; i < geo->no_pairs; i++)
 396                         if (keycmp(geo, node, i, key) <= 0)
 397                                 break;
 398 
 399                 if ((i == geo->no_pairs) || !bval(geo, node, i)) {
 400                         /* right-most key is too large, update it */
 401                         /* FIXME: If the right-most key on higher levels is
 402                          * always zero, this wouldn't be necessary. */
 403                         i--;
 404                         setkey(geo, node, i, key);
 405                 }
 406                 BUG_ON(i < 0);
 407                 node = bval(geo, node, i);
 408         }
 409         BUG_ON(!node);
 410         return node;
 411 }
 412 
 413 static int btree_grow(struct btree_head *head, struct btree_geo *geo,
 414                       gfp_t gfp)
 415 {
 416         unsigned long *node;
 417         int fill;
 418 
 419         node = btree_node_alloc(head, gfp);
 420         if (!node)
 421                 return -ENOMEM;
 422         if (head->node) {
 423                 fill = getfill(geo, head->node, 0);
 424                 setkey(geo, node, 0, bkey(geo, head->node, fill - 1));
 425                 setval(geo, node, 0, head->node);
 426         }
 427         head->node = node;
 428         head->height++;
 429         return 0;
 430 }
 431 
 432 static void btree_shrink(struct btree_head *head, struct btree_geo *geo)
 433 {
 434         unsigned long *node;
 435         int fill;
 436 
 437         if (head->height <= 1)
 438                 return;
 439 
 440         node = head->node;
 441         fill = getfill(geo, node, 0);
 442         BUG_ON(fill > 1);
 443         head->node = bval(geo, node, 0);
 444         head->height--;
 445         mempool_free(node, head->mempool);
 446 }
 447 
 448 static int btree_insert_level(struct btree_head *head, struct btree_geo *geo,
 449                               unsigned long *key, void *val, int level,
 450                               gfp_t gfp)
 451 {
 452         unsigned long *node;
 453         int i, pos, fill, err;
 454 
 455         BUG_ON(!val);
 456         if (head->height < level) {
 457                 err = btree_grow(head, geo, gfp);
 458                 if (err)
 459                         return err;
 460         }
 461 
 462 retry:
 463         node = find_level(head, geo, key, level);
 464         pos = getpos(geo, node, key);
 465         fill = getfill(geo, node, pos);
 466         /* two identical keys are not allowed */
 467         BUG_ON(pos < fill && keycmp(geo, node, pos, key) == 0);
 468 
 469         if (fill == geo->no_pairs) {
 470                 /* need to split node */
 471                 unsigned long *new;
 472 
 473                 new = btree_node_alloc(head, gfp);
 474                 if (!new)
 475                         return -ENOMEM;
 476                 err = btree_insert_level(head, geo,
 477                                 bkey(geo, node, fill / 2 - 1),
 478                                 new, level + 1, gfp);
 479                 if (err) {
 480                         mempool_free(new, head->mempool);
 481                         return err;
 482                 }
 483                 for (i = 0; i < fill / 2; i++) {
 484                         setkey(geo, new, i, bkey(geo, node, i));
 485                         setval(geo, new, i, bval(geo, node, i));
 486                         setkey(geo, node, i, bkey(geo, node, i + fill / 2));
 487                         setval(geo, node, i, bval(geo, node, i + fill / 2));
 488                         clearpair(geo, node, i + fill / 2);
 489                 }
 490                 if (fill & 1) {
 491                         setkey(geo, node, i, bkey(geo, node, fill - 1));
 492                         setval(geo, node, i, bval(geo, node, fill - 1));
 493                         clearpair(geo, node, fill - 1);
 494                 }
 495                 goto retry;
 496         }
 497         BUG_ON(fill >= geo->no_pairs);
 498 
 499         /* shift and insert */
 500         for (i = fill; i > pos; i--) {
 501                 setkey(geo, node, i, bkey(geo, node, i - 1));
 502                 setval(geo, node, i, bval(geo, node, i - 1));
 503         }
 504         setkey(geo, node, pos, key);
 505         setval(geo, node, pos, val);
 506 
 507         return 0;
 508 }
 509 
 510 int btree_insert(struct btree_head *head, struct btree_geo *geo,
 511                 unsigned long *key, void *val, gfp_t gfp)
 512 {
 513         BUG_ON(!val);
 514         return btree_insert_level(head, geo, key, val, 1, gfp);
 515 }
 516 EXPORT_SYMBOL_GPL(btree_insert);
 517 
 518 static void *btree_remove_level(struct btree_head *head, struct btree_geo *geo,
 519                 unsigned long *key, int level);
 520 static void merge(struct btree_head *head, struct btree_geo *geo, int level,
 521                 unsigned long *left, int lfill,
 522                 unsigned long *right, int rfill,
 523                 unsigned long *parent, int lpos)
 524 {
 525         int i;
 526 
 527         for (i = 0; i < rfill; i++) {
 528                 /* Move all keys to the left */
 529                 setkey(geo, left, lfill + i, bkey(geo, right, i));
 530                 setval(geo, left, lfill + i, bval(geo, right, i));
 531         }
 532         /* Exchange left and right child in parent */
 533         setval(geo, parent, lpos, right);
 534         setval(geo, parent, lpos + 1, left);
 535         /* Remove left (formerly right) child from parent */
 536         btree_remove_level(head, geo, bkey(geo, parent, lpos), level + 1);
 537         mempool_free(right, head->mempool);
 538 }
 539 
 540 static void rebalance(struct btree_head *head, struct btree_geo *geo,
 541                 unsigned long *key, int level, unsigned long *child, int fill)
 542 {
 543         unsigned long *parent, *left = NULL, *right = NULL;
 544         int i, no_left, no_right;
 545 
 546         if (fill == 0) {
 547                 /* Because we don't steal entries from a neighbour, this case
 548                  * can happen.  Parent node contains a single child, this
 549                  * node, so merging with a sibling never happens.
 550                  */
 551                 btree_remove_level(head, geo, key, level + 1);
 552                 mempool_free(child, head->mempool);
 553                 return;
 554         }
 555 
 556         parent = find_level(head, geo, key, level + 1);
 557         i = getpos(geo, parent, key);
 558         BUG_ON(bval(geo, parent, i) != child);
 559 
 560         if (i > 0) {
 561                 left = bval(geo, parent, i - 1);
 562                 no_left = getfill(geo, left, 0);
 563                 if (fill + no_left <= geo->no_pairs) {
 564                         merge(head, geo, level,
 565                                         left, no_left,
 566                                         child, fill,
 567                                         parent, i - 1);
 568                         return;
 569                 }
 570         }
 571         if (i + 1 < getfill(geo, parent, i)) {
 572                 right = bval(geo, parent, i + 1);
 573                 no_right = getfill(geo, right, 0);
 574                 if (fill + no_right <= geo->no_pairs) {
 575                         merge(head, geo, level,
 576                                         child, fill,
 577                                         right, no_right,
 578                                         parent, i);
 579                         return;
 580                 }
 581         }
 582         /*
 583          * We could also try to steal one entry from the left or right
 584          * neighbor.  By not doing so we changed the invariant from
 585          * "all nodes are at least half full" to "no two neighboring
 586          * nodes can be merged".  Which means that the average fill of
 587          * all nodes is still half or better.
 588          */
 589 }
 590 
 591 static void *btree_remove_level(struct btree_head *head, struct btree_geo *geo,
 592                 unsigned long *key, int level)
 593 {
 594         unsigned long *node;
 595         int i, pos, fill;
 596         void *ret;
 597 
 598         if (level > head->height) {
 599                 /* we recursed all the way up */
 600                 head->height = 0;
 601                 head->node = NULL;
 602                 return NULL;
 603         }
 604 
 605         node = find_level(head, geo, key, level);
 606         pos = getpos(geo, node, key);
 607         fill = getfill(geo, node, pos);
 608         if ((level == 1) && (keycmp(geo, node, pos, key) != 0))
 609                 return NULL;
 610         ret = bval(geo, node, pos);
 611 
 612         /* remove and shift */
 613         for (i = pos; i < fill - 1; i++) {
 614                 setkey(geo, node, i, bkey(geo, node, i + 1));
 615                 setval(geo, node, i, bval(geo, node, i + 1));
 616         }
 617         clearpair(geo, node, fill - 1);
 618 
 619         if (fill - 1 < geo->no_pairs / 2) {
 620                 if (level < head->height)
 621                         rebalance(head, geo, key, level, node, fill - 1);
 622                 else if (fill - 1 == 1)
 623                         btree_shrink(head, geo);
 624         }
 625 
 626         return ret;
 627 }
 628 
 629 void *btree_remove(struct btree_head *head, struct btree_geo *geo,
 630                 unsigned long *key)
 631 {
 632         if (head->height == 0)
 633                 return NULL;
 634 
 635         return btree_remove_level(head, geo, key, 1);
 636 }
 637 EXPORT_SYMBOL_GPL(btree_remove);
 638 
 639 int btree_merge(struct btree_head *target, struct btree_head *victim,
 640                 struct btree_geo *geo, gfp_t gfp)
 641 {
 642         unsigned long key[MAX_KEYLEN];
 643         unsigned long dup[MAX_KEYLEN];
 644         void *val;
 645         int err;
 646 
 647         BUG_ON(target == victim);
 648 
 649         if (!(target->node)) {
 650                 /* target is empty, just copy fields over */
 651                 target->node = victim->node;
 652                 target->height = victim->height;
 653                 __btree_init(victim);
 654                 return 0;
 655         }
 656 
 657         /* TODO: This needs some optimizations.  Currently we do three tree
 658          * walks to remove a single object from the victim.
 659          */
 660         for (;;) {
 661                 if (!btree_last(victim, geo, key))
 662                         break;
 663                 val = btree_lookup(victim, geo, key);
 664                 err = btree_insert(target, geo, key, val, gfp);
 665                 if (err)
 666                         return err;
 667                 /* We must make a copy of the key, as the original will get
 668                  * mangled inside btree_remove. */
 669                 longcpy(dup, key, geo->keylen);
 670                 btree_remove(victim, geo, dup);
 671         }
 672         return 0;
 673 }
 674 EXPORT_SYMBOL_GPL(btree_merge);
 675 
 676 static size_t __btree_for_each(struct btree_head *head, struct btree_geo *geo,
 677                                unsigned long *node, unsigned long opaque,
 678                                void (*func)(void *elem, unsigned long opaque,
 679                                             unsigned long *key, size_t index,
 680                                             void *func2),
 681                                void *func2, int reap, int height, size_t count)
 682 {
 683         int i;
 684         unsigned long *child;
 685 
 686         for (i = 0; i < geo->no_pairs; i++) {
 687                 child = bval(geo, node, i);
 688                 if (!child)
 689                         break;
 690                 if (height > 1)
 691                         count = __btree_for_each(head, geo, child, opaque,
 692                                         func, func2, reap, height - 1, count);
 693                 else
 694                         func(child, opaque, bkey(geo, node, i), count++,
 695                                         func2);
 696         }
 697         if (reap)
 698                 mempool_free(node, head->mempool);
 699         return count;
 700 }
 701 
 702 static void empty(void *elem, unsigned long opaque, unsigned long *key,
 703                   size_t index, void *func2)
 704 {
 705 }
 706 
 707 void visitorl(void *elem, unsigned long opaque, unsigned long *key,
 708               size_t index, void *__func)
 709 {
 710         visitorl_t func = __func;
 711 
 712         func(elem, opaque, *key, index);
 713 }
 714 EXPORT_SYMBOL_GPL(visitorl);
 715 
 716 void visitor32(void *elem, unsigned long opaque, unsigned long *__key,
 717                size_t index, void *__func)
 718 {
 719         visitor32_t func = __func;
 720         u32 *key = (void *)__key;
 721 
 722         func(elem, opaque, *key, index);
 723 }
 724 EXPORT_SYMBOL_GPL(visitor32);
 725 
 726 void visitor64(void *elem, unsigned long opaque, unsigned long *__key,
 727                size_t index, void *__func)
 728 {
 729         visitor64_t func = __func;
 730         u64 *key = (void *)__key;
 731 
 732         func(elem, opaque, *key, index);
 733 }
 734 EXPORT_SYMBOL_GPL(visitor64);
 735 
 736 void visitor128(void *elem, unsigned long opaque, unsigned long *__key,
 737                 size_t index, void *__func)
 738 {
 739         visitor128_t func = __func;
 740         u64 *key = (void *)__key;
 741 
 742         func(elem, opaque, key[0], key[1], index);
 743 }
 744 EXPORT_SYMBOL_GPL(visitor128);
 745 
 746 size_t btree_visitor(struct btree_head *head, struct btree_geo *geo,
 747                      unsigned long opaque,
 748                      void (*func)(void *elem, unsigned long opaque,
 749                                   unsigned long *key,
 750                                   size_t index, void *func2),
 751                      void *func2)
 752 {
 753         size_t count = 0;
 754 
 755         if (!func2)
 756                 func = empty;
 757         if (head->node)
 758                 count = __btree_for_each(head, geo, head->node, opaque, func,
 759                                 func2, 0, head->height, 0);
 760         return count;
 761 }
 762 EXPORT_SYMBOL_GPL(btree_visitor);
 763 
 764 size_t btree_grim_visitor(struct btree_head *head, struct btree_geo *geo,
 765                           unsigned long opaque,
 766                           void (*func)(void *elem, unsigned long opaque,
 767                                        unsigned long *key,
 768                                        size_t index, void *func2),
 769                           void *func2)
 770 {
 771         size_t count = 0;
 772 
 773         if (!func2)
 774                 func = empty;
 775         if (head->node)
 776                 count = __btree_for_each(head, geo, head->node, opaque, func,
 777                                 func2, 1, head->height, 0);
 778         __btree_init(head);
 779         return count;
 780 }
 781 EXPORT_SYMBOL_GPL(btree_grim_visitor);
 782 
 783 static int __init btree_module_init(void)
 784 {
 785         btree_cachep = kmem_cache_create("btree_node", NODESIZE, 0,
 786                         SLAB_HWCACHE_ALIGN, NULL);
 787         return 0;
 788 }
 789 
 790 static void __exit btree_module_exit(void)
 791 {
 792         kmem_cache_destroy(btree_cachep);
 793 }
 794 
 795 /* If core code starts using btree, initialization should happen even earlier */
 796 module_init(btree_module_init);
 797 module_exit(btree_module_exit);
 798 
 799 MODULE_AUTHOR("Joern Engel <joern@logfs.org>");
 800 MODULE_AUTHOR("Johannes Berg <johannes@sipsolutions.net>");
 801 MODULE_LICENSE("GPL");