2 #include "lfds700_queue_internal.h"
8 /****************************************************************************/
9 int lfds700_queue_dequeue( struct lfds700_queue_state *qs,
10 struct lfds700_queue_element **qe,
11 struct lfds700_misc_prng_state *ps )
17 enum lfds700_queue_queue_state
18 state = LFDS700_QUEUE_QUEUE_STATE_UNKNOWN;
22 finished_flag = LFDS700_MISC_FLAG_LOWERED;
25 backoff_iteration = LFDS700_MISC_ABSTRACTION_BACKOFF_INITIAL_VALUE;
27 struct lfds700_queue_element LFDS700_PAL_ALIGN(LFDS700_PAL_ALIGN_DOUBLE_POINTER)
36 LFDS700_PAL_ASSERT( qs != NULL );
37 LFDS700_PAL_ASSERT( qe != NULL );
38 LFDS700_PAL_ASSERT( ps != NULL );
40 LFDS700_MISC_BARRIER_LOAD;
44 dequeue[COUNTER] = qs->dequeue[COUNTER];
45 dequeue[POINTER] = qs->dequeue[POINTER];
47 enqueue[COUNTER] = qs->enqueue[COUNTER];
48 enqueue[POINTER] = qs->enqueue[POINTER];
50 next[COUNTER] = qs->dequeue[POINTER]->next[COUNTER];
51 next[POINTER] = qs->dequeue[POINTER]->next[POINTER];
53 LFDS700_MISC_BARRIER_LOAD;
55 if( dequeue[COUNTER] == qs->dequeue[COUNTER] and dequeue[POINTER] == qs->dequeue[POINTER] )
57 if( enqueue[POINTER] == dequeue[POINTER] and next[POINTER] == NULL )
58 state = LFDS700_QUEUE_QUEUE_STATE_EMPTY;
60 if( enqueue[POINTER] == dequeue[POINTER] and next[POINTER] != NULL )
61 state = LFDS700_QUEUE_QUEUE_STATE_ENQUEUE_OUT_OF_PLACE;
63 if( enqueue[POINTER] != dequeue[POINTER] )
64 state = LFDS700_QUEUE_QUEUE_STATE_ATTEMPT_DEQUEUE;
68 case LFDS700_QUEUE_QUEUE_STATE_UNKNOWN:
69 // TRD : eliminates compiler warning
72 case LFDS700_QUEUE_QUEUE_STATE_EMPTY:
75 finished_flag = LFDS700_MISC_FLAG_RAISED;
78 case LFDS700_QUEUE_QUEUE_STATE_ENQUEUE_OUT_OF_PLACE:
79 next[COUNTER] = enqueue[COUNTER] + 1;
80 LFDS700_MISC_BARRIER_STORE;
81 LFDS700_PAL_ATOMIC_DWCAS( qs->enqueue, enqueue, next, LFDS700_MISC_CAS_STRENGTH_WEAK, unwanted_result );
84 case LFDS700_QUEUE_QUEUE_STATE_ATTEMPT_DEQUEUE:
85 key = next[POINTER]->key;
86 value = next[POINTER]->value;
88 next[COUNTER] = dequeue[COUNTER] + 1;
89 LFDS700_MISC_BARRIER_STORE;
90 LFDS700_PAL_ATOMIC_DWCAS_WITH_BACKOFF( qs->dequeue, dequeue, next, LFDS700_MISC_CAS_STRENGTH_WEAK, result, backoff_iteration, ps );
93 finished_flag = LFDS700_MISC_FLAG_RAISED;
98 while( finished_flag == LFDS700_MISC_FLAG_LOWERED );
102 *qe = dequeue[POINTER];
104 (*qe)->value = value;