btree.c 19 KB

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