[PATCH] rbtree: Add finger versions of Insert and Find.
Gedare Bloom
gedare at rtems.org
Thu May 3 23:02:16 UTC 2012
The addition of the fingers currently only decreases performance and I
need to go study how they should be working. A newer version of this
patch will come later.
On Thu, May 3, 2012 at 4:00 PM, Gedare Bloom <gedare at rtems.org> wrote:
> 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