 @@ -1,17 +1,17 @@
-/*	$NetBSD: radixtree.c,v 1.17 2011/11/02 13:49:43 yamt Exp $	*/
+/*	$NetBSD: radixtree.c,v 1.18 2019/12/05 18:32:25 ad Exp $	*/
 /*-
- * Copyright (c)2011 YAMAMOTO Takashi,
+ * Copyright (c)2011,2012,2013 YAMAMOTO Takashi,
  * All rights reserved.
+ *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  * 1. Redistributions of source code must retain the above copyright
  *    notice, this list of conditions and the following disclaimer.
  * 2. Redistributions in binary form must reproduce the above copyright
  *    notice, this list of conditions and the following disclaimer in the
  *    documentation and/or other materials provided with the distribution.
+ *
  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 @@ -19,76 +19,120 @@
  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  * SUCH DAMAGE.
  */
 /*
  * radixtree.c
+ *
- * this is an implementation of radix tree, whose keys are uint64_t and leafs
+ * Overview:
+ *
  * This is an implementation of radix tree, whose keys are uint64_t and leafs
  * are user provided pointers.
+ *
- * leaf nodes are just void * and this implementation doesn't care about
+ * Leaf nodes are just void * and this implementation doesn't care about
- * what they actually point to.  however, this implementation has an assumption
+ * what they actually point to.  However, this implementation has an assumption
- * about their alignment.  specifically, this implementation assumes that their
+ * about their alignment.  Specifically, this implementation assumes that their
- * 2 LSBs are zero and uses them internally.
+ * 2 LSBs are always zero and uses them for internal accounting.
+ *
- * intermediate nodes are automatically allocated and freed internally and
+ * Intermediate nodes and memory allocation:
  * basically users don't need to care about them.  only radix_tree_insert_node
- * function can allocate memory for intermediate nodes and thus can fail for
+ * Intermediate nodes are automatically allocated and freed internally and
- * ENOMEM.
+ * basically users don't need to care about them.  The allocation is done via
  * pool_cache_get(9) for _KERNEL, malloc(3) for userland, and alloc() for
- * efficiency:
+ * _STANDALONE environment.  Only radix_tree_insert_node function can allocate
- * it's designed to work efficiently with dense index distribution.
+ * memory for intermediate nodes and thus can fail for ENOMEM.
  * the memory consumption (number of necessary intermediate nodes)
- * heavily depends on index distribution.  basically, more dense index
+ * Memory Efficiency:
  * distribution consumes less nodes per item.
- * approximately,
+ * It's designed to work efficiently with dense index distribution.
- * the best case: about RADIX_TREE_PTR_PER_NODE items per intermediate node.
+ * The memory consumption (number of necessary intermediate nodes) heavily
- * the worst case: RADIX_TREE_MAX_HEIGHT intermediate nodes per item.
+ * depends on the index distribution.  Basically, more dense index distribution
  * consumes less nodes per item.  Approximately,
+ *
  *  - the best case: about RADIX_TREE_PTR_PER_NODE items per intermediate node.
  *    it would look like the following.
+ *
  *     root (t_height=1)
  *      |
  *      v
  *      [ | | | ]   (intermediate node.  RADIX_TREE_PTR_PER_NODE=4 in this fig)
  *       | | | |
  *       v v v v
  *       p p p p    (items)
+ *
  *  - the worst case: RADIX_TREE_MAX_HEIGHT intermediate nodes per item.
  *    it would look like the following if RADIX_TREE_MAX_HEIGHT=3.
+ *
  *     root (t_height=3)
  *      |
  *      v
  *      [ | | | ]
  *           |
  *           v
  *           [ | | | ]
  *                |
  *                v
  *                [ | | | ]
  *                   |
  *                   v
  *                   p
+ *
  * The height of tree (t_height) is dynamic.  It's smaller if only small
  * index values are used.  As an extreme case, if only index 0 is used,
  * the corresponding value is directly stored in the root of the tree
  * (struct radix_tree) without allocating any intermediate nodes.  In that
  * case, t_height=0.
+ *
  * Gang lookup:
+ *
- * gang lookup:
+ * This implementation provides a way to scan many nodes quickly via
  * this implementation provides a way to lookup many nodes quickly via
  * radix_tree_gang_lookup_node function and its varients.
+ *
- * tags:
+ * Tags:
  * this implementation provides tagging functionality to allow quick
- * scanning of a subset of leaf nodes.  leaf nodes are untagged when
+ * This implementation provides tagging functionality, which allows quick
- * inserted into the tree and can be tagged by radix_tree_set_tag function.
+ * scanning of a subset of leaf nodes.  Leaf nodes are untagged when inserted
- * radix_tree_gang_lookup_tagged_node function and its variants returns
+ * into the tree and can be tagged by radix_tree_set_tag function.
- * only leaf nodes with the given tag.  to reduce amount of nodes to visit for
+ * radix_tree_gang_lookup_tagged_node function and its variants returns only
  * leaf nodes with the given tag.  To reduce amount of nodes to visit for
  * these functions, this implementation keeps tagging information in internal
  * intermediate nodes and quickly skips uninterested parts of a tree.
+ *
  * A tree has RADIX_TREE_TAG_ID_MAX independent tag spaces, each of which are
  * identified by an zero-origin numbers, tagid.  For the current implementation,
  * RADIX_TREE_TAG_ID_MAX is 2.  A set of tags is described as a bitmask tagmask,
  * which is a bitwise OR of (1 << tagid).
  */
 #include <sys/cdefs.h>
 #if defined(_KERNEL) || defined(_STANDALONE)
-__KERNEL_RCSID(0, "$NetBSD: radixtree.c,v 1.17 2011/11/02 13:49:43 yamt Exp $");
+__KERNEL_RCSID(0, "$NetBSD: radixtree.c,v 1.18 2019/12/05 18:32:25 ad Exp $");
 #include <sys/param.h>
 #include <sys/errno.h>
 #include <sys/pool.h>
 #include <sys/radixtree.h>
 #include <lib/libkern/libkern.h>
 #if defined(_STANDALONE)
 #include <lib/libsa/stand.h>
 #endif /* defined(_STANDALONE) */
 #else /* defined(_KERNEL) || defined(_STANDALONE) */
-__RCSID("$NetBSD: radixtree.c,v 1.17 2011/11/02 13:49:43 yamt Exp $");
+__RCSID("$NetBSD: radixtree.c,v 1.18 2019/12/05 18:32:25 ad Exp $");
 #include <assert.h>
 #include <errno.h>
 #include <stdbool.h>
 #include <stdlib.h>
 #include <string.h>
 #if 1
 #define KASSERT assert
 #else
 #define KASSERT(a)	/* nothing */
 #endif
 #endif /* defined(_KERNEL) || defined(_STANDALONE) */
 #include <sys/radixtree.h>
 @@ -127,35 +171,26 @@ static inline bool
 entry_match_p(void *p, unsigned int tagmask)
+{
 	KASSERT(entry_ptr(p) != NULL || entry_tagmask(p) == 0);
 	if (p == NULL) {
 		return false;
+	}
 	if (tagmask == 0) {
 		return true;
+	}
 	return (entry_tagmask(p) & tagmask) != 0;
+}
 static inline unsigned int
 tagid_to_mask(radix_tree_tagid_t id)
 	KASSERT(id >= 0);
 	KASSERT(id < RADIX_TREE_TAG_ID_MAX);
 	return 1U << id;
 /*
  * radix_tree_node: an intermediate node
+ *
  * we don't care the type of leaf nodes.  they are just void *.
  */
 struct radix_tree_node {
 	void *n_ptrs[RADIX_TREE_PTR_PER_NODE];
 	unsigned int n_nptrs;	/* # of non-NULL pointers in n_ptrs */
 };
 /*
  * any_children_tagmask:
 @@ -209,63 +244,78 @@ path_pptr(const struct radix_tree *t, co
 static inline struct radix_tree_node *
 path_node(const struct radix_tree * t, const struct radix_tree_path *p,
     unsigned int height)
+{
 	KASSERT(height <= t->t_height);
 	return entry_ptr(*path_pptr(t, p, height));
+}
 /*
  * radix_tree_init_tree:
+ *
- * initialize a tree.
+ * Initialize a tree.
  */
 void
 radix_tree_init_tree(struct radix_tree *t)
