Linux Kernel  3.7.1
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
btree.h
Go to the documentation of this file.
1 #ifndef BTREE_H
2 #define BTREE_H
3 
4 #include <linux/kernel.h>
5 #include <linux/mempool.h>
6 
34 struct btree_head {
35  unsigned long *node;
37  int height;
38 };
39 
40 /* btree geometry */
41 struct btree_geo;
42 
48 void *btree_alloc(gfp_t gfp_mask, void *pool_data);
49 
55 void btree_free(void *element, void *pool_data);
56 
66 void btree_init_mempool(struct btree_head *head, mempool_t *mempool);
67 
79 
88 void btree_destroy(struct btree_head *head);
89 
99 void *btree_lookup(struct btree_head *head, struct btree_geo *geo,
100  unsigned long *key);
101 
114 int __must_check btree_insert(struct btree_head *head, struct btree_geo *geo,
115  unsigned long *key, void *val, gfp_t gfp);
127 int btree_update(struct btree_head *head, struct btree_geo *geo,
128  unsigned long *key, void *val);
139 void *btree_remove(struct btree_head *head, struct btree_geo *geo,
140  unsigned long *key);
141 
157 int btree_merge(struct btree_head *target, struct btree_head *victim,
158  struct btree_geo *geo, gfp_t gfp);
159 
171 void *btree_last(struct btree_head *head, struct btree_geo *geo,
172  unsigned long *key);
173 
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