Module Name: src
Committed By: yamt
Date: Thu May 19 10:06:56 UTC 2011
Modified Files:
src/common/lib/libc/gen: radixtree.c
Log Message:
radix_tree_clear_tag:
- fix a bug which errornously clears tags on intermediate nodes.
- add comments.
To generate a diff of this commit:
cvs rdiff -u -r1.6 -r1.7 src/common/lib/libc/gen/radixtree.c
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.6 src/common/lib/libc/gen/radixtree.c:1.7
--- src/common/lib/libc/gen/radixtree.c:1.6 Thu May 19 10:01:21 2011
+++ src/common/lib/libc/gen/radixtree.c Thu May 19 10:06:56 2011
@@ -1,4 +1,4 @@
-/* $NetBSD: radixtree.c,v 1.6 2011/05/19 10:01:21 yamt Exp $ */
+/* $NetBSD: radixtree.c,v 1.7 2011/05/19 10:06:56 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.6 2011/05/19 10:01:21 yamt Exp $");
+__KERNEL_RCSID(0, "$NetBSD: radixtree.c,v 1.7 2011/05/19 10:06:56 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.6 2011/05/19 10:01:21 yamt Exp $");
+__RCSID("$NetBSD: radixtree.c,v 1.7 2011/05/19 10:06:56 yamt Exp $");
#include <assert.h>
#include <errno.h>
#include <stdbool.h>
@@ -128,6 +128,12 @@
unsigned int n_nptrs; /* # of non-NULL pointers in n_ptrs */
};
+/*
+ * any_children_tagmask:
+ *
+ * return OR'ed tagmask of the given node's children.
+ */
+
static unsigned int
any_children_tagmask(struct radix_tree_node *n)
{
@@ -808,9 +814,15 @@
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.
+ */
for (i = t->t_height; i >= 0; i--) {
void ** const pptr = (void **)path_pptr(t, &path, i);
void *entry;
@@ -820,7 +832,10 @@
KASSERT((entry_tagmask(entry) & tagmask) != 0);
*pptr = entry_compose(entry_ptr(entry),
entry_tagmask(entry) & ~tagmask);
- if (0 < i && i < t->t_height - 1) {
+ /*
+ * check if we should proceed to process the next level.
+ */
+ if (0 < i) {
struct radix_tree_node *n = path_node(t, &path, i - 1);
if ((any_children_tagmask(n) & tagmask) != 0) {