+{
 	t->t_height = 0;
 	t->t_root = NULL;
+}
 /*
- * radix_tree_init_tree:
+ * radix_tree_fini_tree:
+ *
- * clean up a tree.
+ * Finish using a tree.
  */
 void
 radix_tree_fini_tree(struct radix_tree *t)
+{
 	KASSERT(t->t_root == NULL);
 	KASSERT(t->t_height == 0);
+}
 /*
  * radix_tree_empty_tree_p:
+ *
  * Return if the tree is empty.
  */
 bool
 radix_tree_empty_tree_p(struct radix_tree *t)
+{
 	return t->t_root == NULL;
+}
 /*
  * radix_tree_empty_tree_p:
+ *
  * Return true if the tree has any nodes with the given tag.  Otherwise
  * return false.
+ *
  * It's illegal to call this function with tagmask 0.
  */
 bool
-radix_tree_empty_tagged_tree_p(struct radix_tree *t, radix_tree_tagid_t tagid)
+radix_tree_empty_tagged_tree_p(struct radix_tree *t, unsigned int tagmask)
+{
 	const unsigned int tagmask = tagid_to_mask(tagid);
 	KASSERT(tagmask != 0);
 	return (entry_tagmask(t->t_root) & tagmask) == 0;
+}
 static void
 radix_tree_node_init(struct radix_tree_node *n)
+{
 	memset(n, 0, sizeof(*n));
+}
 #if defined(_KERNEL)
 pool_cache_t radix_tree_node_cache __read_mostly;
 @@ -308,26 +358,29 @@ radix_tree_node_clean_p(const struct rad
 		if (n->n_ptrs[i] != NULL) {
 			return false;
+		}
+	}
 	return true;
+}
 static struct radix_tree_node *
 radix_tree_alloc_node(void)
+{
 	struct radix_tree_node *n;
 #if defined(_KERNEL)
 	/*
 	 * note that pool_cache_get can block.
 	 */
 	n = pool_cache_get(radix_tree_node_cache, PR_NOWAIT);
 #else /* defined(_KERNEL) */
 #if defined(_STANDALONE)
 	n = alloc(sizeof(*n));
 #else /* defined(_STANDALONE) */
 	n = malloc(sizeof(*n));
 #endif /* defined(_STANDALONE) */
 	if (n != NULL) {
 		radix_tree_node_init(n);
+	}
 #endif /* defined(_KERNEL) */
 	KASSERT(n == NULL || radix_tree_node_clean_p(n));
 	return n;
 @@ -482,86 +535,88 @@ radix_tree_lookup_ptr(struct radix_tree
 			KASSERT(n->n_nptrs < RADIX_TREE_PTR_PER_NODE);
 			n->n_nptrs++;
+		}
+	}
 	if (path != NULL) {
 		path->p_lastidx = refs - path->p_refs;
+	}
 	return vpp;
+}
 /*
  * radix_tree_insert_node:
+ *
- * insert the node at idx.
+ * Insert the node at the given index.
  * it's illegal to insert NULL.
- * it's illegal to insert a non-aligned pointer.
+ * It's illegal to insert NULL.  It's illegal to insert a non-aligned pointer.
+ *
- * this function returns ENOMEM if necessary memory allocation failed.
+ * This function returns ENOMEM if necessary memory allocation failed.
- * otherwise, this function returns 0.
+ * Otherwise, this function returns 0.
+ *
- * note that inserting a node can involves memory allocation for intermediate
+ * Note that inserting a node can involves memory allocation for intermediate
- * nodes.  if _KERNEL, it's done with no-sleep IPL_NONE memory allocation.
+ * nodes.  If _KERNEL, it's done with no-sleep IPL_NONE memory allocation.
+ *
- * for the newly inserted node, all tags are cleared.
+ * For the newly inserted node, all tags are cleared.
  */
 int
 radix_tree_insert_node(struct radix_tree *t, uint64_t idx, void *p)
+{
 	void **vpp;
 	KASSERT(p != NULL);
-	KASSERT(entry_compose(p, 0) == p);
+	KASSERT(entry_tagmask(entry_compose(p, 0)) == 0);
 	vpp = radix_tree_lookup_ptr(t, idx, NULL, true, 0);
 	if (vpp == NULL) {
 		return ENOMEM;
+	}
 	KASSERT(*vpp == NULL);
 	*vpp = p;
 	return 0;
+}
 /*
  * radix_tree_replace_node:
+ *
- * replace a node at the given index with the given node.
+ * Replace a node at the given index with the given node and return the
- * return the old node.
+ * replaced one.
  * it's illegal to try to replace a node which has not been inserted.
  * It's illegal to try to replace a node which has not been inserted.
+ *
- * this function doesn't change tags.
+ * This function keeps tags intact.
  */
 void *
 radix_tree_replace_node(struct radix_tree *t, uint64_t idx, void *p)
+{
 	void **vpp;
 	void *oldp;
 	KASSERT(p != NULL);
-	KASSERT(entry_compose(p, 0) == p);
+	KASSERT(entry_tagmask(entry_compose(p, 0)) == 0);
 	vpp = radix_tree_lookup_ptr(t, idx, NULL, false, 0);
 	KASSERT(vpp != NULL);
 	oldp = *vpp;
 	KASSERT(oldp != NULL);
 	*vpp = entry_compose(p, entry_tagmask(*vpp));
 	return entry_ptr(oldp);
+}
 /*
  * radix_tree_remove_node:
+ *
- * remove the node at idx.
+ * Remove the node at the given index.
  * it's illegal to try to remove a node which has not been inserted.
  * It's illegal to try to remove a node which has not been inserted.
  */
 void *
 radix_tree_remove_node(struct radix_tree *t, uint64_t idx)
+{
 	struct radix_tree_path path;
 	void **vpp;
 	void *oldp;
 	int i;
 	vpp = radix_tree_lookup_ptr(t, idx, &path, false, 0);
 	KASSERT(vpp != NULL);
 	oldp = *vpp;
 @@ -615,68 +670,71 @@ radix_tree_remove_node(struct radix_tree
+		}
 		*pptr = entry_compose(n, newmask);
+	}
 	/*
 	 * XXX is it worth to try to reduce height?
 	 * if we do that, make radix_tree_grow rollback its change as well.
 	 */
 	return entry_ptr(oldp);
+}
 /*
  * radix_tree_lookup_node:
+ *
- * returns the node at idx.
+ * Returns the node at the given index.
- * returns NULL if nothing is found at idx.
+ * Returns NULL if nothing is found at the given index.
  */
 void *
 radix_tree_lookup_node(struct radix_tree *t, uint64_t idx)
+{
 	void **vpp;
 	vpp = radix_tree_lookup_ptr(t, idx, NULL, false, 0);
 	if (vpp == NULL) {
 		return NULL;
+	}
 	return entry_ptr(*vpp);
+}
 static inline void
 gang_lookup_init(struct radix_tree *t, uint64_t idx,
     struct radix_tree_path *path, const unsigned int tagmask)
