diff options
author | Joel Sherrill <joel.sherrill@OARcorp.com> | 2011-08-21 20:07:11 +0000 |
---|---|---|
committer | Joel Sherrill <joel.sherrill@OARcorp.com> | 2011-08-21 20:07:11 +0000 |
commit | 74f1c73e969fe7a7b1ca53bb6fcb1336f4a179cb (patch) | |
tree | 4f2b74ad7cf7f1c661bdfd0cd89c284964ad2f64 | |
parent | 2011-08-21 Joel Sherrill <joel.sherrilL@OARcorp.com> (diff) | |
download | rtems-74f1c73e969fe7a7b1ca53bb6fcb1336f4a179cb.tar.bz2 |
2011-08-21 Petr Benes <benesp16@fel.cvut.cz>
PR 1886/cpukit
* sapi/include/rtems/rbtree.h, sapi/inline/rtems/rbtree.inl,
score/include/rtems/score/rbtree.h,
score/inline/rtems/score/rbtree.inl, score/src/rbtree.c,
score/src/rbtreeinsert.c: This patch enables inserting duplicate keys
into rbtree. It is possible to turn on this feature when initializing
the tree.
-rw-r--r-- | cpukit/ChangeLog | 10 | ||||
-rw-r--r-- | cpukit/sapi/include/rtems/rbtree.h | 23 | ||||
-rw-r--r-- | cpukit/sapi/inline/rtems/rbtree.inl | 41 | ||||
-rw-r--r-- | cpukit/score/include/rtems/score/rbtree.h | 41 | ||||
-rw-r--r-- | cpukit/score/inline/rtems/score/rbtree.inl | 28 | ||||
-rw-r--r-- | cpukit/score/src/rbtree.c | 13 | ||||
-rw-r--r-- | cpukit/score/src/rbtreeinsert.c | 9 |
7 files changed, 127 insertions, 38 deletions
diff --git a/cpukit/ChangeLog b/cpukit/ChangeLog index 91784af690..d64fb79846 100644 --- a/cpukit/ChangeLog +++ b/cpukit/ChangeLog @@ -1,3 +1,13 @@ +2011-08-21 Petr Benes <benesp16@fel.cvut.cz> + + PR 1886/cpukit + * sapi/include/rtems/rbtree.h, sapi/inline/rtems/rbtree.inl, + score/include/rtems/score/rbtree.h, + score/inline/rtems/score/rbtree.inl, score/src/rbtree.c, + score/src/rbtreeinsert.c: This patch enables inserting duplicate keys + into rbtree. It is possible to turn on this feature when initializing + the tree. + 2011-08-21 Joel Sherrill <joel.sherrilL@OARcorp.com> PR 1890/cpukit diff --git a/cpukit/sapi/include/rtems/rbtree.h b/cpukit/sapi/include/rtems/rbtree.h index 68f4ec697e..9a09b27650 100644 --- a/cpukit/sapi/include/rtems/rbtree.h +++ b/cpukit/sapi/include/rtems/rbtree.h @@ -43,6 +43,29 @@ typedef RBTree_Node rtems_rbtree_node; typedef RBTree_Control rtems_rbtree_control; /** + * @typedef rtems_rbtree_compare_function + * + * This type defines function pointers for user-provided comparison + * function. The function compares two nodes in order to determine + * the order in a red-black tree. + */ +typedef RBTree_Compare_function rtems_rbtree_compare_function; + +/** + * @typedef rtems_rbtree_unique + * + * This enum type defines whether the tree can contain nodes with + * duplicate keys. + */ +typedef enum { + /** The tree is not unique, insertion of duplicate keys is performed + * in a FIFO manner. */ + RTEMS_RBTREE_DUPLICATE = false, + /** The tree is unique, insertion of duplicate key is refused. */ + RTEMS_RBTREE_UNIQUE = true +} rtems_rbtree_unique; + +/** * @brief RBTree initializer for an empty rbtree with designator @a name. */ #define RTEMS_RBTREE_INITIALIZER_EMPTY(name) \ diff --git a/cpukit/sapi/inline/rtems/rbtree.inl b/cpukit/sapi/inline/rtems/rbtree.inl index 52fdcb3f23..16a6e2a0c6 100644 --- a/cpukit/sapi/inline/rtems/rbtree.inl +++ b/cpukit/sapi/inline/rtems/rbtree.inl @@ -35,15 +35,16 @@ * @a starting_address. Each node is of @a node_size bytes. */ RTEMS_INLINE_ROUTINE void rtems_rbtree_initialize( - rtems_rbtree_control *the_rbtree, - void *compare_function, - void *starting_address, - size_t number_nodes, - size_t node_size + rtems_rbtree_control *the_rbtree, + rtems_rbtree_compare_function compare_function, + void *starting_address, + size_t number_nodes, + size_t node_size, + rtems_rbtree_unique is_unique ) { _RBTree_Initialize( the_rbtree, compare_function, starting_address, - number_nodes, node_size); + number_nodes, node_size, is_unique); } /** @@ -52,11 +53,12 @@ RTEMS_INLINE_ROUTINE void rtems_rbtree_initialize( * This routine initializes @a the_rbtree to contain zero nodes. */ RTEMS_INLINE_ROUTINE void rtems_rbtree_initialize_empty( - rtems_rbtree_control *the_rbtree, - void *compare_function + rtems_rbtree_control *the_rbtree, + rtems_rbtree_compare_function compare_function, + rtems_rbtree_unique is_unique ) { - _RBTree_Initialize_empty( the_rbtree, compare_function ); + _RBTree_Initialize_empty( the_rbtree, compare_function, is_unique ); } /** @@ -257,6 +259,9 @@ RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_root( * 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( rtems_rbtree_control *the_rbtree, @@ -382,13 +387,27 @@ RTEMS_INLINE_ROUTINE rtems_rbtree_control *rtems_rbtree_find_header( * * 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 void rtems_rbtree_insert( +RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_insert( rtems_rbtree_control *the_rbtree, rtems_rbtree_node *the_node ) { - _RBTree_Insert( the_rbtree, the_node ); + return _RBTree_Insert( the_rbtree, the_node ); +} + +/** @brief Determines whether the tree is unique + */ +RTEMS_INLINE_ROUTINE rtems_rbtree_unique rtems_rbtree_is_unique( + rtems_rbtree_control *the_rbtree +) +{ + return( _RBTree_Is_unique(the_rbtree) ); } #endif diff --git a/cpukit/score/include/rtems/score/rbtree.h b/cpukit/score/include/rtems/score/rbtree.h index 8a9e11f795..d2cea57208 100644 --- a/cpukit/score/include/rtems/score/rbtree.h +++ b/cpukit/score/include/rtems/score/rbtree.h @@ -100,6 +100,16 @@ typedef enum { } RBTree_Direction; /** + * This type defines function pointers for user-provided comparison + * function. The function compares two nodes in order to determine + * the order in a red-black tree. + */ +typedef int (*RBTree_Compare_function)( + RBTree_Node *node1, + RBTree_Node *node2 +); + +/** * @struct RBTree_Control * * This is used to manage a RBT. A rbtree consists of a tree of zero or more @@ -126,11 +136,13 @@ typedef struct { /** This points to the min and max nodes of this RBT. */ RBTree_Node *first[2]; /** - * Comparison function pointer. Keys to compare has to be found + * Comparison function pointer. Keys to compare have to be found * inside to maintain generality. It has to return 1 if first node * has higher key than second, -1 if lower, 0 if equal. */ - int (*compare_function) (RBTree_Node*, RBTree_Node*); + RBTree_Compare_function compare_function; + /** Determines whether the tree accepts duplicate keys. */ + bool is_unique; } RBTree_Control; /** @@ -142,7 +154,8 @@ typedef struct { .root = NULL, \ .first[0] = NULL, \ .first[1] = NULL, \ - .compare_function = NULL \ + .compare_function = NULL, \ + .is_unique = 0 \ } /** @@ -176,11 +189,12 @@ RBTree_Node name = RBTREE_NODE_INITIALIZER_EMPTY(name) * @a starting_address. Each node is of @a node_size bytes. */ void _RBTree_Initialize( - RBTree_Control *the_rbtree, - void *compare_function, - void *starting_address, - size_t number_nodes, - size_t node_size + RBTree_Control *the_rbtree, + RBTree_Compare_function compare_function, + void *starting_address, + size_t number_nodes, + size_t node_size, + bool is_unique ); /** @@ -247,8 +261,8 @@ RBTree_Control *_RBTree_Find_header( * * @retval 0 Successfully inserted. * @retval -1 NULL @a the_node. - * @retval RBTree_Node* if one with equal value to @a the_node->value exists - * in @a the_rbtree. + * @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. @@ -263,10 +277,15 @@ RBTree_Node *_RBTree_Insert_unprotected( * * 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. */ -void _RBTree_Insert( +RBTree_Node *_RBTree_Insert( RBTree_Control *the_rbtree, RBTree_Node *the_node ); diff --git a/cpukit/score/inline/rtems/score/rbtree.inl b/cpukit/score/inline/rtems/score/rbtree.inl index 08eddfecba..bbc60477c8 100644 --- a/cpukit/score/inline/rtems/score/rbtree.inl +++ b/cpukit/score/inline/rtems/score/rbtree.inl @@ -235,8 +235,9 @@ RTEMS_INLINE_ROUTINE bool _RBTree_Is_root( * This routine initializes @a the_rbtree to contain zero nodes. */ RTEMS_INLINE_ROUTINE void _RBTree_Initialize_empty( - RBTree_Control *the_rbtree, - void *compare_function + RBTree_Control *the_rbtree, + RBTree_Compare_function compare_function, + bool is_unique ) { the_rbtree->permanent_null = NULL; @@ -244,6 +245,7 @@ RTEMS_INLINE_ROUTINE void _RBTree_Initialize_empty( the_rbtree->first[0] = NULL; the_rbtree->first[1] = NULL; the_rbtree->compare_function = compare_function; + the_rbtree->is_unique = is_unique; } /** @brief Return a pointer to node's grandparent @@ -317,6 +319,9 @@ RTEMS_INLINE_ROUTINE RBTree_Control *_RBTree_Find_header_unprotected( * 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, @@ -324,18 +329,21 @@ RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Find_unprotected( ) { 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 (compare_result == 0) { - return(iter_node); + found = iter_node; + if ( the_rbtree->is_unique ) + break; } - RBTree_Direction dir = (compare_result != -1); + RBTree_Direction dir = (compare_result == 1); iter_node = iter_node->child[dir]; } /* while(iter_node) */ - return 0; + return found; } /** @brief Find the nodes in-order predecessor @@ -428,7 +436,6 @@ RTEMS_INLINE_ROUTINE void _RBTree_Rotate( RBTree_Node *c; if (the_node == NULL) return; if (the_node->child[(1-dir)] == NULL) return; - c = the_node->child[(1-dir)]; the_node->child[(1-dir)] = c->child[dir]; @@ -443,6 +450,15 @@ RTEMS_INLINE_ROUTINE void _RBTree_Rotate( c->parent = the_node->parent; the_node->parent = c; } + +/** @brief Determines whether the tree is unique + */ +RTEMS_INLINE_ROUTINE bool _RBTree_Is_unique( + RBTree_Control *the_rbtree +) +{ + return( the_rbtree && the_rbtree->is_unique ); +} /**@}*/ #endif diff --git a/cpukit/score/src/rbtree.c b/cpukit/score/src/rbtree.c index eb3af773cb..e0fc560229 100644 --- a/cpukit/score/src/rbtree.c +++ b/cpukit/score/src/rbtree.c @@ -32,11 +32,12 @@ */ void _RBTree_Initialize( - RBTree_Control *the_rbtree, - void *compare_function, - void *starting_address, - size_t number_nodes, - size_t node_size + RBTree_Control *the_rbtree, + RBTree_Compare_function compare_function, + void *starting_address, + size_t number_nodes, + size_t node_size, + bool is_unique ) { size_t count; @@ -46,7 +47,7 @@ void _RBTree_Initialize( if (!the_rbtree) return; /* could do sanity checks here */ - _RBTree_Initialize_empty(the_rbtree, compare_function); + _RBTree_Initialize_empty(the_rbtree, compare_function, is_unique); count = number_nodes; next = starting_address; diff --git a/cpukit/score/src/rbtreeinsert.c b/cpukit/score/src/rbtreeinsert.c index bb1915de54..1208a3c81a 100644 --- a/cpukit/score/src/rbtreeinsert.c +++ b/cpukit/score/src/rbtreeinsert.c @@ -72,7 +72,7 @@ void _RBTree_Validate_insert_unprotected( * @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 @a the_rbtree. + * in an unique @a the_rbtree. * * @note It does NOT disable interrupts to ensure the atomicity * of the extract operation. @@ -97,7 +97,8 @@ RBTree_Node *_RBTree_Insert_unprotected( /* typical binary search tree insert, descend tree to leaf and insert */ while (iter_node) { compare_result = the_rbtree->compare_function(the_node, iter_node); - if ( !compare_result ) return iter_node; + if ( the_rbtree->is_unique && !compare_result ) + return iter_node; RBTree_Direction dir = (compare_result != -1); if (!iter_node->child[dir]) { the_node->child[RBT_LEFT] = the_node->child[RBT_RIGHT] = NULL; @@ -138,7 +139,7 @@ RBTree_Node *_RBTree_Insert_unprotected( * only case */ -void _RBTree_Insert( +RBTree_Node *_RBTree_Insert( RBTree_Control *tree, RBTree_Node *node ) @@ -146,6 +147,6 @@ void _RBTree_Insert( ISR_Level level; _ISR_Disable( level ); - _RBTree_Insert_unprotected( tree, node ); + return _RBTree_Insert_unprotected( tree, node ); _ISR_Enable( level ); } |