GNU Linux-libre 4.19.211-gnu1
[releases.git] / lib / btree.c
1 /*
2  * lib/btree.c  - Simple In-memory B+Tree
3  *
4  * As should be obvious for Linux kernel code, license is GPLv2
5  *
6  * Copyright (c) 2007-2008 Joern Engel <joern@purestorage.com>
7  * Bits and pieces stolen from Peter Zijlstra's code, which is
8  * Copyright 2007, Red Hat Inc. Peter Zijlstra
9  * GPLv2
10  *
11  * see http://programming.kicks-ass.net/kernel-patches/vma_lookup/btree.patch
12  *
13  * A relatively simple B+Tree implementation.  I have written it as a learning
14  * exercise to understand how B+Trees work.  Turned out to be useful as well.
15  *
16  * B+Trees can be used similar to Linux radix trees (which don't have anything
17  * in common with textbook radix trees, beware).  Prerequisite for them working
18  * well is that access to a random tree node is much faster than a large number
19  * of operations within each node.
20  *
21  * Disks have fulfilled the prerequisite for a long time.  More recently DRAM
22  * has gained similar properties, as memory access times, when measured in cpu
23  * cycles, have increased.  Cacheline sizes have increased as well, which also
24  * helps B+Trees.
25  *
26  * Compared to radix trees, B+Trees are more efficient when dealing with a
27  * sparsely populated address space.  Between 25% and 50% of the memory is
28  * occupied with valid pointers.  When densely populated, radix trees contain
29  * ~98% pointers - hard to beat.  Very sparse radix trees contain only ~2%
30  * pointers.
31  *
32  * This particular implementation stores pointers identified by a long value.
33  * Storing NULL pointers is illegal, lookup will return NULL when no entry
34  * was found.
35  *
36  * A tricks was used that is not commonly found in textbooks.  The lowest
37  * values are to the right, not to the left.  All used slots within a node
38  * are on the left, all unused slots contain NUL values.  Most operations
39  * simply loop once over all slots and terminate on the first NUL.
40  */
41
42 #include <linux/btree.h>
43 #include <linux/cache.h>
44 #include <linux/kernel.h>
45 #include <linux/slab.h>
46 #include <linux/module.h>
47
48 #define MAX(a, b) ((a) > (b) ? (a) : (b))
49 #define NODESIZE MAX(L1_CACHE_BYTES, 128)
50
51 struct btree_geo {
52         int keylen;
53         int no_pairs;
54         int no_longs;
55 };
56
57 struct btree_geo btree_geo32 = {
58         .keylen = 1,
59         .no_pairs = NODESIZE / sizeof(long) / 2,
60         .no_longs = NODESIZE / sizeof(long) / 2,
61 };
62 EXPORT_SYMBOL_GPL(btree_geo32);
63
64 #define LONG_PER_U64 (64 / BITS_PER_LONG)
65 struct btree_geo btree_geo64 = {
66         .keylen = LONG_PER_U64,
67         .no_pairs = NODESIZE / sizeof(long) / (1 + LONG_PER_U64),
68         .no_longs = LONG_PER_U64 * (NODESIZE / sizeof(long) / (1 + LONG_PER_U64)),
69 };
70 EXPORT_SYMBOL_GPL(btree_geo64);
71
72 struct btree_geo btree_geo128 = {
73         .keylen = 2 * LONG_PER_U64,
74         .no_pairs = NODESIZE / sizeof(long) / (1 + 2 * LONG_PER_U64),
75         .no_longs = 2 * LONG_PER_U64 * (NODESIZE / sizeof(long) / (1 + 2 * LONG_PER_U64)),
76 };
77 EXPORT_SYMBOL_GPL(btree_geo128);
78
79 #define MAX_KEYLEN      (2 * LONG_PER_U64)
80
81 static struct kmem_cache *btree_cachep;
82
83 void *btree_alloc(gfp_t gfp_mask, void *pool_data)
84 {
85         return kmem_cache_alloc(btree_cachep, gfp_mask);
86 }
87 EXPORT_SYMBOL_GPL(btree_alloc);
88
89 void btree_free(void *element, void *pool_data)
90 {
91         kmem_cache_free(btree_cachep, element);
92 }
93 EXPORT_SYMBOL_GPL(btree_free);
94
95 static unsigned long *btree_node_alloc(struct btree_head *head, gfp_t gfp)
96 {
97         unsigned long *node;
98
99         node = mempool_alloc(head->mempool, gfp);
100         if (likely(node))
101                 memset(node, 0, NODESIZE);
102         return node;
103 }
104
105 static int longcmp(const unsigned long *l1, const unsigned long *l2, size_t n)
106 {
107         size_t i;
108
109         for (i = 0; i < n; i++) {
110                 if (l1[i] < l2[i])
111                         return -1;
112                 if (l1[i] > l2[i])
113                         return 1;
114         }
115         return 0;
116 }
117
118 static unsigned long *longcpy(unsigned long *dest, const unsigned long *src,
119                 size_t n)
120 {
121         size_t i;
122
123         for (i = 0; i < n; i++)
124                 dest[i] = src[i];
125         return dest;
126 }
127
128 static unsigned long *longset(unsigned long *s, unsigned long c, size_t n)
129 {
130         size_t i;
131
132         for (i = 0; i < n; i++)
133                 s[i] = c;
134         return s;
135 }
136
137 static void dec_key(struct btree_geo *geo, unsigned long *key)
138 {
139         unsigned long val;
140         int i;
141
142         for (i = geo->keylen - 1; i >= 0; i--) {
143                 val = key[i];
144                 key[i] = val - 1;
145                 if (val)
146                         break;
147         }
148 }
149
150 static unsigned long *bkey(struct btree_geo *geo, unsigned long *node, int n)
151 {
152         return &node[n * geo->keylen];
153 }
154
155 static void *bval(struct btree_geo *geo, unsigned long *node, int n)
156 {
157         return (void *)node[geo->no_longs + n];
158 }
159
160 static void setkey(struct btree_geo *geo, unsigned long *node, int n,
161                    unsigned long *key)
162 {
163         longcpy(bkey(geo, node, n), key, geo->keylen);
164 }
165
166 static void setval(struct btree_geo *geo, unsigned long *node, int n,
167                    void *val)
168 {
169         node[geo->no_longs + n] = (unsigned long) val;
170 }
171
172 static void clearpair(struct btree_geo *geo, unsigned long *node, int n)
173 {
174         longset(bkey(geo, node, n), 0, geo->keylen);
175         node[geo->no_longs + n] = 0;
176 }
177
178 static inline void __btree_init(struct btree_head *head)
179 {
180         head->node = NULL;
181         head->height = 0;
182 }
183
184 void btree_init_mempool(struct btree_head *head, mempool_t *mempool)
185 {
186         __btree_init(head);
187         head->mempool = mempool;
188 }
189 EXPORT_SYMBOL_GPL(btree_init_mempool);
190
191 int btree_init(struct btree_head *head)
192 {
193         __btree_init(head);
194         head->mempool = mempool_create(0, btree_alloc, btree_free, NULL);
195         if (!head->mempool)
196                 return -ENOMEM;
197         return 0;
198 }
199 EXPORT_SYMBOL_GPL(btree_init);
200
201 void btree_destroy(struct btree_head *head)
202 {
203         mempool_free(head->node, head->mempool);
204         mempool_destroy(head->mempool);
205         head->mempool = NULL;
206 }
207 EXPORT_SYMBOL_GPL(btree_destroy);
208
209 void *btree_last(struct btree_head *head, struct btree_geo *geo,
210                  unsigned long *key)
211 {
212         int height = head->height;
213         unsigned long *node = head->node;
214
215         if (height == 0)
216                 return NULL;
217
218         for ( ; height > 1; height--)
219                 node = bval(geo, node, 0);
220
221         longcpy(key, bkey(geo, node, 0), geo->keylen);
222         return bval(geo, node, 0);
223 }
224 EXPORT_SYMBOL_GPL(btree_last);
225
226 static int keycmp(struct btree_geo *geo, unsigned long *node, int pos,
227                   unsigned long *key)
228 {
229         return longcmp(bkey(geo, node, pos), key, geo->keylen);
230 }
231
232 static int keyzero(struct btree_geo *geo, unsigned long *key)
233 {
234         int i;
235
236         for (i = 0; i < geo->keylen; i++)
237                 if (key[i])
238                         return 0;
239
240         return 1;
241 }
242
243 void *btree_lookup(struct btree_head *head, struct btree_geo *geo,
244                 unsigned long *key)
245 {
246         int i, height = head->height;
247         unsigned long *node = head->node;
248
249         if (height == 0)
250                 return NULL;
251
252         for ( ; height > 1; height--) {
253                 for (i = 0; i < geo->no_pairs; i++)
254                         if (keycmp(geo, node, i, key) <= 0)
255                                 break;
256                 if (i == geo->no_pairs)
257                         return NULL;
258                 node = bval(geo, node, i);
259                 if (!node)
260                         return NULL;
261         }
262
263         if (!node)
264                 return NULL;
265
266         for (i = 0; i < geo->no_pairs; i++)
267                 if (keycmp(geo, node, i, key) == 0)
268                         return bval(geo, node, i);
269         return NULL;
270 }
271 EXPORT_SYMBOL_GPL(btree_lookup);
272
273 int btree_update(struct btree_head *head, struct btree_geo *geo,
274                  unsigned long *key, void *val)
275 {
276         int i, height = head->height;
277         unsigned long *node = head->node;
278
279         if (height == 0)
280                 return -ENOENT;
281
282         for ( ; height > 1; height--) {
283                 for (i = 0; i < geo->no_pairs; i++)
284                         if (keycmp(geo, node, i, key) <= 0)
285                                 break;
286                 if (i == geo->no_pairs)
287                         return -ENOENT;
288                 node = bval(geo, node, i);
289                 if (!node)
290                         return -ENOENT;
291         }
292
293         if (!node)
294                 return -ENOENT;
295
296         for (i = 0; i < geo->no_pairs; i++)
297                 if (keycmp(geo, node, i, key) == 0) {
298                         setval(geo, node, i, val);
299                         return 0;
300                 }
301         return -ENOENT;
302 }
303 EXPORT_SYMBOL_GPL(btree_update);
304
305 /*
306  * Usually this function is quite similar to normal lookup.  But the key of
307  * a parent node may be smaller than the smallest key of all its siblings.
308  * In such a case we cannot just return NULL, as we have only proven that no
309  * key smaller than __key, but larger than this parent key exists.
310  * So we set __key to the parent key and retry.  We have to use the smallest
311  * such parent key, which is the last parent key we encountered.
312  */
313 void *btree_get_prev(struct btree_head *head, struct btree_geo *geo,
314                      unsigned long *__key)
315 {
316         int i, height;
317         unsigned long *node, *oldnode;
318         unsigned long *retry_key = NULL, key[MAX_KEYLEN];
319
320         if (keyzero(geo, __key))
321                 return NULL;
322
323         if (head->height == 0)
324                 return NULL;
325         longcpy(key, __key, geo->keylen);
326 retry:
327         dec_key(geo, key);
328
329         node = head->node;
330         for (height = head->height ; height > 1; height--) {
331                 for (i = 0; i < geo->no_pairs; i++)
332                         if (keycmp(geo, node, i, key) <= 0)
333                                 break;
334                 if (i == geo->no_pairs)
335                         goto miss;
336                 oldnode = node;
337                 node = bval(geo, node, i);
338                 if (!node)
339                         goto miss;
340                 retry_key = bkey(geo, oldnode, i);
341         }
342
343         if (!node)
344                 goto miss;
345
346         for (i = 0; i < geo->no_pairs; i++) {
347                 if (keycmp(geo, node, i, key) <= 0) {
348                         if (bval(geo, node, i)) {
349                                 longcpy(__key, bkey(geo, node, i), geo->keylen);
350                                 return bval(geo, node, i);
351                         } else
352                                 goto miss;
353                 }
354         }
355 miss:
356         if (retry_key) {
357                 longcpy(key, retry_key, geo->keylen);
358                 retry_key = NULL;
359                 goto retry;
360         }
361         return NULL;
362 }
363 EXPORT_SYMBOL_GPL(btree_get_prev);
364
365 static int getpos(struct btree_geo *geo, unsigned long *node,
366                 unsigned long *key)
367 {
368         int i;
369
370         for (i = 0; i < geo->no_pairs; i++) {
371                 if (keycmp(geo, node, i, key) <= 0)
372                         break;
373         }
374         return i;
375 }
376
377 static int getfill(struct btree_geo *geo, unsigned long *node, int start)
378 {
379         int i;
380
381         for (i = start; i < geo->no_pairs; i++)
382                 if (!bval(geo, node, i))
383                         break;
384         return i;
385 }
386
387 /*
388  * locate the correct leaf node in the btree
389  */
390 static unsigned long *find_level(struct btree_head *head, struct btree_geo *geo,
391                 unsigned long *key, int level)
392 {
393         unsigned long *node = head->node;
394         int i, height;
395
396         for (height = head->height; height > level; height--) {
397                 for (i = 0; i < geo->no_pairs; i++)
398                         if (keycmp(geo, node, i, key) <= 0)
399                                 break;
400
401                 if ((i == geo->no_pairs) || !bval(geo, node, i)) {
402                         /* right-most key is too large, update it */
403                         /* FIXME: If the right-most key on higher levels is
404                          * always zero, this wouldn't be necessary. */
405                         i--;
406                         setkey(geo, node, i, key);
407                 }
408                 BUG_ON(i < 0);
409                 node = bval(geo, node, i);
410         }
411         BUG_ON(!node);
412         return node;
413 }
414
415 static int btree_grow(struct btree_head *head, struct btree_geo *geo,
416                       gfp_t gfp)
417 {
418         unsigned long *node;
419         int fill;
420
421         node = btree_node_alloc(head, gfp);
422         if (!node)
423                 return -ENOMEM;
424         if (head->node) {
425                 fill = getfill(geo, head->node, 0);
426                 setkey(geo, node, 0, bkey(geo, head->node, fill - 1));
427                 setval(geo, node, 0, head->node);
428         }
429         head->node = node;
430         head->height++;
431         return 0;
432 }
433
434 static void btree_shrink(struct btree_head *head, struct btree_geo *geo)
435 {
436         unsigned long *node;
437         int fill;
438
439         if (head->height <= 1)
440                 return;
441
442         node = head->node;
443         fill = getfill(geo, node, 0);
444         BUG_ON(fill > 1);
445         head->node = bval(geo, node, 0);
446         head->height--;
447         mempool_free(node, head->mempool);
448 }
449
450 static int btree_insert_level(struct btree_head *head, struct btree_geo *geo,
451                               unsigned long *key, void *val, int level,
452                               gfp_t gfp)
453 {
454         unsigned long *node;
455         int i, pos, fill, err;
456
457         BUG_ON(!val);
458         if (head->height < level) {
459                 err = btree_grow(head, geo, gfp);
460                 if (err)
461                         return err;
462         }
463
464 retry:
465         node = find_level(head, geo, key, level);
466         pos = getpos(geo, node, key);
467         fill = getfill(geo, node, pos);
468         /* two identical keys are not allowed */
469         BUG_ON(pos < fill && keycmp(geo, node, pos, key) == 0);
470
471         if (fill == geo->no_pairs) {
472                 /* need to split node */
473                 unsigned long *new;
474
475                 new = btree_node_alloc(head, gfp);
476                 if (!new)
477                         return -ENOMEM;
478                 err = btree_insert_level(head, geo,
479                                 bkey(geo, node, fill / 2 - 1),
480                                 new, level + 1, gfp);
481                 if (err) {
482                         mempool_free(new, head->mempool);
483                         return err;
484                 }
485                 for (i = 0; i < fill / 2; i++) {
486                         setkey(geo, new, i, bkey(geo, node, i));
487                         setval(geo, new, i, bval(geo, node, i));
488                         setkey(geo, node, i, bkey(geo, node, i + fill / 2));
489                         setval(geo, node, i, bval(geo, node, i + fill / 2));
490                         clearpair(geo, node, i + fill / 2);
491                 }
492                 if (fill & 1) {
493                         setkey(geo, node, i, bkey(geo, node, fill - 1));
494                         setval(geo, node, i, bval(geo, node, fill - 1));
495                         clearpair(geo, node, fill - 1);
496                 }
497                 goto retry;
498         }
499         BUG_ON(fill >= geo->no_pairs);
500
501         /* shift and insert */
502         for (i = fill; i > pos; i--) {
503                 setkey(geo, node, i, bkey(geo, node, i - 1));
504                 setval(geo, node, i, bval(geo, node, i - 1));
505         }
506         setkey(geo, node, pos, key);
507         setval(geo, node, pos, val);
508
509         return 0;
510 }
511
512 int btree_insert(struct btree_head *head, struct btree_geo *geo,
513                 unsigned long *key, void *val, gfp_t gfp)
514 {
515         BUG_ON(!val);
516         return btree_insert_level(head, geo, key, val, 1, gfp);
517 }
518 EXPORT_SYMBOL_GPL(btree_insert);
519
520 static void *btree_remove_level(struct btree_head *head, struct btree_geo *geo,
521                 unsigned long *key, int level);
522 static void merge(struct btree_head *head, struct btree_geo *geo, int level,
523                 unsigned long *left, int lfill,
524                 unsigned long *right, int rfill,
525                 unsigned long *parent, int lpos)
526 {
527         int i;
528
529         for (i = 0; i < rfill; i++) {
530                 /* Move all keys to the left */
531                 setkey(geo, left, lfill + i, bkey(geo, right, i));
532                 setval(geo, left, lfill + i, bval(geo, right, i));
533         }
534         /* Exchange left and right child in parent */
535         setval(geo, parent, lpos, right);
536         setval(geo, parent, lpos + 1, left);
537         /* Remove left (formerly right) child from parent */
538         btree_remove_level(head, geo, bkey(geo, parent, lpos), level + 1);
539         mempool_free(right, head->mempool);
540 }
541
542 static void rebalance(struct btree_head *head, struct btree_geo *geo,
543                 unsigned long *key, int level, unsigned long *child, int fill)
544 {
545         unsigned long *parent, *left = NULL, *right = NULL;
546         int i, no_left, no_right;
547
548         if (fill == 0) {
549                 /* Because we don't steal entries from a neighbour, this case
550                  * can happen.  Parent node contains a single child, this
551                  * node, so merging with a sibling never happens.
552                  */
553                 btree_remove_level(head, geo, key, level + 1);
554                 mempool_free(child, head->mempool);
555                 return;
556         }
557
558         parent = find_level(head, geo, key, level + 1);
559         i = getpos(geo, parent, key);
560         BUG_ON(bval(geo, parent, i) != child);
561
562         if (i > 0) {
563                 left = bval(geo, parent, i - 1);
564                 no_left = getfill(geo, left, 0);
565                 if (fill + no_left <= geo->no_pairs) {
566                         merge(head, geo, level,
567                                         left, no_left,
568                                         child, fill,
569                                         parent, i - 1);
570                         return;
571                 }
572         }
573         if (i + 1 < getfill(geo, parent, i)) {
574                 right = bval(geo, parent, i + 1);
575                 no_right = getfill(geo, right, 0);
576                 if (fill + no_right <= geo->no_pairs) {
577                         merge(head, geo, level,
578                                         child, fill,
579                                         right, no_right,
580                                         parent, i);
581                         return;
582                 }
583         }
584         /*
585          * We could also try to steal one entry from the left or right
586          * neighbor.  By not doing so we changed the invariant from
587          * "all nodes are at least half full" to "no two neighboring
588          * nodes can be merged".  Which means that the average fill of
589          * all nodes is still half or better.
590          */
591 }
592
593 static void *btree_remove_level(struct btree_head *head, struct btree_geo *geo,
594                 unsigned long *key, int level)
595 {
596         unsigned long *node;
597         int i, pos, fill;
598         void *ret;
599
600         if (level > head->height) {
601                 /* we recursed all the way up */
602                 head->height = 0;
603                 head->node = NULL;
604                 return NULL;
605         }
606
607         node = find_level(head, geo, key, level);
608         pos = getpos(geo, node, key);
609         fill = getfill(geo, node, pos);
610         if ((level == 1) && (keycmp(geo, node, pos, key) != 0))
611                 return NULL;
612         ret = bval(geo, node, pos);
613
614         /* remove and shift */
615         for (i = pos; i < fill - 1; i++) {
616                 setkey(geo, node, i, bkey(geo, node, i + 1));
617                 setval(geo, node, i, bval(geo, node, i + 1));
618         }
619         clearpair(geo, node, fill - 1);
620
621         if (fill - 1 < geo->no_pairs / 2) {
622                 if (level < head->height)
623                         rebalance(head, geo, key, level, node, fill - 1);
624                 else if (fill - 1 == 1)
625                         btree_shrink(head, geo);
626         }
627
628         return ret;
629 }
630
631 void *btree_remove(struct btree_head *head, struct btree_geo *geo,
632                 unsigned long *key)
633 {
634         if (head->height == 0)
635                 return NULL;
636
637         return btree_remove_level(head, geo, key, 1);
638 }
639 EXPORT_SYMBOL_GPL(btree_remove);
640
641 int btree_merge(struct btree_head *target, struct btree_head *victim,
642                 struct btree_geo *geo, gfp_t gfp)
643 {
644         unsigned long key[MAX_KEYLEN];
645         unsigned long dup[MAX_KEYLEN];
646         void *val;
647         int err;
648
649         BUG_ON(target == victim);
650
651         if (!(target->node)) {
652                 /* target is empty, just copy fields over */
653                 target->node = victim->node;
654                 target->height = victim->height;
655                 __btree_init(victim);
656                 return 0;
657         }
658
659         /* TODO: This needs some optimizations.  Currently we do three tree
660          * walks to remove a single object from the victim.
661          */
662         for (;;) {
663                 if (!btree_last(victim, geo, key))
664                         break;
665                 val = btree_lookup(victim, geo, key);
666                 err = btree_insert(target, geo, key, val, gfp);
667                 if (err)
668                         return err;
669                 /* We must make a copy of the key, as the original will get
670                  * mangled inside btree_remove. */
671                 longcpy(dup, key, geo->keylen);
672                 btree_remove(victim, geo, dup);
673         }
674         return 0;
675 }
676 EXPORT_SYMBOL_GPL(btree_merge);
677
678 static size_t __btree_for_each(struct btree_head *head, struct btree_geo *geo,
679                                unsigned long *node, unsigned long opaque,
680                                void (*func)(void *elem, unsigned long opaque,
681                                             unsigned long *key, size_t index,
682                                             void *func2),
683                                void *func2, int reap, int height, size_t count)
684 {
685         int i;
686         unsigned long *child;
687
688         for (i = 0; i < geo->no_pairs; i++) {
689                 child = bval(geo, node, i);
690                 if (!child)
691                         break;
692                 if (height > 1)
693                         count = __btree_for_each(head, geo, child, opaque,
694                                         func, func2, reap, height - 1, count);
695                 else
696                         func(child, opaque, bkey(geo, node, i), count++,
697                                         func2);
698         }
699         if (reap)
700                 mempool_free(node, head->mempool);
701         return count;
702 }
703
704 static void empty(void *elem, unsigned long opaque, unsigned long *key,
705                   size_t index, void *func2)
706 {
707 }
708
709 void visitorl(void *elem, unsigned long opaque, unsigned long *key,
710               size_t index, void *__func)
711 {
712         visitorl_t func = __func;
713
714         func(elem, opaque, *key, index);
715 }
716 EXPORT_SYMBOL_GPL(visitorl);
717
718 void visitor32(void *elem, unsigned long opaque, unsigned long *__key,
719                size_t index, void *__func)
720 {
721         visitor32_t func = __func;
722         u32 *key = (void *)__key;
723
724         func(elem, opaque, *key, index);
725 }
726 EXPORT_SYMBOL_GPL(visitor32);
727
728 void visitor64(void *elem, unsigned long opaque, unsigned long *__key,
729                size_t index, void *__func)
730 {
731         visitor64_t func = __func;
732         u64 *key = (void *)__key;
733
734         func(elem, opaque, *key, index);
735 }
736 EXPORT_SYMBOL_GPL(visitor64);
737
738 void visitor128(void *elem, unsigned long opaque, unsigned long *__key,
739                 size_t index, void *__func)
740 {
741         visitor128_t func = __func;
742         u64 *key = (void *)__key;
743
744         func(elem, opaque, key[0], key[1], index);
745 }
746 EXPORT_SYMBOL_GPL(visitor128);
747
748 size_t btree_visitor(struct btree_head *head, struct btree_geo *geo,
749                      unsigned long opaque,
750                      void (*func)(void *elem, unsigned long opaque,
751                                   unsigned long *key,
752                                   size_t index, void *func2),
753                      void *func2)
754 {
755         size_t count = 0;
756
757         if (!func2)
758                 func = empty;
759         if (head->node)
760                 count = __btree_for_each(head, geo, head->node, opaque, func,
761                                 func2, 0, head->height, 0);
762         return count;
763 }
764 EXPORT_SYMBOL_GPL(btree_visitor);
765
766 size_t btree_grim_visitor(struct btree_head *head, struct btree_geo *geo,
767                           unsigned long opaque,
768                           void (*func)(void *elem, unsigned long opaque,
769                                        unsigned long *key,
770                                        size_t index, void *func2),
771                           void *func2)
772 {
773         size_t count = 0;
774
775         if (!func2)
776                 func = empty;
777         if (head->node)
778                 count = __btree_for_each(head, geo, head->node, opaque, func,
779                                 func2, 1, head->height, 0);
780         __btree_init(head);
781         return count;
782 }
783 EXPORT_SYMBOL_GPL(btree_grim_visitor);
784
785 static int __init btree_module_init(void)
786 {
787         btree_cachep = kmem_cache_create("btree_node", NODESIZE, 0,
788                         SLAB_HWCACHE_ALIGN, NULL);
789         return 0;
790 }
791
792 static void __exit btree_module_exit(void)
793 {
794         kmem_cache_destroy(btree_cachep);
795 }
796
797 /* If core code starts using btree, initialization should happen even earlier */
798 module_init(btree_module_init);
799 module_exit(btree_module_exit);
800
801 MODULE_AUTHOR("Joern Engel <joern@logfs.org>");
802 MODULE_AUTHOR("Johannes Berg <johannes@sipsolutions.net>");
803 MODULE_LICENSE("GPL");