pd.if.org Git - liblfds/blob - liblfds/liblfds7.0.0/liblfds700/src/lfds700_list_addonly_ordered_singlylinked/lfds700_list_addonly_ordered_singlylinked_insert.c

   1 /***** includes *****/
   2 #include "lfds700_list_addonly_ordered_singlylinked_internal.h"
   3
   4
   5
   6
   7
   8 /****************************************************************************/
   9 enum lfds700_list_aos_insert_result lfds700_list_aos_insert( struct lfds700_list_aos_state *laoss,
  10                                                          struct lfds700_list_aos_element *laose,
  11                                                          struct lfds700_list_aos_element **existing_laose,
  12                                                          struct lfds700_misc_prng_state *ps )
  13 {
  14   char unsigned
  15     result;
  16
  17   enum lfds700_misc_flag
  18     finished_flag = LFDS700_MISC_FLAG_LOWERED;
  19
  20   int
  21     compare_result = 0;
  22
  23   lfds700_pal_uint_t
  24     backoff_iteration = LFDS700_MISC_ABSTRACTION_BACKOFF_INITIAL_VALUE;
  25
  26   struct lfds700_list_aos_element
  27     *volatile laose_temp = NULL,
  28     *volatile laose_trailing;
  29
  30   LFDS700_PAL_ASSERT( laoss != NULL );
  31   LFDS700_PAL_ASSERT( laose != NULL );
  32   LFDS700_PAL_ASSERT( (lfds700_pal_uint_t) &laose->next % LFDS700_PAL_ATOMIC_ISOLATION_IN_BYTES == 0 );
  33   LFDS700_PAL_ASSERT( (lfds700_pal_uint_t) &laose->value % LFDS700_PAL_ATOMIC_ISOLATION_IN_BYTES == 0 );
  34   LFDS700_PAL_ASSERT( (lfds700_pal_uint_t) &laose->key % LFDS700_PAL_ATOMIC_ISOLATION_IN_BYTES == 0 );
  35   // TRD : existing_laose can be NULL
  36   LFDS700_PAL_ASSERT( ps != NULL );
  37
  38   /* TRD : imagine a list, sorted small to large
  39
  40            we arrive at an element
  41            we obtain its next pointer
  42            we check we are greater than the current element and smaller than the next element
  43            this means we have found the correct location to insert
  44            we try to CAS ourselves in; in the meantime,
  45            someone else has *aready* swapped in an element which is smaller than we are
  46
  47            e.g.
  48
  49            the list is { 1, 10 } and we are the value 5
  50
  51            we arrive at 1; we check the next element and see it is 10
  52            so we are larger than the current element and smaller than the next
  53            we are in the correct location to insert and we go to insert...
  54
  55            in the meantime, someone else with the value 3 comes along
  56            he too finds this is the correct location and inserts before we do
  57            the list is now { 1, 3, 10 } and we are trying to insert now after
  58            1 and before 3!
  59
  60            our insert CAS fails, because the next pointer of 1 has changed aready;
  61            but we see we are in the wrong location - we need to move forward an
  62            element
  63   */
  64
  65   LFDS700_MISC_BARRIER_LOAD;
  66
  67   /* TRD : we need to begin with the leading dummy element
  68            as the element to be inserted
  69            may be smaller than all elements in the list
  70   */
  71
  72   laose_trailing = laoss->start;
  73   laose_temp = laoss->start->next;
  74
  75   while( finished_flag == LFDS700_MISC_FLAG_LOWERED )
  76   {
  77     if( laose_temp == NULL )
  78       compare_result = -1;
  79
  80     if( laose_temp != NULL )
  81     {
  82       LFDS700_MISC_BARRIER_LOAD;
  83       compare_result = laoss->key_compare_function( laose->key, laose_temp->key );
  84     }
  85
  86     if( compare_result == 0 )
  87     {
  88       if( existing_laose != NULL )
  89         *existing_laose = laose_temp;
  90
  91       switch( laoss->existing_key )
  92       {
  93         case LFDS700_LIST_AOS_EXISTING_KEY_OVERWRITE:
  94           LFDS700_LIST_AOS_SET_VALUE_IN_ELEMENT( *laose_temp, laose->value );
  95           return( LFDS700_LIST_AOS_INSERT_RESULT_SUCCESS_OVERWRITE );
  96         break;
  97
  98         case LFDS700_LIST_AOS_EXISTING_KEY_FAIL:
  99           return( LFDS700_LIST_AOS_INSERT_RESULT_FAILURE_EXISTING_KEY );
 100         break;
 101       }
 102
 103       finished_flag = LFDS700_MISC_FLAG_RAISED;
 104     }
 105
 106     if( compare_result < 0 )
 107     {
 108       laose->next = laose_temp;
 109       LFDS700_MISC_BARRIER_STORE;
 110       LFDS700_PAL_ATOMIC_CAS_WITH_BACKOFF( &laose_trailing->next, &laose->next, laose, LFDS700_MISC_CAS_STRENGTH_WEAK, result, backoff_iteration, ps );
 111
 112       if( result == 1 )
 113         finished_flag = LFDS700_MISC_FLAG_RAISED;
 114       else
 115         // TRD : if we fail to link, someone else has linked and so we need to redetermine our position is correct
 116         laose_temp = laose_trailing->next;
 117     }
 118
 119     if( compare_result > 0 )
 120     {
 121       // TRD : move trailing along by one element
 122       laose_trailing = laose_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                laose_temp will now go to NULL and we'll link at the end
 127       */
 128       laose_temp = laose_trailing->next;
 129     }
 130   }
 131
 132   return( LFDS700_LIST_AOS_INSERT_RESULT_SUCCESS );
 133 }
 134