pd.if.org Git - liblfds/blob - liblfds/liblfds7.1.0/liblfds710/src/lfds710_list_addonly_singlylinked_unordered/lfds710_list_addonly_singlylinked_unordered_insert.c

   1 /***** includes *****/
   2 #include "lfds710_list_addonly_singlylinked_unordered_internal.h"
   3
   4
   5
   6
   7
   8 /****************************************************************************/
   9 void lfds710_list_asu_insert_at_position( struct lfds710_list_asu_state *lasus,
  10                                           struct lfds710_list_asu_element *lasue,
  11                                           struct lfds710_list_asu_element *lasue_predecessor,
  12                                           enum lfds710_list_asu_position position )
  13 {
  14   LFDS710_PAL_ASSERT( lasus != NULL );
  15   LFDS710_PAL_ASSERT( lasue != NULL );
  16   LFDS710_PAL_ASSERT( (lfds710_pal_uint_t) &lasue->next % LFDS710_PAL_ALIGN_SINGLE_POINTER == 0 );
  17   LFDS710_PAL_ASSERT( (lfds710_pal_uint_t) &lasue->value % LFDS710_PAL_ALIGN_SINGLE_POINTER == 0 );
  18   // TRD : lasue_predecessor asserted in the switch
  19   // TRD : position can be any value in its range
  20
  21   switch( position )
  22   {
  23     case LFDS710_LIST_ASU_POSITION_START:
  24       lfds710_list_asu_insert_at_start( lasus, lasue );
  25     break;
  26
  27     case LFDS710_LIST_ASU_POSITION_END:
  28       lfds710_list_asu_insert_at_end( lasus, lasue );
  29     break;
  30
  31     case LFDS710_LIST_ASU_POSITION_AFTER:
  32       lfds710_list_asu_insert_after_element( lasus, lasue, lasue_predecessor );
  33     break;
  34   }
  35
  36   return;
  37 }
  38
  39
  40
  41
  42
  43 /****************************************************************************/
  44 void lfds710_list_asu_insert_at_start( struct lfds710_list_asu_state *lasus,
  45                                        struct lfds710_list_asu_element *lasue )
  46 {
  47   char unsigned
  48     result;
  49
  50   lfds710_pal_uint_t
  51     backoff_iteration = LFDS710_BACKOFF_INITIAL_VALUE;
  52
  53   LFDS710_PAL_ASSERT( lasus != NULL );
  54   LFDS710_PAL_ASSERT( lasue != NULL );
  55   LFDS710_PAL_ASSERT( (lfds710_pal_uint_t) &lasue->next % LFDS710_PAL_ALIGN_SINGLE_POINTER == 0 );
  56   LFDS710_PAL_ASSERT( (lfds710_pal_uint_t) &lasue->value % LFDS710_PAL_ALIGN_SINGLE_POINTER == 0 );
  57
  58   LFDS710_MISC_BARRIER_LOAD;
  59
  60   lasue->next = lasus->start->next;
  61
  62   do
  63   {
  64     LFDS710_MISC_BARRIER_STORE;
  65     LFDS710_PAL_ATOMIC_CAS( &lasus->start->next, (struct lfds710_list_asu_element **) &lasue->next, lasue, LFDS710_MISC_CAS_STRENGTH_WEAK, result );
  66     if( result == 0 )
  67       LFDS710_BACKOFF_EXPONENTIAL_BACKOFF( lasus->start_backoff, backoff_iteration );
  68   }
  69   while( result == 0 );
  70
  71   LFDS710_BACKOFF_AUTOTUNE( lasus->start_backoff, backoff_iteration );
  72
  73   return;
  74 }
  75
  76
  77
  78
  79
  80 /****************************************************************************/
  81 void lfds710_list_asu_insert_at_end( struct lfds710_list_asu_state *lasus,
  82                                      struct lfds710_list_asu_element *lasue )
  83 {
  84   char unsigned
  85     result;
  86
  87   enum lfds710_misc_flag
  88     finished_flag = LFDS710_MISC_FLAG_LOWERED;
  89
  90   lfds710_pal_uint_t
  91     backoff_iteration = LFDS710_BACKOFF_INITIAL_VALUE;
  92
  93   struct lfds710_list_asu_element LFDS710_PAL_ALIGN(LFDS710_PAL_ALIGN_SINGLE_POINTER)
  94     *compare;
  95
  96   struct lfds710_list_asu_element
  97     *volatile lasue_next,
  98     *volatile lasue_end;
  99
 100   LFDS710_PAL_ASSERT( lasus != NULL );
 101   LFDS710_PAL_ASSERT( lasue != NULL );
 102   LFDS710_PAL_ASSERT( (lfds710_pal_uint_t) &lasue->next % LFDS710_PAL_ALIGN_SINGLE_POINTER == 0 );
 103   LFDS710_PAL_ASSERT( (lfds710_pal_uint_t) &lasue->value % LFDS710_PAL_ALIGN_SINGLE_POINTER == 0 );
 104
 105   /* TRD : begin by assuming end is correctly pointing to the final element
 106            try to link (comparing for next being NULL)
 107            if we fail, move down list till we find last element
 108            and retry
 109            when successful, update end to ourselves
 110
 111            note there's a leading dummy element
 112            so lasus->end always points to an element
 113   */
 114
 115   LFDS710_MISC_BARRIER_LOAD;
 116
 117   lasue->next = NULL;
 118   lasue_end = lasus->end;
 119
 120   while( finished_flag == LFDS710_MISC_FLAG_LOWERED )
 121   {
 122     compare = NULL;
 123
 124     LFDS710_MISC_BARRIER_STORE;
 125     LFDS710_PAL_ATOMIC_CAS( &lasue_end->next, &compare, lasue, LFDS710_MISC_CAS_STRENGTH_STRONG, result );
 126
 127     if( result == 1 )
 128       finished_flag = LFDS710_MISC_FLAG_RAISED;
 129     else
 130     {
 131       LFDS710_BACKOFF_EXPONENTIAL_BACKOFF( lasus->end_backoff, backoff_iteration );
 132
 133       lasue_end = compare;
 134       lasue_next = LFDS710_LIST_ASU_GET_NEXT( *lasue_end );
 135
 136       while( lasue_next != NULL )
 137       {
 138         lasue_end = lasue_next;
 139         lasue_next = LFDS710_LIST_ASU_GET_NEXT( *lasue_end );
 140       }
 141     }
 142   }
 143
 144   lasus->end = lasue;
 145
 146   LFDS710_BACKOFF_AUTOTUNE( lasus->end_backoff, backoff_iteration );
 147
 148   return;
 149 }
 150
 151
 152
 153
 154
 155 /****************************************************************************/
 156 #pragma warning( disable : 4100 )
 157
 158 void lfds710_list_asu_insert_after_element( struct lfds710_list_asu_state *lasus,
 159                                             struct lfds710_list_asu_element *lasue,
 160                                             struct lfds710_list_asu_element *lasue_predecessor )
 161 {
 162   char unsigned
 163     result;
 164
 165   lfds710_pal_uint_t
 166     backoff_iteration = LFDS710_BACKOFF_INITIAL_VALUE;
 167
 168   LFDS710_PAL_ASSERT( lasus != NULL );
 169   LFDS710_PAL_ASSERT( lasue != NULL );
 170   LFDS710_PAL_ASSERT( (lfds710_pal_uint_t) &lasue->next % LFDS710_PAL_ALIGN_SINGLE_POINTER == 0 );
 171   LFDS710_PAL_ASSERT( (lfds710_pal_uint_t) &lasue->value % LFDS710_PAL_ALIGN_SINGLE_POINTER == 0 );
 172   LFDS710_PAL_ASSERT( lasue_predecessor != NULL );
 173
 174   LFDS710_MISC_BARRIER_LOAD;
 175
 176   lasue->next = lasue_predecessor->next;
 177
 178   do
 179   {
 180     LFDS710_MISC_BARRIER_STORE;
 181     LFDS710_PAL_ATOMIC_CAS( &lasue_predecessor->next, (struct lfds710_list_asu_element **) &lasue->next, lasue, LFDS710_MISC_CAS_STRENGTH_WEAK, result );
 182     if( result == 0 )
 183       LFDS710_BACKOFF_EXPONENTIAL_BACKOFF( lasus->after_backoff, backoff_iteration );
 184   }
 185   while( result == 0 );
 186
 187   LFDS710_BACKOFF_AUTOTUNE( lasus->after_backoff, backoff_iteration );
 188
 189   return;
 190 }
 191
 192 #pragma warning( default : 4100 )
 193