// SPDX-License-Identifier: GPL-2.0-only /* * lib/btree.c - Simple In-memory B+Tree * * Copyright (c) 2007-2008 Joern Engel <[email protected]> * Bits and pieces stolen from Peter Zijlstra's code, which is * Copyright 2007, Red Hat Inc. Peter Zijlstra * * see http://programming.kicks-ass.net/kernel-patches/vma_lookup/btree.patch * * A relatively simple B+Tree implementation. I have written it as a learning * exercise to understand how B+Trees work. Turned out to be useful as well. * * B+Trees can be used similar to Linux radix trees (which don't have anything * in common with textbook radix trees, beware). Prerequisite for them working * well is that access to a random tree node is much faster than a large number * of operations within each node. * * Disks have fulfilled the prerequisite for a long time. More recently DRAM * has gained similar properties, as memory access times, when measured in cpu * cycles, have increased. Cacheline sizes have increased as well, which also * helps B+Trees. * * Compared to radix trees, B+Trees are more efficient when dealing with a * sparsely populated address space. Between 25% and 50% of the memory is * occupied with valid pointers. When densely populated, radix trees contain * ~98% pointers - hard to beat. Very sparse radix trees contain only ~2% * pointers. * * This particular implementation stores pointers identified by a long value. * Storing NULL pointers is illegal, lookup will return NULL when no entry * was found. * * A tricks was used that is not commonly found in textbooks. The lowest * values are to the right, not to the left. All used slots within a node * are on the left, all unused slots contain NUL values. Most operations * simply loop once over all slots and terminate on the first NUL. */ #include <linux/btree.h> #include <linux/cache.h> #include <linux/kernel.h> #include <linux/slab.h> #include <linux/module.h> #define NODESIZE … struct btree_geo { … }; struct btree_geo btree_geo32 = …; EXPORT_SYMBOL_GPL(…); #define LONG_PER_U64 … struct btree_geo btree_geo64 = …; EXPORT_SYMBOL_GPL(…); struct btree_geo btree_geo128 = …; EXPORT_SYMBOL_GPL(…); #define MAX_KEYLEN … static struct kmem_cache *btree_cachep; void *btree_alloc(gfp_t gfp_mask, void *pool_data) { … } EXPORT_SYMBOL_GPL(…); void btree_free(void *element, void *pool_data) { … } EXPORT_SYMBOL_GPL(…); static unsigned long *btree_node_alloc(struct btree_head *head, gfp_t gfp) { … } static int longcmp(const unsigned long *l1, const unsigned long *l2, size_t n) { … } static unsigned long *longcpy(unsigned long *dest, const unsigned long *src, size_t n) { … } static unsigned long *longset(unsigned long *s, unsigned long c, size_t n) { … } static void dec_key(struct btree_geo *geo, unsigned long *key) { … } static unsigned long *bkey(struct btree_geo *geo, unsigned long *node, int n) { … } static void *bval(struct btree_geo *geo, unsigned long *node, int n) { … } static void setkey(struct btree_geo *geo, unsigned long *node, int n, unsigned long *key) { … } static void setval(struct btree_geo *geo, unsigned long *node, int n, void *val) { … } static void clearpair(struct btree_geo *geo, unsigned long *node, int n) { … } static inline void __btree_init(struct btree_head *head) { … } void btree_init_mempool(struct btree_head *head, mempool_t *mempool) { … } EXPORT_SYMBOL_GPL(…); int btree_init(struct btree_head *head) { … } EXPORT_SYMBOL_GPL(…); void btree_destroy(struct btree_head *head) { … } EXPORT_SYMBOL_GPL(…); void *btree_last(struct btree_head *head, struct btree_geo *geo, unsigned long *key) { … } EXPORT_SYMBOL_GPL(…); static int keycmp(struct btree_geo *geo, unsigned long *node, int pos, unsigned long *key) { … } static int keyzero(struct btree_geo *geo, unsigned long *key) { … } static void *btree_lookup_node(struct btree_head *head, struct btree_geo *geo, unsigned long *key) { … } void *btree_lookup(struct btree_head *head, struct btree_geo *geo, unsigned long *key) { … } EXPORT_SYMBOL_GPL(…); int btree_update(struct btree_head *head, struct btree_geo *geo, unsigned long *key, void *val) { … } EXPORT_SYMBOL_GPL(…); /* * Usually this function is quite similar to normal lookup. But the key of * a parent node may be smaller than the smallest key of all its siblings. * In such a case we cannot just return NULL, as we have only proven that no * key smaller than __key, but larger than this parent key exists. * So we set __key to the parent key and retry. We have to use the smallest * such parent key, which is the last parent key we encountered. */ void *btree_get_prev(struct btree_head *head, struct btree_geo *geo, unsigned long *__key) { … } EXPORT_SYMBOL_GPL(…); static int getpos(struct btree_geo *geo, unsigned long *node, unsigned long *key) { … } static int getfill(struct btree_geo *geo, unsigned long *node, int start) { … } /* * locate the correct leaf node in the btree */ static unsigned long *find_level(struct btree_head *head, struct btree_geo *geo, unsigned long *key, int level) { … } static int btree_grow(struct btree_head *head, struct btree_geo *geo, gfp_t gfp) { … } static void btree_shrink(struct btree_head *head, struct btree_geo *geo) { … } static int btree_insert_level(struct btree_head *head, struct btree_geo *geo, unsigned long *key, void *val, int level, gfp_t gfp) { … } int btree_insert(struct btree_head *head, struct btree_geo *geo, unsigned long *key, void *val, gfp_t gfp) { … } EXPORT_SYMBOL_GPL(…); static void *btree_remove_level(struct btree_head *head, struct btree_geo *geo, unsigned long *key, int level); static void merge(struct btree_head *head, struct btree_geo *geo, int level, unsigned long *left, int lfill, unsigned long *right, int rfill, unsigned long *parent, int lpos) { … } static void rebalance(struct btree_head *head, struct btree_geo *geo, unsigned long *key, int level, unsigned long *child, int fill) { … } static void *btree_remove_level(struct btree_head *head, struct btree_geo *geo, unsigned long *key, int level) { … } void *btree_remove(struct btree_head *head, struct btree_geo *geo, unsigned long *key) { … } EXPORT_SYMBOL_GPL(…); int btree_merge(struct btree_head *target, struct btree_head *victim, struct btree_geo *geo, gfp_t gfp) { … } EXPORT_SYMBOL_GPL(…); static size_t __btree_for_each(struct btree_head *head, struct btree_geo *geo, unsigned long *node, unsigned long opaque, void (*func)(void *elem, unsigned long opaque, unsigned long *key, size_t index, void *func2), void *func2, int reap, int height, size_t count) { … } static void empty(void *elem, unsigned long opaque, unsigned long *key, size_t index, void *func2) { … } void visitorl(void *elem, unsigned long opaque, unsigned long *key, size_t index, void *__func) { … } EXPORT_SYMBOL_GPL(…); void visitor32(void *elem, unsigned long opaque, unsigned long *__key, size_t index, void *__func) { … } EXPORT_SYMBOL_GPL(…); void visitor64(void *elem, unsigned long opaque, unsigned long *__key, size_t index, void *__func) { … } EXPORT_SYMBOL_GPL(…); void visitor128(void *elem, unsigned long opaque, unsigned long *__key, size_t index, void *__func) { … } EXPORT_SYMBOL_GPL(…); size_t btree_visitor(struct btree_head *head, struct btree_geo *geo, unsigned long opaque, void (*func)(void *elem, unsigned long opaque, unsigned long *key, size_t index, void *func2), void *func2) { … } EXPORT_SYMBOL_GPL(…); size_t btree_grim_visitor(struct btree_head *head, struct btree_geo *geo, unsigned long opaque, void (*func)(void *elem, unsigned long opaque, unsigned long *key, size_t index, void *func2), void *func2) { … } EXPORT_SYMBOL_GPL(…); static int __init btree_module_init(void) { … } static void __exit btree_module_exit(void) { … } /* If core code starts using btree, initialization should happen even earlier */ module_init(…) …; module_exit(btree_module_exit); MODULE_AUTHOR(…) …; MODULE_AUTHOR(…) …;
Codebase Browser
linux