Changeset 2445bda in rtems for cpukit/sapi
- Timestamp:
- 07/23/13 07:50:22 (11 years ago)
- Branches:
- 4.11, 5, master
- Children:
- ac252bdc
- Parents:
- 98c7eaca
- git-author:
- Sebastian Huber <sebastian.huber@…> (07/23/13 07:50:22)
- git-committer:
- Sebastian Huber <sebastian.huber@…> (07/23/13 13:12:51)
- Location:
- cpukit/sapi
- Files:
-
- 1 deleted
- 3 edited
Legend:
- Unmodified
- Added
- Removed
-
cpukit/sapi/Makefile.am
r98c7eaca r2445bda 21 21 22 22 include_rtems_HEADERS += inline/rtems/extension.inl 23 include_rtems_HEADERS += inline/rtems/rbtree.inl24 23 25 24 ## src -
cpukit/sapi/include/rtems/rbtree.h
r98c7eaca r2445bda 21 21 #define _RTEMS_RBTREE_H 22 22 23 #include <rtems/score/rbtree.h> 24 23 25 #ifdef __cplusplus 24 26 extern "C" { 25 27 #endif 26 27 #include <rtems/system.h>28 #include <rtems/score/rbtree.h>29 28 30 29 /** … … 73 72 _RBTree_Container_of(node,object_type,object_member) 74 73 75 #include <rtems/rbtree.inl> 74 /** 75 * @brief Initialize a RBTree header. 76 * 77 * This routine initializes @a the_rbtree structure to manage the 78 * contiguous array of @a number_nodes nodes which starts at 79 * @a starting_address. Each node is of @a node_size bytes. 80 */ 81 RTEMS_INLINE_ROUTINE void rtems_rbtree_initialize( 82 rtems_rbtree_control *the_rbtree, 83 rtems_rbtree_compare_function compare_function, 84 void *starting_address, 85 size_t number_nodes, 86 size_t node_size, 87 bool is_unique 88 ) 89 { 90 _RBTree_Initialize( the_rbtree, compare_function, starting_address, 91 number_nodes, node_size, is_unique); 92 } 93 94 /** 95 * @brief Initialize this RBTree as Empty 96 * 97 * This routine initializes @a the_rbtree to contain zero nodes. 98 */ 99 RTEMS_INLINE_ROUTINE void rtems_rbtree_initialize_empty( 100 rtems_rbtree_control *the_rbtree, 101 rtems_rbtree_compare_function compare_function, 102 bool is_unique 103 ) 104 { 105 _RBTree_Initialize_empty( the_rbtree, compare_function, is_unique ); 106 } 107 108 /** 109 * @brief Set off RBtree. 110 * 111 * This function sets the next and previous fields of the @a node to NULL 112 * indicating the @a node is not part of any rbtree. 113 */ 114 RTEMS_INLINE_ROUTINE void rtems_rbtree_set_off_rbtree( 115 rtems_rbtree_node *node 116 ) 117 { 118 _RBTree_Set_off_rbtree( node ); 119 } 120 121 /** 122 * @brief Is the Node off RBTree. 123 * 124 * This function returns true if the @a node is not on a rbtree. A @a node is 125 * off rbtree if the next and previous fields are set to NULL. 126 */ 127 RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_node_off_rbtree( 128 const rtems_rbtree_node *node 129 ) 130 { 131 return _RBTree_Is_node_off_rbtree( node ); 132 } 133 134 /** 135 * @brief Is the RBTree Node Pointer NULL. 136 * 137 * This function returns true if @a the_node is NULL and false otherwise. 138 */ 139 RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_null_node( 140 const rtems_rbtree_node *the_node 141 ) 142 { 143 return _RBTree_Is_null_node( the_node ); 144 } 145 146 /** 147 * @brief Return pointer to RBTree root. 148 * 149 * This function returns a pointer to the root node of @a the_rbtree. 150 */ 151 RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_root( 152 const rtems_rbtree_control *the_rbtree 153 ) 154 { 155 return _RBTree_Root( the_rbtree ); 156 } 157 158 /** 159 * @brief Return pointer to RBTree Minimum 160 * 161 * This function returns a pointer to the minimum node of @a the_rbtree. 162 */ 163 RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_min( 164 const rtems_rbtree_control *the_rbtree 165 ) 166 { 167 return _RBTree_First( the_rbtree, RBT_LEFT ); 168 } 169 170 /** 171 * @brief Return pointer to RBTree maximum. 172 * 173 * This function returns a pointer to the maximum node of @a the_rbtree. 174 */ 175 RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_max( 176 const rtems_rbtree_control *the_rbtree 177 ) 178 { 179 return _RBTree_First( the_rbtree, RBT_RIGHT ); 180 } 181 182 /** 183 * @brief Return pointer to the left child node from this node. 184 * 185 * This function returns a pointer to the left child node of @a the_node. 186 */ 187 RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_left( 188 const rtems_rbtree_node *the_node 189 ) 190 { 191 return _RBTree_Left( the_node ); 192 } 193 194 /** 195 * @brief Return pointer to the right child node from this node. 196 * 197 * This function returns a pointer to the right child node of @a the_node. 198 */ 199 RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_right( 200 const rtems_rbtree_node *the_node 201 ) 202 { 203 return _RBTree_Right( the_node ); 204 } 205 206 /** 207 * @brief Return pointer to the parent child node from this node. 208 * 209 * This function returns a pointer to the parent node of @a the_node. 210 */ 211 RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_parent( 212 const rtems_rbtree_node *the_node 213 ) 214 { 215 return _RBTree_Parent( the_node ); 216 } 217 218 /** 219 * @brief Are two nodes equal. 220 * 221 * This function returns true if @a left and @a right are equal, 222 * and false otherwise. 223 */ 224 RTEMS_INLINE_ROUTINE bool rtems_rbtree_are_nodes_equal( 225 const rtems_rbtree_node *left, 226 const rtems_rbtree_node *right 227 ) 228 { 229 return _RBTree_Are_nodes_equal( left, right ); 230 } 231 232 /** 233 * @brief Is the RBTree empty. 234 * 235 * This function returns true if there a no nodes on @a the_rbtree and 236 * false otherwise. 237 */ 238 RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_empty( 239 const rtems_rbtree_control *the_rbtree 240 ) 241 { 242 return _RBTree_Is_empty( the_rbtree ); 243 } 244 245 /** 246 * @brief Is this the minimum node on the RBTree. 247 * 248 * This function returns true if @a the_node is the min node on @a the_rbtree 249 * and false otherwise. 250 */ 251 RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_min( 252 const rtems_rbtree_control *the_rbtree, 253 const rtems_rbtree_node *the_node 254 ) 255 { 256 return _RBTree_Is_first( the_rbtree, the_node, RBT_LEFT ); 257 } 258 259 /** 260 * @brief Is this the maximum node on the RBTree. 261 * 262 * This function returns true if @a the_node is the max node on @a the_rbtree 263 * and false otherwise. 264 */ 265 RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_max( 266 const rtems_rbtree_control *the_rbtree, 267 const rtems_rbtree_node *the_node 268 ) 269 { 270 return _RBTree_Is_first( the_rbtree, the_node, RBT_RIGHT ); 271 } 272 273 274 /** 275 * @brief Does this RBTree have only one node. 276 * 277 * This function returns true if there is only one node on @a the_rbtree and 278 * false otherwise. 279 */ 280 RTEMS_INLINE_ROUTINE bool rtems_rbtree_has_only_one_node( 281 const rtems_rbtree_control *the_rbtree 282 ) 283 { 284 return _RBTree_Has_only_one_node( the_rbtree ); 285 } 286 287 /** 288 * @brief Is this node the RBTree root. 289 * 290 * This function returns true if @a the_node is the root of @a the_rbtree and 291 * false otherwise. 292 */ 293 RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_root( 294 const rtems_rbtree_control *the_rbtree, 295 const rtems_rbtree_node *the_node 296 ) 297 { 298 return _RBTree_Is_root( the_rbtree, the_node ); 299 } 300 301 /** 302 * @copydoc _RBTree_Find_unprotected() 303 */ 304 RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_find_unprotected( 305 const rtems_rbtree_control *the_rbtree, 306 const rtems_rbtree_node *the_node 307 ) 308 { 309 return _RBTree_Find_unprotected( the_rbtree, the_node ); 310 } 311 312 /** @brief Find the node with given key in the tree. 313 * 314 * This function returns a pointer to the node having key equal to the key 315 * of @a the_node if it exists within @a the_rbtree, and NULL if not. 316 * @a the_node has to be made up before a search. 317 * 318 * @note If the tree is not unique and contains duplicate keys, the set 319 * of duplicate keys acts as FIFO. 320 */ 321 RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_find( 322 const rtems_rbtree_control *the_rbtree, 323 const rtems_rbtree_node *the_node 324 ) 325 { 326 return _RBTree_Find( the_rbtree, the_node ); 327 } 328 329 /** 330 * @copydoc _RBTree_Predecessor_unprotected() 331 */ 332 RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_predecessor_unprotected( 333 const rtems_rbtree_node *node 334 ) 335 { 336 return _RBTree_Predecessor_unprotected( node ); 337 } 338 339 /** 340 * @copydoc _RBTree_Predecessor() 341 */ 342 RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_predecessor( 343 const rtems_rbtree_node *node 344 ) 345 { 346 return _RBTree_Predecessor( node ); 347 } 348 349 /** 350 * @copydoc _RBTree_Successor_unprotected() 351 */ 352 RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_successor_unprotected( 353 const rtems_rbtree_node *node 354 ) 355 { 356 return _RBTree_Successor_unprotected( node ); 357 } 358 359 /** 360 * @copydoc _RBTree_Successor() 361 */ 362 RTEMS_INLINE_ROUTINE rtems_rbtree_node* rtems_rbtree_successor( 363 const rtems_rbtree_node *node 364 ) 365 { 366 return _RBTree_Successor( node ); 367 } 368 369 /** 370 * @copydoc _RBTree_Extract_unprotected() 371 */ 372 RTEMS_INLINE_ROUTINE void rtems_rbtree_extract_unprotected( 373 rtems_rbtree_control *the_rbtree, 374 rtems_rbtree_node *the_node 375 ) 376 { 377 _RBTree_Extract_unprotected( the_rbtree, the_node ); 378 } 379 380 /** 381 * @brief Extract the specified node from a rbtree. 382 * 383 * This routine extracts @a the_node from @a the_rbtree on which it resides. 384 * It disables interrupts to ensure the atomicity of the extract operation. 385 */ 386 RTEMS_INLINE_ROUTINE void rtems_rbtree_extract( 387 rtems_rbtree_control *the_rbtree, 388 rtems_rbtree_node *the_node 389 ) 390 { 391 _RBTree_Extract( the_rbtree, the_node ); 392 } 393 394 /** 395 * @brief Obtain the min node on a rbtree. 396 * 397 * This function removes the min node from @a the_rbtree and returns 398 * a pointer to that node. If @a the_rbtree is empty, then NULL is returned. 399 */ 400 401 RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_get_min_unprotected( 402 rtems_rbtree_control *the_rbtree 403 ) 404 { 405 return _RBTree_Get_unprotected( the_rbtree, RBT_LEFT ); 406 } 407 408 /** 409 * @brief Obtain the min node on a rbtree. 410 * 411 * This function removes the min node from @a the_rbtree and returns 412 * a pointer to that node. If @a the_rbtree is empty, then NULL is returned. 413 * It disables interrupts to ensure the atomicity of the get operation. 414 */ 415 RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_get_min( 416 rtems_rbtree_control *the_rbtree 417 ) 418 { 419 return _RBTree_Get( the_rbtree, RBT_LEFT ); 420 } 421 422 /** 423 * @brief Obtain the max node on a rbtree. 424 * 425 * This function removes the max node from @a the_rbtree and returns 426 * a pointer to that node. If @a the_rbtree is empty, then NULL is returned. 427 */ 428 429 RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_get_max_unprotected( 430 rtems_rbtree_control *the_rbtree 431 ) 432 { 433 return _RBTree_Get_unprotected( the_rbtree, RBT_RIGHT ); 434 } 435 436 /** 437 * @brief Obtain the max node on a rbtree. 438 * 439 * This function removes the max node from @a the_rbtree and returns 440 * a pointer to that node. If @a the_rbtree is empty, then NULL is returned. 441 * It disables interrupts to ensure the atomicity of the get operation. 442 */ 443 RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_get_max( 444 rtems_rbtree_control *the_rbtree 445 ) 446 { 447 return _RBTree_Get( the_rbtree, RBT_RIGHT ); 448 } 449 450 /** 451 * @brief Peek at the min node on a rbtree. 452 * 453 * This function returns a pointer to the min node from @a the_rbtree 454 * without changing the tree. If @a the_rbtree is empty, 455 * then NULL is returned. 456 */ 457 RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_peek_min( 458 const rtems_rbtree_control *the_rbtree 459 ) 460 { 461 return _RBTree_First( the_rbtree, RBT_LEFT ); 462 } 463 464 /** 465 * @brief Peek at the max node on a rbtree. 466 * 467 * This function returns a pointer to the max node from @a the_rbtree 468 * without changing the tree. If @a the_rbtree is empty, 469 * then NULL is returned. 470 */ 471 RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_peek_max( 472 const rtems_rbtree_control *the_rbtree 473 ) 474 { 475 return _RBTree_First( the_rbtree, RBT_RIGHT ); 476 } 477 478 /** 479 * @copydoc _RBTree_Find_header_unprotected() 480 */ 481 RTEMS_INLINE_ROUTINE rtems_rbtree_control *rtems_rbtree_find_header_unprotected( 482 rtems_rbtree_node *the_node 483 ) 484 { 485 return _RBTree_Find_header_unprotected( the_node ); 486 } 487 488 /** 489 * @brief Find the control header of the tree containing a given node. 490 * 491 * This routine finds the rtems_rbtree_control structure of the tree 492 * containing @a the_node. 493 * It disables interrupts to ensure the atomicity of the find operation. 494 */ 495 RTEMS_INLINE_ROUTINE rtems_rbtree_control *rtems_rbtree_find_header( 496 rtems_rbtree_node *the_node 497 ) 498 { 499 return _RBTree_Find_header( the_node ); 500 } 501 502 /** 503 * @copydoc _RBTree_Insert_unprotected() 504 */ 505 RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_insert_unprotected( 506 rtems_rbtree_control *the_rbtree, 507 rtems_rbtree_node *the_node 508 ) 509 { 510 return _RBTree_Insert_unprotected( the_rbtree, the_node ); 511 } 512 513 /** 514 * @brief Insert a node on a rbtree. 515 * 516 * This routine inserts @a the_node on @a the_rbtree. 517 * It disables interrupts to ensure the atomicity of the insert operation. 518 * 519 * @retval 0 Successfully inserted. 520 * @retval -1 NULL @a the_node. 521 * @retval RBTree_Node* if one with equal key to the key of @a the_node exists 522 * in an unique @a the_rbtree. 523 */ 524 RTEMS_INLINE_ROUTINE rtems_rbtree_node *rtems_rbtree_insert( 525 rtems_rbtree_control *the_rbtree, 526 rtems_rbtree_node *the_node 527 ) 528 { 529 return _RBTree_Insert( the_rbtree, the_node ); 530 } 531 532 /** 533 * @brief Determines whether the tree is unique. 534 */ 535 RTEMS_INLINE_ROUTINE bool rtems_rbtree_is_unique( 536 const rtems_rbtree_control *the_rbtree 537 ) 538 { 539 return _RBTree_Is_unique(the_rbtree); 540 } 76 541 77 542 #ifdef __cplusplus -
cpukit/sapi/preinstall.am
r98c7eaca r2445bda 85 85 PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/extension.inl 86 86 87 $(PROJECT_INCLUDE)/rtems/rbtree.inl: inline/rtems/rbtree.inl $(PROJECT_INCLUDE)/rtems/$(dirstamp)88 $(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/rbtree.inl89 PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/rbtree.inl90 91 87 $(PROJECT_LIB)/libsapi.a: libsapi.a $(PROJECT_LIB)/$(dirstamp) 92 88 $(INSTALL_DATA) $< $(PROJECT_LIB)/libsapi.a
Note: See TracChangeset
for help on using the changeset viewer.