xref: /minix3/common/lib/libc/gen/radixtree.c (revision f14fb602092e015ff630df58e17c2a9cd57d29b3)
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