From 64939bc9efcaf945b493e9c371901de33c3868a3 Mon Sep 17 00:00:00 2001 From: Sebastian Huber Date: Sat, 12 Jul 2014 14:22:22 -0500 Subject: rbtree: Reduce RBTree_Control size Remove compare function and is unique indicator from the control structure. Rename RBTree_Compare_function to RBTree_Compare. Rename rtems_rbtree_compare_function to rtems_rbtree_compare. Provide C++ compatible initializers. Add compare function and is unique indicator to _RBTree_Find(), _RBTree_Insert(), rtems_rbtree_find() and rtems_rbtree_insert(). Remove _RBTree_Is_unique() and rtems_rbtree_is_unique(). Remove compare function and is unique indicator from _RBTree_Initialize_empty() and rtems_rbtree_initialize_empty(). --- cpukit/sapi/include/rtems/rbtree.h | 46 +++++++++++++++----------------------- cpukit/sapi/src/rbheap.c | 8 +++---- 2 files changed, 22 insertions(+), 32 deletions(-) (limited to 'cpukit/sapi') diff --git a/cpukit/sapi/include/rtems/rbtree.h b/cpukit/sapi/include/rtems/rbtree.h index 7e59e036a2..2005b367e7 100644 --- a/cpukit/sapi/include/rtems/rbtree.h +++ b/cpukit/sapi/include/rtems/rbtree.h @@ -55,13 +55,11 @@ 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 RBTree_Compare rtems_rbtree_compare; /** * @brief RBTree initializer for an empty rbtree with designator @a name. @@ -93,15 +91,15 @@ typedef RBTree_Compare_function rtems_rbtree_compare_function; * @a starting_address. Each node is of @a node_size bytes. */ RTEMS_INLINE_ROUTINE void rtems_rbtree_initialize( - rtems_rbtree_control *the_rbtree, - rtems_rbtree_compare_function compare_function, - void *starting_address, - size_t number_nodes, - size_t node_size, - bool is_unique + rtems_rbtree_control *the_rbtree, + rtems_rbtree_compare compare, + void *starting_address, + size_t number_nodes, + size_t node_size, + bool is_unique ) { - _RBTree_Initialize( the_rbtree, compare_function, starting_address, + _RBTree_Initialize( the_rbtree, compare, starting_address, number_nodes, node_size, is_unique); } @@ -111,12 +109,10 @@ 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, - rtems_rbtree_compare_function compare_function, - bool is_unique + rtems_rbtree_control *the_rbtree ) { - _RBTree_Initialize_empty( the_rbtree, compare_function, is_unique ); + _RBTree_Initialize_empty( the_rbtree ); } /** @@ -277,10 +273,12 @@ RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_root( */ RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_find( const rtems_rbtree_control *the_rbtree, - const rtems_rbtree_node *the_node + const rtems_rbtree_node *the_node, + rtems_rbtree_compare compare, + bool is_unique ) { - return _RBTree_Find( the_rbtree, the_node ); + return _RBTree_Find( the_rbtree, the_node, compare, is_unique ); } /** @@ -385,20 +383,12 @@ RTEMS_INLINE_ROUTINE rtems_rbtree_control *rtems_rbtree_find_header( */ 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. - */ -RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_unique( - const rtems_rbtree_control *the_rbtree + rtems_rbtree_node *the_node, + rtems_rbtree_compare compare, + bool is_unique ) { - return _RBTree_Is_unique(the_rbtree); + return _RBTree_Insert( the_rbtree, the_node, compare, is_unique ); } /** @} */ diff --git a/cpukit/sapi/src/rbheap.c b/cpukit/sapi/src/rbheap.c index febd65f131..20338eb1bd 100644 --- a/cpukit/sapi/src/rbheap.c +++ b/cpukit/sapi/src/rbheap.c @@ -80,7 +80,7 @@ static void insert_into_tree( rtems_rbheap_chunk *chunk ) { - _RBTree_Insert(tree, &chunk->tree_node); + rtems_rbtree_insert(tree, &chunk->tree_node, chunk_compare, true); } rtems_status_code rtems_rbheap_initialize( @@ -107,7 +107,7 @@ rtems_status_code rtems_rbheap_initialize( rtems_chain_initialize_empty(free_chain); rtems_chain_initialize_empty(&control->spare_descriptor_chain); - rtems_rbtree_initialize_empty(chunk_tree, chunk_compare, true); + rtems_rbtree_initialize_empty(chunk_tree); control->alignment = alignment; control->handler_arg = handler_arg; control->extend_descriptors = extend_descriptors; @@ -198,7 +198,7 @@ static rtems_rbheap_chunk *find(rtems_rbtree_control *chunk_tree, uintptr_t key) rtems_rbheap_chunk chunk = { .begin = key }; return rtems_rbheap_chunk_of_node( - _RBTree_Find(chunk_tree, &chunk.tree_node) + rtems_rbtree_find(chunk_tree, &chunk.tree_node, chunk_compare, true) ); } @@ -230,7 +230,7 @@ static void check_and_merge( a->size += b->size; rtems_chain_extract_unprotected(&b->chain_node); add_to_chain(free_chain, b); - _RBTree_Extract(chunk_tree, &b->tree_node); + rtems_rbtree_extract(chunk_tree, &b->tree_node); } } -- cgit v1.2.3