Back to home page

LXR

 
 

    


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