+{
-	void **vpp;
+	void **vpp __unused;
-	vpp = radix_tree_lookup_ptr(t, idx, path, false, tagmask);
+#if defined(DIAGNOSTIC)
 	vpp =
 #endif /* defined(DIAGNOSTIC) */
 	radix_tree_lookup_ptr(t, idx, path, false, tagmask);
 	KASSERT(vpp == NULL ||
 	    vpp == path_pptr(t, path, path->p_lastidx));
 	KASSERT(&t->t_root == path_pptr(t, path, 0));
 	KASSERT(path->p_lastidx == RADIX_TREE_INVALID_HEIGHT ||
 	   path->p_lastidx == t->t_height ||
 	   !entry_match_p(*path_pptr(t, path, path->p_lastidx), tagmask));
+}
 /*
  * gang_lookup_scan:
+ *
  * a helper routine for radix_tree_gang_lookup_node and its variants.
  */
 static inline unsigned int
 __attribute__((__always_inline__))
 gang_lookup_scan(struct radix_tree *t, struct radix_tree_path *path,
-    void **results, unsigned int maxresults, const unsigned int tagmask,
+    void **results, const unsigned int maxresults, const unsigned int tagmask,
-    bool reverse)
+    const bool reverse, const bool dense)
+{
 	/*
 	 * we keep the path updated only for lastidx-1.
 	 * vpp is what path_pptr(t, path, lastidx) would be.
 	 */
 	void **vpp;
 	unsigned int nfound;
 	unsigned int lastidx;
 	/*
 	 * set up scan direction dependant constants so that we can iterate
 	 * n_ptrs as the following.
+	 *
 @@ -686,48 +744,53 @@ gang_lookup_scan(struct radix_tree *t, s
 	const int step = reverse ? -1 : 1;
 	const unsigned int first = reverse ? RADIX_TREE_PTR_PER_NODE - 1 : 0;
 	const unsigned int last = reverse ? 0 : RADIX_TREE_PTR_PER_NODE - 1;
 	const unsigned int guard = last + step;
 	KASSERT(maxresults > 0);
 	KASSERT(&t->t_root == path_pptr(t, path, 0));
 	lastidx = path->p_lastidx;
 	KASSERT(lastidx == RADIX_TREE_INVALID_HEIGHT ||
 	   lastidx == t->t_height ||
 	   !entry_match_p(*path_pptr(t, path, lastidx), tagmask));
 	nfound = 0;
 	if (lastidx == RADIX_TREE_INVALID_HEIGHT) {
-		if (reverse) {
+		/*
 		 * requested idx is beyond the right-most node.
 		 */
 		if (reverse && !dense) {
 			lastidx = 0;
 			vpp = path_pptr(t, path, lastidx);
 			goto descend;
+		}
 		return 0;
+	}
 	vpp = path_pptr(t, path, lastidx);
 	while (/*CONSTCOND*/true) {
 		struct radix_tree_node *n;
 		unsigned int i;
 		if (entry_match_p(*vpp, tagmask)) {
 			KASSERT(lastidx == t->t_height);
 			/*
 			 * record the matching non-NULL leaf.
 			 */
 			results[nfound] = entry_ptr(*vpp);
 			nfound++;
 			if (nfound == maxresults) {
 				return nfound;
+			}
 		} else if (dense) {
 			return nfound;
+		}
 scan_siblings:
 		/*
 		 * try to find the next matching non-NULL sibling.
 		 */
 		if (lastidx == 0) {
 			/*
 			 * the root has no siblings.
 			 * we've done.
 			 */
 			KASSERT(vpp == &t->t_root);
 			break;
+		}
 @@ -769,185 +832,208 @@ descend:
 			 */
 			path->p_refs[lastidx].pptr = vpp;
 			n = entry_ptr(*vpp);
 			vpp = &n->n_ptrs[first];
 			lastidx++;
+		}
+	}
 	return nfound;
+}
 /*
  * radix_tree_gang_lookup_node:
+ *
- * search nodes starting from idx in the ascending order.
+ * Scan the tree starting from the given index in the ascending order and
  * return found nodes.
+ *
  * results should be an array large enough to hold maxresults pointers.
- * returns the number of nodes found, up to maxresults.
+ * This function returns the number of nodes found, up to maxresults.
- * returning less than maxresults means there are no more nodes.
+ * Returning less than maxresults means there are no more nodes in the tree.
+ *
- * the result of this function is semantically equivalent to what could be
+ * If dense == true, this function stops scanning when it founds a hole of
- * obtained by repeated calls of radix_tree_lookup_node with increasing index.
+ * indexes.  I.e. an index for which radix_tree_lookup_node would returns NULL.
- * but this function is much faster when node indexes are distributed sparsely.
+ * If dense == false, this function skips holes and continue scanning until
  * maxresults nodes are found or it reaches the limit of the index range.
+ *
- * note that this function doesn't return exact values of node indexes of
+ * The result of this function is semantically equivalent to what could be
- * found nodes.  if they are important for a caller, it's the caller's
+ * obtained by repeated calls of radix_tree_lookup_node with increasing index.
- * responsibility to check them, typically by examinining the returned nodes
+ * but this function is expected to be computationally cheaper when looking up
- * using some caller-specific knowledge about them.
+ * multiple nodes at once.  Especially, it's expected to be much cheaper when
  * node indexes are distributed sparsely.
+ *
  * Note that this function doesn't return index values of found nodes.
  * Thus, in the case of dense == false, if index values are important for
  * a caller, it's the caller's responsibility to check them, typically
  * by examinining the returned nodes using some caller-specific knowledge
  * about them.
  * In the case of dense == true, a node returned via results[N] is always for
  * the index (idx + N).
  */
 unsigned int
 radix_tree_gang_lookup_node(struct radix_tree *t, uint64_t idx,
-    void **results, unsigned int maxresults)
+    void **results, unsigned int maxresults, bool dense)
+{
 	struct radix_tree_path path;
 	gang_lookup_init(t, idx, &path, 0);
-	return gang_lookup_scan(t, &path, results, maxresults, 0, false);
+	return gang_lookup_scan(t, &path, results, maxresults, 0, false, dense);
+}
 /*
  * radix_tree_gang_lookup_node_reverse:
+ *
- * same as radix_tree_gang_lookup_node except that this one scans the
+ * Same as radix_tree_gang_lookup_node except that this one scans the
- * tree in the reverse order.  ie. descending index values.
+ * tree in the reverse order.  I.e. descending index values.
  */
 unsigned int
 radix_tree_gang_lookup_node_reverse(struct radix_tree *t, uint64_t idx,
-    void **results, unsigned int maxresults)
+    void **results, unsigned int maxresults, bool dense)
+{
 	struct radix_tree_path path;
 	gang_lookup_init(t, idx, &path, 0);
-	return gang_lookup_scan(t, &path, results, maxresults, 0, true);
+	return gang_lookup_scan(t, &path, results, maxresults, 0, true, dense);
+}
 /*
  * radix_tree_gang_lookup_tagged_node:
+ *
- * same as radix_tree_gang_lookup_node except that this one only returns
+ * Same as radix_tree_gang_lookup_node except that this one only returns
  * nodes tagged with tagid.
+ *
  * It's illegal to call this function with tagmask 0.
  */
 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)
+    void **results, unsigned int maxresults, bool dense, unsigned int tagmask)
+{
 	struct radix_tree_path path;
 	const unsigned int tagmask = tagid_to_mask(tagid);
 	KASSERT(tagmask != 0);
 	gang_lookup_init(t, idx, &path, tagmask);
-	return gang_lookup_scan(t, &path, results, maxresults, tagmask, false);
+	return gang_lookup_scan(t, &path, results, maxresults, tagmask, false,
 	    dense);
+}
 /*
  * radix_tree_gang_lookup_tagged_node_reverse:
+ *
- * same as radix_tree_gang_lookup_tagged_node except that this one scans the
+ * Same as radix_tree_gang_lookup_tagged_node except that this one scans the
- * tree in the reverse order.  ie. descending index values.
+ * tree in the reverse order.  I.e. descending index values.
  */
 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)
