From 7d76ea075c248b2ed64c69a5e5dd4493d943e628 Mon Sep 17 00:00:00 2001 From: Justus Winter <4winter@informatik.uni-hamburg.de> Date: Mon, 16 Mar 2015 11:37:06 +0100 Subject: kern: add radix tree library Import a radix tree library from Richard Braun's librbraun. * Makefile.am (clib_routines): Steal `__ffsdi2'. * Makefrag.am (libkernel_a_SOURCES): Add new files. * kern/rdxtree.c: New file. * kern/rdxtree.h: Likewise. * kern/rdxtree_i.h: Likewise. * kern/startup.c (setup_main): Initialize radix tree library. --- kern/rdxtree_i.h | 66 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 66 insertions(+) create mode 100644 kern/rdxtree_i.h (limited to 'kern/rdxtree_i.h') diff --git a/kern/rdxtree_i.h b/kern/rdxtree_i.h new file mode 100644 index 00000000..1bd1f64a --- /dev/null +++ b/kern/rdxtree_i.h @@ -0,0 +1,66 @@ +/* + * Copyright (c) 2013-2015 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 . + * + * + * Upstream site with license notes : + * http://git.sceen.net/rbraun/librbraun.git/ + */ + +#ifndef _RDXTREE_I_H +#define _RDXTREE_I_H + +/* + * Radix tree. + */ +struct rdxtree { + unsigned int height; + void *root; +}; + +/* + * Radix tree iterator. + * + * The node member refers to the node containing the current pointer, if any. + * The key member refers to the current pointer, and is valid if and only if + * rdxtree_walk() has been called at least once on the iterator. + */ +struct rdxtree_iter { + void *node; + rdxtree_key_t key; +}; + +/* + * Initialize an iterator. + */ +static inline void +rdxtree_iter_init(struct rdxtree_iter *iter) +{ + iter->node = NULL; + iter->key = (rdxtree_key_t)-1; +} + +int rdxtree_insert_common(struct rdxtree *tree, rdxtree_key_t key, + void *ptr, void ***slotp); + +int rdxtree_insert_alloc_common(struct rdxtree *tree, void *ptr, + rdxtree_key_t *keyp, void ***slotp); + +void * rdxtree_lookup_common(const struct rdxtree *tree, rdxtree_key_t key, + int get_slot); + +void * rdxtree_walk(struct rdxtree *tree, struct rdxtree_iter *iter); + +#endif /* _RDXTREE_I_H */ -- cgit v1.2.3