Root/
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 |
244 |
Branches:
ben-wpan
ben-wpan-stefan
javiroman/ks7010
jz-2.6.34
jz-2.6.34-rc5
jz-2.6.34-rc6
jz-2.6.34-rc7
jz-2.6.35
jz-2.6.36
jz-2.6.37
jz-2.6.38
jz-2.6.39
jz-3.0
jz-3.1
jz-3.11
jz-3.12
jz-3.13
jz-3.15
jz-3.16
jz-3.18-dt
jz-3.2
jz-3.3
jz-3.4
jz-3.5
jz-3.6
jz-3.6-rc2-pwm
jz-3.9
jz-3.9-clk
jz-3.9-rc8
jz47xx
jz47xx-2.6.38
master
Tags:
od-2011-09-04
od-2011-09-18
v2.6.34-rc5
v2.6.34-rc6
v2.6.34-rc7
v3.9