pd.if.org Git - liblfds/blob - liblfds/liblfds7.1.0/liblfds710/src/lfds710_list_addonly_singlylinked_ordered/lfds710_list_addonly_singlylinked_ordered_insert.c

   1 /***** includes *****/
   2 #include "lfds710_list_addonly_singlylinked_ordered_internal.h"
   3
   4
   5
   6
   7
   8 /****************************************************************************/
   9 enum lfds710_list_aso_insert_result lfds710_list_aso_insert( struct lfds710_list_aso_state *lasos,
  10                                                              struct lfds710_list_aso_element *lasoe,
  11                                                              struct lfds710_list_aso_element **existing_lasoe )
  12 {
  13   char unsigned
  14     result;
  15
  16   enum lfds710_misc_flag
  17     finished_flag = LFDS710_MISC_FLAG_LOWERED;
  18
  19   int
  20     compare_result = 0;
  21
  22   lfds710_pal_uint_t
  23     backoff_iteration = LFDS710_BACKOFF_INITIAL_VALUE;
  24
  25   struct lfds710_list_aso_element
  26     *volatile lasoe_temp = NULL,
  27     *volatile lasoe_trailing;
  28
  29   LFDS710_PAL_ASSERT( lasos != NULL );
  30   LFDS710_PAL_ASSERT( lasoe != NULL );
  31   LFDS710_PAL_ASSERT( (lfds710_pal_uint_t) &lasoe->next % LFDS710_PAL_ALIGN_SINGLE_POINTER == 0 );
  32   LFDS710_PAL_ASSERT( (lfds710_pal_uint_t) &lasoe->value % LFDS710_PAL_ALIGN_SINGLE_POINTER == 0 );
  33   // TRD : existing_lasoe can be NULL
  34
  35   /* TRD : imagine a list, sorted small to large
  36
  37            we arrive at an element
  38            we obtain its next pointer
  39            we check we are greater than the current element and smaller than the next element
  40            this means we have found the correct location to insert
  41            we try to CAS ourselves in; in the meantime,
  42            someone else has *aready* swapped in an element which is smaller than we are
  43
  44            e.g.
  45
  46            the list is { 1, 10 } and we are the value 5
  47
  48            we arrive at 1; we check the next element and see it is 10
  49            so we are larger than the current element and smaller than the next
  50            we are in the correct location to insert and we go to insert...
  51
  52            in the meantime, someone else with the value 3 comes along
  53            he too finds this is the correct location and inserts before we do
  54            the list is now { 1, 3, 10 } and we are trying to insert now after
  55            1 and before 3!
  56
  57            our insert CAS fails, because the next pointer of 1 has changed aready;
  58            but we see we are in the wrong location - we need to move forward an
  59            element
  60   */
  61
  62   LFDS710_MISC_BARRIER_LOAD;
  63
  64   /* TRD : we need to begin with the leading dummy element
  65            as the element to be inserted
  66            may be smaller than all elements in the list
  67   */
  68
  69   lasoe_trailing = lasos->start;
  70   lasoe_temp = lasos->start->next;
  71
  72   while( finished_flag == LFDS710_MISC_FLAG_LOWERED )
  73   {
  74     if( lasoe_temp == NULL )
  75       compare_result = -1;
  76
  77     if( lasoe_temp != NULL )
  78     {
  79       LFDS710_MISC_BARRIER_LOAD;
  80       compare_result = lasos->key_compare_function( lasoe->key, lasoe_temp->key );
  81     }
  82
  83     if( compare_result == 0 )
  84     {
  85       if( existing_lasoe != NULL )
  86         *existing_lasoe = lasoe_temp;
  87
  88       switch( lasos->existing_key )
  89       {
  90         case LFDS710_LIST_ASO_EXISTING_KEY_OVERWRITE:
  91           LFDS710_LIST_ASO_SET_VALUE_IN_ELEMENT( *lasoe_temp, lasoe->value );
  92           return LFDS710_LIST_ASO_INSERT_RESULT_SUCCESS_OVERWRITE;
  93         break;
  94
  95         case LFDS710_LIST_ASO_EXISTING_KEY_FAIL:
  96           return LFDS710_LIST_ASO_INSERT_RESULT_FAILURE_EXISTING_KEY;
  97         break;
  98       }
  99
 100       finished_flag = LFDS710_MISC_FLAG_RAISED;
 101     }
 102
 103     if( compare_result < 0 )
 104     {
 105       lasoe->next = lasoe_temp;
 106       LFDS710_MISC_BARRIER_STORE;
 107       LFDS710_PAL_ATOMIC_CAS( &lasoe_trailing->next, (struct lfds710_list_aso_element **) &lasoe->next, lasoe, LFDS710_MISC_CAS_STRENGTH_WEAK, result );
 108
 109       if( result == 1 )
 110         finished_flag = LFDS710_MISC_FLAG_RAISED;
 111       else
 112       {
 113         LFDS710_BACKOFF_EXPONENTIAL_BACKOFF( lasos->insert_backoff, backoff_iteration );
 114         // TRD : if we fail to link, someone else has linked and so we need to redetermine our position is correct
 115         lasoe_temp = lasoe_trailing->next;
 116       }
 117     }
 118
 119     if( compare_result > 0 )
 120     {
 121       // TRD : move trailing along by one element
 122       lasoe_trailing = lasoe_trailing->next;
 123
 124       /* TRD : set temp as the element after trailing
 125                if the new element we're linking is larger than all elements in the list,
 126                lasoe_temp will now go to NULL and we'll link at the end
 127       */
 128       lasoe_temp = lasoe_trailing->next;
 129     }
 130   }
 131
 132   LFDS710_BACKOFF_AUTOTUNE( lasos->insert_backoff, backoff_iteration );
 133
 134   return LFDS710_LIST_ASO_INSERT_RESULT_SUCCESS;
 135 }
 136