[PATCH] rbtree: Add finger versions of Insert and Find.
Gedare Bloom
gedare at rtems.org
Thu May 3 20:00:54 UTC 2012
A finger is a pointer to a node in a tree and is used like a hint for
algorithms that traverse the tree. If the hint is bad performance may
decrease although the asymptotic complexity of the algorithms are not
changed. Using the tree's root as a finger yields the default behavior
of these algorithms.
This patch also cleans up Insert and Find, and fixes a bug in Insert
that left interrupts disabled after returning.
---
cpukit/sapi/inline/rtems/rbtree.inl | 44 ++++---
cpukit/score/include/rtems/score/rbtree.h | 67 +++++++----
cpukit/score/inline/rtems/score/rbtree.inl | 60 ++++-----
cpukit/score/src/rbtreefind.c | 70 ++++++++----
cpukit/score/src/rbtreeinsert.c | 177 ++++++++++++++--------------
testsuites/sptests/sprbtree01/init.c | 41 +++++++
6 files changed, 277 insertions(+), 182 deletions(-)
diff --git a/cpukit/sapi/inline/rtems/rbtree.inl b/cpukit/sapi/inline/rtems/rbtree.inl
index 1da2d3b..7b6602a 100644
--- a/cpukit/sapi/inline/rtems/rbtree.inl
+++ b/cpukit/sapi/inline/rtems/rbtree.inl
@@ -262,14 +262,8 @@ RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_find_unprotected(
return _RBTree_Find_unprotected( the_rbtree, the_node );
}
-/** @brief Find the node with given key in the tree
- *
- * This function returns a pointer to the node having key equal to the key
- * of @a the_node if it exists within @a the_rbtree, and NULL if not.
- * @a the_node has to be made up before a search.
- *
- * @note If the tree is not unique and contains duplicate keys, the set
- * of duplicate keys acts as FIFO.
+/**
+ * @copydoc _RBTree_Find()
*/
RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_find(
rtems_rbtree_control *the_rbtree,
@@ -280,6 +274,18 @@ RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_find(
}
/**
+ * @copydoc _RBTree_Find_finger()
+ */
+RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_find_finger(
+ rtems_rbtree_control *the_rbtree,
+ rtems_rbtree_node *the_node,
+ rtems_rbtree_node *finger
+)
+{
+ return _RBTree_Find_finger( the_rbtree, the_node, finger );
+}
+
+/**
* @copydoc _RBTree_Predecessor_unprotected()
*/
RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_predecessor_unprotected(
@@ -464,15 +470,7 @@ RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_insert_unprotected(
}
/**
- * @brief Insert a node on a rbtree
- *
- * This routine inserts @a the_node on @a the_rbtree.
- * It disables interrupts to ensure the atomicity of the insert operation.
- *
- * @retval 0 Successfully inserted.
- * @retval -1 NULL @a the_node.
- * @retval RBTree_Node* if one with equal key to the key of @a the_node exists
- * in an unique @a the_rbtree.
+ * @copydoc _RBTree_Insert()
*/
RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_insert(
rtems_rbtree_control *the_rbtree,
@@ -482,6 +480,18 @@ RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_insert(
return _RBTree_Insert( the_rbtree, the_node );
}
+/**
+ * @copydoc _RBTree_Insert_finger()
+ */
+RTEMS_INLINE_ROUTINE void rtems_rbtree_insert_finger(
+ rtems_rbtree_control *the_rbtree,
+ rtems_rbtree_node *the_node,
+ rtems_rbtree_node *finger
+)
+{
+ _RBTree_Insert_finger( the_rbtree, the_node, finger );
+}
+
/** @brief Determines whether the tree sorts node in stable (FIFO) order.
*/
RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_stable(
diff --git a/cpukit/score/include/rtems/score/rbtree.h b/cpukit/score/include/rtems/score/rbtree.h
index b0affe7..ae83697 100644
--- a/cpukit/score/include/rtems/score/rbtree.h
+++ b/cpukit/score/include/rtems/score/rbtree.h
@@ -219,12 +219,22 @@ RBTree_Node *_RBTree_Get(
RBTree_Direction dir
);
+/** @brief Find the node with given key in the tree
+ *
+ * This function returns a pointer to the node in @a the_rbtree
+ * having key equal to key of @a the_node if it exists,
+ * and NULL if not. @a the_node has to be made up before a search.
+ * If the tree is stable duplicate keys act as FIFO.
+ */
+RBTree_Node *_RBTree_Find_unprotected(
+ RBTree_Control *the_rbtree,
+ RBTree_Node *the_node
+);
+
/**
- * @brief Find the node with given key in the tree
+ * @copydoc _RBTree_Find_unprotected()
*
- * This function returns a pointer to the node with key equal to a key
- * of @a the_node if it exists in the Red-Black Tree @a the_rbtree,
- * and NULL if not.
+ * This function disables interrupts to protect the operation.
*/
RBTree_Node *_RBTree_Find(
RBTree_Control *the_rbtree,
@@ -232,6 +242,17 @@ RBTree_Node *_RBTree_Find(
);
/**
+ * @copydoc _RBTree_Find_unprotected()
+ *
+ * This function starts at a finger node instead of the root node.
+ */
+RBTree_Node *_RBTree_Find_finger(
+ RBTree_Control *the_rbtree,
+ RBTree_Node *the_node,
+ RBTree_Node *finger
+);
+
+/**
* @brief Find the control structure of the tree containing the given node
*
* This function returns a pointer to the control structure of the tree
@@ -242,17 +263,26 @@ RBTree_Control *_RBTree_Find_header(
);
/**
- * @brief Insert a Node (unprotected)
+ * @brief Insert a node as a descendent of a finger node.
*
- * This routine inserts @a the_node on the Red-Black Tree @a the_rbtree.
+ * @param[in] the_rbtree The red-black tree.
+ * @param[in] finger Ancestor of new node.
+ * @param[in] the_node The node to insert.
+ */
+void _RBTree_Insert_finger(
+ RBTree_Control *the_rbtree,
+ RBTree_Node *the_node,
+ RBTree_Node *finger
+);
+
+/**
+ * @brief Inserts a node into a red-black tree.
*
- * @retval 0 Successfully inserted.
- * @retval -1 NULL @a the_node.
- * @retval RBTree_Node* if one with equal value to @a the_node 's key exists
- * in an unique @a the_rbtree.
+ * @param[in] the_rbtree The red-black tree.
+ * @param[in] the_node The node to insert.
*
- * @note It does NOT disable interrupts to ensure the atomicity
- * of the extract operation.
+ * @retval @a the_node if successfully inserted.
+ * @retval NULL otherwise.
*/
RBTree_Node *_RBTree_Insert_unprotected(
RBTree_Control *the_rbtree,
@@ -260,24 +290,15 @@ RBTree_Node *_RBTree_Insert_unprotected(
);
/**
- * @brief Insert a node on a rbtree
- *
- * This routine inserts @a the_node on the tree @a the_rbtree.
+ * @copydoc _RBTree_Insert_unprotected()
*
- * @retval 0 Successfully inserted.
- * @retval -1 NULL @a the_node.
- * @retval RBTree_Node* if one with equal value to @a the_node 's key exists
- * in an unique @a the_rbtree.
- *
- * @note It disables interrupts to ensure the atomicity
- * of the extract operation.
+ * The function disables interrupts to protect the operation.
*/
RBTree_Node *_RBTree_Insert(
RBTree_Control *the_rbtree,
RBTree_Node *the_node
);
-
/**
* @brief Extract a Node (unprotected)
*
diff --git a/cpukit/score/inline/rtems/score/rbtree.inl b/cpukit/score/inline/rtems/score/rbtree.inl
index 91e0d65..d75ff96 100644
--- a/cpukit/score/inline/rtems/score/rbtree.inl
+++ b/cpukit/score/inline/rtems/score/rbtree.inl
@@ -341,39 +341,6 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Is_lesser(
return compare_result < 0;
}
-/** @brief Find the node with given key in the tree
- *
- * This function returns a pointer to the node in @a the_rbtree
- * having key equal to key of @a the_node if it exists,
- * and NULL if not. @a the_node has to be made up before a search.
- *
- * @note If the tree is not unique and contains duplicate keys, the set
- * of duplicate keys acts as FIFO.
- */
-RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Find_unprotected(
- RBTree_Control *the_rbtree,
- RBTree_Node *the_node
- )
-{
- RBTree_Node* iter_node = the_rbtree->root;
- RBTree_Node* found = NULL;
- int compare_result;
- while (iter_node) {
- compare_result = the_rbtree->compare_function(the_node, iter_node);
- if ( _RBTree_Is_equal( compare_result ) ) {
- found = iter_node;
- if ( !the_rbtree->is_stable )
- break;
- }
-
- RBTree_Direction dir =
- (RBTree_Direction) _RBTree_Is_greater( compare_result );
- iter_node = iter_node->child[dir];
- } /* while(iter_node) */
-
- return found;
-}
-
/**
* @brief Returns the predecessor of a node.
*
@@ -489,6 +456,33 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Is_stable(
{
return( the_rbtree && the_rbtree->is_stable );
}
+
+/**
+ * @brief Returns the closest common ancestor of two nodes.
+ *
+ */
+RTEMS_INLINE_ROUTINE RBTree_Node* _RBTree_Common_ancestor(
+ const RBTree_Control *the_rbtree,
+ const RBTree_Node *the_node,
+ RBTree_Node *finger
+)
+{
+ int compare_result;
+ RBTree_Direction dir;
+ RBTree_Node* ancestor = finger;
+
+ while ( finger->parent->parent ) {
+ compare_result = the_rbtree->compare_function(the_node, finger->parent);
+ dir = (RBTree_Direction)_RBTree_Is_greater( compare_result );
+ if ( finger != finger->parent->child[dir] ) {
+ /* finger is not on path between the_node and root. reset ancestor. */
+ ancestor = finger->parent;
+ }
+ finger = finger->parent;
+ }
+ return ancestor;
+}
+
/**@}*/
#endif
diff --git a/cpukit/score/src/rbtreefind.c b/cpukit/score/src/rbtreefind.c
index 904a5b8..57841ad 100644
--- a/cpukit/score/src/rbtreefind.c
+++ b/cpukit/score/src/rbtreefind.c
@@ -1,11 +1,17 @@
+/**
+ * @file
+ *
+ * @ingroup ScoreRBTree
+ *
+ * @brief _RBTree_Find_finger, _RBTree_Find_unprotected, and _RBTree_Find.
+ */
+
/*
- * Copyright (c) 2010 Gedare Bloom.
+ * Copyright (c) 2010-2012 Gedare Bloom.
*
* The license and distribution terms for this file may be
* found in the file LICENSE in this distribution or at
* http://www.rtems.com/license/LICENSE.
- *
- * $Id$
*/
#if HAVE_CONFIG_H
@@ -17,24 +23,44 @@
#include <rtems/score/rbtree.h>
#include <rtems/score/isr.h>
-/*
- * _RBTree_Find
- *
- * This kernel routine returns a pointer to the rbtree node containing the
- * given key within the given tree, if it exists, or NULL otherwise.
- *
- * Input parameters:
- * the_rbtree - pointer to rbtree control
- * search_node - node with the key to search for
- *
- * Output parameters:
- * return_node - pointer to control header of rbtree
- * NULL - if there is no control header available (the node is not part
- * of a tree)
- *
- * INTERRUPT LATENCY:
- * only case
- */
+RBTree_Node *_RBTree_Find_finger(
+ RBTree_Control *the_rbtree,
+ RBTree_Node *the_node,
+ RBTree_Node *finger
+)
+{
+ RBTree_Node* iter_node;
+ RBTree_Node* found = NULL;
+ RBTree_Direction dir;
+ int compare_result;
+
+ /* first make sure the finger is good. this can be cheaper if a finger
+ * path is kept to the root instead of reconstructing it here. */
+ iter_node = _RBTree_Common_ancestor(the_rbtree, the_node, finger);
+
+ while ( iter_node ) {
+ compare_result = the_rbtree->compare_function( the_node, iter_node );
+ if ( _RBTree_Is_equal( compare_result ) ) {
+ found = iter_node;
+ if ( !the_rbtree->is_stable )
+ break;
+ }
+
+ dir = (RBTree_Direction)_RBTree_Is_greater( compare_result );
+ iter_node = iter_node->child[dir];
+ }
+
+ return found;
+}
+
+RBTree_Node *_RBTree_Find_unprotected(
+ RBTree_Control *the_rbtree,
+ RBTree_Node *the_node
+)
+{
+ RBTree_Node* root = the_rbtree->root;
+ return _RBTree_Find_finger(the_rbtree, the_node, root);
+}
RBTree_Node *_RBTree_Find(
RBTree_Control *the_rbtree,
@@ -46,7 +72,7 @@ RBTree_Node *_RBTree_Find(
return_node = NULL;
_ISR_Disable( level );
- return_node = _RBTree_Find_unprotected( the_rbtree, search_node );
+ return_node = _RBTree_Find_unprotected( the_rbtree, search_node );
_ISR_Enable( level );
return return_node;
}
diff --git a/cpukit/score/src/rbtreeinsert.c b/cpukit/score/src/rbtreeinsert.c
index 74f8a33..d40cbde 100644
--- a/cpukit/score/src/rbtreeinsert.c
+++ b/cpukit/score/src/rbtreeinsert.c
@@ -1,155 +1,158 @@
+/**
+ * @file
+ *
+ * @ingroup ScoreRBTree
+ *
+ * @brief _RBTree_Insert_finger, _RBTree_Insert_unprotected, and _RBTree_Insert.
+ */
+
/*
- * Copyright (c) 2010 Gedare Bloom.
+ * Copyright (c) 2010-2012 Gedare Bloom.
*
* The license and distribution terms for this file may be
* found in the file LICENSE in this distribution or at
* http://www.rtems.com/license/LICENSE.
- *
- * $Id$
*/
#if HAVE_CONFIG_H
#include "config.h"
#endif
-#include <rtems/system.h>
-#include <rtems/score/address.h>
#include <rtems/score/rbtree.h>
#include <rtems/score/isr.h>
-/** @brief Validate and fix-up tree properties for a new insert/colored node
+/*
+ * Validate and fix-up tree properties for a newly inserted/colored node.
*
- * This routine checks and fixes the Red-Black Tree properties based on
- * @a the_node being just added to the tree.
+ * Checks and fixes the red-black tree properties based on the_node being
+ * just added to the tree as a leaf with the color red.
*
- * @note It does NOT disable interrupts to ensure the atomicity of the
- * append operation.
+ * Note: the insert root case is handled already so no special care is needed.
*/
static void _RBTree_Validate_insert_unprotected(
RBTree_Node *the_node
- )
+)
{
- RBTree_Node *u,*g;
+ RBTree_Node *u;
+ RBTree_Node *g;
- /* note: the insert root case is handled already */
/* if the parent is black, nothing needs to be done
* otherwise may need to loop a few times */
- while (_RBTree_Is_red(_RBTree_Parent(the_node))) {
- u = _RBTree_Parent_sibling(the_node);
+ while ( _RBTree_Is_red( _RBTree_Parent( the_node ) ) ) {
+ u = _RBTree_Parent_sibling( the_node );
g = the_node->parent->parent;
/* if uncle is red, repaint uncle/parent black and grandparent red */
- if(_RBTree_Is_red(u)) {
+ if( _RBTree_Is_red( u ) ) {
the_node->parent->color = RBT_BLACK;
u->color = RBT_BLACK;
g->color = RBT_RED;
the_node = g;
} else { /* if uncle is black */
- RBTree_Direction dir = the_node != the_node->parent->child[0];
- RBTree_Direction pdir = the_node->parent != g->child[0];
+ RBTree_Direction dir;
+ RBTree_Direction pdir;
+ dir = the_node != the_node->parent->child[0];
+ pdir = the_node->parent != g->child[0];
/* ensure node is on the same branch direction as parent */
- if (dir != pdir) {
- _RBTree_Rotate(the_node->parent, pdir);
+ if ( dir != pdir ) {
+ _RBTree_Rotate( the_node->parent, pdir );
the_node = the_node->child[pdir];
}
the_node->parent->color = RBT_BLACK;
g->color = RBT_RED;
/* now rotate grandparent in the other branch direction (toward uncle) */
- _RBTree_Rotate(g, (1-pdir));
+ _RBTree_Rotate( g, ( 1 - pdir ) );
}
}
- if(!the_node->parent->parent) the_node->color = RBT_BLACK;
+
+ /* if the_node is now the root recolor it black */
+ if ( !the_node->parent->parent ) {
+ the_node->color = RBT_BLACK;
+ }
}
+void _RBTree_Insert_finger(
+ RBTree_Control *the_rbtree,
+ RBTree_Node *the_node,
+ RBTree_Node *finger
+)
+{
+ int compare_result;
+ RBTree_Direction dir;
+ RBTree_Node* iter_node;
+
+ /* first make sure the finger is good. this can be cheaper if a finger
+ * path is kept to the root instead of reconstructing it here. */
+ iter_node = _RBTree_Common_ancestor(the_rbtree, the_node, finger);
+
+ /* descend tree to leaf and insert */
+ while ( iter_node ) {
+ compare_result = the_rbtree->compare_function( the_node, iter_node );
+ dir = !_RBTree_Is_lesser( compare_result );
+ if ( !iter_node->child[dir] ) {
+ /* found insertion point: iter_node->child[dir] */
+ the_node->child[RBT_LEFT] = the_node->child[RBT_RIGHT] = NULL;
+ the_node->color = RBT_RED;
+ iter_node->child[dir] = the_node;
+ the_node->parent = iter_node;
+
+ /* update min/max */
+ compare_result = the_rbtree->compare_function(
+ the_node,
+ _RBTree_First(the_rbtree, dir)
+ );
+ if ( ( !dir && _RBTree_Is_lesser( compare_result ) ) ||
+ ( dir && _RBTree_Is_greater( compare_result ) ) ) {
+ the_rbtree->first[dir] = the_node;
+ }
+ break;
+ } else {
+ iter_node = iter_node->child[dir];
+ }
+ } /* while(iter_node) */
+ /* verify red-black properties */
+ _RBTree_Validate_insert_unprotected(the_node);
+}
-/** @brief Insert a Node (unprotected)
- *
- * This routine inserts @a the_node on the Red-Black Tree @a the_rbtree.
- *
- * @retval 0 Successfully inserted.
- * @retval -1 NULL @a the_node.
- * @retval RBTree_Node* if one with equal key to the key of @a the_node exists
- * in an unique @a the_rbtree.
- *
- * @note It does NOT disable interrupts to ensure the atomicity
- * of the extract operation.
- */
RBTree_Node *_RBTree_Insert_unprotected(
- RBTree_Control *the_rbtree,
- RBTree_Node *the_node
- )
+ RBTree_Control *the_rbtree,
+ RBTree_Node *the_node
+)
{
- if(!the_node) return (RBTree_Node*)-1;
+ RBTree_Node *root_node;
- RBTree_Node *iter_node = the_rbtree->root;
- int compare_result;
+ if ( !the_node ) {
+ return NULL;
+ }
- if (!iter_node) { /* special case: first node inserted */
+ root_node = the_rbtree->root;
+
+ if ( !root_node ) {
+ /* special case: node inserted to empty tree */
the_node->color = RBT_BLACK;
the_rbtree->root = the_node;
the_rbtree->first[0] = the_rbtree->first[1] = the_node;
the_node->parent = (RBTree_Node *) the_rbtree;
the_node->child[RBT_LEFT] = the_node->child[RBT_RIGHT] = NULL;
} else {
- /* typical binary search tree insert, descend tree to leaf and insert */
- while (iter_node) {
- compare_result = the_rbtree->compare_function(the_node, iter_node);
- RBTree_Direction dir = !_RBTree_Is_lesser( compare_result );
- if (!iter_node->child[dir]) {
- the_node->child[RBT_LEFT] = the_node->child[RBT_RIGHT] = NULL;
- the_node->color = RBT_RED;
- iter_node->child[dir] = the_node;
- the_node->parent = iter_node;
- /* update min/max */
- compare_result = the_rbtree->compare_function(
- the_node,
- _RBTree_First(the_rbtree, dir)
- );
- if ( (!dir && _RBTree_Is_lesser(compare_result)) ||
- (dir && _RBTree_Is_greater(compare_result)) ) {
- the_rbtree->first[dir] = the_node;
- }
- break;
- } else {
- iter_node = iter_node->child[dir];
- }
-
- } /* while(iter_node) */
-
- /* verify red-black properties */
- _RBTree_Validate_insert_unprotected(the_node);
+ _RBTree_Insert_finger( the_rbtree, the_node, root_node );
}
- return (RBTree_Node*)0;
+ return the_node;
}
-
-/*
- * _RBTree_Insert
- *
- * This kernel routine inserts a given node after a specified node
- * a requested rbtree.
- *
- * Input parameters:
- * tree - pointer to RBTree Control for tree to insert to
- * node - pointer to node to be inserted
- *
- * Output parameters: NONE
- *
- * INTERRUPT LATENCY:
- * only case
- */
-
RBTree_Node *_RBTree_Insert(
RBTree_Control *tree,
RBTree_Node *node
)
{
ISR_Level level;
+ RBTree_Node *return_node;
_ISR_Disable( level );
- return _RBTree_Insert_unprotected( tree, node );
+ return_node = _RBTree_Insert_unprotected( tree, node );
_ISR_Enable( level );
+ return return_node;
}
diff --git a/testsuites/sptests/sprbtree01/init.c b/testsuites/sptests/sprbtree01/init.c
index 15e17e5..7f3aaf3 100644
--- a/testsuites/sptests/sprbtree01/init.c
+++ b/testsuites/sptests/sprbtree01/init.c
@@ -545,6 +545,47 @@ rtems_task Init(
rtems_test_exit(0);
}
+ puts( "INIT - Verify rtems_rbtree_insert_finger" );
+ node_array[0].id = numbers[0];
+ node_array[0].key = numbers[0];
+ rtems_rbtree_insert( &rbtree1, &node_array[0].Node );
+ for (i = 1; i < 20; i++) {
+ node_array[i].id = numbers[i];
+ node_array[i].key = numbers[i];
+ rtems_rbtree_insert_finger(
+ &rbtree1,
+ &node_array[i].Node,
+ &node_array[i-1].Node
+ );
+
+ if (!rb_assert(rbtree1.root) )
+ puts( "INIT - FAILED TREE CHECK" );
+ }
+
+ puts( "INIT - Removing 20 nodes" );
+
+ for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ;
+ p = rtems_rbtree_get_min(&rbtree1) , id++ ) {
+ test_node *t = rtems_rbtree_container_of(p,test_node,Node);
+ if ( id > 19 ) {
+ puts( "INIT - TOO MANY NODES ON RBTREE" );
+ rtems_test_exit(0);
+ }
+ if ( t->id != numbers_sorted[id] ) {
+ puts( "INIT - ERROR ON RBTREE ID MISMATCH" );
+ rtems_test_exit(0);
+ }
+
+ if (!rb_assert(rbtree1.root) )
+ puts( "INIT - FAILED TREE CHECK" );
+ }
+
+ if(!rtems_rbtree_is_empty(&rbtree1)) {
+ puts( "INIT - TREE NOT EMPTY" );
+ rtems_test_exit(0);
+ }
+
+
/* Initialize the tree for duplicate keys */
puts( "Init - Initialize duplicate rbtree empty" );
rtems_rbtree_initialize_empty( &rbtree1, &test_compare_function, true );
--
1.7.1
More information about the devel
mailing list