the-tree/lib/btree.c

0001 // SPDX-License-Identifier: GPL-2.0-only
0002 /*
0003  * lib/btree.c  - Simple In-memory B+Tree
0004  *
0005  * Copyright (c) 2007-2008 Joern Engel <joern@purestorage.com>
0006  * Bits and pieces stolen from Peter Zijlstra's code, which is
0007  * Copyright 2007, Red Hat Inc. Peter Zijlstra
0008  *
0009  * see http://programming.kicks-ass.net/kernel-patches/vma_lookup/btree.patch
0010  *
0011  * A relatively simple B+Tree implementation.  I have written it as a learning
0012  * exercise to understand how B+Trees work.  Turned out to be useful as well.
0013  *
0014  * B+Trees can be used similar to Linux radix trees (which don't have anything
0015  * in common with textbook radix trees, beware).  Prerequisite for them working
0016  * well is that access to a random tree node is much faster than a large number
0017  * of operations within each node.
0018  *
0019  * Disks have fulfilled the prerequisite for a long time.  More recently DRAM
0020  * has gained similar properties, as memory access times, when measured in cpu
0021  * cycles, have increased.  Cacheline sizes have increased as well, which also
0022  * helps B+Trees.
0023  *
0024  * Compared to radix trees, B+Trees are more efficient when dealing with a
0025  * sparsely populated address space.  Between 25% and 50% of the memory is
0026  * occupied with valid pointers.  When densely populated, radix trees contain
0027  * ~98% pointers - hard to beat.  Very sparse radix trees contain only ~2%
0028  * pointers.
0029  *
0030  * This particular implementation stores pointers identified by a long value.
0031  * Storing NULL pointers is illegal, lookup will return NULL when no entry
0032  * was found.
0033  *
0034  * A tricks was used that is not commonly found in textbooks.  The lowest
0035  * values are to the right, not to the left.  All used slots within a node
0036  * are on the left, all unused slots contain NUL values.  Most operations
0037  * simply loop once over all slots and terminate on the first NUL.
0038  */
0039
0040 #include <linux/btree.h>
0041 #include <linux/cache.h>
0042 #include <linux/kernel.h>
0043 #include <linux/slab.h>
0044 #include <linux/module.h>
0045
0046 #define MAX(a, b) ((a) > (b) ? (a) : (b))
0047 #define NODESIZE MAX(L1_CACHE_BYTES, 128)
0048
0049 struct btree_geo {
0050     int keylen;
0051     int no_pairs;
0052     int no_longs;
0053 };
0054
0055 struct btree_geo btree_geo32 = {
0056     .keylen = 1,
0057     .no_pairs = NODESIZE / sizeof(long) / 2,
0058     .no_longs = NODESIZE / sizeof(long) / 2,
0059 };
0060 EXPORT_SYMBOL_GPL(btree_geo32);
0061
0062 #define LONG_PER_U64 (64 / BITS_PER_LONG)
0063 struct btree_geo btree_geo64 = {
0064     .keylen = LONG_PER_U64,
0065     .no_pairs = NODESIZE / sizeof(long) / (1 + LONG_PER_U64),
0066     .no_longs = LONG_PER_U64 * (NODESIZE / sizeof(long) / (1 + LONG_PER_U64)),
0067 };
0068 EXPORT_SYMBOL_GPL(btree_geo64);
0069
0070 struct btree_geo btree_geo128 = {
0071     .keylen = 2 * LONG_PER_U64,
0072     .no_pairs = NODESIZE / sizeof(long) / (1 + 2 * LONG_PER_U64),
0073     .no_longs = 2 * LONG_PER_U64 * (NODESIZE / sizeof(long) / (1 + 2 * LONG_PER_U64)),
0074 };
0075 EXPORT_SYMBOL_GPL(btree_geo128);
0076
0077 #define MAX_KEYLEN  (2 * LONG_PER_U64)
0078
0079 static struct kmem_cache *btree_cachep;
0080
0081 void *btree_alloc(gfp_t gfp_mask, void *pool_data)
0082 {
0083     return kmem_cache_alloc(btree_cachep, gfp_mask);
0084 }
0085 EXPORT_SYMBOL_GPL(btree_alloc);
0086
0087 void btree_free(void *element, void *pool_data)
0088 {
0089     kmem_cache_free(btree_cachep, element);
0090 }
0091 EXPORT_SYMBOL_GPL(btree_free);
0092
0093 static unsigned long *btree_node_alloc(struct btree_head *head, gfp_t gfp)
0094 {
0095     unsigned long *node;
0096
0097     node = mempool_alloc(head->mempool, gfp);
0098     if (likely(node))
0099         memset(node, 0, NODESIZE);
0100     return node;
0101 }
0102
0103 static int longcmp(const unsigned long *l1, const unsigned long *l2, size_t n)
0104 {
0105     size_t i;
0106
0107     for (i = 0; i < n; i++) {
0108         if (l1[i] < l2[i])
0109             return -1;
0110         if (l1[i] > l2[i])
0111             return 1;
0112     }
0113     return 0;
0114 }
0115
0116 static unsigned long *longcpy(unsigned long *dest, const unsigned long *src,
0117         size_t n)
0118 {
0119     size_t i;
0120
0121     for (i = 0; i < n; i++)
0122         dest[i] = src[i];
0123     return dest;
0124 }
0125
0126 static unsigned long *longset(unsigned long *s, unsigned long c, size_t n)
0127 {
0128     size_t i;
0129
0130     for (i = 0; i < n; i++)
0131         s[i] = c;
0132     return s;
0133 }
0134
0135 static void dec_key(struct btree_geo *geo, unsigned long *key)
0136 {
0137     unsigned long val;
0138     int i;
0139
0140     for (i = geo->keylen - 1; i >= 0; i--) {
0141         val = key[i];
0142         key[i] = val - 1;
0143         if (val)
0144             break;
0145     }
0146 }
0147
0148 static unsigned long *bkey(struct btree_geo *geo, unsigned long *node, int n)
0149 {
0150     return &node[n * geo->keylen];
0151 }
0152
0153 static void *bval(struct btree_geo *geo, unsigned long *node, int n)
0154 {
0155     return (void *)node[geo->no_longs + n];
0156 }
0157
0158 static void setkey(struct btree_geo *geo, unsigned long *node, int n,
0159            unsigned long *key)
0160 {
0161     longcpy(bkey(geo, node, n), key, geo->keylen);
0162 }
0163
0164 static void setval(struct btree_geo *geo, unsigned long *node, int n,
0165            void *val)
0166 {
0167     node[geo->no_longs + n] = (unsigned long) val;
0168 }
0169
0170 static void clearpair(struct btree_geo *geo, unsigned long *node, int n)
0171 {
0172     longset(bkey(geo, node, n), 0, geo->keylen);
0173     node[geo->no_longs + n] = 0;
0174 }
0175
0176 static inline void __btree_init(struct btree_head *head)
0177 {
0178     head->node = NULL;
0179     head->height = 0;
0180 }
0181
0182 void btree_init_mempool(struct btree_head *head, mempool_t *mempool)
0183 {
0184     __btree_init(head);
0185     head->mempool = mempool;
0186 }
0187 EXPORT_SYMBOL_GPL(btree_init_mempool);
0188
0189 int btree_init(struct btree_head *head)
0190 {
0191     __btree_init(head);
0192     head->mempool = mempool_create(0, btree_alloc, btree_free, NULL);
0193     if (!head->mempool)
0194         return -ENOMEM;
0195     return 0;
0196 }
0197 EXPORT_SYMBOL_GPL(btree_init);
0198
0199 void btree_destroy(struct btree_head *head)
0200 {
0201     mempool_free(head->node, head->mempool);
0202     mempool_destroy(head->mempool);
0203     head->mempool = NULL;
0204 }
0205 EXPORT_SYMBOL_GPL(btree_destroy);
0206
0207 void *btree_last(struct btree_head *head, struct btree_geo *geo,
0208          unsigned long *key)
0209 {
0210     int height = head->height;
0211     unsigned long *node = head->node;
0212
0213     if (height == 0)
0214         return NULL;
0215
0216     for ( ; height > 1; height--)
0217         node = bval(geo, node, 0);
0218
0219     longcpy(key, bkey(geo, node, 0), geo->keylen);
0220     return bval(geo, node, 0);
0221 }
0222 EXPORT_SYMBOL_GPL(btree_last);
0223
0224 static int keycmp(struct btree_geo *geo, unsigned long *node, int pos,
0225           unsigned long *key)
0226 {
0227     return longcmp(bkey(geo, node, pos), key, geo->keylen);
0228 }
0229
0230 static int keyzero(struct btree_geo *geo, unsigned long *key)
0231 {
0232     int i;
0233
0234     for (i = 0; i < geo->keylen; i++)
0235         if (key[i])
0236             return 0;
0237
0238     return 1;
0239 }
0240
0241 static void *btree_lookup_node(struct btree_head *head, struct btree_geo *geo,
0242         unsigned long *key)
0243 {
0244     int i, height = head->height;
0245     unsigned long *node = head->node;
0246
0247     if (height == 0)
0248         return NULL;
0249
0250     for ( ; height > 1; height--) {
0251         for (i = 0; i < geo->no_pairs; i++)
0252             if (keycmp(geo, node, i, key) <= 0)
0253                 break;
0254         if (i == geo->no_pairs)
0255             return NULL;
0256         node = bval(geo, node, i);
0257         if (!node)
0258             return NULL;
0259     }
0260     return node;
0261 }
0262
0263 void *btree_lookup(struct btree_head *head, struct btree_geo *geo,
0264         unsigned long *key)
0265 {
0266     int i;
0267     unsigned long *node;
0268
0269     node = btree_lookup_node(head, geo, key);
0270     if (!node)
0271         return NULL;
0272
0273     for (i = 0; i < geo->no_pairs; i++)
0274         if (keycmp(geo, node, i, key) == 0)
0275             return bval(geo, node, i);
0276     return NULL;
0277 }
0278 EXPORT_SYMBOL_GPL(btree_lookup);
0279
0280 int btree_update(struct btree_head *head, struct btree_geo *geo,
0281          unsigned long *key, void *val)
0282 {
0283     int i;
0284     unsigned long *node;
0285
0286     node = btree_lookup_node(head, geo, key);
0287     if (!node)
0288         return -ENOENT;
0289
0290     for (i = 0; i < geo->no_pairs; i++)
0291         if (keycmp(geo, node, i, key) == 0) {
0292             setval(geo, node, i, val);
0293             return 0;
0294         }
0295     return -ENOENT;
0296 }
0297 EXPORT_SYMBOL_GPL(btree_update);
0298
0299 /*
0300  * Usually this function is quite similar to normal lookup.  But the key of
0301  * a parent node may be smaller than the smallest key of all its siblings.
0302  * In such a case we cannot just return NULL, as we have only proven that no
0303  * key smaller than __key, but larger than this parent key exists.
0304  * So we set __key to the parent key and retry.  We have to use the smallest
0305  * such parent key, which is the last parent key we encountered.
0306  */
0307 void *btree_get_prev(struct btree_head *head, struct btree_geo *geo,
0308              unsigned long *__key)
0309 {
0310     int i, height;
0311     unsigned long *node, *oldnode;
0312     unsigned long *retry_key = NULL, key[MAX_KEYLEN];
0313
0314     if (keyzero(geo, __key))
0315         return NULL;
0316
0317     if (head->height == 0)
0318         return NULL;
0319     longcpy(key, __key, geo->keylen);
0320 retry:
0321     dec_key(geo, key);
0322
0323     node = head->node;
0324     for (height = head->height ; height > 1; height--) {
0325         for (i = 0; i < geo->no_pairs; i++)
0326             if (keycmp(geo, node, i, key) <= 0)
0327                 break;
0328         if (i == geo->no_pairs)
0329             goto miss;
0330         oldnode = node;
0331         node = bval(geo, node, i);
0332         if (!node)
0333             goto miss;
0334         retry_key = bkey(geo, oldnode, i);
0335     }
0336
0337     if (!node)
0338         goto miss;
0339
0340     for (i = 0; i < geo->no_pairs; i++) {
0341         if (keycmp(geo, node, i, key) <= 0) {
0342             if (bval(geo, node, i)) {
0343                 longcpy(__key, bkey(geo, node, i), geo->keylen);
0344                 return bval(geo, node, i);
0345             } else
0346                 goto miss;
0347         }
0348     }
0349 miss:
0350     if (retry_key) {
0351         longcpy(key, retry_key, geo->keylen);
0352         retry_key = NULL;
0353         goto retry;
0354     }
0355     return NULL;
0356 }
0357 EXPORT_SYMBOL_GPL(btree_get_prev);
0358
0359 static int getpos(struct btree_geo *geo, unsigned long *node,
0360         unsigned long *key)
0361 {
0362     int i;
0363
0364     for (i = 0; i < geo->no_pairs; i++) {
0365         if (keycmp(geo, node, i, key) <= 0)
0366             break;
0367     }
0368     return i;
0369 }
0370
0371 static int getfill(struct btree_geo *geo, unsigned long *node, int start)
0372 {
0373     int i;
0374
0375     for (i = start; i < geo->no_pairs; i++)
0376         if (!bval(geo, node, i))
0377             break;
0378     return i;
0379 }
0380
0381 /*
0382  * locate the correct leaf node in the btree
0383  */
0384 static unsigned long *find_level(struct btree_head *head, struct btree_geo *geo,
0385         unsigned long *key, int level)
0386 {
0387     unsigned long *node = head->node;
0388     int i, height;
0389
0390     for (height = head->height; height > level; height--) {
0391         for (i = 0; i < geo->no_pairs; i++)
0392             if (keycmp(geo, node, i, key) <= 0)
0393                 break;
0394
0395         if ((i == geo->no_pairs) || !bval(geo, node, i)) {
0396             /* right-most key is too large, update it */
0397             /* FIXME: If the right-most key on higher levels is
0398              * always zero, this wouldn't be necessary. */
0399             i--;
0400             setkey(geo, node, i, key);
0401         }
0402         BUG_ON(i < 0);
0403         node = bval(geo, node, i);
0404     }
0405     BUG_ON(!node);
0406     return node;
0407 }
0408
0409 static int btree_grow(struct btree_head *head, struct btree_geo *geo,
0410               gfp_t gfp)
0411 {
0412     unsigned long *node;
0413     int fill;
0414
0415     node = btree_node_alloc(head, gfp);
0416     if (!node)
0417         return -ENOMEM;
0418     if (head->node) {
0419         fill = getfill(geo, head->node, 0);
0420         setkey(geo, node, 0, bkey(geo, head->node, fill - 1));
0421         setval(geo, node, 0, head->node);
0422     }
0423     head->node = node;
0424     head->height++;
0425     return 0;
0426 }
0427
0428 static void btree_shrink(struct btree_head *head, struct btree_geo *geo)
0429 {
0430     unsigned long *node;
0431     int fill;
0432
0433     if (head->height <= 1)
0434         return;
0435
0436     node = head->node;
0437     fill = getfill(geo, node, 0);
0438     BUG_ON(fill > 1);
0439     head->node = bval(geo, node, 0);
0440     head->height--;
0441     mempool_free(node, head->mempool);
0442 }
0443
0444 static int btree_insert_level(struct btree_head *head, struct btree_geo *geo,
0445                   unsigned long *key, void *val, int level,
0446                   gfp_t gfp)
0447 {
0448     unsigned long *node;
0449     int i, pos, fill, err;
0450
0451     BUG_ON(!val);
0452     if (head->height < level) {
0453         err = btree_grow(head, geo, gfp);
0454         if (err)
0455             return err;
0456     }
0457
0458 retry:
0459     node = find_level(head, geo, key, level);
0460     pos = getpos(geo, node, key);
0461     fill = getfill(geo, node, pos);
0462     /* two identical keys are not allowed */
0463     BUG_ON(pos < fill && keycmp(geo, node, pos, key) == 0);
0464
0465     if (fill == geo->no_pairs) {
0466         /* need to split node */
0467         unsigned long *new;
0468
0469         new = btree_node_alloc(head, gfp);
0470         if (!new)
0471             return -ENOMEM;
0472         err = btree_insert_level(head, geo,
0473                 bkey(geo, node, fill / 2 - 1),
0474                 new, level + 1, gfp);
0475         if (err) {
0476             mempool_free(new, head->mempool);
0477             return err;
0478         }
0479         for (i = 0; i < fill / 2; i++) {
0480             setkey(geo, new, i, bkey(geo, node, i));
0481             setval(geo, new, i, bval(geo, node, i));
0482             setkey(geo, node, i, bkey(geo, node, i + fill / 2));
0483             setval(geo, node, i, bval(geo, node, i + fill / 2));
0484             clearpair(geo, node, i + fill / 2);
0485         }
0486         if (fill & 1) {
0487             setkey(geo, node, i, bkey(geo, node, fill - 1));
0488             setval(geo, node, i, bval(geo, node, fill - 1));
0489             clearpair(geo, node, fill - 1);
0490         }
0491         goto retry;
0492     }
0493     BUG_ON(fill >= geo->no_pairs);
0494
0495     /* shift and insert */
0496     for (i = fill; i > pos; i--) {
0497         setkey(geo, node, i, bkey(geo, node, i - 1));
0498         setval(geo, node, i, bval(geo, node, i - 1));
0499     }
0500     setkey(geo, node, pos, key);
0501     setval(geo, node, pos, val);
0502
0503     return 0;
0504 }
0505
0506 int btree_insert(struct btree_head *head, struct btree_geo *geo,
0507         unsigned long *key, void *val, gfp_t gfp)
0508 {
0509     BUG_ON(!val);
0510     return btree_insert_level(head, geo, key, val, 1, gfp);
0511 }
0512 EXPORT_SYMBOL_GPL(btree_insert);
0513
0514 static void *btree_remove_level(struct btree_head *head, struct btree_geo *geo,
0515         unsigned long *key, int level);
0516 static void merge(struct btree_head *head, struct btree_geo *geo, int level,
0517         unsigned long *left, int lfill,
0518         unsigned long *right, int rfill,
0519         unsigned long *parent, int lpos)
0520 {
0521     int i;
0522
0523     for (i = 0; i < rfill; i++) {
0524         /* Move all keys to the left */
0525         setkey(geo, left, lfill + i, bkey(geo, right, i));
0526         setval(geo, left, lfill + i, bval(geo, right, i));
0527     }
0528     /* Exchange left and right child in parent */
0529     setval(geo, parent, lpos, right);
0530     setval(geo, parent, lpos + 1, left);
0531     /* Remove left (formerly right) child from parent */
0532     btree_remove_level(head, geo, bkey(geo, parent, lpos), level + 1);
0533     mempool_free(right, head->mempool);
0534 }
0535
0536 static void rebalance(struct btree_head *head, struct btree_geo *geo,
0537         unsigned long *key, int level, unsigned long *child, int fill)
0538 {
0539     unsigned long *parent, *left = NULL, *right = NULL;
0540     int i, no_left, no_right;
0541
0542     if (fill == 0) {
0543         /* Because we don't steal entries from a neighbour, this case
0544          * can happen.  Parent node contains a single child, this
0545          * node, so merging with a sibling never happens.
0546          */
0547         btree_remove_level(head, geo, key, level + 1);
0548         mempool_free(child, head->mempool);
0549         return;
0550     }
0551
0552     parent = find_level(head, geo, key, level + 1);
0553     i = getpos(geo, parent, key);
0554     BUG_ON(bval(geo, parent, i) != child);
0555
0556     if (i > 0) {
0557         left = bval(geo, parent, i - 1);
0558         no_left = getfill(geo, left, 0);
0559         if (fill + no_left <= geo->no_pairs) {
0560             merge(head, geo, level,
0561                     left, no_left,
0562                     child, fill,
0563                     parent, i - 1);
0564             return;
0565         }
0566     }
0567     if (i + 1 < getfill(geo, parent, i)) {
0568         right = bval(geo, parent, i + 1);
0569         no_right = getfill(geo, right, 0);
0570         if (fill + no_right <= geo->no_pairs) {
0571             merge(head, geo, level,
0572                     child, fill,
0573                     right, no_right,
0574                     parent, i);
0575             return;
0576         }
0577     }
0578     /*
0579      * We could also try to steal one entry from the left or right
0580      * neighbor.  By not doing so we changed the invariant from
0581      * "all nodes are at least half full" to "no two neighboring
0582      * nodes can be merged".  Which means that the average fill of
0583      * all nodes is still half or better.
0584      */
0585 }
0586
0587 static void *btree_remove_level(struct btree_head *head, struct btree_geo *geo,
0588         unsigned long *key, int level)
0589 {
0590     unsigned long *node;
0591     int i, pos, fill;
0592     void *ret;
0593
0594     if (level > head->height) {
0595         /* we recursed all the way up */
0596         head->height = 0;
0597         head->node = NULL;
0598         return NULL;
0599     }
0600
0601     node = find_level(head, geo, key, level);
0602     pos = getpos(geo, node, key);
0603     fill = getfill(geo, node, pos);
0604     if ((level == 1) && (keycmp(geo, node, pos, key) != 0))
0605         return NULL;
0606     ret = bval(geo, node, pos);
0607
0608     /* remove and shift */
0609     for (i = pos; i < fill - 1; i++) {
0610         setkey(geo, node, i, bkey(geo, node, i + 1));
0611         setval(geo, node, i, bval(geo, node, i + 1));
0612     }
0613     clearpair(geo, node, fill - 1);
0614
0615     if (fill - 1 < geo->no_pairs / 2) {
0616         if (level < head->height)
0617             rebalance(head, geo, key, level, node, fill - 1);
0618         else if (fill - 1 == 1)
0619             btree_shrink(head, geo);
0620     }
0621
0622     return ret;
0623 }
0624
0625 void *btree_remove(struct btree_head *head, struct btree_geo *geo,
0626         unsigned long *key)
0627 {
0628     if (head->height == 0)
0629         return NULL;
0630
0631     return btree_remove_level(head, geo, key, 1);
0632 }
0633 EXPORT_SYMBOL_GPL(btree_remove);
0634
0635 int btree_merge(struct btree_head *target, struct btree_head *victim,
0636         struct btree_geo *geo, gfp_t gfp)
0637 {
0638     unsigned long key[MAX_KEYLEN];
0639     unsigned long dup[MAX_KEYLEN];
0640     void *val;
0641     int err;
0642
0643     BUG_ON(target == victim);
0644
0645     if (!(target->node)) {
0646         /* target is empty, just copy fields over */
0647         target->node = victim->node;
0648         target->height = victim->height;
0649         __btree_init(victim);
0650         return 0;
0651     }
0652
0653     /* TODO: This needs some optimizations.  Currently we do three tree
0654      * walks to remove a single object from the victim.
0655      */
0656     for (;;) {
0657         if (!btree_last(victim, geo, key))
0658             break;
0659         val = btree_lookup(victim, geo, key);
0660         err = btree_insert(target, geo, key, val, gfp);
0661         if (err)
0662             return err;
0663         /* We must make a copy of the key, as the original will get
0664          * mangled inside btree_remove. */
0665         longcpy(dup, key, geo->keylen);
0666         btree_remove(victim, geo, dup);
0667     }
0668     return 0;
0669 }
0670 EXPORT_SYMBOL_GPL(btree_merge);
0671
0672 static size_t __btree_for_each(struct btree_head *head, struct btree_geo *geo,
0673                    unsigned long *node, unsigned long opaque,
0674                    void (*func)(void *elem, unsigned long opaque,
0675                         unsigned long *key, size_t index,
0676                         void *func2),
0677                    void *func2, int reap, int height, size_t count)
0678 {
0679     int i;
0680     unsigned long *child;
0681
0682     for (i = 0; i < geo->no_pairs; i++) {
0683         child = bval(geo, node, i);
0684         if (!child)
0685             break;
0686         if (height > 1)
0687             count = __btree_for_each(head, geo, child, opaque,
0688                     func, func2, reap, height - 1, count);
0689         else
0690             func(child, opaque, bkey(geo, node, i), count++,
0691                     func2);
0692     }
0693     if (reap)
0694         mempool_free(node, head->mempool);
0695     return count;
0696 }
0697
0698 static void empty(void *elem, unsigned long opaque, unsigned long *key,
0699           size_t index, void *func2)
0700 {
0701 }
0702
0703 void visitorl(void *elem, unsigned long opaque, unsigned long *key,
0704           size_t index, void *__func)
0705 {
0706     visitorl_t func = __func;
0707
0708     func(elem, opaque, *key, index);
0709 }
0710 EXPORT_SYMBOL_GPL(visitorl);
0711
0712 void visitor32(void *elem, unsigned long opaque, unsigned long *__key,
0713            size_t index, void *__func)
0714 {
0715     visitor32_t func = __func;
0716     u32 *key = (void *)__key;
0717
0718     func(elem, opaque, *key, index);
0719 }
0720 EXPORT_SYMBOL_GPL(visitor32);
0721
0722 void visitor64(void *elem, unsigned long opaque, unsigned long *__key,
0723            size_t index, void *__func)
0724 {
0725     visitor64_t func = __func;
0726     u64 *key = (void *)__key;
0727
0728     func(elem, opaque, *key, index);
0729 }
0730 EXPORT_SYMBOL_GPL(visitor64);
0731
0732 void visitor128(void *elem, unsigned long opaque, unsigned long *__key,
0733         size_t index, void *__func)
0734 {
0735     visitor128_t func = __func;
0736     u64 *key = (void *)__key;
0737
0738     func(elem, opaque, key[0], key[1], index);
0739 }
0740 EXPORT_SYMBOL_GPL(visitor128);
0741
0742 size_t btree_visitor(struct btree_head *head, struct btree_geo *geo,
0743              unsigned long opaque,
0744              void (*func)(void *elem, unsigned long opaque,
0745                       unsigned long *key,
0746                       size_t index, void *func2),
0747              void *func2)
0748 {
0749     size_t count = 0;
0750
0751     if (!func2)
0752         func = empty;
0753     if (head->node)
0754         count = __btree_for_each(head, geo, head->node, opaque, func,
0755                 func2, 0, head->height, 0);
0756     return count;
0757 }
0758 EXPORT_SYMBOL_GPL(btree_visitor);
0759
0760 size_t btree_grim_visitor(struct btree_head *head, struct btree_geo *geo,
0761               unsigned long opaque,
0762               void (*func)(void *elem, unsigned long opaque,
0763                        unsigned long *key,
0764                        size_t index, void *func2),
0765               void *func2)
0766 {
0767     size_t count = 0;
0768
0769     if (!func2)
0770         func = empty;
0771     if (head->node)
0772         count = __btree_for_each(head, geo, head->node, opaque, func,
0773                 func2, 1, head->height, 0);
0774     __btree_init(head);
0775     return count;
0776 }
0777 EXPORT_SYMBOL_GPL(btree_grim_visitor);
0778
0779 static int __init btree_module_init(void)
0780 {
0781     btree_cachep = kmem_cache_create("btree_node", NODESIZE, 0,
0782             SLAB_HWCACHE_ALIGN, NULL);
0783     return 0;
0784 }
0785
0786 static void __exit btree_module_exit(void)
0787 {
0788     kmem_cache_destroy(btree_cachep);
0789 }
0790
0791 /* If core code starts using btree, initialization should happen even earlier */
0792 module_init(btree_module_init);
0793 module_exit(btree_module_exit);
0794
0795 MODULE_AUTHOR("Joern Engel <joern@logfs.org>");
0796 MODULE_AUTHOR("Johannes Berg <johannes@sipsolutions.net>");
0797 MODULE_LICENSE("GPL");