linux/lib/btree.c
<<
>>
Prefs
   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@logfs.org>
   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
  51struct btree_geo {
  52        int keylen;
  53        int no_pairs;
  54        int no_longs;
  55};
  56
  57struct btree_geo btree_geo32 = {
  58        .keylen = 1,
  59        .no_pairs = NODESIZE / sizeof(long) / 2,
  60        .no_longs = NODESIZE / sizeof(long) / 2,
  61};
  62EXPORT_SYMBOL_GPL(btree_geo32);
  63
  64#define LONG_PER_U64 (64 / BITS_PER_LONG)
  65struct 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};
  70EXPORT_SYMBOL_GPL(btree_geo64);
  71
  72struct 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};
  77EXPORT_SYMBOL_GPL(btree_geo128);
  78
  79static struct kmem_cache *btree_cachep;
  80
  81void *btree_alloc(gfp_t gfp_mask, void *pool_data)
  82{
  83        return kmem_cache_alloc(btree_cachep, gfp_mask);
  84}
  85EXPORT_SYMBOL_GPL(btree_alloc);
  86
  87void btree_free(void *element, void *pool_data)
  88{
  89        kmem_cache_free(btree_cachep, element);
  90}
  91EXPORT_SYMBOL_GPL(btree_free);
  92
  93static 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
 103static 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
 116static 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
 126static 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
 135static 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
 148static unsigned long *bkey(struct btree_geo *geo, unsigned long *node, int n)
 149{
 150        return &node[n * geo->keylen];
 151}
 152
 153static void *bval(struct btree_geo *geo, unsigned long *node, int n)
 154{
 155        return (void *)node[geo->no_longs + n];
 156}
 157
 158static 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
 164static 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
 170static 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
 176static inline void __btree_init(struct btree_head *head)
 177{
 178        head->node = NULL;
 179        head->height = 0;
 180}
 181
 182void btree_init_mempool(struct btree_head *head, mempool_t *mempool)
 183{
 184        __btree_init(head);
 185        head->mempool = mempool;
 186}
 187EXPORT_SYMBOL_GPL(btree_init_mempool);
 188
 189int 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}
 197EXPORT_SYMBOL_GPL(btree_init);
 198
 199void btree_destroy(struct btree_head *head)
 200{
 201        mempool_free(head->node, head->mempool);
 202        mempool_destroy(head->mempool);
 203        head->mempool = NULL;
 204}
 205EXPORT_SYMBOL_GPL(btree_destroy);
 206
 207void *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}
 222EXPORT_SYMBOL_GPL(btree_last);
 223
 224static 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
 230static 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
 241void *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}
 269EXPORT_SYMBOL_GPL(btree_lookup);
 270
 271int 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}
 301EXPORT_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 */
 311void *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[geo->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);
 324retry:
 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        }
 353miss:
 354        if (retry_key) {
 355                longcpy(key, retry_key, geo->keylen);
 356                retry_key = NULL;
 357                goto retry;
 358        }
 359        return NULL;
 360}
 361EXPORT_SYMBOL_GPL(btree_get_prev);
 362
 363static 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
 375static 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 */
 388static 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
 413static 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
 432static 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
 448static 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
 462retry:
 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
 510int 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}
 516EXPORT_SYMBOL_GPL(btree_insert);
 517
 518static void *btree_remove_level(struct btree_head *head, struct btree_geo *geo,
 519                unsigned long *key, int level);
 520static 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
 540static 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
 591static 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
 629void *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}
 637EXPORT_SYMBOL_GPL(btree_remove);
 638
 639int btree_merge(struct btree_head *target, struct btree_head *victim,
 640                struct btree_geo *geo, gfp_t gfp)
 641{
 642        unsigned long key[geo->keylen];
 643        unsigned long dup[geo->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}
 674EXPORT_SYMBOL_GPL(btree_merge);
 675
 676static 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
 702static void empty(void *elem, unsigned long opaque, unsigned long *key,
 703                  size_t index, void *func2)
 704{
 705}
 706
 707void 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}
 714EXPORT_SYMBOL_GPL(visitorl);
 715
 716void 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}
 724EXPORT_SYMBOL_GPL(visitor32);
 725
 726void 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}
 734EXPORT_SYMBOL_GPL(visitor64);
 735
 736void 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}
 744EXPORT_SYMBOL_GPL(visitor128);
 745
 746size_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}
 762EXPORT_SYMBOL_GPL(btree_visitor);
 763
 764size_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}
 781EXPORT_SYMBOL_GPL(btree_grim_visitor);
 782
 783static 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
 790static 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 */
 796module_init(btree_module_init);
 797module_exit(btree_module_exit);
 798
 799MODULE_AUTHOR("Joern Engel <joern@logfs.org>");
 800MODULE_AUTHOR("Johannes Berg <johannes@sipsolutions.net>");
 801MODULE_LICENSE("GPL");
 802