btree.h 6.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244
  1. /* SPDX-License-Identifier: GPL-2.0 */
  2. #ifndef BTREE_H
  3. #define BTREE_H
  4. #include <linux/kernel.h>
  5. #include <linux/mempool.h>
  6. /**
  7. * DOC: B+Tree basics
  8. *
  9. * A B+Tree is a data structure for looking up arbitrary (currently allowing
  10. * unsigned long, u32, u64 and 2 * u64) keys into pointers. The data structure
  11. * is described at https://en.wikipedia.org/wiki/B-tree, we currently do not
  12. * use binary search to find the key on lookups.
  13. *
  14. * Each B+Tree consists of a head, that contains bookkeeping information and
  15. * a variable number (starting with zero) nodes. Each node contains the keys
  16. * and pointers to sub-nodes, or, for leaf nodes, the keys and values for the
  17. * tree entries.
  18. *
  19. * Each node in this implementation has the following layout:
  20. * [key1, key2, ..., keyN] [val1, val2, ..., valN]
  21. *
  22. * Each key here is an array of unsigned longs, geo->no_longs in total. The
  23. * number of keys and values (N) is geo->no_pairs.
  24. */
  25. /**
  26. * struct btree_head - btree head
  27. *
  28. * @node: the first node in the tree
  29. * @mempool: mempool used for node allocations
  30. * @height: current of the tree
  31. */
  32. struct btree_head {
  33. unsigned long *node;
  34. mempool_t *mempool;
  35. int height;
  36. };
  37. /* btree geometry */
  38. struct btree_geo;
  39. /**
  40. * btree_alloc - allocate function for the mempool
  41. * @gfp_mask: gfp mask for the allocation
  42. * @pool_data: unused
  43. */
  44. void *btree_alloc(gfp_t gfp_mask, void *pool_data);
  45. /**
  46. * btree_free - free function for the mempool
  47. * @element: the element to free
  48. * @pool_data: unused
  49. */
  50. void btree_free(void *element, void *pool_data);
  51. /**
  52. * btree_init_mempool - initialise a btree with given mempool
  53. *
  54. * @head: the btree head to initialise
  55. * @mempool: the mempool to use
  56. *
  57. * When this function is used, there is no need to destroy
  58. * the mempool.
  59. */
  60. void btree_init_mempool(struct btree_head *head, mempool_t *mempool);
  61. /**
  62. * btree_init - initialise a btree
  63. *
  64. * @head: the btree head to initialise
  65. *
  66. * This function allocates the memory pool that the
  67. * btree needs. Returns zero or a negative error code
  68. * (-%ENOMEM) when memory allocation fails.
  69. *
  70. */
  71. int __must_check btree_init(struct btree_head *head);
  72. /**
  73. * btree_destroy - destroy mempool
  74. *
  75. * @head: the btree head to destroy
  76. *
  77. * This function destroys the internal memory pool, use only
  78. * when using btree_init(), not with btree_init_mempool().
  79. */
  80. void btree_destroy(struct btree_head *head);
  81. /**
  82. * btree_lookup - look up a key in the btree
  83. *
  84. * @head: the btree to look in
  85. * @geo: the btree geometry
  86. * @key: the key to look up
  87. *
  88. * This function returns the value for the given key, or %NULL.
  89. */
  90. void *btree_lookup(struct btree_head *head, struct btree_geo *geo,
  91. unsigned long *key);
  92. /**
  93. * btree_insert - insert an entry into the btree
  94. *
  95. * @head: the btree to add to
  96. * @geo: the btree geometry
  97. * @key: the key to add (must not already be present)
  98. * @val: the value to add (must not be %NULL)
  99. * @gfp: allocation flags for node allocations
  100. *
  101. * This function returns 0 if the item could be added, or an
  102. * error code if it failed (may fail due to memory pressure).
  103. */
  104. int __must_check btree_insert(struct btree_head *head, struct btree_geo *geo,
  105. unsigned long *key, void *val, gfp_t gfp);
  106. /**
  107. * btree_update - update an entry in the btree
  108. *
  109. * @head: the btree to update
  110. * @geo: the btree geometry
  111. * @key: the key to update
  112. * @val: the value to change it to (must not be %NULL)
  113. *
  114. * This function returns 0 if the update was successful, or
  115. * -%ENOENT if the key could not be found.
  116. */
  117. int btree_update(struct btree_head *head, struct btree_geo *geo,
  118. unsigned long *key, void *val);
  119. /**
  120. * btree_remove - remove an entry from the btree
  121. *
  122. * @head: the btree to update
  123. * @geo: the btree geometry
  124. * @key: the key to remove
  125. *
  126. * This function returns the removed entry, or %NULL if the key
  127. * could not be found.
  128. */
  129. void *btree_remove(struct btree_head *head, struct btree_geo *geo,
  130. unsigned long *key);
  131. /**
  132. * btree_merge - merge two btrees
  133. *
  134. * @target: the tree that gets all the entries
  135. * @victim: the tree that gets merged into @target
  136. * @geo: the btree geometry
  137. * @gfp: allocation flags
  138. *
  139. * The two trees @target and @victim may not contain the same keys,
  140. * that is a bug and triggers a BUG(). This function returns zero
  141. * if the trees were merged successfully, and may return a failure
  142. * when memory allocation fails, in which case both trees might have
  143. * been partially merged, i.e. some entries have been moved from
  144. * @victim to @target.
  145. */
  146. int btree_merge(struct btree_head *target, struct btree_head *victim,
  147. struct btree_geo *geo, gfp_t gfp);
  148. /**
  149. * btree_last - get last entry in btree
  150. *
  151. * @head: btree head
  152. * @geo: btree geometry
  153. * @key: last key
  154. *
  155. * Returns the last entry in the btree, and sets @key to the key
  156. * of that entry; returns NULL if the tree is empty, in that case
  157. * key is not changed.
  158. */
  159. void *btree_last(struct btree_head *head, struct btree_geo *geo,
  160. unsigned long *key);
  161. /**
  162. * btree_get_prev - get previous entry
  163. *
  164. * @head: btree head
  165. * @geo: btree geometry
  166. * @key: pointer to key
  167. *
  168. * The function returns the next item right before the value pointed to by
  169. * @key, and updates @key with its key, or returns %NULL when there is no
  170. * entry with a key smaller than the given key.
  171. */
  172. void *btree_get_prev(struct btree_head *head, struct btree_geo *geo,
  173. unsigned long *key);
  174. /* internal use, use btree_visitor{l,32,64,128} */
  175. size_t btree_visitor(struct btree_head *head, struct btree_geo *geo,
  176. unsigned long opaque,
  177. void (*func)(void *elem, unsigned long opaque,
  178. unsigned long *key, size_t index,
  179. void *func2),
  180. void *func2);
  181. /* internal use, use btree_grim_visitor{l,32,64,128} */
  182. size_t btree_grim_visitor(struct btree_head *head, struct btree_geo *geo,
  183. unsigned long opaque,
  184. void (*func)(void *elem, unsigned long opaque,
  185. unsigned long *key,
  186. size_t index, void *func2),
  187. void *func2);
  188. #include <linux/btree-128.h>
  189. extern struct btree_geo btree_geo32;
  190. #define BTREE_TYPE_SUFFIX l
  191. #define BTREE_TYPE_BITS BITS_PER_LONG
  192. #define BTREE_TYPE_GEO &btree_geo32
  193. #define BTREE_KEYTYPE unsigned long
  194. #include <linux/btree-type.h>
  195. #define btree_for_each_safel(head, key, val) \
  196. for (val = btree_lastl(head, &key); \
  197. val; \
  198. val = btree_get_prevl(head, &key))
  199. #define BTREE_TYPE_SUFFIX 32
  200. #define BTREE_TYPE_BITS 32
  201. #define BTREE_TYPE_GEO &btree_geo32
  202. #define BTREE_KEYTYPE u32
  203. #include <linux/btree-type.h>
  204. #define btree_for_each_safe32(head, key, val) \
  205. for (val = btree_last32(head, &key); \
  206. val; \
  207. val = btree_get_prev32(head, &key))
  208. extern struct btree_geo btree_geo64;
  209. #define BTREE_TYPE_SUFFIX 64
  210. #define BTREE_TYPE_BITS 64
  211. #define BTREE_TYPE_GEO &btree_geo64
  212. #define BTREE_KEYTYPE u64
  213. #include <linux/btree-type.h>
  214. #define btree_for_each_safe64(head, key, val) \
  215. for (val = btree_last64(head, &key); \
  216. val; \
  217. val = btree_get_prev64(head, &key))
  218. #endif