1 #include "lfds601_queue_internal.h"
\r
7 /****************************************************************************/
\r
8 int lfds601_queue_enqueue( struct lfds601_queue_state *qs, void *user_data )
\r
10 LFDS601_ALIGN(LFDS601_ALIGN_DOUBLE_POINTER) struct lfds601_queue_element
\r
11 *qe[LFDS601_QUEUE_PAC_SIZE];
\r
13 assert( qs != NULL );
\r
14 // TRD : user_data can be NULL
\r
16 lfds601_queue_internal_new_element_from_freelist( qs, qe, user_data );
\r
18 if( qe[LFDS601_QUEUE_POINTER] == NULL )
\r
21 lfds601_queue_internal_queue( qs, qe );
\r
30 /****************************************************************************/
\r
31 int lfds601_queue_guaranteed_enqueue( struct lfds601_queue_state *qs, void *user_data )
\r
33 LFDS601_ALIGN(LFDS601_ALIGN_DOUBLE_POINTER) struct lfds601_queue_element
\r
34 *qe[LFDS601_QUEUE_PAC_SIZE];
\r
36 assert( qs != NULL );
\r
37 // TRD : user_data can be NULL
\r
39 lfds601_queue_internal_guaranteed_new_element_from_freelist( qs, qe, user_data );
\r
41 if( qe[LFDS601_QUEUE_POINTER] == NULL )
\r
44 lfds601_queue_internal_queue( qs, qe );
\r
53 /****************************************************************************/
\r
54 void lfds601_queue_internal_queue( struct lfds601_queue_state *qs, struct lfds601_queue_element *qe[LFDS601_QUEUE_PAC_SIZE] )
\r
56 LFDS601_ALIGN(LFDS601_ALIGN_DOUBLE_POINTER) struct lfds601_queue_element
\r
57 *enqueue[LFDS601_QUEUE_PAC_SIZE],
\r
58 *next[LFDS601_QUEUE_PAC_SIZE];
\r
63 assert( qs != NULL );
\r
64 assert( qe != NULL );
\r
68 enqueue[LFDS601_QUEUE_POINTER] = qs->enqueue[LFDS601_QUEUE_POINTER];
\r
69 enqueue[LFDS601_QUEUE_COUNTER] = qs->enqueue[LFDS601_QUEUE_COUNTER];
\r
71 next[LFDS601_QUEUE_POINTER] = enqueue[LFDS601_QUEUE_POINTER]->next[LFDS601_QUEUE_POINTER];
\r
72 next[LFDS601_QUEUE_COUNTER] = enqueue[LFDS601_QUEUE_POINTER]->next[LFDS601_QUEUE_COUNTER];
\r
74 /* TRD : this if() ensures that the next we read, just above,
\r
75 really is from qs->enqueue (which we copied into enqueue)
\r
78 if( qs->enqueue[LFDS601_QUEUE_POINTER] == enqueue[LFDS601_QUEUE_POINTER] and qs->enqueue[LFDS601_QUEUE_COUNTER] == enqueue[LFDS601_QUEUE_COUNTER] )
\r
80 if( next[LFDS601_QUEUE_POINTER] == NULL )
\r
82 qe[LFDS601_QUEUE_COUNTER] = next[LFDS601_QUEUE_COUNTER] + 1;
\r
83 cas_result = lfds601_abstraction_dcas( (volatile lfds601_atom_t *) enqueue[LFDS601_QUEUE_POINTER]->next, (lfds601_atom_t *) qe, (lfds601_atom_t *) next );
\r
87 next[LFDS601_QUEUE_COUNTER] = enqueue[LFDS601_QUEUE_COUNTER] + 1;
\r
88 lfds601_abstraction_dcas( (volatile lfds601_atom_t *) qs->enqueue, (lfds601_atom_t *) next, (lfds601_atom_t *) enqueue );
\r
92 while( cas_result == 0 );
\r
94 qe[LFDS601_QUEUE_COUNTER] = enqueue[LFDS601_QUEUE_COUNTER] + 1;
\r
95 lfds601_abstraction_dcas( (volatile lfds601_atom_t *) qs->enqueue, (lfds601_atom_t *) qe, (lfds601_atom_t *) enqueue );
\r
104 /****************************************************************************/
\r
105 int lfds601_queue_dequeue( struct lfds601_queue_state *qs, void **user_data )
\r
107 LFDS601_ALIGN(LFDS601_ALIGN_DOUBLE_POINTER) struct lfds601_queue_element
\r
108 *enqueue[LFDS601_QUEUE_PAC_SIZE],
\r
109 *dequeue[LFDS601_QUEUE_PAC_SIZE],
\r
110 *next[LFDS601_QUEUE_PAC_SIZE];
\r
117 state = LFDS601_QUEUE_STATE_UNKNOWN,
\r
118 finished_flag = LOWERED;
\r
120 assert( qs != NULL );
\r
121 assert( user_data != NULL );
\r
125 dequeue[LFDS601_QUEUE_POINTER] = qs->dequeue[LFDS601_QUEUE_POINTER];
\r
126 dequeue[LFDS601_QUEUE_COUNTER] = qs->dequeue[LFDS601_QUEUE_COUNTER];
\r
128 enqueue[LFDS601_QUEUE_POINTER] = qs->enqueue[LFDS601_QUEUE_POINTER];
\r
129 enqueue[LFDS601_QUEUE_COUNTER] = qs->enqueue[LFDS601_QUEUE_COUNTER];
\r
131 next[LFDS601_QUEUE_POINTER] = dequeue[LFDS601_QUEUE_POINTER]->next[LFDS601_QUEUE_POINTER];
\r
132 next[LFDS601_QUEUE_COUNTER] = dequeue[LFDS601_QUEUE_POINTER]->next[LFDS601_QUEUE_COUNTER];
\r
134 /* TRD : confirm that dequeue didn't move between reading it
\r
135 and reading its next pointer
\r
138 if( dequeue[LFDS601_QUEUE_POINTER] == qs->dequeue[LFDS601_QUEUE_POINTER] and dequeue[LFDS601_QUEUE_COUNTER] == qs->dequeue[LFDS601_QUEUE_COUNTER] )
\r
140 if( enqueue[LFDS601_QUEUE_POINTER] == dequeue[LFDS601_QUEUE_POINTER] and next[LFDS601_QUEUE_POINTER] == NULL )
\r
141 state = LFDS601_QUEUE_STATE_EMPTY;
\r
143 if( enqueue[LFDS601_QUEUE_POINTER] == dequeue[LFDS601_QUEUE_POINTER] and next[LFDS601_QUEUE_POINTER] != NULL )
\r
144 state = LFDS601_QUEUE_STATE_ENQUEUE_OUT_OF_PLACE;
\r
146 if( enqueue[LFDS601_QUEUE_POINTER] != dequeue[LFDS601_QUEUE_POINTER] )
\r
147 state = LFDS601_QUEUE_STATE_ATTEMPT_DELFDS601_QUEUE;
\r
151 case LFDS601_QUEUE_STATE_EMPTY:
\r
154 finished_flag = RAISED;
\r
157 case LFDS601_QUEUE_STATE_ENQUEUE_OUT_OF_PLACE:
\r
158 next[LFDS601_QUEUE_COUNTER] = enqueue[LFDS601_QUEUE_COUNTER] + 1;
\r
159 lfds601_abstraction_dcas( (volatile lfds601_atom_t *) qs->enqueue, (lfds601_atom_t *) next, (lfds601_atom_t *) enqueue );
\r
162 case LFDS601_QUEUE_STATE_ATTEMPT_DELFDS601_QUEUE:
\r
163 *user_data = next[LFDS601_QUEUE_POINTER]->user_data;
\r
165 next[LFDS601_QUEUE_COUNTER] = dequeue[LFDS601_QUEUE_COUNTER] + 1;
\r
166 cas_result = lfds601_abstraction_dcas( (volatile lfds601_atom_t *) qs->dequeue, (lfds601_atom_t *) next, (lfds601_atom_t *) dequeue );
\r
168 if( cas_result == 1 )
\r
169 finished_flag = RAISED;
\r
174 while( finished_flag == LOWERED );
\r
176 if( cas_result == 1 )
\r
177 lfds601_freelist_push( qs->fs, dequeue[LFDS601_QUEUE_POINTER]->fe );
\r