[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