| @@ -1,1466 +1,1679 @@ | | | @@ -1,1466 +1,1679 @@ |
1 | /* $NetBSD: radixtree.c,v 1.17 2011/11/02 13:49:43 yamt Exp $ */ | | 1 | /* $NetBSD: radixtree.c,v 1.18 2019/12/05 18:32:25 ad Exp $ */ |
2 | | | 2 | |
3 | /*- | | 3 | /*- |
4 | * Copyright (c)2011 YAMAMOTO Takashi, | | 4 | * Copyright (c)2011,2012,2013 YAMAMOTO Takashi, |
5 | * All rights reserved. | | 5 | * All rights reserved. |
6 | * | | 6 | * |
7 | * Redistribution and use in source and binary forms, with or without | | 7 | * Redistribution and use in source and binary forms, with or without |
8 | * modification, are permitted provided that the following conditions | | 8 | * modification, are permitted provided that the following conditions |
9 | * are met: | | 9 | * are met: |
10 | * 1. Redistributions of source code must retain the above copyright | | 10 | * 1. Redistributions of source code must retain the above copyright |
11 | * notice, this list of conditions and the following disclaimer. | | 11 | * notice, this list of conditions and the following disclaimer. |
12 | * 2. Redistributions in binary form must reproduce the above copyright | | 12 | * 2. Redistributions in binary form must reproduce the above copyright |
13 | * notice, this list of conditions and the following disclaimer in the | | 13 | * notice, this list of conditions and the following disclaimer in the |
14 | * documentation and/or other materials provided with the distribution. | | 14 | * documentation and/or other materials provided with the distribution. |
15 | * | | 15 | * |
16 | * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND | | 16 | * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND |
17 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | | 17 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
18 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | | 18 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
19 | * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE | | 19 | * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE |
20 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | | 20 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL |
21 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS | | 21 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS |
22 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | | 22 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
23 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | | 23 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT |
24 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY | | 24 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY |
25 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF | | 25 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF |
26 | * SUCH DAMAGE. | | 26 | * SUCH DAMAGE. |
27 | */ | | 27 | */ |
28 | | | 28 | |
29 | /* | | 29 | /* |
30 | * radixtree.c | | 30 | * radixtree.c |
31 | * | | 31 | * |
32 | * this is an implementation of radix tree, whose keys are uint64_t and leafs | | 32 | * Overview: |
| | | 33 | * |
| | | 34 | * This is an implementation of radix tree, whose keys are uint64_t and leafs |
33 | * are user provided pointers. | | 35 | * are user provided pointers. |
34 | * | | 36 | * |
35 | * leaf nodes are just void * and this implementation doesn't care about | | 37 | * Leaf nodes are just void * and this implementation doesn't care about |
36 | * what they actually point to. however, this implementation has an assumption | | 38 | * what they actually point to. However, this implementation has an assumption |
37 | * about their alignment. specifically, this implementation assumes that their | | 39 | * about their alignment. Specifically, this implementation assumes that their |
38 | * 2 LSBs are zero and uses them internally. | | 40 | * 2 LSBs are always zero and uses them for internal accounting. |
39 | * | | 41 | * |
40 | * intermediate nodes are automatically allocated and freed internally and | | 42 | * Intermediate nodes and memory allocation: |
41 | * basically users don't need to care about them. only radix_tree_insert_node | | 43 | * |
42 | * function can allocate memory for intermediate nodes and thus can fail for | | 44 | * Intermediate nodes are automatically allocated and freed internally and |
43 | * ENOMEM. | | 45 | * basically users don't need to care about them. The allocation is done via |
44 | * | | 46 | * pool_cache_get(9) for _KERNEL, malloc(3) for userland, and alloc() for |
45 | * efficiency: | | 47 | * _STANDALONE environment. Only radix_tree_insert_node function can allocate |
46 | * it's designed to work efficiently with dense index distribution. | | 48 | * memory for intermediate nodes and thus can fail for ENOMEM. |
47 | * the memory consumption (number of necessary intermediate nodes) | | 49 | * |
48 | * heavily depends on index distribution. basically, more dense index | | 50 | * Memory Efficiency: |
49 | * distribution consumes less nodes per item. | | 51 | * |
50 | * approximately, | | 52 | * It's designed to work efficiently with dense index distribution. |
51 | * the best case: about RADIX_TREE_PTR_PER_NODE items per intermediate node. | | 53 | * The memory consumption (number of necessary intermediate nodes) heavily |
52 | * the worst case: RADIX_TREE_MAX_HEIGHT intermediate nodes per item. | | 54 | * depends on the index distribution. Basically, more dense index distribution |
| | | 55 | * consumes less nodes per item. Approximately, |
| | | 56 | * |
| | | 57 | * - the best case: about RADIX_TREE_PTR_PER_NODE items per intermediate node. |
| | | 58 | * it would look like the following. |
| | | 59 | * |
| | | 60 | * root (t_height=1) |
| | | 61 | * | |
| | | 62 | * v |
| | | 63 | * [ | | | ] (intermediate node. RADIX_TREE_PTR_PER_NODE=4 in this fig) |
| | | 64 | * | | | | |
| | | 65 | * v v v v |
| | | 66 | * p p p p (items) |
| | | 67 | * |
| | | 68 | * - the worst case: RADIX_TREE_MAX_HEIGHT intermediate nodes per item. |
| | | 69 | * it would look like the following if RADIX_TREE_MAX_HEIGHT=3. |
| | | 70 | * |
| | | 71 | * root (t_height=3) |
| | | 72 | * | |
| | | 73 | * v |
| | | 74 | * [ | | | ] |
| | | 75 | * | |
| | | 76 | * v |
| | | 77 | * [ | | | ] |
| | | 78 | * | |
| | | 79 | * v |
| | | 80 | * [ | | | ] |
| | | 81 | * | |
| | | 82 | * v |
| | | 83 | * p |
| | | 84 | * |
| | | 85 | * The height of tree (t_height) is dynamic. It's smaller if only small |
| | | 86 | * index values are used. As an extreme case, if only index 0 is used, |
| | | 87 | * the corresponding value is directly stored in the root of the tree |
| | | 88 | * (struct radix_tree) without allocating any intermediate nodes. In that |
| | | 89 | * case, t_height=0. |
| | | 90 | * |
| | | 91 | * Gang lookup: |
53 | * | | 92 | * |
54 | * gang lookup: | | 93 | * This implementation provides a way to scan many nodes quickly via |
55 | * this implementation provides a way to lookup many nodes quickly via | | | |
56 | * radix_tree_gang_lookup_node function and its varients. | | 94 | * radix_tree_gang_lookup_node function and its varients. |
57 | * | | 95 | * |
58 | * tags: | | 96 | * Tags: |
59 | * this implementation provides tagging functionality to allow quick | | 97 | * |
60 | * scanning of a subset of leaf nodes. leaf nodes are untagged when | | 98 | * This implementation provides tagging functionality, which allows quick |
61 | * inserted into the tree and can be tagged by radix_tree_set_tag function. | | 99 | * scanning of a subset of leaf nodes. Leaf nodes are untagged when inserted |
62 | * radix_tree_gang_lookup_tagged_node function and its variants returns | | 100 | * into the tree and can be tagged by radix_tree_set_tag function. |
63 | * only leaf nodes with the given tag. to reduce amount of nodes to visit for | | 101 | * radix_tree_gang_lookup_tagged_node function and its variants returns only |
| | | 102 | * leaf nodes with the given tag. To reduce amount of nodes to visit for |
64 | * these functions, this implementation keeps tagging information in internal | | 103 | * these functions, this implementation keeps tagging information in internal |
65 | * intermediate nodes and quickly skips uninterested parts of a tree. | | 104 | * intermediate nodes and quickly skips uninterested parts of a tree. |
| | | 105 | * |
| | | 106 | * A tree has RADIX_TREE_TAG_ID_MAX independent tag spaces, each of which are |
| | | 107 | * identified by an zero-origin numbers, tagid. For the current implementation, |
| | | 108 | * RADIX_TREE_TAG_ID_MAX is 2. A set of tags is described as a bitmask tagmask, |
| | | 109 | * which is a bitwise OR of (1 << tagid). |
66 | */ | | 110 | */ |
67 | | | 111 | |
68 | #include <sys/cdefs.h> | | 112 | #include <sys/cdefs.h> |
69 | | | 113 | |
70 | #if defined(_KERNEL) || defined(_STANDALONE) | | 114 | #if defined(_KERNEL) || defined(_STANDALONE) |
71 | __KERNEL_RCSID(0, "$NetBSD: radixtree.c,v 1.17 2011/11/02 13:49:43 yamt Exp $"); | | 115 | __KERNEL_RCSID(0, "$NetBSD: radixtree.c,v 1.18 2019/12/05 18:32:25 ad Exp $"); |
72 | #include <sys/param.h> | | 116 | #include <sys/param.h> |
73 | #include <sys/errno.h> | | 117 | #include <sys/errno.h> |
74 | #include <sys/pool.h> | | 118 | #include <sys/pool.h> |
75 | #include <sys/radixtree.h> | | 119 | #include <sys/radixtree.h> |
76 | #include <lib/libkern/libkern.h> | | 120 | #include <lib/libkern/libkern.h> |
77 | #if defined(_STANDALONE) | | 121 | #if defined(_STANDALONE) |
78 | #include <lib/libsa/stand.h> | | 122 | #include <lib/libsa/stand.h> |
79 | #endif /* defined(_STANDALONE) */ | | 123 | #endif /* defined(_STANDALONE) */ |
80 | #else /* defined(_KERNEL) || defined(_STANDALONE) */ | | 124 | #else /* defined(_KERNEL) || defined(_STANDALONE) */ |
81 | __RCSID("$NetBSD: radixtree.c,v 1.17 2011/11/02 13:49:43 yamt Exp $"); | | 125 | __RCSID("$NetBSD: radixtree.c,v 1.18 2019/12/05 18:32:25 ad Exp $"); |
82 | #include <assert.h> | | 126 | #include <assert.h> |
83 | #include <errno.h> | | 127 | #include <errno.h> |
84 | #include <stdbool.h> | | 128 | #include <stdbool.h> |
85 | #include <stdlib.h> | | 129 | #include <stdlib.h> |
86 | #include <string.h> | | 130 | #include <string.h> |
87 | #if 1 | | 131 | #if 1 |
88 | #define KASSERT assert | | 132 | #define KASSERT assert |
89 | #else | | 133 | #else |
90 | #define KASSERT(a) /* nothing */ | | 134 | #define KASSERT(a) /* nothing */ |
91 | #endif | | 135 | #endif |
92 | #endif /* defined(_KERNEL) || defined(_STANDALONE) */ | | 136 | #endif /* defined(_KERNEL) || defined(_STANDALONE) */ |
93 | | | 137 | |
94 | #include <sys/radixtree.h> | | 138 | #include <sys/radixtree.h> |
95 | | | 139 | |
96 | #define RADIX_TREE_BITS_PER_HEIGHT 4 /* XXX tune */ | | 140 | #define RADIX_TREE_BITS_PER_HEIGHT 4 /* XXX tune */ |
97 | #define RADIX_TREE_PTR_PER_NODE (1 << RADIX_TREE_BITS_PER_HEIGHT) | | 141 | #define RADIX_TREE_PTR_PER_NODE (1 << RADIX_TREE_BITS_PER_HEIGHT) |
98 | #define RADIX_TREE_MAX_HEIGHT (64 / RADIX_TREE_BITS_PER_HEIGHT) | | 142 | #define RADIX_TREE_MAX_HEIGHT (64 / RADIX_TREE_BITS_PER_HEIGHT) |
99 | #define RADIX_TREE_INVALID_HEIGHT (RADIX_TREE_MAX_HEIGHT + 1) | | 143 | #define RADIX_TREE_INVALID_HEIGHT (RADIX_TREE_MAX_HEIGHT + 1) |
100 | __CTASSERT((64 % RADIX_TREE_BITS_PER_HEIGHT) == 0); | | 144 | __CTASSERT((64 % RADIX_TREE_BITS_PER_HEIGHT) == 0); |
101 | | | 145 | |
102 | __CTASSERT(((1 << RADIX_TREE_TAG_ID_MAX) & (sizeof(int) - 1)) == 0); | | 146 | __CTASSERT(((1 << RADIX_TREE_TAG_ID_MAX) & (sizeof(int) - 1)) == 0); |
103 | #define RADIX_TREE_TAG_MASK ((1 << RADIX_TREE_TAG_ID_MAX) - 1) | | 147 | #define RADIX_TREE_TAG_MASK ((1 << RADIX_TREE_TAG_ID_MAX) - 1) |
104 | | | 148 | |
105 | static inline void * | | 149 | static inline void * |
106 | entry_ptr(void *p) | | 150 | entry_ptr(void *p) |
107 | { | | 151 | { |
108 | | | 152 | |
109 | return (void *)((uintptr_t)p & ~RADIX_TREE_TAG_MASK); | | 153 | return (void *)((uintptr_t)p & ~RADIX_TREE_TAG_MASK); |
110 | } | | 154 | } |
111 | | | 155 | |
112 | static inline unsigned int | | 156 | static inline unsigned int |
113 | entry_tagmask(void *p) | | 157 | entry_tagmask(void *p) |
114 | { | | 158 | { |
115 | | | 159 | |
116 | return (uintptr_t)p & RADIX_TREE_TAG_MASK; | | 160 | return (uintptr_t)p & RADIX_TREE_TAG_MASK; |
117 | } | | 161 | } |
118 | | | 162 | |
119 | static inline void * | | 163 | static inline void * |
120 | entry_compose(void *p, unsigned int tagmask) | | 164 | entry_compose(void *p, unsigned int tagmask) |
121 | { | | 165 | { |
122 | | | 166 | |
123 | return (void *)((uintptr_t)p | tagmask); | | 167 | return (void *)((uintptr_t)p | tagmask); |
124 | } | | 168 | } |
125 | | | 169 | |
126 | static inline bool | | 170 | static inline bool |
127 | entry_match_p(void *p, unsigned int tagmask) | | 171 | entry_match_p(void *p, unsigned int tagmask) |
128 | { | | 172 | { |
129 | | | 173 | |
130 | KASSERT(entry_ptr(p) != NULL || entry_tagmask(p) == 0); | | 174 | KASSERT(entry_ptr(p) != NULL || entry_tagmask(p) == 0); |
131 | if (p == NULL) { | | 175 | if (p == NULL) { |
132 | return false; | | 176 | return false; |
133 | } | | 177 | } |
134 | if (tagmask == 0) { | | 178 | if (tagmask == 0) { |
135 | return true; | | 179 | return true; |
136 | } | | 180 | } |
137 | return (entry_tagmask(p) & tagmask) != 0; | | 181 | return (entry_tagmask(p) & tagmask) != 0; |
138 | } | | 182 | } |
139 | | | 183 | |
140 | static inline unsigned int | | | |
141 | tagid_to_mask(radix_tree_tagid_t id) | | | |
142 | { | | | |
143 | | | | |
144 | KASSERT(id >= 0); | | | |
145 | KASSERT(id < RADIX_TREE_TAG_ID_MAX); | | | |
146 | return 1U << id; | | | |
147 | } | | | |
148 | | | | |
149 | /* | | 184 | /* |
150 | * radix_tree_node: an intermediate node | | 185 | * radix_tree_node: an intermediate node |
151 | * | | 186 | * |
152 | * we don't care the type of leaf nodes. they are just void *. | | 187 | * we don't care the type of leaf nodes. they are just void *. |
153 | */ | | 188 | */ |
154 | | | 189 | |
155 | struct radix_tree_node { | | 190 | struct radix_tree_node { |
156 | void *n_ptrs[RADIX_TREE_PTR_PER_NODE]; | | 191 | void *n_ptrs[RADIX_TREE_PTR_PER_NODE]; |
157 | unsigned int n_nptrs; /* # of non-NULL pointers in n_ptrs */ | | 192 | unsigned int n_nptrs; /* # of non-NULL pointers in n_ptrs */ |
158 | }; | | 193 | }; |
159 | | | 194 | |
160 | /* | | 195 | /* |
161 | * any_children_tagmask: | | 196 | * any_children_tagmask: |
162 | * | | 197 | * |
163 | * return OR'ed tagmask of the given node's children. | | 198 | * return OR'ed tagmask of the given node's children. |
164 | */ | | 199 | */ |
165 | | | 200 | |
166 | static unsigned int | | 201 | static unsigned int |
167 | any_children_tagmask(const struct radix_tree_node *n) | | 202 | any_children_tagmask(const struct radix_tree_node *n) |
168 | { | | 203 | { |
169 | unsigned int mask; | | 204 | unsigned int mask; |
170 | int i; | | 205 | int i; |
171 | | | 206 | |
172 | mask = 0; | | 207 | mask = 0; |
173 | for (i = 0; i < RADIX_TREE_PTR_PER_NODE; i++) { | | 208 | for (i = 0; i < RADIX_TREE_PTR_PER_NODE; i++) { |
174 | mask |= (unsigned int)(uintptr_t)n->n_ptrs[i]; | | 209 | mask |= (unsigned int)(uintptr_t)n->n_ptrs[i]; |
175 | } | | 210 | } |
176 | return mask & RADIX_TREE_TAG_MASK; | | 211 | return mask & RADIX_TREE_TAG_MASK; |
177 | } | | 212 | } |
178 | | | 213 | |
179 | /* | | 214 | /* |
180 | * p_refs[0].pptr == &t->t_root | | 215 | * p_refs[0].pptr == &t->t_root |
181 | * : | | 216 | * : |
182 | * p_refs[n].pptr == &(*p_refs[n-1])->n_ptrs[x] | | 217 | * p_refs[n].pptr == &(*p_refs[n-1])->n_ptrs[x] |
183 | * : | | 218 | * : |
184 | * : | | 219 | * : |
185 | * p_refs[t->t_height].pptr == &leaf_pointer | | 220 | * p_refs[t->t_height].pptr == &leaf_pointer |
186 | */ | | 221 | */ |
187 | | | 222 | |
188 | struct radix_tree_path { | | 223 | struct radix_tree_path { |
189 | struct radix_tree_node_ref { | | 224 | struct radix_tree_node_ref { |
190 | void **pptr; | | 225 | void **pptr; |
191 | } p_refs[RADIX_TREE_MAX_HEIGHT + 1]; /* +1 for the root ptr */ | | 226 | } p_refs[RADIX_TREE_MAX_HEIGHT + 1]; /* +1 for the root ptr */ |
192 | /* | | 227 | /* |
193 | * p_lastidx is either the index of the last valid element of p_refs[] | | 228 | * p_lastidx is either the index of the last valid element of p_refs[] |
194 | * or RADIX_TREE_INVALID_HEIGHT. | | 229 | * or RADIX_TREE_INVALID_HEIGHT. |
195 | * RADIX_TREE_INVALID_HEIGHT means that radix_tree_lookup_ptr found | | 230 | * RADIX_TREE_INVALID_HEIGHT means that radix_tree_lookup_ptr found |
196 | * that the height of the tree is not enough to cover the given index. | | 231 | * that the height of the tree is not enough to cover the given index. |
197 | */ | | 232 | */ |
198 | unsigned int p_lastidx; | | 233 | unsigned int p_lastidx; |
199 | }; | | 234 | }; |
200 | | | 235 | |
201 | static inline void ** | | 236 | static inline void ** |
202 | path_pptr(const struct radix_tree *t, const struct radix_tree_path *p, | | 237 | path_pptr(const struct radix_tree *t, const struct radix_tree_path *p, |
203 | unsigned int height) | | 238 | unsigned int height) |
204 | { | | 239 | { |
205 | | | 240 | |
206 | KASSERT(height <= t->t_height); | | 241 | KASSERT(height <= t->t_height); |
207 | return p->p_refs[height].pptr; | | 242 | return p->p_refs[height].pptr; |
208 | } | | 243 | } |
209 | | | 244 | |
210 | static inline struct radix_tree_node * | | 245 | static inline struct radix_tree_node * |
211 | path_node(const struct radix_tree * t, const struct radix_tree_path *p, | | 246 | path_node(const struct radix_tree * t, const struct radix_tree_path *p, |
212 | unsigned int height) | | 247 | unsigned int height) |
213 | { | | 248 | { |
214 | | | 249 | |
215 | KASSERT(height <= t->t_height); | | 250 | KASSERT(height <= t->t_height); |
216 | return entry_ptr(*path_pptr(t, p, height)); | | 251 | return entry_ptr(*path_pptr(t, p, height)); |
217 | } | | 252 | } |
218 | | | 253 | |
219 | /* | | 254 | /* |
220 | * radix_tree_init_tree: | | 255 | * radix_tree_init_tree: |
221 | * | | 256 | * |
222 | * initialize a tree. | | 257 | * Initialize a tree. |
223 | */ | | 258 | */ |
224 | | | 259 | |
225 | void | | 260 | void |
226 | radix_tree_init_tree(struct radix_tree *t) | | 261 | radix_tree_init_tree(struct radix_tree *t) |
227 | { | | 262 | { |
228 | | | 263 | |
229 | t->t_height = 0; | | 264 | t->t_height = 0; |
230 | t->t_root = NULL; | | 265 | t->t_root = NULL; |
231 | } | | 266 | } |
232 | | | 267 | |
233 | /* | | 268 | /* |
234 | * radix_tree_init_tree: | | 269 | * radix_tree_fini_tree: |
235 | * | | 270 | * |
236 | * clean up a tree. | | 271 | * Finish using a tree. |
237 | */ | | 272 | */ |
238 | | | 273 | |
239 | void | | 274 | void |
240 | radix_tree_fini_tree(struct radix_tree *t) | | 275 | radix_tree_fini_tree(struct radix_tree *t) |
241 | { | | 276 | { |
242 | | | 277 | |
243 | KASSERT(t->t_root == NULL); | | 278 | KASSERT(t->t_root == NULL); |
244 | KASSERT(t->t_height == 0); | | 279 | KASSERT(t->t_height == 0); |
245 | } | | 280 | } |
246 | | | 281 | |
| | | 282 | /* |
| | | 283 | * radix_tree_empty_tree_p: |
| | | 284 | * |
| | | 285 | * Return if the tree is empty. |
| | | 286 | */ |
| | | 287 | |
247 | bool | | 288 | bool |
248 | radix_tree_empty_tree_p(struct radix_tree *t) | | 289 | radix_tree_empty_tree_p(struct radix_tree *t) |
249 | { | | 290 | { |
250 | | | 291 | |
251 | return t->t_root == NULL; | | 292 | return t->t_root == NULL; |
252 | } | | 293 | } |
253 | | | 294 | |
| | | 295 | /* |
| | | 296 | * radix_tree_empty_tree_p: |
| | | 297 | * |
| | | 298 | * Return true if the tree has any nodes with the given tag. Otherwise |
| | | 299 | * return false. |
| | | 300 | * |
| | | 301 | * It's illegal to call this function with tagmask 0. |
| | | 302 | */ |
| | | 303 | |
254 | bool | | 304 | bool |
255 | radix_tree_empty_tagged_tree_p(struct radix_tree *t, radix_tree_tagid_t tagid) | | 305 | radix_tree_empty_tagged_tree_p(struct radix_tree *t, unsigned int tagmask) |
256 | { | | 306 | { |
257 | const unsigned int tagmask = tagid_to_mask(tagid); | | | |
258 | | | 307 | |
| | | 308 | KASSERT(tagmask != 0); |
259 | return (entry_tagmask(t->t_root) & tagmask) == 0; | | 309 | return (entry_tagmask(t->t_root) & tagmask) == 0; |
260 | } | | 310 | } |
261 | | | 311 | |
262 | static void | | 312 | static void |
263 | radix_tree_node_init(struct radix_tree_node *n) | | 313 | radix_tree_node_init(struct radix_tree_node *n) |
264 | { | | 314 | { |
265 | | | 315 | |
266 | memset(n, 0, sizeof(*n)); | | 316 | memset(n, 0, sizeof(*n)); |
267 | } | | 317 | } |
268 | | | 318 | |
269 | #if defined(_KERNEL) | | 319 | #if defined(_KERNEL) |
270 | pool_cache_t radix_tree_node_cache __read_mostly; | | 320 | pool_cache_t radix_tree_node_cache __read_mostly; |
271 | | | 321 | |
272 | static int | | 322 | static int |
273 | radix_tree_node_ctor(void *dummy, void *item, int flags) | | 323 | radix_tree_node_ctor(void *dummy, void *item, int flags) |
274 | { | | 324 | { |
275 | struct radix_tree_node *n = item; | | 325 | struct radix_tree_node *n = item; |
276 | | | 326 | |
277 | KASSERT(dummy == NULL); | | 327 | KASSERT(dummy == NULL); |
278 | radix_tree_node_init(n); | | 328 | radix_tree_node_init(n); |
279 | return 0; | | 329 | return 0; |
280 | } | | 330 | } |
281 | | | 331 | |
282 | /* | | 332 | /* |
283 | * radix_tree_init: | | 333 | * radix_tree_init: |
284 | * | | 334 | * |
285 | * initialize the subsystem. | | 335 | * initialize the subsystem. |
286 | */ | | 336 | */ |
287 | | | 337 | |
288 | void | | 338 | void |
289 | radix_tree_init(void) | | 339 | radix_tree_init(void) |
290 | { | | 340 | { |
291 | | | 341 | |
292 | radix_tree_node_cache = pool_cache_init(sizeof(struct radix_tree_node), | | 342 | radix_tree_node_cache = pool_cache_init(sizeof(struct radix_tree_node), |
293 | 0, 0, 0, "radix_tree_node", NULL, IPL_NONE, radix_tree_node_ctor, | | 343 | 0, 0, 0, "radix_tree_node", NULL, IPL_NONE, radix_tree_node_ctor, |
294 | NULL, NULL); | | 344 | NULL, NULL); |
295 | KASSERT(radix_tree_node_cache != NULL); | | 345 | KASSERT(radix_tree_node_cache != NULL); |
296 | } | | 346 | } |
297 | #endif /* defined(_KERNEL) */ | | 347 | #endif /* defined(_KERNEL) */ |
298 | | | 348 | |
299 | static bool __unused | | 349 | static bool __unused |
300 | radix_tree_node_clean_p(const struct radix_tree_node *n) | | 350 | radix_tree_node_clean_p(const struct radix_tree_node *n) |
301 | { | | 351 | { |
302 | unsigned int i; | | 352 | unsigned int i; |
303 | | | 353 | |
304 | if (n->n_nptrs != 0) { | | 354 | if (n->n_nptrs != 0) { |
305 | return false; | | 355 | return false; |
306 | } | | 356 | } |
307 | for (i = 0; i < RADIX_TREE_PTR_PER_NODE; i++) { | | 357 | for (i = 0; i < RADIX_TREE_PTR_PER_NODE; i++) { |
308 | if (n->n_ptrs[i] != NULL) { | | 358 | if (n->n_ptrs[i] != NULL) { |
309 | return false; | | 359 | return false; |
310 | } | | 360 | } |
311 | } | | 361 | } |
312 | return true; | | 362 | return true; |
313 | } | | 363 | } |
314 | | | 364 | |
315 | static struct radix_tree_node * | | 365 | static struct radix_tree_node * |
316 | radix_tree_alloc_node(void) | | 366 | radix_tree_alloc_node(void) |
317 | { | | 367 | { |
318 | struct radix_tree_node *n; | | 368 | struct radix_tree_node *n; |
319 | | | 369 | |
320 | #if defined(_KERNEL) | | 370 | #if defined(_KERNEL) |
| | | 371 | /* |
| | | 372 | * note that pool_cache_get can block. |
| | | 373 | */ |
321 | n = pool_cache_get(radix_tree_node_cache, PR_NOWAIT); | | 374 | n = pool_cache_get(radix_tree_node_cache, PR_NOWAIT); |
322 | #else /* defined(_KERNEL) */ | | 375 | #else /* defined(_KERNEL) */ |
323 | #if defined(_STANDALONE) | | 376 | #if defined(_STANDALONE) |
324 | n = alloc(sizeof(*n)); | | 377 | n = alloc(sizeof(*n)); |
325 | #else /* defined(_STANDALONE) */ | | 378 | #else /* defined(_STANDALONE) */ |
326 | n = malloc(sizeof(*n)); | | 379 | n = malloc(sizeof(*n)); |
327 | #endif /* defined(_STANDALONE) */ | | 380 | #endif /* defined(_STANDALONE) */ |
328 | if (n != NULL) { | | 381 | if (n != NULL) { |
329 | radix_tree_node_init(n); | | 382 | radix_tree_node_init(n); |
330 | } | | 383 | } |
331 | #endif /* defined(_KERNEL) */ | | 384 | #endif /* defined(_KERNEL) */ |
332 | KASSERT(n == NULL || radix_tree_node_clean_p(n)); | | 385 | KASSERT(n == NULL || radix_tree_node_clean_p(n)); |
333 | return n; | | 386 | return n; |
334 | } | | 387 | } |
335 | | | 388 | |
336 | static void | | 389 | static void |
337 | radix_tree_free_node(struct radix_tree_node *n) | | 390 | radix_tree_free_node(struct radix_tree_node *n) |
338 | { | | 391 | { |
339 | | | 392 | |
340 | KASSERT(radix_tree_node_clean_p(n)); | | 393 | KASSERT(radix_tree_node_clean_p(n)); |
341 | #if defined(_KERNEL) | | 394 | #if defined(_KERNEL) |
342 | pool_cache_put(radix_tree_node_cache, n); | | 395 | pool_cache_put(radix_tree_node_cache, n); |
343 | #elif defined(_STANDALONE) | | 396 | #elif defined(_STANDALONE) |
344 | dealloc(n, sizeof(*n)); | | 397 | dealloc(n, sizeof(*n)); |
345 | #else | | 398 | #else |
346 | free(n); | | 399 | free(n); |
347 | #endif | | 400 | #endif |
348 | } | | 401 | } |
349 | | | 402 | |
350 | static int | | 403 | static int |
351 | radix_tree_grow(struct radix_tree *t, unsigned int newheight) | | 404 | radix_tree_grow(struct radix_tree *t, unsigned int newheight) |
352 | { | | 405 | { |
353 | const unsigned int tagmask = entry_tagmask(t->t_root); | | 406 | const unsigned int tagmask = entry_tagmask(t->t_root); |
354 | | | 407 | |
355 | KASSERT(newheight <= 64 / RADIX_TREE_BITS_PER_HEIGHT); | | 408 | KASSERT(newheight <= 64 / RADIX_TREE_BITS_PER_HEIGHT); |
356 | if (t->t_root == NULL) { | | 409 | if (t->t_root == NULL) { |
357 | t->t_height = newheight; | | 410 | t->t_height = newheight; |
358 | return 0; | | 411 | return 0; |
359 | } | | 412 | } |
360 | while (t->t_height < newheight) { | | 413 | while (t->t_height < newheight) { |
361 | struct radix_tree_node *n; | | 414 | struct radix_tree_node *n; |
362 | | | 415 | |
363 | n = radix_tree_alloc_node(); | | 416 | n = radix_tree_alloc_node(); |
364 | if (n == NULL) { | | 417 | if (n == NULL) { |
365 | /* | | 418 | /* |
366 | * don't bother to revert our changes. | | 419 | * don't bother to revert our changes. |
367 | * the caller will likely retry. | | 420 | * the caller will likely retry. |
368 | */ | | 421 | */ |
369 | return ENOMEM; | | 422 | return ENOMEM; |
370 | } | | 423 | } |
371 | n->n_nptrs = 1; | | 424 | n->n_nptrs = 1; |
372 | n->n_ptrs[0] = t->t_root; | | 425 | n->n_ptrs[0] = t->t_root; |
373 | t->t_root = entry_compose(n, tagmask); | | 426 | t->t_root = entry_compose(n, tagmask); |
374 | t->t_height++; | | 427 | t->t_height++; |
375 | } | | 428 | } |
376 | return 0; | | 429 | return 0; |
377 | } | | 430 | } |
378 | | | 431 | |
379 | /* | | 432 | /* |
380 | * radix_tree_lookup_ptr: | | 433 | * radix_tree_lookup_ptr: |
381 | * | | 434 | * |
382 | * an internal helper function used for various exported functions. | | 435 | * an internal helper function used for various exported functions. |
383 | * | | 436 | * |
384 | * return the pointer to store the node for the given index. | | 437 | * return the pointer to store the node for the given index. |
385 | * | | 438 | * |
386 | * if alloc is true, try to allocate the storage. (note for _KERNEL: | | 439 | * if alloc is true, try to allocate the storage. (note for _KERNEL: |
387 | * in that case, this function can block.) if the allocation failed or | | 440 | * in that case, this function can block.) if the allocation failed or |
388 | * alloc is false, return NULL. | | 441 | * alloc is false, return NULL. |
389 | * | | 442 | * |
390 | * if path is not NULL, fill it for the caller's investigation. | | 443 | * if path is not NULL, fill it for the caller's investigation. |
391 | * | | 444 | * |
392 | * if tagmask is not zero, search only for nodes with the tag set. | | 445 | * if tagmask is not zero, search only for nodes with the tag set. |
393 | * note that, however, this function doesn't check the tagmask for the leaf | | 446 | * note that, however, this function doesn't check the tagmask for the leaf |
394 | * pointer. it's a caller's responsibility to investigate the value which | | 447 | * pointer. it's a caller's responsibility to investigate the value which |
395 | * is pointed by the returned pointer if necessary. | | 448 | * is pointed by the returned pointer if necessary. |
396 | * | | 449 | * |
397 | * while this function is a bit large, as it's called with some constant | | 450 | * while this function is a bit large, as it's called with some constant |
398 | * arguments, inlining might have benefits. anyway, a compiler will decide. | | 451 | * arguments, inlining might have benefits. anyway, a compiler will decide. |
399 | */ | | 452 | */ |
400 | | | 453 | |
401 | static inline void ** | | 454 | static inline void ** |
402 | radix_tree_lookup_ptr(struct radix_tree *t, uint64_t idx, | | 455 | radix_tree_lookup_ptr(struct radix_tree *t, uint64_t idx, |
403 | struct radix_tree_path *path, bool alloc, const unsigned int tagmask) | | 456 | struct radix_tree_path *path, bool alloc, const unsigned int tagmask) |
404 | { | | 457 | { |
405 | struct radix_tree_node *n; | | 458 | struct radix_tree_node *n; |
406 | int hshift = RADIX_TREE_BITS_PER_HEIGHT * t->t_height; | | 459 | int hshift = RADIX_TREE_BITS_PER_HEIGHT * t->t_height; |
407 | int shift; | | 460 | int shift; |
408 | void **vpp; | | 461 | void **vpp; |
409 | const uint64_t mask = (UINT64_C(1) << RADIX_TREE_BITS_PER_HEIGHT) - 1; | | 462 | const uint64_t mask = (UINT64_C(1) << RADIX_TREE_BITS_PER_HEIGHT) - 1; |
410 | struct radix_tree_node_ref *refs = NULL; | | 463 | struct radix_tree_node_ref *refs = NULL; |
411 | | | 464 | |
412 | /* | | 465 | /* |
413 | * check unsupported combinations | | 466 | * check unsupported combinations |
414 | */ | | 467 | */ |
415 | KASSERT(tagmask == 0 || !alloc); | | 468 | KASSERT(tagmask == 0 || !alloc); |
416 | KASSERT(path == NULL || !alloc); | | 469 | KASSERT(path == NULL || !alloc); |
417 | vpp = &t->t_root; | | 470 | vpp = &t->t_root; |
418 | if (path != NULL) { | | 471 | if (path != NULL) { |
419 | refs = path->p_refs; | | 472 | refs = path->p_refs; |
420 | refs->pptr = vpp; | | 473 | refs->pptr = vpp; |
421 | } | | 474 | } |
422 | n = NULL; | | 475 | n = NULL; |
423 | for (shift = 64 - RADIX_TREE_BITS_PER_HEIGHT; shift >= 0;) { | | 476 | for (shift = 64 - RADIX_TREE_BITS_PER_HEIGHT; shift >= 0;) { |
424 | struct radix_tree_node *c; | | 477 | struct radix_tree_node *c; |
425 | void *entry; | | 478 | void *entry; |
426 | const uint64_t i = (idx >> shift) & mask; | | 479 | const uint64_t i = (idx >> shift) & mask; |
427 | | | 480 | |
428 | if (shift >= hshift) { | | 481 | if (shift >= hshift) { |
429 | unsigned int newheight; | | 482 | unsigned int newheight; |
430 | | | 483 | |
431 | KASSERT(vpp == &t->t_root); | | 484 | KASSERT(vpp == &t->t_root); |
432 | if (i == 0) { | | 485 | if (i == 0) { |
433 | shift -= RADIX_TREE_BITS_PER_HEIGHT; | | 486 | shift -= RADIX_TREE_BITS_PER_HEIGHT; |
434 | continue; | | 487 | continue; |
435 | } | | 488 | } |
436 | if (!alloc) { | | 489 | if (!alloc) { |
437 | if (path != NULL) { | | 490 | if (path != NULL) { |
438 | KASSERT((refs - path->p_refs) == 0); | | 491 | KASSERT((refs - path->p_refs) == 0); |
439 | path->p_lastidx = | | 492 | path->p_lastidx = |
440 | RADIX_TREE_INVALID_HEIGHT; | | 493 | RADIX_TREE_INVALID_HEIGHT; |
441 | } | | 494 | } |
442 | return NULL; | | 495 | return NULL; |
443 | } | | 496 | } |
444 | newheight = shift / RADIX_TREE_BITS_PER_HEIGHT + 1; | | 497 | newheight = shift / RADIX_TREE_BITS_PER_HEIGHT + 1; |
445 | if (radix_tree_grow(t, newheight)) { | | 498 | if (radix_tree_grow(t, newheight)) { |
446 | return NULL; | | 499 | return NULL; |
447 | } | | 500 | } |
448 | hshift = RADIX_TREE_BITS_PER_HEIGHT * t->t_height; | | 501 | hshift = RADIX_TREE_BITS_PER_HEIGHT * t->t_height; |
449 | } | | 502 | } |
450 | entry = *vpp; | | 503 | entry = *vpp; |
451 | c = entry_ptr(entry); | | 504 | c = entry_ptr(entry); |
452 | if (c == NULL || | | 505 | if (c == NULL || |
453 | (tagmask != 0 && | | 506 | (tagmask != 0 && |
454 | (entry_tagmask(entry) & tagmask) == 0)) { | | 507 | (entry_tagmask(entry) & tagmask) == 0)) { |
455 | if (!alloc) { | | 508 | if (!alloc) { |
456 | if (path != NULL) { | | 509 | if (path != NULL) { |
457 | path->p_lastidx = refs - path->p_refs; | | 510 | path->p_lastidx = refs - path->p_refs; |
458 | } | | 511 | } |
459 | return NULL; | | 512 | return NULL; |
460 | } | | 513 | } |
461 | c = radix_tree_alloc_node(); | | 514 | c = radix_tree_alloc_node(); |
462 | if (c == NULL) { | | 515 | if (c == NULL) { |
463 | return NULL; | | 516 | return NULL; |
464 | } | | 517 | } |
465 | *vpp = c; | | 518 | *vpp = c; |
466 | if (n != NULL) { | | 519 | if (n != NULL) { |
467 | KASSERT(n->n_nptrs < RADIX_TREE_PTR_PER_NODE); | | 520 | KASSERT(n->n_nptrs < RADIX_TREE_PTR_PER_NODE); |
468 | n->n_nptrs++; | | 521 | n->n_nptrs++; |
469 | } | | 522 | } |
470 | } | | 523 | } |
471 | n = c; | | 524 | n = c; |
472 | vpp = &n->n_ptrs[i]; | | 525 | vpp = &n->n_ptrs[i]; |
473 | if (path != NULL) { | | 526 | if (path != NULL) { |
474 | refs++; | | 527 | refs++; |
475 | refs->pptr = vpp; | | 528 | refs->pptr = vpp; |
476 | } | | 529 | } |
477 | shift -= RADIX_TREE_BITS_PER_HEIGHT; | | 530 | shift -= RADIX_TREE_BITS_PER_HEIGHT; |
478 | } | | 531 | } |
479 | if (alloc) { | | 532 | if (alloc) { |
480 | KASSERT(*vpp == NULL); | | 533 | KASSERT(*vpp == NULL); |
481 | if (n != NULL) { | | 534 | if (n != NULL) { |
482 | KASSERT(n->n_nptrs < RADIX_TREE_PTR_PER_NODE); | | 535 | KASSERT(n->n_nptrs < RADIX_TREE_PTR_PER_NODE); |
483 | n->n_nptrs++; | | 536 | n->n_nptrs++; |
484 | } | | 537 | } |
485 | } | | 538 | } |
486 | if (path != NULL) { | | 539 | if (path != NULL) { |
487 | path->p_lastidx = refs - path->p_refs; | | 540 | path->p_lastidx = refs - path->p_refs; |
488 | } | | 541 | } |
489 | return vpp; | | 542 | return vpp; |
490 | } | | 543 | } |
491 | | | 544 | |
492 | /* | | 545 | /* |
493 | * radix_tree_insert_node: | | 546 | * radix_tree_insert_node: |
494 | * | | 547 | * |
495 | * insert the node at idx. | | 548 | * Insert the node at the given index. |
496 | * it's illegal to insert NULL. | | 549 | * |
497 | * it's illegal to insert a non-aligned pointer. | | 550 | * It's illegal to insert NULL. It's illegal to insert a non-aligned pointer. |
498 | * | | 551 | * |
499 | * this function returns ENOMEM if necessary memory allocation failed. | | 552 | * This function returns ENOMEM if necessary memory allocation failed. |
500 | * otherwise, this function returns 0. | | 553 | * Otherwise, this function returns 0. |
501 | * | | 554 | * |
502 | * note that inserting a node can involves memory allocation for intermediate | | 555 | * Note that inserting a node can involves memory allocation for intermediate |
503 | * nodes. if _KERNEL, it's done with no-sleep IPL_NONE memory allocation. | | 556 | * nodes. If _KERNEL, it's done with no-sleep IPL_NONE memory allocation. |
504 | * | | 557 | * |
505 | * for the newly inserted node, all tags are cleared. | | 558 | * For the newly inserted node, all tags are cleared. |
506 | */ | | 559 | */ |
507 | | | 560 | |
508 | int | | 561 | int |
509 | radix_tree_insert_node(struct radix_tree *t, uint64_t idx, void *p) | | 562 | radix_tree_insert_node(struct radix_tree *t, uint64_t idx, void *p) |
510 | { | | 563 | { |
511 | void **vpp; | | 564 | void **vpp; |
512 | | | 565 | |
513 | KASSERT(p != NULL); | | 566 | KASSERT(p != NULL); |
514 | KASSERT(entry_compose(p, 0) == p); | | 567 | KASSERT(entry_tagmask(entry_compose(p, 0)) == 0); |
515 | vpp = radix_tree_lookup_ptr(t, idx, NULL, true, 0); | | 568 | vpp = radix_tree_lookup_ptr(t, idx, NULL, true, 0); |
516 | if (vpp == NULL) { | | 569 | if (vpp == NULL) { |
517 | return ENOMEM; | | 570 | return ENOMEM; |
518 | } | | 571 | } |
519 | KASSERT(*vpp == NULL); | | 572 | KASSERT(*vpp == NULL); |
520 | *vpp = p; | | 573 | *vpp = p; |
521 | return 0; | | 574 | return 0; |
522 | } | | 575 | } |
523 | | | 576 | |
524 | /* | | 577 | /* |
525 | * radix_tree_replace_node: | | 578 | * radix_tree_replace_node: |
526 | * | | 579 | * |
527 | * replace a node at the given index with the given node. | | 580 | * Replace a node at the given index with the given node and return the |
528 | * return the old node. | | 581 | * replaced one. |
529 | * it's illegal to try to replace a node which has not been inserted. | | 582 | * |
| | | 583 | * It's illegal to try to replace a node which has not been inserted. |
530 | * | | 584 | * |
531 | * this function doesn't change tags. | | 585 | * This function keeps tags intact. |
532 | */ | | 586 | */ |
533 | | | 587 | |
534 | void * | | 588 | void * |
535 | radix_tree_replace_node(struct radix_tree *t, uint64_t idx, void *p) | | 589 | radix_tree_replace_node(struct radix_tree *t, uint64_t idx, void *p) |
536 | { | | 590 | { |
537 | void **vpp; | | 591 | void **vpp; |
538 | void *oldp; | | 592 | void *oldp; |
539 | | | 593 | |
540 | KASSERT(p != NULL); | | 594 | KASSERT(p != NULL); |
541 | KASSERT(entry_compose(p, 0) == p); | | 595 | KASSERT(entry_tagmask(entry_compose(p, 0)) == 0); |
542 | vpp = radix_tree_lookup_ptr(t, idx, NULL, false, 0); | | 596 | vpp = radix_tree_lookup_ptr(t, idx, NULL, false, 0); |
543 | KASSERT(vpp != NULL); | | 597 | KASSERT(vpp != NULL); |
544 | oldp = *vpp; | | 598 | oldp = *vpp; |
545 | KASSERT(oldp != NULL); | | 599 | KASSERT(oldp != NULL); |
546 | *vpp = entry_compose(p, entry_tagmask(*vpp)); | | 600 | *vpp = entry_compose(p, entry_tagmask(*vpp)); |
547 | return entry_ptr(oldp); | | 601 | return entry_ptr(oldp); |
548 | } | | 602 | } |
549 | | | 603 | |
550 | /* | | 604 | /* |
551 | * radix_tree_remove_node: | | 605 | * radix_tree_remove_node: |
552 | * | | 606 | * |
553 | * remove the node at idx. | | 607 | * Remove the node at the given index. |
554 | * it's illegal to try to remove a node which has not been inserted. | | 608 | * |
| | | 609 | * It's illegal to try to remove a node which has not been inserted. |
555 | */ | | 610 | */ |
556 | | | 611 | |
557 | void * | | 612 | void * |
558 | radix_tree_remove_node(struct radix_tree *t, uint64_t idx) | | 613 | radix_tree_remove_node(struct radix_tree *t, uint64_t idx) |
559 | { | | 614 | { |
560 | struct radix_tree_path path; | | 615 | struct radix_tree_path path; |
561 | void **vpp; | | 616 | void **vpp; |
562 | void *oldp; | | 617 | void *oldp; |
563 | int i; | | 618 | int i; |
564 | | | 619 | |
565 | vpp = radix_tree_lookup_ptr(t, idx, &path, false, 0); | | 620 | vpp = radix_tree_lookup_ptr(t, idx, &path, false, 0); |
566 | KASSERT(vpp != NULL); | | 621 | KASSERT(vpp != NULL); |
567 | oldp = *vpp; | | 622 | oldp = *vpp; |
568 | KASSERT(oldp != NULL); | | 623 | KASSERT(oldp != NULL); |
569 | KASSERT(path.p_lastidx == t->t_height); | | 624 | KASSERT(path.p_lastidx == t->t_height); |
570 | KASSERT(vpp == path_pptr(t, &path, path.p_lastidx)); | | 625 | KASSERT(vpp == path_pptr(t, &path, path.p_lastidx)); |
571 | *vpp = NULL; | | 626 | *vpp = NULL; |
572 | for (i = t->t_height - 1; i >= 0; i--) { | | 627 | for (i = t->t_height - 1; i >= 0; i--) { |
573 | void *entry; | | 628 | void *entry; |
574 | struct radix_tree_node ** const pptr = | | 629 | struct radix_tree_node ** const pptr = |
575 | (struct radix_tree_node **)path_pptr(t, &path, i); | | 630 | (struct radix_tree_node **)path_pptr(t, &path, i); |
576 | struct radix_tree_node *n; | | 631 | struct radix_tree_node *n; |
577 | | | 632 | |
578 | KASSERT(pptr != NULL); | | 633 | KASSERT(pptr != NULL); |
579 | entry = *pptr; | | 634 | entry = *pptr; |
580 | n = entry_ptr(entry); | | 635 | n = entry_ptr(entry); |
581 | KASSERT(n != NULL); | | 636 | KASSERT(n != NULL); |
582 | KASSERT(n->n_nptrs > 0); | | 637 | KASSERT(n->n_nptrs > 0); |
583 | n->n_nptrs--; | | 638 | n->n_nptrs--; |
584 | if (n->n_nptrs > 0) { | | 639 | if (n->n_nptrs > 0) { |
585 | break; | | 640 | break; |
586 | } | | 641 | } |
587 | radix_tree_free_node(n); | | 642 | radix_tree_free_node(n); |
588 | *pptr = NULL; | | 643 | *pptr = NULL; |
589 | } | | 644 | } |
590 | /* | | 645 | /* |
591 | * fix up height | | 646 | * fix up height |
592 | */ | | 647 | */ |
593 | if (i < 0) { | | 648 | if (i < 0) { |
594 | KASSERT(t->t_root == NULL); | | 649 | KASSERT(t->t_root == NULL); |
595 | t->t_height = 0; | | 650 | t->t_height = 0; |
596 | } | | 651 | } |
597 | /* | | 652 | /* |
598 | * update tags | | 653 | * update tags |
599 | */ | | 654 | */ |
600 | for (; i >= 0; i--) { | | 655 | for (; i >= 0; i--) { |
601 | void *entry; | | 656 | void *entry; |
602 | struct radix_tree_node ** const pptr = | | 657 | struct radix_tree_node ** const pptr = |
603 | (struct radix_tree_node **)path_pptr(t, &path, i); | | 658 | (struct radix_tree_node **)path_pptr(t, &path, i); |
604 | struct radix_tree_node *n; | | 659 | struct radix_tree_node *n; |
605 | unsigned int newmask; | | 660 | unsigned int newmask; |
606 | | | 661 | |
607 | KASSERT(pptr != NULL); | | 662 | KASSERT(pptr != NULL); |
608 | entry = *pptr; | | 663 | entry = *pptr; |
609 | n = entry_ptr(entry); | | 664 | n = entry_ptr(entry); |
610 | KASSERT(n != NULL); | | 665 | KASSERT(n != NULL); |
611 | KASSERT(n->n_nptrs > 0); | | 666 | KASSERT(n->n_nptrs > 0); |
612 | newmask = any_children_tagmask(n); | | 667 | newmask = any_children_tagmask(n); |
613 | if (newmask == entry_tagmask(entry)) { | | 668 | if (newmask == entry_tagmask(entry)) { |
614 | break; | | 669 | break; |
615 | } | | 670 | } |
616 | *pptr = entry_compose(n, newmask); | | 671 | *pptr = entry_compose(n, newmask); |
617 | } | | 672 | } |
618 | /* | | 673 | /* |
619 | * XXX is it worth to try to reduce height? | | 674 | * XXX is it worth to try to reduce height? |
620 | * if we do that, make radix_tree_grow rollback its change as well. | | 675 | * if we do that, make radix_tree_grow rollback its change as well. |
621 | */ | | 676 | */ |
622 | return entry_ptr(oldp); | | 677 | return entry_ptr(oldp); |
623 | } | | 678 | } |
624 | | | 679 | |
625 | /* | | 680 | /* |
626 | * radix_tree_lookup_node: | | 681 | * radix_tree_lookup_node: |
627 | * | | 682 | * |
628 | * returns the node at idx. | | 683 | * Returns the node at the given index. |
629 | * returns NULL if nothing is found at idx. | | 684 | * Returns NULL if nothing is found at the given index. |
630 | */ | | 685 | */ |
631 | | | 686 | |
632 | void * | | 687 | void * |
633 | radix_tree_lookup_node(struct radix_tree *t, uint64_t idx) | | 688 | radix_tree_lookup_node(struct radix_tree *t, uint64_t idx) |
634 | { | | 689 | { |
635 | void **vpp; | | 690 | void **vpp; |
636 | | | 691 | |
637 | vpp = radix_tree_lookup_ptr(t, idx, NULL, false, 0); | | 692 | vpp = radix_tree_lookup_ptr(t, idx, NULL, false, 0); |
638 | if (vpp == NULL) { | | 693 | if (vpp == NULL) { |
639 | return NULL; | | 694 | return NULL; |
640 | } | | 695 | } |
641 | return entry_ptr(*vpp); | | 696 | return entry_ptr(*vpp); |
642 | } | | 697 | } |
643 | | | 698 | |
644 | static inline void | | 699 | static inline void |
645 | gang_lookup_init(struct radix_tree *t, uint64_t idx, | | 700 | gang_lookup_init(struct radix_tree *t, uint64_t idx, |
646 | struct radix_tree_path *path, const unsigned int tagmask) | | 701 | struct radix_tree_path *path, const unsigned int tagmask) |
647 | { | | 702 | { |
648 | void **vpp; | | 703 | void **vpp __unused; |
649 | | | 704 | |
650 | vpp = radix_tree_lookup_ptr(t, idx, path, false, tagmask); | | 705 | #if defined(DIAGNOSTIC) |
| | | 706 | vpp = |
| | | 707 | #endif /* defined(DIAGNOSTIC) */ |
| | | 708 | radix_tree_lookup_ptr(t, idx, path, false, tagmask); |
651 | KASSERT(vpp == NULL || | | 709 | KASSERT(vpp == NULL || |
652 | vpp == path_pptr(t, path, path->p_lastidx)); | | 710 | vpp == path_pptr(t, path, path->p_lastidx)); |
653 | KASSERT(&t->t_root == path_pptr(t, path, 0)); | | 711 | KASSERT(&t->t_root == path_pptr(t, path, 0)); |
654 | KASSERT(path->p_lastidx == RADIX_TREE_INVALID_HEIGHT || | | 712 | KASSERT(path->p_lastidx == RADIX_TREE_INVALID_HEIGHT || |
655 | path->p_lastidx == t->t_height || | | 713 | path->p_lastidx == t->t_height || |
656 | !entry_match_p(*path_pptr(t, path, path->p_lastidx), tagmask)); | | 714 | !entry_match_p(*path_pptr(t, path, path->p_lastidx), tagmask)); |
657 | } | | 715 | } |
658 | | | 716 | |
659 | /* | | 717 | /* |
660 | * gang_lookup_scan: | | 718 | * gang_lookup_scan: |
661 | * | | 719 | * |
662 | * a helper routine for radix_tree_gang_lookup_node and its variants. | | 720 | * a helper routine for radix_tree_gang_lookup_node and its variants. |
663 | */ | | 721 | */ |
664 | | | 722 | |
665 | static inline unsigned int | | 723 | static inline unsigned int |
666 | __attribute__((__always_inline__)) | | 724 | __attribute__((__always_inline__)) |
667 | gang_lookup_scan(struct radix_tree *t, struct radix_tree_path *path, | | 725 | gang_lookup_scan(struct radix_tree *t, struct radix_tree_path *path, |
668 | void **results, unsigned int maxresults, const unsigned int tagmask, | | 726 | void **results, const unsigned int maxresults, const unsigned int tagmask, |
669 | bool reverse) | | 727 | const bool reverse, const bool dense) |
670 | { | | 728 | { |
671 | | | 729 | |
672 | /* | | 730 | /* |
673 | * we keep the path updated only for lastidx-1. | | 731 | * we keep the path updated only for lastidx-1. |
674 | * vpp is what path_pptr(t, path, lastidx) would be. | | 732 | * vpp is what path_pptr(t, path, lastidx) would be. |
675 | */ | | 733 | */ |
676 | void **vpp; | | 734 | void **vpp; |
677 | unsigned int nfound; | | 735 | unsigned int nfound; |
678 | unsigned int lastidx; | | 736 | unsigned int lastidx; |
679 | /* | | 737 | /* |
680 | * set up scan direction dependant constants so that we can iterate | | 738 | * set up scan direction dependant constants so that we can iterate |
681 | * n_ptrs as the following. | | 739 | * n_ptrs as the following. |
682 | * | | 740 | * |
683 | * for (i = first; i != guard; i += step) | | 741 | * for (i = first; i != guard; i += step) |
684 | * visit n->n_ptrs[i]; | | 742 | * visit n->n_ptrs[i]; |
685 | */ | | 743 | */ |
686 | const int step = reverse ? -1 : 1; | | 744 | const int step = reverse ? -1 : 1; |
687 | const unsigned int first = reverse ? RADIX_TREE_PTR_PER_NODE - 1 : 0; | | 745 | const unsigned int first = reverse ? RADIX_TREE_PTR_PER_NODE - 1 : 0; |
688 | const unsigned int last = reverse ? 0 : RADIX_TREE_PTR_PER_NODE - 1; | | 746 | const unsigned int last = reverse ? 0 : RADIX_TREE_PTR_PER_NODE - 1; |
689 | const unsigned int guard = last + step; | | 747 | const unsigned int guard = last + step; |
690 | | | 748 | |
691 | KASSERT(maxresults > 0); | | 749 | KASSERT(maxresults > 0); |
692 | KASSERT(&t->t_root == path_pptr(t, path, 0)); | | 750 | KASSERT(&t->t_root == path_pptr(t, path, 0)); |
693 | lastidx = path->p_lastidx; | | 751 | lastidx = path->p_lastidx; |
694 | KASSERT(lastidx == RADIX_TREE_INVALID_HEIGHT || | | 752 | KASSERT(lastidx == RADIX_TREE_INVALID_HEIGHT || |
695 | lastidx == t->t_height || | | 753 | lastidx == t->t_height || |
696 | !entry_match_p(*path_pptr(t, path, lastidx), tagmask)); | | 754 | !entry_match_p(*path_pptr(t, path, lastidx), tagmask)); |
697 | nfound = 0; | | 755 | nfound = 0; |
698 | if (lastidx == RADIX_TREE_INVALID_HEIGHT) { | | 756 | if (lastidx == RADIX_TREE_INVALID_HEIGHT) { |
699 | if (reverse) { | | 757 | /* |
| | | 758 | * requested idx is beyond the right-most node. |
| | | 759 | */ |
| | | 760 | if (reverse && !dense) { |
700 | lastidx = 0; | | 761 | lastidx = 0; |
701 | vpp = path_pptr(t, path, lastidx); | | 762 | vpp = path_pptr(t, path, lastidx); |
702 | goto descend; | | 763 | goto descend; |
703 | } | | 764 | } |
704 | return 0; | | 765 | return 0; |
705 | } | | 766 | } |
706 | vpp = path_pptr(t, path, lastidx); | | 767 | vpp = path_pptr(t, path, lastidx); |
707 | while (/*CONSTCOND*/true) { | | 768 | while (/*CONSTCOND*/true) { |
708 | struct radix_tree_node *n; | | 769 | struct radix_tree_node *n; |
709 | unsigned int i; | | 770 | unsigned int i; |
710 | | | 771 | |
711 | if (entry_match_p(*vpp, tagmask)) { | | 772 | if (entry_match_p(*vpp, tagmask)) { |
712 | KASSERT(lastidx == t->t_height); | | 773 | KASSERT(lastidx == t->t_height); |
713 | /* | | 774 | /* |
714 | * record the matching non-NULL leaf. | | 775 | * record the matching non-NULL leaf. |
715 | */ | | 776 | */ |
716 | results[nfound] = entry_ptr(*vpp); | | 777 | results[nfound] = entry_ptr(*vpp); |
717 | nfound++; | | 778 | nfound++; |
718 | if (nfound == maxresults) { | | 779 | if (nfound == maxresults) { |
719 | return nfound; | | 780 | return nfound; |
720 | } | | 781 | } |
| | | 782 | } else if (dense) { |
| | | 783 | return nfound; |
721 | } | | 784 | } |
722 | scan_siblings: | | 785 | scan_siblings: |
723 | /* | | 786 | /* |
724 | * try to find the next matching non-NULL sibling. | | 787 | * try to find the next matching non-NULL sibling. |
725 | */ | | 788 | */ |
726 | if (lastidx == 0) { | | 789 | if (lastidx == 0) { |
727 | /* | | 790 | /* |
728 | * the root has no siblings. | | 791 | * the root has no siblings. |
729 | * we've done. | | 792 | * we've done. |
730 | */ | | 793 | */ |
731 | KASSERT(vpp == &t->t_root); | | 794 | KASSERT(vpp == &t->t_root); |
732 | break; | | 795 | break; |
733 | } | | 796 | } |
734 | n = path_node(t, path, lastidx - 1); | | 797 | n = path_node(t, path, lastidx - 1); |
735 | if (*vpp != NULL && n->n_nptrs == 1) { | | 798 | if (*vpp != NULL && n->n_nptrs == 1) { |
736 | /* | | 799 | /* |
737 | * optimization; if the node has only a single pointer | | 800 | * optimization; if the node has only a single pointer |
738 | * and we've already visited it, there's no point to | | 801 | * and we've already visited it, there's no point to |
739 | * keep scanning in this node. | | 802 | * keep scanning in this node. |
740 | */ | | 803 | */ |
741 | goto no_siblings; | | 804 | goto no_siblings; |
742 | } | | 805 | } |
743 | for (i = vpp - n->n_ptrs + step; i != guard; i += step) { | | 806 | for (i = vpp - n->n_ptrs + step; i != guard; i += step) { |
744 | KASSERT(i < RADIX_TREE_PTR_PER_NODE); | | 807 | KASSERT(i < RADIX_TREE_PTR_PER_NODE); |
745 | if (entry_match_p(n->n_ptrs[i], tagmask)) { | | 808 | if (entry_match_p(n->n_ptrs[i], tagmask)) { |
746 | vpp = &n->n_ptrs[i]; | | 809 | vpp = &n->n_ptrs[i]; |
747 | break; | | 810 | break; |
748 | } | | 811 | } |
749 | } | | 812 | } |
750 | if (i == guard) { | | 813 | if (i == guard) { |
751 | no_siblings: | | 814 | no_siblings: |
752 | /* | | 815 | /* |
753 | * not found. go to parent. | | 816 | * not found. go to parent. |
754 | */ | | 817 | */ |
755 | lastidx--; | | 818 | lastidx--; |
756 | vpp = path_pptr(t, path, lastidx); | | 819 | vpp = path_pptr(t, path, lastidx); |
757 | goto scan_siblings; | | 820 | goto scan_siblings; |
758 | } | | 821 | } |
759 | descend: | | 822 | descend: |
760 | /* | | 823 | /* |
761 | * following the left-most (or right-most in the case of | | 824 | * following the left-most (or right-most in the case of |
762 | * reverse scan) child node, decend until reaching the leaf or | | 825 | * reverse scan) child node, decend until reaching the leaf or |
763 | * an non-matching entry. | | 826 | * an non-matching entry. |
764 | */ | | 827 | */ |
765 | while (entry_match_p(*vpp, tagmask) && lastidx < t->t_height) { | | 828 | while (entry_match_p(*vpp, tagmask) && lastidx < t->t_height) { |
766 | /* | | 829 | /* |
767 | * save vpp in the path so that we can come back to this | | 830 | * save vpp in the path so that we can come back to this |
768 | * node after finishing visiting children. | | 831 | * node after finishing visiting children. |
769 | */ | | 832 | */ |
770 | path->p_refs[lastidx].pptr = vpp; | | 833 | path->p_refs[lastidx].pptr = vpp; |
771 | n = entry_ptr(*vpp); | | 834 | n = entry_ptr(*vpp); |
772 | vpp = &n->n_ptrs[first]; | | 835 | vpp = &n->n_ptrs[first]; |
773 | lastidx++; | | 836 | lastidx++; |
774 | } | | 837 | } |
775 | } | | 838 | } |
776 | return nfound; | | 839 | return nfound; |
777 | } | | 840 | } |
778 | | | 841 | |
779 | /* | | 842 | /* |
780 | * radix_tree_gang_lookup_node: | | 843 | * radix_tree_gang_lookup_node: |
781 | * | | 844 | * |
782 | * search nodes starting from idx in the ascending order. | | 845 | * Scan the tree starting from the given index in the ascending order and |
| | | 846 | * return found nodes. |
| | | 847 | * |
783 | * results should be an array large enough to hold maxresults pointers. | | 848 | * results should be an array large enough to hold maxresults pointers. |
784 | * returns the number of nodes found, up to maxresults. | | 849 | * This function returns the number of nodes found, up to maxresults. |
785 | * returning less than maxresults means there are no more nodes. | | 850 | * Returning less than maxresults means there are no more nodes in the tree. |
786 | * | | 851 | * |
787 | * the result of this function is semantically equivalent to what could be | | 852 | * If dense == true, this function stops scanning when it founds a hole of |
788 | * obtained by repeated calls of radix_tree_lookup_node with increasing index. | | 853 | * indexes. I.e. an index for which radix_tree_lookup_node would returns NULL. |
789 | * but this function is much faster when node indexes are distributed sparsely. | | 854 | * If dense == false, this function skips holes and continue scanning until |
| | | 855 | * maxresults nodes are found or it reaches the limit of the index range. |
790 | * | | 856 | * |
791 | * note that this function doesn't return exact values of node indexes of | | 857 | * The result of this function is semantically equivalent to what could be |
792 | * found nodes. if they are important for a caller, it's the caller's | | 858 | * obtained by repeated calls of radix_tree_lookup_node with increasing index. |
793 | * responsibility to check them, typically by examinining the returned nodes | | 859 | * but this function is expected to be computationally cheaper when looking up |
794 | * using some caller-specific knowledge about them. | | 860 | * multiple nodes at once. Especially, it's expected to be much cheaper when |
| | | 861 | * node indexes are distributed sparsely. |
| | | 862 | * |
| | | 863 | * Note that this function doesn't return index values of found nodes. |
| | | 864 | * Thus, in the case of dense == false, if index values are important for |
| | | 865 | * a caller, it's the caller's responsibility to check them, typically |
| | | 866 | * by examinining the returned nodes using some caller-specific knowledge |
| | | 867 | * about them. |
| | | 868 | * In the case of dense == true, a node returned via results[N] is always for |
| | | 869 | * the index (idx + N). |
795 | */ | | 870 | */ |
796 | | | 871 | |
797 | unsigned int | | 872 | unsigned int |
798 | radix_tree_gang_lookup_node(struct radix_tree *t, uint64_t idx, | | 873 | radix_tree_gang_lookup_node(struct radix_tree *t, uint64_t idx, |
799 | void **results, unsigned int maxresults) | | 874 | void **results, unsigned int maxresults, bool dense) |
800 | { | | 875 | { |
801 | struct radix_tree_path path; | | 876 | struct radix_tree_path path; |
802 | | | 877 | |
803 | gang_lookup_init(t, idx, &path, 0); | | 878 | gang_lookup_init(t, idx, &path, 0); |
804 | return gang_lookup_scan(t, &path, results, maxresults, 0, false); | | 879 | return gang_lookup_scan(t, &path, results, maxresults, 0, false, dense); |
805 | } | | 880 | } |
806 | | | 881 | |
807 | /* | | 882 | /* |
808 | * radix_tree_gang_lookup_node_reverse: | | 883 | * radix_tree_gang_lookup_node_reverse: |
809 | * | | 884 | * |
810 | * same as radix_tree_gang_lookup_node except that this one scans the | | 885 | * Same as radix_tree_gang_lookup_node except that this one scans the |
811 | * tree in the reverse order. ie. descending index values. | | 886 | * tree in the reverse order. I.e. descending index values. |
812 | */ | | 887 | */ |
813 | | | 888 | |
814 | unsigned int | | 889 | unsigned int |
815 | radix_tree_gang_lookup_node_reverse(struct radix_tree *t, uint64_t idx, | | 890 | radix_tree_gang_lookup_node_reverse(struct radix_tree *t, uint64_t idx, |
816 | void **results, unsigned int maxresults) | | 891 | void **results, unsigned int maxresults, bool dense) |
817 | { | | 892 | { |
818 | struct radix_tree_path path; | | 893 | struct radix_tree_path path; |
819 | | | 894 | |
820 | gang_lookup_init(t, idx, &path, 0); | | 895 | gang_lookup_init(t, idx, &path, 0); |
821 | return gang_lookup_scan(t, &path, results, maxresults, 0, true); | | 896 | return gang_lookup_scan(t, &path, results, maxresults, 0, true, dense); |
822 | } | | 897 | } |
823 | | | 898 | |
824 | /* | | 899 | /* |
825 | * radix_tree_gang_lookup_tagged_node: | | 900 | * radix_tree_gang_lookup_tagged_node: |
826 | * | | 901 | * |
827 | * same as radix_tree_gang_lookup_node except that this one only returns | | 902 | * Same as radix_tree_gang_lookup_node except that this one only returns |
828 | * nodes tagged with tagid. | | 903 | * nodes tagged with tagid. |
| | | 904 | * |
| | | 905 | * It's illegal to call this function with tagmask 0. |
829 | */ | | 906 | */ |
830 | | | 907 | |
831 | unsigned int | | 908 | unsigned int |
832 | radix_tree_gang_lookup_tagged_node(struct radix_tree *t, uint64_t idx, | | 909 | radix_tree_gang_lookup_tagged_node(struct radix_tree *t, uint64_t idx, |
833 | void **results, unsigned int maxresults, radix_tree_tagid_t tagid) | | 910 | void **results, unsigned int maxresults, bool dense, unsigned int tagmask) |
834 | { | | 911 | { |
835 | struct radix_tree_path path; | | 912 | struct radix_tree_path path; |
836 | const unsigned int tagmask = tagid_to_mask(tagid); | | | |
837 | | | 913 | |
| | | 914 | KASSERT(tagmask != 0); |
838 | gang_lookup_init(t, idx, &path, tagmask); | | 915 | gang_lookup_init(t, idx, &path, tagmask); |
839 | return gang_lookup_scan(t, &path, results, maxresults, tagmask, false); | | 916 | return gang_lookup_scan(t, &path, results, maxresults, tagmask, false, |
| | | 917 | dense); |
840 | } | | 918 | } |
841 | | | 919 | |
842 | /* | | 920 | /* |
843 | * radix_tree_gang_lookup_tagged_node_reverse: | | 921 | * radix_tree_gang_lookup_tagged_node_reverse: |
844 | * | | 922 | * |
845 | * same as radix_tree_gang_lookup_tagged_node except that this one scans the | | 923 | * Same as radix_tree_gang_lookup_tagged_node except that this one scans the |
846 | * tree in the reverse order. ie. descending index values. | | 924 | * tree in the reverse order. I.e. descending index values. |
847 | */ | | 925 | */ |
848 | | | 926 | |
849 | unsigned int | | 927 | unsigned int |
850 | radix_tree_gang_lookup_tagged_node_reverse(struct radix_tree *t, uint64_t idx, | | 928 | radix_tree_gang_lookup_tagged_node_reverse(struct radix_tree *t, uint64_t idx, |
851 | void **results, unsigned int maxresults, radix_tree_tagid_t tagid) | | 929 | void **results, unsigned int maxresults, bool dense, unsigned int tagmask) |
852 | { | | 930 | { |
853 | struct radix_tree_path path; | | 931 | struct radix_tree_path path; |
854 | const unsigned int tagmask = tagid_to_mask(tagid); | | | |
855 | | | 932 | |
| | | 933 | KASSERT(tagmask != 0); |
856 | gang_lookup_init(t, idx, &path, tagmask); | | 934 | gang_lookup_init(t, idx, &path, tagmask); |
857 | return gang_lookup_scan(t, &path, results, maxresults, tagmask, true); | | 935 | return gang_lookup_scan(t, &path, results, maxresults, tagmask, true, |
| | | 936 | dense); |
858 | } | | 937 | } |
859 | | | 938 | |
860 | /* | | 939 | /* |
861 | * radix_tree_get_tag: | | 940 | * radix_tree_get_tag: |
862 | * | | 941 | * |
863 | * return if the tag is set for the node at the given index. (true if set) | | 942 | * Return the tagmask for the node at the given index. |
864 | * it's illegal to call this function for a node which has not been inserted. | | 943 | * |
| | | 944 | * It's illegal to call this function for a node which has not been inserted. |
865 | */ | | 945 | */ |
866 | | | 946 | |
867 | bool | | 947 | unsigned int |
868 | radix_tree_get_tag(struct radix_tree *t, uint64_t idx, | | 948 | radix_tree_get_tag(struct radix_tree *t, uint64_t idx, unsigned int tagmask) |
869 | radix_tree_tagid_t tagid) | | | |
870 | { | | 949 | { |
| | | 950 | /* |
| | | 951 | * the following two implementations should behave same. |
| | | 952 | * the former one was chosen because it seems faster. |
| | | 953 | */ |
871 | #if 1 | | 954 | #if 1 |
872 | const unsigned int tagmask = tagid_to_mask(tagid); | | | |
873 | void **vpp; | | 955 | void **vpp; |
874 | | | 956 | |
875 | vpp = radix_tree_lookup_ptr(t, idx, NULL, false, tagmask); | | 957 | vpp = radix_tree_lookup_ptr(t, idx, NULL, false, tagmask); |
876 | if (vpp == NULL) { | | 958 | if (vpp == NULL) { |
877 | return false; | | 959 | return false; |
878 | } | | 960 | } |
879 | KASSERT(*vpp != NULL); | | 961 | KASSERT(*vpp != NULL); |
880 | return (entry_tagmask(*vpp) & tagmask) != 0; | | 962 | return (entry_tagmask(*vpp) & tagmask); |
881 | #else | | 963 | #else |
882 | const unsigned int tagmask = tagid_to_mask(tagid); | | | |
883 | void **vpp; | | 964 | void **vpp; |
884 | | | 965 | |
885 | vpp = radix_tree_lookup_ptr(t, idx, NULL, false, 0); | | 966 | vpp = radix_tree_lookup_ptr(t, idx, NULL, false, 0); |
886 | KASSERT(vpp != NULL); | | 967 | KASSERT(vpp != NULL); |
887 | return (entry_tagmask(*vpp) & tagmask) != 0; | | 968 | return (entry_tagmask(*vpp) & tagmask); |
888 | #endif | | 969 | #endif |
889 | } | | 970 | } |
890 | | | 971 | |
891 | /* | | 972 | /* |
892 | * radix_tree_set_tag: | | 973 | * radix_tree_set_tag: |
893 | * | | 974 | * |
894 | * set the tag for the node at the given index. | | 975 | * Set the tag for the node at the given index. |
895 | * it's illegal to call this function for a node which has not been inserted. | | 976 | * |
| | | 977 | * It's illegal to call this function for a node which has not been inserted. |
| | | 978 | * It's illegal to call this function with tagmask 0. |
896 | */ | | 979 | */ |
897 | | | 980 | |
898 | void | | 981 | void |
899 | radix_tree_set_tag(struct radix_tree *t, uint64_t idx, | | 982 | radix_tree_set_tag(struct radix_tree *t, uint64_t idx, unsigned int tagmask) |
900 | radix_tree_tagid_t tagid) | | | |
901 | { | | 983 | { |
902 | struct radix_tree_path path; | | 984 | struct radix_tree_path path; |
903 | const unsigned int tagmask = tagid_to_mask(tagid); | | 985 | void **vpp __unused; |
904 | void **vpp; | | | |
905 | int i; | | 986 | int i; |
906 | | | 987 | |
907 | vpp = radix_tree_lookup_ptr(t, idx, &path, false, 0); | | 988 | KASSERT(tagmask != 0); |
| | | 989 | #if defined(DIAGNOSTIC) |
| | | 990 | vpp = |
| | | 991 | #endif /* defined(DIAGNOSTIC) */ |
| | | 992 | radix_tree_lookup_ptr(t, idx, &path, false, 0); |
908 | KASSERT(vpp != NULL); | | 993 | KASSERT(vpp != NULL); |
909 | KASSERT(*vpp != NULL); | | 994 | KASSERT(*vpp != NULL); |
910 | KASSERT(path.p_lastidx == t->t_height); | | 995 | KASSERT(path.p_lastidx == t->t_height); |
911 | KASSERT(vpp == path_pptr(t, &path, path.p_lastidx)); | | 996 | KASSERT(vpp == path_pptr(t, &path, path.p_lastidx)); |
912 | for (i = t->t_height; i >= 0; i--) { | | 997 | for (i = t->t_height; i >= 0; i--) { |
913 | void ** const pptr = (void **)path_pptr(t, &path, i); | | 998 | void ** const pptr = (void **)path_pptr(t, &path, i); |
914 | void *entry; | | 999 | void *entry; |
915 | | | 1000 | |
916 | KASSERT(pptr != NULL); | | 1001 | KASSERT(pptr != NULL); |
917 | entry = *pptr; | | 1002 | entry = *pptr; |
918 | if ((entry_tagmask(entry) & tagmask) != 0) { | | 1003 | if ((entry_tagmask(entry) & tagmask) != 0) { |
919 | break; | | 1004 | break; |
920 | } | | 1005 | } |
921 | *pptr = (void *)((uintptr_t)entry | tagmask); | | 1006 | *pptr = (void *)((uintptr_t)entry | tagmask); |
922 | } | | 1007 | } |
923 | } | | 1008 | } |
924 | | | 1009 | |
925 | /* | | 1010 | /* |
926 | * radix_tree_clear_tag: | | 1011 | * radix_tree_clear_tag: |
927 | * | | 1012 | * |
928 | * clear the tag for the node at the given index. | | 1013 | * Clear the tag for the node at the given index. |
929 | * it's illegal to call this function for a node which has not been inserted. | | 1014 | * |
| | | 1015 | * It's illegal to call this function for a node which has not been inserted. |
| | | 1016 | * It's illegal to call this function with tagmask 0. |
930 | */ | | 1017 | */ |
931 | | | 1018 | |
932 | void | | 1019 | void |
933 | radix_tree_clear_tag(struct radix_tree *t, uint64_t idx, | | 1020 | radix_tree_clear_tag(struct radix_tree *t, uint64_t idx, unsigned int tagmask) |
934 | radix_tree_tagid_t tagid) | | | |
935 | { | | 1021 | { |
936 | struct radix_tree_path path; | | 1022 | struct radix_tree_path path; |
937 | const unsigned int tagmask = tagid_to_mask(tagid); | | | |
938 | void **vpp; | | 1023 | void **vpp; |
939 | int i; | | 1024 | int i; |
940 | | | 1025 | |
| | | 1026 | KASSERT(tagmask != 0); |
941 | vpp = radix_tree_lookup_ptr(t, idx, &path, false, 0); | | 1027 | vpp = radix_tree_lookup_ptr(t, idx, &path, false, 0); |
942 | KASSERT(vpp != NULL); | | 1028 | KASSERT(vpp != NULL); |
943 | KASSERT(*vpp != NULL); | | 1029 | KASSERT(*vpp != NULL); |
944 | KASSERT(path.p_lastidx == t->t_height); | | 1030 | KASSERT(path.p_lastidx == t->t_height); |
945 | KASSERT(vpp == path_pptr(t, &path, path.p_lastidx)); | | 1031 | KASSERT(vpp == path_pptr(t, &path, path.p_lastidx)); |
946 | /* | | 1032 | /* |
947 | * if already cleared, nothing to do | | 1033 | * if already cleared, nothing to do |
948 | */ | | 1034 | */ |
949 | if ((entry_tagmask(*vpp) & tagmask) == 0) { | | 1035 | if ((entry_tagmask(*vpp) & tagmask) == 0) { |
950 | return; | | 1036 | return; |
951 | } | | 1037 | } |
952 | /* | | 1038 | /* |
953 | * clear the tag only if no children have the tag. | | 1039 | * clear the tag only if no children have the tag. |
954 | */ | | 1040 | */ |
955 | for (i = t->t_height; i >= 0; i--) { | | 1041 | for (i = t->t_height; i >= 0; i--) { |
956 | void ** const pptr = (void **)path_pptr(t, &path, i); | | 1042 | void ** const pptr = (void **)path_pptr(t, &path, i); |
957 | void *entry; | | 1043 | void *entry; |
958 | | | 1044 | |
959 | KASSERT(pptr != NULL); | | 1045 | KASSERT(pptr != NULL); |
960 | entry = *pptr; | | 1046 | entry = *pptr; |
961 | KASSERT((entry_tagmask(entry) & tagmask) != 0); | | 1047 | KASSERT((entry_tagmask(entry) & tagmask) != 0); |
962 | *pptr = entry_compose(entry_ptr(entry), | | 1048 | *pptr = entry_compose(entry_ptr(entry), |
963 | entry_tagmask(entry) & ~tagmask); | | 1049 | entry_tagmask(entry) & ~tagmask); |
964 | /* | | 1050 | /* |
965 | * check if we should proceed to process the next level. | | 1051 | * check if we should proceed to process the next level. |
966 | */ | | 1052 | */ |
967 | if (0 < i) { | | 1053 | if (0 < i) { |
968 | struct radix_tree_node *n = path_node(t, &path, i - 1); | | 1054 | struct radix_tree_node *n = path_node(t, &path, i - 1); |
969 | | | 1055 | |
970 | if ((any_children_tagmask(n) & tagmask) != 0) { | | 1056 | if ((any_children_tagmask(n) & tagmask) != 0) { |
971 | break; | | 1057 | break; |
972 | } | | 1058 | } |
973 | } | | 1059 | } |
974 | } | | 1060 | } |
975 | } | | 1061 | } |
976 | | | 1062 | |
977 | #if defined(UNITTEST) | | 1063 | #if defined(UNITTEST) |
978 | | | 1064 | |
979 | #include <inttypes.h> | | 1065 | #include <inttypes.h> |
980 | #include <stdio.h> | | 1066 | #include <stdio.h> |
981 | | | 1067 | |
982 | static void | | 1068 | static void |
983 | radix_tree_dump_node(const struct radix_tree *t, void *vp, | | 1069 | radix_tree_dump_node(const struct radix_tree *t, void *vp, |
984 | uint64_t offset, unsigned int height) | | 1070 | uint64_t offset, unsigned int height) |
985 | { | | 1071 | { |
986 | struct radix_tree_node *n; | | 1072 | struct radix_tree_node *n; |
987 | unsigned int i; | | 1073 | unsigned int i; |
988 | | | 1074 | |
989 | for (i = 0; i < t->t_height - height; i++) { | | 1075 | for (i = 0; i < t->t_height - height; i++) { |
990 | printf(" "); | | 1076 | printf(" "); |
991 | } | | 1077 | } |
992 | if (entry_tagmask(vp) == 0) { | | 1078 | if (entry_tagmask(vp) == 0) { |
993 | printf("[%" PRIu64 "] %p", offset, entry_ptr(vp)); | | 1079 | printf("[%" PRIu64 "] %p", offset, entry_ptr(vp)); |
994 | } else { | | 1080 | } else { |
995 | printf("[%" PRIu64 "] %p (tagmask=0x%x)", offset, entry_ptr(vp), | | 1081 | printf("[%" PRIu64 "] %p (tagmask=0x%x)", offset, entry_ptr(vp), |
996 | entry_tagmask(vp)); | | 1082 | entry_tagmask(vp)); |
997 | } | | 1083 | } |
998 | if (height == 0) { | | 1084 | if (height == 0) { |
999 | printf(" (leaf)\n"); | | 1085 | printf(" (leaf)\n"); |
1000 | return; | | 1086 | return; |
1001 | } | | 1087 | } |
1002 | n = entry_ptr(vp); | | 1088 | n = entry_ptr(vp); |
1003 | assert(any_children_tagmask(n) == entry_tagmask(vp)); | | 1089 | assert(any_children_tagmask(n) == entry_tagmask(vp)); |
1004 | printf(" (%u children)\n", n->n_nptrs); | | 1090 | printf(" (%u children)\n", n->n_nptrs); |
1005 | for (i = 0; i < __arraycount(n->n_ptrs); i++) { | | 1091 | for (i = 0; i < __arraycount(n->n_ptrs); i++) { |
1006 | void *c; | | 1092 | void *c; |
1007 | | | 1093 | |
1008 | c = n->n_ptrs[i]; | | 1094 | c = n->n_ptrs[i]; |
1009 | if (c == NULL) { | | 1095 | if (c == NULL) { |
1010 | continue; | | 1096 | continue; |
1011 | } | | 1097 | } |
1012 | radix_tree_dump_node(t, c, | | 1098 | radix_tree_dump_node(t, c, |
1013 | offset + i * (UINT64_C(1) << | | 1099 | offset + i * (UINT64_C(1) << |
1014 | (RADIX_TREE_BITS_PER_HEIGHT * (height - 1))), height - 1); | | 1100 | (RADIX_TREE_BITS_PER_HEIGHT * (height - 1))), height - 1); |
1015 | } | | 1101 | } |
1016 | } | | 1102 | } |
1017 | | | 1103 | |
1018 | void radix_tree_dump(const struct radix_tree *); | | 1104 | void radix_tree_dump(const struct radix_tree *); |
1019 | | | 1105 | |
1020 | void | | 1106 | void |
1021 | radix_tree_dump(const struct radix_tree *t) | | 1107 | radix_tree_dump(const struct radix_tree *t) |
1022 | { | | 1108 | { |
1023 | | | 1109 | |
1024 | printf("tree %p height=%u\n", t, t->t_height); | | 1110 | printf("tree %p height=%u\n", t, t->t_height); |
1025 | radix_tree_dump_node(t, t->t_root, 0, t->t_height); | | 1111 | radix_tree_dump_node(t, t->t_root, 0, t->t_height); |
1026 | } | | 1112 | } |
1027 | | | 1113 | |
1028 | static void | | 1114 | static void |
1029 | test1(void) | | 1115 | test1(void) |
1030 | { | | 1116 | { |
1031 | struct radix_tree s; | | 1117 | struct radix_tree s; |
1032 | struct radix_tree *t = &s; | | 1118 | struct radix_tree *t = &s; |
1033 | void *results[3]; | | 1119 | void *results[3]; |
1034 | | | 1120 | |
1035 | radix_tree_init_tree(t); | | 1121 | radix_tree_init_tree(t); |
1036 | radix_tree_dump(t); | | 1122 | radix_tree_dump(t); |
1037 | assert(radix_tree_lookup_node(t, 0) == NULL); | | 1123 | assert(radix_tree_lookup_node(t, 0) == NULL); |
1038 | assert(radix_tree_lookup_node(t, 1000) == NULL); | | 1124 | assert(radix_tree_lookup_node(t, 1000) == NULL); |
1039 | assert(radix_tree_gang_lookup_node(t, 0, results, 3) == 0); | | 1125 | assert(radix_tree_gang_lookup_node(t, 0, results, 3, false) == 0); |
1040 | assert(radix_tree_gang_lookup_node(t, 1000, results, 3) == 0); | | 1126 | assert(radix_tree_gang_lookup_node(t, 0, results, 3, true) == 0); |
1041 | assert(radix_tree_gang_lookup_node_reverse(t, 0, results, 3) == 0); | | 1127 | assert(radix_tree_gang_lookup_node(t, 1000, results, 3, false) == 0); |
1042 | assert(radix_tree_gang_lookup_node_reverse(t, 1000, results, 3) == 0); | | 1128 | assert(radix_tree_gang_lookup_node(t, 1000, results, 3, true) == 0); |
1043 | assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 3, 0) == 0); | | 1129 | assert(radix_tree_gang_lookup_node_reverse(t, 0, results, 3, false) == |
1044 | assert(radix_tree_gang_lookup_tagged_node(t, 1000, results, 3, 0) == 0); | | 1130 | 0); |
1045 | assert(radix_tree_gang_lookup_tagged_node_reverse(t, 0, results, 3, 0) | | 1131 | assert(radix_tree_gang_lookup_node_reverse(t, 0, results, 3, true) == |
| | | 1132 | 0); |
| | | 1133 | assert(radix_tree_gang_lookup_node_reverse(t, 1000, results, 3, false) |
| | | 1134 | == 0); |
| | | 1135 | assert(radix_tree_gang_lookup_node_reverse(t, 1000, results, 3, true) |
| | | 1136 | == 0); |
| | | 1137 | assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 3, false, 1) |
| | | 1138 | == 0); |
| | | 1139 | assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 3, true, 1) |
| | | 1140 | == 0); |
| | | 1141 | assert(radix_tree_gang_lookup_tagged_node(t, 1000, results, 3, false, 1) |
| | | 1142 | == 0); |
| | | 1143 | assert(radix_tree_gang_lookup_tagged_node(t, 1000, results, 3, true, 1) |
1046 | == 0); | | 1144 | == 0); |
| | | 1145 | assert(radix_tree_gang_lookup_tagged_node_reverse(t, 0, results, 3, |
| | | 1146 | false, 1) == 0); |
| | | 1147 | assert(radix_tree_gang_lookup_tagged_node_reverse(t, 0, results, 3, |
| | | 1148 | true, 1) == 0); |
1047 | assert(radix_tree_gang_lookup_tagged_node_reverse(t, 1000, results, 3, | | 1149 | assert(radix_tree_gang_lookup_tagged_node_reverse(t, 1000, results, 3, |
1048 | 0) == 0); | | 1150 | false, 1) == 0); |
| | | 1151 | assert(radix_tree_gang_lookup_tagged_node_reverse(t, 1000, results, 3, |
| | | 1152 | true, 1) == 0); |
1049 | assert(radix_tree_empty_tree_p(t)); | | 1153 | assert(radix_tree_empty_tree_p(t)); |
1050 | assert(radix_tree_empty_tagged_tree_p(t, 0)); | | | |
1051 | assert(radix_tree_empty_tagged_tree_p(t, 1)); | | 1154 | assert(radix_tree_empty_tagged_tree_p(t, 1)); |
| | | 1155 | assert(radix_tree_empty_tagged_tree_p(t, 2)); |
1052 | assert(radix_tree_insert_node(t, 0, (void *)0xdeadbea0) == 0); | | 1156 | assert(radix_tree_insert_node(t, 0, (void *)0xdeadbea0) == 0); |
1053 | assert(!radix_tree_empty_tree_p(t)); | | 1157 | assert(!radix_tree_empty_tree_p(t)); |
1054 | assert(radix_tree_empty_tagged_tree_p(t, 0)); | | | |
1055 | assert(radix_tree_empty_tagged_tree_p(t, 1)); | | 1158 | assert(radix_tree_empty_tagged_tree_p(t, 1)); |
| | | 1159 | assert(radix_tree_empty_tagged_tree_p(t, 2)); |
1056 | assert(radix_tree_lookup_node(t, 0) == (void *)0xdeadbea0); | | 1160 | assert(radix_tree_lookup_node(t, 0) == (void *)0xdeadbea0); |
1057 | assert(radix_tree_lookup_node(t, 1000) == NULL); | | 1161 | assert(radix_tree_lookup_node(t, 1000) == NULL); |
1058 | memset(results, 0, sizeof(results)); | | 1162 | memset(results, 0, sizeof(results)); |
1059 | assert(radix_tree_gang_lookup_node(t, 0, results, 3) == 1); | | 1163 | assert(radix_tree_gang_lookup_node(t, 0, results, 3, false) == 1); |
| | | 1164 | assert(results[0] == (void *)0xdeadbea0); |
| | | 1165 | memset(results, 0, sizeof(results)); |
| | | 1166 | assert(radix_tree_gang_lookup_node(t, 0, results, 3, true) == 1); |
1060 | assert(results[0] == (void *)0xdeadbea0); | | 1167 | assert(results[0] == (void *)0xdeadbea0); |
1061 | assert(radix_tree_gang_lookup_node(t, 1000, results, 3) == 0); | | 1168 | assert(radix_tree_gang_lookup_node(t, 1000, results, 3, false) == 0); |
| | | 1169 | assert(radix_tree_gang_lookup_node(t, 1000, results, 3, true) == 0); |
1062 | memset(results, 0, sizeof(results)); | | 1170 | memset(results, 0, sizeof(results)); |
1063 | assert(radix_tree_gang_lookup_node_reverse(t, 0, results, 3) == 1); | | 1171 | assert(radix_tree_gang_lookup_node_reverse(t, 0, results, 3, false) == |
| | | 1172 | 1); |
1064 | assert(results[0] == (void *)0xdeadbea0); | | 1173 | assert(results[0] == (void *)0xdeadbea0); |
1065 | memset(results, 0, sizeof(results)); | | 1174 | memset(results, 0, sizeof(results)); |
1066 | assert(radix_tree_gang_lookup_node_reverse(t, 1000, results, 3) == 1); | | 1175 | assert(radix_tree_gang_lookup_node_reverse(t, 0, results, 3, true) == |
| | | 1176 | 1); |
1067 | assert(results[0] == (void *)0xdeadbea0); | | 1177 | assert(results[0] == (void *)0xdeadbea0); |
1068 | assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 3, 0) | | 1178 | memset(results, 0, sizeof(results)); |
| | | 1179 | assert(radix_tree_gang_lookup_node_reverse(t, 1000, results, 3, false) |
| | | 1180 | == 1); |
| | | 1181 | assert(results[0] == (void *)0xdeadbea0); |
| | | 1182 | assert(radix_tree_gang_lookup_node_reverse(t, 1000, results, 3, true) |
| | | 1183 | == 0); |
| | | 1184 | assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 3, false, 1) |
1069 | == 0); | | 1185 | == 0); |
1070 | assert(radix_tree_gang_lookup_tagged_node_reverse(t, 0, results, 3, 0) | | 1186 | assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 3, true, 1) |
1071 | == 0); | | 1187 | == 0); |
| | | 1188 | assert(radix_tree_gang_lookup_tagged_node_reverse(t, 0, results, 3, |
| | | 1189 | false, 1) == 0); |
| | | 1190 | assert(radix_tree_gang_lookup_tagged_node_reverse(t, 0, results, 3, |
| | | 1191 | true, 1) == 0); |
1072 | assert(radix_tree_insert_node(t, 1000, (void *)0xdeadbea0) == 0); | | 1192 | assert(radix_tree_insert_node(t, 1000, (void *)0xdeadbea0) == 0); |
1073 | assert(radix_tree_remove_node(t, 0) == (void *)0xdeadbea0); | | 1193 | assert(radix_tree_remove_node(t, 0) == (void *)0xdeadbea0); |
1074 | assert(!radix_tree_empty_tree_p(t)); | | 1194 | assert(!radix_tree_empty_tree_p(t)); |
1075 | radix_tree_dump(t); | | 1195 | radix_tree_dump(t); |
1076 | assert(radix_tree_lookup_node(t, 0) == NULL); | | 1196 | assert(radix_tree_lookup_node(t, 0) == NULL); |
1077 | assert(radix_tree_lookup_node(t, 1000) == (void *)0xdeadbea0); | | 1197 | assert(radix_tree_lookup_node(t, 1000) == (void *)0xdeadbea0); |
1078 | memset(results, 0, sizeof(results)); | | 1198 | memset(results, 0, sizeof(results)); |
1079 | assert(radix_tree_gang_lookup_node(t, 0, results, 3) == 1); | | 1199 | assert(radix_tree_gang_lookup_node(t, 0, results, 3, false) == 1); |
1080 | assert(results[0] == (void *)0xdeadbea0); | | 1200 | assert(results[0] == (void *)0xdeadbea0); |
| | | 1201 | assert(radix_tree_gang_lookup_node(t, 0, results, 3, true) == 0); |
1081 | memset(results, 0, sizeof(results)); | | 1202 | memset(results, 0, sizeof(results)); |
1082 | assert(radix_tree_gang_lookup_node(t, 1000, results, 3) == 1); | | 1203 | assert(radix_tree_gang_lookup_node(t, 1000, results, 3, false) == 1); |
1083 | assert(results[0] == (void *)0xdeadbea0); | | 1204 | assert(results[0] == (void *)0xdeadbea0); |
1084 | assert(radix_tree_gang_lookup_node_reverse(t, 0, results, 3) == 0); | | | |
1085 | memset(results, 0, sizeof(results)); | | 1205 | memset(results, 0, sizeof(results)); |
1086 | assert(radix_tree_gang_lookup_node_reverse(t, 1000, results, 3) == 1); | | 1206 | assert(radix_tree_gang_lookup_node(t, 1000, results, 3, true) == 1); |
1087 | assert(results[0] == (void *)0xdeadbea0); | | 1207 | assert(results[0] == (void *)0xdeadbea0); |
1088 | assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 3, 0) | | 1208 | assert(radix_tree_gang_lookup_node_reverse(t, 0, results, 3, false) |
1089 | == 0); | | 1209 | == 0); |
1090 | assert(radix_tree_gang_lookup_tagged_node_reverse(t, 0, results, 3, 0) | | 1210 | assert(radix_tree_gang_lookup_node_reverse(t, 0, results, 3, true) |
1091 | == 0); | | 1211 | == 0); |
1092 | assert(!radix_tree_get_tag(t, 1000, 0)); | | 1212 | memset(results, 0, sizeof(results)); |
| | | 1213 | assert(radix_tree_gang_lookup_node_reverse(t, 1000, results, 3, false) |
| | | 1214 | == 1); |
| | | 1215 | memset(results, 0, sizeof(results)); |
| | | 1216 | assert(radix_tree_gang_lookup_node_reverse(t, 1000, results, 3, true) |
| | | 1217 | == 1); |
| | | 1218 | assert(results[0] == (void *)0xdeadbea0); |
| | | 1219 | assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 3, false, 1) |
| | | 1220 | == 0); |
| | | 1221 | assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 3, true, 1) |
| | | 1222 | == 0); |
| | | 1223 | assert(radix_tree_gang_lookup_tagged_node_reverse(t, 0, results, 3, |
| | | 1224 | false, 1) == 0); |
| | | 1225 | assert(radix_tree_gang_lookup_tagged_node_reverse(t, 0, results, 3, |
| | | 1226 | true, 1) == 0); |
| | | 1227 | assert(!radix_tree_get_tag(t, 1000, 1)); |
| | | 1228 | assert(!radix_tree_get_tag(t, 1000, 2)); |
| | | 1229 | assert(radix_tree_get_tag(t, 1000, 2 | 1) == 0); |
| | | 1230 | assert(radix_tree_empty_tagged_tree_p(t, 1)); |
| | | 1231 | assert(radix_tree_empty_tagged_tree_p(t, 2)); |
| | | 1232 | radix_tree_set_tag(t, 1000, 2); |
1093 | assert(!radix_tree_get_tag(t, 1000, 1)); | | 1233 | assert(!radix_tree_get_tag(t, 1000, 1)); |
1094 | assert(radix_tree_empty_tagged_tree_p(t, 0)); | | 1234 | assert(radix_tree_get_tag(t, 1000, 2)); |
| | | 1235 | assert(radix_tree_get_tag(t, 1000, 2 | 1) == 2); |
1095 | assert(radix_tree_empty_tagged_tree_p(t, 1)); | | 1236 | assert(radix_tree_empty_tagged_tree_p(t, 1)); |
1096 | radix_tree_set_tag(t, 1000, 1); | | 1237 | assert(!radix_tree_empty_tagged_tree_p(t, 2)); |
1097 | assert(!radix_tree_get_tag(t, 1000, 0)); | | | |
1098 | assert(radix_tree_get_tag(t, 1000, 1)); | | | |
1099 | assert(radix_tree_empty_tagged_tree_p(t, 0)); | | | |
1100 | assert(!radix_tree_empty_tagged_tree_p(t, 1)); | | | |
1101 | radix_tree_dump(t); | | 1238 | radix_tree_dump(t); |
1102 | assert(radix_tree_lookup_node(t, 1000) == (void *)0xdeadbea0); | | 1239 | assert(radix_tree_lookup_node(t, 1000) == (void *)0xdeadbea0); |
1103 | assert(radix_tree_insert_node(t, 0, (void *)0xbea0) == 0); | | 1240 | assert(radix_tree_insert_node(t, 0, (void *)0xbea0) == 0); |
1104 | radix_tree_dump(t); | | 1241 | radix_tree_dump(t); |
1105 | assert(radix_tree_lookup_node(t, 0) == (void *)0xbea0); | | 1242 | assert(radix_tree_lookup_node(t, 0) == (void *)0xbea0); |
1106 | assert(radix_tree_lookup_node(t, 1000) == (void *)0xdeadbea0); | | 1243 | assert(radix_tree_lookup_node(t, 1000) == (void *)0xdeadbea0); |
1107 | assert(radix_tree_insert_node(t, UINT64_C(10000000000), (void *)0xdea0) | | 1244 | assert(radix_tree_insert_node(t, UINT64_C(10000000000), (void *)0xdea0) |
1108 | == 0); | | 1245 | == 0); |
1109 | radix_tree_dump(t); | | 1246 | radix_tree_dump(t); |
1110 | assert(radix_tree_lookup_node(t, 0) == (void *)0xbea0); | | 1247 | assert(radix_tree_lookup_node(t, 0) == (void *)0xbea0); |
1111 | assert(radix_tree_lookup_node(t, 1000) == (void *)0xdeadbea0); | | 1248 | assert(radix_tree_lookup_node(t, 1000) == (void *)0xdeadbea0); |
1112 | assert(radix_tree_lookup_node(t, UINT64_C(10000000000)) == | | 1249 | assert(radix_tree_lookup_node(t, UINT64_C(10000000000)) == |
1113 | (void *)0xdea0); | | 1250 | (void *)0xdea0); |
1114 | radix_tree_dump(t); | | 1251 | radix_tree_dump(t); |
1115 | assert(!radix_tree_get_tag(t, 0, 1)); | | 1252 | assert(!radix_tree_get_tag(t, 0, 2)); |
1116 | assert(radix_tree_get_tag(t, 1000, 1)); | | 1253 | assert(radix_tree_get_tag(t, 1000, 2)); |
1117 | assert(!radix_tree_get_tag(t, UINT64_C(10000000000), 1)); | | 1254 | assert(!radix_tree_get_tag(t, UINT64_C(10000000000), 1)); |
1118 | radix_tree_set_tag(t, 0, 1);; | | 1255 | radix_tree_set_tag(t, 0, 2);; |
1119 | radix_tree_set_tag(t, UINT64_C(10000000000), 1); | | 1256 | radix_tree_set_tag(t, UINT64_C(10000000000), 2); |
1120 | radix_tree_dump(t); | | 1257 | radix_tree_dump(t); |
1121 | assert(radix_tree_get_tag(t, 0, 1)); | | 1258 | assert(radix_tree_get_tag(t, 0, 2)); |
1122 | assert(radix_tree_get_tag(t, 1000, 1)); | | 1259 | assert(radix_tree_get_tag(t, 1000, 2)); |
1123 | assert(radix_tree_get_tag(t, UINT64_C(10000000000), 1)); | | 1260 | assert(radix_tree_get_tag(t, UINT64_C(10000000000), 2)); |
1124 | radix_tree_clear_tag(t, 0, 1);; | | 1261 | radix_tree_clear_tag(t, 0, 2);; |
1125 | radix_tree_clear_tag(t, UINT64_C(10000000000), 1); | | 1262 | radix_tree_clear_tag(t, UINT64_C(10000000000), 2); |
1126 | radix_tree_dump(t); | | 1263 | radix_tree_dump(t); |
1127 | assert(!radix_tree_get_tag(t, 0, 1)); | | 1264 | assert(!radix_tree_get_tag(t, 0, 2)); |
1128 | assert(radix_tree_get_tag(t, 1000, 1)); | | 1265 | assert(radix_tree_get_tag(t, 1000, 2)); |
1129 | assert(!radix_tree_get_tag(t, UINT64_C(10000000000), 1)); | | 1266 | assert(!radix_tree_get_tag(t, UINT64_C(10000000000), 2)); |
1130 | radix_tree_dump(t); | | 1267 | radix_tree_dump(t); |
1131 | assert(radix_tree_replace_node(t, 1000, (void *)0x12345678) == | | 1268 | assert(radix_tree_replace_node(t, 1000, (void *)0x12345678) == |
1132 | (void *)0xdeadbea0); | | 1269 | (void *)0xdeadbea0); |
1133 | assert(!radix_tree_get_tag(t, 1000, 0)); | | 1270 | assert(!radix_tree_get_tag(t, 1000, 1)); |
1134 | assert(radix_tree_get_tag(t, 1000, 1)); | | 1271 | assert(radix_tree_get_tag(t, 1000, 2)); |
1135 | assert(radix_tree_gang_lookup_node(t, 0, results, 3) == 3); | | 1272 | assert(radix_tree_get_tag(t, 1000, 2 | 1) == 2); |
| | | 1273 | memset(results, 0, sizeof(results)); |
| | | 1274 | assert(radix_tree_gang_lookup_node(t, 0, results, 3, false) == 3); |
1136 | assert(results[0] == (void *)0xbea0); | | 1275 | assert(results[0] == (void *)0xbea0); |
1137 | assert(results[1] == (void *)0x12345678); | | 1276 | assert(results[1] == (void *)0x12345678); |
1138 | assert(results[2] == (void *)0xdea0); | | 1277 | assert(results[2] == (void *)0xdea0); |
1139 | assert(radix_tree_gang_lookup_node(t, 1, results, 3) == 2); | | 1278 | memset(results, 0, sizeof(results)); |
| | | 1279 | assert(radix_tree_gang_lookup_node(t, 0, results, 3, true) == 1); |
| | | 1280 | assert(results[0] == (void *)0xbea0); |
| | | 1281 | memset(results, 0, sizeof(results)); |
| | | 1282 | assert(radix_tree_gang_lookup_node(t, 1, results, 3, false) == 2); |
1140 | assert(results[0] == (void *)0x12345678); | | 1283 | assert(results[0] == (void *)0x12345678); |
1141 | assert(results[1] == (void *)0xdea0); | | 1284 | assert(results[1] == (void *)0xdea0); |
1142 | assert(radix_tree_gang_lookup_node(t, 1001, results, 3) == 1); | | 1285 | assert(radix_tree_gang_lookup_node(t, 1, results, 3, true) == 0); |
| | | 1286 | memset(results, 0, sizeof(results)); |
| | | 1287 | assert(radix_tree_gang_lookup_node(t, 1001, results, 3, false) == 1); |
1143 | assert(results[0] == (void *)0xdea0); | | 1288 | assert(results[0] == (void *)0xdea0); |
1144 | assert(radix_tree_gang_lookup_node(t, UINT64_C(10000000001), results, 3) | | 1289 | assert(radix_tree_gang_lookup_node(t, 1001, results, 3, true) == 0); |
1145 | == 0); | | 1290 | assert(radix_tree_gang_lookup_node(t, UINT64_C(10000000001), results, 3, |
| | | 1291 | false) == 0); |
| | | 1292 | assert(radix_tree_gang_lookup_node(t, UINT64_C(10000000001), results, 3, |
| | | 1293 | true) == 0); |
1146 | assert(radix_tree_gang_lookup_node(t, UINT64_C(1000000000000), results, | | 1294 | assert(radix_tree_gang_lookup_node(t, UINT64_C(1000000000000), results, |
1147 | 3) == 0); | | 1295 | 3, false) == 0); |
1148 | assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 100, 1) == 1); | | 1296 | assert(radix_tree_gang_lookup_node(t, UINT64_C(1000000000000), results, |
| | | 1297 | 3, true) == 0); |
| | | 1298 | memset(results, 0, sizeof(results)); |
| | | 1299 | assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 100, false, 2) |
| | | 1300 | == 1); |
1149 | assert(results[0] == (void *)0x12345678); | | 1301 | assert(results[0] == (void *)0x12345678); |
| | | 1302 | assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 100, true, 2) |
| | | 1303 | == 0); |
1150 | assert(entry_tagmask(t->t_root) != 0); | | 1304 | assert(entry_tagmask(t->t_root) != 0); |
1151 | assert(radix_tree_remove_node(t, 1000) == (void *)0x12345678); | | 1305 | assert(radix_tree_remove_node(t, 1000) == (void *)0x12345678); |
1152 | assert(entry_tagmask(t->t_root) == 0); | | 1306 | assert(entry_tagmask(t->t_root) == 0); |
1153 | radix_tree_dump(t); | | 1307 | radix_tree_dump(t); |
| | | 1308 | assert(radix_tree_insert_node(t, UINT64_C(10000000001), (void *)0xfff0) |
| | | 1309 | == 0); |
| | | 1310 | memset(results, 0, sizeof(results)); |
| | | 1311 | assert(radix_tree_gang_lookup_node(t, UINT64_C(10000000000), results, 3, |
| | | 1312 | false) == 2); |
| | | 1313 | assert(results[0] == (void *)0xdea0); |
| | | 1314 | assert(results[1] == (void *)0xfff0); |
| | | 1315 | memset(results, 0, sizeof(results)); |
| | | 1316 | assert(radix_tree_gang_lookup_node(t, UINT64_C(10000000000), results, 3, |
| | | 1317 | true) == 2); |
| | | 1318 | assert(results[0] == (void *)0xdea0); |
| | | 1319 | assert(results[1] == (void *)0xfff0); |
| | | 1320 | memset(results, 0, sizeof(results)); |
| | | 1321 | assert(radix_tree_gang_lookup_node_reverse(t, UINT64_C(10000000001), |
| | | 1322 | results, 3, false) == 3); |
| | | 1323 | assert(results[0] == (void *)0xfff0); |
| | | 1324 | assert(results[1] == (void *)0xdea0); |
| | | 1325 | assert(results[2] == (void *)0xbea0); |
| | | 1326 | memset(results, 0, sizeof(results)); |
| | | 1327 | assert(radix_tree_gang_lookup_node_reverse(t, UINT64_C(10000000001), |
| | | 1328 | results, 3, true) == 2); |
| | | 1329 | assert(results[0] == (void *)0xfff0); |
| | | 1330 | assert(results[1] == (void *)0xdea0); |
1154 | assert(radix_tree_remove_node(t, UINT64_C(10000000000)) == | | 1331 | assert(radix_tree_remove_node(t, UINT64_C(10000000000)) == |
1155 | (void *)0xdea0); | | 1332 | (void *)0xdea0); |
| | | 1333 | assert(radix_tree_remove_node(t, UINT64_C(10000000001)) == |
| | | 1334 | (void *)0xfff0); |
1156 | radix_tree_dump(t); | | 1335 | radix_tree_dump(t); |
1157 | assert(radix_tree_remove_node(t, 0) == (void *)0xbea0); | | 1336 | assert(radix_tree_remove_node(t, 0) == (void *)0xbea0); |
1158 | radix_tree_dump(t); | | 1337 | radix_tree_dump(t); |
1159 | radix_tree_fini_tree(t); | | 1338 | radix_tree_fini_tree(t); |
1160 | } | | 1339 | } |
1161 | | | 1340 | |
1162 | #include <sys/time.h> | | 1341 | #include <sys/time.h> |
1163 | | | 1342 | |
1164 | struct testnode { | | 1343 | struct testnode { |
1165 | uint64_t idx; | | 1344 | uint64_t idx; |
1166 | bool tagged[RADIX_TREE_TAG_ID_MAX]; | | 1345 | bool tagged[RADIX_TREE_TAG_ID_MAX]; |
1167 | }; | | 1346 | }; |
1168 | | | 1347 | |
1169 | static void | | 1348 | static void |
1170 | printops(const char *title, const char *name, int tag, unsigned int n, | | 1349 | printops(const char *title, const char *name, int tag, unsigned int n, |
1171 | const struct timeval *stv, const struct timeval *etv) | | 1350 | const struct timeval *stv, const struct timeval *etv) |
1172 | { | | 1351 | { |
1173 | uint64_t s = stv->tv_sec * 1000000 + stv->tv_usec; | | 1352 | uint64_t s = stv->tv_sec * 1000000 + stv->tv_usec; |
1174 | uint64_t e = etv->tv_sec * 1000000 + etv->tv_usec; | | 1353 | uint64_t e = etv->tv_sec * 1000000 + etv->tv_usec; |
1175 | | | 1354 | |
1176 | printf("RESULT %s %s %d %lf op/s\n", title, name, tag, | | 1355 | printf("RESULT %s %s %d %lf op/s\n", title, name, tag, |
1177 | (double)n / (e - s) * 1000000); | | 1356 | (double)n / (e - s) * 1000000); |
1178 | } | | 1357 | } |
1179 | | | 1358 | |
1180 | #define TEST2_GANG_LOOKUP_NODES 16 | | 1359 | #define TEST2_GANG_LOOKUP_NODES 16 |
1181 | | | 1360 | |
1182 | static bool | | 1361 | static bool |
1183 | test2_should_tag(unsigned int i, radix_tree_tagid_t tagid) | | 1362 | test2_should_tag(unsigned int i, unsigned int tagid) |
1184 | { | | 1363 | { |
1185 | | | 1364 | |
1186 | if (tagid == 0) { | | 1365 | if (tagid == 0) { |
1187 | return (i & 0x3) == 0; /* 25% */ | | 1366 | return (i % 4) == 0; /* 25% */ |
1188 | } else { | | 1367 | } else { |
1189 | return (i % 7) == 0; /* 14% */ | | 1368 | return (i % 7) == 0; /* 14% */ |
1190 | } | | 1369 | } |
| | | 1370 | return 1; |
| | | 1371 | } |
| | | 1372 | |
| | | 1373 | static void |
| | | 1374 | check_tag_count(const unsigned int *ntagged, unsigned int tagmask, |
| | | 1375 | unsigned int count) |
| | | 1376 | { |
| | | 1377 | unsigned int tag; |
| | | 1378 | |
| | | 1379 | for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) { |
| | | 1380 | if ((tagmask & (1 << tag)) == 0) { |
| | | 1381 | continue; |
| | | 1382 | } |
| | | 1383 | if (((tagmask - 1) & tagmask) == 0) { |
| | | 1384 | assert(count == ntagged[tag]); |
| | | 1385 | } else { |
| | | 1386 | assert(count >= ntagged[tag]); |
| | | 1387 | } |
| | | 1388 | } |
1191 | } | | 1389 | } |
1192 | | | 1390 | |
1193 | static void | | 1391 | static void |
1194 | test2(const char *title, bool dense) | | 1392 | test2(const char *title, bool dense) |
1195 | { | | 1393 | { |
1196 | struct radix_tree s; | | 1394 | struct radix_tree s; |
1197 | struct radix_tree *t = &s; | | 1395 | struct radix_tree *t = &s; |
1198 | struct testnode *n; | | 1396 | struct testnode *n; |
1199 | unsigned int i; | | 1397 | unsigned int i; |
1200 | unsigned int nnodes = 100000; | | 1398 | unsigned int nnodes = 100000; |
1201 | unsigned int removed; | | 1399 | unsigned int removed; |
1202 | radix_tree_tagid_t tag; | | 1400 | unsigned int tag; |
| | | 1401 | unsigned int tagmask; |
1203 | unsigned int ntagged[RADIX_TREE_TAG_ID_MAX]; | | 1402 | unsigned int ntagged[RADIX_TREE_TAG_ID_MAX]; |
1204 | struct testnode *nodes; | | 1403 | struct testnode *nodes; |
1205 | struct timeval stv; | | 1404 | struct timeval stv; |
1206 | struct timeval etv; | | 1405 | struct timeval etv; |
1207 | | | 1406 | |
1208 | nodes = malloc(nnodes * sizeof(*nodes)); | | 1407 | nodes = malloc(nnodes * sizeof(*nodes)); |
1209 | for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) { | | 1408 | for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) { |
1210 | ntagged[tag] = 0; | | 1409 | ntagged[tag] = 0; |
1211 | } | | 1410 | } |
1212 | radix_tree_init_tree(t); | | 1411 | radix_tree_init_tree(t); |
1213 | for (i = 0; i < nnodes; i++) { | | 1412 | for (i = 0; i < nnodes; i++) { |
1214 | n = &nodes[i]; | | 1413 | n = &nodes[i]; |
1215 | n->idx = random(); | | 1414 | n->idx = random(); |
1216 | if (sizeof(long) == 4) { | | 1415 | if (sizeof(long) == 4) { |
1217 | n->idx <<= 32; | | 1416 | n->idx <<= 32; |
1218 | n->idx |= (uint32_t)random(); | | 1417 | n->idx |= (uint32_t)random(); |
1219 | } | | 1418 | } |
1220 | if (dense) { | | 1419 | if (dense) { |
1221 | n->idx %= nnodes * 2; | | 1420 | n->idx %= nnodes * 2; |
1222 | } | | 1421 | } |
1223 | while (radix_tree_lookup_node(t, n->idx) != NULL) { | | 1422 | while (radix_tree_lookup_node(t, n->idx) != NULL) { |
1224 | n->idx++; | | 1423 | n->idx++; |
1225 | } | | 1424 | } |
1226 | radix_tree_insert_node(t, n->idx, n); | | 1425 | radix_tree_insert_node(t, n->idx, n); |
1227 | for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) { | | 1426 | for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) { |
| | | 1427 | tagmask = 1 << tag; |
| | | 1428 | |
1228 | n->tagged[tag] = test2_should_tag(i, tag); | | 1429 | n->tagged[tag] = test2_should_tag(i, tag); |
1229 | if (n->tagged[tag]) { | | 1430 | if (n->tagged[tag]) { |
1230 | radix_tree_set_tag(t, n->idx, tag); | | 1431 | radix_tree_set_tag(t, n->idx, tagmask); |
1231 | ntagged[tag]++; | | 1432 | ntagged[tag]++; |
1232 | } | | 1433 | } |
1233 | assert(n->tagged[tag] == | | 1434 | assert((n->tagged[tag] ? tagmask : 0) == |
1234 | radix_tree_get_tag(t, n->idx, tag)); | | 1435 | radix_tree_get_tag(t, n->idx, tagmask)); |
1235 | } | | 1436 | } |
1236 | } | | 1437 | } |
1237 | | | 1438 | |
1238 | gettimeofday(&stv, NULL); | | 1439 | gettimeofday(&stv, NULL); |
1239 | for (i = 0; i < nnodes; i++) { | | 1440 | for (i = 0; i < nnodes; i++) { |
1240 | n = &nodes[i]; | | 1441 | n = &nodes[i]; |
1241 | assert(radix_tree_lookup_node(t, n->idx) == n); | | 1442 | assert(radix_tree_lookup_node(t, n->idx) == n); |
1242 | } | | 1443 | } |
1243 | gettimeofday(&etv, NULL); | | 1444 | gettimeofday(&etv, NULL); |
1244 | printops(title, "lookup", 0, nnodes, &stv, &etv); | | 1445 | printops(title, "lookup", 0, nnodes, &stv, &etv); |
1245 | | | 1446 | |
1246 | for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) { | | 1447 | for (tagmask = 1; tagmask <= RADIX_TREE_TAG_MASK; tagmask ++) { |
1247 | unsigned int count = 0; | | 1448 | unsigned int count = 0; |
1248 | | | 1449 | |
1249 | gettimeofday(&stv, NULL); | | 1450 | gettimeofday(&stv, NULL); |
1250 | for (i = 0; i < nnodes; i++) { | | 1451 | for (i = 0; i < nnodes; i++) { |
1251 | bool tagged; | | 1452 | unsigned int tagged; |
1252 | | | 1453 | |
1253 | n = &nodes[i]; | | 1454 | n = &nodes[i]; |
1254 | tagged = radix_tree_get_tag(t, n->idx, tag); | | 1455 | tagged = radix_tree_get_tag(t, n->idx, tagmask); |
1255 | assert(n->tagged[tag] == tagged); | | 1456 | assert((tagged & ~tagmask) == 0); |
| | | 1457 | for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) { |
| | | 1458 | assert((tagmask & (1 << tag)) == 0 || |
| | | 1459 | n->tagged[tag] == !!(tagged & (1 << tag))); |
| | | 1460 | } |
1256 | if (tagged) { | | 1461 | if (tagged) { |
1257 | count++; | | 1462 | count++; |
1258 | } | | 1463 | } |
1259 | } | | 1464 | } |
1260 | gettimeofday(&etv, NULL); | | 1465 | gettimeofday(&etv, NULL); |
1261 | assert(ntagged[tag] == count); | | 1466 | check_tag_count(ntagged, tagmask, count); |
1262 | printops(title, "get_tag", tag, nnodes, &stv, &etv); | | 1467 | printops(title, "get_tag", tagmask, nnodes, &stv, &etv); |
1263 | } | | 1468 | } |
1264 | | | 1469 | |
1265 | gettimeofday(&stv, NULL); | | 1470 | gettimeofday(&stv, NULL); |
1266 | for (i = 0; i < nnodes; i++) { | | 1471 | for (i = 0; i < nnodes; i++) { |
1267 | n = &nodes[i]; | | 1472 | n = &nodes[i]; |
1268 | radix_tree_remove_node(t, n->idx); | | 1473 | radix_tree_remove_node(t, n->idx); |
1269 | } | | 1474 | } |
1270 | gettimeofday(&etv, NULL); | | 1475 | gettimeofday(&etv, NULL); |
1271 | printops(title, "remove", 0, nnodes, &stv, &etv); | | 1476 | printops(title, "remove", 0, nnodes, &stv, &etv); |
1272 | | | 1477 | |
1273 | gettimeofday(&stv, NULL); | | 1478 | gettimeofday(&stv, NULL); |
1274 | for (i = 0; i < nnodes; i++) { | | 1479 | for (i = 0; i < nnodes; i++) { |
1275 | n = &nodes[i]; | | 1480 | n = &nodes[i]; |
1276 | radix_tree_insert_node(t, n->idx, n); | | 1481 | radix_tree_insert_node(t, n->idx, n); |
1277 | } | | 1482 | } |
1278 | gettimeofday(&etv, NULL); | | 1483 | gettimeofday(&etv, NULL); |
1279 | printops(title, "insert", 0, nnodes, &stv, &etv); | | 1484 | printops(title, "insert", 0, nnodes, &stv, &etv); |
1280 | | | 1485 | |
1281 | for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) { | | 1486 | for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) { |
| | | 1487 | tagmask = 1 << tag; |
| | | 1488 | |
1282 | ntagged[tag] = 0; | | 1489 | ntagged[tag] = 0; |
1283 | gettimeofday(&stv, NULL); | | 1490 | gettimeofday(&stv, NULL); |
1284 | for (i = 0; i < nnodes; i++) { | | 1491 | for (i = 0; i < nnodes; i++) { |
1285 | n = &nodes[i]; | | 1492 | n = &nodes[i]; |
1286 | if (n->tagged[tag]) { | | 1493 | if (n->tagged[tag]) { |
1287 | radix_tree_set_tag(t, n->idx, tag); | | 1494 | radix_tree_set_tag(t, n->idx, tagmask); |
1288 | ntagged[tag]++; | | 1495 | ntagged[tag]++; |
1289 | } | | 1496 | } |
1290 | } | | 1497 | } |
1291 | gettimeofday(&etv, NULL); | | 1498 | gettimeofday(&etv, NULL); |
1292 | printops(title, "set_tag", tag, ntagged[tag], &stv, &etv); | | 1499 | printops(title, "set_tag", tag, ntagged[tag], &stv, &etv); |
1293 | } | | 1500 | } |
1294 | | | 1501 | |
1295 | gettimeofday(&stv, NULL); | | 1502 | gettimeofday(&stv, NULL); |
1296 | { | | 1503 | { |
1297 | struct testnode *results[TEST2_GANG_LOOKUP_NODES]; | | 1504 | struct testnode *results[TEST2_GANG_LOOKUP_NODES]; |
1298 | uint64_t nextidx; | | 1505 | uint64_t nextidx; |
1299 | unsigned int nfound; | | 1506 | unsigned int nfound; |
1300 | unsigned int total; | | 1507 | unsigned int total; |
1301 | | | 1508 | |
1302 | nextidx = 0; | | 1509 | nextidx = 0; |
1303 | total = 0; | | 1510 | total = 0; |
1304 | while ((nfound = radix_tree_gang_lookup_node(t, nextidx, | | 1511 | while ((nfound = radix_tree_gang_lookup_node(t, nextidx, |
1305 | (void *)results, __arraycount(results))) > 0) { | | 1512 | (void *)results, __arraycount(results), false)) > 0) { |
1306 | nextidx = results[nfound - 1]->idx + 1; | | 1513 | nextidx = results[nfound - 1]->idx + 1; |
1307 | total += nfound; | | 1514 | total += nfound; |
1308 | if (nextidx == 0) { | | 1515 | if (nextidx == 0) { |
1309 | break; | | 1516 | break; |
1310 | } | | 1517 | } |
1311 | } | | 1518 | } |
1312 | assert(total == nnodes); | | 1519 | assert(total == nnodes); |
1313 | } | | 1520 | } |
1314 | gettimeofday(&etv, NULL); | | 1521 | gettimeofday(&etv, NULL); |
1315 | printops(title, "ganglookup", 0, nnodes, &stv, &etv); | | 1522 | printops(title, "ganglookup", 0, nnodes, &stv, &etv); |
1316 | | | 1523 | |
1317 | gettimeofday(&stv, NULL); | | 1524 | gettimeofday(&stv, NULL); |
1318 | { | | 1525 | { |
1319 | struct testnode *results[TEST2_GANG_LOOKUP_NODES]; | | 1526 | struct testnode *results[TEST2_GANG_LOOKUP_NODES]; |
1320 | uint64_t nextidx; | | 1527 | uint64_t nextidx; |
1321 | unsigned int nfound; | | 1528 | unsigned int nfound; |
1322 | unsigned int total; | | 1529 | unsigned int total; |
1323 | | | 1530 | |
1324 | nextidx = UINT64_MAX; | | 1531 | nextidx = UINT64_MAX; |
1325 | total = 0; | | 1532 | total = 0; |
1326 | while ((nfound = radix_tree_gang_lookup_node_reverse(t, nextidx, | | 1533 | while ((nfound = radix_tree_gang_lookup_node_reverse(t, nextidx, |
1327 | (void *)results, __arraycount(results))) > 0) { | | 1534 | (void *)results, __arraycount(results), false)) > 0) { |
1328 | nextidx = results[nfound - 1]->idx - 1; | | 1535 | nextidx = results[nfound - 1]->idx - 1; |
1329 | total += nfound; | | 1536 | total += nfound; |
1330 | if (nextidx == UINT64_MAX) { | | 1537 | if (nextidx == UINT64_MAX) { |
1331 | break; | | 1538 | break; |
1332 | } | | 1539 | } |
1333 | } | | 1540 | } |
1334 | assert(total == nnodes); | | 1541 | assert(total == nnodes); |
1335 | } | | 1542 | } |
1336 | gettimeofday(&etv, NULL); | | 1543 | gettimeofday(&etv, NULL); |
1337 | printops(title, "ganglookup_reverse", 0, nnodes, &stv, &etv); | | 1544 | printops(title, "ganglookup_reverse", 0, nnodes, &stv, &etv); |
1338 | | | 1545 | |
1339 | for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) { | | 1546 | for (tagmask = 1; tagmask <= RADIX_TREE_TAG_MASK; tagmask ++) { |
| | | 1547 | unsigned int total = 0; |
| | | 1548 | |
1340 | gettimeofday(&stv, NULL); | | 1549 | gettimeofday(&stv, NULL); |
1341 | { | | 1550 | { |
1342 | struct testnode *results[TEST2_GANG_LOOKUP_NODES]; | | 1551 | struct testnode *results[TEST2_GANG_LOOKUP_NODES]; |
1343 | uint64_t nextidx; | | 1552 | uint64_t nextidx; |
1344 | unsigned int nfound; | | 1553 | unsigned int nfound; |
1345 | unsigned int total; | | | |
1346 | | | 1554 | |
1347 | nextidx = 0; | | 1555 | nextidx = 0; |
1348 | total = 0; | | | |
1349 | while ((nfound = radix_tree_gang_lookup_tagged_node(t, | | 1556 | while ((nfound = radix_tree_gang_lookup_tagged_node(t, |
1350 | nextidx, (void *)results, __arraycount(results), | | 1557 | nextidx, (void *)results, __arraycount(results), |
1351 | tag)) > 0) { | | 1558 | false, tagmask)) > 0) { |
1352 | nextidx = results[nfound - 1]->idx + 1; | | 1559 | nextidx = results[nfound - 1]->idx + 1; |
1353 | total += nfound; | | 1560 | total += nfound; |
1354 | } | | 1561 | } |
1355 | assert(total == ntagged[tag]); | | | |
1356 | } | | 1562 | } |
1357 | gettimeofday(&etv, NULL); | | 1563 | gettimeofday(&etv, NULL); |
1358 | printops(title, "ganglookup_tag", tag, ntagged[tag], &stv, | | 1564 | check_tag_count(ntagged, tagmask, total); |
1359 | &etv); | | 1565 | assert(tagmask != 0 || total == 0); |
| | | 1566 | printops(title, "ganglookup_tag", tagmask, total, &stv, &etv); |
1360 | } | | 1567 | } |
1361 | | | 1568 | |
1362 | for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) { | | 1569 | for (tagmask = 1; tagmask <= RADIX_TREE_TAG_MASK; tagmask ++) { |
| | | 1570 | unsigned int total = 0; |
| | | 1571 | |
1363 | gettimeofday(&stv, NULL); | | 1572 | gettimeofday(&stv, NULL); |
1364 | { | | 1573 | { |
1365 | struct testnode *results[TEST2_GANG_LOOKUP_NODES]; | | 1574 | struct testnode *results[TEST2_GANG_LOOKUP_NODES]; |
1366 | uint64_t nextidx; | | 1575 | uint64_t nextidx; |
1367 | unsigned int nfound; | | 1576 | unsigned int nfound; |
1368 | unsigned int total; | | | |
1369 | | | 1577 | |
1370 | nextidx = UINT64_MAX; | | 1578 | nextidx = UINT64_MAX; |
1371 | total = 0; | | | |
1372 | while ((nfound = | | 1579 | while ((nfound = |
1373 | radix_tree_gang_lookup_tagged_node_reverse(t, | | 1580 | radix_tree_gang_lookup_tagged_node_reverse(t, |
1374 | nextidx, (void *)results, __arraycount(results), | | 1581 | nextidx, (void *)results, __arraycount(results), |
1375 | tag)) > 0) { | | 1582 | false, tagmask)) > 0) { |
1376 | nextidx = results[nfound - 1]->idx - 1; | | 1583 | nextidx = results[nfound - 1]->idx - 1; |
1377 | total += nfound; | | 1584 | total += nfound; |
1378 | if (nextidx == UINT64_MAX) { | | 1585 | if (nextidx == UINT64_MAX) { |
1379 | break; | | 1586 | break; |
1380 | } | | 1587 | } |
1381 | } | | 1588 | } |
1382 | assert(total == ntagged[tag]); | | | |
1383 | } | | 1589 | } |
1384 | gettimeofday(&etv, NULL); | | 1590 | gettimeofday(&etv, NULL); |
1385 | printops(title, "ganglookup_tag_reverse", tag, ntagged[tag], | | 1591 | check_tag_count(ntagged, tagmask, total); |
| | | 1592 | assert(tagmask != 0 || total == 0); |
| | | 1593 | printops(title, "ganglookup_tag_reverse", tagmask, total, |
1386 | &stv, &etv); | | 1594 | &stv, &etv); |
1387 | } | | 1595 | } |
1388 | | | 1596 | |
1389 | removed = 0; | | 1597 | removed = 0; |
1390 | for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) { | | 1598 | for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) { |
1391 | unsigned int total; | | 1599 | unsigned int total; |
1392 | | | 1600 | |
1393 | total = 0; | | 1601 | total = 0; |
| | | 1602 | tagmask = 1 << tag; |
1394 | gettimeofday(&stv, NULL); | | 1603 | gettimeofday(&stv, NULL); |
1395 | { | | 1604 | { |
1396 | struct testnode *results[TEST2_GANG_LOOKUP_NODES]; | | 1605 | struct testnode *results[TEST2_GANG_LOOKUP_NODES]; |
1397 | uint64_t nextidx; | | 1606 | uint64_t nextidx; |
1398 | unsigned int nfound; | | 1607 | unsigned int nfound; |
1399 | | | 1608 | |
1400 | nextidx = 0; | | 1609 | nextidx = 0; |
1401 | while ((nfound = radix_tree_gang_lookup_tagged_node(t, | | 1610 | while ((nfound = radix_tree_gang_lookup_tagged_node(t, |
1402 | nextidx, (void *)results, __arraycount(results), | | 1611 | nextidx, (void *)results, __arraycount(results), |
1403 | tag)) > 0) { | | 1612 | false, tagmask)) > 0) { |
1404 | for (i = 0; i < nfound; i++) { | | 1613 | for (i = 0; i < nfound; i++) { |
1405 | radix_tree_remove_node(t, | | 1614 | radix_tree_remove_node(t, |
1406 | results[i]->idx); | | 1615 | results[i]->idx); |
1407 | } | | 1616 | } |
1408 | nextidx = results[nfound - 1]->idx + 1; | | 1617 | nextidx = results[nfound - 1]->idx + 1; |
1409 | total += nfound; | | 1618 | total += nfound; |
1410 | if (nextidx == 0) { | | 1619 | if (nextidx == 0) { |
1411 | break; | | 1620 | break; |
1412 | } | | 1621 | } |
1413 | } | | 1622 | } |
1414 | assert(tag != 0 || total == ntagged[tag]); | | | |
1415 | assert(total <= ntagged[tag]); | | | |
1416 | } | | 1623 | } |
1417 | gettimeofday(&etv, NULL); | | 1624 | gettimeofday(&etv, NULL); |
1418 | printops(title, "ganglookup_tag+remove", tag, total, &stv, | | 1625 | if (tag == 0) { |
| | | 1626 | check_tag_count(ntagged, tagmask, total); |
| | | 1627 | } else { |
| | | 1628 | assert(total <= ntagged[tag]); |
| | | 1629 | } |
| | | 1630 | printops(title, "ganglookup_tag+remove", tagmask, total, &stv, |
1419 | &etv); | | 1631 | &etv); |
1420 | removed += total; | | 1632 | removed += total; |
1421 | } | | 1633 | } |
1422 | | | 1634 | |
1423 | gettimeofday(&stv, NULL); | | 1635 | gettimeofday(&stv, NULL); |
1424 | { | | 1636 | { |
1425 | struct testnode *results[TEST2_GANG_LOOKUP_NODES]; | | 1637 | struct testnode *results[TEST2_GANG_LOOKUP_NODES]; |
1426 | uint64_t nextidx; | | 1638 | uint64_t nextidx; |
1427 | unsigned int nfound; | | 1639 | unsigned int nfound; |
1428 | unsigned int total; | | 1640 | unsigned int total; |
1429 | | | 1641 | |
1430 | nextidx = 0; | | 1642 | nextidx = 0; |
1431 | total = 0; | | 1643 | total = 0; |
1432 | while ((nfound = radix_tree_gang_lookup_node(t, nextidx, | | 1644 | while ((nfound = radix_tree_gang_lookup_node(t, nextidx, |
1433 | (void *)results, __arraycount(results))) > 0) { | | 1645 | (void *)results, __arraycount(results), false)) > 0) { |
1434 | for (i = 0; i < nfound; i++) { | | 1646 | for (i = 0; i < nfound; i++) { |
1435 | assert(results[i] == radix_tree_remove_node(t, | | 1647 | assert(results[i] == radix_tree_remove_node(t, |
1436 | results[i]->idx)); | | 1648 | results[i]->idx)); |
1437 | } | | 1649 | } |
1438 | nextidx = results[nfound - 1]->idx + 1; | | 1650 | nextidx = results[nfound - 1]->idx + 1; |
1439 | total += nfound; | | 1651 | total += nfound; |
1440 | if (nextidx == 0) { | | 1652 | if (nextidx == 0) { |
1441 | break; | | 1653 | break; |
1442 | } | | 1654 | } |
1443 | } | | 1655 | } |
1444 | assert(total == nnodes - removed); | | 1656 | assert(total == nnodes - removed); |
1445 | } | | 1657 | } |
1446 | gettimeofday(&etv, NULL); | | 1658 | gettimeofday(&etv, NULL); |
1447 | printops(title, "ganglookup+remove", 0, nnodes - removed, &stv, &etv); | | 1659 | printops(title, "ganglookup+remove", 0, nnodes - removed, &stv, &etv); |
1448 | | | 1660 | |
1449 | assert(radix_tree_empty_tree_p(t)); | | 1661 | assert(radix_tree_empty_tree_p(t)); |
1450 | assert(radix_tree_empty_tagged_tree_p(t, 0)); | | 1662 | for (tagmask = 1; tagmask <= RADIX_TREE_TAG_MASK; tagmask ++) { |
1451 | assert(radix_tree_empty_tagged_tree_p(t, 1)); | | 1663 | assert(radix_tree_empty_tagged_tree_p(t, tagmask)); |
| | | 1664 | } |
1452 | radix_tree_fini_tree(t); | | 1665 | radix_tree_fini_tree(t); |
1453 | free(nodes); | | 1666 | free(nodes); |
1454 | } | | 1667 | } |
1455 | | | 1668 | |
1456 | int | | 1669 | int |
1457 | main(int argc, char *argv[]) | | 1670 | main(int argc, char *argv[]) |
1458 | { | | 1671 | { |
1459 | | | 1672 | |
1460 | test1(); | | 1673 | test1(); |
1461 | test2("dense", true); | | 1674 | test2("dense", true); |
1462 | test2("sparse", false); | | 1675 | test2("sparse", false); |
1463 | return 0; | | 1676 | return 0; |
1464 | } | | 1677 | } |
1465 | | | 1678 | |
1466 | #endif /* defined(UNITTEST) */ | | 1679 | #endif /* defined(UNITTEST) */ |