]> pd.if.org Git - liblfds/blob - liblfds/liblfds6.1.1/liblfds611/src/lfds611_queue/lfds611_queue_queue.c
Initial import (all versions, including the new 7.1.0)
[liblfds] / liblfds / liblfds6.1.1 / liblfds611 / src / lfds611_queue / lfds611_queue_queue.c
1 #include "lfds611_queue_internal.h"\r
2 \r
3 \r
4 \r
5 \r
6 \r
7 /****************************************************************************/\r
8 int lfds611_queue_enqueue( struct lfds611_queue_state *qs, void *user_data )\r
9 {\r
10   LFDS611_ALIGN(LFDS611_ALIGN_DOUBLE_POINTER) struct lfds611_queue_element\r
11     *qe[LFDS611_QUEUE_PAC_SIZE];\r
12 \r
13   assert( qs != NULL );\r
14   // TRD : user_data can be NULL\r
15 \r
16   lfds611_queue_internal_new_element_from_freelist( qs, qe, user_data );\r
17 \r
18   if( qe[LFDS611_QUEUE_POINTER] == NULL )\r
19     return( 0 );\r
20 \r
21   lfds611_queue_internal_queue( qs, qe );\r
22 \r
23   return( 1 );\r
24 }\r
25 \r
26 \r
27 \r
28 \r
29 \r
30 /****************************************************************************/\r
31 int lfds611_queue_guaranteed_enqueue( struct lfds611_queue_state *qs, void *user_data )\r
32 {\r
33   LFDS611_ALIGN(LFDS611_ALIGN_DOUBLE_POINTER) struct lfds611_queue_element\r
34     *qe[LFDS611_QUEUE_PAC_SIZE];\r
35 \r
36   assert( qs != NULL );\r
37   // TRD : user_data can be NULL\r
38 \r
39   lfds611_queue_internal_guaranteed_new_element_from_freelist( qs, qe, user_data );\r
40 \r
41   if( qe[LFDS611_QUEUE_POINTER] == NULL )\r
42     return( 0 );\r
43 \r
44   lfds611_queue_internal_queue( qs, qe );\r
45 \r
46   return( 1 );\r
47 }\r
48 \r
49 \r
50 \r
51 \r
52 \r
53 /****************************************************************************/\r
54 void lfds611_queue_internal_queue( struct lfds611_queue_state *qs, struct lfds611_queue_element *qe[LFDS611_QUEUE_PAC_SIZE] )\r
55 {\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
59 \r
60   unsigned char\r
61     cas_result = 0;\r
62 \r
63   assert( qs != NULL );\r
64   assert( qe != NULL );\r
65 \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
67 \r
68   LFDS611_BARRIER_LOAD;\r
69 \r
70   do\r
71   {\r
72     enqueue[LFDS611_QUEUE_POINTER] = qs->enqueue[LFDS611_QUEUE_POINTER];\r
73     enqueue[LFDS611_QUEUE_COUNTER] = qs->enqueue[LFDS611_QUEUE_COUNTER];\r
74 \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
77 \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
80     */\r
81 \r
82     LFDS611_BARRIER_LOAD;\r
83 \r
84     if( qs->enqueue[LFDS611_QUEUE_POINTER] == enqueue[LFDS611_QUEUE_POINTER] and qs->enqueue[LFDS611_QUEUE_COUNTER] == enqueue[LFDS611_QUEUE_COUNTER] )\r
85     {\r
86       if( next[LFDS611_QUEUE_POINTER] == NULL )\r
87       {\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
90       }\r
91       else\r
92       {\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
95       }\r
96     }\r
97   }\r
98   while( cas_result == 0 );\r
99 \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
102 \r
103   return;\r
104 }\r
105 \r
106 \r
107 \r
108 \r
109 \r
110 /****************************************************************************/\r
111 int lfds611_queue_dequeue( struct lfds611_queue_state *qs, void **user_data )\r
112 {\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
117 \r
118   unsigned char\r
119     cas_result = 0;\r
120 \r
121   int\r
122     rv = 1,\r
123     state = LFDS611_QUEUE_STATE_UNKNOWN,\r
124     finished_flag = LOWERED;\r
125 \r
126   assert( qs != NULL );\r
127   assert( user_data != NULL );\r
128 \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
130 \r
131   LFDS611_BARRIER_LOAD;\r
132 \r
133   do\r
134   {\r
135     dequeue[LFDS611_QUEUE_POINTER] = qs->dequeue[LFDS611_QUEUE_POINTER];\r
136     dequeue[LFDS611_QUEUE_COUNTER] = qs->dequeue[LFDS611_QUEUE_COUNTER];\r
137 \r
138     enqueue[LFDS611_QUEUE_POINTER] = qs->enqueue[LFDS611_QUEUE_POINTER];\r
139     enqueue[LFDS611_QUEUE_COUNTER] = qs->enqueue[LFDS611_QUEUE_COUNTER];\r
140 \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
143 \r
144     /* TRD : confirm that dequeue didn't move between reading it\r
145              and reading its next pointer\r
146     */\r
147 \r
148     LFDS611_BARRIER_LOAD;\r
149 \r
150     if( dequeue[LFDS611_QUEUE_POINTER] == qs->dequeue[LFDS611_QUEUE_POINTER] and dequeue[LFDS611_QUEUE_COUNTER] == qs->dequeue[LFDS611_QUEUE_COUNTER] )\r
151     {\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
154 \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
157 \r
158       if( enqueue[LFDS611_QUEUE_POINTER] != dequeue[LFDS611_QUEUE_POINTER] )\r
159         state = LFDS611_QUEUE_STATE_ATTEMPT_DELFDS611_QUEUE;\r
160 \r
161       switch( state )\r
162       {\r
163         case LFDS611_QUEUE_STATE_EMPTY:\r
164           *user_data = NULL;\r
165           rv = 0;\r
166           finished_flag = RAISED;\r
167         break;\r
168 \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
172         break;\r
173 \r
174         case LFDS611_QUEUE_STATE_ATTEMPT_DELFDS611_QUEUE:\r
175           *user_data = next[LFDS611_QUEUE_POINTER]->user_data;\r
176 \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
179 \r
180           if( cas_result == 1 )\r
181             finished_flag = RAISED;\r
182         break;\r
183       }\r
184     }\r
185   }\r
186   while( finished_flag == LOWERED );\r
187 \r
188   if( cas_result == 1 )\r
189     lfds611_freelist_push( qs->fs, dequeue[LFDS611_QUEUE_POINTER]->fe );\r
190 \r
191   return( rv );\r
192 }\r
193 \r