~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/include/linux/btree.h

Version: ~ [ linux-4.20-rc6 ] ~ [ linux-4.19.8 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.87 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.144 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.166 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.128 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.61 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-3.9.11 ] ~ [ linux-3.8.13 ] ~ [ linux-3.7.10 ] ~ [ linux-3.6.11 ] ~ [ linux-3.5.7 ] ~ [ linux-3.4.113 ] ~ [ linux-3.3.8 ] ~ [ linux-3.2.102 ] ~ [ linux-3.1.10 ] ~ [ linux-3.0.101 ] ~ [ linux-2.6.39.4 ] ~ [ linux-2.6.38.8 ] ~ [ linux-2.6.37.6 ] ~ [ linux-2.6.36.4 ] ~ [ linux-2.6.35.14 ] ~ [ linux-2.6.34.15 ] ~ [ linux-2.6.33.20 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.31.14 ] ~ [ linux-2.6.30.10 ] ~ [ linux-2.6.29.6 ] ~ [ linux-2.6.28.10 ] ~ [ linux-2.6.27.62 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  1 /* SPDX-License-Identifier: GPL-2.0 */
  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
 13  * is described at http://en.wikipedia.org/wiki/B-tree, we currently do not
 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
245 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp