~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/lib/btree.c

Version: ~ [ linux-4.19-rc4 ] ~ [ linux-4.18.8 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.70 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.127 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.156 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.122 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.57 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-3.9.11 ] ~ [ linux-3.8.13 ] ~ [ linux-3.7.10 ] ~ [ linux-3.6.11 ] ~ [ linux-3.5.7 ] ~ [ linux-3.4.113 ] ~ [ linux-3.3.8 ] ~ [ linux-3.2.102 ] ~ [ linux-3.1.10 ] ~ [ linux-3.0.101 ] ~ [ linux-2.6.39.4 ] ~ [ linux-2.6.38.8 ] ~ [ linux-2.6.37.6 ] ~ [ linux-2.6.36.4 ] ~ [ linux-2.6.35.14 ] ~ [ linux-2.6.34.15 ] ~ [ linux-2.6.33.20 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.31.14 ] ~ [ linux-2.6.30.10 ] ~ [ linux-2.6.29.6 ] ~ [ linux-2.6.28.10 ] ~ [ linux-2.6.27.62 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  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");
804 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp