diff options
Diffstat (limited to 'cpukit')
-rw-r--r-- | cpukit/sapi/include/rtems/rbtree.h | 112 | ||||
-rw-r--r-- | cpukit/score/Makefile.am | 4 | ||||
-rw-r--r-- | cpukit/score/include/rtems/score/rbtree.h | 141 | ||||
-rw-r--r-- | cpukit/score/src/rbtreeextract.c | 27 | ||||
-rw-r--r-- | cpukit/score/src/rbtreefind.c | 15 | ||||
-rw-r--r-- | cpukit/score/src/rbtreefindheader.c | 38 | ||||
-rw-r--r-- | cpukit/score/src/rbtreeget.c | 37 | ||||
-rw-r--r-- | cpukit/score/src/rbtreeinsert.c | 31 | ||||
-rw-r--r-- | cpukit/score/src/rbtreenext.c | 15 |
9 files changed, 9 insertions, 411 deletions
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() */ @@ -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 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,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 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 <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 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 <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 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 <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 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; -} |