Commit | Line | Data |
---|---|---|
b2441318 | 1 | /* SPDX-License-Identifier: GPL-2.0 */ |
5db53f3e JE |
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 | |
7f317d34 | 13 | * is described at https://en.wikipedia.org/wiki/B-tree, we currently do not |
5db53f3e JE |
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 |