From 833dd903356eae776975fc8e43a96687430f2e64 Mon Sep 17 00:00:00 2001 From: Sebastian Huber Date: Tue, 19 Nov 2013 16:09:39 +0100 Subject: score/rbtree: Delete protected operations The user of the red-black tree container must now ensure that at most one thread at once can access an instance. --- cpukit/sapi/include/rtems/rbtree.h | 112 ------------------------ cpukit/score/Makefile.am | 4 +- cpukit/score/include/rtems/score/rbtree.h | 141 ++---------------------------- cpukit/score/src/rbtreeextract.c | 27 ------ cpukit/score/src/rbtreefind.c | 15 ---- cpukit/score/src/rbtreefindheader.c | 38 -------- cpukit/score/src/rbtreeget.c | 37 -------- cpukit/score/src/rbtreeinsert.c | 31 ------- cpukit/score/src/rbtreenext.c | 15 ---- testsuites/sptests/sprbtree01/init.c | 128 +++++++++++++-------------- 10 files changed, 73 insertions(+), 475 deletions(-) delete mode 100644 cpukit/score/src/rbtreefindheader.c delete mode 100644 cpukit/score/src/rbtreeget.c diff --git a/cpukit/sapi/include/rtems/rbtree.h b/cpukit/sapi/include/rtems/rbtree.h index bce7013fd9..5cbdab46c2 100644 --- a/cpukit/sapi/include/rtems/rbtree.h +++ b/cpukit/sapi/include/rtems/rbtree.h @@ -309,23 +309,6 @@ 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. - */ -RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_find( - const rtems_rbtree_control *the_rbtree, - const rtems_rbtree_node *the_node -) -{ - return _RBTree_Find( the_rbtree, the_node ); -} - /** * @copydoc _RBTree_Predecessor_unprotected() */ @@ -336,16 +319,6 @@ RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_predecessor_unprotected( return _RBTree_Predecessor_unprotected( node ); } -/** - * @copydoc _RBTree_Predecessor() - */ -RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_predecessor( - const rtems_rbtree_node *node -) -{ - return _RBTree_Predecessor( node ); -} - /** * @copydoc _RBTree_Successor_unprotected() */ @@ -356,16 +329,6 @@ RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_successor_unprotected( return _RBTree_Successor_unprotected( node ); } -/** - * @copydoc _RBTree_Successor() - */ -RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_successor( - const rtems_rbtree_node *node -) -{ - return _RBTree_Successor( node ); -} - /** * @copydoc _RBTree_Extract_unprotected() */ @@ -377,20 +340,6 @@ RTEMS_INLINE_ROUTINE void rtems_rbtree_extract_unprotected( _RBTree_Extract_unprotected( the_rbtree, the_node ); } -/** - * @brief Extract the specified node from a rbtree. - * - * This routine extracts @a the_node from @a the_rbtree on which it resides. - * It disables interrupts to ensure the atomicity of the extract operation. - */ -RTEMS_INLINE_ROUTINE void rtems_rbtree_extract( - rtems_rbtree_control *the_rbtree, - rtems_rbtree_node *the_node -) -{ - _RBTree_Extract( the_rbtree, the_node ); -} - /** * @brief Obtain the min node on a rbtree. * @@ -405,20 +354,6 @@ RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_get_min_unprotected( return _RBTree_Get_unprotected( the_rbtree, RBT_LEFT ); } -/** - * @brief Obtain the min node on a rbtree. - * - * This function removes the min node from @a the_rbtree and returns - * a pointer to that node. If @a the_rbtree is empty, then NULL is returned. - * It disables interrupts to ensure the atomicity of the get operation. - */ -RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_get_min( - rtems_rbtree_control *the_rbtree -) -{ - return _RBTree_Get( the_rbtree, RBT_LEFT ); -} - /** * @brief Obtain the max node on a rbtree. * @@ -433,20 +368,6 @@ RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_get_max_unprotected( return _RBTree_Get_unprotected( the_rbtree, RBT_RIGHT ); } -/** - * @brief Obtain the max node on a rbtree. - * - * This function removes the max node from @a the_rbtree and returns - * a pointer to that node. If @a the_rbtree is empty, then NULL is returned. - * It disables interrupts to ensure the atomicity of the get operation. - */ -RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_get_max( - rtems_rbtree_control *the_rbtree -) -{ - return _RBTree_Get( the_rbtree, RBT_RIGHT ); -} - /** * @brief Peek at the min node on a rbtree. * @@ -485,20 +406,6 @@ RTEMS_INLINE_ROUTINE rtems_rbtree_control *rtems_rbtree_find_header_unprotected( return _RBTree_Find_header_unprotected( the_node ); } -/** - * @brief Find the control header of the tree containing a given node. - * - * This routine finds the rtems_rbtree_control structure of the tree - * containing @a the_node. - * It disables interrupts to ensure the atomicity of the find operation. - */ -RTEMS_INLINE_ROUTINE rtems_rbtree_control *rtems_rbtree_find_header( - rtems_rbtree_node *the_node -) -{ - return _RBTree_Find_header( the_node ); -} - /** * @copydoc _RBTree_Insert_unprotected() */ @@ -510,25 +417,6 @@ RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_insert_unprotected( return _RBTree_Insert_unprotected( the_rbtree, the_node ); } -/** - * @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. - */ -RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_insert( - rtems_rbtree_control *the_rbtree, - rtems_rbtree_node *the_node -) -{ - return _RBTree_Insert( the_rbtree, the_node ); -} - /** * @brief Determines whether the tree is unique. */ diff --git a/cpukit/score/Makefile.am b/cpukit/score/Makefile.am index c9d2d477d3..4570ffd16a 100644 --- a/cpukit/score/Makefile.am +++ b/cpukit/score/Makefile.am @@ -260,8 +260,8 @@ libscore_a_SOURCES += src/freechain.c ## RBTREE_C_FILES libscore_a_SOURCES += src/rbtree.c \ - src/rbtreeextract.c src/rbtreefind.c src/rbtreefindheader.c \ - src/rbtreeget.c src/rbtreeinsert.c src/rbtreeiterate.c src/rbtreenext.c + src/rbtreeextract.c src/rbtreefind.c \ + src/rbtreeinsert.c src/rbtreeiterate.c src/rbtreenext.c ## THREAD_C_FILES libscore_a_SOURCES += src/thread.c src/threadchangepriority.c \ diff --git a/cpukit/score/include/rtems/score/rbtree.h b/cpukit/score/include/rtems/score/rbtree.h index 1414bdf04f..a3744e57e3 100644 --- a/cpukit/score/include/rtems/score/rbtree.h +++ b/cpukit/score/include/rtems/score/rbtree.h @@ -207,74 +207,20 @@ void _RBTree_Initialize( ); /** - * @brief Obtain the min or max node of a rbtree. + * @brief Tries to find a node for the specified key in the tree. * - * This function removes the min or max node from @a the_rbtree and returns - * a pointer to that node. If @a the_rbtree is empty, then NULL is returned. - * @a dir specifies whether to return the min (0) or max (1). + * @param[in] the_rbtree The red-black tree control. + * @param[in] the_node A node specifying the key. * - * @retval This method returns a pointer to a node. If a node was removed, - * then a pointer to that node is returned. If @a the_rbtree was - * empty, then NULL is returned. - * - * @note It disables interrupts to ensure the atomicity of the get operation. - */ -RBTree_Node *_RBTree_Get( - RBTree_Control *the_rbtree, - 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. - * - * @note If the tree is not unique and contains duplicate keys, the set - * of duplicate keys acts as FIFO. + * @retval node A node corresponding to the key. If the tree is not unique + * and contains duplicate keys, the set of duplicate keys acts as FIFO. + * @retval NULL No node exists in the tree for the key. */ RBTree_Node *_RBTree_Find_unprotected( const RBTree_Control *the_rbtree, const RBTree_Node *the_node ); -/** - * @brief Find the node with given key in the tree. - * - * 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. - * - * @param[in] the_rbtree pointer to rbtree control - * @param[in] the_node node with the key to search for - * @retval This method returns pointer to control header of rbtree. * - * If there is no control header available (the node is not part - * of a tree), then NULL is returned. * - * - * - INTERRUPT LATENCY: - * + single case - */ -RBTree_Node *_RBTree_Find( - const RBTree_Control *the_rbtree, - const RBTree_Node *the_node -); - -/** - * @brief Find the control structure of the tree containing the given node. - * - * This function returns a pointer called @a return_header to the - * control structure of the tree containing @a the_node, if it exists, - * and @a NULL if not. - * - * @param[in] the_node is the pointer to the rbtree node. - * - * -INTERRUPT LATENCY: - * + single case - */ -RBTree_Control *_RBTree_Find_header( - RBTree_Node *the_node -); - /** * @brief Insert @a the_node on the Red-Black Tree @a the_rbtree (unprotected). * @@ -284,60 +230,22 @@ RBTree_Control *_RBTree_Find_header( * @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 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 ); -/** - * @brief Insert a node on a rbtree. - * - * This routine inserts @a the_node on the tree @a the_rbtree. - * - * @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. - */ -RBTree_Node *_RBTree_Insert( - RBTree_Control *the_rbtree, - RBTree_Node *the_node -); - - /** * @brief Extracts (removes) @a the_node from @a the_rbtree (unprotected). * * This routine extracts (removes) @a the_node from @a the_rbtree. - * - * @note It does NOT disable interrupts to ensure the atomicity - * of the extract operation. */ void _RBTree_Extract_unprotected( RBTree_Control *the_rbtree, RBTree_Node *the_node ); -/** - * @brief Delete a node from the rbtree. - * - * This routine deletes @a the_node from @a the_rbtree. - * - * @note It disables interrupts to ensure the atomicity of the - * append operation. - */ -void _RBTree_Extract( - RBTree_Control *the_rbtree, - RBTree_Node *the_node -); - /** * @brief Returns the in-order next node of a node. * @@ -352,16 +260,6 @@ RBTree_Node *_RBTree_Next_unprotected( RBTree_Direction dir ); -/** - * @copydoc _RBTree_Next_unprotected() - * - * The function disables the interrupts protect the operation. - */ -RBTree_Node *_RBTree_Next( - const RBTree_Node *node, - RBTree_Direction dir -); - /** * @brief Set off RBtree. * @@ -617,18 +515,6 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Predecessor_unprotected( return _RBTree_Next_unprotected( node, RBT_LEFT ); } -/** - * @copydoc _RBTree_Predecessor_unprotected() - * - * The function disables the interrupts protect the operation. - */ -RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Predecessor( - const RBTree_Node *node -) -{ - return _RBTree_Next( node, RBT_LEFT ); -} - /** * @brief Returns the successor of a node. * @@ -643,24 +529,11 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Successor_unprotected( return _RBTree_Next_unprotected( node, RBT_RIGHT ); } -/** - * @copydoc _RBTree_Successor_unprotected() - * - * The function disables the interrupts protect the operation. - */ -RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Successor( - const RBTree_Node *node -) -{ - return _RBTree_Next( node, RBT_RIGHT ); -} - /** * @brief Get the first node (unprotected). * * This function removes the minimum or maximum node from the_rbtree and - * returns a pointer to that node. It does NOT disable interrupts to ensure - * the atomicity of the get operation. + * returns a pointer to that node. * * @param[in] the_rbtree is the rbtree to attempt to get the min node from. * @param[in] dir specifies whether to get minimum (0) or maximum (1) diff --git a/cpukit/score/src/rbtreeextract.c b/cpukit/score/src/rbtreeextract.c index 0f38fbc325..8dafe3b72c 100644 --- a/cpukit/score/src/rbtreeextract.c +++ b/cpukit/score/src/rbtreeextract.c @@ -202,30 +202,3 @@ void _RBTree_Extract_unprotected( /* set root to black, if it exists */ if (the_rbtree->root) the_rbtree->root->color = RBT_BLACK; } - - -/* - * _RBTree_Extract - * - * This kernel routine deletes the given node from a rbtree. - * - * Input parameters: - * node - pointer to node in rbtree to be deleted - * - * Output parameters: NONE - * - * INTERRUPT LATENCY: - * only case - */ - -void _RBTree_Extract( - RBTree_Control *the_rbtree, - RBTree_Node *the_node -) -{ - ISR_Level level; - - _ISR_Disable( level ); - _RBTree_Extract_unprotected( the_rbtree, the_node ); - _ISR_Enable( level ); -} diff --git a/cpukit/score/src/rbtreefind.c b/cpukit/score/src/rbtreefind.c index b485845dbd..9b2663d493 100644 --- a/cpukit/score/src/rbtreefind.c +++ b/cpukit/score/src/rbtreefind.c @@ -20,21 +20,6 @@ #include #include -RBTree_Node *_RBTree_Find( - const RBTree_Control *the_rbtree, - const RBTree_Node *search_node -) -{ - ISR_Level level; - RBTree_Node *return_node; - - return_node = NULL; - _ISR_Disable( level ); - return_node = _RBTree_Find_unprotected( the_rbtree, search_node ); - _ISR_Enable( level ); - return return_node; -} - RBTree_Node *_RBTree_Find_unprotected( const RBTree_Control *the_rbtree, const RBTree_Node *the_node diff --git a/cpukit/score/src/rbtreefindheader.c b/cpukit/score/src/rbtreefindheader.c deleted file mode 100644 index 2368a11428..0000000000 --- a/cpukit/score/src/rbtreefindheader.c +++ /dev/null @@ -1,38 +0,0 @@ -/** - * @file - * - * @brief Finds the Header of a Tree if it Exists - * - * @ingroup ScoreRBTree - */ - -/* - * Copyright (c) 2010 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. - */ - -#if HAVE_CONFIG_H -#include "config.h" -#endif - -#include -#include -#include -#include - -RBTree_Control *_RBTree_Find_header( - RBTree_Node *the_node -) -{ - ISR_Level level; - RBTree_Control *return_header; - - return_header = NULL; - _ISR_Disable( level ); - return_header = _RBTree_Find_header_unprotected( the_node ); - _ISR_Enable( level ); - return return_header; -} diff --git a/cpukit/score/src/rbtreeget.c b/cpukit/score/src/rbtreeget.c deleted file mode 100644 index a805a4090f..0000000000 --- a/cpukit/score/src/rbtreeget.c +++ /dev/null @@ -1,37 +0,0 @@ -/** - * @file - * - * @brief Obtain the min or max node of a rbtree - * @ingroup ScoreRBTree - */ - -/* - * Copyright (c) 2010 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. - */ - -#if HAVE_CONFIG_H -#include "config.h" -#endif - -#include -#include - -RBTree_Node *_RBTree_Get( - RBTree_Control *the_rbtree, - RBTree_Direction dir -) -{ - ISR_Level level; - RBTree_Node *return_node; - - return_node = NULL; - _ISR_Disable( level ); - return_node = _RBTree_Get_unprotected( the_rbtree, dir ); - _ISR_Enable( level ); - return return_node; -} - diff --git a/cpukit/score/src/rbtreeinsert.c b/cpukit/score/src/rbtreeinsert.c index 0d8e4a6dc4..a2f6f09ab3 100644 --- a/cpukit/score/src/rbtreeinsert.c +++ b/cpukit/score/src/rbtreeinsert.c @@ -122,34 +122,3 @@ RBTree_Node *_RBTree_Insert_unprotected( } return (RBTree_Node*)0; } - - -/* - * _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_node = _RBTree_Insert_unprotected( tree, node ); - _ISR_Enable( level ); - return return_node; -} diff --git a/cpukit/score/src/rbtreenext.c b/cpukit/score/src/rbtreenext.c index 7dd305a3dc..f3268d246b 100644 --- a/cpukit/score/src/rbtreenext.c +++ b/cpukit/score/src/rbtreenext.c @@ -60,18 +60,3 @@ RBTree_Node *_RBTree_Next_unprotected( return next; } - -RBTree_Node *_RBTree_Next( - const RBTree_Node *node, - RBTree_Direction dir -) -{ - RBTree_Node *next; - ISR_Level level; - - _ISR_Disable( level ); - next = _RBTree_Next_unprotected( node, dir ); - _ISR_Enable( level ); - - return next; -} diff --git a/testsuites/sptests/sprbtree01/init.c b/testsuites/sptests/sprbtree01/init.c index df2a947aaa..a0dd9b987a 100644 --- a/testsuites/sptests/sprbtree01/init.c +++ b/testsuites/sptests/sprbtree01/init.c @@ -117,10 +117,10 @@ rtems_task Init( node1.key = 1; node2.id = 2; node2.key = 2; - rtems_rbtree_insert( &rbtree1, &node1.Node ); - rtems_rbtree_insert( &rbtree1, &node2.Node ); + rtems_rbtree_insert_unprotected( &rbtree1, &node1.Node ); + rtems_rbtree_insert_unprotected( &rbtree1, &node2.Node ); - p = rtems_rbtree_insert( &rbtree1, NULL ); + p = rtems_rbtree_insert_unprotected( &rbtree1, NULL ); if (p != (void *)(-1)) puts( "INIT - FAILED NULL NODE INSERT" ); @@ -135,8 +135,8 @@ rtems_task Init( if (!rb_assert(rbtree1.root) ) puts( "INIT - FAILED TREE CHECK" ); - for ( p = rtems_rbtree_get_min(&rbtree1), id = 1 ; p ; - p = rtems_rbtree_get_min(&rbtree1) , id++ ) { + for ( p = rtems_rbtree_get_min_unprotected(&rbtree1), id = 1 ; p ; + p = rtems_rbtree_get_min_unprotected(&rbtree1) , id++ ) { test_node *t = rtems_rbtree_container_of(p,test_node,Node); if ( id > 2 ) { puts( "INIT - TOO MANY NODES ON RBTREE" ); @@ -157,14 +157,14 @@ rtems_task Init( puts("INIT - Verify rtems_rbtree_insert with the same value twice"); node2.key = node1.key; - rtems_rbtree_insert(&rbtree1, &node1.Node); - p = rtems_rbtree_insert(&rbtree1, &node2.Node); + rtems_rbtree_insert_unprotected(&rbtree1, &node1.Node); + p = rtems_rbtree_insert_unprotected(&rbtree1, &node2.Node); if (p != &node1.Node) puts( "INIT - FAILED DUPLICATE INSERT" ); - for ( p = rtems_rbtree_get_min(&rbtree1), id = 1 ; p ; - p = rtems_rbtree_get_min(&rbtree1) , id++ ) { + for ( p = rtems_rbtree_get_min_unprotected(&rbtree1), id = 1 ; p ; + p = rtems_rbtree_get_min_unprotected(&rbtree1) , id++ ) { test_node *t = rtems_rbtree_container_of(p,test_node,Node); if ( id > 1 ) { puts( "INIT - TOO MANY NODES ON RBTREE" ); @@ -192,11 +192,11 @@ rtems_task Init( } puts( "INIT - Verify rtems_XXX on an empty tree" ); - if(rtems_rbtree_get_min(&rbtree1)) { + if(rtems_rbtree_get_min_unprotected(&rbtree1)) { puts("INIT - get_min on empty returned non-NULL"); rtems_test_exit(0); } - if(rtems_rbtree_get_max(&rbtree1)) { + if(rtems_rbtree_get_max_unprotected(&rbtree1)) { puts("INIT - get_max on empty returned non-NULL"); rtems_test_exit(0); } @@ -216,8 +216,8 @@ rtems_task Init( node1.key = 2; node2.id = 1; node2.key = 1; - rtems_rbtree_insert( &rbtree1, &node1.Node ); - rtems_rbtree_insert( &rbtree1, &node2.Node ); + rtems_rbtree_insert_unprotected( &rbtree1, &node1.Node ); + rtems_rbtree_insert_unprotected( &rbtree1, &node2.Node ); puts( "INIT - Verify rtems_rbtree_peek_max/min, rtems_rbtree_extract" ); test_node *t1 = rtems_rbtree_container_of(rtems_rbtree_peek_max(&rbtree1), @@ -229,16 +229,16 @@ rtems_task Init( rtems_test_exit(0); } p = rtems_rbtree_peek_max(&rbtree1); - rtems_rbtree_extract(&rbtree1, p); + rtems_rbtree_extract_unprotected(&rbtree1, p); t1 = rtems_rbtree_container_of(p,test_node,Node); if (t1->key != 2) { puts( "INIT - rtems_rbtree_extract failed"); rtems_test_exit(0); } - rtems_rbtree_insert(&rbtree1, p); + rtems_rbtree_insert_unprotected(&rbtree1, p); - for ( p = rtems_rbtree_get_min(&rbtree1), id = 1 ; p ; - p = rtems_rbtree_get_min(&rbtree1) , id++ ) { + for ( p = rtems_rbtree_get_min_unprotected(&rbtree1), id = 1 ; p ; + p = rtems_rbtree_get_min_unprotected(&rbtree1) , id++ ) { test_node *t = rtems_rbtree_container_of(p,test_node,Node); if ( id > 2 ) { puts( "INIT - TOO MANY NODES ON RBTREE" ); @@ -254,7 +254,7 @@ rtems_task Init( for (i = 0; i < 100; i++) { node_array[i].id = i; node_array[i].key = i; - rtems_rbtree_insert( &rbtree1, &node_array[i].Node ); + rtems_rbtree_insert_unprotected( &rbtree1, &node_array[i].Node ); if (!rb_assert(rbtree1.root) ) puts( "INIT - FAILED TREE CHECK" ); @@ -262,8 +262,8 @@ rtems_task Init( puts( "INIT - Removing 100 nodes" ); - for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ; - p = rtems_rbtree_get_min(&rbtree1) , id++ ) { + for ( p = rtems_rbtree_get_min_unprotected(&rbtree1), id = 0 ; p ; + p = rtems_rbtree_get_min_unprotected(&rbtree1) , id++ ) { test_node *t = rtems_rbtree_container_of(p,test_node,Node); if ( id > 99 ) { puts( "INIT - TOO MANY NODES ON RBTREE" ); @@ -287,7 +287,7 @@ rtems_task Init( for (i = 0; i < 100; i++) { node_array[i].id = 99-i; node_array[i].key = 99-i; - rtems_rbtree_insert( &rbtree1, &node_array[i].Node ); + rtems_rbtree_insert_unprotected( &rbtree1, &node_array[i].Node ); if (!rb_assert(rbtree1.root) ) puts( "INIT - FAILED TREE CHECK" ); @@ -295,8 +295,8 @@ rtems_task Init( puts( "INIT - Removing 100 nodes" ); - for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ; - p = rtems_rbtree_get_min(&rbtree1) , id++ ) { + for ( p = rtems_rbtree_get_min_unprotected(&rbtree1), id = 0 ; p ; + p = rtems_rbtree_get_min_unprotected(&rbtree1) , id++ ) { test_node *t = rtems_rbtree_container_of(p,test_node,Node); if ( id > 99 ) { puts( "INIT - TOO MANY NODES ON RBTREE" ); @@ -322,7 +322,7 @@ rtems_task Init( for (i = 0; i < 100; i++) { node_array[i].id = i; node_array[i].key = i; - rtems_rbtree_insert( &rbtree1, &node_array[i].Node ); + rtems_rbtree_insert_unprotected( &rbtree1, &node_array[i].Node ); if (!rb_assert(rbtree1.root) ) puts( "INIT - FAILED TREE CHECK" ); @@ -332,15 +332,15 @@ rtems_task Init( for (i = 0; i < 20; i++) { id = numbers[i]; - rtems_rbtree_extract( &rbtree1, &node_array[id].Node ); + rtems_rbtree_extract_unprotected( &rbtree1, &node_array[id].Node ); if (!rb_assert(rbtree1.root) ) puts( "INIT - FAILED TREE CHECK" ); } puts( "INIT - Removing 80 nodes" ); - for ( p = rtems_rbtree_get_min(&rbtree1), id = 0, i = 0 ; p ; - p = rtems_rbtree_get_min(&rbtree1) , id++ ) { + for ( p = rtems_rbtree_get_min_unprotected(&rbtree1), id = 0, i = 0 ; p ; + p = rtems_rbtree_get_min_unprotected(&rbtree1) , id++ ) { test_node *t = rtems_rbtree_container_of(p, test_node, Node); while ( id == numbers_sorted[i] ) { @@ -374,26 +374,26 @@ rtems_task Init( node_array[i].id = i; node_array[i].key = i; } - rtems_rbtree_insert( &rbtree1, &node_array[3].Node ); - rtems_rbtree_insert( &rbtree1, &node_array[1].Node ); - rtems_rbtree_insert( &rbtree1, &node_array[5].Node ); - rtems_rbtree_insert( &rbtree1, &node_array[0].Node ); - rtems_rbtree_insert( &rbtree1, &node_array[2].Node ); - rtems_rbtree_insert( &rbtree1, &node_array[4].Node ); - rtems_rbtree_insert( &rbtree1, &node_array[6].Node ); - rtems_rbtree_extract( &rbtree1, &node_array[2].Node ); + rtems_rbtree_insert_unprotected( &rbtree1, &node_array[3].Node ); + rtems_rbtree_insert_unprotected( &rbtree1, &node_array[1].Node ); + rtems_rbtree_insert_unprotected( &rbtree1, &node_array[5].Node ); + rtems_rbtree_insert_unprotected( &rbtree1, &node_array[0].Node ); + rtems_rbtree_insert_unprotected( &rbtree1, &node_array[2].Node ); + rtems_rbtree_insert_unprotected( &rbtree1, &node_array[4].Node ); + rtems_rbtree_insert_unprotected( &rbtree1, &node_array[6].Node ); + rtems_rbtree_extract_unprotected( &rbtree1, &node_array[2].Node ); /* node_array[1] has now only a left child. */ if ( !node_array[1].Node.child[RBT_LEFT] || node_array[1].Node.child[RBT_RIGHT] ) puts( "INIT - LEFT CHILD ONLY NOT FOUND" ); - rtems_rbtree_extract( &rbtree1, &node_array[3].Node ); - while( (p = rtems_rbtree_get_max(&rbtree1)) ); + rtems_rbtree_extract_unprotected( &rbtree1, &node_array[3].Node ); + while( (p = rtems_rbtree_get_max_unprotected(&rbtree1)) ); puts( "INIT - Verify rtems_rbtree_get_max with 100 nodes value [99,0]" ); for (i = 0; i < 100; i++) { node_array[i].id = 99-i; node_array[i].key = 99-i; - rtems_rbtree_insert( &rbtree1, &node_array[i].Node ); + rtems_rbtree_insert_unprotected( &rbtree1, &node_array[i].Node ); if (!rb_assert(rbtree1.root) ) puts( "INIT - FAILED TREE CHECK" ); @@ -401,8 +401,8 @@ rtems_task Init( puts( "INIT - Removing 100 nodes" ); - for ( p = rtems_rbtree_get_max(&rbtree1), id = 0 ; p ; - p = rtems_rbtree_get_max(&rbtree1) , id++ ) { + for ( p = rtems_rbtree_get_max_unprotected(&rbtree1), id = 0 ; p ; + p = rtems_rbtree_get_max_unprotected(&rbtree1) , id++ ) { test_node *t = rtems_rbtree_container_of(p,test_node,Node); if ( id > 99 ) { puts( "INIT - TOO MANY NODES ON RBTREE" ); @@ -426,7 +426,7 @@ rtems_task Init( for (i = 0; i < 100; i++) { node_array[i].id = i; node_array[i].key = i; - rtems_rbtree_insert( &rbtree1, &node_array[i].Node ); + rtems_rbtree_insert_unprotected( &rbtree1, &node_array[i].Node ); if (!rb_assert(rbtree1.root) ) puts( "INIT - FAILED TREE CHECK" ); @@ -434,28 +434,28 @@ rtems_task Init( puts( "INIT - Verify rtems_rbtree_find" ); search_node.key = 30; - p = rtems_rbtree_find(&rbtree1, &search_node.Node); + p = rtems_rbtree_find_unprotected(&rbtree1, &search_node.Node); if(rtems_rbtree_container_of(p,test_node,Node)->id != 30) { puts ("INIT - ERROR ON RBTREE ID MISMATCH"); rtems_test_exit(0); } puts( "INIT - Verify rtems_rbtree_predecessor/successor"); - p = rtems_rbtree_predecessor(p); + p = rtems_rbtree_predecessor_unprotected(p); if(p && rtems_rbtree_container_of(p,test_node,Node)->id != 29) { puts ("INIT - ERROR ON RBTREE ID MISMATCH"); rtems_test_exit(0); } - p = rtems_rbtree_find(&rbtree1, &search_node.Node); - p = rtems_rbtree_successor(p); + p = rtems_rbtree_find_unprotected(&rbtree1, &search_node.Node); + p = rtems_rbtree_successor_unprotected(p); if(p && rtems_rbtree_container_of(p,test_node,Node)->id != 31) { puts ("INIT - ERROR ON RBTREE ID MISMATCH"); rtems_test_exit(0); } - p = rtems_rbtree_find(&rbtree1, &search_node.Node); + p = rtems_rbtree_find_unprotected(&rbtree1, &search_node.Node); puts( "INIT - Verify rtems_rbtree_find_header" ); - if (rtems_rbtree_find_header(p) != &rbtree1) { + if (rtems_rbtree_find_header_unprotected(p) != &rbtree1) { puts ("INIT - ERROR ON RBTREE HEADER MISMATCH"); rtems_test_exit(0); } @@ -473,8 +473,8 @@ rtems_task Init( puts( "INIT - Removing 100 nodes" ); - for ( p = rtems_rbtree_get_max(&rbtree1), id = 99 ; p ; - p = rtems_rbtree_get_max(&rbtree1) , id-- ) { + for ( p = rtems_rbtree_get_max_unprotected(&rbtree1), id = 99 ; p ; + p = rtems_rbtree_get_max_unprotected(&rbtree1) , id-- ) { test_node *t = rtems_rbtree_container_of(p,test_node,Node); if ( id < 0 ) { puts( "INIT - TOO MANY NODES ON RBTREE" ); @@ -494,11 +494,11 @@ rtems_task Init( rtems_test_exit(0); } - if (rtems_rbtree_find_header(&node_array[0].Node) != NULL) { + if (rtems_rbtree_find_header_unprotected(&node_array[0].Node) != NULL) { puts ("INIT - ERROR ON RBTREE HEADER MISMATCH"); rtems_test_exit(0); } - if (rtems_rbtree_find_header(NULL) != NULL) { + if (rtems_rbtree_find_header_unprotected(NULL) != NULL) { puts ("INIT - ERROR ON RBTREE HEADER MISMATCH"); rtems_test_exit(0); } @@ -507,7 +507,7 @@ rtems_task Init( for (i = 0; i < 20; i++) { node_array[i].id = numbers[i]; node_array[i].key = numbers[i]; - rtems_rbtree_insert( &rbtree1, &node_array[i].Node ); + rtems_rbtree_insert_unprotected( &rbtree1, &node_array[i].Node ); if (!rb_assert(rbtree1.root) ) puts( "INIT - FAILED TREE CHECK" ); @@ -515,8 +515,8 @@ rtems_task Init( puts( "INIT - Removing 20 nodes" ); - for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ; - p = rtems_rbtree_get_min(&rbtree1) , id++ ) { + for ( p = rtems_rbtree_get_min_unprotected(&rbtree1), id = 0 ; p ; + p = rtems_rbtree_get_min_unprotected(&rbtree1) , id++ ) { test_node *t = rtems_rbtree_container_of(p,test_node,Node); if ( id > 19 ) { puts( "INIT - TOO MANY NODES ON RBTREE" ); @@ -547,8 +547,8 @@ rtems_task Init( puts( "INIT - Removing 100 nodes" ); - for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ; - p = rtems_rbtree_get_min(&rbtree1) , id++ ) { + for ( p = rtems_rbtree_get_min_unprotected(&rbtree1), id = 0 ; p ; + p = rtems_rbtree_get_min_unprotected(&rbtree1) , id++ ) { test_node *t = rtems_rbtree_container_of(p,test_node,Node); if ( id > 99 ) { puts( "INIT - TOO MANY NODES ON RBTREE" ); @@ -582,7 +582,7 @@ rtems_task Init( for (i = 0; i < 100; i++) { node_array[i].id = i; node_array[i].key = i%5; - rtems_rbtree_insert( &rbtree1, &node_array[i].Node ); + rtems_rbtree_insert_unprotected( &rbtree1, &node_array[i].Node ); if (!rb_assert(rbtree1.root) ) puts( "INIT - FAILED TREE CHECK" ); @@ -590,7 +590,7 @@ rtems_task Init( puts( "INIT - Verify rtems_rbtree_find in a duplicate tree" ); search_node.key = 2; - p = rtems_rbtree_find(&rbtree1, &search_node.Node); + p = rtems_rbtree_find_unprotected(&rbtree1, &search_node.Node); if(rtems_rbtree_container_of(p,test_node,Node)->id != 2) { puts ("INIT - ERROR ON RBTREE ID MISMATCH"); rtems_test_exit(0); @@ -598,8 +598,8 @@ rtems_task Init( puts( "INIT - Removing 100 nodes" ); - for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ; - p = rtems_rbtree_get_min(&rbtree1) , id++ ) { + for ( p = rtems_rbtree_get_min_unprotected(&rbtree1), id = 0 ; p ; + p = rtems_rbtree_get_min_unprotected(&rbtree1) , id++ ) { test_node *t = rtems_rbtree_container_of(p,test_node,Node); if ( id > 99 ) { puts( "INIT - TOO MANY NODES ON RBTREE" ); @@ -623,7 +623,7 @@ rtems_task Init( for (i = 0; i < 100; i++) { node_array[i].id = 99-i; node_array[i].key = (99-i)%5; - rtems_rbtree_insert( &rbtree1, &node_array[i].Node ); + rtems_rbtree_insert_unprotected( &rbtree1, &node_array[i].Node ); if (!rb_assert(rbtree1.root) ) puts( "INIT - FAILED TREE CHECK" ); @@ -631,7 +631,7 @@ rtems_task Init( puts( "INIT - Verify rtems_rbtree_find in a duplicate tree" ); search_node.key = 2; - p = rtems_rbtree_find(&rbtree1, &search_node.Node); + p = rtems_rbtree_find_unprotected(&rbtree1, &search_node.Node); if(rtems_rbtree_container_of(p,test_node,Node)->id != 97) { puts ("INIT - ERROR ON RBTREE ID MISMATCH"); rtems_test_exit(0); @@ -639,8 +639,8 @@ rtems_task Init( puts( "INIT - Removing 100 nodes" ); - for ( p = rtems_rbtree_get_min(&rbtree1), id = 0 ; p ; - p = rtems_rbtree_get_min(&rbtree1) , id++ ) { + for ( p = rtems_rbtree_get_min_unprotected(&rbtree1), id = 0 ; p ; + p = rtems_rbtree_get_min_unprotected(&rbtree1) , id++ ) { test_node *t = rtems_rbtree_container_of(p,test_node,Node); if ( id > 99 ) { puts( "INIT - TOO MANY NODES ON RBTREE" ); -- cgit v1.2.3