lib/btree.c

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