[src/netbsd-6]: src Pull up following revision(s) (requested by rmind in tick...

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

details:   https://anonhg.NetBSD.org/src/rev/736bbcaa16d1
branches:  netbsd-6
changeset: 774335:736bbcaa16d1
user:      riz <riz%NetBSD.org@localhost>
date:      Mon Jul 16 22:10:46 2012 +0000

description:
Pull up following revision(s) (requested by rmind in ticket #420):
        common/lib/libc/gen/ptree.c: revision 1.7
        common/lib/libc/gen/ptree.c: revision 1.8
        common/lib/libc/gen/ptree.c: revision 1.9
        sys/sys/ptree.h: revision 1.7
Don't bother testing 0 length keys since they can only have one possible value.
Add code to protect the ptree from multiple insertions of the same node.
ptree_find_filtered_node: make key argument const.

diffstat:

 common/lib/libc/gen/ptree.c |  35 +++++++++++++++++++++++++----------
 sys/sys/ptree.h             |   4 ++--
 2 files changed, 27 insertions(+), 12 deletions(-)

diffs (136 lines):

diff -r 4f0ab10bb5df -r 736bbcaa16d1 common/lib/libc/gen/ptree.c
--- a/common/lib/libc/gen/ptree.c       Mon Jul 16 22:08:03 2012 +0000
+++ b/common/lib/libc/gen/ptree.c       Mon Jul 16 22:10:46 2012 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: ptree.c,v 1.5.8.1 2012/07/12 18:35:10 riz Exp $        */
+/*     $NetBSD: ptree.c,v 1.5.8.2 2012/07/16 22:10:46 riz Exp $        */
 
 /*-
  * Copyright (c) 2008 The NetBSD Foundation, Inc.
@@ -40,7 +40,7 @@
 #include <sys/types.h>
 #include <sys/systm.h>
 #include <lib/libkern/libkern.h>
-__KERNEL_RCSID(0, "$NetBSD: ptree.c,v 1.5.8.1 2012/07/12 18:35:10 riz Exp $");
+__KERNEL_RCSID(0, "$NetBSD: ptree.c,v 1.5.8.2 2012/07/16 22:10:46 riz Exp $");
 #else
 #include <stddef.h>
 #include <stdint.h>
@@ -53,7 +53,7 @@
 #else
 #define        KASSERT(e)      do { } while (/*CONSTCOND*/ 0)
 #endif
-__RCSID("$NetBSD: ptree.c,v 1.5.8.1 2012/07/12 18:35:10 riz Exp $");
+__RCSID("$NetBSD: ptree.c,v 1.5.8.2 2012/07/16 22:10:46 riz Exp $");
 #endif /* _KERNEL || _STANDALONE */
 
 #ifdef _LIBC
@@ -67,7 +67,7 @@
 #endif
 
 /*
- * This is an implementation of a radix / PATRICIA tree.  As in a traditional 
+ * This is an implementation of a radix / PATRICIA tree.  As in a traditional
  * patricia tree, all the data is at the leaves of the tree.  An N-value
  * tree would have N leaves, N-1 branching nodes, and a root pointer.  Each
  * branching node would have left(0) and right(1) pointers that either point
@@ -76,15 +76,15 @@
  * have no need for pointers.
  *
  * However, allocation for these branching nodes is problematic since the
- * allocation could fail.  This would cause insertions to fail for reasons  
- * beyond the users control.  So to prevent this, in this implementation
+ * allocation could fail.  This would cause insertions to fail for reasons
+ * beyond the user's control.  So to prevent this, in this implementation
  * each node has two identities: its leaf identity and its branch identity.
  * Each is separate from the other.  Every branch is tagged as to whether
  * it points to a leaf or a branch.  This is not an attribute of the object
  * but of the pointer to the object.  The low bit of the pointer is used as
  * the tag to determine whether it points to a leaf or branch identity, with
  * branch identities having the low bit set.
- * 
+ *
  * A node's branch identity has one rule: when traversing the tree from the
  * root to the node's leaf identity, one of the branches traversed will be via
  * the node's branch identity.  Of course, that has an exception: since to
@@ -93,7 +93,7 @@
  *
  * Branching nodes also has a bit offset and a bit length which determines
  * which branch slot is used.  The bit length can be zero resulting in a
- * one-way branch.  This is happens in two special cases: the root and
+ * one-way branch.  This happens in two special cases: the root and
  * interior mask nodes.
  *
  * To support longest match first lookups, when a mask node (one that only
@@ -134,7 +134,7 @@
 {
        const pt_bitlen_t bitlen = PTN_BRANCH_BITLEN(ptn);
        if (bitlen == 0)
-               return PT_SLOT_ROOT;
+               return PT_SLOT_ROOT;    /* mask or root, doesn't matter */
        return (*pt->pt_ops->ptto_testnode)(NODETOKEY(pt, target),
            PTN_BRANCH_BITOFF(ptn), bitlen, pt->pt_context);
 }
