Module Name: src
Committed By: yamt
Date: Tue Oct 25 14:11:27 UTC 2011
Modified Files:
src/common/lib/libc/gen: radixtree.c
src/sys/sys: radixtree.h
Log Message:
add radix_tree_empty_tagged_tree_p, a "tagged" variant of
radix_tree_empty_tree_p.
To generate a diff of this commit:
cvs rdiff -u -r1.15 -r1.16 src/common/lib/libc/gen/radixtree.c
cvs rdiff -u -r1.4 -r1.5 src/sys/sys/radixtree.h
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Modified files:
Index: src/common/lib/libc/gen/radixtree.c
diff -u src/common/lib/libc/gen/radixtree.c:1.15 src/common/lib/libc/gen/radixtree.c:1.16
--- src/common/lib/libc/gen/radixtree.c:1.15 Fri Oct 14 19:42:15 2011
+++ src/common/lib/libc/gen/radixtree.c Tue Oct 25 14:11:27 2011
@@ -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 @@ __KERNEL_RCSID(0, "$NetBSD: radixtree.c,
#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 @@ radix_tree_empty_tree_p(struct radix_tre
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 @@ test1(void)
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 @@ test1(void)
== 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 @@ test2(const char *title, bool dense)
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);
}
Index: src/sys/sys/radixtree.h
diff -u src/sys/sys/radixtree.h:1.4 src/sys/sys/radixtree.h:1.5
--- src/sys/sys/radixtree.h:1.4 Fri Oct 14 19:42:14 2011
+++ src/sys/sys/radixtree.h Tue Oct 25 14:11:27 2011
@@ -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 @@ unsigned int radix_tree_gang_lookup_tagg
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_) */
