// SPDX-License-Identifier: GPL-2.0-only/* * lib/btree.c - Simple In-memory B+Tree * * 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 * * 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 MAX(L1_CACHE_BYTES, 128) struct btree_geo { int keylen; int no_pairs; int no_longs;}; struct btree_geo btree_geo32 = { .keylen = 1, .no_pairs = NODESIZE / sizeof(long) / 2, .no_longs = NODESIZE / sizeof(long) / 2,};EXPORT_SYMBOL_GPL(btree_geo32); #define LONG_PER_U64 (64 / BITS_PER_LONG)struct btree_geo btree_geo64 = { .keylen = LONG_PER_U64, .no_pairs = NODESIZE / sizeof(long) / (1 + LONG_PER_U64), .no_longs = LONG_PER_U64 * (NODESIZE / sizeof(long) / (1 + LONG_PER_U64)),};EXPORT_SYMBOL_GPL(btree_geo64); struct btree_geo btree_geo128 = { .keylen = 2 * LONG_PER_U64, .no_pairs = NODESIZE / sizeof(long) / (1 + 2 * LONG_PER_U64), .no_longs = 2 * LONG_PER_U64 * (NODESIZE / sizeof(long) / (1 + 2 * LONG_PER_U64)),};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){ return kmem_cache_alloc(btree_cachep, gfp_mask);}EXPORT_SYMBOL_GPL(btree_alloc); void btree_free(void *element, void *pool_data){ kmem_cache_free(btree_cachep, element);}EXPORT_SYMBOL_GPL(btree_free); static unsigned long *btree_node_alloc(struct btree_head *head, gfp_t gfp){ unsigned long *node; node = mempool_alloc(head->mempool, gfp); if (likely(node)) memset(node, 0, NODESIZE); return node;} static int longcmp(const unsigned long *l1, const unsigned long *l2, size_t n){ size_t i; for (i = 0; i < n; i++) { if (l1[i] < l2[i]) return -1; if (l1[i] > l2[i]) return 1; } return 0;} static unsigned long *longcpy(unsigned long *dest, const unsigned long *src, size_t n){ size_t i; for (i = 0; i < n; i++) dest[i] = src[i]; return dest;} static unsigned long *longset(unsigned long *s, unsigned long c, size_t n){ size_t i; for (i = 0; i < n; i++) s[i] = c; return s;} static void dec_key(struct btree_geo *geo, unsigned long *key){ unsigned long val; int i; for (i = geo->keylen - 1; i >= 0; i--) { val = key[i]; key[i] = val - 1; if (val) break; }} static unsigned long *bkey(struct btree_geo *geo, unsigned long *node, int n){ return &node[n * geo->keylen];} static void *bval(struct btree_geo *geo, unsigned long *node, int n){ return (void *)node[geo->no_longs + n];} static void setkey(struct btree_geo *geo, unsigned long *node, int n, unsigned long *key){ longcpy(bkey(geo, node, n), key, geo->keylen);} static void setval(struct btree_geo *geo, unsigned long *node, int n, void *val){ node[geo->no_longs + n] = (unsigned long) val;} static void clearpair(struct btree_geo *geo, unsigned long *node, int n){ longset(bkey(geo, node, n), 0, geo->keylen); node[geo->no_longs + n] = 0;} static inline void __btree_init(struct btree_head *head){ head->node = NULL; head->height = 0;} void btree_init_mempool(struct btree_head *head, mempool_t *mempool){ __btree_init(head); head->mempool = mempool;}EXPORT_SYMBOL_GPL(btree_init_mempool); int btree_init(struct btree_head *head){ __btree_init(head); head->mempool = mempool_create(0, btree_alloc, btree_free, NULL); if (!head->mempool) return -ENOMEM; return 0;}EXPORT_SYMBOL_GPL(btree_init); void btree_destroy(struct btree_head *head){ mempool_free(head->node, head->mempool); mempool_destroy(head->mempool); head->mempool = NULL;}EXPORT_SYMBOL_GPL(btree_destroy); void *btree_last(struct btree_head *head, struct btree_geo *geo, unsigned long *key){ int height = head->height; unsigned long *node = head->node; if (height == 0) return NULL; for ( ; height > 1; height--) node = bval(geo, node, 0); longcpy(key, bkey(geo, node, 0), geo->keylen); return bval(geo, node, 0);}EXPORT_SYMBOL_GPL(btree_last); static int keycmp(struct btree_geo *geo, unsigned long *node, int pos, unsigned long *key){ return longcmp(bkey(geo, node, pos), key, geo->keylen);} static int keyzero(struct btree_geo *geo, unsigned long *key){ int i; for (i = 0; i < geo->keylen; i++) if (key[i]) return 0; return 1;} static void *btree_lookup_node(struct btree_head *head, struct btree_geo *geo, unsigned long *key){ int i, height = head->height; unsigned long *node = head->node; if (height == 0) return NULL; 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 NULL; node = bval(geo, node, i); 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; for (i = 0; i < geo->no_pairs; i++) if (keycmp(geo, node, i, key) == 0) return bval(geo, node, i); return NULL;}EXPORT_SYMBOL_GPL(btree_lookup); int btree_update(struct btree_head *head, struct btree_geo *geo, unsigned long *key, void *val){ int i; unsigned long *node; node = btree_lookup_node(head, geo, key); if (!node) return -ENOENT; for (i = 0; i < geo->no_pairs; i++) if (keycmp(geo, node, i, key) == 0) { setval(geo, node, i, val); return 0; } return -ENOENT;}EXPORT_SYMBOL_GPL(btree_update); /* * 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){ int i, height; unsigned long *node, *oldnode; unsigned long *retry_key = NULL, key[MAX_KEYLEN]; if (keyzero(geo, __key)) return NULL; if (head->height == 0) return NULL; longcpy(key, __key, geo->keylen);retry: dec_key(geo, key); node = head->node; for (height = head->height ; height > 1; height--) { for (i = 0; i < geo->no_pairs; i++) if (keycmp(geo, node, i, key) <= 0) break; if (i == geo->no_pairs) goto miss; oldnode = node; node = bval(geo, node, i); if (!node) goto miss; retry_key = bkey(geo, oldnode, i); } if (!node) goto miss; for (i = 0; i < geo->no_pairs; i++) { if (keycmp(geo, node, i, key) <= 0) { if (bval(geo, node, i)) { longcpy(__key, bkey(geo, node, i), geo->keylen); return bval(geo, node, i); } else goto miss; } }miss: if (retry_key) { longcpy(key, retry_key, geo->keylen); retry_key = NULL; goto retry; } return NULL;}EXPORT_SYMBOL_GPL(btree_get_prev); static int getpos(struct btree_geo *geo, unsigned long *node, unsigned long *key){ int i; for (i = 0; i < geo->no_pairs; i++) { if (keycmp(geo, node, i, key) <= 0) break; } return i;} static int getfill(struct btree_geo *geo, unsigned long *node, int start){ int i; for (i = start; i < geo->no_pairs; i++) if (!bval(geo, node, i)) break; return i;} /* * 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){ unsigned long *node = head->node; int i, height; for (height = head->height; height > level; height--) { for (i = 0; i < geo->no_pairs; i++) if (keycmp(geo, node, i, key) <= 0) break; if ((i == geo->no_pairs) || !bval(geo, node, i)) { /* right-most key is too large, update it */ /* FIXME: If the right-most key on higher levels is * always zero, this wouldn't be necessary. */ i--; setkey(geo, node, i, key); } BUG_ON(i < 0); node = bval(geo, node, i); } BUG_ON(!node); return node;} static int btree_grow(struct btree_head *head, struct btree_geo *geo, gfp_t gfp){ unsigned long *node; int fill; node = btree_node_alloc(head, gfp); if (!node) return -ENOMEM; if (head->node) { fill = getfill(geo, head->node, 0); setkey(geo, node, 0, bkey(geo, head->node, fill - 1)); setval(geo, node, 0, head->node); } head->node = node; head->height++; return 0;} static void btree_shrink(struct btree_head *head, struct btree_geo *geo){ unsigned long *node; int fill; if (head->height <= 1) return; node = head->node; fill = getfill(geo, node, 0); BUG_ON(fill > 1); head->node = bval(geo, node, 0); head->height--; mempool_free(node, head->mempool);} static int btree_insert_level(struct btree_head *head, struct btree_geo *geo, unsigned long *key, void *val, int level, gfp_t gfp){ unsigned long *node; int i, pos, fill, err; BUG_ON(!val); if (head->height < level) { err = btree_grow(head, geo, gfp); if (err) return err; } retry: node = find_level(head, geo, key, level); pos = getpos(geo, node, key); fill = getfill(geo, node, pos); /* two identical keys are not allowed */ BUG_ON(pos < fill && keycmp(geo, node, pos, key) == 0); if (fill == geo->no_pairs) { /* need to split node */ unsigned long *new; new = btree_node_alloc(head, gfp); if (!new) return -ENOMEM; err = btree_insert_level(head, geo, bkey(geo, node, fill / 2 - 1), new, level + 1, gfp); if (err) { mempool_free(new, head->mempool); return err; } for (i = 0; i < fill / 2; i++) { setkey(geo, new, i, bkey(geo, node, i)); setval(geo, new, i, bval(geo, node, i)); setkey(geo, node, i, bkey(geo, node, i + fill / 2)); setval(geo, node, i, bval(geo, node, i + fill / 2)); clearpair(geo, node, i + fill / 2); } if (fill & 1) { setkey(geo, node, i, bkey(geo, node, fill - 1)); setval(geo, node, i, bval(geo, node, fill - 1)); clearpair(geo, node, fill - 1); } goto retry; } BUG_ON(fill >= geo->no_pairs); /* shift and insert */ for (i = fill; i > pos; i--) { setkey(geo, node, i, bkey(geo, node, i - 1)); setval(geo, node, i, bval(geo, node, i - 1)); } setkey(geo, node, pos, key); setval(geo, node, pos, val);Lines 1–500 of 795. Load more
// SPDX-License-Identifier: GPL-2.0-only /* * lib/btree.c - Simple In-memory B+Tree * * 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 * * 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 MAX(L1_CACHE_BYTES, 128) struct btree_geo { int keylen; int no_pairs; int no_longs; }; struct btree_geo btree_geo32 = { .keylen = 1, .no_pairs = NODESIZE / sizeof(long) / 2, .no_longs = NODESIZE / sizeof(long) / 2, }; EXPORT_SYMBOL_GPL(btree_geo32); #define LONG_PER_U64 (64 / BITS_PER_LONG) struct btree_geo btree_geo64 = { .keylen = LONG_PER_U64, .no_pairs = NODESIZE / sizeof(long) / (1 + LONG_PER_U64), .no_longs = LONG_PER_U64 * (NODESIZE / sizeof(long) / (1 + LONG_PER_U64)), }; EXPORT_SYMBOL_GPL(btree_geo64); struct btree_geo btree_geo128 = { .keylen = 2 * LONG_PER_U64, .no_pairs = NODESIZE / sizeof(long) / (1 + 2 * LONG_PER_U64), .no_longs = 2 * LONG_PER_U64 * (NODESIZE / sizeof(long) / (1 + 2 * LONG_PER_U64)), }; 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) { return kmem_cache_alloc(btree_cachep, gfp_mask); } EXPORT_SYMBOL_GPL(btree_alloc); void btree_free(void *element, void *pool_data) { kmem_cache_free(btree_cachep, element); } EXPORT_SYMBOL_GPL(btree_free); static unsigned long *btree_node_alloc(struct btree_head *head, gfp_t gfp) { unsigned long *node; node = mempool_alloc(head->mempool, gfp); if (likely(node)) memset(node, 0, NODESIZE); return node; } static int longcmp(const unsigned long *l1, const unsigned long *l2, size_t n) { size_t i; for (i = 0; i < n; i++) { if (l1[i] < l2[i]) return -1; if (l1[i] > l2[i]) return 1; } return 0; } static unsigned long *longcpy(unsigned long *dest, const unsigned long *src, size_t n) { size_t i; for (i = 0; i < n; i++) dest[i] = src[i]; return dest; } static unsigned long *longset(unsigned long *s, unsigned long c, size_t n) { size_t i; for (i = 0; i < n; i++) s[i] = c; return s; } static void dec_key(struct btree_geo *geo, unsigned long *key) { unsigned long val; int i; for (i = geo->keylen - 1; i >= 0; i--) { val = key[i]; key[i] = val - 1; if (val) break; } } static unsigned long *bkey(struct btree_geo *geo, unsigned long *node, int n) { return &node[n * geo->keylen]; } static void *bval(struct btree_geo *geo, unsigned long *node, int n) { return (void *)node[geo->no_longs + n]; } static void setkey(struct btree_geo *geo, unsigned long *node, int n, unsigned long *key) { longcpy(bkey(geo, node, n), key, geo->keylen); } static void setval(struct btree_geo *geo, unsigned long *node, int n, void *val) { node[geo->no_longs + n] = (unsigned long) val; } static void clearpair(struct btree_geo *geo, unsigned long *node, int n) { longset(bkey(geo, node, n), 0, geo->keylen); node[geo->no_longs + n] = 0; } static inline void __btree_init(struct btree_head *head) { head->node = NULL; head->height = 0; } void btree_init_mempool(struct btree_head *head, mempool_t *mempool) { __btree_init(head); head->mempool = mempool; } EXPORT_SYMBOL_GPL(btree_init_mempool); int btree_init(struct btree_head *head) { __btree_init(head); head->mempool = mempool_create(0, btree_alloc, btree_free, NULL); if (!head->mempool) return -ENOMEM; return 0; } EXPORT_SYMBOL_GPL(btree_init); void btree_destroy(struct btree_head *head) { mempool_free(head->node, head->mempool); mempool_destroy(head->mempool); head->mempool = NULL; } EXPORT_SYMBOL_GPL(btree_destroy); void *btree_last(struct btree_head *head, struct btree_geo *geo, unsigned long *key) { int height = head->height; unsigned long *node = head->node; if (height == 0) return NULL; for ( ; height > 1; height--) node = bval(geo, node, 0); longcpy(key, bkey(geo, node, 0), geo->keylen); return bval(geo, node, 0); } EXPORT_SYMBOL_GPL(btree_last); static int keycmp(struct btree_geo *geo, unsigned long *node, int pos, unsigned long *key) { return longcmp(bkey(geo, node, pos), key, geo->keylen); } static int keyzero(struct btree_geo *geo, unsigned long *key) { int i; for (i = 0; i < geo->keylen; i++) if (key[i]) return 0; return 1; } static void *btree_lookup_node(struct btree_head *head, struct btree_geo *geo, unsigned long *key) { int i, height = head->height; unsigned long *node = head->node; if (height == 0) return NULL; 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 NULL; node = bval(geo, node, i); 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; for (i = 0; i < geo->no_pairs; i++) if (keycmp(geo, node, i, key) == 0) return bval(geo, node, i); return NULL; } EXPORT_SYMBOL_GPL(btree_lookup); int btree_update(struct btree_head *head, struct btree_geo *geo, unsigned long *key, void *val) { int i; unsigned long *node; node = btree_lookup_node(head, geo, key); if (!node) return -ENOENT; for (i = 0; i < geo->no_pairs; i++) if (keycmp(geo, node, i, key) == 0) { setval(geo, node, i, val); return 0; } return -ENOENT; } EXPORT_SYMBOL_GPL(btree_update); /* * 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) { int i, height; unsigned long *node, *oldnode; unsigned long *retry_key = NULL, key[MAX_KEYLEN]; if (keyzero(geo, __key)) return NULL; if (head->height == 0) return NULL; longcpy(key, __key, geo->keylen); retry: dec_key(geo, key); node = head->node; for (height = head->height ; height > 1; height--) { for (i = 0; i < geo->no_pairs; i++) if (keycmp(geo, node, i, key) <= 0) break; if (i == geo->no_pairs) goto miss; oldnode = node; node = bval(geo, node, i); if (!node) goto miss; retry_key = bkey(geo, oldnode, i); } if (!node) goto miss; for (i = 0; i < geo->no_pairs; i++) { if (keycmp(geo, node, i, key) <= 0) { if (bval(geo, node, i)) { longcpy(__key, bkey(geo, node, i), geo->keylen); return bval(geo, node, i); } else goto miss; } } miss: if (retry_key) { longcpy(key, retry_key, geo->keylen); retry_key = NULL; goto retry; } return NULL; } EXPORT_SYMBOL_GPL(btree_get_prev); static int getpos(struct btree_geo *geo, unsigned long *node, unsigned long *key) { int i; for (i = 0; i < geo->no_pairs; i++) { if (keycmp(geo, node, i, key) <= 0) break; } return i; } static int getfill(struct btree_geo *geo, unsigned long *node, int start) { int i; for (i = start; i < geo->no_pairs; i++) if (!bval(geo, node, i)) break; return i; } /* * 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) { unsigned long *node = head->node; int i, height; for (height = head->height; height > level; height--) { for (i = 0; i < geo->no_pairs; i++) if (keycmp(geo, node, i, key) <= 0) break; if ((i == geo->no_pairs) || !bval(geo, node, i)) { /* right-most key is too large, update it */ /* FIXME: If the right-most key on higher levels is * always zero, this wouldn't be necessary. */ i--; setkey(geo, node, i, key); } BUG_ON(i < 0); node = bval(geo, node, i); } BUG_ON(!node); return node; } static int btree_grow(struct btree_head *head, struct btree_geo *geo, gfp_t gfp) { unsigned long *node; int fill; node = btree_node_alloc(head, gfp); if (!node) return -ENOMEM; if (head->node) { fill = getfill(geo, head->node, 0); setkey(geo, node, 0, bkey(geo, head->node, fill - 1)); setval(geo, node, 0, head->node); } head->node = node; head->height++; return 0; } static void btree_shrink(struct btree_head *head, struct btree_geo *geo) { unsigned long *node; int fill; if (head->height <= 1) return; node = head->node; fill = getfill(geo, node, 0); BUG_ON(fill > 1); head->node = bval(geo, node, 0); head->height--; mempool_free(node, head->mempool); } static int btree_insert_level(struct btree_head *head, struct btree_geo *geo, unsigned long *key, void *val, int level, gfp_t gfp) { unsigned long *node; int i, pos, fill, err; BUG_ON(!val); if (head->height < level) { err = btree_grow(head, geo, gfp); if (err) return err; } retry: node = find_level(head, geo, key, level); pos = getpos(geo, node, key); fill = getfill(geo, node, pos); /* two identical keys are not allowed */ BUG_ON(pos < fill && keycmp(geo, node, pos, key) == 0); if (fill == geo->no_pairs) { /* need to split node */ unsigned long *new; new = btree_node_alloc(head, gfp); if (!new) return -ENOMEM; err = btree_insert_level(head, geo, bkey(geo, node, fill / 2 - 1), new, level + 1, gfp); if (err) { mempool_free(new, head->mempool); return err; } for (i = 0; i < fill / 2; i++) { setkey(geo, new, i, bkey(geo, node, i)); setval(geo, new, i, bval(geo, node, i)); setkey(geo, node, i, bkey(geo, node, i + fill / 2)); setval(geo, node, i, bval(geo, node, i + fill / 2)); clearpair(geo, node, i + fill / 2); } if (fill & 1) { setkey(geo, node, i, bkey(geo, node, fill - 1)); setval(geo, node, i, bval(geo, node, fill - 1)); clearpair(geo, node, fill - 1); } goto retry; } BUG_ON(fill >= geo->no_pairs); /* shift and insert */ for (i = fill; i > pos; i--) { setkey(geo, node, i, bkey(geo, node, i - 1)); setval(geo, node, i, bval(geo, node, i - 1)); } setkey(geo, node, pos, key); setval(geo, node, pos, val);