^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1) // SPDX-License-Identifier: GPL-2.0-only
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 2) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 3) * lib/btree.c - Simple In-memory B+Tree
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 4) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 5) * Copyright (c) 2007-2008 Joern Engel <joern@purestorage.com>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 6) * Bits and pieces stolen from Peter Zijlstra's code, which is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 7) * Copyright 2007, Red Hat Inc. Peter Zijlstra
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 8) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 9) * see http://programming.kicks-ass.net/kernel-patches/vma_lookup/btree.patch
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 10) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 11) * A relatively simple B+Tree implementation. I have written it as a learning
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 12) * exercise to understand how B+Trees work. Turned out to be useful as well.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 13) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 14) * B+Trees can be used similar to Linux radix trees (which don't have anything
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 15) * in common with textbook radix trees, beware). Prerequisite for them working
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 16) * well is that access to a random tree node is much faster than a large number
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 17) * of operations within each node.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 18) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 19) * Disks have fulfilled the prerequisite for a long time. More recently DRAM
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 20) * has gained similar properties, as memory access times, when measured in cpu
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 21) * cycles, have increased. Cacheline sizes have increased as well, which also
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 22) * helps B+Trees.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 23) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 24) * Compared to radix trees, B+Trees are more efficient when dealing with a
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 25) * sparsely populated address space. Between 25% and 50% of the memory is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 26) * occupied with valid pointers. When densely populated, radix trees contain
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 27) * ~98% pointers - hard to beat. Very sparse radix trees contain only ~2%
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 28) * pointers.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 29) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 30) * This particular implementation stores pointers identified by a long value.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 31) * Storing NULL pointers is illegal, lookup will return NULL when no entry
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 32) * was found.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 33) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 34) * A tricks was used that is not commonly found in textbooks. The lowest
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 35) * values are to the right, not to the left. All used slots within a node
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 36) * are on the left, all unused slots contain NUL values. Most operations
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 37) * simply loop once over all slots and terminate on the first NUL.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 38) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 39)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 40) #include <linux/btree.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 41) #include <linux/cache.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 42) #include <linux/kernel.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 43) #include <linux/slab.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 44) #include <linux/module.h>
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 45)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 46) #define MAX(a, b) ((a) > (b) ? (a) : (b))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47) #define NODESIZE MAX(L1_CACHE_BYTES, 128)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49) struct btree_geo {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50) int keylen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51) int no_pairs;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52) int no_longs;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 54)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 55) struct btree_geo btree_geo32 = {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 56) .keylen = 1,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57) .no_pairs = NODESIZE / sizeof(long) / 2,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58) .no_longs = NODESIZE / sizeof(long) / 2,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60) EXPORT_SYMBOL_GPL(btree_geo32);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62) #define LONG_PER_U64 (64 / BITS_PER_LONG)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63) struct btree_geo btree_geo64 = {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64) .keylen = LONG_PER_U64,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 65) .no_pairs = NODESIZE / sizeof(long) / (1 + LONG_PER_U64),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 66) .no_longs = LONG_PER_U64 * (NODESIZE / sizeof(long) / (1 + LONG_PER_U64)),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 67) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 68) EXPORT_SYMBOL_GPL(btree_geo64);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 69)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 70) struct btree_geo btree_geo128 = {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 71) .keylen = 2 * LONG_PER_U64,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 72) .no_pairs = NODESIZE / sizeof(long) / (1 + 2 * LONG_PER_U64),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 73) .no_longs = 2 * LONG_PER_U64 * (NODESIZE / sizeof(long) / (1 + 2 * LONG_PER_U64)),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 74) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 75) EXPORT_SYMBOL_GPL(btree_geo128);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 76)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 77) #define MAX_KEYLEN (2 * LONG_PER_U64)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 78)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 79) static struct kmem_cache *btree_cachep;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 80)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 81) void *btree_alloc(gfp_t gfp_mask, void *pool_data)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 82) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 83) return kmem_cache_alloc(btree_cachep, gfp_mask);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 84) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 85) EXPORT_SYMBOL_GPL(btree_alloc);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 86)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 87) void btree_free(void *element, void *pool_data)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 88) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 89) kmem_cache_free(btree_cachep, element);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 90) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 91) EXPORT_SYMBOL_GPL(btree_free);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 92)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 93) static unsigned long *btree_node_alloc(struct btree_head *head, gfp_t gfp)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 94) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 95) unsigned long *node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 96)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 97) node = mempool_alloc(head->mempool, gfp);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 98) if (likely(node))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 99) memset(node, 0, NODESIZE);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 100) return node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 101) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 102)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 103) static int longcmp(const unsigned long *l1, const unsigned long *l2, size_t n)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 104) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 105) size_t i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 106)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 107) for (i = 0; i < n; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 108) if (l1[i] < l2[i])
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 109) return -1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 110) if (l1[i] > l2[i])
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 111) return 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 112) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 113) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 114) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 115)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 116) static unsigned long *longcpy(unsigned long *dest, const unsigned long *src,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 117) size_t n)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 118) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 119) size_t i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 120)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 121) for (i = 0; i < n; i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 122) dest[i] = src[i];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 123) return dest;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 124) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 125)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 126) static unsigned long *longset(unsigned long *s, unsigned long c, size_t n)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 127) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 128) size_t i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 129)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 130) for (i = 0; i < n; i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 131) s[i] = c;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 132) return s;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 133) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 134)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 135) static void dec_key(struct btree_geo *geo, unsigned long *key)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 136) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 137) unsigned long val;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 138) int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 139)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 140) for (i = geo->keylen - 1; i >= 0; i--) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 141) val = key[i];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 142) key[i] = val - 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 143) if (val)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 144) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 145) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 146) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 147)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 148) static unsigned long *bkey(struct btree_geo *geo, unsigned long *node, int n)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 149) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 150) return &node[n * geo->keylen];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 151) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 152)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 153) static void *bval(struct btree_geo *geo, unsigned long *node, int n)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 154) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 155) return (void *)node[geo->no_longs + n];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 156) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 157)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 158) static void setkey(struct btree_geo *geo, unsigned long *node, int n,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 159) unsigned long *key)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 160) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 161) longcpy(bkey(geo, node, n), key, geo->keylen);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 162) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 163)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 164) static void setval(struct btree_geo *geo, unsigned long *node, int n,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 165) void *val)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 166) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 167) node[geo->no_longs + n] = (unsigned long) val;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 168) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 169)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 170) static void clearpair(struct btree_geo *geo, unsigned long *node, int n)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 171) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 172) longset(bkey(geo, node, n), 0, geo->keylen);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 173) node[geo->no_longs + n] = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 174) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 175)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 176) static inline void __btree_init(struct btree_head *head)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 177) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 178) head->node = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 179) head->height = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 180) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 181)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 182) void btree_init_mempool(struct btree_head *head, mempool_t *mempool)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 183) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 184) __btree_init(head);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 185) head->mempool = mempool;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 186) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 187) EXPORT_SYMBOL_GPL(btree_init_mempool);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 188)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 189) int btree_init(struct btree_head *head)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 190) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 191) __btree_init(head);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 192) head->mempool = mempool_create(0, btree_alloc, btree_free, NULL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 193) if (!head->mempool)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 194) return -ENOMEM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 195) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 196) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 197) EXPORT_SYMBOL_GPL(btree_init);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 198)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 199) void btree_destroy(struct btree_head *head)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 200) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 201) mempool_free(head->node, head->mempool);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 202) mempool_destroy(head->mempool);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 203) head->mempool = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 204) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 205) EXPORT_SYMBOL_GPL(btree_destroy);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 206)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 207) void *btree_last(struct btree_head *head, struct btree_geo *geo,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 208) unsigned long *key)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 209) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 210) int height = head->height;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 211) unsigned long *node = head->node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 212)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 213) if (height == 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 214) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 215)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 216) for ( ; height > 1; height--)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 217) node = bval(geo, node, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 218)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 219) longcpy(key, bkey(geo, node, 0), geo->keylen);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 220) return bval(geo, node, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 221) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 222) EXPORT_SYMBOL_GPL(btree_last);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 223)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 224) static int keycmp(struct btree_geo *geo, unsigned long *node, int pos,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 225) unsigned long *key)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 226) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 227) return longcmp(bkey(geo, node, pos), key, geo->keylen);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 228) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 229)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 230) static int keyzero(struct btree_geo *geo, unsigned long *key)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 231) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 232) int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 233)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 234) for (i = 0; i < geo->keylen; i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 235) if (key[i])
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 236) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 237)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 238) return 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 239) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 240)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 241) void *btree_lookup(struct btree_head *head, struct btree_geo *geo,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 242) unsigned long *key)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 243) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 244) int i, height = head->height;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 245) unsigned long *node = head->node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 246)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 247) if (height == 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 248) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 249)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 250) for ( ; height > 1; height--) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 251) for (i = 0; i < geo->no_pairs; i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 252) if (keycmp(geo, node, i, key) <= 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 253) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 254) if (i == geo->no_pairs)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 255) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 256) node = bval(geo, node, i);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 257) if (!node)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 258) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 259) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 260)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 261) if (!node)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 262) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 263)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 264) for (i = 0; i < geo->no_pairs; i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 265) if (keycmp(geo, node, i, key) == 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 266) return bval(geo, node, i);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 267) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 268) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 269) EXPORT_SYMBOL_GPL(btree_lookup);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 270)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 271) int btree_update(struct btree_head *head, struct btree_geo *geo,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 272) unsigned long *key, void *val)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 273) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 274) int i, height = head->height;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 275) unsigned long *node = head->node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 276)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 277) if (height == 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 278) return -ENOENT;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 279)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 280) for ( ; height > 1; height--) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 281) for (i = 0; i < geo->no_pairs; i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 282) if (keycmp(geo, node, i, key) <= 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 283) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 284) if (i == geo->no_pairs)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 285) return -ENOENT;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 286) node = bval(geo, node, i);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 287) if (!node)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 288) return -ENOENT;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 289) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 290)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 291) if (!node)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 292) return -ENOENT;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 293)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 294) for (i = 0; i < geo->no_pairs; i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 295) if (keycmp(geo, node, i, key) == 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 296) setval(geo, node, i, val);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 297) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 298) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 299) return -ENOENT;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 300) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 301) EXPORT_SYMBOL_GPL(btree_update);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 302)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 303) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 304) * Usually this function is quite similar to normal lookup. But the key of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 305) * a parent node may be smaller than the smallest key of all its siblings.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 306) * In such a case we cannot just return NULL, as we have only proven that no
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 307) * key smaller than __key, but larger than this parent key exists.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 308) * So we set __key to the parent key and retry. We have to use the smallest
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 309) * such parent key, which is the last parent key we encountered.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 310) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 311) void *btree_get_prev(struct btree_head *head, struct btree_geo *geo,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 312) unsigned long *__key)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 313) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 314) int i, height;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 315) unsigned long *node, *oldnode;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 316) unsigned long *retry_key = NULL, key[MAX_KEYLEN];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 317)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 318) if (keyzero(geo, __key))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 319) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 320)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 321) if (head->height == 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 322) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 323) longcpy(key, __key, geo->keylen);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 324) retry:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 325) dec_key(geo, key);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 326)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 327) node = head->node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 328) for (height = head->height ; height > 1; height--) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 329) for (i = 0; i < geo->no_pairs; i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 330) if (keycmp(geo, node, i, key) <= 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 331) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 332) if (i == geo->no_pairs)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 333) goto miss;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 334) oldnode = node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 335) node = bval(geo, node, i);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 336) if (!node)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 337) goto miss;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 338) retry_key = bkey(geo, oldnode, i);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 339) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 340)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 341) if (!node)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 342) goto miss;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 343)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 344) for (i = 0; i < geo->no_pairs; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 345) if (keycmp(geo, node, i, key) <= 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 346) if (bval(geo, node, i)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 347) longcpy(__key, bkey(geo, node, i), geo->keylen);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 348) return bval(geo, node, i);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 349) } else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 350) goto miss;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 351) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 352) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 353) miss:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 354) if (retry_key) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 355) longcpy(key, retry_key, geo->keylen);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 356) retry_key = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 357) goto retry;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 358) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 359) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 360) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 361) EXPORT_SYMBOL_GPL(btree_get_prev);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 362)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 363) static int getpos(struct btree_geo *geo, unsigned long *node,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 364) unsigned long *key)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 365) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 366) int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 367)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 368) for (i = 0; i < geo->no_pairs; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 369) if (keycmp(geo, node, i, key) <= 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 370) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 371) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 372) return i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 373) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 374)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 375) static int getfill(struct btree_geo *geo, unsigned long *node, int start)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 376) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 377) int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 378)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 379) for (i = start; i < geo->no_pairs; i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 380) if (!bval(geo, node, i))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 381) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 382) return i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 383) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 384)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 385) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 386) * locate the correct leaf node in the btree
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 387) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 388) static unsigned long *find_level(struct btree_head *head, struct btree_geo *geo,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 389) unsigned long *key, int level)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 390) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 391) unsigned long *node = head->node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 392) int i, height;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 393)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 394) for (height = head->height; height > level; height--) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 395) for (i = 0; i < geo->no_pairs; i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 396) if (keycmp(geo, node, i, key) <= 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 397) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 398)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 399) if ((i == geo->no_pairs) || !bval(geo, node, i)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 400) /* right-most key is too large, update it */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 401) /* FIXME: If the right-most key on higher levels is
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 402) * always zero, this wouldn't be necessary. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 403) i--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 404) setkey(geo, node, i, key);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 405) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 406) BUG_ON(i < 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 407) node = bval(geo, node, i);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 408) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 409) BUG_ON(!node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 410) return node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 411) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 412)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 413) static int btree_grow(struct btree_head *head, struct btree_geo *geo,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 414) gfp_t gfp)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 415) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 416) unsigned long *node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 417) int fill;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 418)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 419) node = btree_node_alloc(head, gfp);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 420) if (!node)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 421) return -ENOMEM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 422) if (head->node) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 423) fill = getfill(geo, head->node, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 424) setkey(geo, node, 0, bkey(geo, head->node, fill - 1));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 425) setval(geo, node, 0, head->node);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 426) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 427) head->node = node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 428) head->height++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 429) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 430) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 431)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 432) static void btree_shrink(struct btree_head *head, struct btree_geo *geo)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 433) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 434) unsigned long *node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 435) int fill;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 436)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 437) if (head->height <= 1)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 438) return;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 439)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 440) node = head->node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 441) fill = getfill(geo, node, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 442) BUG_ON(fill > 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 443) head->node = bval(geo, node, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 444) head->height--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 445) mempool_free(node, head->mempool);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 446) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 447)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 448) static int btree_insert_level(struct btree_head *head, struct btree_geo *geo,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 449) unsigned long *key, void *val, int level,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 450) gfp_t gfp)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 451) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 452) unsigned long *node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 453) int i, pos, fill, err;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 454)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 455) BUG_ON(!val);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 456) if (head->height < level) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 457) err = btree_grow(head, geo, gfp);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 458) if (err)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 459) return err;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 460) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 461)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 462) retry:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 463) node = find_level(head, geo, key, level);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 464) pos = getpos(geo, node, key);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 465) fill = getfill(geo, node, pos);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 466) /* two identical keys are not allowed */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 467) BUG_ON(pos < fill && keycmp(geo, node, pos, key) == 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 468)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 469) if (fill == geo->no_pairs) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 470) /* need to split node */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 471) unsigned long *new;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 472)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 473) new = btree_node_alloc(head, gfp);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 474) if (!new)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 475) return -ENOMEM;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 476) err = btree_insert_level(head, geo,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 477) bkey(geo, node, fill / 2 - 1),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 478) new, level + 1, gfp);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 479) if (err) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 480) mempool_free(new, head->mempool);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 481) return err;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 482) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 483) for (i = 0; i < fill / 2; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 484) setkey(geo, new, i, bkey(geo, node, i));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 485) setval(geo, new, i, bval(geo, node, i));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 486) setkey(geo, node, i, bkey(geo, node, i + fill / 2));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 487) setval(geo, node, i, bval(geo, node, i + fill / 2));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 488) clearpair(geo, node, i + fill / 2);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 489) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 490) if (fill & 1) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 491) setkey(geo, node, i, bkey(geo, node, fill - 1));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 492) setval(geo, node, i, bval(geo, node, fill - 1));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 493) clearpair(geo, node, fill - 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 494) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 495) goto retry;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 496) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 497) BUG_ON(fill >= geo->no_pairs);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 498)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 499) /* shift and insert */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 500) for (i = fill; i > pos; i--) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 501) setkey(geo, node, i, bkey(geo, node, i - 1));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 502) setval(geo, node, i, bval(geo, node, i - 1));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 503) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 504) setkey(geo, node, pos, key);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 505) setval(geo, node, pos, val);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 506)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 507) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 508) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 509)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 510) int btree_insert(struct btree_head *head, struct btree_geo *geo,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 511) unsigned long *key, void *val, gfp_t gfp)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 512) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 513) BUG_ON(!val);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 514) return btree_insert_level(head, geo, key, val, 1, gfp);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 515) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 516) EXPORT_SYMBOL_GPL(btree_insert);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 517)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 518) static void *btree_remove_level(struct btree_head *head, struct btree_geo *geo,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 519) unsigned long *key, int level);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 520) static void merge(struct btree_head *head, struct btree_geo *geo, int level,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 521) unsigned long *left, int lfill,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 522) unsigned long *right, int rfill,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 523) unsigned long *parent, int lpos)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 524) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 525) int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 526)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 527) for (i = 0; i < rfill; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 528) /* Move all keys to the left */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 529) setkey(geo, left, lfill + i, bkey(geo, right, i));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 530) setval(geo, left, lfill + i, bval(geo, right, i));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 531) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 532) /* Exchange left and right child in parent */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 533) setval(geo, parent, lpos, right);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 534) setval(geo, parent, lpos + 1, left);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 535) /* Remove left (formerly right) child from parent */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 536) btree_remove_level(head, geo, bkey(geo, parent, lpos), level + 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 537) mempool_free(right, head->mempool);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 538) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 539)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 540) static void rebalance(struct btree_head *head, struct btree_geo *geo,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 541) unsigned long *key, int level, unsigned long *child, int fill)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 542) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 543) unsigned long *parent, *left = NULL, *right = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 544) int i, no_left, no_right;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 545)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 546) if (fill == 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 547) /* Because we don't steal entries from a neighbour, this case
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 548) * can happen. Parent node contains a single child, this
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 549) * node, so merging with a sibling never happens.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 550) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 551) btree_remove_level(head, geo, key, level + 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 552) mempool_free(child, head->mempool);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 553) return;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 554) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 555)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 556) parent = find_level(head, geo, key, level + 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 557) i = getpos(geo, parent, key);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 558) BUG_ON(bval(geo, parent, i) != child);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 559)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 560) if (i > 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 561) left = bval(geo, parent, i - 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 562) no_left = getfill(geo, left, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 563) if (fill + no_left <= geo->no_pairs) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 564) merge(head, geo, level,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 565) left, no_left,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 566) child, fill,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 567) parent, i - 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 568) return;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 569) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 570) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 571) if (i + 1 < getfill(geo, parent, i)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 572) right = bval(geo, parent, i + 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 573) no_right = getfill(geo, right, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 574) if (fill + no_right <= geo->no_pairs) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 575) merge(head, geo, level,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 576) child, fill,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 577) right, no_right,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 578) parent, i);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 579) return;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 580) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 581) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 582) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 583) * We could also try to steal one entry from the left or right
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 584) * neighbor. By not doing so we changed the invariant from
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 585) * "all nodes are at least half full" to "no two neighboring
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 586) * nodes can be merged". Which means that the average fill of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 587) * all nodes is still half or better.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 588) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 589) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 590)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 591) static void *btree_remove_level(struct btree_head *head, struct btree_geo *geo,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 592) unsigned long *key, int level)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 593) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 594) unsigned long *node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 595) int i, pos, fill;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 596) void *ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 597)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 598) if (level > head->height) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 599) /* we recursed all the way up */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 600) head->height = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 601) head->node = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 602) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 603) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 604)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 605) node = find_level(head, geo, key, level);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 606) pos = getpos(geo, node, key);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 607) fill = getfill(geo, node, pos);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 608) if ((level == 1) && (keycmp(geo, node, pos, key) != 0))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 609) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 610) ret = bval(geo, node, pos);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 611)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 612) /* remove and shift */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 613) for (i = pos; i < fill - 1; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 614) setkey(geo, node, i, bkey(geo, node, i + 1));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 615) setval(geo, node, i, bval(geo, node, i + 1));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 616) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 617) clearpair(geo, node, fill - 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 618)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 619) if (fill - 1 < geo->no_pairs / 2) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 620) if (level < head->height)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 621) rebalance(head, geo, key, level, node, fill - 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 622) else if (fill - 1 == 1)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 623) btree_shrink(head, geo);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 624) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 625)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 626) return ret;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 627) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 628)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 629) void *btree_remove(struct btree_head *head, struct btree_geo *geo,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 630) unsigned long *key)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 631) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 632) if (head->height == 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 633) return NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 634)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 635) return btree_remove_level(head, geo, key, 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 636) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 637) EXPORT_SYMBOL_GPL(btree_remove);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 638)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 639) int btree_merge(struct btree_head *target, struct btree_head *victim,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 640) struct btree_geo *geo, gfp_t gfp)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 641) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 642) unsigned long key[MAX_KEYLEN];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 643) unsigned long dup[MAX_KEYLEN];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 644) void *val;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 645) int err;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 646)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 647) BUG_ON(target == victim);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 648)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 649) if (!(target->node)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 650) /* target is empty, just copy fields over */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 651) target->node = victim->node;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 652) target->height = victim->height;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 653) __btree_init(victim);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 654) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 655) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 656)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 657) /* TODO: This needs some optimizations. Currently we do three tree
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 658) * walks to remove a single object from the victim.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 659) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 660) for (;;) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 661) if (!btree_last(victim, geo, key))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 662) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 663) val = btree_lookup(victim, geo, key);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 664) err = btree_insert(target, geo, key, val, gfp);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 665) if (err)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 666) return err;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 667) /* We must make a copy of the key, as the original will get
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 668) * mangled inside btree_remove. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 669) longcpy(dup, key, geo->keylen);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 670) btree_remove(victim, geo, dup);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 671) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 672) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 673) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 674) EXPORT_SYMBOL_GPL(btree_merge);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 675)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 676) static size_t __btree_for_each(struct btree_head *head, struct btree_geo *geo,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 677) unsigned long *node, unsigned long opaque,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 678) void (*func)(void *elem, unsigned long opaque,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 679) unsigned long *key, size_t index,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 680) void *func2),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 681) void *func2, int reap, int height, size_t count)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 682) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 683) int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 684) unsigned long *child;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 685)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 686) for (i = 0; i < geo->no_pairs; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 687) child = bval(geo, node, i);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 688) if (!child)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 689) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 690) if (height > 1)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 691) count = __btree_for_each(head, geo, child, opaque,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 692) func, func2, reap, height - 1, count);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 693) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 694) func(child, opaque, bkey(geo, node, i), count++,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 695) func2);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 696) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 697) if (reap)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 698) mempool_free(node, head->mempool);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 699) return count;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 700) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 701)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 702) static void empty(void *elem, unsigned long opaque, unsigned long *key,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 703) size_t index, void *func2)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 704) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 705) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 706)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 707) void visitorl(void *elem, unsigned long opaque, unsigned long *key,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 708) size_t index, void *__func)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 709) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 710) visitorl_t func = __func;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 711)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 712) func(elem, opaque, *key, index);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 713) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 714) EXPORT_SYMBOL_GPL(visitorl);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 715)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 716) void visitor32(void *elem, unsigned long opaque, unsigned long *__key,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 717) size_t index, void *__func)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 718) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 719) visitor32_t func = __func;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 720) u32 *key = (void *)__key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 721)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 722) func(elem, opaque, *key, index);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 723) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 724) EXPORT_SYMBOL_GPL(visitor32);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 725)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 726) void visitor64(void *elem, unsigned long opaque, unsigned long *__key,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 727) size_t index, void *__func)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 728) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 729) visitor64_t func = __func;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 730) u64 *key = (void *)__key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 731)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 732) func(elem, opaque, *key, index);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 733) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 734) EXPORT_SYMBOL_GPL(visitor64);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 735)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 736) void visitor128(void *elem, unsigned long opaque, unsigned long *__key,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 737) size_t index, void *__func)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 738) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 739) visitor128_t func = __func;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 740) u64 *key = (void *)__key;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 741)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 742) func(elem, opaque, key[0], key[1], index);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 743) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 744) EXPORT_SYMBOL_GPL(visitor128);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 745)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 746) size_t btree_visitor(struct btree_head *head, struct btree_geo *geo,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 747) unsigned long opaque,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 748) void (*func)(void *elem, unsigned long opaque,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 749) unsigned long *key,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 750) size_t index, void *func2),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 751) void *func2)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 752) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 753) size_t count = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 754)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 755) if (!func2)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 756) func = empty;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 757) if (head->node)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 758) count = __btree_for_each(head, geo, head->node, opaque, func,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 759) func2, 0, head->height, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 760) return count;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 761) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 762) EXPORT_SYMBOL_GPL(btree_visitor);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 763)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 764) size_t btree_grim_visitor(struct btree_head *head, struct btree_geo *geo,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 765) unsigned long opaque,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 766) void (*func)(void *elem, unsigned long opaque,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 767) unsigned long *key,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 768) size_t index, void *func2),
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 769) void *func2)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 770) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 771) size_t count = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 772)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 773) if (!func2)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 774) func = empty;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 775) if (head->node)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 776) count = __btree_for_each(head, geo, head->node, opaque, func,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 777) func2, 1, head->height, 0);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 778) __btree_init(head);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 779) return count;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 780) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 781) EXPORT_SYMBOL_GPL(btree_grim_visitor);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 782)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 783) static int __init btree_module_init(void)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 784) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 785) btree_cachep = kmem_cache_create("btree_node", NODESIZE, 0,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 786) SLAB_HWCACHE_ALIGN, NULL);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 787) return 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 788) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 789)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 790) static void __exit btree_module_exit(void)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 791) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 792) kmem_cache_destroy(btree_cachep);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 793) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 794)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 795) /* If core code starts using btree, initialization should happen even earlier */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 796) module_init(btree_module_init);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 797) module_exit(btree_module_exit);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 798)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 799) MODULE_AUTHOR("Joern Engel <joern@logfs.org>");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 800) MODULE_AUTHOR("Johannes Berg <johannes@sipsolutions.net>");
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 801) MODULE_LICENSE("GPL");
Orange Pi5 kernel
Deprecated Linux kernel 5.10.110 for OrangePi 5/5B/5+ boards
3 Commits
0 Branches
0 Tags