P99
p99_fifo.h
Go to the documentation of this file.
1 /* This may look like nonsense, but it really is -*- mode: C; coding: utf-8 -*- */
2 /* */
3 /* Except for parts copied from previous work and as explicitly stated below, */
4 /* the author and copyright holder for this work is */
5 /* (C) copyright 2012-2014 Jens Gustedt, INRIA, France */
6 /* */
7 /* This file is free software; it is part of the P99 project. */
8 /* */
9 /* Licensed under the Apache License, Version 2.0 (the "License"); */
10 /* you may not use this file except in compliance with the License. */
11 /* You may obtain a copy of the License at */
12 /* */
13 /* http://www.apache.org/licenses/LICENSE-2.0 */
14 /* */
15 /* Unless required by applicable law or agreed to in writing, software */
16 /* distributed under the License is distributed on an "AS IS" BASIS, */
17 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
18 /* See the License for the specific language governing permissions and */
19 /* limitations under the License. */
20 /* */
21 #ifndef P99_FIFO_H
22 #define P99_FIFO_H 1
23 
24 #include "p99_enum.h"
25 #include "p99_generic.h"
26 
27 /* Additions by C11 */
28 # if __STDC_VERSION__ < 201100L
29 # include "p99_atomic.h"
30 # endif
31 
32 
38 #if defined(P99_DECLARE_ATOMIC) || P00_DOXYGEN
39 # define P99_FIFO(T) P99_PASTE2(p00_fifo_, T)
40 # define P99_FIFO_DECLARE(T) \
41 typedef T P99_PASTE2(p00_fifo_base_, T); \
42 P99_DECLARE_ATOMIC(P99_PASTE2(p00_fifo_base_, T)); \
43  struct P99_PASTE2(p00_fifo_, T) { \
44  _Atomic(P99_PASTE2(p00_fifo_base_, T)) p00_head; \
45  _Atomic(P99_PASTE2(p00_fifo_base_, T)) p00_tail; \
46  }; \
47 typedef struct P99_PASTE2(p00_fifo_, T) P99_PASTE2(p00_fifo_, T)
48 # define P99_FIFO_INITIALIZER(HEAD, TAIL) { \
49  .p00_head = ATOMIC_VAR_INIT(HEAD), \
50  .p00_tail = ATOMIC_VAR_INIT(TAIL), \
51 }
52 
59 P00_DOCUMENT_PERMITTED_ARGUMENT(P99_FIFO_APPEND, 0)
60 P00_DOCUMENT_PERMITTED_ARGUMENT(P99_FIFO_APPEND, 1)
61 #define P99_FIFO_APPEND(L, EL) \
62 do { \
63  /* first evaluate the macro arguments such that there can't be */ \
64  /* name conflicts */ \
65  register const P99_MACRO_VAR(p00_l, (L)); \
66  register const P99_MACRO_VAR(p00_el, (EL)); \
67  register const P99_MACRO_VAR(p00_h, &p00_l->p00_head); \
68  register const P99_MACRO_VAR(p00_t, &p00_l->p00_tail); \
69  p00_el->p99_lifo = 0; \
70  P99_MACRO_VAR(p00_head, atomic_load_explicit(p00_h, memory_order_relaxed)); \
71  for (;;) { \
72  if (p00_head) { \
73  /* spin lock the whole fifo */ \
74  if (atomic_compare_exchange_weak_explicit(p00_h, &p00_head, 0, memory_order_acq_rel, memory_order_relaxed)) { \
75  /* make p00_el the last element */ \
76  atomic_exchange_explicit(p00_t, p00_el, memory_order_acq_rel)->p99_lifo = p00_el; \
77  /* unlock the fifo */ \
78  atomic_store_explicit(p00_h, p00_head, memory_order_release); \
79  break; \
80  } \
81  } else { \
82  P99_MACRO_VAR(p00_tail, atomic_load_explicit(p00_t, memory_order_relaxed)); \
83  if (!p00_tail \
84  && atomic_compare_exchange_weak_explicit(p00_t, &p00_tail, p00_el, memory_order_acq_rel, memory_order_relaxed)) { \
85  /* the fifo was empty, our element is inserted, update the head */ \
86  atomic_store_explicit(p00_h, p00_el, memory_order_release); \
87  break; \
88  } \
89  /* we were in the middle of an update of another thread */ \
90  p00_head = atomic_load_explicit(p00_h, memory_order_consume); \
91  } \
92  } \
93 } while (false)
94 
135 P00_DOCUMENT_PERMITTED_ARGUMENT(P99_FIFO_POP, 0)
136 #define P99_FIFO_POP(L) \
137 p99_extension \
138 ({ \
139  /* first evaluate the macro argument such that there can't be */ \
140  /* a name conflict */ \
141  register const P99_MACRO_VAR(p00_l, (L)); \
142  register const P99_MACRO_VAR(p00_h, &p00_l->p00_head); \
143  register const P99_MACRO_VAR(p00_t, &p00_l->p00_tail); \
144  P99_MACRO_VAR(p00_head, atomic_load_explicit(p00_h, memory_order_relaxed)); \
145  for (;;) { \
146  if (p00_head) { \
147  /* spin lock the whole fifo */ \
148  if (atomic_compare_exchange_weak_explicit(p00_h, &p00_head, 0, memory_order_acq_rel, memory_order_consume)) { \
149  if (p00_head->p99_lifo) \
150  /* there is still another element to come in the fifo, make it \
151  the head */ \
152  atomic_store_explicit(p00_h, p00_head->p99_lifo, memory_order_release); \
153  else \
154  /* this was the last element in the fifo, set the tail to 0, \
155  too */ \
156  atomic_store_explicit(p00_t, 0, memory_order_release); \
157  p00_head->p99_lifo = 0; \
158  break; \
159  } \
160  } else { \
161  register P99_MACRO_VAR(p00_tail, atomic_load_explicit(p00_t, memory_order_consume)); \
162  if (!p00_tail) break; \
163  p00_head = atomic_load_explicit(p00_h, memory_order_relaxed); \
164  } \
165  } \
166  /* make sure that the result can not be used as an lvalue */ \
167  register const __typeof__(p00_head = p00_head) p00_r = p00_head; \
168  p00_r; \
169 })
170 
180 P00_DOCUMENT_PERMITTED_ARGUMENT(P99_FIFO_CLEAR, 0)
181 #define P99_FIFO_CLEAR(L) \
182 p99_extension \
183 ({ \
184  /* first evaluate the macro argument such that there can't be */ \
185  /* a name conflict */ \
186  register const P99_MACRO_VAR(p00_l, (L)); \
187  register const P99_MACRO_VAR(p00_h, &p00_l->p00_head); \
188  register const P99_MACRO_VAR(p00_t, &p00_l->p00_tail); \
189  P99_MACRO_VAR(p00_head, atomic_load_explicit(p00_h, memory_order_relaxed)); \
190  for (;;) { \
191  if (p00_head) { \
192  /* spin lock the whole fifo */ \
193  if (atomic_compare_exchange_weak_explicit(p00_h, &p00_head, 0, memory_order_acq_rel, memory_order_consume)) { \
194  atomic_store_explicit(p00_t, 0, memory_order_release); \
195  break; \
196  } \
197  } else { \
198  register const P99_MACRO_VAR(p00_tail, atomic_load_explicit(p00_t, memory_order_consume)); \
199  if (!p00_tail) break; \
200  p00_head = atomic_load_explicit(p00_h, memory_order_relaxed); \
201  } \
202  } \
203  /* make sure that the result can not be used as an lvalue */ \
204  register const __typeof__(p00_head = p00_head) p00_r = p00_head; \
205  p00_r; \
206 })
207 
208 #else
209 
210 /* A fall back implementation for the case that there are no atomic
211  operations available */
212 
213 # define P99_FIFO(T) P99_PASTE2(p00_fifo_, T)
214 # define P99_FIFO_DECLARE(T) typedef T P99_PASTE2(p00_fifo_, T)[2]
215 # define P99_FIFO_INITIALIZER(HEAD, TAIL) { [0] = (HEAD), [1] = (TAIL) }
216 
217 #define P99_FIFO_APPEND(L, EL) \
218 p99_extension \
219 ({ \
220  P99_MACRO_VAR(p00_l, (L)); \
221  P99_MACRO_VAR(p00_el, (EL)); \
222  p00_el->p99_lifo = (*p00_l)[1]; \
223  (*p00_l)[1] = p00_el; \
224  if (!(*p00_l)[0]) (*p00_l)[0] = p00_el; \
225 })
226 
227 #define P99_FIFO_POP(L) \
228 p99_extension \
229 ({ \
230  P99_MACRO_VAR(p00_l, (L)); \
231  P99_MACRO_VAR(p00_el, (*p00_l)[0]); \
232  (*p00_l)[0] = p00_el->p99_lifo; \
233  if (!(*p00_l)[0]) = (*p00_l)[0] = 0; \
234  if (p00_el) p00_el->p99_lifo = 0; \
235  /* be sure that the result can not be used as an lvalue */ \
236  register const __typeof__(p00_el = p00_el) p00_r = p00_el; \
237  p00_r; \
238 })
239 
240 P00_DOCUMENT_PERMITTED_ARGUMENT(P99_FIFO_CLEAR, 0)
241 #define P99_FIFO_CLEAR(L) \
242 ({ \
243  P99_MACRO_VAR(p00_l, (L)); \
244  register P99_MACRO_VAR(p00_ret, (*p00_l)[0]); \
245  (*p00_l)[0] = 0; \
246  (*p00_l)[1] = 0; \
247  p00_ret; \
248 })
249 
250 #endif
251 
252 P00_DOCUMENT_TYPE_ARGUMENT(P99_FIFO_TABULATE, 0)
253 P00_DOCUMENT_IDENTIFIER_ARGUMENT(P99_FIFO_TABULATE, 1)
254 P00_DOCUMENT_PERMITTED_ARGUMENT(P99_FIFO_TABULATE, 2)
255 #define P99_FIFO_TABULATE(TYPE, TAB, L) P00_FIFO_TABULATE(TYPE, TAB, P99_UNIQ(TAB), L)
256 
257 #define P00_FIFO_TABULATE(TYPE, TAB, ID, L) \
258 size_t P99_PASTE2(ID, _cnt) = 0; \
259 TYPE * P99_PASTE2(ID, _head) = P99_FIFO_CLEAR(L); \
260 for (TYPE * p00_e = P99_PASTE2(ID, _head); \
261  p00_e; \
262  p00_e = p00_e->p99_lifo) \
263  ++P99_PASTE2(ID, _cnt); \
264 TYPE * TAB[P99_PASTE2(ID, _cnt)]; \
265 for (TYPE ** p00_t = &(TAB[0]), \
266  * p00_e = P99_PASTE2(ID, _head); \
267  p00_e; \
268  p00_e = p00_e->p99_lifo, \
269  ++p00_t) \
270  *p00_t = p00_e
271 
276 #endif
P99_FIFO_CLEAR
#define P99_FIFO_CLEAR(L)
Atomically clear an atomic FIFO L and return a pointer to the start of the list that it previously co...
Definition: p99_fifo.h:179
P99_FIFO_POP
#define P99_FIFO_POP(L)
Pop the front element from an atomic FIFO L.
Definition: p99_fifo.h:136
P99_FIFO_APPEND
#define P99_FIFO_APPEND(L, EL)
Append element EL to an atomic FIFO L.
Definition: p99_fifo.h:61
p99_enum.h
p99_atomic.h
P99_FIFO_TABULATE
#define P99_FIFO_TABULATE(TYPE, TAB, L)
Definition: p99_fifo.h:253
p99_generic.h
Generated by   doxygen 1.8.17