Changeset 60fe374 in rtems


Ignore:
Timestamp:
08/03/14 11:02:58 (8 years ago)
Author:
Sebastian Huber <sebastian.huber@…>
Branches:
4.11, 5, master
Children:
390cfcd
Parents:
40dcafa
git-author:
Sebastian Huber <sebastian.huber@…> (08/03/14 11:02:58)
git-committer:
Sebastian Huber <sebastian.huber@…> (08/05/14 07:30:37)
Message:

rbtree: Add and use RBTree_Compare_result

Files:
15 edited

Legend:

Unmodified
Added
Removed

  • cpukit/posix/include/rtems/posix/keyimpl.h

    r40dcafa r60fe374  
    6565 * This routine compares the rbtree node
    6666 */
    67 int _POSIX_Keys_Key_value_compare(
     67RBTree_Compare_result _POSIX_Keys_Key_value_compare(
    6868  const RBTree_Node *node1,
    6969  const RBTree_Node *node2

  • cpukit/posix/src/key.c

    r40dcafa r60fe374  
    4545 */
    4646
    47 int _POSIX_Keys_Key_value_compare(
     47RBTree_Compare_result _POSIX_Keys_Key_value_compare(
    4848  const RBTree_Node *node1,
    4949  const RBTree_Node *node2
    … …  
    5353  POSIX_Keys_Key_value_pair *n2;
    5454  Objects_Id thread_id1, thread_id2;
    55   int diff;
     55  RBTree_Compare_result diff;
    5656
    5757  n1 = POSIX_KEYS_RBTREE_NODE_TO_KEY_VALUE_PAIR( node1 );

  • cpukit/sapi/include/rtems/rbheap.h

    r40dcafa r60fe374  
    155155 *
    156156 * @retval RTEMS_SUCCESSFUL Successful operation.
    157  * @retval RTEMS_INVALID_NUMBER The alignment is not positive.
    158157 * @retval RTEMS_INVALID_ADDRESS The memory area is invalid.
    159158 * @retval RTEMS_NO_MEMORY Not enough chunk descriptors.

  • cpukit/sapi/include/rtems/rbtree.h

    r40dcafa r60fe374  
    5656
    5757/**
    58  * This type defines function pointers for user-provided comparison
    59  * function. The function compares two nodes in order to determine
    60  * the order in a red-black tree.
     58 * @copydoc RBTree_Compare_result
     59 */
     60typedef RBTree_Compare_result rtems_rbtree_compare_result;
     61
     62/**
     63 * @copydoc RBTree_Compare
    6164 */
    6265typedef RBTree_Compare rtems_rbtree_compare;

  • cpukit/sapi/src/rbheap.c

    r40dcafa r60fe374  
    4747}
    4848
    49 static int chunk_compare(const rtems_rbtree_node *a, const rtems_rbtree_node *b)
     49static rtems_rbtree_compare_result chunk_compare(
     50  const rtems_rbtree_node *a,
     51  const rtems_rbtree_node *b
     52)
    5053{
    5154  const rtems_rbheap_chunk *left = rtems_rbheap_chunk_of_node(a);
    5255  const rtems_rbheap_chunk *right = rtems_rbheap_chunk_of_node(b);
    5356
    54   return (int) (left->begin - right->begin);
     57  return (rtems_rbtree_compare_result)
     58    ((left->begin >> 1) - (right->begin >> 1));
    5559}
    5660
    … …  
    9498{
    9599  rtems_status_code sc = RTEMS_SUCCESSFUL;
    96 
    97   if (alignment > 0) {
    98     uintptr_t begin = (uintptr_t) area_begin;
    99     uintptr_t end = begin + area_size;
    100     uintptr_t aligned_begin = align_up(alignment, begin);
    101     uintptr_t aligned_end = align_down(alignment, end);
    102 
    103     if (begin < end && begin <= aligned_begin && aligned_begin < aligned_end) {
    104       rtems_chain_control *free_chain = &control->free_chunk_chain;
    105       rtems_rbtree_control *chunk_tree = &control->chunk_tree;
    106       rtems_rbheap_chunk *first = NULL;
    107 
    108       rtems_chain_initialize_empty(free_chain);
    109       rtems_chain_initialize_empty(&control->spare_descriptor_chain);
    110       rtems_rbtree_initialize_empty(chunk_tree);
    111       control->alignment = alignment;
    112       control->handler_arg = handler_arg;
    113       control->extend_descriptors = extend_descriptors;
    114 
    115       first = get_chunk(control);
    116       if (first != NULL) {
    117         first->begin = aligned_begin;
    118         first->size = aligned_end - aligned_begin;
    119         add_to_chain(free_chain, first);
    120         insert_into_tree(chunk_tree, first);
    121       } else {
    122         sc = RTEMS_NO_MEMORY;
    123       }
     100  uintptr_t begin = (uintptr_t) area_begin;
     101  uintptr_t end = begin + area_size;
     102  uintptr_t aligned_begin;
     103  uintptr_t aligned_end;
     104
     105  /*
     106   * Ensure that the alignment is at least two, so that we can keep
     107   * chunk_compare() that simple.
     108   */
     109  alignment = alignment < 2 ? 2 : alignment;
     110
     111  aligned_begin = align_up(alignment, begin);
     112  aligned_end = align_down(alignment, end);
     113
     114  if (begin < end && begin <= aligned_begin && aligned_begin < aligned_end) {
     115    rtems_chain_control *free_chain = &control->free_chunk_chain;
     116    rtems_rbtree_control *chunk_tree = &control->chunk_tree;
     117    rtems_rbheap_chunk *first = NULL;
     118
     119    rtems_chain_initialize_empty(free_chain);
     120    rtems_chain_initialize_empty(&control->spare_descriptor_chain);
     121    rtems_rbtree_initialize_empty(chunk_tree);
     122    control->alignment = alignment;
     123    control->handler_arg = handler_arg;
     124    control->extend_descriptors = extend_descriptors;
     125
     126    first = get_chunk(control);
     127    if (first != NULL) {
     128      first->begin = aligned_begin;
     129      first->size = aligned_end - aligned_begin;
     130      add_to_chain(free_chain, first);
     131      insert_into_tree(chunk_tree, first);
    124132    } else {
    125       sc = RTEMS_INVALID_ADDRESS;
     133      sc = RTEMS_NO_MEMORY;
    126134    }
    127135  } else {
    128     sc = RTEMS_INVALID_NUMBER;
     136    sc = RTEMS_INVALID_ADDRESS;
    129137  }
    130138

  • cpukit/score/include/rtems/score/rbtree.h

    r40dcafa r60fe374  
    9191
    9292/**
     93 * @brief Integer type for compare results.
     94 *
     95 * The type is large enough to represent pointers and 32-bit signed integers.
     96 *
     97 * @see RBTree_Compare.
     98 */
     99typedef long RBTree_Compare_result;
     100
     101/**
    93102 * @brief Compares two red-black tree nodes.
    94103 *
    … …  
    103112 *   second node.
    104113 */
    105 typedef int ( *RBTree_Compare )(
     114typedef RBTree_Compare_result ( *RBTree_Compare )(
    106115  const RBTree_Node *first,
    107116  const RBTree_Node *second

  • cpukit/score/include/rtems/score/rbtreeimpl.h

    r40dcafa r60fe374  
    145145}
    146146
    147 RTEMS_INLINE_ROUTINE bool _RBTree_Is_equal( int compare_result )
     147RTEMS_INLINE_ROUTINE bool _RBTree_Is_equal(
     148  RBTree_Compare_result compare_result
     149)
    148150{
    149151  return compare_result == 0;
    … …  
    151153
    152154RTEMS_INLINE_ROUTINE bool _RBTree_Is_greater(
    153   int compare_result
     155  RBTree_Compare_result compare_result
    154156)
    155157{
    … …  
    158160
    159161RTEMS_INLINE_ROUTINE bool _RBTree_Is_lesser(
    160   int compare_result
     162  RBTree_Compare_result compare_result
    161163)
    162164{

  • cpukit/score/include/rtems/score/scheduleredfimpl.h

    r40dcafa r60fe374  
    4545}
    4646
    47 int _Scheduler_EDF_Compare(
     47RBTree_Compare_result _Scheduler_EDF_Compare(
    4848  const RBTree_Node* n1,
    4949  const RBTree_Node* n2

  • cpukit/score/include/rtems/score/threadqimpl.h

    r40dcafa r60fe374  
    261261 * @retval 1 The @left node is less important than @right node.
    262262 */
    263 int _Thread_queue_Compare_priority(
     263RBTree_Compare_result _Thread_queue_Compare_priority(
    264264  const RBTree_Node *left,
    265265  const RBTree_Node *right

  • cpukit/score/src/rbtreefind.c

    r40dcafa r60fe374  
    3131
    3232  while ( iter_node != NULL ) {
    33     int              compare_result = ( *compare )( the_node, iter_node );
    34     RBTree_Direction dir;
     33    RBTree_Compare_result compare_result = ( *compare )( the_node, iter_node );
     34    RBTree_Direction      dir;
    3535
    3636    if ( _RBTree_Is_equal( compare_result ) ) {

  • cpukit/score/src/rbtreeinsert.c

    r40dcafa r60fe374  
    1212
    1313#include <rtems/score/rbtreeimpl.h>
     14
     15RTEMS_STATIC_ASSERT(
     16  sizeof( RBTree_Compare_result ) >= sizeof( intptr_t ),
     17  RBTree_Compare_result_intptr_t
     18);
     19
     20RTEMS_STATIC_ASSERT(
     21  sizeof( RBTree_Compare_result ) >= sizeof( int32_t ),
     22  RBTree_Compare_result_int32_t
     23);
    1424
    1525/** @brief Validate and fix-up tree properties for a new insert/colored node
    … …  
    7888    /* typical binary search tree insert, descend tree to leaf and insert */
    7989    while ( iter_node ) {
    80       int compare_result = ( *compare )( the_node, iter_node );
     90      RBTree_Compare_result compare_result =
     91        ( *compare )( the_node, iter_node );
    8192
    8293      if ( is_unique && _RBTree_Is_equal( compare_result ) )

  • cpukit/score/src/scheduleredf.c

    r40dcafa r60fe374  
    2121#include <rtems/score/scheduleredfimpl.h>
    2222
    23 int _Scheduler_EDF_Compare(
     23RBTree_Compare_result _Scheduler_EDF_Compare(
    2424  const RBTree_Node* n1,
    2525  const RBTree_Node* n2

  • cpukit/score/src/threadq.c

    r40dcafa r60fe374  
    2525#include <rtems/score/threadimpl.h>
    2626
    27 int _Thread_queue_Compare_priority(
     27RBTree_Compare_result _Thread_queue_Compare_priority(
    2828  const RBTree_Node *left,
    2929  const RBTree_Node *right

  • testsuites/libtests/rbheap01/init.c

    r40dcafa r60fe374  
    9595}
    9696
    97 static void test_init_chunk_alignment(void)
    98 {
    99   rtems_status_code sc = RTEMS_SUCCESSFUL;
    100   rtems_rbheap_control control;
    101 
    102   sc = rtems_rbheap_initialize(
    103     &control,
    104     area,
    105     sizeof(area),
    106     0,
    107     extend_descriptors,
    108     NULL
    109   );
    110   rtems_test_assert(sc == RTEMS_INVALID_NUMBER);
    111 }
    112 
    11397static void test_init_begin_greater_than_end(void)
    11498{
    … …  
    598582  TEST_BEGIN();
    599583
    600   test_init_chunk_alignment();
    601584  test_init_begin_greater_than_end();
    602585  test_init_begin_greater_than_aligned_begin();

  • testsuites/sptests/sprbtree01/init.c

    r40dcafa r60fe374  
    3434} test_node;
    3535
    36 static int test_compare_function (
     36static rtems_rbtree_compare_result test_compare_function (
    3737  const rtems_rbtree_node *n1,
    3838  const rtems_rbtree_node *n2
Note: See TracChangeset for help on using the changeset viewer.