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