Source-Changes-HG archive

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]

[src/trunk]: src/common/lib/libprop The local copy of rb_tree code has been u...



details:   https://anonhg.NetBSD.org/src/rev/234c0134adf0
branches:  trunk
changeset: 816280:234c0134adf0
user:      pgoyette <pgoyette%NetBSD.org@localhost>
date:      Tue Jun 28 05:18:11 2016 +0000

description:
The local copy of rb_tree code has been unused for quite some time.  So
we can just remove it, and adjust callers to use the "real" rbtree
function names.

Addresses PR lib/44090

diffstat:

 common/lib/libprop/Makefile.inc      |     6 +-
 common/lib/libprop/prop_dictionary.c |    15 +-
 common/lib/libprop/prop_number.c     |    14 +-
 common/lib/libprop/prop_rb.c         |  1275 ----------------------------------
 common/lib/libprop/prop_rb_impl.h    |   196 -----
 5 files changed, 16 insertions(+), 1490 deletions(-)

diffs (truncated from 1622 to 300 lines):

diff -r a216eb8a349c -r 234c0134adf0 common/lib/libprop/Makefile.inc
--- a/common/lib/libprop/Makefile.inc   Tue Jun 28 02:36:54 2016 +0000
+++ b/common/lib/libprop/Makefile.inc   Tue Jun 28 05:18:11 2016 +0000
@@ -1,11 +1,7 @@
-#      $NetBSD: Makefile.inc,v 1.9 2012/07/27 09:10:59 pooka Exp $
+#      $NetBSD: Makefile.inc,v 1.10 2016/06/28 05:18:11 pgoyette Exp $
 
 .PATH: ${.PARSEDIR}
 
 SRCS+= prop_array.c prop_array_util.c prop_bool.c prop_data.c \
         prop_dictionary.c prop_dictionary_util.c prop_ingest.c \
         prop_kern.c prop_number.c prop_object.c prop_stack.c prop_string.c
-
-.ifdef (PROPLIB_WANT_RB)
-SRCS+= prop_rb.c
-.endif
diff -r a216eb8a349c -r 234c0134adf0 common/lib/libprop/prop_dictionary.c
--- a/common/lib/libprop/prop_dictionary.c      Tue Jun 28 02:36:54 2016 +0000
+++ b/common/lib/libprop/prop_dictionary.c      Tue Jun 28 05:18:11 2016 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: prop_dictionary.c,v 1.39 2013/10/18 18:26:20 martin Exp $      */
+/*     $NetBSD: prop_dictionary.c,v 1.40 2016/06/28 05:18:11 pgoyette Exp $    */
 
 /*-
  * Copyright (c) 2006, 2007 The NetBSD Foundation, Inc.
@@ -33,7 +33,8 @@
 #include <prop/prop_array.h>
 #include <prop/prop_dictionary.h>
 #include <prop/prop_string.h>
-#include "prop_rb_impl.h"
+
+#include <sys/rbtree.h>
 
 #if !defined(_KERNEL) && !defined(_STANDALONE)
 #include <errno.h>
@@ -210,7 +211,7 @@
 {
 
        _PROP_MUTEX_INIT(_prop_dict_keysym_tree_mutex);
-       _prop_rb_tree_init(&_prop_dict_keysym_tree,
+       rb_tree_init(&_prop_dict_keysym_tree,
                           &_prop_dict_keysym_rb_tree_ops);
        return 0;
 }
@@ -235,7 +236,7 @@
 {
        prop_dictionary_keysym_t pdk = *obj;
 
-       _prop_rb_tree_remove_node(&_prop_dict_keysym_tree, pdk);
+       rb_tree_remove_node(&_prop_dict_keysym_tree, pdk);
        _prop_dict_keysym_put(pdk);
 
        return _PROP_OBJECT_FREE_DONE;
@@ -292,7 +293,7 @@
         * we just retain it and return it.
         */
        _PROP_MUTEX_LOCK(_prop_dict_keysym_tree_mutex);
