2 #include "lfds700_list_addonly_singlylinked_unordered_internal.h"
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 )
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 );
26 case LFDS700_LIST_ASU_POSITION_START:
27 lfds700_list_asu_insert_at_start( lasus, lasue, ps );
30 case LFDS700_LIST_ASU_POSITION_END:
31 lfds700_list_asu_insert_at_end( lasus, lasue, ps );
34 case LFDS700_LIST_ASU_POSITION_AFTER:
35 lfds700_list_asu_insert_after_element( lasus, lasue, lasue_predecessor, ps );
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 )
55 backoff_iteration = LFDS700_MISC_ABSTRACTION_BACKOFF_INITIAL_VALUE;
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 );
64 LFDS700_MISC_BARRIER_LOAD;
66 lasue->next = lasus->start->next;
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 );
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 )
90 enum lfds700_misc_flag
91 finished_flag = LFDS700_MISC_FLAG_LOWERED;
94 backoff_iteration = LFDS700_MISC_ABSTRACTION_BACKOFF_INITIAL_VALUE;
96 struct lfds700_list_asu_element LFDS700_PAL_ALIGN(LFDS700_PAL_ALIGN_SINGLE_POINTER)
99 struct lfds700_list_asu_element
100 *volatile lasue_next,
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 );
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
114 when successful, update end to ourselves
116 note there's a leading dummy element
117 so lasus->end always points to an element
120 LFDS700_MISC_BARRIER_LOAD;
123 lasue_end = lasus->end;
125 while( finished_flag == LFDS700_MISC_FLAG_LOWERED )
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 );
133 finished_flag = LFDS700_MISC_FLAG_RAISED;
137 lasue_next = LFDS700_LIST_ASU_GET_NEXT( *lasue_end );
139 while( lasue_next != NULL )
141 lasue_end = lasue_next;
142 lasue_next = LFDS700_LIST_ASU_GET_NEXT( *lasue_end );
156 /****************************************************************************/
157 #pragma warning( disable : 4100 )
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 )
168 backoff_iteration = LFDS700_MISC_ABSTRACTION_BACKOFF_INITIAL_VALUE;
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 );
178 LFDS700_MISC_BARRIER_LOAD;
180 lasue->next = lasue_predecessor->next;
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 );
187 while( result != 1 );
192 #pragma warning( default : 4100 )