@@ -150,6 +150,9 @@
 static inline pt_slot_t
 ptree_testkey(const pt_tree_t *pt, const void *key, const pt_node_t *ptn)
 {
+       const pt_bitlen_t bitlen = PTN_BRANCH_BITLEN(ptn);
+       if (bitlen == 0)
+               return PT_SLOT_ROOT;    /* mask or root, doesn't matter */
        return (*pt->pt_ops->ptto_testkey)(key, PTN_BRANCH_BITOFF(ptn),
            PTN_BRANCH_BITLEN(ptn), pt->pt_context);
 }
@@ -456,6 +459,12 @@
        pt_insertdata_t id;
 
        /*
+        * If this node already exists in the tree, return failure.
+        */
+       if (target == PT_NODE(pt->pt_root))
+               return false;
+
+       /*
         * We need a leaf so we can match against.  Until we get a leaf
         * we having nothing to test against.
         */
@@ -477,6 +486,12 @@
                id.id_node = *id.id_insertp;
 
                /*
+                * If this node already exists in the tree, return failure.
+                */
+               if (target == ptn)
+                       return false;
+
+               /*
                 * If we hit a leaf, try to insert target at leaf.  We could
                 * have inlined ptree_insert_leaf here but that would have
                 * made this routine much harder to understand.  Trust the
@@ -613,7 +628,7 @@
 #endif /* !PTNOMASH */
 
 void *
-ptree_find_filtered_node(pt_tree_t *pt, void *key, pt_filter_t filter,
+ptree_find_filtered_node(pt_tree_t *pt, const void *key, pt_filter_t filter,
        void *filter_arg)
 {
 #ifndef PTNOMASK
diff -r 4f0ab10bb5df -r 736bbcaa16d1 sys/sys/ptree.h
--- a/sys/sys/ptree.h   Mon Jul 16 22:08:03 2012 +0000
+++ b/sys/sys/ptree.h   Mon Jul 16 22:10:46 2012 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: ptree.h,v 1.4.8.1 2012/07/12 18:35:10 riz Exp $        */
+/*     $NetBSD: ptree.h,v 1.4.8.2 2012/07/16 22:10:47 riz Exp $        */
 
 /*-
  * Copyright (c) 2008 The NetBSD Foundation, Inc.
@@ -184,7 +184,7 @@
 void   ptree_init(pt_tree_t *, const pt_tree_ops_t *, void *, size_t, size_t);
 bool   ptree_insert_node(pt_tree_t *, void *);
 bool   ptree_insert_mask_node(pt_tree_t *, void *, pt_bitlen_t);
-void * ptree_find_filtered_node(pt_tree_t *, void *, pt_filter_t, void *);
+void * ptree_find_filtered_node(pt_tree_t *, const void *, pt_filter_t, void *);
 #define        ptree_find_node(pt,key) \
        ptree_find_filtered_node((pt), (key), NULL, NULL)
 void   ptree_remove_node(pt_tree_t *, void *);