+    void **results, unsigned int maxresults, bool dense, unsigned int tagmask)
+{
 	struct radix_tree_path path;
 	const unsigned int tagmask = tagid_to_mask(tagid);
 	KASSERT(tagmask != 0);
 	gang_lookup_init(t, idx, &path, tagmask);
-	return gang_lookup_scan(t, &path, results, maxresults, tagmask, true);
+	return gang_lookup_scan(t, &path, results, maxresults, tagmask, true,
 	    dense);
+}
 /*
  * radix_tree_get_tag:
+ *
- * return if the tag is set for the node at the given index.  (true if set)
+ * Return the tagmask for the node at the given index.
  * it's illegal to call this function for a node which has not been inserted.
  * It's illegal to call this function for a node which has not been inserted.
  */
-bool
+unsigned int
-radix_tree_get_tag(struct radix_tree *t, uint64_t idx,
+radix_tree_get_tag(struct radix_tree *t, uint64_t idx, unsigned int tagmask)
     radix_tree_tagid_t tagid)
+{
 	/*
 	 * the following two implementations should behave same.
 	 * the former one was chosen because it seems faster.
 	 */
 #if 1
 	const unsigned int tagmask = tagid_to_mask(tagid);
 	void **vpp;
 	vpp = radix_tree_lookup_ptr(t, idx, NULL, false, tagmask);
 	if (vpp == NULL) {
 		return false;
+	}
 	KASSERT(*vpp != NULL);
-	return (entry_tagmask(*vpp) & tagmask) != 0;
+	return (entry_tagmask(*vpp) & tagmask);
 #else
 	const unsigned int tagmask = tagid_to_mask(tagid);
 	void **vpp;
 	vpp = radix_tree_lookup_ptr(t, idx, NULL, false, 0);
 	KASSERT(vpp != NULL);
-	return (entry_tagmask(*vpp) & tagmask) != 0;
+	return (entry_tagmask(*vpp) & tagmask);
 #endif
+}
 /*
  * radix_tree_set_tag:
+ *
- * set the tag for the node at the given index.
+ * Set the tag for the node at the given index.
  * it's illegal to call this function for a node which has not been inserted.
  * It's illegal to call this function for a node which has not been inserted.
  * It's illegal to call this function with tagmask 0.
  */
 void
-radix_tree_set_tag(struct radix_tree *t, uint64_t idx,
+radix_tree_set_tag(struct radix_tree *t, uint64_t idx, unsigned int tagmask)
     radix_tree_tagid_t tagid)
+{
 	struct radix_tree_path path;
-	const unsigned int tagmask = tagid_to_mask(tagid);
+	void **vpp __unused;
 	void **vpp;
 	int i;
-	vpp = radix_tree_lookup_ptr(t, idx, &path, false, 0);
+	KASSERT(tagmask != 0);
 #if defined(DIAGNOSTIC)
 	vpp =
 #endif /* defined(DIAGNOSTIC) */
 	radix_tree_lookup_ptr(t, idx, &path, false, 0);
 	KASSERT(vpp != NULL);
 	KASSERT(*vpp != NULL);
 	KASSERT(path.p_lastidx == t->t_height);
 	KASSERT(vpp == path_pptr(t, &path, path.p_lastidx));
 	for (i = t->t_height; i >= 0; i--) {
 		void ** const pptr = (void **)path_pptr(t, &path, i);
 		void *entry;
 		KASSERT(pptr != NULL);
 		entry = *pptr;
 		if ((entry_tagmask(entry) & tagmask) != 0) {
 			break;
+		}
 		*pptr = (void *)((uintptr_t)entry | tagmask);
+	}
+}
 /*
  * radix_tree_clear_tag:
+ *
- * clear the tag for the node at the given index.
+ * Clear the tag for the node at the given index.
  * it's illegal to call this function for a node which has not been inserted.
  * It's illegal to call this function for a node which has not been inserted.
  * It's illegal to call this function with tagmask 0.
  */
 void
-radix_tree_clear_tag(struct radix_tree *t, uint64_t idx,
+radix_tree_clear_tag(struct radix_tree *t, uint64_t idx, unsigned int tagmask)
     radix_tree_tagid_t tagid)
