Source-Changes-HG archive
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
[src/trunk]: src Fixes/improvements to RB-tree implementation:
details: https://anonhg.NetBSD.org/src/rev/6f9c716d8d3a
branches: trunk
changeset: 757817:6f9c716d8d3a
user: rmind <rmind%NetBSD.org@localhost>
date: Fri Sep 24 22:51:50 2010 +0000
description:
Fixes/improvements to RB-tree implementation:
1. Fix inverted node order, so that negative value from comparison operator
would represent lower (left) node, and positive - higher (right) node.
2. Add an argument (i.e. "context"), passed to comparison operators.
3. Change rb_tree_insert_node() to return a node - either inserted one or
already existing one.
4. Amend the interface to manipulate the actual object, instead of the
rb_node (in a similar way as Patricia-tree interface does).
5. Update all RB-tree users accordingly.
XXX: Perhaps rename rb.h to rbtree.h, since cleaning-up..
1-3 address the PR/43488 by Jeremy Huddleston.
Passes RB-tree regression tests.
Reviewed by: matt@, christos@
diffstat:
common/lib/libc/gen/rb.c | 163 +++++++++++++++++++++-------------
common/lib/libprop/prop_dictionary.c | 52 +++++------
common/lib/libprop/prop_number.c | 54 +++++------
sys/fs/udf/udf.h | 8 +-
sys/fs/udf/udf_subr.c | 38 ++++----
sys/kern/subr_lockdebug.c | 40 ++++---
sys/net/npf/npf_session.c | 52 ++++------
sys/net/npf/npf_tableset.c | 63 ++++++-------
sys/nfs/nfs_node.c | 36 +++----
sys/rump/librump/rumpkern/vm.c | 24 ++--
sys/sys/rb.h | 61 ++++++------
sys/uvm/uvm_map.c | 63 +++++++------
sys/uvm/uvm_object.h | 4 +-
sys/uvm/uvm_page.c | 38 ++++---
14 files changed, 357 insertions(+), 339 deletions(-)
diffs (truncated from 1829 to 300 lines):
diff -r e9687504c346 -r 6f9c716d8d3a common/lib/libc/gen/rb.c
--- a/common/lib/libc/gen/rb.c Fri Sep 24 21:53:00 2010 +0000
+++ b/common/lib/libc/gen/rb.c Fri Sep 24 22:51:50 2010 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: rb.c,v 1.6 2010/04/30 13:58:09 joerg Exp $ */
+/* $NetBSD: rb.c,v 1.7 2010/09/24 22:51:51 rmind Exp $ */
/*-
* Copyright (c) 2001 The NetBSD Foundation, Inc.
@@ -87,11 +87,17 @@
#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
-rb_tree_init(struct rb_tree *rbt, const struct rb_tree_ops *ops)
+rb_tree_init(struct rb_tree *rbt, const rb_tree_ops_t *ops)
{
+
rbt->rbt_ops = ops;
*((const struct rb_node **)&rbt->rbt_root) = RB_SENTINEL_NODE;
RB_TAILQ_INIT(&rbt->rbt_nodes);
@@ -110,65 +116,73 @@
#endif
}
-struct rb_node *
+void *
rb_tree_find_node(struct rb_tree *rbt, const void *key)
{
- rbto_compare_key_fn compare_key = rbt->rbt_ops->rbto_compare_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)) {
- const signed int diff = (*compare_key)(parent, key);
+ void *pobj = RB_NODETOITEM(rbto, parent);
+ const signed int diff = (*compare_key)(rbto->rbto_context,
+ pobj, key);
if (diff == 0)
- return parent;
- parent = parent->rb_nodes[diff > 0];
+ return pobj;
+ parent = parent->rb_nodes[diff < 0];
}
return NULL;
}
-
-struct rb_node *
+
+void *
rb_tree_find_node_geq(struct rb_tree *rbt, const void *key)
{
- rbto_compare_key_fn compare_key = rbt->rbt_ops->rbto_compare_key;
- struct rb_node *parent = rbt->rbt_root;
- struct rb_node *last = NULL;
+ 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, *last = NULL;
while (!RB_SENTINEL_P(parent)) {
- const signed int diff = (*compare_key)(parent, key);
+ void *pobj = RB_NODETOITEM(rbto, parent);
+ const signed int diff = (*compare_key)(rbto->rbto_context,
+ pobj, key);
if (diff == 0)
- return parent;
- if (diff < 0)
+ return pobj;
+ if (diff > 0)
last = parent;
- parent = parent->rb_nodes[diff > 0];
+ parent = parent->rb_nodes[diff < 0];
}
- return last;
+ return RB_NODETOITEM(rbto, last);
}
-
-struct rb_node *
+
+void *
rb_tree_find_node_leq(struct rb_tree *rbt, const void *key)
{
- rbto_compare_key_fn compare_key = rbt->rbt_ops->rbto_compare_key;
- struct rb_node *parent = rbt->rbt_root;
- struct rb_node *last = NULL;
+ 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, *last = NULL;
while (!RB_SENTINEL_P(parent)) {
- const signed int diff = (*compare_key)(parent, key);
+ void *pobj = RB_NODETOITEM(rbto, parent);
+ const signed int diff = (*compare_key)(rbto->rbto_context,
+ pobj, key);
if (diff == 0)
- return parent;
- if (diff > 0)
+ return pobj;
+ if (diff < 0)
last = parent;
- parent = parent->rb_nodes[diff > 0];
+ parent = parent->rb_nodes[diff < 0];
}
- return last;
+ return RB_NODETOITEM(rbto, last);
}
-
-bool
-rb_tree_insert_node(struct rb_tree *rbt, struct rb_node *self)
+
+void *
+rb_tree_insert_node(struct rb_tree *rbt, void *object)
{
- rbto_compare_nodes_fn compare_nodes = rbt->rbt_ops->rbto_compare_nodes;
- struct rb_node *parent, *tmp;
+ 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;
@@ -189,15 +203,17 @@
* Find out where to place this new leaf.
*/
while (!RB_SENTINEL_P(tmp)) {
- const signed int diff = (*compare_nodes)(tmp, self);
+ 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; don't insert.
+ * Node already exists; return it.
*/
- return false;
+ return tobj;
}
parent = tmp;
- position = (diff > 0);
+ position = (diff < 0);
tmp = parent->rb_nodes[position];
}
@@ -221,8 +237,10 @@
prev = TAILQ_PREV(next, rb_node_qh, rb_link);
KASSERT(prev == NULL || !RB_SENTINEL_P(prev));
KASSERT(next == NULL || !RB_SENTINEL_P(next));
- KASSERT(prev == NULL || (*compare_nodes)(prev, self) > 0);
- KASSERT(next == NULL || (*compare_nodes)(self, next) > 0);
+ KASSERT(prev == NULL || (*compare_nodes)(rbto->rbto_context,
+ RB_NODETOITEM(rbto, prev), RB_NODETOITEM(rbto, self)) < 0);
+ KASSERT(next == NULL || (*compare_nodes)(rbto->rbto_context,
+ RB_NODETOITEM(rbto, self), RB_NODETOITEM(rbto, next)) < 0);
}
#endif
@@ -270,10 +288,14 @@
if (RB_ROOT_P(rbt, self)) {
RB_TAILQ_INSERT_HEAD(&rbt->rbt_nodes, self, rb_link);
} else if (position == RB_DIR_LEFT) {
- KASSERT((*compare_nodes)(self, RB_FATHER(self)) > 0);
+ KASSERT((*compare_nodes)(rbto->rbto_context,
+ RB_NODETOITEM(rbto, self),
+ RB_NODETOITEM(rbto, RB_FATHER(self))) < 0);
RB_TAILQ_INSERT_BEFORE(RB_FATHER(self), self, rb_link);
} else {
- KASSERT((*compare_nodes)(RB_FATHER(self), self) > 0);
+ KASSERT((*compare_nodes)(rbto->rbto_context,
+ RB_NODETOITEM(rbto, RB_FATHER(self)),
+ RB_NODETOITEM(rbto, self)) < 0);
RB_TAILQ_INSERT_AFTER(&rbt->rbt_nodes, RB_FATHER(self),
self, rb_link);
}
@@ -288,9 +310,10 @@
KASSERT(rb_tree_check_node(rbt, self, NULL, true));
}
- return true;
+ /* Succesfully inserted, return our node pointer. */
+ return object;
}
-
+
/*
* Swap the location and colors of 'self' and its child @ which. The child
* can not be a sentinel node. This is our rotation function. However,
@@ -316,7 +339,8 @@
KASSERT(rb_tree_check_node(rbt, old_father, NULL, false));
KASSERT(rb_tree_check_node(rbt, old_child, NULL, false));
- KASSERT(RB_ROOT_P(rbt, old_father) || rb_tree_check_node(rbt, grandpa, NULL, false));
+ KASSERT(RB_ROOT_P(rbt, old_father) ||
+ rb_tree_check_node(rbt, grandpa, NULL, false));
/*
* Exchange descendant linkages.
@@ -358,9 +382,10 @@
KASSERT(rb_tree_check_node(rbt, new_father, NULL, false));
KASSERT(rb_tree_check_node(rbt, new_child, NULL, false));
- KASSERT(RB_ROOT_P(rbt, new_father) || rb_tree_check_node(rbt, grandpa, NULL, false));
+ KASSERT(RB_ROOT_P(rbt, new_father) ||
+ rb_tree_check_node(rbt, grandpa, NULL, false));
}
-
+
static void
rb_tree_insert_rebalance(struct rb_tree *rbt, struct rb_node *self)
{
@@ -466,7 +491,7 @@
*/
RB_MARK_BLACK(rbt->rbt_root);
}
-
+
static void
rb_tree_prune_node(struct rb_tree *rbt, struct rb_node *self, bool rebalance)
{
@@ -515,7 +540,7 @@
rb_tree_removal_rebalance(rbt, father, which);
KASSERT(was_root || rb_tree_check_node(rbt, father, NULL, true));
}
-
+
/*
* When deleting an interior node
*/
@@ -716,13 +741,12 @@
KASSERT(was_root || rb_tree_check_node(rbt, father, NULL, true));
KASSERT(rb_tree_check_node(rbt, son, NULL, true));
}
-/*
- *
- */
+
void
-rb_tree_remove_node(struct rb_tree *rbt, struct rb_node *self)
+rb_tree_remove_node(struct rb_tree *rbt, void *object)
{
- struct rb_node *standin;
+ const rb_tree_ops_t *rbto = rbt->rbt_ops;
+ struct rb_node *standin, *self = RB_ITEMTONODE(rbto, object);
unsigned int which;
KASSERT(!RB_SENTINEL_P(self));
@@ -779,7 +803,7 @@
* Let's find the node closes to us opposite of our parent
* Now swap it with ourself, "prune" it, and rebalance, if needed.
*/
- standin = rb_tree_iterate(rbt, self, which);
+ standin = RB_ITEMTONODE(rbto, rb_tree_iterate(rbt, object, which));
rb_tree_swap_prune_and_rebalance(rbt, self, standin);
}
@@ -934,27 +958,30 @@
KASSERT(rb_tree_check_node(rbt, parent, NULL, true));
}
-struct rb_node *
-rb_tree_iterate(struct rb_tree *rbt, struct rb_node *self,
- const unsigned int direction)
+void *
+rb_tree_iterate(struct rb_tree *rbt, void *object, const unsigned int direction)
{
+ const rb_tree_ops_t *rbto = rbt->rbt_ops;
const unsigned int other = direction ^ RB_DIR_OTHER;
+ struct rb_node *self;
+
KASSERT(direction == RB_DIR_LEFT || direction == RB_DIR_RIGHT);
- if (self == NULL) {
+ if (object == NULL) {
#ifndef RBSMALL
if (RB_SENTINEL_P(rbt->rbt_root))
return NULL;
- return rbt->rbt_minmax[direction];
+ return RB_NODETOITEM(rbto, rbt->rbt_minmax[direction]);
#else
self = rbt->rbt_root;
if (RB_SENTINEL_P(self))
return NULL;
while (!RB_SENTINEL_P(self->rb_nodes[direction]))
self = self->rb_nodes[direction];
- return self;
+ return RB_NODETOITEM(rbto, self);
#endif /* !RBSMALL */
}
+ self = RB_ITEMTONODE(rbto, object);
KASSERT(!RB_SENTINEL_P(self));
Home |
Main Index |
Thread Index |
Old Index