2 #include "lfds700_queue_internal.h"
8 /****************************************************************************/
9 void lfds700_queue_enqueue( struct lfds700_queue_state *qs,
10 struct lfds700_queue_element *qe,
11 struct lfds700_misc_prng_state *ps )
18 backoff_iteration = LFDS700_MISC_ABSTRACTION_BACKOFF_INITIAL_VALUE;
20 struct lfds700_queue_element LFDS700_PAL_ALIGN(LFDS700_PAL_ALIGN_DOUBLE_POINTER)
21 *volatile enqueue[PAC_SIZE],
22 *new_enqueue[PAC_SIZE],
23 *volatile next[PAC_SIZE];
25 LFDS700_PAL_ASSERT( qs != NULL );
26 LFDS700_PAL_ASSERT( qe != NULL );
27 LFDS700_PAL_ASSERT( (lfds700_pal_uint_t) qe->next % LFDS700_PAL_ATOMIC_ISOLATION_IN_BYTES == 0 );
28 LFDS700_PAL_ASSERT( (lfds700_pal_uint_t) &qe->key % LFDS700_PAL_ATOMIC_ISOLATION_IN_BYTES == 0 );
29 LFDS700_PAL_ASSERT( ps != NULL );
31 qe->next[COUNTER] = (struct lfds700_queue_element *) LFDS700_MISC_PRNG_GENERATE( ps );
32 qe->next[POINTER] = NULL;
34 new_enqueue[POINTER] = qe;
36 LFDS700_MISC_BARRIER_LOAD;
40 enqueue[COUNTER] = qs->enqueue[COUNTER];
41 enqueue[POINTER] = qs->enqueue[POINTER];
43 next[COUNTER] = qs->enqueue[POINTER]->next[COUNTER];
44 next[POINTER] = qs->enqueue[POINTER]->next[POINTER];
46 LFDS700_MISC_BARRIER_LOAD;
48 if( qs->enqueue[COUNTER] == enqueue[COUNTER] and qs->enqueue[POINTER] == enqueue[POINTER] )
50 if( next[POINTER] == NULL )
52 new_enqueue[COUNTER] = next[COUNTER] + 1;
53 LFDS700_MISC_BARRIER_STORE;
54 LFDS700_PAL_ATOMIC_DWCAS_WITH_BACKOFF( enqueue[POINTER]->next, next, new_enqueue, LFDS700_MISC_CAS_STRENGTH_WEAK, result, backoff_iteration, ps );
58 next[COUNTER] = enqueue[COUNTER] + 1;
59 LFDS700_MISC_BARRIER_STORE;
60 // TRD : strictly, this is a weak CAS, but we do an extra iteration of the main loop on a fake failure, so we set it to be strong
61 LFDS700_PAL_ATOMIC_DWCAS( qs->enqueue, enqueue, next, LFDS700_MISC_CAS_STRENGTH_STRONG, unwanted_result );
67 new_enqueue[COUNTER] = enqueue[COUNTER] + 1;
68 LFDS700_MISC_BARRIER_STORE;
69 // TRD : move enqueue along; only a weak CAS as the dequeue will solve this if its out of place
70 LFDS700_PAL_ATOMIC_DWCAS( qs->enqueue, enqueue, new_enqueue, LFDS700_MISC_CAS_STRENGTH_WEAK, unwanted_result );