[PATCH 2/3] score/rbtree: Delete protected operations
Gedare Bloom
gedare at rtems.org
Tue Nov 19 17:41:42 UTC 2013
OK
On Tue, Nov 19, 2013 at 10:54 AM, Sebastian Huber
<sebastian.huber at embedded-brains.de> wrote:
> 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 bce7013..5cbdab4 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()
> */
> @@ -337,16 +320,6 @@ RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_predecessor_unprotected(
> }
>
> /**
> - * @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()
> */
> RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_successor_unprotected(
> @@ -357,16 +330,6 @@ RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_successor_unprotected(
> }
>
> /**
> - * @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()
> */
> RTEMS_INLINE_ROUTINE void rtems_rbtree_extract_unprotected(
> @@ -378,20 +341,6 @@ RTEMS_INLINE_ROUTINE void rtems_rbtree_extract_unprotected(
> }
>
> /**
> - * @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.
> *
> * This function removes the min node from @a the_rbtree and returns
> @@ -406,20 +355,6 @@ RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_get_min_unprotected(
> }
>
> /**
> - * @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.
> *
> * This function removes the max node from @a the_rbtree and returns
> @@ -434,20 +369,6 @@ RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_get_max_unprotected(
> }
>
> /**
> - * @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.
> *
> * This function returns a pointer to the min node from @a the_rbtree
> @@ -486,20 +407,6 @@ RTEMS_INLINE_ROUTINE rtems_rbtree_control *rtems_rbtree_find_header_unprotected(
> }
>
> /**
> - * @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()
> */
> RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_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 c9d2d47..4570ffd 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 1414bdf..a3744e5 100644
> --- a/cpukit/score/include/rtems/score/rbtree.h
> +++ b/cpukit/score/include/rtems/score/rbtree.h
> @@ -207,31 +207,14 @@ 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,
> @@ -239,43 +222,6 @@ RBTree_Node *_RBTree_Find_unprotected(
> );
>
> /**
> - * @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).
> *
> * This routine inserts @a the_node on the Red-Black Tree @a the_rbtree.
> @@ -284,9 +230,6 @@ 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,
> @@ -294,31 +237,9 @@ RBTree_Node *_RBTree_Insert_unprotected(
> );
>
> /**
> - * @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,
> @@ -326,19 +247,6 @@ void _RBTree_Extract_unprotected(
> );
>
> /**
> - * @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.
> *
> * @param[in] node The node.
> @@ -353,16 +261,6 @@ RBTree_Node *_RBTree_Next_unprotected(
> );
>
> /**
> - * @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.
> *
> * This function sets the parent and child fields of the @a node to NULL
> @@ -618,18 +516,6 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Predecessor_unprotected(
> }
>
> /**
> - * @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.
> *
> * @param[in] node is the node.
> @@ -644,23 +530,10 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Successor_unprotected(
> }
>
> /**
> - * @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 0f38fbc..8dafe3b 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 b485845..9b2663d 100644
> --- a/cpukit/score/src/rbtreefind.c
> +++ b/cpukit/score/src/rbtreefind.c
> @@ -20,21 +20,6 @@
> #include <rtems/score/rbtreeimpl.h>
> #include <rtems/score/isr.h>
>
> -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 2368a11..0000000
> --- 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 <rtems/system.h>
> -#include <rtems/score/address.h>
> -#include <rtems/score/rbtree.h>
> -#include <rtems/score/isr.h>
> -
> -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 a805a40..0000000
> --- 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 <rtems/score/rbtreeimpl.h>
> -#include <rtems/score/isr.h>
> -
> -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 0d8e4a6..a2f6f09 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 7dd305a..f3268d2 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 df2a947..a0dd9b9 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" );
> --
> 1.7.7
>
> _______________________________________________
> rtems-devel mailing list
> rtems-devel at rtems.org
> http://www.rtems.org/mailman/listinfo/rtems-devel
More information about the devel
mailing list