1bb9b83dfSThomas Gleixner // SPDX-License-Identifier: GPL-2.0-only
25db53f3eSJoern Engel /*
35db53f3eSJoern Engel * lib/btree.c - Simple In-memory B+Tree
45db53f3eSJoern Engel *
58df3aaafSJoern Engel * Copyright (c) 2007-2008 Joern Engel <joern@purestorage.com>
65db53f3eSJoern Engel * Bits and pieces stolen from Peter Zijlstra's code, which is
790eec103SPeter Zijlstra * Copyright 2007, Red Hat Inc. Peter Zijlstra
85db53f3eSJoern Engel *
95db53f3eSJoern Engel * see http://programming.kicks-ass.net/kernel-patches/vma_lookup/btree.patch
105db53f3eSJoern Engel *
115db53f3eSJoern Engel * A relatively simple B+Tree implementation. I have written it as a learning
1225985edcSLucas De Marchi * exercise to understand how B+Trees work. Turned out to be useful as well.
135db53f3eSJoern Engel *
145db53f3eSJoern Engel * B+Trees can be used similar to Linux radix trees (which don't have anything
155db53f3eSJoern Engel * in common with textbook radix trees, beware). Prerequisite for them working
165db53f3eSJoern Engel * well is that access to a random tree node is much faster than a large number
175db53f3eSJoern Engel * of operations within each node.
185db53f3eSJoern Engel *
195db53f3eSJoern Engel * Disks have fulfilled the prerequisite for a long time. More recently DRAM
205db53f3eSJoern Engel * has gained similar properties, as memory access times, when measured in cpu
215db53f3eSJoern Engel * cycles, have increased. Cacheline sizes have increased as well, which also
225db53f3eSJoern Engel * helps B+Trees.
235db53f3eSJoern Engel *
245db53f3eSJoern Engel * Compared to radix trees, B+Trees are more efficient when dealing with a
255db53f3eSJoern Engel * sparsely populated address space. Between 25% and 50% of the memory is
265db53f3eSJoern Engel * occupied with valid pointers. When densely populated, radix trees contain
275db53f3eSJoern Engel * ~98% pointers - hard to beat. Very sparse radix trees contain only ~2%
285db53f3eSJoern Engel * pointers.
295db53f3eSJoern Engel *
305db53f3eSJoern Engel * This particular implementation stores pointers identified by a long value.
315db53f3eSJoern Engel * Storing NULL pointers is illegal, lookup will return NULL when no entry
325db53f3eSJoern Engel * was found.
335db53f3eSJoern Engel *
345db53f3eSJoern Engel * A tricks was used that is not commonly found in textbooks. The lowest
355db53f3eSJoern Engel * values are to the right, not to the left. All used slots within a node
365db53f3eSJoern Engel * are on the left, all unused slots contain NUL values. Most operations
375db53f3eSJoern Engel * simply loop once over all slots and terminate on the first NUL.
385db53f3eSJoern Engel */
395db53f3eSJoern Engel
405db53f3eSJoern Engel #include <linux/btree.h>
415db53f3eSJoern Engel #include <linux/cache.h>
425db53f3eSJoern Engel #include <linux/kernel.h>
435db53f3eSJoern Engel #include <linux/slab.h>
445db53f3eSJoern Engel #include <linux/module.h>
455db53f3eSJoern Engel
465db53f3eSJoern Engel #define MAX(a, b) ((a) > (b) ? (a) : (b))
475db53f3eSJoern Engel #define NODESIZE MAX(L1_CACHE_BYTES, 128)
485db53f3eSJoern Engel
495db53f3eSJoern Engel struct btree_geo {
505db53f3eSJoern Engel int keylen;
515db53f3eSJoern Engel int no_pairs;
525db53f3eSJoern Engel int no_longs;
535db53f3eSJoern Engel };
545db53f3eSJoern Engel
555db53f3eSJoern Engel struct btree_geo btree_geo32 = {
565db53f3eSJoern Engel .keylen = 1,
575db53f3eSJoern Engel .no_pairs = NODESIZE / sizeof(long) / 2,
585db53f3eSJoern Engel .no_longs = NODESIZE / sizeof(long) / 2,
595db53f3eSJoern Engel };
605db53f3eSJoern Engel EXPORT_SYMBOL_GPL(btree_geo32);
615db53f3eSJoern Engel
625db53f3eSJoern Engel #define LONG_PER_U64 (64 / BITS_PER_LONG)
635db53f3eSJoern Engel struct btree_geo btree_geo64 = {
645db53f3eSJoern Engel .keylen = LONG_PER_U64,
655db53f3eSJoern Engel .no_pairs = NODESIZE / sizeof(long) / (1 + LONG_PER_U64),
665db53f3eSJoern Engel .no_longs = LONG_PER_U64 * (NODESIZE / sizeof(long) / (1 + LONG_PER_U64)),
675db53f3eSJoern Engel };
685db53f3eSJoern Engel EXPORT_SYMBOL_GPL(btree_geo64);
695db53f3eSJoern Engel
705db53f3eSJoern Engel struct btree_geo btree_geo128 = {
715db53f3eSJoern Engel .keylen = 2 * LONG_PER_U64,
725db53f3eSJoern Engel .no_pairs = NODESIZE / sizeof(long) / (1 + 2 * LONG_PER_U64),
735db53f3eSJoern Engel .no_longs = 2 * LONG_PER_U64 * (NODESIZE / sizeof(long) / (1 + 2 * LONG_PER_U64)),
745db53f3eSJoern Engel };
755db53f3eSJoern Engel EXPORT_SYMBOL_GPL(btree_geo128);
765db53f3eSJoern Engel
778df3aaafSJoern Engel #define MAX_KEYLEN (2 * LONG_PER_U64)
788df3aaafSJoern Engel
795db53f3eSJoern Engel static struct kmem_cache *btree_cachep;
805db53f3eSJoern Engel
btree_alloc(gfp_t gfp_mask,void * pool_data)815db53f3eSJoern Engel void *btree_alloc(gfp_t gfp_mask, void *pool_data)
825db53f3eSJoern Engel {
835db53f3eSJoern Engel return kmem_cache_alloc(btree_cachep, gfp_mask);
845db53f3eSJoern Engel }
855db53f3eSJoern Engel EXPORT_SYMBOL_GPL(btree_alloc);
865db53f3eSJoern Engel
btree_free(void * element,void * pool_data)875db53f3eSJoern Engel void btree_free(void *element, void *pool_data)
885db53f3eSJoern Engel {
895db53f3eSJoern Engel kmem_cache_free(btree_cachep, element);
905db53f3eSJoern Engel }
915db53f3eSJoern Engel EXPORT_SYMBOL_GPL(btree_free);
925db53f3eSJoern Engel
btree_node_alloc(struct btree_head * head,gfp_t gfp)935db53f3eSJoern Engel static unsigned long *btree_node_alloc(struct btree_head *head, gfp_t gfp)
945db53f3eSJoern Engel {
955db53f3eSJoern Engel unsigned long *node;
965db53f3eSJoern Engel
975db53f3eSJoern Engel node = mempool_alloc(head->mempool, gfp);
9843aa7ac7Skirjanov@gmail.com if (likely(node))
995db53f3eSJoern Engel memset(node, 0, NODESIZE);
1005db53f3eSJoern Engel return node;
1015db53f3eSJoern Engel }
1025db53f3eSJoern Engel
longcmp(const unsigned long * l1,const unsigned long * l2,size_t n)1035db53f3eSJoern Engel static int longcmp(const unsigned long *l1, const unsigned long *l2, size_t n)
1045db53f3eSJoern Engel {
1055db53f3eSJoern Engel size_t i;
1065db53f3eSJoern Engel
1075db53f3eSJoern Engel for (i = 0; i < n; i++) {
1085db53f3eSJoern Engel if (l1[i] < l2[i])
1095db53f3eSJoern Engel return -1;
1105db53f3eSJoern Engel if (l1[i] > l2[i])
1115db53f3eSJoern Engel return 1;
1125db53f3eSJoern Engel }
1135db53f3eSJoern Engel return 0;
1145db53f3eSJoern Engel }
1155db53f3eSJoern Engel
longcpy(unsigned long * dest,const unsigned long * src,size_t n)1165db53f3eSJoern Engel static unsigned long *longcpy(unsigned long *dest, const unsigned long *src,
1175db53f3eSJoern Engel size_t n)
1185db53f3eSJoern Engel {
1195db53f3eSJoern Engel size_t i;
1205db53f3eSJoern Engel
1215db53f3eSJoern Engel for (i = 0; i < n; i++)
1225db53f3eSJoern Engel dest[i] = src[i];
1235db53f3eSJoern Engel return dest;
1245db53f3eSJoern Engel }
1255db53f3eSJoern Engel
longset(unsigned long * s,unsigned long c,size_t n)1265db53f3eSJoern Engel static unsigned long *longset(unsigned long *s, unsigned long c, size_t n)
1275db53f3eSJoern Engel {
1285db53f3eSJoern Engel size_t i;
1295db53f3eSJoern Engel
1305db53f3eSJoern Engel for (i = 0; i < n; i++)
1315db53f3eSJoern Engel s[i] = c;
1325db53f3eSJoern Engel return s;
1335db53f3eSJoern Engel }
1345db53f3eSJoern Engel
dec_key(struct btree_geo * geo,unsigned long * key)1355db53f3eSJoern Engel static void dec_key(struct btree_geo *geo, unsigned long *key)
1365db53f3eSJoern Engel {
1375db53f3eSJoern Engel unsigned long val;
1385db53f3eSJoern Engel int i;
1395db53f3eSJoern Engel
1405db53f3eSJoern Engel for (i = geo->keylen - 1; i >= 0; i--) {
1415db53f3eSJoern Engel val = key[i];
1425db53f3eSJoern Engel key[i] = val - 1;
1435db53f3eSJoern Engel if (val)
1445db53f3eSJoern Engel break;
1455db53f3eSJoern Engel }
1465db53f3eSJoern Engel }
1475db53f3eSJoern Engel
bkey(struct btree_geo * geo,unsigned long * node,int n)1485db53f3eSJoern Engel static unsigned long *bkey(struct btree_geo *geo, unsigned long *node, int n)
1495db53f3eSJoern Engel {
1505db53f3eSJoern Engel return &node[n * geo->keylen];
1515db53f3eSJoern Engel }
1525db53f3eSJoern Engel
bval(struct btree_geo * geo,unsigned long * node,int n)1535db53f3eSJoern Engel static void *bval(struct btree_geo *geo, unsigned long *node, int n)
1545db53f3eSJoern Engel {
1555db53f3eSJoern Engel return (void *)node[geo->no_longs + n];
1565db53f3eSJoern Engel }
1575db53f3eSJoern Engel
setkey(struct btree_geo * geo,unsigned long * node,int n,unsigned long * key)1585db53f3eSJoern Engel static void setkey(struct btree_geo *geo, unsigned long *node, int n,
1595db53f3eSJoern Engel unsigned long *key)
1605db53f3eSJoern Engel {
1615db53f3eSJoern Engel longcpy(bkey(geo, node, n), key, geo->keylen);
1625db53f3eSJoern Engel }
1635db53f3eSJoern Engel
setval(struct btree_geo * geo,unsigned long * node,int n,void * val)1645db53f3eSJoern Engel static void setval(struct btree_geo *geo, unsigned long *node, int n,
1655db53f3eSJoern Engel void *val)
1665db53f3eSJoern Engel {
1675db53f3eSJoern Engel node[geo->no_longs + n] = (unsigned long) val;
1685db53f3eSJoern Engel }
1695db53f3eSJoern Engel
clearpair(struct btree_geo * geo,unsigned long * node,int n)1705db53f3eSJoern Engel static void clearpair(struct btree_geo *geo, unsigned long *node, int n)
1715db53f3eSJoern Engel {
1725db53f3eSJoern Engel longset(bkey(geo, node, n), 0, geo->keylen);
1735db53f3eSJoern Engel node[geo->no_longs + n] = 0;
1745db53f3eSJoern Engel }
1755db53f3eSJoern Engel
__btree_init(struct btree_head * head)1765db53f3eSJoern Engel static inline void __btree_init(struct btree_head *head)
1775db53f3eSJoern Engel {
1785db53f3eSJoern Engel head->node = NULL;
1795db53f3eSJoern Engel head->height = 0;
1805db53f3eSJoern Engel }
1815db53f3eSJoern Engel
btree_init_mempool(struct btree_head * head,mempool_t * mempool)1825db53f3eSJoern Engel void btree_init_mempool(struct btree_head *head, mempool_t *mempool)
1835db53f3eSJoern Engel {
1845db53f3eSJoern Engel __btree_init(head);
1855db53f3eSJoern Engel head->mempool = mempool;
1865db53f3eSJoern Engel }
1875db53f3eSJoern Engel EXPORT_SYMBOL_GPL(btree_init_mempool);
1885db53f3eSJoern Engel
btree_init(struct btree_head * head)1895db53f3eSJoern Engel int btree_init(struct btree_head *head)
1905db53f3eSJoern Engel {
1915db53f3eSJoern Engel __btree_init(head);
1925db53f3eSJoern Engel head->mempool = mempool_create(0, btree_alloc, btree_free, NULL);
1935db53f3eSJoern Engel if (!head->mempool)
1945db53f3eSJoern Engel return -ENOMEM;
1955db53f3eSJoern Engel return 0;
1965db53f3eSJoern Engel }
1975db53f3eSJoern Engel EXPORT_SYMBOL_GPL(btree_init);
1985db53f3eSJoern Engel
btree_destroy(struct btree_head * head)1995db53f3eSJoern Engel void btree_destroy(struct btree_head *head)
2005db53f3eSJoern Engel {
201c75b53afSMinfei Huang mempool_free(head->node, head->mempool);
2025db53f3eSJoern Engel mempool_destroy(head->mempool);
2035db53f3eSJoern Engel head->mempool = NULL;
2045db53f3eSJoern Engel }
2055db53f3eSJoern Engel EXPORT_SYMBOL_GPL(btree_destroy);
2065db53f3eSJoern Engel
btree_last(struct btree_head * head,struct btree_geo * geo,unsigned long * key)2075db53f3eSJoern Engel void *btree_last(struct btree_head *head, struct btree_geo *geo,
2085db53f3eSJoern Engel unsigned long *key)
2095db53f3eSJoern Engel {
2105db53f3eSJoern Engel int height = head->height;
2115db53f3eSJoern Engel unsigned long *node = head->node;
2125db53f3eSJoern Engel
2135db53f3eSJoern Engel if (height == 0)
2145db53f3eSJoern Engel return NULL;
2155db53f3eSJoern Engel
2165db53f3eSJoern Engel for ( ; height > 1; height--)
2175db53f3eSJoern Engel node = bval(geo, node, 0);
2185db53f3eSJoern Engel
2195db53f3eSJoern Engel longcpy(key, bkey(geo, node, 0), geo->keylen);
2205db53f3eSJoern Engel return bval(geo, node, 0);
2215db53f3eSJoern Engel }
2225db53f3eSJoern Engel EXPORT_SYMBOL_GPL(btree_last);
2235db53f3eSJoern Engel
keycmp(struct btree_geo * geo,unsigned long * node,int pos,unsigned long * key)2245db53f3eSJoern Engel static int keycmp(struct btree_geo *geo, unsigned long *node, int pos,
2255db53f3eSJoern Engel unsigned long *key)
2265db53f3eSJoern Engel {
2275db53f3eSJoern Engel return longcmp(bkey(geo, node, pos), key, geo->keylen);
2285db53f3eSJoern Engel }
2295db53f3eSJoern Engel
keyzero(struct btree_geo * geo,unsigned long * key)2305db53f3eSJoern Engel static int keyzero(struct btree_geo *geo, unsigned long *key)
2315db53f3eSJoern Engel {
2325db53f3eSJoern Engel int i;
2335db53f3eSJoern Engel
2345db53f3eSJoern Engel for (i = 0; i < geo->keylen; i++)
2355db53f3eSJoern Engel if (key[i])
2365db53f3eSJoern Engel return 0;
2375db53f3eSJoern Engel
2385db53f3eSJoern Engel return 1;
2395db53f3eSJoern Engel }
2405db53f3eSJoern Engel
btree_lookup_node(struct btree_head * head,struct btree_geo * geo,unsigned long * key)241*c0af32fdSwuchi static void *btree_lookup_node(struct btree_head *head, struct btree_geo *geo,
2425db53f3eSJoern Engel unsigned long *key)
2435db53f3eSJoern Engel {
2445db53f3eSJoern Engel int i, height = head->height;
2455db53f3eSJoern Engel unsigned long *node = head->node;
2465db53f3eSJoern Engel
2475db53f3eSJoern Engel if (height == 0)
2485db53f3eSJoern Engel return NULL;
2495db53f3eSJoern Engel
2505db53f3eSJoern Engel for ( ; height > 1; height--) {
2515db53f3eSJoern Engel for (i = 0; i < geo->no_pairs; i++)
2525db53f3eSJoern Engel if (keycmp(geo, node, i, key) <= 0)
2535db53f3eSJoern Engel break;
2545db53f3eSJoern Engel if (i == geo->no_pairs)
2555db53f3eSJoern Engel return NULL;
2565db53f3eSJoern Engel node = bval(geo, node, i);
2575db53f3eSJoern Engel if (!node)
2585db53f3eSJoern Engel return NULL;
2595db53f3eSJoern Engel }
260*c0af32fdSwuchi return node;
261*c0af32fdSwuchi }
2625db53f3eSJoern Engel
btree_lookup(struct btree_head * head,struct btree_geo * geo,unsigned long * key)263*c0af32fdSwuchi void *btree_lookup(struct btree_head *head, struct btree_geo *geo,
264*c0af32fdSwuchi unsigned long *key)
265*c0af32fdSwuchi {
266*c0af32fdSwuchi int i;
267*c0af32fdSwuchi unsigned long *node;
268*c0af32fdSwuchi
269*c0af32fdSwuchi node = btree_lookup_node(head, geo, key);
2705db53f3eSJoern Engel if (!node)
2715db53f3eSJoern Engel return NULL;
2725db53f3eSJoern Engel
2735db53f3eSJoern Engel for (i = 0; i < geo->no_pairs; i++)
2745db53f3eSJoern Engel if (keycmp(geo, node, i, key) == 0)
2755db53f3eSJoern Engel return bval(geo, node, i);
2765db53f3eSJoern Engel return NULL;
2775db53f3eSJoern Engel }
2785db53f3eSJoern Engel EXPORT_SYMBOL_GPL(btree_lookup);
2795db53f3eSJoern Engel
btree_update(struct btree_head * head,struct btree_geo * geo,unsigned long * key,void * val)2805db53f3eSJoern Engel int btree_update(struct btree_head *head, struct btree_geo *geo,
2815db53f3eSJoern Engel unsigned long *key, void *val)
2825db53f3eSJoern Engel {
283*c0af32fdSwuchi int i;
284*c0af32fdSwuchi unsigned long *node;
2855db53f3eSJoern Engel
286*c0af32fdSwuchi node = btree_lookup_node(head, geo, key);
2875db53f3eSJoern Engel if (!node)
2885db53f3eSJoern Engel return -ENOENT;
2895db53f3eSJoern Engel
2905db53f3eSJoern Engel for (i = 0; i < geo->no_pairs; i++)
2915db53f3eSJoern Engel if (keycmp(geo, node, i, key) == 0) {
2925db53f3eSJoern Engel setval(geo, node, i, val);
2935db53f3eSJoern Engel return 0;
2945db53f3eSJoern Engel }
2955db53f3eSJoern Engel return -ENOENT;
2965db53f3eSJoern Engel }
2975db53f3eSJoern Engel EXPORT_SYMBOL_GPL(btree_update);
2985db53f3eSJoern Engel
2995db53f3eSJoern Engel /*
3005db53f3eSJoern Engel * Usually this function is quite similar to normal lookup. But the key of
3015db53f3eSJoern Engel * a parent node may be smaller than the smallest key of all its siblings.
3025db53f3eSJoern Engel * In such a case we cannot just return NULL, as we have only proven that no
3035db53f3eSJoern Engel * key smaller than __key, but larger than this parent key exists.
3045db53f3eSJoern Engel * So we set __key to the parent key and retry. We have to use the smallest
3055db53f3eSJoern Engel * such parent key, which is the last parent key we encountered.
3065db53f3eSJoern Engel */
btree_get_prev(struct btree_head * head,struct btree_geo * geo,unsigned long * __key)3075db53f3eSJoern Engel void *btree_get_prev(struct btree_head *head, struct btree_geo *geo,
3085db53f3eSJoern Engel unsigned long *__key)
3095db53f3eSJoern Engel {
3105db53f3eSJoern Engel int i, height;
3115db53f3eSJoern Engel unsigned long *node, *oldnode;
3128df3aaafSJoern Engel unsigned long *retry_key = NULL, key[MAX_KEYLEN];
3135db53f3eSJoern Engel
3145db53f3eSJoern Engel if (keyzero(geo, __key))
3155db53f3eSJoern Engel return NULL;
3165db53f3eSJoern Engel
3175db53f3eSJoern Engel if (head->height == 0)
3185db53f3eSJoern Engel return NULL;
3195db53f3eSJoern Engel longcpy(key, __key, geo->keylen);
320cbf8ae32SRoland Dreier retry:
3215db53f3eSJoern Engel dec_key(geo, key);
3225db53f3eSJoern Engel
3235db53f3eSJoern Engel node = head->node;
3245db53f3eSJoern Engel for (height = head->height ; height > 1; height--) {
3255db53f3eSJoern Engel for (i = 0; i < geo->no_pairs; i++)
3265db53f3eSJoern Engel if (keycmp(geo, node, i, key) <= 0)
3275db53f3eSJoern Engel break;
3285db53f3eSJoern Engel if (i == geo->no_pairs)
3295db53f3eSJoern Engel goto miss;
3305db53f3eSJoern Engel oldnode = node;
3315db53f3eSJoern Engel node = bval(geo, node, i);
3325db53f3eSJoern Engel if (!node)
3335db53f3eSJoern Engel goto miss;
3345db53f3eSJoern Engel retry_key = bkey(geo, oldnode, i);
3355db53f3eSJoern Engel }
3365db53f3eSJoern Engel
3375db53f3eSJoern Engel if (!node)
3385db53f3eSJoern Engel goto miss;
3395db53f3eSJoern Engel
3405db53f3eSJoern Engel for (i = 0; i < geo->no_pairs; i++) {
3415db53f3eSJoern Engel if (keycmp(geo, node, i, key) <= 0) {
3425db53f3eSJoern Engel if (bval(geo, node, i)) {
3435db53f3eSJoern Engel longcpy(__key, bkey(geo, node, i), geo->keylen);
3445db53f3eSJoern Engel return bval(geo, node, i);
3455db53f3eSJoern Engel } else
3465db53f3eSJoern Engel goto miss;
3475db53f3eSJoern Engel }
3485db53f3eSJoern Engel }
3495db53f3eSJoern Engel miss:
3505db53f3eSJoern Engel if (retry_key) {
351cbf8ae32SRoland Dreier longcpy(key, retry_key, geo->keylen);
3525db53f3eSJoern Engel retry_key = NULL;
3535db53f3eSJoern Engel goto retry;
3545db53f3eSJoern Engel }
3555db53f3eSJoern Engel return NULL;
3565db53f3eSJoern Engel }
35796b62067SSteve Hodgson EXPORT_SYMBOL_GPL(btree_get_prev);
3585db53f3eSJoern Engel
getpos(struct btree_geo * geo,unsigned long * node,unsigned long * key)3595db53f3eSJoern Engel static int getpos(struct btree_geo *geo, unsigned long *node,
3605db53f3eSJoern Engel unsigned long *key)
3615db53f3eSJoern Engel {
3625db53f3eSJoern Engel int i;
3635db53f3eSJoern Engel
3645db53f3eSJoern Engel for (i = 0; i < geo->no_pairs; i++) {
3655db53f3eSJoern Engel if (keycmp(geo, node, i, key) <= 0)
3665db53f3eSJoern Engel break;
3675db53f3eSJoern Engel }
3685db53f3eSJoern Engel return i;
3695db53f3eSJoern Engel }
3705db53f3eSJoern Engel
getfill(struct btree_geo * geo,unsigned long * node,int start)3715db53f3eSJoern Engel static int getfill(struct btree_geo *geo, unsigned long *node, int start)
3725db53f3eSJoern Engel {
3735db53f3eSJoern Engel int i;
3745db53f3eSJoern Engel
3755db53f3eSJoern Engel for (i = start; i < geo->no_pairs; i++)
3765db53f3eSJoern Engel if (!bval(geo, node, i))
3775db53f3eSJoern Engel break;
3785db53f3eSJoern Engel return i;
3795db53f3eSJoern Engel }
3805db53f3eSJoern Engel
3815db53f3eSJoern Engel /*
3825db53f3eSJoern Engel * locate the correct leaf node in the btree
3835db53f3eSJoern Engel */
find_level(struct btree_head * head,struct btree_geo * geo,unsigned long * key,int level)3845db53f3eSJoern Engel static unsigned long *find_level(struct btree_head *head, struct btree_geo *geo,
3855db53f3eSJoern Engel unsigned long *key, int level)
3865db53f3eSJoern Engel {
3875db53f3eSJoern Engel unsigned long *node = head->node;
3885db53f3eSJoern Engel int i, height;
3895db53f3eSJoern Engel
3905db53f3eSJoern Engel for (height = head->height; height > level; height--) {
3915db53f3eSJoern Engel for (i = 0; i < geo->no_pairs; i++)
3925db53f3eSJoern Engel if (keycmp(geo, node, i, key) <= 0)
3935db53f3eSJoern Engel break;
3945db53f3eSJoern Engel
3955db53f3eSJoern Engel if ((i == geo->no_pairs) || !bval(geo, node, i)) {
3965db53f3eSJoern Engel /* right-most key is too large, update it */
3975db53f3eSJoern Engel /* FIXME: If the right-most key on higher levels is
3985db53f3eSJoern Engel * always zero, this wouldn't be necessary. */
3995db53f3eSJoern Engel i--;
4005db53f3eSJoern Engel setkey(geo, node, i, key);
4015db53f3eSJoern Engel }
4025db53f3eSJoern Engel BUG_ON(i < 0);
4035db53f3eSJoern Engel node = bval(geo, node, i);
4045db53f3eSJoern Engel }
4055db53f3eSJoern Engel BUG_ON(!node);
4065db53f3eSJoern Engel return node;
4075db53f3eSJoern Engel }
4085db53f3eSJoern Engel
btree_grow(struct btree_head * head,struct btree_geo * geo,gfp_t gfp)4095db53f3eSJoern Engel static int btree_grow(struct btree_head *head, struct btree_geo *geo,
4105db53f3eSJoern Engel gfp_t gfp)
4115db53f3eSJoern Engel {
4125db53f3eSJoern Engel unsigned long *node;
4135db53f3eSJoern Engel int fill;
4145db53f3eSJoern Engel
4155db53f3eSJoern Engel node = btree_node_alloc(head, gfp);
4165db53f3eSJoern Engel if (!node)
4175db53f3eSJoern Engel return -ENOMEM;
4185db53f3eSJoern Engel if (head->node) {
4195db53f3eSJoern Engel fill = getfill(geo, head->node, 0);
4205db53f3eSJoern Engel setkey(geo, node, 0, bkey(geo, head->node, fill - 1));
4215db53f3eSJoern Engel setval(geo, node, 0, head->node);
4225db53f3eSJoern Engel }
4235db53f3eSJoern Engel head->node = node;
4245db53f3eSJoern Engel head->height++;
4255db53f3eSJoern Engel return 0;
4265db53f3eSJoern Engel }
4275db53f3eSJoern Engel
btree_shrink(struct btree_head * head,struct btree_geo * geo)4285db53f3eSJoern Engel static void btree_shrink(struct btree_head *head, struct btree_geo *geo)
4295db53f3eSJoern Engel {
4305db53f3eSJoern Engel unsigned long *node;
4315db53f3eSJoern Engel int fill;
4325db53f3eSJoern Engel
4335db53f3eSJoern Engel if (head->height <= 1)
4345db53f3eSJoern Engel return;
4355db53f3eSJoern Engel
4365db53f3eSJoern Engel node = head->node;
4375db53f3eSJoern Engel fill = getfill(geo, node, 0);
4385db53f3eSJoern Engel BUG_ON(fill > 1);
4395db53f3eSJoern Engel head->node = bval(geo, node, 0);
4405db53f3eSJoern Engel head->height--;
4415db53f3eSJoern Engel mempool_free(node, head->mempool);
4425db53f3eSJoern Engel }
4435db53f3eSJoern Engel
btree_insert_level(struct btree_head * head,struct btree_geo * geo,unsigned long * key,void * val,int level,gfp_t gfp)4445db53f3eSJoern Engel static int btree_insert_level(struct btree_head *head, struct btree_geo *geo,
4455db53f3eSJoern Engel unsigned long *key, void *val, int level,
4465db53f3eSJoern Engel gfp_t gfp)
4475db53f3eSJoern Engel {
4485db53f3eSJoern Engel unsigned long *node;
4495db53f3eSJoern Engel int i, pos, fill, err;
4505db53f3eSJoern Engel
4515db53f3eSJoern Engel BUG_ON(!val);
4525db53f3eSJoern Engel if (head->height < level) {
4535db53f3eSJoern Engel err = btree_grow(head, geo, gfp);
4545db53f3eSJoern Engel if (err)
4555db53f3eSJoern Engel return err;
4565db53f3eSJoern Engel }
4575db53f3eSJoern Engel
4585db53f3eSJoern Engel retry:
4595db53f3eSJoern Engel node = find_level(head, geo, key, level);
4605db53f3eSJoern Engel pos = getpos(geo, node, key);
4615db53f3eSJoern Engel fill = getfill(geo, node, pos);
4625db53f3eSJoern Engel /* two identical keys are not allowed */
4635db53f3eSJoern Engel BUG_ON(pos < fill && keycmp(geo, node, pos, key) == 0);
4645db53f3eSJoern Engel
4655db53f3eSJoern Engel if (fill == geo->no_pairs) {
4665db53f3eSJoern Engel /* need to split node */
4675db53f3eSJoern Engel unsigned long *new;
4685db53f3eSJoern Engel
4695db53f3eSJoern Engel new = btree_node_alloc(head, gfp);
4705db53f3eSJoern Engel if (!new)
4715db53f3eSJoern Engel return -ENOMEM;
4725db53f3eSJoern Engel err = btree_insert_level(head, geo,
4735db53f3eSJoern Engel bkey(geo, node, fill / 2 - 1),
4745db53f3eSJoern Engel new, level + 1, gfp);
4755db53f3eSJoern Engel if (err) {
4765db53f3eSJoern Engel mempool_free(new, head->mempool);
4775db53f3eSJoern Engel return err;
4785db53f3eSJoern Engel }
4795db53f3eSJoern Engel for (i = 0; i < fill / 2; i++) {
4805db53f3eSJoern Engel setkey(geo, new, i, bkey(geo, node, i));
4815db53f3eSJoern Engel setval(geo, new, i, bval(geo, node, i));
4825db53f3eSJoern Engel setkey(geo, node, i, bkey(geo, node, i + fill / 2));
4835db53f3eSJoern Engel setval(geo, node, i, bval(geo, node, i + fill / 2));
4845db53f3eSJoern Engel clearpair(geo, node, i + fill / 2);
4855db53f3eSJoern Engel }
4865db53f3eSJoern Engel if (fill & 1) {
4875db53f3eSJoern Engel setkey(geo, node, i, bkey(geo, node, fill - 1));
4885db53f3eSJoern Engel setval(geo, node, i, bval(geo, node, fill - 1));
4895db53f3eSJoern Engel clearpair(geo, node, fill - 1);
4905db53f3eSJoern Engel }
4915db53f3eSJoern Engel goto retry;
4925db53f3eSJoern Engel }
4935db53f3eSJoern Engel BUG_ON(fill >= geo->no_pairs);
4945db53f3eSJoern Engel
4955db53f3eSJoern Engel /* shift and insert */
4965db53f3eSJoern Engel for (i = fill; i > pos; i--) {
4975db53f3eSJoern Engel setkey(geo, node, i, bkey(geo, node, i - 1));
4985db53f3eSJoern Engel setval(geo, node, i, bval(geo, node, i - 1));
4995db53f3eSJoern Engel }
5005db53f3eSJoern Engel setkey(geo, node, pos, key);
5015db53f3eSJoern Engel setval(geo, node, pos, val);
5025db53f3eSJoern Engel
5035db53f3eSJoern Engel return 0;
5045db53f3eSJoern Engel }
5055db53f3eSJoern Engel
btree_insert(struct btree_head * head,struct btree_geo * geo,unsigned long * key,void * val,gfp_t gfp)5065db53f3eSJoern Engel int btree_insert(struct btree_head *head, struct btree_geo *geo,
5075db53f3eSJoern Engel unsigned long *key, void *val, gfp_t gfp)
5085db53f3eSJoern Engel {
50939caa091SJoern Engel BUG_ON(!val);
5105db53f3eSJoern Engel return btree_insert_level(head, geo, key, val, 1, gfp);
5115db53f3eSJoern Engel }
5125db53f3eSJoern Engel EXPORT_SYMBOL_GPL(btree_insert);
5135db53f3eSJoern Engel
5145db53f3eSJoern Engel static void *btree_remove_level(struct btree_head *head, struct btree_geo *geo,
5155db53f3eSJoern Engel unsigned long *key, int level);
merge(struct btree_head * head,struct btree_geo * geo,int level,unsigned long * left,int lfill,unsigned long * right,int rfill,unsigned long * parent,int lpos)5165db53f3eSJoern Engel static void merge(struct btree_head *head, struct btree_geo *geo, int level,
5175db53f3eSJoern Engel unsigned long *left, int lfill,
5185db53f3eSJoern Engel unsigned long *right, int rfill,
5195db53f3eSJoern Engel unsigned long *parent, int lpos)
5205db53f3eSJoern Engel {
5215db53f3eSJoern Engel int i;
5225db53f3eSJoern Engel
5235db53f3eSJoern Engel for (i = 0; i < rfill; i++) {
5245db53f3eSJoern Engel /* Move all keys to the left */
5255db53f3eSJoern Engel setkey(geo, left, lfill + i, bkey(geo, right, i));
5265db53f3eSJoern Engel setval(geo, left, lfill + i, bval(geo, right, i));
5275db53f3eSJoern Engel }
5285db53f3eSJoern Engel /* Exchange left and right child in parent */
5295db53f3eSJoern Engel setval(geo, parent, lpos, right);
5305db53f3eSJoern Engel setval(geo, parent, lpos + 1, left);
5315db53f3eSJoern Engel /* Remove left (formerly right) child from parent */
5325db53f3eSJoern Engel btree_remove_level(head, geo, bkey(geo, parent, lpos), level + 1);
5335db53f3eSJoern Engel mempool_free(right, head->mempool);
5345db53f3eSJoern Engel }
5355db53f3eSJoern Engel
rebalance(struct btree_head * head,struct btree_geo * geo,unsigned long * key,int level,unsigned long * child,int fill)5365db53f3eSJoern Engel static void rebalance(struct btree_head *head, struct btree_geo *geo,
5375db53f3eSJoern Engel unsigned long *key, int level, unsigned long *child, int fill)
5385db53f3eSJoern Engel {
5395db53f3eSJoern Engel unsigned long *parent, *left = NULL, *right = NULL;
5405db53f3eSJoern Engel int i, no_left, no_right;
5415db53f3eSJoern Engel
5425db53f3eSJoern Engel if (fill == 0) {
54325985edcSLucas De Marchi /* Because we don't steal entries from a neighbour, this case
5445db53f3eSJoern Engel * can happen. Parent node contains a single child, this
5455db53f3eSJoern Engel * node, so merging with a sibling never happens.
5465db53f3eSJoern Engel */
5475db53f3eSJoern Engel btree_remove_level(head, geo, key, level + 1);
5485db53f3eSJoern Engel mempool_free(child, head->mempool);
5495db53f3eSJoern Engel return;
5505db53f3eSJoern Engel }
5515db53f3eSJoern Engel
5525db53f3eSJoern Engel parent = find_level(head, geo, key, level + 1);
5535db53f3eSJoern Engel i = getpos(geo, parent, key);
5545db53f3eSJoern Engel BUG_ON(bval(geo, parent, i) != child);
5555db53f3eSJoern Engel
5565db53f3eSJoern Engel if (i > 0) {
5575db53f3eSJoern Engel left = bval(geo, parent, i - 1);
5585db53f3eSJoern Engel no_left = getfill(geo, left, 0);
5595db53f3eSJoern Engel if (fill + no_left <= geo->no_pairs) {
5605db53f3eSJoern Engel merge(head, geo, level,
5615db53f3eSJoern Engel left, no_left,
5625db53f3eSJoern Engel child, fill,
5635db53f3eSJoern Engel parent, i - 1);
5645db53f3eSJoern Engel return;
5655db53f3eSJoern Engel }
5665db53f3eSJoern Engel }
5675db53f3eSJoern Engel if (i + 1 < getfill(geo, parent, i)) {
5685db53f3eSJoern Engel right = bval(geo, parent, i + 1);
5695db53f3eSJoern Engel no_right = getfill(geo, right, 0);
5705db53f3eSJoern Engel if (fill + no_right <= geo->no_pairs) {
5715db53f3eSJoern Engel merge(head, geo, level,
5725db53f3eSJoern Engel child, fill,
5735db53f3eSJoern Engel right, no_right,
5745db53f3eSJoern Engel parent, i);
5755db53f3eSJoern Engel return;
5765db53f3eSJoern Engel }
5775db53f3eSJoern Engel }
5785db53f3eSJoern Engel /*
5795db53f3eSJoern Engel * We could also try to steal one entry from the left or right
5805db53f3eSJoern Engel * neighbor. By not doing so we changed the invariant from
5815db53f3eSJoern Engel * "all nodes are at least half full" to "no two neighboring
5825db53f3eSJoern Engel * nodes can be merged". Which means that the average fill of
5835db53f3eSJoern Engel * all nodes is still half or better.
5845db53f3eSJoern Engel */
5855db53f3eSJoern Engel }
5865db53f3eSJoern Engel
btree_remove_level(struct btree_head * head,struct btree_geo * geo,unsigned long * key,int level)5875db53f3eSJoern Engel static void *btree_remove_level(struct btree_head *head, struct btree_geo *geo,
5885db53f3eSJoern Engel unsigned long *key, int level)
5895db53f3eSJoern Engel {
5905db53f3eSJoern Engel unsigned long *node;
5915db53f3eSJoern Engel int i, pos, fill;
5925db53f3eSJoern Engel void *ret;
5935db53f3eSJoern Engel
5945db53f3eSJoern Engel if (level > head->height) {
5955db53f3eSJoern Engel /* we recursed all the way up */
5965db53f3eSJoern Engel head->height = 0;
5975db53f3eSJoern Engel head->node = NULL;
5985db53f3eSJoern Engel return NULL;
5995db53f3eSJoern Engel }
6005db53f3eSJoern Engel
6015db53f3eSJoern Engel node = find_level(head, geo, key, level);
6025db53f3eSJoern Engel pos = getpos(geo, node, key);
6035db53f3eSJoern Engel fill = getfill(geo, node, pos);
6045db53f3eSJoern Engel if ((level == 1) && (keycmp(geo, node, pos, key) != 0))
6055db53f3eSJoern Engel return NULL;
6065db53f3eSJoern Engel ret = bval(geo, node, pos);
6075db53f3eSJoern Engel
6085db53f3eSJoern Engel /* remove and shift */
6095db53f3eSJoern Engel for (i = pos; i < fill - 1; i++) {
6105db53f3eSJoern Engel setkey(geo, node, i, bkey(geo, node, i + 1));
6115db53f3eSJoern Engel setval(geo, node, i, bval(geo, node, i + 1));
6125db53f3eSJoern Engel }
6135db53f3eSJoern Engel clearpair(geo, node, fill - 1);
6145db53f3eSJoern Engel
6155db53f3eSJoern Engel if (fill - 1 < geo->no_pairs / 2) {
6165db53f3eSJoern Engel if (level < head->height)
6175db53f3eSJoern Engel rebalance(head, geo, key, level, node, fill - 1);
6185db53f3eSJoern Engel else if (fill - 1 == 1)
6195db53f3eSJoern Engel btree_shrink(head, geo);
6205db53f3eSJoern Engel }
6215db53f3eSJoern Engel
6225db53f3eSJoern Engel return ret;
6235db53f3eSJoern Engel }
6245db53f3eSJoern Engel
btree_remove(struct btree_head * head,struct btree_geo * geo,unsigned long * key)6255db53f3eSJoern Engel void *btree_remove(struct btree_head *head, struct btree_geo *geo,
6265db53f3eSJoern Engel unsigned long *key)
6275db53f3eSJoern Engel {
6285db53f3eSJoern Engel if (head->height == 0)
6295db53f3eSJoern Engel return NULL;
6305db53f3eSJoern Engel
6315db53f3eSJoern Engel return btree_remove_level(head, geo, key, 1);
6325db53f3eSJoern Engel }
6335db53f3eSJoern Engel EXPORT_SYMBOL_GPL(btree_remove);
6345db53f3eSJoern Engel
btree_merge(struct btree_head * target,struct btree_head * victim,struct btree_geo * geo,gfp_t gfp)6355db53f3eSJoern Engel int btree_merge(struct btree_head *target, struct btree_head *victim,
6365db53f3eSJoern Engel struct btree_geo *geo, gfp_t gfp)
6375db53f3eSJoern Engel {
6388df3aaafSJoern Engel unsigned long key[MAX_KEYLEN];
6398df3aaafSJoern Engel unsigned long dup[MAX_KEYLEN];
6405db53f3eSJoern Engel void *val;
6415db53f3eSJoern Engel int err;
6425db53f3eSJoern Engel
6435db53f3eSJoern Engel BUG_ON(target == victim);
6445db53f3eSJoern Engel
6455db53f3eSJoern Engel if (!(target->node)) {
6465db53f3eSJoern Engel /* target is empty, just copy fields over */
6475db53f3eSJoern Engel target->node = victim->node;
6485db53f3eSJoern Engel target->height = victim->height;
6495db53f3eSJoern Engel __btree_init(victim);
6505db53f3eSJoern Engel return 0;
6515db53f3eSJoern Engel }
6525db53f3eSJoern Engel
6535db53f3eSJoern Engel /* TODO: This needs some optimizations. Currently we do three tree
6545db53f3eSJoern Engel * walks to remove a single object from the victim.
6555db53f3eSJoern Engel */
6565db53f3eSJoern Engel for (;;) {
6575db53f3eSJoern Engel if (!btree_last(victim, geo, key))
6585db53f3eSJoern Engel break;
6595db53f3eSJoern Engel val = btree_lookup(victim, geo, key);
6605db53f3eSJoern Engel err = btree_insert(target, geo, key, val, gfp);
6615db53f3eSJoern Engel if (err)
6625db53f3eSJoern Engel return err;
6635db53f3eSJoern Engel /* We must make a copy of the key, as the original will get
6645db53f3eSJoern Engel * mangled inside btree_remove. */
6655db53f3eSJoern Engel longcpy(dup, key, geo->keylen);
6665db53f3eSJoern Engel btree_remove(victim, geo, dup);
6675db53f3eSJoern Engel }
6685db53f3eSJoern Engel return 0;
6695db53f3eSJoern Engel }
6705db53f3eSJoern Engel EXPORT_SYMBOL_GPL(btree_merge);
6715db53f3eSJoern Engel
__btree_for_each(struct btree_head * head,struct btree_geo * geo,unsigned long * node,unsigned long opaque,void (* func)(void * elem,unsigned long opaque,unsigned long * key,size_t index,void * func2),void * func2,int reap,int height,size_t count)6725db53f3eSJoern Engel static size_t __btree_for_each(struct btree_head *head, struct btree_geo *geo,
6735db53f3eSJoern Engel unsigned long *node, unsigned long opaque,
6745db53f3eSJoern Engel void (*func)(void *elem, unsigned long opaque,
6755db53f3eSJoern Engel unsigned long *key, size_t index,
6765db53f3eSJoern Engel void *func2),
6775db53f3eSJoern Engel void *func2, int reap, int height, size_t count)
6785db53f3eSJoern Engel {
6795db53f3eSJoern Engel int i;
6805db53f3eSJoern Engel unsigned long *child;
6815db53f3eSJoern Engel
6825db53f3eSJoern Engel for (i = 0; i < geo->no_pairs; i++) {
6835db53f3eSJoern Engel child = bval(geo, node, i);
6845db53f3eSJoern Engel if (!child)
6855db53f3eSJoern Engel break;
6865db53f3eSJoern Engel if (height > 1)
6875db53f3eSJoern Engel count = __btree_for_each(head, geo, child, opaque,
6885db53f3eSJoern Engel func, func2, reap, height - 1, count);
6895db53f3eSJoern Engel else
6905db53f3eSJoern Engel func(child, opaque, bkey(geo, node, i), count++,
6915db53f3eSJoern Engel func2);
6925db53f3eSJoern Engel }
6935db53f3eSJoern Engel if (reap)
6945db53f3eSJoern Engel mempool_free(node, head->mempool);
6955db53f3eSJoern Engel return count;
6965db53f3eSJoern Engel }
6975db53f3eSJoern Engel
empty(void * elem,unsigned long opaque,unsigned long * key,size_t index,void * func2)6985db53f3eSJoern Engel static void empty(void *elem, unsigned long opaque, unsigned long *key,
6995db53f3eSJoern Engel size_t index, void *func2)
7005db53f3eSJoern Engel {
7015db53f3eSJoern Engel }
7025db53f3eSJoern Engel
visitorl(void * elem,unsigned long opaque,unsigned long * key,size_t index,void * __func)7035db53f3eSJoern Engel void visitorl(void *elem, unsigned long opaque, unsigned long *key,
7045db53f3eSJoern Engel size_t index, void *__func)
7055db53f3eSJoern Engel {
7065db53f3eSJoern Engel visitorl_t func = __func;
7075db53f3eSJoern Engel
7085db53f3eSJoern Engel func(elem, opaque, *key, index);
7095db53f3eSJoern Engel }
7105db53f3eSJoern Engel EXPORT_SYMBOL_GPL(visitorl);
7115db53f3eSJoern Engel
visitor32(void * elem,unsigned long opaque,unsigned long * __key,size_t index,void * __func)7125db53f3eSJoern Engel void visitor32(void *elem, unsigned long opaque, unsigned long *__key,
7135db53f3eSJoern Engel size_t index, void *__func)
7145db53f3eSJoern Engel {
7155db53f3eSJoern Engel visitor32_t func = __func;
7165db53f3eSJoern Engel u32 *key = (void *)__key;
7175db53f3eSJoern Engel
7185db53f3eSJoern Engel func(elem, opaque, *key, index);
7195db53f3eSJoern Engel }
7205db53f3eSJoern Engel EXPORT_SYMBOL_GPL(visitor32);
7215db53f3eSJoern Engel
visitor64(void * elem,unsigned long opaque,unsigned long * __key,size_t index,void * __func)7225db53f3eSJoern Engel void visitor64(void *elem, unsigned long opaque, unsigned long *__key,
7235db53f3eSJoern Engel size_t index, void *__func)
7245db53f3eSJoern Engel {
7255db53f3eSJoern Engel visitor64_t func = __func;
7265db53f3eSJoern Engel u64 *key = (void *)__key;
7275db53f3eSJoern Engel
7285db53f3eSJoern Engel func(elem, opaque, *key, index);
7295db53f3eSJoern Engel }
7305db53f3eSJoern Engel EXPORT_SYMBOL_GPL(visitor64);
7315db53f3eSJoern Engel
visitor128(void * elem,unsigned long opaque,unsigned long * __key,size_t index,void * __func)7325db53f3eSJoern Engel void visitor128(void *elem, unsigned long opaque, unsigned long *__key,
7335db53f3eSJoern Engel size_t index, void *__func)
7345db53f3eSJoern Engel {
7355db53f3eSJoern Engel visitor128_t func = __func;
7365db53f3eSJoern Engel u64 *key = (void *)__key;
7375db53f3eSJoern Engel
7385db53f3eSJoern Engel func(elem, opaque, key[0], key[1], index);
7395db53f3eSJoern Engel }
7405db53f3eSJoern Engel EXPORT_SYMBOL_GPL(visitor128);
7415db53f3eSJoern Engel
btree_visitor(struct btree_head * head,struct btree_geo * geo,unsigned long opaque,void (* func)(void * elem,unsigned long opaque,unsigned long * key,size_t index,void * func2),void * func2)7425db53f3eSJoern Engel size_t btree_visitor(struct btree_head *head, struct btree_geo *geo,
7435db53f3eSJoern Engel unsigned long opaque,
7445db53f3eSJoern Engel void (*func)(void *elem, unsigned long opaque,
7455db53f3eSJoern Engel unsigned long *key,
7465db53f3eSJoern Engel size_t index, void *func2),
7475db53f3eSJoern Engel void *func2)
7485db53f3eSJoern Engel {
7495db53f3eSJoern Engel size_t count = 0;
7505db53f3eSJoern Engel
7515db53f3eSJoern Engel if (!func2)
7525db53f3eSJoern Engel func = empty;
7535db53f3eSJoern Engel if (head->node)
7545db53f3eSJoern Engel count = __btree_for_each(head, geo, head->node, opaque, func,
7555db53f3eSJoern Engel func2, 0, head->height, 0);
7565db53f3eSJoern Engel return count;
7575db53f3eSJoern Engel }
7585db53f3eSJoern Engel EXPORT_SYMBOL_GPL(btree_visitor);
7595db53f3eSJoern Engel
btree_grim_visitor(struct btree_head * head,struct btree_geo * geo,unsigned long opaque,void (* func)(void * elem,unsigned long opaque,unsigned long * key,size_t index,void * func2),void * func2)7605db53f3eSJoern Engel size_t btree_grim_visitor(struct btree_head *head, struct btree_geo *geo,
7615db53f3eSJoern Engel unsigned long opaque,
7625db53f3eSJoern Engel void (*func)(void *elem, unsigned long opaque,
7635db53f3eSJoern Engel unsigned long *key,
7645db53f3eSJoern Engel size_t index, void *func2),
7655db53f3eSJoern Engel void *func2)
7665db53f3eSJoern Engel {
7675db53f3eSJoern Engel size_t count = 0;
7685db53f3eSJoern Engel
7695db53f3eSJoern Engel if (!func2)
7705db53f3eSJoern Engel func = empty;
7715db53f3eSJoern Engel if (head->node)
7725db53f3eSJoern Engel count = __btree_for_each(head, geo, head->node, opaque, func,
7735db53f3eSJoern Engel func2, 1, head->height, 0);
7745db53f3eSJoern Engel __btree_init(head);
7755db53f3eSJoern Engel return count;
7765db53f3eSJoern Engel }
7775db53f3eSJoern Engel EXPORT_SYMBOL_GPL(btree_grim_visitor);
7785db53f3eSJoern Engel
btree_module_init(void)7795db53f3eSJoern Engel static int __init btree_module_init(void)
7805db53f3eSJoern Engel {
7815db53f3eSJoern Engel btree_cachep = kmem_cache_create("btree_node", NODESIZE, 0,
7825db53f3eSJoern Engel SLAB_HWCACHE_ALIGN, NULL);
7835db53f3eSJoern Engel return 0;
7845db53f3eSJoern Engel }
7855db53f3eSJoern Engel
btree_module_exit(void)7865db53f3eSJoern Engel static void __exit btree_module_exit(void)
7875db53f3eSJoern Engel {
7885db53f3eSJoern Engel kmem_cache_destroy(btree_cachep);
7895db53f3eSJoern Engel }
7905db53f3eSJoern Engel
7915db53f3eSJoern Engel /* If core code starts using btree, initialization should happen even earlier */
7925db53f3eSJoern Engel module_init(btree_module_init);
7935db53f3eSJoern Engel module_exit(btree_module_exit);
7945db53f3eSJoern Engel
7955db53f3eSJoern Engel MODULE_AUTHOR("Joern Engel <joern@logfs.org>");
7965db53f3eSJoern Engel MODULE_AUTHOR("Johannes Berg <johannes@sipsolutions.net>");
797