+{
 	struct radix_tree_path path;
 	const unsigned int tagmask = tagid_to_mask(tagid);
 	void **vpp;
 	int i;
 	KASSERT(tagmask != 0);
 	vpp = radix_tree_lookup_ptr(t, idx, &path, false, 0);
 	KASSERT(vpp != NULL);
 	KASSERT(*vpp != NULL);
 	KASSERT(path.p_lastidx == t->t_height);
 	KASSERT(vpp == path_pptr(t, &path, path.p_lastidx));
 	/*
 	 * if already cleared, nothing to do
 	 */
 	if ((entry_tagmask(*vpp) & tagmask) == 0) {
 		return;
+	}
 	/*
 	 * clear the tag only if no children have the tag.
 @@ -1026,143 +1112,236 @@ radix_tree_dump(const struct radix_tree
+}
 static void
 test1(void)
+{
 	struct radix_tree s;
 	struct radix_tree *t = &s;
 	void *results[3];
 	radix_tree_init_tree(t);
 	radix_tree_dump(t);
 	assert(radix_tree_lookup_node(t, 0) == NULL);
 	assert(radix_tree_lookup_node(t, 1000) == NULL);
-	assert(radix_tree_gang_lookup_node(t, 0, results, 3) == 0);
+	assert(radix_tree_gang_lookup_node(t, 0, results, 3, false) == 0);
-	assert(radix_tree_gang_lookup_node(t, 1000, results, 3) == 0);
+	assert(radix_tree_gang_lookup_node(t, 0, results, 3, true) == 0);
-	assert(radix_tree_gang_lookup_node_reverse(t, 0, results, 3) == 0);
+	assert(radix_tree_gang_lookup_node(t, 1000, results, 3, false) == 0);
-	assert(radix_tree_gang_lookup_node_reverse(t, 1000, results, 3) == 0);
+	assert(radix_tree_gang_lookup_node(t, 1000, results, 3, true) == 0);
-	assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 3, 0) == 0);
+	assert(radix_tree_gang_lookup_node_reverse(t, 0, results, 3, false) ==
-	assert(radix_tree_gang_lookup_tagged_node(t, 1000, results, 3, 0) == 0);
+);
-	assert(radix_tree_gang_lookup_tagged_node_reverse(t, 0, results, 3, 0)
+	assert(radix_tree_gang_lookup_node_reverse(t, 0, results, 3, true) ==
 );
 	assert(radix_tree_gang_lookup_node_reverse(t, 1000, results, 3, false)
 	    == 0);
 	assert(radix_tree_gang_lookup_node_reverse(t, 1000, results, 3, true)
 	    == 0);
 	assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 3, false, 1)
 	    == 0);
 	assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 3, true, 1)
 	    == 0);
 	assert(radix_tree_gang_lookup_tagged_node(t, 1000, results, 3, false, 1)
 	    == 0);
 	assert(radix_tree_gang_lookup_tagged_node(t, 1000, results, 3, true, 1)
 	    == 0);
 	assert(radix_tree_gang_lookup_tagged_node_reverse(t, 0, results, 3,
 	    false, 1) == 0);
 	assert(radix_tree_gang_lookup_tagged_node_reverse(t, 0, results, 3,
 	    true, 1) == 0);
 	assert(radix_tree_gang_lookup_tagged_node_reverse(t, 1000, results, 3,
-) == 0);
+	    false, 1) == 0);
 	assert(radix_tree_gang_lookup_tagged_node_reverse(t, 1000, results, 3,
 	    true, 1) == 0);
 	assert(radix_tree_empty_tree_p(t));
 	assert(radix_tree_empty_tagged_tree_p(t, 0));
 	assert(radix_tree_empty_tagged_tree_p(t, 1));
 	assert(radix_tree_empty_tagged_tree_p(t, 2));
 	assert(radix_tree_insert_node(t, 0, (void *)0xdeadbea0) == 0);
 	assert(!radix_tree_empty_tree_p(t));
 	assert(radix_tree_empty_tagged_tree_p(t, 0));
 	assert(radix_tree_empty_tagged_tree_p(t, 1));
 	assert(radix_tree_empty_tagged_tree_p(t, 2));
 	assert(radix_tree_lookup_node(t, 0) == (void *)0xdeadbea0);
 	assert(radix_tree_lookup_node(t, 1000) == NULL);
 	memset(results, 0, sizeof(results));
-	assert(radix_tree_gang_lookup_node(t, 0, results, 3) == 1);
+	assert(radix_tree_gang_lookup_node(t, 0, results, 3, false) == 1);
 	assert(results[0] == (void *)0xdeadbea0);
 	memset(results, 0, sizeof(results));
 	assert(radix_tree_gang_lookup_node(t, 0, results, 3, true) == 1);
 	assert(results[0] == (void *)0xdeadbea0);
-	assert(radix_tree_gang_lookup_node(t, 1000, results, 3) == 0);
+	assert(radix_tree_gang_lookup_node(t, 1000, results, 3, false) == 0);
 	assert(radix_tree_gang_lookup_node(t, 1000, results, 3, true) == 0);
 	memset(results, 0, sizeof(results));
-	assert(radix_tree_gang_lookup_node_reverse(t, 0, results, 3) == 1);
+	assert(radix_tree_gang_lookup_node_reverse(t, 0, results, 3, false) ==
 );
 	assert(results[0] == (void *)0xdeadbea0);
 	memset(results, 0, sizeof(results));
-	assert(radix_tree_gang_lookup_node_reverse(t, 1000, results, 3) == 1);
+	assert(radix_tree_gang_lookup_node_reverse(t, 0, results, 3, true) ==
 );
 	assert(results[0] == (void *)0xdeadbea0);
-	assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 3, 0)
+	memset(results, 0, sizeof(results));
 	assert(radix_tree_gang_lookup_node_reverse(t, 1000, results, 3, false)
 	    == 1);
 	assert(results[0] == (void *)0xdeadbea0);
 	assert(radix_tree_gang_lookup_node_reverse(t, 1000, results, 3, true)
 	    == 0);
 	assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 3, false, 1)
 	    == 0);
-	assert(radix_tree_gang_lookup_tagged_node_reverse(t, 0, results, 3, 0)
+	assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 3, true, 1)
 	    == 0);
 	assert(radix_tree_gang_lookup_tagged_node_reverse(t, 0, results, 3,
 	    false, 1) == 0);
 	assert(radix_tree_gang_lookup_tagged_node_reverse(t, 0, results, 3,
 	    true, 1) == 0);
 	assert(radix_tree_insert_node(t, 1000, (void *)0xdeadbea0) == 0);
 	assert(radix_tree_remove_node(t, 0) == (void *)0xdeadbea0);
 	assert(!radix_tree_empty_tree_p(t));
 	radix_tree_dump(t);
 	assert(radix_tree_lookup_node(t, 0) == NULL);
 	assert(radix_tree_lookup_node(t, 1000) == (void *)0xdeadbea0);
 	memset(results, 0, sizeof(results));
-	assert(radix_tree_gang_lookup_node(t, 0, results, 3) == 1);
+	assert(radix_tree_gang_lookup_node(t, 0, results, 3, false) == 1);
 	assert(results[0] == (void *)0xdeadbea0);
 	assert(radix_tree_gang_lookup_node(t, 0, results, 3, true) == 0);
 	memset(results, 0, sizeof(results));
-	assert(radix_tree_gang_lookup_node(t, 1000, results, 3) == 1);
+	assert(radix_tree_gang_lookup_node(t, 1000, results, 3, false) == 1);
 	assert(results[0] == (void *)0xdeadbea0);
 	assert(radix_tree_gang_lookup_node_reverse(t, 0, results, 3) == 0);
 	memset(results, 0, sizeof(results));
-	assert(radix_tree_gang_lookup_node_reverse(t, 1000, results, 3) == 1);
+	assert(radix_tree_gang_lookup_node(t, 1000, results, 3, true) == 1);
 	assert(results[0] == (void *)0xdeadbea0);
-	assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 3, 0)
+	assert(radix_tree_gang_lookup_node_reverse(t, 0, results, 3, false)
 	    == 0);
-	assert(radix_tree_gang_lookup_tagged_node_reverse(t, 0, results, 3, 0)
+	assert(radix_tree_gang_lookup_node_reverse(t, 0, results, 3, true)
 	    == 0);
-	assert(!radix_tree_get_tag(t, 1000, 0));
+	memset(results, 0, sizeof(results));
 	assert(radix_tree_gang_lookup_node_reverse(t, 1000, results, 3, false)
 	    == 1);
 	memset(results, 0, sizeof(results));
 	assert(radix_tree_gang_lookup_node_reverse(t, 1000, results, 3, true)
 	    == 1);
 	assert(results[0] == (void *)0xdeadbea0);
 	assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 3, false, 1)
 	    == 0);
 	assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 3, true, 1)
 	    == 0);
 	assert(radix_tree_gang_lookup_tagged_node_reverse(t, 0, results, 3,
 	    false, 1) == 0);
 	assert(radix_tree_gang_lookup_tagged_node_reverse(t, 0, results, 3,
 	    true, 1) == 0);
 	assert(!radix_tree_get_tag(t, 1000, 1));
 	assert(!radix_tree_get_tag(t, 1000, 2));
 	assert(radix_tree_get_tag(t, 1000, 2 | 1) == 0);
 	assert(radix_tree_empty_tagged_tree_p(t, 1));
 	assert(radix_tree_empty_tagged_tree_p(t, 2));
 	radix_tree_set_tag(t, 1000, 2);
 	assert(!radix_tree_get_tag(t, 1000, 1));
-	assert(radix_tree_empty_tagged_tree_p(t, 0));
+	assert(radix_tree_get_tag(t, 1000, 2));
 	assert(radix_tree_get_tag(t, 1000, 2 | 1) == 2);
 	assert(radix_tree_empty_tagged_tree_p(t, 1));
-	radix_tree_set_tag(t, 1000, 1);
+	assert(!radix_tree_empty_tagged_tree_p(t, 2));
 	assert(!radix_tree_get_tag(t, 1000, 0));
 	assert(radix_tree_get_tag(t, 1000, 1));
 	assert(radix_tree_empty_tagged_tree_p(t, 0));
 	assert(!radix_tree_empty_tagged_tree_p(t, 1));
 	radix_tree_dump(t);
 	assert(radix_tree_lookup_node(t, 1000) == (void *)0xdeadbea0);
 	assert(radix_tree_insert_node(t, 0, (void *)0xbea0) == 0);
 	radix_tree_dump(t);
 	assert(radix_tree_lookup_node(t, 0) == (void *)0xbea0);
 	assert(radix_tree_lookup_node(t, 1000) == (void *)0xdeadbea0);
 	assert(radix_tree_insert_node(t, UINT64_C(10000000000), (void *)0xdea0)
 	    == 0);
 	radix_tree_dump(t);
 	assert(radix_tree_lookup_node(t, 0) == (void *)0xbea0);
 	assert(radix_tree_lookup_node(t, 1000) == (void *)0xdeadbea0);
 	assert(radix_tree_lookup_node(t, UINT64_C(10000000000)) ==
 	    (void *)0xdea0);
 	radix_tree_dump(t);
-	assert(!radix_tree_get_tag(t, 0, 1));
+	assert(!radix_tree_get_tag(t, 0, 2));
-	assert(radix_tree_get_tag(t, 1000, 1));
+	assert(radix_tree_get_tag(t, 1000, 2));
 	assert(!radix_tree_get_tag(t, UINT64_C(10000000000), 1));
-	radix_tree_set_tag(t, 0, 1);;
+	radix_tree_set_tag(t, 0, 2);;
-	radix_tree_set_tag(t, UINT64_C(10000000000), 1);
+	radix_tree_set_tag(t, UINT64_C(10000000000), 2);
 	radix_tree_dump(t);
-	assert(radix_tree_get_tag(t, 0, 1));
+	assert(radix_tree_get_tag(t, 0, 2));
-	assert(radix_tree_get_tag(t, 1000, 1));
+	assert(radix_tree_get_tag(t, 1000, 2));
-	assert(radix_tree_get_tag(t, UINT64_C(10000000000), 1));
+	assert(radix_tree_get_tag(t, UINT64_C(10000000000), 2));
-	radix_tree_clear_tag(t, 0, 1);;
+	radix_tree_clear_tag(t, 0, 2);;
-	radix_tree_clear_tag(t, UINT64_C(10000000000), 1);
+	radix_tree_clear_tag(t, UINT64_C(10000000000), 2);
 	radix_tree_dump(t);
-	assert(!radix_tree_get_tag(t, 0, 1));
+	assert(!radix_tree_get_tag(t, 0, 2));
-	assert(radix_tree_get_tag(t, 1000, 1));
+	assert(radix_tree_get_tag(t, 1000, 2));
-	assert(!radix_tree_get_tag(t, UINT64_C(10000000000), 1));
+	assert(!radix_tree_get_tag(t, UINT64_C(10000000000), 2));
 	radix_tree_dump(t);
 	assert(radix_tree_replace_node(t, 1000, (void *)0x12345678) ==
 	    (void *)0xdeadbea0);
-	assert(!radix_tree_get_tag(t, 1000, 0));
+	assert(!radix_tree_get_tag(t, 1000, 1));
-	assert(radix_tree_get_tag(t, 1000, 1));
+	assert(radix_tree_get_tag(t, 1000, 2));
-	assert(radix_tree_gang_lookup_node(t, 0, results, 3) == 3);
+	assert(radix_tree_get_tag(t, 1000, 2 | 1) == 2);
 	memset(results, 0, sizeof(results));
 	assert(radix_tree_gang_lookup_node(t, 0, results, 3, false) == 3);
 	assert(results[0] == (void *)0xbea0);
 	assert(results[1] == (void *)0x12345678);
 	assert(results[2] == (void *)0xdea0);
-	assert(radix_tree_gang_lookup_node(t, 1, results, 3) == 2);
+	memset(results, 0, sizeof(results));
 	assert(radix_tree_gang_lookup_node(t, 0, results, 3, true) == 1);
 	assert(results[0] == (void *)0xbea0);
 	memset(results, 0, sizeof(results));
 	assert(radix_tree_gang_lookup_node(t, 1, results, 3, false) == 2);
 	assert(results[0] == (void *)0x12345678);
 	assert(results[1] == (void *)0xdea0);
-	assert(radix_tree_gang_lookup_node(t, 1001, results, 3) == 1);
+	assert(radix_tree_gang_lookup_node(t, 1, results, 3, true) == 0);
 	memset(results, 0, sizeof(results));
 	assert(radix_tree_gang_lookup_node(t, 1001, results, 3, false) == 1);
 	assert(results[0] == (void *)0xdea0);
-	assert(radix_tree_gang_lookup_node(t, UINT64_C(10000000001), results, 3)
+	assert(radix_tree_gang_lookup_node(t, 1001, results, 3, true) == 0);
-	    == 0);
+	assert(radix_tree_gang_lookup_node(t, UINT64_C(10000000001), results, 3,
 	    false) == 0);
 	assert(radix_tree_gang_lookup_node(t, UINT64_C(10000000001), results, 3,
 	    true) == 0);
 	assert(radix_tree_gang_lookup_node(t, UINT64_C(1000000000000), results,
-) == 0);
+, false) == 0);
-	assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 100, 1) == 1);
+	assert(radix_tree_gang_lookup_node(t, UINT64_C(1000000000000), results,
 , true) == 0);
 	memset(results, 0, sizeof(results));
 	assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 100, false, 2)
 	    == 1);
 	assert(results[0] == (void *)0x12345678);
 	assert(radix_tree_gang_lookup_tagged_node(t, 0, results, 100, true, 2)
 	    == 0);
 	assert(entry_tagmask(t->t_root) != 0);
 	assert(radix_tree_remove_node(t, 1000) == (void *)0x12345678);
 	assert(entry_tagmask(t->t_root) == 0);
 	radix_tree_dump(t);
 	assert(radix_tree_insert_node(t, UINT64_C(10000000001), (void *)0xfff0)
 	    == 0);
 	memset(results, 0, sizeof(results));
 	assert(radix_tree_gang_lookup_node(t, UINT64_C(10000000000), results, 3,
 	    false) == 2);
 	assert(results[0] == (void *)0xdea0);
 	assert(results[1] == (void *)0xfff0);
 	memset(results, 0, sizeof(results));
 	assert(radix_tree_gang_lookup_node(t, UINT64_C(10000000000), results, 3,
 	    true) == 2);
 	assert(results[0] == (void *)0xdea0);
 	assert(results[1] == (void *)0xfff0);
 	memset(results, 0, sizeof(results));
 	assert(radix_tree_gang_lookup_node_reverse(t, UINT64_C(10000000001),
 	    results, 3, false) == 3);
 	assert(results[0] == (void *)0xfff0);
 	assert(results[1] == (void *)0xdea0);
 	assert(results[2] == (void *)0xbea0);
 	memset(results, 0, sizeof(results));
 	assert(radix_tree_gang_lookup_node_reverse(t, UINT64_C(10000000001),
 	    results, 3, true) == 2);
 	assert(results[0] == (void *)0xfff0);
 	assert(results[1] == (void *)0xdea0);
 	assert(radix_tree_remove_node(t, UINT64_C(10000000000)) ==
 	    (void *)0xdea0);
 	assert(radix_tree_remove_node(t, UINT64_C(10000000001)) ==
 	    (void *)0xfff0);
 	radix_tree_dump(t);
 	assert(radix_tree_remove_node(t, 0) == (void *)0xbea0);
 	radix_tree_dump(t);
 	radix_tree_fini_tree(t);
+}
 #include <sys/time.h>
 struct testnode {
 	uint64_t idx;
 	bool tagged[RADIX_TREE_TAG_ID_MAX];
 };
 @@ -1170,295 +1349,329 @@ static void
 printops(const char *title, const char *name, int tag, unsigned int n,
     const struct timeval *stv, const struct timeval *etv)
+{
 	uint64_t s = stv->tv_sec * 1000000 + stv->tv_usec;
 	uint64_t e = etv->tv_sec * 1000000 + etv->tv_usec;
 	printf("RESULT %s %s %d %lf op/s\n", title, name, tag,
 	    (double)n / (e - s) * 1000000);
+}
 #define	TEST2_GANG_LOOKUP_NODES	16
 static bool
-test2_should_tag(unsigned int i, radix_tree_tagid_t tagid)
+test2_should_tag(unsigned int i, unsigned int tagid)
+{
 	if (tagid == 0) {
-		return (i & 0x3) == 0;	/* 25% */
+		return (i % 4) == 0;	/* 25% */
 	} else {
 		return (i % 7) == 0;	/* 14% */
+	}
 	return 1;
