2 #include "lfds700_list_addonly_ordered_singlylinked_internal.h"
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 )
17 enum lfds700_misc_flag
18 finished_flag = LFDS700_MISC_FLAG_LOWERED;
24 backoff_iteration = LFDS700_MISC_ABSTRACTION_BACKOFF_INITIAL_VALUE;
26 struct lfds700_list_aos_element
27 *volatile laose_temp = NULL,
28 *volatile laose_trailing;
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 );
38 /* TRD : imagine a list, sorted small to large
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
49 the list is { 1, 10 } and we are the value 5
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...
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
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
65 LFDS700_MISC_BARRIER_LOAD;
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
72 laose_trailing = laoss->start;
73 laose_temp = laoss->start->next;
75 while( finished_flag == LFDS700_MISC_FLAG_LOWERED )
77 if( laose_temp == NULL )
80 if( laose_temp != NULL )
82 LFDS700_MISC_BARRIER_LOAD;
83 compare_result = laoss->key_compare_function( laose->key, laose_temp->key );
86 if( compare_result == 0 )
88 if( existing_laose != NULL )
89 *existing_laose = laose_temp;
91 switch( laoss->existing_key )
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 );
98 case LFDS700_LIST_AOS_EXISTING_KEY_FAIL:
99 return( LFDS700_LIST_AOS_INSERT_RESULT_FAILURE_EXISTING_KEY );
103 finished_flag = LFDS700_MISC_FLAG_RAISED;
106 if( compare_result < 0 )
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 );
113 finished_flag = LFDS700_MISC_FLAG_RAISED;
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;
119 if( compare_result > 0 )
121 // TRD : move trailing along by one element
122 laose_trailing = laose_trailing->next;
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
128 laose_temp = laose_trailing->next;
132 return( LFDS700_LIST_AOS_INSERT_RESULT_SUCCESS );