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/137a4b4441ff
branches: trunk
changeset: 346138:137a4b4441ff
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 898e37f80f9e -r 137a4b4441ff 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 898e37f80f9e -r 137a4b4441ff 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 898e37f80f9e -r 137a4b4441ff 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 898e37f80f9e -r 137a4b4441ff 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