include/linux/btree.h

1 /* SPDX-License-Identifier: GPL-2.0 */
11  * A B+Tree is a data structure for looking up arbitrary (currently allowing
13  * is described at https://en.wikipedia.org/wiki/B-tree, we currently do not
14  * use binary search to find the key on lookups.
18  * and pointers to sub-nodes, or, for leaf nodes, the keys and values for the
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.
29  * struct btree_head - btree head
45  * btree_alloc - allocate function for the mempool
52  * btree_free - free function for the mempool
59  * btree_init_mempool - initialise a btree with given mempool
70  * btree_init - initialise a btree
76  * (-%ENOMEM) when memory allocation fails.
82  * btree_destroy - destroy mempool
92  * btree_lookup - look up a key in the btree
96  * @key: the key to look up
98  * This function returns the value for the given key, or %NULL.
101 		   unsigned long *key);
104  * btree_insert - insert an entry into the btree
108  * @key: the key to add (must not already be present)
116 			      unsigned long *key, void *val, gfp_t gfp);
118  * btree_update - update an entry in the btree
122  * @key: the key to update
126  * -%ENOENT if the key could not be found.
129 		 unsigned long *key, void *val);
131  * btree_remove - remove an entry from the btree
135  * @key: the key to remove
137  * This function returns the removed entry, or %NULL if the key
141 		   unsigned long *key);
144  * btree_merge - merge two btrees
162  * btree_last - get last entry in btree
166  * @key: last key
168  * Returns the last entry in the btree, and sets @key to the key
170  * key is not changed.
173 		 unsigned long *key);
176  * btree_get_prev - get previous entry
180  * @key: pointer to key
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.
187 		     unsigned long *key);
194 				  unsigned long *key, size_t index,
202 				       unsigned long *key,
207 #include <linux/btree-128.h>
214 #include <linux/btree-type.h>
216 #define btree_for_each_safel(head, key, val)	\  argument
217 	for (val = btree_lastl(head, &key);	\
219 	     val = btree_get_prevl(head, &key))
225 #include <linux/btree-type.h>
227 #define btree_for_each_safe32(head, key, val)	\  argument
228 	for (val = btree_last32(head, &key);	\
230 	     val = btree_get_prev32(head, &key))
237 #include <linux/btree-type.h>
239 #define btree_for_each_safe64(head, key, val)	\  argument
240 	for (val = btree_last64(head, &key);	\
242 	     val = btree_get_prev64(head, &key))