pd.if.org Git - liblfds/blob - liblfds/liblfds7.0.0/liblfds700/src/lfds700_list_addonly_singlylinked_unordered/lfds700_list_addonly_singlylinked_unordered_insert.c

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