OSCL-LXR |
|
|
|
|||
0001 /* SPDX-License-Identifier: GPL-2.0 */ 0002 #ifndef BTREE_H 0003 #define BTREE_H 0004 0005 #include <linux/kernel.h> 0006 #include <linux/mempool.h> 0007 0008 /** 0009 * DOC: B+Tree basics 0010 * 0011 * A B+Tree is a data structure for looking up arbitrary (currently allowing 0012 * unsigned long, u32, u64 and 2 * u64) keys into pointers. The data structure 0013 * is described at https://en.wikipedia.org/wiki/B-tree, we currently do not 0014 * use binary search to find the key on lookups. 0015 * 0016 * Each B+Tree consists of a head, that contains bookkeeping information and 0017 * a variable number (starting with zero) nodes. Each node contains the keys 0018 * and pointers to sub-nodes, or, for leaf nodes, the keys and values for the 0019 * tree entries. 0020 * 0021 * Each node in this implementation has the following layout: 0022 * [key1, key2, ..., keyN] [val1, val2, ..., valN] 0023 * 0024 * Each key here is an array of unsigned longs, geo->no_longs in total. The 0025 * number of keys and values (N) is geo->no_pairs. 0026 */ 0027 0028 /** 0029 * struct btree_head - btree head 0030 * 0031 * @node: the first node in the tree 0032 * @mempool: mempool used for node allocations 0033 * @height: current of the tree 0034 */ 0035 struct btree_head { 0036 unsigned long *node; 0037 mempool_t *mempool; 0038 int height; 0039 }; 0040 0041 /* btree geometry */ 0042 struct btree_geo; 0043 0044 /** 0045 * btree_alloc - allocate function for the mempool 0046 * @gfp_mask: gfp mask for the allocation 0047 * @pool_data: unused 0048 */ 0049 void *btree_alloc(gfp_t gfp_mask, void *pool_data); 0050 0051 /** 0052 * btree_free - free function for the mempool 0053 * @element: the element to free 0054 * @pool_data: unused 0055 */ 0056 void btree_free(void *element, void *pool_data); 0057 0058 /** 0059 * btree_init_mempool - initialise a btree with given mempool 0060 * 0061 * @head: the btree head to initialise 0062 * @mempool: the mempool to use 0063 * 0064 * When this function is used, there is no need to destroy 0065 * the mempool. 0066 */ 0067 void btree_init_mempool(struct btree_head *head, mempool_t *mempool); 0068 0069 /** 0070 * btree_init - initialise a btree 0071 * 0072 * @head: the btree head to initialise 0073 * 0074 * This function allocates the memory pool that the 0075 * btree needs. Returns zero or a negative error code 0076 * (-%ENOMEM) when memory allocation fails. 0077 * 0078 */ 0079 int __must_check btree_init(struct btree_head *head); 0080 0081 /** 0082 * btree_destroy - destroy mempool 0083 * 0084 * @head: the btree head to destroy 0085 * 0086 * This function destroys the internal memory pool, use only 0087 * when using btree_init(), not with btree_init_mempool(). 0088 */ 0089 void btree_destroy(struct btree_head *head); 0090 0091 /** 0092 * btree_lookup - look up a key in the btree 0093 * 0094 * @head: the btree to look in 0095 * @geo: the btree geometry 0096 * @key: the key to look up 0097 * 0098 * This function returns the value for the given key, or %NULL. 0099 */ 0100 void *btree_lookup(struct btree_head *head, struct btree_geo *geo, 0101 unsigned long *key); 0102 0103 /** 0104 * btree_insert - insert an entry into the btree 0105 * 0106 * @head: the btree to add to 0107 * @geo: the btree geometry 0108 * @key: the key to add (must not already be present) 0109 * @val: the value to add (must not be %NULL) 0110 * @gfp: allocation flags for node allocations 0111 * 0112 * This function returns 0 if the item could be added, or an 0113 * error code if it failed (may fail due to memory pressure). 0114 */ 0115 int __must_check btree_insert(struct btree_head *head, struct btree_geo *geo, 0116 unsigned long *key, void *val, gfp_t gfp); 0117 /** 0118 * btree_update - update an entry in the btree 0119 * 0120 * @head: the btree to update 0121 * @geo: the btree geometry 0122 * @key: the key to update 0123 * @val: the value to change it to (must not be %NULL) 0124 * 0125 * This function returns 0 if the update was successful, or 0126 * -%ENOENT if the key could not be found. 0127 */ 0128 int btree_update(struct btree_head *head, struct btree_geo *geo, 0129 unsigned long *key, void *val); 0130 /** 0131 * btree_remove - remove an entry from the btree 0132 * 0133 * @head: the btree to update 0134 * @geo: the btree geometry 0135 * @key: the key to remove 0136 * 0137 * This function returns the removed entry, or %NULL if the key 0138 * could not be found. 0139 */ 0140 void *btree_remove(struct btree_head *head, struct btree_geo *geo, 0141 unsigned long *key); 0142 0143 /** 0144 * btree_merge - merge two btrees 0145 * 0146 * @target: the tree that gets all the entries 0147 * @victim: the tree that gets merged into @target 0148 * @geo: the btree geometry 0149 * @gfp: allocation flags 0150 * 0151 * The two trees @target and @victim may not contain the same keys, 0152 * that is a bug and triggers a BUG(). This function returns zero 0153 * if the trees were merged successfully, and may return a failure 0154 * when memory allocation fails, in which case both trees might have 0155 * been partially merged, i.e. some entries have been moved from 0156 * @victim to @target. 0157 */ 0158 int btree_merge(struct btree_head *target, struct btree_head *victim, 0159 struct btree_geo *geo, gfp_t gfp); 0160 0161 /** 0162 * btree_last - get last entry in btree 0163 * 0164 * @head: btree head 0165 * @geo: btree geometry 0166 * @key: last key 0167 * 0168 * Returns the last entry in the btree, and sets @key to the key 0169 * of that entry; returns NULL if the tree is empty, in that case 0170 * key is not changed. 0171 */ 0172 void *btree_last(struct btree_head *head, struct btree_geo *geo, 0173 unsigned long *key); 0174 0175 /** 0176 * btree_get_prev - get previous entry 0177 * 0178 * @head: btree head 0179 * @geo: btree geometry 0180 * @key: pointer to key 0181 * 0182 * The function returns the next item right before the value pointed to by 0183 * @key, and updates @key with its key, or returns %NULL when there is no 0184 * entry with a key smaller than the given key. 0185 */ 0186 void *btree_get_prev(struct btree_head *head, struct btree_geo *geo, 0187 unsigned long *key); 0188 0189 0190 /* internal use, use btree_visitor{l,32,64,128} */ 0191 size_t btree_visitor(struct btree_head *head, struct btree_geo *geo, 0192 unsigned long opaque, 0193 void (*func)(void *elem, unsigned long opaque, 0194 unsigned long *key, size_t index, 0195 void *func2), 0196 void *func2); 0197 0198 /* internal use, use btree_grim_visitor{l,32,64,128} */ 0199 size_t btree_grim_visitor(struct btree_head *head, struct btree_geo *geo, 0200 unsigned long opaque, 0201 void (*func)(void *elem, unsigned long opaque, 0202 unsigned long *key, 0203 size_t index, void *func2), 0204 void *func2); 0205 0206 0207 #include <linux/btree-128.h> 0208 0209 extern struct btree_geo btree_geo32; 0210 #define BTREE_TYPE_SUFFIX l 0211 #define BTREE_TYPE_BITS BITS_PER_LONG 0212 #define BTREE_TYPE_GEO &btree_geo32 0213 #define BTREE_KEYTYPE unsigned long 0214 #include <linux/btree-type.h> 0215 0216 #define btree_for_each_safel(head, key, val) \ 0217 for (val = btree_lastl(head, &key); \ 0218 val; \ 0219 val = btree_get_prevl(head, &key)) 0220 0221 #define BTREE_TYPE_SUFFIX 32 0222 #define BTREE_TYPE_BITS 32 0223 #define BTREE_TYPE_GEO &btree_geo32 0224 #define BTREE_KEYTYPE u32 0225 #include <linux/btree-type.h> 0226 0227 #define btree_for_each_safe32(head, key, val) \ 0228 for (val = btree_last32(head, &key); \ 0229 val; \ 0230 val = btree_get_prev32(head, &key)) 0231 0232 extern struct btree_geo btree_geo64; 0233 #define BTREE_TYPE_SUFFIX 64 0234 #define BTREE_TYPE_BITS 64 0235 #define BTREE_TYPE_GEO &btree_geo64 0236 #define BTREE_KEYTYPE u64 0237 #include <linux/btree-type.h> 0238 0239 #define btree_for_each_safe64(head, key, val) \ 0240 for (val = btree_last64(head, &key); \ 0241 val; \ 0242 val = btree_get_prev64(head, &key)) 0243 0244 #endif
| [ Source navigation ] | [ Diff markup ] | [ Identifier search ] | [ general search ] |
|
This page was automatically generated by the 2.1.0 LXR engine. The LXR team |
|