[src/trunk]: src/common/lib/libc/gen radix_tree_clear_tag:

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

details:   https://anonhg.NetBSD.org/src/rev/fb44ceac76aa
branches:  trunk
changeset: 765107:fb44ceac76aa
user:      yamt <yamt%NetBSD.org@localhost>
date:      Thu May 19 10:06:56 2011 +0000

description:
radix_tree_clear_tag:
- fix a bug which errornously clears tags on intermediate nodes.
- add comments.

diffstat:

 common/lib/libc/gen/radixtree.c |  23 +++++++++++++++++++----
 1 files changed, 19 insertions(+), 4 deletions(-)

diffs (68 lines):

diff -r 0f5ad37ee952 -r fb44ceac76aa common/lib/libc/gen/radixtree.c
--- a/common/lib/libc/gen/radixtree.c   Thu May 19 10:01:21 2011 +0000
+++ b/common/lib/libc/gen/radixtree.c   Thu May 19 10:06:56 2011 +0000
@@ -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) {