1b2441318SGreg Kroah-Hartman /* SPDX-License-Identifier: GPL-2.0 */ 25db53f3eSJoern Engel #ifndef BTREE_H 35db53f3eSJoern Engel #define BTREE_H 45db53f3eSJoern Engel 55db53f3eSJoern Engel #include <linux/kernel.h> 65db53f3eSJoern Engel #include <linux/mempool.h> 75db53f3eSJoern Engel 85db53f3eSJoern Engel /** 95db53f3eSJoern Engel * DOC: B+Tree basics 105db53f3eSJoern Engel * 115db53f3eSJoern Engel * A B+Tree is a data structure for looking up arbitrary (currently allowing 125db53f3eSJoern Engel * unsigned long, u32, u64 and 2 * u64) keys into pointers. The data structure 137f317d34SAlexander A. Klimov * is described at https://en.wikipedia.org/wiki/B-tree, we currently do not 145db53f3eSJoern Engel * use binary search to find the key on lookups. 155db53f3eSJoern Engel * 165db53f3eSJoern Engel * Each B+Tree consists of a head, that contains bookkeeping information and 175db53f3eSJoern Engel * a variable number (starting with zero) nodes. Each node contains the keys 185db53f3eSJoern Engel * and pointers to sub-nodes, or, for leaf nodes, the keys and values for the 195db53f3eSJoern Engel * tree entries. 205db53f3eSJoern Engel * 215db53f3eSJoern Engel * Each node in this implementation has the following layout: 225db53f3eSJoern Engel * [key1, key2, ..., keyN] [val1, val2, ..., valN] 235db53f3eSJoern Engel * 245db53f3eSJoern Engel * Each key here is an array of unsigned longs, geo->no_longs in total. The 255db53f3eSJoern Engel * number of keys and values (N) is geo->no_pairs. 265db53f3eSJoern Engel */ 275db53f3eSJoern Engel 285db53f3eSJoern Engel /** 295db53f3eSJoern Engel * struct btree_head - btree head 305db53f3eSJoern Engel * 315db53f3eSJoern Engel * @node: the first node in the tree 325db53f3eSJoern Engel * @mempool: mempool used for node allocations 335db53f3eSJoern Engel * @height: current of the tree 345db53f3eSJoern Engel */ 355db53f3eSJoern Engel struct btree_head { 365db53f3eSJoern Engel unsigned long *node; 375db53f3eSJoern Engel mempool_t *mempool; 385db53f3eSJoern Engel int height; 395db53f3eSJoern Engel }; 405db53f3eSJoern Engel 415db53f3eSJoern Engel /* btree geometry */ 425db53f3eSJoern Engel struct btree_geo; 435db53f3eSJoern Engel 445db53f3eSJoern Engel /** 455db53f3eSJoern Engel * btree_alloc - allocate function for the mempool 465db53f3eSJoern Engel * @gfp_mask: gfp mask for the allocation 475db53f3eSJoern Engel * @pool_data: unused 485db53f3eSJoern Engel */ 495db53f3eSJoern Engel void *btree_alloc(gfp_t gfp_mask, void *pool_data); 505db53f3eSJoern Engel 515db53f3eSJoern Engel /** 525db53f3eSJoern Engel * btree_free - free function for the mempool 535db53f3eSJoern Engel * @element: the element to free 545db53f3eSJoern Engel * @pool_data: unused 555db53f3eSJoern Engel */ 565db53f3eSJoern Engel void btree_free(void *element, void *pool_data); 575db53f3eSJoern Engel 585db53f3eSJoern Engel /** 595db53f3eSJoern Engel * btree_init_mempool - initialise a btree with given mempool 605db53f3eSJoern Engel * 615db53f3eSJoern Engel * @head: the btree head to initialise 625db53f3eSJoern Engel * @mempool: the mempool to use 635db53f3eSJoern Engel * 645db53f3eSJoern Engel * When this function is used, there is no need to destroy 655db53f3eSJoern Engel * the mempool. 665db53f3eSJoern Engel */ 675db53f3eSJoern Engel void btree_init_mempool(struct btree_head *head, mempool_t *mempool); 685db53f3eSJoern Engel 695db53f3eSJoern Engel /** 705db53f3eSJoern Engel * btree_init - initialise a btree 715db53f3eSJoern Engel * 725db53f3eSJoern Engel * @head: the btree head to initialise 735db53f3eSJoern Engel * 745db53f3eSJoern Engel * This function allocates the memory pool that the 755db53f3eSJoern Engel * btree needs. Returns zero or a negative error code 765db53f3eSJoern Engel * (-%ENOMEM) when memory allocation fails. 775db53f3eSJoern Engel * 785db53f3eSJoern Engel */ 795db53f3eSJoern Engel int __must_check btree_init(struct btree_head *head); 805db53f3eSJoern Engel 815db53f3eSJoern Engel /** 825db53f3eSJoern Engel * btree_destroy - destroy mempool 835db53f3eSJoern Engel * 845db53f3eSJoern Engel * @head: the btree head to destroy 855db53f3eSJoern Engel * 865db53f3eSJoern Engel * This function destroys the internal memory pool, use only 875db53f3eSJoern Engel * when using btree_init(), not with btree_init_mempool(). 885db53f3eSJoern Engel */ 895db53f3eSJoern Engel void btree_destroy(struct btree_head *head); 905db53f3eSJoern Engel 915db53f3eSJoern Engel /** 925db53f3eSJoern Engel * btree_lookup - look up a key in the btree 935db53f3eSJoern Engel * 945db53f3eSJoern Engel * @head: the btree to look in 955db53f3eSJoern Engel * @geo: the btree geometry 965db53f3eSJoern Engel * @key: the key to look up 975db53f3eSJoern Engel * 985db53f3eSJoern Engel * This function returns the value for the given key, or %NULL. 995db53f3eSJoern Engel */ 1005db53f3eSJoern Engel void *btree_lookup(struct btree_head *head, struct btree_geo *geo, 1015db53f3eSJoern Engel unsigned long *key); 1025db53f3eSJoern Engel 1035db53f3eSJoern Engel /** 1045db53f3eSJoern Engel * btree_insert - insert an entry into the btree 1055db53f3eSJoern Engel * 1065db53f3eSJoern Engel * @head: the btree to add to 1075db53f3eSJoern Engel * @geo: the btree geometry 1085db53f3eSJoern Engel * @key: the key to add (must not already be present) 1095db53f3eSJoern Engel * @val: the value to add (must not be %NULL) 1105db53f3eSJoern Engel * @gfp: allocation flags for node allocations 1115db53f3eSJoern Engel * 1125db53f3eSJoern Engel * This function returns 0 if the item could be added, or an 1135db53f3eSJoern Engel * error code if it failed (may fail due to memory pressure). 1145db53f3eSJoern Engel */ 1155db53f3eSJoern Engel int __must_check btree_insert(struct btree_head *head, struct btree_geo *geo, 1165db53f3eSJoern Engel unsigned long *key, void *val, gfp_t gfp); 1175db53f3eSJoern Engel /** 1185db53f3eSJoern Engel * btree_update - update an entry in the btree 1195db53f3eSJoern Engel * 1205db53f3eSJoern Engel * @head: the btree to update 1215db53f3eSJoern Engel * @geo: the btree geometry 1225db53f3eSJoern Engel * @key: the key to update 1235db53f3eSJoern Engel * @val: the value to change it to (must not be %NULL) 1245db53f3eSJoern Engel * 1255db53f3eSJoern Engel * This function returns 0 if the update was successful, or 1265db53f3eSJoern Engel * -%ENOENT if the key could not be found. 1275db53f3eSJoern Engel */ 1285db53f3eSJoern Engel int btree_update(struct btree_head *head, struct btree_geo *geo, 1295db53f3eSJoern Engel unsigned long *key, void *val); 1305db53f3eSJoern Engel /** 1315db53f3eSJoern Engel * btree_remove - remove an entry from the btree 1325db53f3eSJoern Engel * 1335db53f3eSJoern Engel * @head: the btree to update 1345db53f3eSJoern Engel * @geo: the btree geometry 1355db53f3eSJoern Engel * @key: the key to remove 1365db53f3eSJoern Engel * 1375db53f3eSJoern Engel * This function returns the removed entry, or %NULL if the key 1385db53f3eSJoern Engel * could not be found. 1395db53f3eSJoern Engel */ 1405db53f3eSJoern Engel void *btree_remove(struct btree_head *head, struct btree_geo *geo, 1415db53f3eSJoern Engel unsigned long *key); 1425db53f3eSJoern Engel 1435db53f3eSJoern Engel /** 1445db53f3eSJoern Engel * btree_merge - merge two btrees 1455db53f3eSJoern Engel * 1465db53f3eSJoern Engel * @target: the tree that gets all the entries 1475db53f3eSJoern Engel * @victim: the tree that gets merged into @target 1485db53f3eSJoern Engel * @geo: the btree geometry 1495db53f3eSJoern Engel * @gfp: allocation flags 1505db53f3eSJoern Engel * 1515db53f3eSJoern Engel * The two trees @target and @victim may not contain the same keys, 1525db53f3eSJoern Engel * that is a bug and triggers a BUG(). This function returns zero 1535db53f3eSJoern Engel * if the trees were merged successfully, and may return a failure 1545db53f3eSJoern Engel * when memory allocation fails, in which case both trees might have 1555db53f3eSJoern Engel * been partially merged, i.e. some entries have been moved from 1565db53f3eSJoern Engel * @victim to @target. 1575db53f3eSJoern Engel */ 1585db53f3eSJoern Engel int btree_merge(struct btree_head *target, struct btree_head *victim, 1595db53f3eSJoern Engel struct btree_geo *geo, gfp_t gfp); 1605db53f3eSJoern Engel 1615db53f3eSJoern Engel /** 1625db53f3eSJoern Engel * btree_last - get last entry in btree 1635db53f3eSJoern Engel * 1645db53f3eSJoern Engel * @head: btree head 1655db53f3eSJoern Engel * @geo: btree geometry 1665db53f3eSJoern Engel * @key: last key 1675db53f3eSJoern Engel * 1685db53f3eSJoern Engel * Returns the last entry in the btree, and sets @key to the key 1695db53f3eSJoern Engel * of that entry; returns NULL if the tree is empty, in that case 1705db53f3eSJoern Engel * key is not changed. 1715db53f3eSJoern Engel */ 1725db53f3eSJoern Engel void *btree_last(struct btree_head *head, struct btree_geo *geo, 1735db53f3eSJoern Engel unsigned long *key); 1745db53f3eSJoern Engel 1755db53f3eSJoern Engel /** 1765db53f3eSJoern Engel * btree_get_prev - get previous entry 1775db53f3eSJoern Engel * 1785db53f3eSJoern Engel * @head: btree head 1795db53f3eSJoern Engel * @geo: btree geometry 1805db53f3eSJoern Engel * @key: pointer to key 1815db53f3eSJoern Engel * 1825db53f3eSJoern Engel * The function returns the next item right before the value pointed to by 1835db53f3eSJoern Engel * @key, and updates @key with its key, or returns %NULL when there is no 1845db53f3eSJoern Engel * entry with a key smaller than the given key. 1855db53f3eSJoern Engel */ 1865db53f3eSJoern Engel void *btree_get_prev(struct btree_head *head, struct btree_geo *geo, 1875db53f3eSJoern Engel unsigned long *key); 1885db53f3eSJoern Engel 1895db53f3eSJoern Engel 1905db53f3eSJoern Engel /* internal use, use btree_visitor{l,32,64,128} */ 1915db53f3eSJoern Engel size_t btree_visitor(struct btree_head *head, struct btree_geo *geo, 1925db53f3eSJoern Engel unsigned long opaque, 1935db53f3eSJoern Engel void (*func)(void *elem, unsigned long opaque, 1945db53f3eSJoern Engel unsigned long *key, size_t index, 1955db53f3eSJoern Engel void *func2), 1965db53f3eSJoern Engel void *func2); 1975db53f3eSJoern Engel 1985db53f3eSJoern Engel /* internal use, use btree_grim_visitor{l,32,64,128} */ 1995db53f3eSJoern Engel size_t btree_grim_visitor(struct btree_head *head, struct btree_geo *geo, 2005db53f3eSJoern Engel unsigned long opaque, 2015db53f3eSJoern Engel void (*func)(void *elem, unsigned long opaque, 2025db53f3eSJoern Engel unsigned long *key, 2035db53f3eSJoern Engel size_t index, void *func2), 2045db53f3eSJoern Engel void *func2); 2055db53f3eSJoern Engel 2065db53f3eSJoern Engel 2075db53f3eSJoern Engel #include <linux/btree-128.h> 2085db53f3eSJoern Engel 2095db53f3eSJoern Engel extern struct btree_geo btree_geo32; 2105db53f3eSJoern Engel #define BTREE_TYPE_SUFFIX l 2115db53f3eSJoern Engel #define BTREE_TYPE_BITS BITS_PER_LONG 2125db53f3eSJoern Engel #define BTREE_TYPE_GEO &btree_geo32 2135db53f3eSJoern Engel #define BTREE_KEYTYPE unsigned long 2145db53f3eSJoern Engel #include <linux/btree-type.h> 2155db53f3eSJoern Engel 2165db53f3eSJoern Engel #define btree_for_each_safel(head, key, val) \ 2175db53f3eSJoern Engel for (val = btree_lastl(head, &key); \ 2185db53f3eSJoern Engel val; \ 2195db53f3eSJoern Engel val = btree_get_prevl(head, &key)) 2205db53f3eSJoern Engel 2215db53f3eSJoern Engel #define BTREE_TYPE_SUFFIX 32 2225db53f3eSJoern Engel #define BTREE_TYPE_BITS 32 2235db53f3eSJoern Engel #define BTREE_TYPE_GEO &btree_geo32 2245db53f3eSJoern Engel #define BTREE_KEYTYPE u32 2255db53f3eSJoern Engel #include <linux/btree-type.h> 2265db53f3eSJoern Engel 2275db53f3eSJoern Engel #define btree_for_each_safe32(head, key, val) \ 2285db53f3eSJoern Engel for (val = btree_last32(head, &key); \ 2295db53f3eSJoern Engel val; \ 2305db53f3eSJoern Engel val = btree_get_prev32(head, &key)) 2315db53f3eSJoern Engel 2325db53f3eSJoern Engel extern struct btree_geo btree_geo64; 2335db53f3eSJoern Engel #define BTREE_TYPE_SUFFIX 64 2345db53f3eSJoern Engel #define BTREE_TYPE_BITS 64 2355db53f3eSJoern Engel #define BTREE_TYPE_GEO &btree_geo64 2365db53f3eSJoern Engel #define BTREE_KEYTYPE u64 2375db53f3eSJoern Engel #include <linux/btree-type.h> 2385db53f3eSJoern Engel 2395db53f3eSJoern Engel #define btree_for_each_safe64(head, key, val) \ 2405db53f3eSJoern Engel for (val = btree_last64(head, &key); \ 2415db53f3eSJoern Engel val; \ 2425db53f3eSJoern Engel val = btree_get_prev64(head, &key)) 2435db53f3eSJoern Engel 2445db53f3eSJoern Engel #endif 245