4:2 _I|Mjq؂File not found. File not found. *l4( (  fB- t_I|+X/* SPDX-License-Identifier: GPL-2.0 */ #ifndef BTREE_H #define BTREE_H #include #include /** * DOC: B+Tree basics * * A B+Tree is a data structure for looking up arbitrary (currently allowing * unsigned long, u32, u64 and 2 * u64) keys into pointers. The data structure * is described at https://en.wikipedia.org/wiki/B-tree, we currently do not * use binary search to find the key on lookups. * * Each B+Tree consists of a head, that contains bookkeeping information and * a variable number (starting with zero) nodes. Each node contains the keys * and pointers to sub-nodes, or, for leaf nodes, the keys and values for the * tree entries. * * Each node in this implementation has the following layout: * [key1, key2, ..., keyN] [val1, val2, ..., valN] * * Each key here is an array of unsigned longs, geo->no_longs in total. The * number of keys and values (N) is geo->no_pairs. */ /** * struct btree_head - btree head * * @node: the first node in the tree * @mempool: mempool used for node allocations * @height: current of the tree */ struct btree_head { unsigned long *node; mempool_t *mempool; int height; }; /* btree geometry */ struct btree_geo; /** * btree_alloc - allocate function for the mempool * @gfp_mask: gfp mask for the allocation * @pool_data: unused */ void *btree_alloc(gfp_t gfp_mask, void *pool_data); /** * btree_free - free function for the mempool * @element: the element to free * @pool_data: unused */ void btree_free(void *element, void *pool_data); /** * btree_init_mempool - initialise a btree with given mempool * * @head: the btree head to initialise * @mempool: the mempool to use * * When this function is used, there is no need to destroy * the mempool. */ void btree_init_mempool(struct btree_head *head, mempool_t *mempool); /** * btree_init - initialise a btree * * @head: the btree head to initialise * * This function allocates the memory pool that the * btree needs. Returns zero or a negative error code * (-%ENOMEM) when memory allocation fails. * */ int __must_check btree_init(struct btree_head *head); /** * btree_destroy - destroy mempool * * @head: the btree head to destroy * * This function destroys the internal memory pool, use only * when using btree_init(), not with btree_init_mempool(). */ void btree_destroy(struct btree_head *head); /** * btree_lookup - look up a key in the btree * * @head: the btree to look in * @geo: the btree geometry * @key: the key to look up * * This function returns the value for the given key, or %NULL. */ void *btree_lookup(struct btree_head *head, struct btree_geo *geo, unsigned long *key); /** * btree_insert - insert an entry into the btree * * @head: the btree to add to * @geo: the btree geometry * @key: the key to add (must not already be present) * @val: the value to add (must not be %NULL) * @gfp: allocation flags for node allocations * * This function returns 0 if the item could be added, or an * error code if it failed (may fail due to memory pressure). */ int __must_check btree_insert(struct btree_head *head, struct btree_geo *geo, unsigned long *key, void *val, gfp_t gfp); /** * btree_update - update an entry in the btree * * @head: the btree to update * @geo: the btree geometry * @key: the key to update * @val: the value to change it to (must not be %NULL) * * This function returns 0 if the update was successful, or * -%ENOENT if the key could not be found. */ int btree_update(struct btree_head *head, struct btree_geo *geo, unsigned long *key, void *val); /** * btree_remove - remove an entry from the btree * * @head: the btree to update * @geo: the btree geometry * @key: the key to remove * * This function returns the removed entry, or %NULL if the key * could not be found. */ void *btree_remove(struct btree_head *head, struct btree_geo *geo, unsig