-       opdk = _prop_rb_tree_find(&_prop_dict_keysym_tree, key);
+       opdk = rb_tree_find(&_prop_dict_keysym_tree, key);
        if (opdk != NULL) {
                prop_object_retain(opdk);
                _PROP_MUTEX_UNLOCK(_prop_dict_keysym_tree_mutex);
@@ -328,14 +329,14 @@
         * we have to check again if it is in the tree.
         */
        _PROP_MUTEX_LOCK(_prop_dict_keysym_tree_mutex);
-       opdk = _prop_rb_tree_find(&_prop_dict_keysym_tree, key);
+       opdk = rb_tree_find(&_prop_dict_keysym_tree, key);
        if (opdk != NULL) {
                prop_object_retain(opdk);
                _PROP_MUTEX_UNLOCK(_prop_dict_keysym_tree_mutex);
                _prop_dict_keysym_put(pdk);
                return (opdk);
        }
-       rpdk = _prop_rb_tree_insert_node(&_prop_dict_keysym_tree, pdk);
+       rpdk = rb_tree_insert_node(&_prop_dict_keysym_tree, pdk);
        _PROP_ASSERT(rpdk == pdk);
        _PROP_MUTEX_UNLOCK(_prop_dict_keysym_tree_mutex);
        return (rpdk);
diff -r a216eb8a349c -r 234c0134adf0 common/lib/libprop/prop_number.c
--- a/common/lib/libprop/prop_number.c  Tue Jun 28 02:36:54 2016 +0000
+++ b/common/lib/libprop/prop_number.c  Tue Jun 28 05:18:11 2016 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: prop_number.c,v 1.27 2014/09/05 05:19:24 matt Exp $    */
+/*     $NetBSD: prop_number.c,v 1.28 2016/06/28 05:18:11 pgoyette Exp $        */
 
 /*-
  * Copyright (c) 2006 The NetBSD Foundation, Inc.
@@ -29,9 +29,9 @@
  * POSSIBILITY OF SUCH DAMAGE.
  */
 
+#include <sys/rbtree.h>
 #include <prop/prop_number.h>
 #include "prop_object_impl.h"
-#include "prop_rb_impl.h"
 
 #if defined(_KERNEL)
 #include <sys/systm.h>
@@ -157,7 +157,7 @@
 {
        prop_number_t pn = *obj;
 
-       _prop_rb_tree_remove_node(&_prop_number_tree, pn);
+       rb_tree_remove_node(&_prop_number_tree, pn);
 
        _PROP_POOL_PUT(_prop_number_pool, pn);
 
@@ -171,7 +171,7 @@
 {
 
        _PROP_MUTEX_INIT(_prop_number_tree_mutex);
-       _prop_rb_tree_init(&_prop_number_tree, &_prop_number_rb_tree_ops);
+       rb_tree_init(&_prop_number_tree, &_prop_number_rb_tree_ops);
        return 0;
 }
 
@@ -283,7 +283,7 @@
         * we just retain it and return it.
         */
        _PROP_MUTEX_LOCK(_prop_number_tree_mutex);
-       opn = _prop_rb_tree_find(&_prop_number_tree, pnv);
+       opn = rb_tree_find(&_prop_number_tree, pnv);
        if (opn != NULL) {
                prop_object_retain(opn);
                _PROP_MUTEX_UNLOCK(_prop_number_tree_mutex);
@@ -308,14 +308,14 @@
         * we have to check again if it is in the tree.
         */
        _PROP_MUTEX_LOCK(_prop_number_tree_mutex);
-       opn = _prop_rb_tree_find(&_prop_number_tree, pnv);
+       opn = rb_tree_find_node(&_prop_number_tree, pnv);
        if (opn != NULL) {
                prop_object_retain(opn);
                _PROP_MUTEX_UNLOCK(_prop_number_tree_mutex);
                _PROP_POOL_PUT(_prop_number_pool, pn);
                return (opn);
        }
-       rpn = _prop_rb_tree_insert_node(&_prop_number_tree, pn);
+       rpn = rb_tree_insert_node(&_prop_number_tree, pn);
        _PROP_ASSERT(rpn == pn);
        _PROP_MUTEX_UNLOCK(_prop_number_tree_mutex);
        return (rpn);
diff -r a216eb8a349c -r 234c0134adf0 common/lib/libprop/prop_rb.c
--- a/common/lib/libprop/prop_rb.c      Tue Jun 28 02:36:54 2016 +0000
+++ /dev/null   Thu Jan 01 00:00:00 1970 +0000
@@ -1,1275 +0,0 @@
-/*     $NetBSD: prop_rb.c,v 1.10 2012/07/27 09:10:59 pooka Exp $       */
-
-/*-
- * Copyright (c) 2001 The NetBSD Foundation, Inc.
- * All rights reserved.
- *
- * This code is derived from software contributed to The NetBSD Foundation
- * by Matt Thomas <matt%3am-software.com@localhost>.
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions
- * are met:
- * 1. Redistributions of source code must retain the above copyright
- *    notice, this list of conditions and the following disclaimer.
- * 2. Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- *
- * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
- * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
- * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
- * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
- * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
- * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
- * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
- * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
- * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
- * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
- * POSSIBILITY OF SUCH DAMAGE.
- *
- *     NetBSD: rb.c,v 1.11 2011/06/20 09:11:16 mrg Exp
- */
-
-#include "prop_object_impl.h"
-#include <prop/proplib.h>
-
-#include "prop_rb_impl.h"
-
-#ifdef RBDEBUG
-#define        KASSERT(s)      _PROP_ASSERT(s)
-#else
-#define KASSERT(s)     do { } while (/*CONSTCOND*/ 0)
-#endif
-
-#ifndef __predict_false
-#define __predict_false(x)     (x)
-#endif
-
-static void rb_tree_insert_rebalance(struct rb_tree *, struct rb_node *);
-static void rb_tree_removal_rebalance(struct rb_tree *, struct rb_node *,
-       unsigned int);
-#ifdef RBDEBUG
-static const struct rb_node *rb_tree_iterate_const(const struct rb_tree *,
-       const struct rb_node *, const unsigned int);
-static bool rb_tree_check_node(const struct rb_tree *, const struct rb_node *,
-       const struct rb_node *, bool);
-#else
-#define        rb_tree_check_node(a, b, c, d)  true
-#endif
-
-#define        RB_NODETOITEM(rbto, rbn)        \
-    ((void *)((uintptr_t)(rbn) - (rbto)->rbto_node_offset))
-#define        RB_ITEMTONODE(rbto, rbn)        \
-    ((rb_node_t *)((uintptr_t)(rbn) + (rbto)->rbto_node_offset))
-
-#define        RB_SENTINEL_NODE        NULL
-
-void
-_prop_rb_tree_init(struct rb_tree *rbt, const rb_tree_ops_t *ops)
-{
-
-       rbt->rbt_ops = ops;
-       rbt->rbt_root = RB_SENTINEL_NODE;
-       RB_TAILQ_INIT(&rbt->rbt_nodes);
-#ifndef RBSMALL
-       rbt->rbt_minmax[RB_DIR_LEFT] = rbt->rbt_root;   /* minimum node */
-       rbt->rbt_minmax[RB_DIR_RIGHT] = rbt->rbt_root;  /* maximum node */
-#endif
-#ifdef RBSTATS
-       rbt->rbt_count = 0;
-       rbt->rbt_insertions = 0;
-       rbt->rbt_removals = 0;
-       rbt->rbt_insertion_rebalance_calls = 0;
-       rbt->rbt_insertion_rebalance_passes = 0;
-       rbt->rbt_removal_rebalance_calls = 0;
-       rbt->rbt_removal_rebalance_passes = 0;
-#endif
-}
-
-void *
-_prop_rb_tree_find(struct rb_tree *rbt, const void *key)
-{
-       const rb_tree_ops_t *rbto = rbt->rbt_ops;
-       rbto_compare_key_fn compare_key = rbto->rbto_compare_key;
-       struct rb_node *parent = rbt->rbt_root;
-
-       while (!RB_SENTINEL_P(parent)) {
-               void *pobj = RB_NODETOITEM(rbto, parent);
-               const signed int diff = (*compare_key)(rbto->rbto_context,
-                   pobj, key);
-               if (diff == 0)
-                       return pobj;
-               parent = parent->rb_nodes[diff < 0];
-       }
-
-       return NULL;
-}
-
-void *
-_prop_rb_tree_insert_node(struct rb_tree *rbt, void *object)
-{
-       const rb_tree_ops_t *rbto = rbt->rbt_ops;
-       rbto_compare_nodes_fn compare_nodes = rbto->rbto_compare_nodes;
-       struct rb_node *parent, *tmp, *self = RB_ITEMTONODE(rbto, object);
-       unsigned int position;
-       bool rebalance;
-
-       RBSTAT_INC(rbt->rbt_insertions);
-
-       tmp = rbt->rbt_root;
-       /*
-        * This is a hack.  Because rbt->rbt_root is just a struct rb_node *,
-        * just like rb_node->rb_nodes[RB_DIR_LEFT], we can use this fact to
-        * avoid a lot of tests for root and know that even at root,
-        * updating RB_FATHER(rb_node)->rb_nodes[RB_POSITION(rb_node)] will
-        * update rbt->rbt_root.
-        */
-       parent = (struct rb_node *)(void *)&rbt->rbt_root;
-       position = RB_DIR_LEFT;
-
-       /*
-        * Find out where to place this new leaf.
-        */
-       while (!RB_SENTINEL_P(tmp)) {
-               void *tobj = RB_NODETOITEM(rbto, tmp);
-               const signed int diff = (*compare_nodes)(rbto->rbto_context,
-                   tobj, object);
-               if (__predict_false(diff == 0)) {
-                       /*
-                        * Node already exists; return it.
-                        */
-                       return tobj;
-               }
-               parent = tmp;
-               position = (diff < 0);
-               tmp = parent->rb_nodes[position];
-       }
-
-#ifdef RBDEBUG
-       {
-               struct rb_node *prev = NULL, *next = NULL;
-
-               if (position == RB_DIR_RIGHT)



Home | Main Index | Thread Index | Old Index