![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to rdxtree.h CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [GnuMach] / Gnu-Mach / kern|
Return to rdxtree.h CVS log | Up to [GnuMach] / Gnu-Mach / kern |
1.1 root 1: /*
2: * Copyright (c) 2011-2015 Richard Braun.
3: * All rights reserved.
4: *
5: * Redistribution and use in source and binary forms, with or without
6: * modification, are permitted provided that the following conditions
7: * are met:
8: * 1. Redistributions of source code must retain the above copyright
9: * notice, this list of conditions and the following disclaimer.
10: * 2. Redistributions in binary form must reproduce the above copyright
11: * notice, this list of conditions and the following disclaimer in the
12: * documentation and/or other materials provided with the distribution.
13: *
14: * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
15: * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
16: * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
17: * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
18: * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
19: * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
20: * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
21: * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
23: * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24: *
25: *
26: * Radix tree.
27: *
28: * In addition to the standard insertion operation, this implementation
29: * can allocate keys for the caller at insertion time.
30: *
31: * Upstream site with license notes :
32: * http://git.sceen.net/rbraun/librbraun.git/
33: */
34:
35: #ifndef _RDXTREE_H
36: #define _RDXTREE_H
37:
38: #include <stddef.h>
39: #include <sys/types.h>
40:
41: /*
42: * Initialize the node cache.
43: */
44: void rdxtree_cache_init(void);
45:
46: /*
47: * This macro selects between 32 or 64-bits (the default) keys.
48: */
49: #if 0
50: #define RDXTREE_KEY_32
51: #endif
52:
53: #ifdef RDXTREE_KEY_32
54: typedef uint32_t rdxtree_key_t;
55: #else /* RDXTREE_KEY_32 */
56: typedef uint64_t rdxtree_key_t;
57: #endif /* RDXTREE_KEY_32 */
58:
59: /*
60: * Radix tree.
61: */
62: struct rdxtree;
63:
64: /*
65: * Radix tree iterator.
66: */
67: struct rdxtree_iter;
68:
69: /*
70: * Static tree initializer.
71: */
72: #define RDXTREE_INITIALIZER { 0, NULL }
73:
74: #include "rdxtree_i.h"
75:
76: /*
77: * Initialize a tree.
78: */
79: static inline void
80: rdxtree_init(struct rdxtree *tree)
81: {
82: tree->height = 0;
83: tree->root = NULL;
84: }
85:
86: /*
87: * Insert a pointer in a tree.
88: *
89: * The ptr parameter must not be NULL.
90: */
91: static inline int
92: rdxtree_insert(struct rdxtree *tree, rdxtree_key_t key, void *ptr)
93: {
94: return rdxtree_insert_common(tree, key, ptr, NULL);
95: }
96:
97: /*
98: * Insert a pointer in a tree and obtain its slot.
99: *
100: * The ptr and slotp parameters must not be NULL. If successful, the slot of
101: * the newly inserted pointer is stored at the address pointed to by the slotp
102: * parameter.
103: */
104: static inline int
105: rdxtree_insert_slot(struct rdxtree *tree, rdxtree_key_t key,
106: void *ptr, void ***slotp)
107: {
108: return rdxtree_insert_common(tree, key, ptr, slotp);
109: }
110:
111: /*
112: * Insert a pointer in a tree, for which a new key is allocated.
113: *
114: * The ptr and keyp parameters must not be NULL. The newly allocated key is
115: * stored at the address pointed to by the keyp parameter.
116: */
117: static inline int
118: rdxtree_insert_alloc(struct rdxtree *tree, void *ptr, rdxtree_key_t *keyp)
119: {
120: return rdxtree_insert_alloc_common(tree, ptr, keyp, NULL);
121: }
122:
123: /*
124: * Insert a pointer in a tree, for which a new key is allocated, and obtain
125: * its slot.
126: *
127: * The ptr, keyp and slotp parameters must not be NULL. The newly allocated
128: * key is stored at the address pointed to by the keyp parameter while the
129: * slot of the inserted pointer is stored at the address pointed to by the
130: * slotp parameter.
131: */
132: static inline int
133: rdxtree_insert_alloc_slot(struct rdxtree *tree, void *ptr,
134: rdxtree_key_t *keyp, void ***slotp)
135: {
136: return rdxtree_insert_alloc_common(tree, ptr, keyp, slotp);
137: }
138:
139: /*
140: * Remove a pointer from a tree.
141: *
142: * The matching pointer is returned if successful, NULL otherwise.
143: */
144: void * rdxtree_remove(struct rdxtree *tree, rdxtree_key_t key);
145:
146: /*
147: * Look up a pointer in a tree.
148: *
149: * The matching pointer is returned if successful, NULL otherwise.
150: */
151: static inline void *
152: rdxtree_lookup(const struct rdxtree *tree, rdxtree_key_t key)
153: {
154: return rdxtree_lookup_common(tree, key, 0);
155: }
156:
157: /*
158: * Look up a slot in a tree.
159: *
160: * A slot is a pointer to a stored pointer in a tree. It can be used as
161: * a placeholder for fast replacements to avoid multiple lookups on the same
162: * key.
163: *
164: * A slot for the matching pointer is returned if successful, NULL otherwise.
165: *
166: * See rdxtree_replace_slot().
167: */
168: static inline void **
169: rdxtree_lookup_slot(const struct rdxtree *tree, rdxtree_key_t key)
170: {
171: return rdxtree_lookup_common(tree, key, 1);
172: }
173:
174: /*
175: * Replace a pointer in a tree.
176: *
177: * The ptr parameter must not be NULL. The previous pointer is returned.
178: *
179: * See rdxtree_lookup_slot().
180: */
181: void * rdxtree_replace_slot(void **slot, void *ptr);
182:
183: /*
184: * Forge a loop to process all pointers of a tree.
185: */
186: #define rdxtree_for_each(tree, iter, ptr) \
187: for (rdxtree_iter_init(iter), ptr = rdxtree_walk(tree, iter); \
188: ptr != NULL; \
189: ptr = rdxtree_walk(tree, iter))
190:
191: /*
192: * Return the key of the current pointer from an iterator.
193: */
194: static inline rdxtree_key_t
195: rdxtree_iter_key(const struct rdxtree_iter *iter)
196: {
197: return iter->key;
198: }
199:
200: /*
201: * Remove all pointers from a tree.
202: *
203: * The common way to destroy a tree and its pointers is to loop over all
204: * the pointers using rdxtree_for_each(), freeing them, then call this
205: * function.
206: */
207: void rdxtree_remove_all(struct rdxtree *tree);
208:
209: #endif /* _RDXTREE_H */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.