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 <pzijlstr@redhat.com>
   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_destroy(head->mempool);
 202        head->mempool = NULL;
 203}
 204EXPORT_SYMBOL_GPL(btree_destroy);
 205
 206void *btree_last(struct btree_head *head, struct btree_geo *geo,
 207                 unsigned long *key)
 208{
 209        int height = head->height;
 210        unsigned long *node = head->node;
 211
 212        if (height == 0)
 213                return NULL;
 214
 215        for ( ; height > 1; height--)
 216                node = bval(geo, node, 0);
 217
 218        longcpy(key, bkey(geo, node, 0), geo->keylen);
 219        return bval(geo, node, 0);
 220}
 221EXPORT_SYMBOL_GPL(btree_last);
 222
 223static int keycmp(struct btree_geo *geo, unsigned long *node, int pos,
 224                  unsigned long *key)
 225{
 226        return longcmp(bkey(geo, node, pos), key, geo->keylen);
 227}
 228
 229static int keyzero(struct btree_geo *geo, unsigned long *key)
 230{
 231        int i;
 232
 233        for (i = 0; i < geo->keylen; i++)
 234                if (key[i])
 235                        return 0;
 236
 237        return 1;
 238}
 239
 240void *btree_lookup(struct btree_head *head, struct btree_geo *geo,
 241                unsigned long *key)
 242{
 243        int i, height = head->height;
 244        unsigned long *node = head->node;
 245
 246        if (height == 0)
 247                return NULL;
 248
 249        for ( ; height > 1; height--) {
 250                for (i = 0; i < geo->no_pairs; i++)
 251                        if (keycmp(geo, node, i, key) <= 0)
 252                                break;
 253                if (i == geo->no_pairs)
 254                        return NULL;
 255                node = bval(geo, node, i);
 256                if (!node)
 257                        return NULL;
 258        }
 259
 260        if (!node)
 261                return NULL;
 262
 263        for (i = 0; i < geo->no_pairs; i++)
 264                if (keycmp(geo, node, i, key) == 0)
 265                        return bval(geo, node, i);
 266        return NULL;
 267}
 268EXPORT_SYMBOL_GPL(btree_lookup);
 269
 270int btree_update(struct btree_head *head, struct btree_geo *geo,
 271                 unsigned long *key, void *val)
 272{
 273        int i, height = head->height;
 274        unsigned long *node = head->node;
 275
 276        if (height == 0)
 277                return -ENOENT;
 278
 279        for ( ; height > 1; height--) {
 280                for (i = 0; i < geo->no_pairs; i++)
 281                        if (keycmp(geo, node, i, key) <= 0)
 282                                break;
 283                if (i == geo->no_pairs)
 284                        return -ENOENT;
 285                node = bval(geo, node, i);
 286                if (!node)
 287                        return -ENOENT;
 288        }
 289
 290        if (!node)
 291                return -ENOENT;
 292
 293        for (i = 0; i < geo->no_pairs; i++)
 294                if (keycmp(geo, node, i, key) == 0) {
 295                        setval(geo, node, i, val);
 296                        return 0;
 297                }
 298        return -ENOENT;
 299}
 300EXPORT_SYMBOL_GPL(btree_update);
 301
 302/*
 303 * Usually this function is quite similar to normal lookup.  But the key of
 304 * a parent node may be smaller than the smallest key of all its siblings.
 305 * In such a case we cannot just return NULL, as we have only proven that no
 306 * key smaller than __key, but larger than this parent key exists.
 307 * So we set __key to the parent key and retry.  We have to use the smallest
 308 * such parent key, which is the last parent key we encountered.
 309 */
 310void *btree_get_prev(struct btree_head *head, struct btree_geo *geo,
 311                     unsigned long *__key)
 312{
 313        int i, height;
 314        unsigned long *node, *oldnode;
 315        unsigned long *retry_key = NULL, key[geo->keylen];
 316
 317        if (keyzero(geo, __key))
 318                return NULL;
 319
 320        if (head->height == 0)
 321                return NULL;
 322retry:
 323        longcpy(key, __key, geo->keylen);
 324        dec_key(geo, key);
 325
 326        node = head->node;
 327        for (height = head->height ; height > 1; height--) {
 328                for (i = 0; i < geo->no_pairs; i++)
 329                        if (keycmp(geo, node, i, key) <= 0)
 330                                break;
 331                if (i == geo->no_pairs)
 332                        goto miss;
 333                oldnode = node;
 334                node = bval(geo, node, i);
 335                if (!node)
 336                        goto miss;
 337                retry_key = bkey(geo, oldnode, i);
 338        }
 339
 340        if (!node)
 341                goto miss;
 342
 343        for (i = 0; i < geo->no_pairs; i++) {
 344                if (keycmp(geo, node, i, key) <= 0) {
 345                        if (bval(geo, node, i)) {
 346                                longcpy(__key, bkey(geo, node, i), geo->keylen);
 347                                return bval(geo, node, i);
 348                        } else
 349                                goto miss;
 350                }
 351        }
 352miss:
 353        if (retry_key) {
 354                __key = retry_key;
 355                retry_key = NULL;
 356                goto retry;
 357        }
 358        return NULL;
 359}
 360
 361static int getpos(struct btree_geo *geo, unsigned long *node,
 362                unsigned long *key)
 363{
 364        int i;
 365
 366        for (i = 0; i < geo->no_pairs; i++) {
 367                if (keycmp(geo, node, i, key) <= 0)
 368                        break;
 369        }
 370        return i;
 371}
 372
 373static int getfill(struct btree_geo *geo, unsigned long *node, int start)
 374{
 375        int i;
 376
 377        for (i = start; i < geo->no_pairs; i++)
 378                if (!bval(geo, node, i))
 379                        break;
 380        return i;
 381}
 382
 383/*
 384 * locate the correct leaf node in the btree
 385 */
 386static unsigned long *find_level(struct btree_head *head, struct btree_geo *geo,
 387                unsigned long *key, int level)
 388{
 389        unsigned long *node = head->node;
 390        int i, height;
 391
 392        for (height = head->height; height > level; height--) {
 393                for (i = 0; i < geo->no_pairs; i++)
 394                        if (keycmp(geo, node, i, key) <= 0)
 395                                break;
 396
 397                if ((i == geo->no_pairs) || !bval(geo, node, i)) {
 398                        /* right-most key is too large, update it */
 399                        /* FIXME: If the right-most key on higher levels is
 400                         * always zero, this wouldn't be necessary. */
 401                        i--;
 402                        setkey(geo, node, i, key);
 403                }
 404                BUG_ON(i < 0);
 405                node = bval(geo, node, i);
 406        }
 407        BUG_ON(!node);
 408        return node;
 409}
 410
 411static int btree_grow(struct btree_head *head, struct btree_geo *geo,
 412                      gfp_t gfp)
 413{
 414        unsigned long *node;
 415        int fill;
 416
 417        node = btree_node_alloc(head, gfp);
 418        if (!node)
 419                return -ENOMEM;
 420        if (head->node) {
 421                fill = getfill(geo, head->node, 0);
 422                setkey(geo, node, 0, bkey(geo, head->node, fill - 1));
 423                setval(geo, node, 0, head->node);
 424        }
 425        head->node = node;
 426        head->height++;
 427        return 0;
 428}
 429
 430static void btree_shrink(struct btree_head *head, struct btree_geo *geo)
 431{
 432        unsigned long *node;
 433        int fill;
 434
 435        if (head->height <= 1)
 436                return;
 437
 438        node = head->node;
 439        fill = getfill(geo, node, 0);
 440        BUG_ON(fill > 1);
 441        head->node = bval(geo, node, 0);
 442        head->height--;
 443        mempool_free(node, head->mempool);
 444}
 445
 446static int btree_insert_level(struct btree_head *head, struct btree_geo *geo,
 447                              unsigned long *key, void *val, int level,
 448                              gfp_t gfp)
 449{
 450        unsigned long *node;
 451        int i, pos, fill, err;
 452
 453        BUG_ON(!val);
 454        if (head->height < level) {
 455                err = btree_grow(head, geo, gfp);
 456                if (err)
 457                        return err;
 458        }
 459
 460retry:
 461        node = find_level(head, geo, key, level);
 462        pos = getpos(geo, node, key);
 463        fill = getfill(geo, node, pos);
 464        /* two identical keys are not allowed */
 465        BUG_ON(pos < fill && keycmp(geo, node, pos, key) == 0);
 466
 467        if (fill == geo->no_pairs) {
 468                /* need to split node */
 469                unsigned long *new;
 470
 471                new = btree_node_alloc(head, gfp);
 472                if (!new)
 473                        return -ENOMEM;
 474                err = btree_insert_level(head, geo,
 475                                bkey(geo, node, fill / 2 - 1),
 476                                new, level + 1, gfp);
 477                if (err) {
 478                        mempool_free(new, head->mempool);
 479                        return err;
 480                }
 481                for (i = 0; i < fill / 2; i++) {
 482                        setkey(geo, new, i, bkey(geo, node, i));
 483                        setval(geo, new, i, bval(geo, node, i));
 484                        setkey(geo, node, i, bkey(geo, node, i + fill / 2));
 485                        setval(geo, node, i, bval(geo, node, i + fill / 2));
 486                        clearpair(geo, node, i + fill / 2);
 487                }
 488                if (fill & 1) {
 489                        setkey(geo, node, i, bkey(geo, node, fill - 1));
 490                        setval(geo, node, i, bval(geo, node, fill - 1));
 491                        clearpair(geo, node, fill - 1);
 492                }
 493                goto retry;
 494        }
 495        BUG_ON(fill >= geo->no_pairs);
 496
 497        /* shift and insert */
 498        for (i = fill; i > pos; i--) {
 499                setkey(geo, node, i, bkey(geo, node, i - 1));
 500                setval(geo, node, i, bval(geo, node, i - 1));
 501        }
 502        setkey(geo, node, pos, key);
 503        setval(geo, node, pos, val);
 504
 505        return 0;
 506}
 507
 508int btree_insert(struct btree_head *head, struct btree_geo *geo,
 509                unsigned long *key, void *val, gfp_t gfp)
 510{
 511        return btree_insert_level(head, geo, key, val, 1, gfp);
 512}
 513EXPORT_SYMBOL_GPL(btree_insert);
 514
 515static void *btree_remove_level(struct btree_head *head, struct btree_geo *geo,
 516                unsigned long *key, int level);
 517static void merge(struct btree_head *head, struct btree_geo *geo, int level,
 518                unsigned long *left, int lfill,
 519                unsigned long *right, int rfill,
 520                unsigned long *parent, int lpos)
 521{
 522        int i;
 523
 524        for (i = 0; i < rfill; i++) {
 525                /* Move all keys to the left */
 526                setkey(geo, left, lfill + i, bkey(geo, right, i));
 527                setval(geo, left, lfill + i, bval(geo, right, i));
 528        }
 529        /* Exchange left and right child in parent */
 530        setval(geo, parent, lpos, right);
 531        setval(geo, parent, lpos + 1, left);
 532        /* Remove left (formerly right) child from parent */
 533        btree_remove_level(head, geo, bkey(geo, parent, lpos), level + 1);
 534        mempool_free(right, head->mempool);
 535}
 536
 537static void rebalance(struct btree_head *head, struct btree_geo *geo,
 538                unsigned long *key, int level, unsigned long *child, int fill)
 539{
 540        unsigned long *parent, *left = NULL, *right = NULL;
 541        int i, no_left, no_right;
 542
 543        if (fill == 0) {
 544                /* Because we don't steal entries from a neighbour, this case
 545                 * can happen.  Parent node contains a single child, this
 546                 * node, so merging with a sibling never happens.
 547                 */
 548                btree_remove_level(head, geo, key, level + 1);
 549                mempool_free(child, head->mempool);
 550                return;
 551        }
 552
 553        parent = find_level(head, geo, key, level + 1);
 554        i = getpos(geo, parent, key);
 555        BUG_ON(bval(geo, parent, i) != child);
 556
 557        if (i > 0) {
 558                left = bval(geo, parent, i - 1);
 559                no_left = getfill(geo, left, 0);
 560                if (fill + no_left <= geo->no_pairs) {
 561                        merge(head, geo, level,
 562                                        left, no_left,
 563                                        child, fill,
 564                                        parent, i - 1);
 565                        return;
 566                }
 567        }
 568        if (i + 1 < getfill(geo, parent, i)) {
 569                right = bval(geo, parent, i + 1);
 570                no_right = getfill(geo, right, 0);
 571                if (fill + no_right <= geo->no_pairs) {
 572                        merge(head, geo, level,
 573                                        child, fill,
 574                                        right, no_right,
 575                                        parent, i);
 576                        return;
 577                }
 578        }
 579        /*
 580         * We could also try to steal one entry from the left or right
 581         * neighbor.  By not doing so we changed the invariant from
 582         * "all nodes are at least half full" to "no two neighboring
 583         * nodes can be merged".  Which means that the average fill of
 584         * all nodes is still half or better.
 585         */
 586}
 587
 588static void *btree_remove_level(struct btree_head *head, struct btree_geo *geo,
 589                unsigned long *key, int level)
 590{
 591        unsigned long *node;
 592        int i, pos, fill;
 593        void *ret;
 594
 595        if (level > head->height) {
 596                /* we recursed all the way up */
 597                head->height = 0;
 598                head->node = NULL;
 599                return NULL;
 600        }
 601
 602        node = find_level(head, geo, key, level);
 603        pos = getpos(geo, node, key);
 604        fill = getfill(geo, node, pos);
 605        if ((level == 1) && (keycmp(geo, node, pos, key) != 0))
 606                return NULL;
 607        ret = bval(geo, node, pos);
 608
 609        /* remove and shift */
 610        for (i = pos; i < fill - 1; i++) {
 611                setkey(geo, node, i, bkey(geo, node, i + 1));
 612                setval(geo, node, i, bval(geo, node, i + 1));
 613        }
 614        clearpair(geo, node, fill - 1);
 615
 616        if (fill - 1 < geo->no_pairs / 2) {
 617                if (level < head->height)
 618                        rebalance(head, geo, key, level, node, fill - 1);
 619                else if (fill - 1 == 1)
 620                        btree_shrink(head, geo);
 621        }
 622
 623        return ret;
 624}
 625
 626void *btree_remove(struct btree_head *head, struct btree_geo *geo,
 627                unsigned long *key)
 628{
 629        if (head->height == 0)
 630                return NULL;
 631
 632        return btree_remove_level(head, geo, key, 1);
 633}
 634EXPORT_SYMBOL_GPL(btree_remove);
 635
 636int btree_merge(struct btree_head *target, struct btree_head *victim,
 637                struct btree_geo *geo, gfp_t gfp)
 638{
 639        unsigned long key[geo->keylen];
 640        unsigned long dup[geo->keylen];
 641        void *val;
 642        int err;
 643
 644        BUG_ON(target == victim);
 645
 646        if (!(target->node)) {
 647                /* target is empty, just copy fields over */
 648                target->node = victim->node;
 649                target->height = victim->height;
 650                __btree_init(victim);
 651                return 0;
 652        }
 653
 654        /* TODO: This needs some optimizations.  Currently we do three tree
 655         * walks to remove a single object from the victim.
 656         */
 657        for (;;) {
 658                if (!btree_last(victim, geo, key))
 659                        break;
 660                val = btree_lookup(victim, geo, key);
 661                err = btree_insert(target, geo, key, val, gfp);
 662                if (err)
 663                        return err;
 664                /* We must make a copy of the key, as the original will get
 665                 * mangled inside btree_remove. */
 666                longcpy(dup, key, geo->keylen);
 667                btree_remove(victim, geo, dup);
 668        }
 669        return 0;
 670}
 671EXPORT_SYMBOL_GPL(btree_merge);
 672
 673static size_t __btree_for_each(struct btree_head *head, struct btree_geo *geo,
 674                               unsigned long *node, unsigned long opaque,
 675                               void (*func)(void *elem, unsigned long opaque,
 676                                            unsigned long *key, size_t index,
 677                                            void *func2),
 678                               void *func2, int reap, int height, size_t count)
 679{
 680        int i;
 681        unsigned long *child;
 682
 683        for (i = 0; i < geo->no_pairs; i++) {
 684                child = bval(geo, node, i);
 685                if (!child)
 686                        break;
 687                if (height > 1)
 688                        count = __btree_for_each(head, geo, child, opaque,
 689                                        func, func2, reap, height - 1, count);
 690                else
 691                        func(child, opaque, bkey(geo, node, i), count++,
 692                                        func2);
 693        }
 694        if (reap)
 695                mempool_free(node, head->mempool);
 696        return count;
 697}
 698
 699static void empty(void *elem, unsigned long opaque, unsigned long *key,
 700                  size_t index, void *func2)
 701{
 702}
 703
 704void visitorl(void *elem, unsigned long opaque, unsigned long *key,
 705              size_t index, void *__func)
 706{
 707        visitorl_t func = __func;
 708
 709        func(elem, opaque, *key, index);
 710}
 711EXPORT_SYMBOL_GPL(visitorl);
 712
 713void visitor32(void *elem, unsigned long opaque, unsigned long *__key,
 714               size_t index, void *__func)
 715{
 716        visitor32_t func = __func;
 717        u32 *key = (void *)__key;
 718
 719        func(elem, opaque, *key, index);
 720}
 721EXPORT_SYMBOL_GPL(visitor32);
 722
 723void visitor64(void *elem, unsigned long opaque, unsigned long *__key,
 724               size_t index, void *__func)
 725{
 726        visitor64_t func = __func;
 727        u64 *key = (void *)__key;
 728
 729        func(elem, opaque, *key, index);
 730}
 731EXPORT_SYMBOL_GPL(visitor64);
 732
 733void visitor128(void *elem, unsigned long opaque, unsigned long *__key,
 734                size_t index, void *__func)
 735{
 736        visitor128_t func = __func;
 737        u64 *key = (void *)__key;
 738
 739        func(elem, opaque, key[0], key[1], index);
 740}
 741EXPORT_SYMBOL_GPL(visitor128);
 742
 743size_t btree_visitor(struct btree_head *head, struct btree_geo *geo,
 744                     unsigned long opaque,
 745                     void (*func)(void *elem, unsigned long opaque,
 746                                  unsigned long *key,
 747                                  size_t index, void *func2),
 748                     void *func2)
 749{
 750        size_t count = 0;
 751
 752        if (!func2)
 753                func = empty;
 754        if (head->node)
 755                count = __btree_for_each(head, geo, head->node, opaque, func,
 756                                func2, 0, head->height, 0);
 757        return count;
 758}
 759EXPORT_SYMBOL_GPL(btree_visitor);
 760
 761size_t btree_grim_visitor(struct btree_head *head, struct btree_geo *geo,
 762                          unsigned long opaque,
 763                          void (*func)(void *elem, unsigned long opaque,
 764                                       unsigned long *key,
 765                                       size_t index, void *func2),
 766                          void *func2)
 767{
 768        size_t count = 0;
 769
 770        if (!func2)
 771                func = empty;
 772        if (head->node)
 773                count = __btree_for_each(head, geo, head->node, opaque, func,
 774                                func2, 1, head->height, 0);
 775        __btree_init(head);
 776        return count;
 777}
 778EXPORT_SYMBOL_GPL(btree_grim_visitor);
 779
 780static int __init btree_module_init(void)
 781{
 782        btree_cachep = kmem_cache_create("btree_node", NODESIZE, 0,
 783                        SLAB_HWCACHE_ALIGN, NULL);
 784        return 0;
 785}
 786
 787static void __exit btree_module_exit(void)
 788{
 789        kmem_cache_destroy(btree_cachep);
 790}
 791
 792/* If core code starts using btree, initialization should happen even earlier */
 793module_init(btree_module_init);
 794module_exit(btree_module_exit);
 795
 796MODULE_AUTHOR("Joern Engel <joern@logfs.org>");
 797MODULE_AUTHOR("Johannes Berg <johannes@sipsolutions.net>");
 798MODULE_LICENSE("GPL");
 799
lxr.linux.no kindly hosted by Redpill Linpro AS, provider of Linux consulting and operations services since 1995.