+}
 static void
 check_tag_count(const unsigned int *ntagged, unsigned int tagmask,
     unsigned int count)
+{
 	unsigned int tag;
 	for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) {
 		if ((tagmask & (1 << tag)) == 0) {
 			continue;
+		}
 		if (((tagmask - 1) & tagmask) == 0) {
 			assert(count == ntagged[tag]);
 		} else {
 			assert(count >= ntagged[tag]);
+		}
+	}
+}
 static void
 test2(const char *title, bool dense)
+{
 	struct radix_tree s;
 	struct radix_tree *t = &s;
 	struct testnode *n;
 	unsigned int i;
 	unsigned int nnodes = 100000;
 	unsigned int removed;
-	radix_tree_tagid_t tag;
+	unsigned int tag;
 	unsigned int tagmask;
 	unsigned int ntagged[RADIX_TREE_TAG_ID_MAX];
 	struct testnode *nodes;
 	struct timeval stv;
 	struct timeval etv;
 	nodes = malloc(nnodes * sizeof(*nodes));
 	for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) {
 		ntagged[tag] = 0;
+	}
 	radix_tree_init_tree(t);
 	for (i = 0; i < nnodes; i++) {
 		n = &nodes[i];
 		n->idx = random();
 		if (sizeof(long) == 4) {
 			n->idx <<= 32;
 			n->idx |= (uint32_t)random();
+		}
 		if (dense) {
 			n->idx %= nnodes * 2;
+		}
 		while (radix_tree_lookup_node(t, n->idx) != NULL) {
 			n->idx++;
+		}
 		radix_tree_insert_node(t, n->idx, n);
 		for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) {
 			tagmask = 1 << tag;
 			n->tagged[tag] = test2_should_tag(i, tag);
 			if (n->tagged[tag]) {
-				radix_tree_set_tag(t, n->idx, tag);
+				radix_tree_set_tag(t, n->idx, tagmask);
 				ntagged[tag]++;
+			}
-			assert(n->tagged[tag] ==
+			assert((n->tagged[tag] ? tagmask : 0) ==
-			    radix_tree_get_tag(t, n->idx, tag));
+			    radix_tree_get_tag(t, n->idx, tagmask));
+		}
+	}
 	gettimeofday(&stv, NULL);
 	for (i = 0; i < nnodes; i++) {
 		n = &nodes[i];
 		assert(radix_tree_lookup_node(t, n->idx) == n);
+	}
 	gettimeofday(&etv, NULL);
 	printops(title, "lookup", 0, nnodes, &stv, &etv);
