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