[src/trunk]: src add radix_tree_empty_tagged_tree_p, a "tagged" variant of

[yamt <yamt%NetBSD.org@localhost>]

details:   https://anonhg.NetBSD.org/src/rev/a0353e810820
branches:  trunk
changeset: 770611:a0353e810820
user:      yamt <yamt%NetBSD.org@localhost>
date:      Tue Oct 25 14:11:27 2011 +0000

description:
add radix_tree_empty_tagged_tree_p, a "tagged" variant of
radix_tree_empty_tree_p.

diffstat:

 common/lib/libc/gen/radixtree.c |  25 ++++++++++++++++++++++---
 sys/sys/radixtree.h             |   3 ++-
 2 files changed, 24 insertions(+), 4 deletions(-)

diffs (95 lines):

diff -r 911c8db1e7d5 -r a0353e810820 common/lib/libc/gen/radixtree.c
--- a/common/lib/libc/gen/radixtree.c   Tue Oct 25 11:35:49 2011 +0000
+++ b/common/lib/libc/gen/radixtree.c   Tue Oct 25 14:11:27 2011 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: radixtree.c,v 1.15 2011/10/14 19:42:15 yamt Exp $      */
+/*     $NetBSD: radixtree.c,v 1.16 2011/10/25 14:11:27 yamt Exp $      */
 
 /*-
  * Copyright (c)2011 YAMAMOTO Takashi,
@@ -41,7 +41,7 @@
 #include <sys/cdefs.h>
 
 #if defined(_KERNEL) || defined(_STANDALONE)
-__KERNEL_RCSID(0, "$NetBSD: radixtree.c,v 1.15 2011/10/14 19:42:15 yamt Exp $");
+__KERNEL_RCSID(0, "$NetBSD: radixtree.c,v 1.16 2011/10/25 14:11:27 yamt Exp $");
 #include <sys/param.h>
 #include <sys/errno.h>
 #include <sys/pool.h>
@@ -51,7 +51,7 @@
 #include <lib/libsa/stand.h>
 #endif /* defined(_STANDALONE) */
 #else /* defined(_KERNEL) || defined(_STANDALONE) */
-__RCSID("$NetBSD: radixtree.c,v 1.15 2011/10/14 19:42:15 yamt Exp $");
+__RCSID("$NetBSD: radixtree.c,v 1.16 2011/10/25 14:11:27 yamt Exp $");
 #include <assert.h>
 #include <errno.h>
 #include <stdbool.h>
@@ -224,6 +224,14 @@
        return t->t_root == NULL;
 }
 
+bool
+radix_tree_empty_tagged_tree_p(struct radix_tree *t, radix_tree_tagid_t tagid)
+{
+       const unsigned int tagmask = tagid_to_mask(tagid);
+
+       return (entry_tagmask(t->t_root) & tagmask) == 0;
+}
+
 static void
 radix_tree_node_init(struct radix_tree_node *n)
 {
@@ -1012,8 +1020,12 @@
        assert(radix_tree_gang_lookup_tagged_node_reverse(t, 1000, results, 3,
            0) == 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_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_lookup_node(t, 0) == (void *)0xdeadbea0);
        assert(radix_tree_lookup_node(t, 1000) == NULL);
        memset(results, 0, sizeof(results));
@@ -1052,9 +1064,13 @@
            == 0);
        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_set_tag(t, 1000, 1);
        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);
@@ -1403,6 +1419,9 @@
        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));
+       assert(radix_tree_empty_tagged_tree_p(t, 1));
        radix_tree_fini_tree(t);
        free(nodes);
 }
diff -r 911c8db1e7d5 -r a0353e810820 sys/sys/radixtree.h
--- a/sys/sys/radixtree.h       Tue Oct 25 11:35:49 2011 +0000
+++ b/sys/sys/radixtree.h       Tue Oct 25 14:11:27 2011 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: radixtree.h,v 1.4 2011/10/14 19:42:14 yamt Exp $       */
+/*     $NetBSD: radixtree.h,v 1.5 2011/10/25 14:11:27 yamt Exp $       */
 
 /*-
  * Copyright (c)2011 YAMAMOTO Takashi,
@@ -83,5 +83,6 @@
     void **, unsigned int, radix_tree_tagid_t);
 unsigned int radix_tree_gang_lookup_tagged_node_reverse(struct radix_tree *,
     uint64_t, void **, unsigned int, radix_tree_tagid_t);
+bool radix_tree_empty_tagged_tree_p(struct radix_tree *, radix_tree_tagid_t);
 
 #endif /* !defined(_SYS_RADIXTREE_H_) */