-	for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) {
+	for (tagmask = 1; tagmask <= RADIX_TREE_TAG_MASK; tagmask ++) {
 		unsigned int count = 0;
 		gettimeofday(&stv, NULL);
 		for (i = 0; i < nnodes; i++) {
-			bool tagged;
+			unsigned int tagged;
 			n = &nodes[i];
-			tagged = radix_tree_get_tag(t, n->idx, tag);
+			tagged = radix_tree_get_tag(t, n->idx, tagmask);
-			assert(n->tagged[tag] == tagged);
+			assert((tagged & ~tagmask) == 0);
 			for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) {
 				assert((tagmask & (1 << tag)) == 0 ||
 				    n->tagged[tag] == !!(tagged & (1 << tag)));
+			}
 			if (tagged) {
 				count++;
+			}
+		}
 		gettimeofday(&etv, NULL);
-		assert(ntagged[tag] == count);
+		check_tag_count(ntagged, tagmask, count);
-		printops(title, "get_tag", tag, nnodes, &stv, &etv);
+		printops(title, "get_tag", tagmask, nnodes, &stv, &etv);
+	}
 	gettimeofday(&stv, NULL);
 	for (i = 0; i < nnodes; i++) {
 		n = &nodes[i];
 		radix_tree_remove_node(t, n->idx);
+	}
 	gettimeofday(&etv, NULL);
 	printops(title, "remove", 0, nnodes, &stv, &etv);
 	gettimeofday(&stv, NULL);
 	for (i = 0; i < nnodes; i++) {
 		n = &nodes[i];
 		radix_tree_insert_node(t, n->idx, n);
+	}
 	gettimeofday(&etv, NULL);
 	printops(title, "insert", 0, nnodes, &stv, &etv);
 	for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) {
 		tagmask = 1 << tag;
 		ntagged[tag] = 0;
 		gettimeofday(&stv, NULL);
 		for (i = 0; i < nnodes; i++) {
 			n = &nodes[i];
 			if (n->tagged[tag]) {
-				radix_tree_set_tag(t, n->idx, tag);
+				radix_tree_set_tag(t, n->idx, tagmask);
 				ntagged[tag]++;
+			}
+		}
 		gettimeofday(&etv, NULL);
 		printops(title, "set_tag", tag, ntagged[tag], &stv, &etv);
+	}
 	gettimeofday(&stv, NULL);
+	{
 		struct testnode *results[TEST2_GANG_LOOKUP_NODES];
 		uint64_t nextidx;
 		unsigned int nfound;
 		unsigned int total;
 		nextidx = 0;
 		total = 0;
 		while ((nfound = radix_tree_gang_lookup_node(t, nextidx,
-		    (void *)results, __arraycount(results))) > 0) {
+		    (void *)results, __arraycount(results), false)) > 0) {
 			nextidx = results[nfound - 1]->idx + 1;
 			total += nfound;
 			if (nextidx == 0) {
 				break;
+			}
+		}
 		assert(total == nnodes);
+	}
 	gettimeofday(&etv, NULL);
 	printops(title, "ganglookup", 0, nnodes, &stv, &etv);
 	gettimeofday(&stv, NULL);
+	{
 		struct testnode *results[TEST2_GANG_LOOKUP_NODES];
 		uint64_t nextidx;
 		unsigned int nfound;
 		unsigned int total;
 		nextidx = UINT64_MAX;
 		total = 0;
 		while ((nfound = radix_tree_gang_lookup_node_reverse(t, nextidx,
-		    (void *)results, __arraycount(results))) > 0) {
+		    (void *)results, __arraycount(results), false)) > 0) {
 			nextidx = results[nfound - 1]->idx - 1;
 			total += nfound;
 			if (nextidx == UINT64_MAX) {
 				break;
+			}
+		}
 		assert(total == nnodes);
+	}
 	gettimeofday(&etv, NULL);
 	printops(title, "ganglookup_reverse", 0, nnodes, &stv, &etv);
-	for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) {
+	for (tagmask = 1; tagmask <= RADIX_TREE_TAG_MASK; tagmask ++) {
 		unsigned int total = 0;
 		gettimeofday(&stv, NULL);
+		{
 			struct testnode *results[TEST2_GANG_LOOKUP_NODES];
 			uint64_t nextidx;
 			unsigned int nfound;
 			unsigned int total;
 			nextidx = 0;
 			total = 0;
 			while ((nfound = radix_tree_gang_lookup_tagged_node(t,
 			    nextidx, (void *)results, __arraycount(results),
-			    tag)) > 0) {
+			    false, tagmask)) > 0) {
 				nextidx = results[nfound - 1]->idx + 1;
 				total += nfound;
+			}
 			assert(total == ntagged[tag]);
+		}
 		gettimeofday(&etv, NULL);
