diff options
Diffstat (limited to 'lib/btree.c')
| -rw-r--r-- | lib/btree.c | 50 |
1 files changed, 22 insertions, 28 deletions
diff --git a/lib/btree.c b/lib/btree.c index f93a945274af..9c80c0c7bba8 100644 --- a/lib/btree.c +++ b/lib/btree.c @@ -1,12 +1,10 @@ +// SPDX-License-Identifier: GPL-2.0-only /* * lib/btree.c - Simple In-memory B+Tree * - * As should be obvious for Linux kernel code, license is GPLv2 - * - * Copyright (c) 2007-2008 Joern Engel <joern@logfs.org> + * Copyright (c) 2007-2008 Joern Engel <joern@purestorage.com> * Bits and pieces stolen from Peter Zijlstra's code, which is * Copyright 2007, Red Hat Inc. Peter Zijlstra - * GPLv2 * * see http://programming.kicks-ass.net/kernel-patches/vma_lookup/btree.patch * @@ -45,7 +43,6 @@ #include <linux/slab.h> #include <linux/module.h> -#define MAX(a, b) ((a) > (b) ? (a) : (b)) #define NODESIZE MAX(L1_CACHE_BYTES, 128) struct btree_geo { @@ -76,6 +73,8 @@ struct btree_geo btree_geo128 = { }; EXPORT_SYMBOL_GPL(btree_geo128); +#define MAX_KEYLEN (2 * LONG_PER_U64) + static struct kmem_cache *btree_cachep; void *btree_alloc(gfp_t gfp_mask, void *pool_data) @@ -238,7 +237,7 @@ static int keyzero(struct btree_geo *geo, unsigned long *key) return 1; } -void *btree_lookup(struct btree_head *head, struct btree_geo *geo, +static void *btree_lookup_node(struct btree_head *head, struct btree_geo *geo, unsigned long *key) { int i, height = head->height; @@ -257,7 +256,16 @@ void *btree_lookup(struct btree_head *head, struct btree_geo *geo, if (!node) return NULL; } + return node; +} + +void *btree_lookup(struct btree_head *head, struct btree_geo *geo, + unsigned long *key) +{ + int i; + unsigned long *node; + node = btree_lookup_node(head, geo, key); if (!node) return NULL; @@ -271,23 +279,10 @@ EXPORT_SYMBOL_GPL(btree_lookup); int btree_update(struct btree_head *head, struct btree_geo *geo, unsigned long *key, void *val) { - int i, height = head->height; - unsigned long *node = head->node; - - if (height == 0) - return -ENOENT; - - for ( ; height > 1; height--) { - for (i = 0; i < geo->no_pairs; i++) - if (keycmp(geo, node, i, key) <= 0) - break; - if (i == geo->no_pairs) - return -ENOENT; - node = bval(geo, node, i); - if (!node) - return -ENOENT; - } + int i; + unsigned long *node; + node = btree_lookup_node(head, geo, key); if (!node) return -ENOENT; @@ -313,7 +308,7 @@ void *btree_get_prev(struct btree_head *head, struct btree_geo *geo, { int i, height; unsigned long *node, *oldnode; - unsigned long *retry_key = NULL, key[geo->keylen]; + unsigned long *retry_key = NULL, key[MAX_KEYLEN]; if (keyzero(geo, __key)) return NULL; @@ -639,8 +634,8 @@ EXPORT_SYMBOL_GPL(btree_remove); int btree_merge(struct btree_head *target, struct btree_head *victim, struct btree_geo *geo, gfp_t gfp) { - unsigned long key[geo->keylen]; - unsigned long dup[geo->keylen]; + unsigned long key[MAX_KEYLEN]; + unsigned long dup[MAX_KEYLEN]; void *val; int err; @@ -658,9 +653,9 @@ int btree_merge(struct btree_head *target, struct btree_head *victim, * walks to remove a single object from the victim. */ for (;;) { - if (!btree_last(victim, geo, key)) + val = btree_last(victim, geo, key); + if (!val) break; - val = btree_lookup(victim, geo, key); err = btree_insert(target, geo, key, val, gfp); if (err) return err; @@ -798,4 +793,3 @@ module_exit(btree_module_exit); MODULE_AUTHOR("Joern Engel <joern@logfs.org>"); MODULE_AUTHOR("Johannes Berg <johannes@sipsolutions.net>"); -MODULE_LICENSE("GPL"); |