]> pd.if.org Git - liblfds/blob - liblfds/liblfds6.0.0/liblfds600/src/lfds600_queue/lfds600_queue_queue.c
Initial import (all versions, including the new 7.1.0)
[liblfds] / liblfds / liblfds6.0.0 / liblfds600 / src / lfds600_queue / lfds600_queue_queue.c
1 #include "lfds600_queue_internal.h"
2
3
4
5
6
7 /****************************************************************************/
8 int lfds600_queue_enqueue( struct lfds600_queue_state *qs, void *user_data )
9 {
10   LFDS600_ALIGN(LFDS600_ALIGN_DOUBLE_POINTER) struct lfds600_queue_element
11     *qe[LFDS600_QUEUE_PAC_SIZE];
12
13   assert( qs != NULL );
14   // TRD : user_data can be NULL
15
16   lfds600_queue_internal_new_element_from_freelist( qs, qe, user_data );
17
18   if( qe[LFDS600_QUEUE_POINTER] == NULL )
19     return( 0 );
20
21   lfds600_queue_internal_queue( qs, qe );
22
23   return( 1 );
24 }
25
26
27
28
29
30 /****************************************************************************/
31 int lfds600_queue_guaranteed_enqueue( struct lfds600_queue_state *qs, void *user_data )
32 {
33   LFDS600_ALIGN(LFDS600_ALIGN_DOUBLE_POINTER) struct lfds600_queue_element
34     *qe[LFDS600_QUEUE_PAC_SIZE];
35
36   assert( qs != NULL );
37   // TRD : user_data can be NULL
38
39   lfds600_queue_internal_guaranteed_new_element_from_freelist( qs, qe, user_data );
40
41   if( qe[LFDS600_QUEUE_POINTER] == NULL )
42     return( 0 );
43
44   lfds600_queue_internal_queue( qs, qe );
45
46   return( 1 );
47 }
48
49
50
51
52
53 /****************************************************************************/
54 void lfds600_queue_internal_queue( struct lfds600_queue_state *qs, struct lfds600_queue_element *qe[LFDS600_QUEUE_PAC_SIZE] )
55 {
56   LFDS600_ALIGN(LFDS600_ALIGN_DOUBLE_POINTER) struct lfds600_queue_element
57     *enqueue[LFDS600_QUEUE_PAC_SIZE],
58     *next[LFDS600_QUEUE_PAC_SIZE];
59
60   unsigned char
61     cas_result = 0;
62
63   assert( qs != NULL );
64   assert( qe != NULL );
65
66   do
67   {
68     enqueue[LFDS600_QUEUE_POINTER] = qs->enqueue[LFDS600_QUEUE_POINTER];
69     enqueue[LFDS600_QUEUE_COUNTER] = qs->enqueue[LFDS600_QUEUE_COUNTER];
70
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];
73
74     /* TRD : this if() ensures that the next we read, just above,
75              really is from qs->enqueue (which we copied into enqueue)
76     */
77
78     if( qs->enqueue[LFDS600_QUEUE_POINTER] == enqueue[LFDS600_QUEUE_POINTER] and qs->enqueue[LFDS600_QUEUE_COUNTER] == enqueue[LFDS600_QUEUE_COUNTER] )
79     {
80       if( next[LFDS600_QUEUE_POINTER] == NULL )
81       {
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 );
84       }
85       else
86       {
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 );
89       }
90     }
91   }
92   while( cas_result == 0 );
93
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 );
96
97   return;
98 }
99
100
101
102
103
104 /****************************************************************************/
105 int lfds600_queue_dequeue( struct lfds600_queue_state *qs, void **user_data )
106 {
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];
111
112   unsigned char
113     cas_result = 0;
114
115   int
116     rv = 1,
117     state = LFDS600_QUEUE_STATE_UNKNOWN,
118     finished_flag = LOWERED;
119
120   assert( qs != NULL );
121   assert( user_data != NULL );
122
123   do
124   {
125     dequeue[LFDS600_QUEUE_POINTER] = qs->dequeue[LFDS600_QUEUE_POINTER];
126     dequeue[LFDS600_QUEUE_COUNTER] = qs->dequeue[LFDS600_QUEUE_COUNTER];
127
128     enqueue[LFDS600_QUEUE_POINTER] = qs->enqueue[LFDS600_QUEUE_POINTER];
129     enqueue[LFDS600_QUEUE_COUNTER] = qs->enqueue[LFDS600_QUEUE_COUNTER];
130
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];
133
134     /* TRD : confirm that dequeue didn't move between reading it
135              and reading its next pointer
136     */
137
138     if( dequeue[LFDS600_QUEUE_POINTER] == qs->dequeue[LFDS600_QUEUE_POINTER] and dequeue[LFDS600_QUEUE_COUNTER] == qs->dequeue[LFDS600_QUEUE_COUNTER] )
139     {
140       if( enqueue[LFDS600_QUEUE_POINTER] == dequeue[LFDS600_QUEUE_POINTER] and next[LFDS600_QUEUE_POINTER] == NULL )
141         state = LFDS600_QUEUE_STATE_EMPTY;
142
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;
145
146       if( enqueue[LFDS600_QUEUE_POINTER] != dequeue[LFDS600_QUEUE_POINTER] )
147         state = LFDS600_QUEUE_STATE_ATTEMPT_DELFDS600_QUEUE;
148
149       switch( state )
150       {
151         case LFDS600_QUEUE_STATE_EMPTY:
152           *user_data = NULL;
153           rv = 0;
154           finished_flag = RAISED;
155         break;
156
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 );
160         break;
161
162         case LFDS600_QUEUE_STATE_ATTEMPT_DELFDS600_QUEUE:
163           *user_data = next[LFDS600_QUEUE_POINTER]->user_data;
164
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 );
167
168           if( cas_result == 1 )
169             finished_flag = RAISED;
170         break;
171       }
172     }
173   }
174   while( finished_flag == LOWERED );
175
176   if( cas_result == 1 )
177     lfds600_freelist_push( qs->fs, dequeue[LFDS600_QUEUE_POINTER]->fe );
178
179   return( rv );
180 }
181