Changeset 74f1c73e in rtems
- Timestamp:
- 08/21/11 20:07:11 (11 years ago)
- Branches:
- 4.11, 5, master
- Children:
- 611909e
- Parents:
- 08ef1631
- Location:
- cpukit
- Files:
-
- 7 edited
Legend:
- Unmodified
- Added
- Removed
-
cpukit/ChangeLog
r08ef1631 r74f1c73e 1 2011-08-21 Petr Benes <benesp16@fel.cvut.cz> 2 3 PR 1886/cpukit 4 * sapi/include/rtems/rbtree.h, sapi/inline/rtems/rbtree.inl, 5 score/include/rtems/score/rbtree.h, 6 score/inline/rtems/score/rbtree.inl, score/src/rbtree.c, 7 score/src/rbtreeinsert.c: This patch enables inserting duplicate keys 8 into rbtree. It is possible to turn on this feature when initializing 9 the tree. 10 1 11 2011-08-21 Joel Sherrill <joel.sherrilL@OARcorp.com> 2 12 -
cpukit/sapi/include/rtems/rbtree.h
r08ef1631 r74f1c73e 44 44 45 45 /** 46 * @typedef rtems_rbtree_compare_function 47 * 48 * This type defines function pointers for user-provided comparison 49 * function. The function compares two nodes in order to determine 50 * the order in a red-black tree. 51 */ 52 typedef RBTree_Compare_function rtems_rbtree_compare_function; 53 54 /** 55 * @typedef rtems_rbtree_unique 56 * 57 * This enum type defines whether the tree can contain nodes with 58 * duplicate keys. 59 */ 60 typedef enum { 61 /** The tree is not unique, insertion of duplicate keys is performed 62 * in a FIFO manner. */ 63 RTEMS_RBTREE_DUPLICATE = false, 64 /** The tree is unique, insertion of duplicate key is refused. */ 65 RTEMS_RBTREE_UNIQUE = true 66 } rtems_rbtree_unique; 67 68 /** 46 69 * @brief RBTree initializer for an empty rbtree with designator @a name. 47 70 */ -
cpukit/sapi/inline/rtems/rbtree.inl
r08ef1631 r74f1c73e 36 36 */ 37 37 RTEMS_INLINE_ROUTINE void rtems_rbtree_initialize( 38 rtems_rbtree_control *the_rbtree, 39 void *compare_function, 40 void *starting_address, 41 size_t number_nodes, 42 size_t node_size 38 rtems_rbtree_control *the_rbtree, 39 rtems_rbtree_compare_function compare_function, 40 void *starting_address, 41 size_t number_nodes, 42 size_t node_size, 43 rtems_rbtree_unique is_unique 43 44 ) 44 45 { 45 46 _RBTree_Initialize( the_rbtree, compare_function, starting_address, 46 number_nodes, node_size );47 number_nodes, node_size, is_unique); 47 48 } 48 49 … … 53 54 */ 54 55 RTEMS_INLINE_ROUTINE void rtems_rbtree_initialize_empty( 55 rtems_rbtree_control *the_rbtree, 56 void *compare_function 57 ) 58 { 59 _RBTree_Initialize_empty( the_rbtree, compare_function ); 56 rtems_rbtree_control *the_rbtree, 57 rtems_rbtree_compare_function compare_function, 58 rtems_rbtree_unique is_unique 59 ) 60 { 61 _RBTree_Initialize_empty( the_rbtree, compare_function, is_unique ); 60 62 } 61 63 … … 258 260 * of @a the_node if it exists within @a the_rbtree, and NULL if not. 259 261 * @a the_node has to be made up before a search. 262 * 263 * @note If the tree is not unique and contains duplicate keys, the set 264 * of duplicate keys acts as FIFO. 260 265 */ 261 266 RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_find( … … 383 388 * This routine inserts @a the_node on @a the_rbtree. 384 389 * It disables interrupts to ensure the atomicity of the insert operation. 385 */ 386 RTEMS_INLINE_ROUTINE void rtems_rbtree_insert( 390 * 391 * @retval 0 Successfully inserted. 392 * @retval -1 NULL @a the_node. 393 * @retval RBTree_Node* if one with equal key to the key of @a the_node exists 394 * in an unique @a the_rbtree. 395 */ 396 RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_insert( 387 397 rtems_rbtree_control *the_rbtree, 388 398 rtems_rbtree_node *the_node 389 399 ) 390 400 { 391 _RBTree_Insert( the_rbtree, the_node ); 401 return _RBTree_Insert( the_rbtree, the_node ); 402 } 403 404 /** @brief Determines whether the tree is unique 405 */ 406 RTEMS_INLINE_ROUTINE rtems_rbtree_unique rtems_rbtree_is_unique( 407 rtems_rbtree_control *the_rbtree 408 ) 409 { 410 return( _RBTree_Is_unique(the_rbtree) ); 392 411 } 393 412 -
cpukit/score/include/rtems/score/rbtree.h
r08ef1631 r74f1c73e 101 101 102 102 /** 103 * This type defines function pointers for user-provided comparison 104 * function. The function compares two nodes in order to determine 105 * the order in a red-black tree. 106 */ 107 typedef int (*RBTree_Compare_function)( 108 RBTree_Node *node1, 109 RBTree_Node *node2 110 ); 111 112 /** 103 113 * @struct RBTree_Control 104 114 * … … 127 137 RBTree_Node *first[2]; 128 138 /** 129 * Comparison function pointer. Keys to compare ha sto be found139 * Comparison function pointer. Keys to compare have to be found 130 140 * inside to maintain generality. It has to return 1 if first node 131 141 * has higher key than second, -1 if lower, 0 if equal. 132 142 */ 133 int (*compare_function) (RBTree_Node*, RBTree_Node*); 143 RBTree_Compare_function compare_function; 144 /** Determines whether the tree accepts duplicate keys. */ 145 bool is_unique; 134 146 } RBTree_Control; 135 147 … … 143 155 .first[0] = NULL, \ 144 156 .first[1] = NULL, \ 145 .compare_function = NULL \ 157 .compare_function = NULL, \ 158 .is_unique = 0 \ 146 159 } 147 160 … … 177 190 */ 178 191 void _RBTree_Initialize( 179 RBTree_Control *the_rbtree, 180 void *compare_function, 181 void *starting_address, 182 size_t number_nodes, 183 size_t node_size 192 RBTree_Control *the_rbtree, 193 RBTree_Compare_function compare_function, 194 void *starting_address, 195 size_t number_nodes, 196 size_t node_size, 197 bool is_unique 184 198 ); 185 199 … … 248 262 * @retval 0 Successfully inserted. 249 263 * @retval -1 NULL @a the_node. 250 * @retval RBTree_Node* if one with equal value to @a the_node ->valueexists251 * in @a the_rbtree.264 * @retval RBTree_Node* if one with equal value to @a the_node 's key exists 265 * in an unique @a the_rbtree. 252 266 * 253 267 * @note It does NOT disable interrupts to ensure the atomicity … … 264 278 * This routine inserts @a the_node on the tree @a the_rbtree. 265 279 * 280 * @retval 0 Successfully inserted. 281 * @retval -1 NULL @a the_node. 282 * @retval RBTree_Node* if one with equal value to @a the_node 's key exists 283 * in an unique @a the_rbtree. 284 * 266 285 * @note It disables interrupts to ensure the atomicity 267 286 * of the extract operation. 268 287 */ 269 void_RBTree_Insert(288 RBTree_Node *_RBTree_Insert( 270 289 RBTree_Control *the_rbtree, 271 290 RBTree_Node *the_node -
cpukit/score/inline/rtems/score/rbtree.inl
r08ef1631 r74f1c73e 236 236 */ 237 237 RTEMS_INLINE_ROUTINE void _RBTree_Initialize_empty( 238 RBTree_Control *the_rbtree, 239 void *compare_function 238 RBTree_Control *the_rbtree, 239 RBTree_Compare_function compare_function, 240 bool is_unique 240 241 ) 241 242 { … … 245 246 the_rbtree->first[1] = NULL; 246 247 the_rbtree->compare_function = compare_function; 248 the_rbtree->is_unique = is_unique; 247 249 } 248 250 … … 318 320 * having key equal to key of @a the_node if it exists, 319 321 * and NULL if not. @a the_node has to be made up before a search. 322 * 323 * @note If the tree is not unique and contains duplicate keys, the set 324 * of duplicate keys acts as FIFO. 320 325 */ 321 326 RTEMS_INLINE_ROUTINE RBTree_Node *_RBTree_Find_unprotected( … … 325 330 { 326 331 RBTree_Node* iter_node = the_rbtree->root; 332 RBTree_Node* found = NULL; 327 333 int compare_result; 328 334 while (iter_node) { 329 335 compare_result = the_rbtree->compare_function(the_node, iter_node); 330 336 if (compare_result == 0) { 331 return(iter_node); 337 found = iter_node; 338 if ( the_rbtree->is_unique ) 339 break; 332 340 } 333 341 334 RBTree_Direction dir = (compare_result != -1);342 RBTree_Direction dir = (compare_result == 1); 335 343 iter_node = iter_node->child[dir]; 336 344 } /* while(iter_node) */ 337 345 338 return 0;346 return found; 339 347 } 340 348 … … 429 437 if (the_node == NULL) return; 430 438 if (the_node->child[(1-dir)] == NULL) return; 431 432 439 433 440 c = the_node->child[(1-dir)]; … … 444 451 the_node->parent = c; 445 452 } 453 454 /** @brief Determines whether the tree is unique 455 */ 456 RTEMS_INLINE_ROUTINE bool _RBTree_Is_unique( 457 RBTree_Control *the_rbtree 458 ) 459 { 460 return( the_rbtree && the_rbtree->is_unique ); 461 } 446 462 /**@}*/ 447 463 -
cpukit/score/src/rbtree.c
r08ef1631 r74f1c73e 33 33 34 34 void _RBTree_Initialize( 35 RBTree_Control *the_rbtree, 36 void *compare_function, 37 void *starting_address, 38 size_t number_nodes, 39 size_t node_size 35 RBTree_Control *the_rbtree, 36 RBTree_Compare_function compare_function, 37 void *starting_address, 38 size_t number_nodes, 39 size_t node_size, 40 bool is_unique 40 41 ) 41 42 { … … 47 48 48 49 /* could do sanity checks here */ 49 _RBTree_Initialize_empty(the_rbtree, compare_function );50 _RBTree_Initialize_empty(the_rbtree, compare_function, is_unique); 50 51 51 52 count = number_nodes; -
cpukit/score/src/rbtreeinsert.c
r08ef1631 r74f1c73e 73 73 * @retval -1 NULL @a the_node. 74 74 * @retval RBTree_Node* if one with equal key to the key of @a the_node exists 75 * in @a the_rbtree.75 * in an unique @a the_rbtree. 76 76 * 77 77 * @note It does NOT disable interrupts to ensure the atomicity … … 98 98 while (iter_node) { 99 99 compare_result = the_rbtree->compare_function(the_node, iter_node); 100 if ( !compare_result ) return iter_node; 100 if ( the_rbtree->is_unique && !compare_result ) 101 return iter_node; 101 102 RBTree_Direction dir = (compare_result != -1); 102 103 if (!iter_node->child[dir]) { … … 139 140 */ 140 141 141 void_RBTree_Insert(142 RBTree_Node *_RBTree_Insert( 142 143 RBTree_Control *tree, 143 144 RBTree_Node *node … … 147 148 148 149 _ISR_Disable( level ); 149 _RBTree_Insert_unprotected( tree, node );150 return _RBTree_Insert_unprotected( tree, node ); 150 151 _ISR_Enable( level ); 151 152 }
Note: See TracChangeset
for help on using the changeset viewer.