diff options
author | Richard Braun <rbraun@sceen.net> | 2013-06-09 14:34:12 +0200 |
---|---|---|
committer | Richard Braun <rbraun@sceen.net> | 2013-06-09 14:34:12 +0200 |
commit | 281a28a6f311d56cc1d77b8bc89b1d7997ad86d1 (patch) | |
tree | 17477ae5a87730440d4157eb3f9eb9b8d0c81849 | |
parent | 485e24a7afeebb7f0ce933fd3be8c61472902c34 (diff) |
kern/rdxtree: new module
This module implements radix trees, a data structure consisting of a tree
of arrays which can store many items while guaranteeing a small maximum
tree height.
-rw-r--r-- | Makefrag.am | 3 | ||||
-rw-r--r-- | kern/error.h | 1 | ||||
-rw-r--r-- | kern/kernel.c | 2 | ||||
-rw-r--r-- | kern/rdxtree.c | 789 | ||||
-rw-r--r-- | kern/rdxtree.h | 182 | ||||
-rw-r--r-- | kern/rdxtree_i.h | 65 |
6 files changed, 1042 insertions, 0 deletions
diff --git a/Makefrag.am b/Makefrag.am index fdfbf6c5..67086d5c 100644 --- a/Makefrag.am +++ b/Makefrag.am @@ -34,6 +34,9 @@ x15_SOURCES += \ kern/rbtree.c \ kern/rbtree.h \ kern/rbtree_i.h \ + kern/rdxtree.c \ + kern/rdxtree.h \ + kern/rdxtree_i.h \ kern/spinlock.h \ kern/spinlock_i.h \ kern/sprintf.c \ diff --git a/kern/error.h b/kern/error.h index 6cf18b7e..bdb6bda1 100644 --- a/kern/error.h +++ b/kern/error.h @@ -21,5 +21,6 @@ #define ERROR_NOMEM 1 #define ERROR_AGAIN 2 #define ERROR_INVAL 3 +#define ERROR_BUSY 4 #endif /* _KERN_ERROR_H */ diff --git a/kern/kernel.c b/kern/kernel.c index 5508d569..d636d54a 100644 --- a/kern/kernel.c +++ b/kern/kernel.c @@ -20,6 +20,7 @@ #include <kern/kernel.h> #include <kern/llsync.h> #include <kern/panic.h> +#include <kern/rdxtree.h> #include <kern/task.h> #include <kern/thread.h> #include <kern/work.h> @@ -34,6 +35,7 @@ kernel_main(void) cpu_intr_enable(); /* Initialize the kernel */ + rdxtree_setup(); cpumap_setup(); task_setup(); thread_setup(); diff --git a/kern/rdxtree.c b/kern/rdxtree.c new file mode 100644 index 00000000..ef822ac2 --- /dev/null +++ b/kern/rdxtree.c @@ -0,0 +1,789 @@ +/* + * Copyright (c) 2011, 2013 Richard Braun. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +#include <kern/assert.h> +#include <kern/error.h> +#include <kern/kmem.h> +#include <kern/limits.h> +#include <kern/llsync.h> +#include <kern/macros.h> +#include <kern/rdxtree.h> +#include <kern/rdxtree_i.h> +#include <kern/stddef.h> +#include <kern/string.h> +#include <kern/work.h> + +/* + * Mask applied on an entry to obtain its address. + */ +#define RDXTREE_ENTRY_ADDR_MASK (~0x3UL) + +/* + * Global properties used to shape radix trees. + */ +#define RDXTREE_RADIX 6 +#define RDXTREE_RADIX_SIZE (1UL << RDXTREE_RADIX) +#define RDXTREE_RADIX_MASK (RDXTREE_RADIX_SIZE - 1) + +#if RDXTREE_RADIX < 6 +typedef unsigned long rdxtree_bm_t; +#define rdxtree_ffs(x) __builtin_ffsl(x) +#elif RDXTREE_RADIX == 6 /* RDXTREE_RADIX < 6 */ +#ifdef __LP64__ +typedef unsigned long rdxtree_bm_t; +#define rdxtree_ffs(x) __builtin_ffsl(x) +#else /* __LP64__ */ +typedef unsigned long long rdxtree_bm_t; +#define rdxtree_ffs(x) __builtin_ffsll(x) +#endif /* __LP64__ */ +#else /* RDXTREE_RADIX < 6 */ +#error "radix too high" +#endif /* RDXTREE_RADIX < 6 */ + +/* + * Allocation bitmap size in bits. + */ +#define RDXTREE_BM_SIZE (sizeof(rdxtree_bm_t) * CHAR_BIT) + +/* + * Empty/full allocation bitmap words. + */ +#define RDXTREE_BM_EMPTY ((rdxtree_bm_t)0) +#define RDXTREE_BM_FULL \ + ((~(rdxtree_bm_t)0) >> (RDXTREE_BM_SIZE - RDXTREE_RADIX_SIZE)) + +/* + * Radix tree node. + * + * The height of a tree is the number of nodes to traverse until stored + * pointers are reached. A height of 0 means the entries of a node (or the + * tree root) directly point to stored pointers. + * + * The index is valid if and only if the parent isn't NULL. + * + * Concerning the allocation bitmap, a bit is set when the node it denotes, + * or one of its children, can be used to allocate an entry. Conversely, a bit + * is clear when the matching node and all of its children have no free entry. + * + * In order to support safe lockless lookups, in particular during a resize, + * each node includes the height of its subtree, which is invariant during + * the entire node lifetime. Since the tree height does vary, it can't be + * used to determine whether the tree root is a node or a stored pointer. + * This implementation assumes that all nodes and stored pointers are 4-byte + * aligned, and uses the least significant bit of entries to indicate the + * pointer type. This bit is set for internal nodes, and clear for stored + * pointers so that they can be accessed from slots without conversion. + */ +struct rdxtree_node { + union { + struct { + struct rdxtree_node *parent; + unsigned int index; + }; + + /* Deferred destruction when unlinked */ + struct work work; + }; + + unsigned int height; + unsigned int nr_entries; + rdxtree_bm_t alloc_bm; + void *entries[RDXTREE_RADIX_SIZE]; +}; + +static struct kmem_cache rdxtree_node_cache; + +static inline int +rdxtree_check_alignment(const void *ptr) +{ + return ((unsigned long)ptr & ~RDXTREE_ENTRY_ADDR_MASK) == 0; +} + +static inline void * +rdxtree_entry_addr(void *entry) +{ + return (void *)((unsigned long)entry & RDXTREE_ENTRY_ADDR_MASK); +} + +static inline int +rdxtree_entry_is_node(const void *entry) +{ + return ((unsigned long)entry & 1) != 0; +} + +static inline void * +rdxtree_node_to_entry(struct rdxtree_node *node) +{ + return (void *)((unsigned long)node | 1); +} + +static int +rdxtree_node_create(struct rdxtree_node **nodep, unsigned int height) +{ + struct rdxtree_node *node; + + node = kmem_cache_alloc(&rdxtree_node_cache); + + if (node == NULL) + return ERROR_NOMEM; + + assert(rdxtree_check_alignment(node)); + node->parent = NULL; + node->height = height; + node->nr_entries = 0; + node->alloc_bm = RDXTREE_BM_FULL; + memset(node->entries, 0, sizeof(node->entries)); + *nodep = node; + return 0; +} + +static void +rdxtree_node_destroy(struct work *work) +{ + struct rdxtree_node *node; + + node = structof(work, struct rdxtree_node, work); + kmem_cache_free(&rdxtree_node_cache, node); +} + +static void +rdxtree_node_schedule_destruction(struct rdxtree_node *node) +{ + assert(node->parent == NULL); + + work_init(&node->work, rdxtree_node_destroy); + llsync_defer(&node->work); +} + +static inline void +rdxtree_node_link(struct rdxtree_node *node, struct rdxtree_node *parent, + unsigned int index) +{ + node->parent = parent; + node->index = index; +} + +static inline void +rdxtree_node_unlink(struct rdxtree_node *node) +{ + assert(node->parent != NULL); + node->parent = NULL; +} + +static inline int +rdxtree_node_full(struct rdxtree_node *node) +{ + return (node->nr_entries == ARRAY_SIZE(node->entries)); +} + +static inline int +rdxtree_node_empty(struct rdxtree_node *node) +{ + return (node->nr_entries == 0); +} + +static inline void +rdxtree_node_insert(struct rdxtree_node *node, unsigned int index, + void *entry) +{ + assert(index < ARRAY_SIZE(node->entries)); + assert(node->entries[index] == NULL); + + node->nr_entries++; + llsync_assign_ptr(node->entries[index], entry); +} + +static inline void +rdxtree_node_insert_node(struct rdxtree_node *node, unsigned int index, + struct rdxtree_node *child) +{ + rdxtree_node_insert(node, index, rdxtree_node_to_entry(child)); +} + +static inline void +rdxtree_node_remove(struct rdxtree_node *node, unsigned int index) +{ + assert(index < ARRAY_SIZE(node->entries)); + assert(node->entries[index] != NULL); + + node->nr_entries--; + llsync_assign_ptr(node->entries[index], NULL); +} + +static inline void * +rdxtree_node_find(struct rdxtree_node *node, unsigned int index, int get_slot) +{ + void *ptr; + + while (index < ARRAY_SIZE(node->entries)) { + ptr = rdxtree_entry_addr(node->entries[index]); + + if (ptr != NULL) + return get_slot ? (void *)&node->entries[index] : ptr; + + index++; + } + + return NULL; +} + +static inline void +rdxtree_node_bm_set(struct rdxtree_node *node, unsigned int index) +{ + node->alloc_bm |= (rdxtree_bm_t)1 << index; +} + +static inline void +rdxtree_node_bm_clear(struct rdxtree_node *node, unsigned int index) +{ + node->alloc_bm &= ~((rdxtree_bm_t)1 << index); +} + +static inline int +rdxtree_node_bm_is_set(struct rdxtree_node *node, unsigned int index) +{ + return (node->alloc_bm & ((rdxtree_bm_t)1 << index)); +} + +static inline int +rdxtree_node_bm_empty(struct rdxtree_node *node) +{ + return (node->alloc_bm == RDXTREE_BM_EMPTY); +} + +static inline unsigned int +rdxtree_node_bm_first(struct rdxtree_node *node) +{ + return rdxtree_ffs(node->alloc_bm) - 1; +} + +static inline unsigned long +rdxtree_max_key(unsigned int height) +{ + unsigned int shift; + + shift = RDXTREE_RADIX * height; + + if (likely(shift < (sizeof(unsigned long) * CHAR_BIT))) + return (1 << shift) - 1; + else + return ~0UL; +} + +static void +rdxtree_shrink(struct rdxtree *tree) +{ + struct rdxtree_node *node; + void *entry; + + while (tree->height > 0) { + node = rdxtree_entry_addr(tree->root); + + if (node->nr_entries != 1) + break; + + entry = node->entries[0]; + + if (entry == NULL) + break; + + tree->height--; + + if (tree->height > 0) + rdxtree_node_unlink(rdxtree_entry_addr(entry)); + + llsync_assign_ptr(tree->root, entry); + rdxtree_node_schedule_destruction(node); + } +} + +static int +rdxtree_grow(struct rdxtree *tree, unsigned long key) +{ + struct rdxtree_node *root, *node; + unsigned int new_height; + int error; + + new_height = tree->height + 1; + + while (key > rdxtree_max_key(new_height)) + new_height++; + + if (tree->root == NULL) { + tree->height = new_height; + return 0; + } + + root = rdxtree_entry_addr(tree->root); + + do { + error = rdxtree_node_create(&node, tree->height); + + if (error) { + rdxtree_shrink(tree); + return error; + } + + if (tree->height == 0) + rdxtree_node_bm_clear(node, 0); + else { + rdxtree_node_link(root, node, 0); + + if (rdxtree_node_bm_empty(root)) + rdxtree_node_bm_clear(node, 0); + } + + rdxtree_node_insert(node, 0, tree->root); + tree->height++; + llsync_assign_ptr(tree->root, rdxtree_node_to_entry(node)); + root = node; + } while (new_height > tree->height); + + return 0; +} + +static void +rdxtree_cleanup(struct rdxtree *tree, struct rdxtree_node *node) +{ + struct rdxtree_node *prev; + + for (;;) { + if (likely(!rdxtree_node_empty(node))) { + if (unlikely(node->parent == NULL)) + rdxtree_shrink(tree); + + break; + } + + if (node->parent == NULL) { + tree->height = 0; + llsync_assign_ptr(tree->root, NULL); + rdxtree_node_schedule_destruction(node); + break; + } + + prev = node; + node = node->parent; + rdxtree_node_unlink(prev); + rdxtree_node_remove(node, prev->index); + rdxtree_node_schedule_destruction(prev); + } +} + +static void +rdxtree_insert_bm_clear(struct rdxtree_node *node, unsigned int index) +{ + for (;;) { + rdxtree_node_bm_clear(node, index); + + if (!rdxtree_node_full(node) || (node->parent == NULL)) + break; + + index = node->index; + node = node->parent; + } +} + +int +rdxtree_insert_common(struct rdxtree *tree, unsigned long key, void *ptr, + void ***slotp) +{ + struct rdxtree_node *node, *prev; + unsigned int height, shift, index = index; + int error; + + assert(ptr != NULL); + assert(rdxtree_check_alignment(ptr)); + + if (unlikely(key > rdxtree_max_key(tree->height))) { + error = rdxtree_grow(tree, key); + + if (error) + return error; + } + + height = tree->height; + + if (unlikely(height == 0)) { + if (tree->root != NULL) + return ERROR_BUSY; + + llsync_assign_ptr(tree->root, ptr); + + if (slotp != NULL) + *slotp = &tree->root; + + return 0; + } + + node = rdxtree_entry_addr(tree->root); + shift = (height - 1) * RDXTREE_RADIX; + prev = NULL; + + do { + if (node == NULL) { + error = rdxtree_node_create(&node, height - 1); + + if (error) { + if (prev == NULL) + tree->height = 0; + else + rdxtree_cleanup(tree, prev); + + return error; + } + + if (prev == NULL) + llsync_assign_ptr(tree->root, rdxtree_node_to_entry(node)); + else { + rdxtree_node_link(node, prev, index); + rdxtree_node_insert_node(prev, index, node); + } + } + + prev = node; + index = (key >> shift) & RDXTREE_RADIX_MASK; + node = rdxtree_entry_addr(prev->entries[index]); + shift -= RDXTREE_RADIX; + height--; + } while (height > 0); + + if (unlikely(node != NULL)) + return ERROR_BUSY; + + rdxtree_node_insert(prev, index, ptr); + rdxtree_insert_bm_clear(prev, index); + + if (slotp != NULL) + *slotp = &prev->entries[index]; + + return 0; +} + +int +rdxtree_insert_alloc_common(struct rdxtree *tree, void *ptr, + unsigned long *keyp, void ***slotp) +{ + struct rdxtree_node *node, *prev; + unsigned long key; + unsigned int height, shift, index = index; + int error; + + assert(ptr != NULL); + assert(rdxtree_check_alignment(ptr)); + + height = tree->height; + + if (unlikely(height == 0)) { + if (tree->root == NULL) { + llsync_assign_ptr(tree->root, ptr); + *keyp = 0; + + if (slotp != NULL) + *slotp = &tree->root; + + return 0; + } + + goto grow; + } + + node = rdxtree_entry_addr(tree->root); + key = 0; + shift = (height - 1) * RDXTREE_RADIX; + prev = NULL; + + do { + if (node == NULL) { + error = rdxtree_node_create(&node, height - 1); + + if (error) { + rdxtree_cleanup(tree, prev); + return error; + } + + rdxtree_node_link(node, prev, index); + rdxtree_node_insert_node(prev, index, node); + } + + prev = node; + index = rdxtree_node_bm_first(node); + + if (index == (unsigned int)-1) + goto grow; + + key |= ((unsigned long)index << shift); + node = rdxtree_entry_addr(node->entries[index]); + shift -= RDXTREE_RADIX; + height--; + } while (height > 0); + + rdxtree_node_insert(prev, index, ptr); + rdxtree_insert_bm_clear(prev, index); + + if (slotp != NULL) + *slotp = &prev->entries[index]; + + goto out; + +grow: + key = rdxtree_max_key(height) + 1; + error = rdxtree_insert_common(tree, key, ptr, slotp); + + if (error) + return error; + +out: + *keyp = key; + return 0; +} + +static void +rdxtree_remove_bm_set(struct rdxtree_node *node, unsigned int index) +{ + do { + rdxtree_node_bm_set(node, index); + + if (node->parent == NULL) + break; + + index = node->index; + node = node->parent; + } while (!rdxtree_node_bm_is_set(node, index)); +} + +void * +rdxtree_remove(struct rdxtree *tree, unsigned long key) +{ + struct rdxtree_node *node, *prev; + unsigned int height, shift, index; + + height = tree->height; + + if (unlikely(key > rdxtree_max_key(height))) + return NULL; + + node = rdxtree_entry_addr(tree->root); + + if (unlikely(height == 0)) { + llsync_assign_ptr(tree->root, NULL); + return node; + } + + shift = (height - 1) * RDXTREE_RADIX; + + do { + if (node == NULL) + return NULL; + + prev = node; + index = (key >> shift) & RDXTREE_RADIX_MASK; + node = rdxtree_entry_addr(node->entries[index]); + shift -= RDXTREE_RADIX; + height--; + } while (height > 0); + + if (node == NULL) + return NULL; + + rdxtree_node_remove(prev, index); + rdxtree_remove_bm_set(prev, index); + rdxtree_cleanup(tree, prev); + return node; +} + +void * +rdxtree_lookup_common(struct rdxtree *tree, unsigned long key, int get_slot) +{ + struct rdxtree_node *node, *prev; + unsigned int height, shift, index; + void *entry; + + entry = llsync_read_ptr(tree->root); + + if (entry == NULL) { + node = NULL; + height = 0; + } else { + node = rdxtree_entry_addr(entry); + height = rdxtree_entry_is_node(entry) ? node->height + 1 : 0; + } + + if (key > rdxtree_max_key(height)) + return NULL; + + if (height == 0) { + if (node == NULL) + return NULL; + + return get_slot ? (void *)&tree->root : node; + } + + shift = (height - 1) * RDXTREE_RADIX; + + do { + if (node == NULL) + return NULL; + + prev = node; + index = (key >> shift) & RDXTREE_RADIX_MASK; + entry = llsync_read_ptr(node->entries[index]); + node = rdxtree_entry_addr(entry); + shift -= RDXTREE_RADIX; + height--; + } while (height > 0); + + if (node == NULL) + return NULL; + + return get_slot ? (void *)&prev->entries[index] : node; +} + +void * +rdxtree_replace_slot(void **slot, void *ptr) +{ + void *old; + + assert(ptr != NULL); + assert(rdxtree_check_alignment(ptr)); + + old = *slot; + assert(old != NULL); + assert(rdxtree_check_alignment(old)); + llsync_assign_ptr(*slot, ptr); + return old; +} + +static struct rdxtree_node * +rdxtree_walk(struct rdxtree *tree, struct rdxtree_node *node) +{ + struct rdxtree_node *prev, *child; + unsigned int height, index; + + if (node == NULL) { + height = tree->height; + node = rdxtree_entry_addr(tree->root); + + while (height > 1) { + node = rdxtree_node_find(node, 0, 0); + height--; + } + + return node; + } + + height = 0; + + for (;;) { + prev = node->parent; + + if (prev == NULL) + return NULL; + + index = node->index; + child = rdxtree_node_find(prev, index + 1, 0); + + if (child != NULL) + break; + + height++; + node = prev; + } + + node = child; + + while (height > 0) { + node = rdxtree_node_find(node, 0, 0); + height--; + } + + return node; +} + +void * +rdxtree_iter_next(struct rdxtree *tree, struct rdxtree_iter *iter) +{ + unsigned int index; + + if (tree->height == 0) { + if (iter->slot != NULL) + return NULL; + + iter->slot = &tree->root; + return *iter->slot; + } + + if (iter->node != NULL) { + index = iter->slot - ((struct rdxtree_node *)iter->node)->entries; + iter->slot = rdxtree_node_find(iter->node, index + 1, 1); + } + + if (iter->slot == NULL) { + iter->node = rdxtree_walk(tree, iter->node); + + if (iter->node != NULL) + iter->slot = rdxtree_node_find(iter->node, 0, 1); + } + + if (iter->slot == NULL) + return NULL; + + return *iter->slot; +} + +void +rdxtree_remove_all(struct rdxtree *tree) +{ + struct rdxtree_node *node, *parent, *next; + unsigned int height, index; + + height = tree->height; + + if (height == 0) { + if (tree->root != NULL) + llsync_assign_ptr(tree->root, NULL); + + return; + } + + node = rdxtree_walk(tree, NULL); + + do { + next = rdxtree_walk(tree, node); + + parent = node->parent; + + if (parent != NULL) { + index = node->index; + rdxtree_node_remove(parent, index); + rdxtree_remove_bm_set(parent, index); + rdxtree_cleanup(tree, parent); + node->parent = NULL; + } + + rdxtree_node_schedule_destruction(node); + + node = next; + } while (node != NULL); +} + +void +rdxtree_setup(void) +{ + kmem_cache_init(&rdxtree_node_cache, "rdxtree_node", + sizeof(struct rdxtree_node), 0, NULL, NULL, NULL, 0); +} diff --git a/kern/rdxtree.h b/kern/rdxtree.h new file mode 100644 index 00000000..147e3e5e --- /dev/null +++ b/kern/rdxtree.h @@ -0,0 +1,182 @@ +/* + * Copyright (c) 2011, 2013 Richard Braun. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + * + * + * Radix tree. + * + * In addition to the standard insertion operation, this implementation can + * allocate keys for the caller at insertion time. It also allows lookups to + * occur concurrently with updates through the use of lockless synchronization + * (see the llsync module). + */ + +#ifndef _KERN_RDXTREE_H +#define _KERN_RDXTREE_H + +#include <kern/stddef.h> +#include <kern/rdxtree_i.h> + +/* + * Radix tree. + */ +struct rdxtree; + +/* + * Radix tree iterator. + */ +struct rdxtree_iter; + +/* + * Static tree initializer. + */ +#define RDXTREE_INITIALIZER { 0, NULL } + +/* + * Initialize a tree. + */ +static inline void +rdxtree_init(struct rdxtree *tree) +{ + tree->height = 0; + tree->root = NULL; +} + +/* + * Insert a pointer in a tree. + * + * The ptr parameter must not be null. + */ +static inline int +rdxtree_insert(struct rdxtree *tree, unsigned long key, void *ptr) +{ + return rdxtree_insert_common(tree, key, ptr, NULL); +} + +/* + * Insert a pointer in a tree and obtain its slot. + * + * The ptr and slotp parameters must not be null. If successful, the slot of + * the newly inserted pointer is stored at the address pointed to by the slotp + * parameter. + */ +static inline int +rdxtree_insert_slot(struct rdxtree *tree, unsigned long key, void *ptr, + void ***slotp) +{ + return rdxtree_insert_common(tree, key, ptr, slotp); +} + +/* + * Insert a pointer in a tree, for which a new key is allocated. + * + * The ptr and keyp parameters must not be null. The newly allocated key is + * stored at the address pointed to by the keyp parameter. + */ +static inline int +rdxtree_insert_alloc(struct rdxtree *tree, void *ptr, unsigned long *keyp) +{ + return rdxtree_insert_alloc_common(tree, ptr, keyp, NULL); +} + +/* + * Insert a pointer in a tree, for which a new key is allocated, and obtain + * its slot. + * + * The ptr, keyp and slotp parameters must not be null. The newly allocated + * key is stored at the address pointed to by the keyp parameter while the + * slot of the inserted pointer is stored at the address pointed to by the + * slotp parameter. + */ +static inline int +rdxtree_insert_alloc_slot(struct rdxtree *tree, void *ptr, + unsigned long *keyp, void ***slotp) +{ + return rdxtree_insert_alloc_common(tree, ptr, keyp, slotp); +} + +/* + * Remove a pointer from a tree. + * + * The matching pointer is returned if successful, null otherwise. + */ +void * rdxtree_remove(struct rdxtree *tree, unsigned long key); + +/* + * Look up a pointer in a tree. + * + * The matching pointer is returned if successful, null otherwise. + * + * This function can safely proceed while the tree is being concurrently + * updated through the use of lockless synchronization. + */ +static inline void * +rdxtree_lookup(struct rdxtree *tree, unsigned long key) +{ + return rdxtree_lookup_common(tree, key, 0); +} + +/* + * Look up a slot in a tree. + * + * A slot is a pointer to a contained pointer in a tree. It can be used as + * a placeholder for fast replacements to avoid multiple lookups on the same + * key. + * + * A slot for the matching pointer is returned if successful, null otherwise. + * + * Unlike rdxtree_lookup(), the caller must synchronize access to the tree, + * because otherwise, the slot might be made invalid by concurrent updates. + * + * See rdxtree_replace_slot(). + */ +static inline void ** +rdxtree_lookup_slot(struct rdxtree *tree, unsigned long key) +{ + return rdxtree_lookup_common(tree, key, 1); +} + +/* + * Replace a pointer in a tree. + * + * The ptr parameter must not be null. The previous pointer is returned. + * + * See rdxtree_lookup_slot(). + */ +void * rdxtree_replace_slot(void **slot, void *ptr); + +/* + * Forge a loop to process all pointers of a tree. + */ +#define rdxtree_for_each(tree, iter, ptr) \ +for (rdxtree_iter_init(iter), ptr = rdxtree_iter_next(tree, iter); \ + ptr != NULL; \ + ptr = rdxtree_iter_next(tree, iter)) + +/* + * Remove all pointers from a tree. + * + * The common way to destroy a tree and its pointers is to loop over all + * the pointers using rdxtree_for_each(), freeing them, then call this + * function. + */ +void rdxtree_remove_all(struct rdxtree *tree); + +/* + * Initialize the rdxtree module. + */ +void rdxtree_setup(void); + +#endif /* _KERN_RDXTREE_H */ diff --git a/kern/rdxtree_i.h b/kern/rdxtree_i.h new file mode 100644 index 00000000..fd57e78f --- /dev/null +++ b/kern/rdxtree_i.h @@ -0,0 +1,65 @@ +/* + * Copyright (c) 2013 Richard Braun. + * + * This program is free software: you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +#ifndef _KERN_RDXTREE_I_H +#define _KERN_RDXTREE_I_H + +/* + * Radix tree. + */ +struct rdxtree { + unsigned int height; + void *root; +}; + +/* + * Radix tree iterator. + */ +struct rdxtree_iter { + void *node; + void **slot; +}; + +/* + * Initialize an iterator. + */ +static inline void +rdxtree_iter_init(struct rdxtree_iter *iter) +{ + iter->node = NULL; + iter->slot = NULL; +} + +int rdxtree_insert_common(struct rdxtree *tree, unsigned long key, + void *ptr, void ***slotp); + +int rdxtree_insert_alloc_common(struct rdxtree *tree, void *ptr, + unsigned long *keyp, void ***slotp); + +void * rdxtree_lookup_common(struct rdxtree *tree, unsigned long key, + int get_slot); + +/* + * Walk over pointers in a tree. + * + * Move the iterator to the next pointer in the given tree. + * + * The next pointer is returned if there is one, null otherwise. + */ +void * rdxtree_iter_next(struct rdxtree *tree, struct rdxtree_iter *iter); + +#endif /* _KERN_RDXTREE_I_H */ |