-		printops(title, "ganglookup_tag", tag, ntagged[tag], &stv,
+		check_tag_count(ntagged, tagmask, total);
-		    &etv);
+		assert(tagmask != 0 || total == 0);
 		printops(title, "ganglookup_tag", tagmask, total, &stv, &etv);
+	}
-	for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) {
+	for (tagmask = 1; tagmask <= RADIX_TREE_TAG_MASK; tagmask ++) {
 		unsigned int total = 0;
 		gettimeofday(&stv, NULL);
+		{
 			struct testnode *results[TEST2_GANG_LOOKUP_NODES];
 			uint64_t nextidx;
 			unsigned int nfound;
 			unsigned int total;
 			nextidx = UINT64_MAX;
 			total = 0;
 			while ((nfound =
 			    radix_tree_gang_lookup_tagged_node_reverse(t,
 			    nextidx, (void *)results, __arraycount(results),
-			    tag)) > 0) {
+			    false, tagmask)) > 0) {
 				nextidx = results[nfound - 1]->idx - 1;
 				total += nfound;
 				if (nextidx == UINT64_MAX) {
 					break;
+				}
+			}
 			assert(total == ntagged[tag]);
+		}
 		gettimeofday(&etv, NULL);
-		printops(title, "ganglookup_tag_reverse", tag, ntagged[tag],
+		check_tag_count(ntagged, tagmask, total);
 		assert(tagmask != 0 || total == 0);
 		printops(title, "ganglookup_tag_reverse", tagmask, total,
 		    &stv, &etv);
+	}
 	removed = 0;
 	for (tag = 0; tag < RADIX_TREE_TAG_ID_MAX; tag++) {
 		unsigned int total;
 		total = 0;
 		tagmask = 1 << tag;
 		gettimeofday(&stv, NULL);
+		{
 			struct testnode *results[TEST2_GANG_LOOKUP_NODES];
 			uint64_t nextidx;
 			unsigned int nfound;
 			nextidx = 0;
 			while ((nfound = radix_tree_gang_lookup_tagged_node(t,
 			    nextidx, (void *)results, __arraycount(results),
-			    tag)) > 0) {
+			    false, tagmask)) > 0) {
 				for (i = 0; i < nfound; i++) {
 					radix_tree_remove_node(t,
 					    results[i]->idx);
+				}
 				nextidx = results[nfound - 1]->idx + 1;
 				total += nfound;
 				if (nextidx == 0) {
 					break;
+				}
+			}
 			assert(tag != 0 || total == ntagged[tag]);
 			assert(total <= ntagged[tag]);
+		}
 		gettimeofday(&etv, NULL);
-		printops(title, "ganglookup_tag+remove", tag, total, &stv,
+		if (tag == 0) {
 			check_tag_count(ntagged, tagmask, total);
 		} else {
 			assert(total <= ntagged[tag]);
+		}
 		printops(title, "ganglookup_tag+remove", tagmask, total, &stv,
 		    &etv);
 		removed += total;
+	}
 	gettimeofday(&stv, NULL);
+	{
 		struct testnode *results[TEST2_GANG_LOOKUP_NODES];
 		uint64_t nextidx;
 		unsigned int nfound;
 		unsigned int total;
 		nextidx = 0;
 		total = 0;
 		while ((nfound = radix_tree_gang_lookup_node(t, nextidx,
-		    (void *)results, __arraycount(results))) > 0) {
+		    (void *)results, __arraycount(results), false)) > 0) {
 			for (i = 0; i < nfound; i++) {
 				assert(results[i] == radix_tree_remove_node(t,
 				    results[i]->idx));
+			}
 			nextidx = results[nfound - 1]->idx + 1;
 			total += nfound;
 			if (nextidx == 0) {
 				break;
+			}
+		}
 		assert(total == nnodes - removed);
+	}
 	gettimeofday(&etv, NULL);
 	printops(title, "ganglookup+remove", 0, nnodes - removed, &stv, &etv);
 	assert(radix_tree_empty_tree_p(t));
-	assert(radix_tree_empty_tagged_tree_p(t, 0));
+	for (tagmask = 1; tagmask <= RADIX_TREE_TAG_MASK; tagmask ++) {
-	assert(radix_tree_empty_tagged_tree_p(t, 1));
+		assert(radix_tree_empty_tagged_tree_p(t, tagmask));
+	}
 	radix_tree_fini_tree(t);
 	free(nodes);
+}
 int
 main(int argc, char *argv[])
+{
 	test1();
 	test2("dense", true);
 	test2("sparse", false);
 	return 0;
+}

 @@ -1,14 +1,14 @@
-/*	$NetBSD: radixtree.h,v 1.5 2011/10/25 14:11:27 yamt Exp $	*/
+/*	$NetBSD: radixtree.h,v 1.6 2019/12/05 18:32:25 ad Exp $	*/
 /*-
  * Copyright (c)2011 YAMAMOTO Takashi,
  * All rights reserved.
+ *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  * 1. Redistributions of source code must retain the above copyright
  *    notice, this list of conditions and the following disclaimer.
  * 2. Redistributions in binary form must reproduce the above copyright
  *    notice, this list of conditions and the following disclaimer in the
  *    documentation and/or other materials provided with the distribution.
 @@ -56,33 +56,34 @@ void radix_tree_init(void);
 void radix_tree_init_tree(struct radix_tree *);
 void radix_tree_fini_tree(struct radix_tree *);
 bool radix_tree_empty_tree_p(struct radix_tree *);
 /*
  * node
  */
 int radix_tree_insert_node(struct radix_tree *, uint64_t, void *);
 void *radix_tree_replace_node(struct radix_tree *, uint64_t, void *);
 void *radix_tree_remove_node(struct radix_tree *, uint64_t);
 void *radix_tree_lookup_node(struct radix_tree *, uint64_t);
 unsigned int radix_tree_gang_lookup_node(struct radix_tree *, uint64_t,
-    void **, unsigned int);
+    void **, unsigned int, bool);
 unsigned int radix_tree_gang_lookup_node_reverse(struct radix_tree *, uint64_t,
-    void **, unsigned int);
+    void **, unsigned int, bool);
 /*
  * tag
  */
-typedef int radix_tree_tagid_t;
+typedef unsigned int radix_tree_tagmask_t;
 #define	RADIX_TREE_TAG_ID_MAX	2
-bool radix_tree_get_tag(struct radix_tree *, uint64_t, radix_tree_tagid_t);
+radix_tree_tagmask_t radix_tree_get_tag(struct radix_tree *, uint64_t,
-void radix_tree_set_tag(struct radix_tree *, uint64_t, radix_tree_tagid_t);
+    radix_tree_tagmask_t);
-void radix_tree_clear_tag(struct radix_tree *, uint64_t, radix_tree_tagid_t);
+void radix_tree_set_tag(struct radix_tree *, uint64_t, radix_tree_tagmask_t);
 void radix_tree_clear_tag(struct radix_tree *, uint64_t, radix_tree_tagmask_t);
 unsigned int radix_tree_gang_lookup_tagged_node(struct radix_tree *, uint64_t,
-    void **, unsigned int, radix_tree_tagid_t);
+    void **, unsigned int, bool, radix_tree_tagmask_t);
 unsigned int radix_tree_gang_lookup_tagged_node_reverse(struct radix_tree *,
-    uint64_t, void **, unsigned int, radix_tree_tagid_t);
+    uint64_t, void **, unsigned int, bool, radix_tree_tagmask_t);
-bool radix_tree_empty_tagged_tree_p(struct radix_tree *, radix_tree_tagid_t);
+bool radix_tree_empty_tagged_tree_p(struct radix_tree *, radix_tree_tagmask_t);
 #endif /* !defined(_SYS_RADIXTREE_H_) */