1 #include "lfds600_queue_internal.h"
7 /****************************************************************************/
8 int lfds600_queue_enqueue( struct lfds600_queue_state *qs, void *user_data )
10 LFDS600_ALIGN(LFDS600_ALIGN_DOUBLE_POINTER) struct lfds600_queue_element
11 *qe[LFDS600_QUEUE_PAC_SIZE];
14 // TRD : user_data can be NULL
16 lfds600_queue_internal_new_element_from_freelist( qs, qe, user_data );
18 if( qe[LFDS600_QUEUE_POINTER] == NULL )
21 lfds600_queue_internal_queue( qs, qe );
30 /****************************************************************************/
31 int lfds600_queue_guaranteed_enqueue( struct lfds600_queue_state *qs, void *user_data )
33 LFDS600_ALIGN(LFDS600_ALIGN_DOUBLE_POINTER) struct lfds600_queue_element
34 *qe[LFDS600_QUEUE_PAC_SIZE];
37 // TRD : user_data can be NULL
39 lfds600_queue_internal_guaranteed_new_element_from_freelist( qs, qe, user_data );
41 if( qe[LFDS600_QUEUE_POINTER] == NULL )
44 lfds600_queue_internal_queue( qs, qe );
53 /****************************************************************************/
54 void lfds600_queue_internal_queue( struct lfds600_queue_state *qs, struct lfds600_queue_element *qe[LFDS600_QUEUE_PAC_SIZE] )
56 LFDS600_ALIGN(LFDS600_ALIGN_DOUBLE_POINTER) struct lfds600_queue_element
57 *enqueue[LFDS600_QUEUE_PAC_SIZE],
58 *next[LFDS600_QUEUE_PAC_SIZE];
68 enqueue[LFDS600_QUEUE_POINTER] = qs->enqueue[LFDS600_QUEUE_POINTER];
69 enqueue[LFDS600_QUEUE_COUNTER] = qs->enqueue[LFDS600_QUEUE_COUNTER];
71 next[LFDS600_QUEUE_POINTER] = enqueue[LFDS600_QUEUE_POINTER]->next[LFDS600_QUEUE_POINTER];
72 next[LFDS600_QUEUE_COUNTER] = enqueue[LFDS600_QUEUE_POINTER]->next[LFDS600_QUEUE_COUNTER];
74 /* TRD : this if() ensures that the next we read, just above,
75 really is from qs->enqueue (which we copied into enqueue)
78 if( qs->enqueue[LFDS600_QUEUE_POINTER] == enqueue[LFDS600_QUEUE_POINTER] and qs->enqueue[LFDS600_QUEUE_COUNTER] == enqueue[LFDS600_QUEUE_COUNTER] )
80 if( next[LFDS600_QUEUE_POINTER] == NULL )
82 qe[LFDS600_QUEUE_COUNTER] = next[LFDS600_QUEUE_COUNTER] + 1;
83 cas_result = lfds600_abstraction_dcas( (volatile lfds600_atom_t *) enqueue[LFDS600_QUEUE_POINTER]->next, (lfds600_atom_t *) qe, (lfds600_atom_t *) next );
87 next[LFDS600_QUEUE_COUNTER] = enqueue[LFDS600_QUEUE_COUNTER] + 1;
88 lfds600_abstraction_dcas( (volatile lfds600_atom_t *) qs->enqueue, (lfds600_atom_t *) next, (lfds600_atom_t *) enqueue );
92 while( cas_result == 0 );
94 qe[LFDS600_QUEUE_COUNTER] = enqueue[LFDS600_QUEUE_COUNTER] + 1;
95 lfds600_abstraction_dcas( (volatile lfds600_atom_t *) qs->enqueue, (lfds600_atom_t *) qe, (lfds600_atom_t *) enqueue );
104 /****************************************************************************/
105 int lfds600_queue_dequeue( struct lfds600_queue_state *qs, void **user_data )
107 LFDS600_ALIGN(LFDS600_ALIGN_DOUBLE_POINTER) struct lfds600_queue_element
108 *enqueue[LFDS600_QUEUE_PAC_SIZE],
109 *dequeue[LFDS600_QUEUE_PAC_SIZE],
110 *next[LFDS600_QUEUE_PAC_SIZE];
117 state = LFDS600_QUEUE_STATE_UNKNOWN,
118 finished_flag = LOWERED;
120 assert( qs != NULL );
121 assert( user_data != NULL );
125 dequeue[LFDS600_QUEUE_POINTER] = qs->dequeue[LFDS600_QUEUE_POINTER];
126 dequeue[LFDS600_QUEUE_COUNTER] = qs->dequeue[LFDS600_QUEUE_COUNTER];
128 enqueue[LFDS600_QUEUE_POINTER] = qs->enqueue[LFDS600_QUEUE_POINTER];
129 enqueue[LFDS600_QUEUE_COUNTER] = qs->enqueue[LFDS600_QUEUE_COUNTER];
131 next[LFDS600_QUEUE_POINTER] = dequeue[LFDS600_QUEUE_POINTER]->next[LFDS600_QUEUE_POINTER];
132 next[LFDS600_QUEUE_COUNTER] = dequeue[LFDS600_QUEUE_POINTER]->next[LFDS600_QUEUE_COUNTER];
134 /* TRD : confirm that dequeue didn't move between reading it
135 and reading its next pointer
138 if( dequeue[LFDS600_QUEUE_POINTER] == qs->dequeue[LFDS600_QUEUE_POINTER] and dequeue[LFDS600_QUEUE_COUNTER] == qs->dequeue[LFDS600_QUEUE_COUNTER] )
140 if( enqueue[LFDS600_QUEUE_POINTER] == dequeue[LFDS600_QUEUE_POINTER] and next[LFDS600_QUEUE_POINTER] == NULL )
141 state = LFDS600_QUEUE_STATE_EMPTY;
143 if( enqueue[LFDS600_QUEUE_POINTER] == dequeue[LFDS600_QUEUE_POINTER] and next[LFDS600_QUEUE_POINTER] != NULL )
144 state = LFDS600_QUEUE_STATE_ENQUEUE_OUT_OF_PLACE;
146 if( enqueue[LFDS600_QUEUE_POINTER] != dequeue[LFDS600_QUEUE_POINTER] )
147 state = LFDS600_QUEUE_STATE_ATTEMPT_DELFDS600_QUEUE;
151 case LFDS600_QUEUE_STATE_EMPTY:
154 finished_flag = RAISED;
157 case LFDS600_QUEUE_STATE_ENQUEUE_OUT_OF_PLACE:
158 next[LFDS600_QUEUE_COUNTER] = enqueue[LFDS600_QUEUE_COUNTER] + 1;
159 lfds600_abstraction_dcas( (volatile lfds600_atom_t *) qs->enqueue, (lfds600_atom_t *) next, (lfds600_atom_t *) enqueue );
162 case LFDS600_QUEUE_STATE_ATTEMPT_DELFDS600_QUEUE:
163 *user_data = next[LFDS600_QUEUE_POINTER]->user_data;
165 next[LFDS600_QUEUE_COUNTER] = dequeue[LFDS600_QUEUE_COUNTER] + 1;
166 cas_result = lfds600_abstraction_dcas( (volatile lfds600_atom_t *) qs->dequeue, (lfds600_atom_t *) next, (lfds600_atom_t *) dequeue );
168 if( cas_result == 1 )
169 finished_flag = RAISED;
174 while( finished_flag == LOWERED );
176 if( cas_result == 1 )
177 lfds600_freelist_push( qs->fs, dequeue[LFDS600_QUEUE_POINTER]->fe );