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