1 #include "lfds611_queue_internal.h"
\r
7 /****************************************************************************/
\r
8 int lfds611_queue_enqueue( struct lfds611_queue_state *qs, void *user_data )
\r
10 LFDS611_ALIGN(LFDS611_ALIGN_DOUBLE_POINTER) struct lfds611_queue_element
\r
11 *qe[LFDS611_QUEUE_PAC_SIZE];
\r
13 assert( qs != NULL );
\r
14 // TRD : user_data can be NULL
\r
16 lfds611_queue_internal_new_element_from_freelist( qs, qe, user_data );
\r
18 if( qe[LFDS611_QUEUE_POINTER] == NULL )
\r
21 lfds611_queue_internal_queue( qs, qe );
\r
30 /****************************************************************************/
\r
31 int lfds611_queue_guaranteed_enqueue( struct lfds611_queue_state *qs, void *user_data )
\r
33 LFDS611_ALIGN(LFDS611_ALIGN_DOUBLE_POINTER) struct lfds611_queue_element
\r
34 *qe[LFDS611_QUEUE_PAC_SIZE];
\r
36 assert( qs != NULL );
\r
37 // TRD : user_data can be NULL
\r
39 lfds611_queue_internal_guaranteed_new_element_from_freelist( qs, qe, user_data );
\r
41 if( qe[LFDS611_QUEUE_POINTER] == NULL )
\r
44 lfds611_queue_internal_queue( qs, qe );
\r
53 /****************************************************************************/
\r
54 void lfds611_queue_internal_queue( struct lfds611_queue_state *qs, struct lfds611_queue_element *qe[LFDS611_QUEUE_PAC_SIZE] )
\r
56 LFDS611_ALIGN(LFDS611_ALIGN_DOUBLE_POINTER) struct lfds611_queue_element
\r
57 *enqueue[LFDS611_QUEUE_PAC_SIZE],
\r
58 *next[LFDS611_QUEUE_PAC_SIZE];
\r
63 assert( qs != NULL );
\r
64 assert( qe != NULL );
\r
66 // TRD : the DCAS operation issues a read and write barrier, so we don't need a read barrier in the do() loop
\r
68 LFDS611_BARRIER_LOAD;
\r
72 enqueue[LFDS611_QUEUE_POINTER] = qs->enqueue[LFDS611_QUEUE_POINTER];
\r
73 enqueue[LFDS611_QUEUE_COUNTER] = qs->enqueue[LFDS611_QUEUE_COUNTER];
\r
75 next[LFDS611_QUEUE_POINTER] = enqueue[LFDS611_QUEUE_POINTER]->next[LFDS611_QUEUE_POINTER];
\r
76 next[LFDS611_QUEUE_COUNTER] = enqueue[LFDS611_QUEUE_POINTER]->next[LFDS611_QUEUE_COUNTER];
\r
78 /* TRD : this if() ensures that the next we read, just above,
\r
79 really is from qs->enqueue (which we copied into enqueue)
\r
82 LFDS611_BARRIER_LOAD;
\r
84 if( qs->enqueue[LFDS611_QUEUE_POINTER] == enqueue[LFDS611_QUEUE_POINTER] and qs->enqueue[LFDS611_QUEUE_COUNTER] == enqueue[LFDS611_QUEUE_COUNTER] )
\r
86 if( next[LFDS611_QUEUE_POINTER] == NULL )
\r
88 qe[LFDS611_QUEUE_COUNTER] = next[LFDS611_QUEUE_COUNTER] + 1;
\r
89 cas_result = lfds611_abstraction_dcas( (volatile lfds611_atom_t *) enqueue[LFDS611_QUEUE_POINTER]->next, (lfds611_atom_t *) qe, (lfds611_atom_t *) next );
\r
93 next[LFDS611_QUEUE_COUNTER] = enqueue[LFDS611_QUEUE_COUNTER] + 1;
\r
94 lfds611_abstraction_dcas( (volatile lfds611_atom_t *) qs->enqueue, (lfds611_atom_t *) next, (lfds611_atom_t *) enqueue );
\r
98 while( cas_result == 0 );
\r
100 qe[LFDS611_QUEUE_COUNTER] = enqueue[LFDS611_QUEUE_COUNTER] + 1;
\r
101 lfds611_abstraction_dcas( (volatile lfds611_atom_t *) qs->enqueue, (lfds611_atom_t *) qe, (lfds611_atom_t *) enqueue );
\r
110 /****************************************************************************/
\r
111 int lfds611_queue_dequeue( struct lfds611_queue_state *qs, void **user_data )
\r
113 LFDS611_ALIGN(LFDS611_ALIGN_DOUBLE_POINTER) struct lfds611_queue_element
\r
114 *enqueue[LFDS611_QUEUE_PAC_SIZE],
\r
115 *dequeue[LFDS611_QUEUE_PAC_SIZE],
\r
116 *next[LFDS611_QUEUE_PAC_SIZE];
\r
123 state = LFDS611_QUEUE_STATE_UNKNOWN,
\r
124 finished_flag = LOWERED;
\r
126 assert( qs != NULL );
\r
127 assert( user_data != NULL );
\r
129 // TRD : the DCAS operation issues a read and write barrier, so we don't need a read barrier in the do() loop
\r
131 LFDS611_BARRIER_LOAD;
\r
135 dequeue[LFDS611_QUEUE_POINTER] = qs->dequeue[LFDS611_QUEUE_POINTER];
\r
136 dequeue[LFDS611_QUEUE_COUNTER] = qs->dequeue[LFDS611_QUEUE_COUNTER];
\r
138 enqueue[LFDS611_QUEUE_POINTER] = qs->enqueue[LFDS611_QUEUE_POINTER];
\r
139 enqueue[LFDS611_QUEUE_COUNTER] = qs->enqueue[LFDS611_QUEUE_COUNTER];
\r
141 next[LFDS611_QUEUE_POINTER] = dequeue[LFDS611_QUEUE_POINTER]->next[LFDS611_QUEUE_POINTER];
\r
142 next[LFDS611_QUEUE_COUNTER] = dequeue[LFDS611_QUEUE_POINTER]->next[LFDS611_QUEUE_COUNTER];
\r
144 /* TRD : confirm that dequeue didn't move between reading it
\r
145 and reading its next pointer
\r
148 LFDS611_BARRIER_LOAD;
\r
150 if( dequeue[LFDS611_QUEUE_POINTER] == qs->dequeue[LFDS611_QUEUE_POINTER] and dequeue[LFDS611_QUEUE_COUNTER] == qs->dequeue[LFDS611_QUEUE_COUNTER] )
\r
152 if( enqueue[LFDS611_QUEUE_POINTER] == dequeue[LFDS611_QUEUE_POINTER] and next[LFDS611_QUEUE_POINTER] == NULL )
\r
153 state = LFDS611_QUEUE_STATE_EMPTY;
\r
155 if( enqueue[LFDS611_QUEUE_POINTER] == dequeue[LFDS611_QUEUE_POINTER] and next[LFDS611_QUEUE_POINTER] != NULL )
\r
156 state = LFDS611_QUEUE_STATE_ENQUEUE_OUT_OF_PLACE;
\r
158 if( enqueue[LFDS611_QUEUE_POINTER] != dequeue[LFDS611_QUEUE_POINTER] )
\r
159 state = LFDS611_QUEUE_STATE_ATTEMPT_DELFDS611_QUEUE;
\r
163 case LFDS611_QUEUE_STATE_EMPTY:
\r
166 finished_flag = RAISED;
\r
169 case LFDS611_QUEUE_STATE_ENQUEUE_OUT_OF_PLACE:
\r
170 next[LFDS611_QUEUE_COUNTER] = enqueue[LFDS611_QUEUE_COUNTER] + 1;
\r
171 lfds611_abstraction_dcas( (volatile lfds611_atom_t *) qs->enqueue, (lfds611_atom_t *) next, (lfds611_atom_t *) enqueue );
\r
174 case LFDS611_QUEUE_STATE_ATTEMPT_DELFDS611_QUEUE:
\r
175 *user_data = next[LFDS611_QUEUE_POINTER]->user_data;
\r
177 next[LFDS611_QUEUE_COUNTER] = dequeue[LFDS611_QUEUE_COUNTER] + 1;
\r
178 cas_result = lfds611_abstraction_dcas( (volatile lfds611_atom_t *) qs->dequeue, (lfds611_atom_t *) next, (lfds611_atom_t *) dequeue );
\r
180 if( cas_result == 1 )
\r
181 finished_flag = RAISED;
\r
186 while( finished_flag == LOWERED );
\r
188 if( cas_result == 1 )
\r
189 lfds611_freelist_push( qs->fs, dequeue[LFDS611_QUEUE_POINTER]->fe );
\r