]> git.kernelconcepts.de Git - karo-tx-linux.git/blob - include/linux/btree.h
Merge commit 'v2.6.36' into kbuild/misc
[karo-tx-linux.git] / include / linux / btree.h
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  */
34 struct btree_head {
35         unsigned long *node;
36         mempool_t *mempool;
37         int height;
38 };
39
40 /* btree geometry */
41 struct 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  */
48 void *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  */
55 void 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  */
66 void 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  */
78 int __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  */
88 void 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  */
99 void *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  */
114 int __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  */
127 int 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  */
139 void *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  */
157 int 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  */
171 void *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  */
185 void *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} */
190 size_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} */
198 size_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
208 extern 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
231 extern 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