p99_lifo.h 8.72 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/* This may look like nonsense, but it really is -*- mode: C -*-              */
/*                                                                            */
/* Except for parts copied from previous work and as explicitly stated below, */
/* the author and copyright holder for this work is                           */
/* (C) copyright  2012 Jens Gustedt, INRIA, France                            */
/*                                                                            */
/* This file is free software; it is part of the P99 project.                 */
/* You can redistribute it and/or modify it under the terms of the QPL as     */
/* given in the file LICENSE. It is distributed without any warranty;         */
/* without even the implied warranty of merchantability or fitness for a      */
/* particular purpose.                                                        */
/*                                                                            */
#ifndef P99_LIFO_H
#define P99_LIFO_H 1

#include "p99_enum.h"
#include "p99_generic.h"

/* Additions by C11 */
# if __STDC_VERSION__ < 201100L
#  include "p99_atomic.h"
# endif


/**
 ** @addtogroup atomic C11 atomic operations
 ** @{
 **/

30
31
#if defined(P99_DECLARE_ATOMIC) || P00_DOXYGEN
# define P99_LIFO(T) _Atomic(P99_PASTE2(p00_lifo_, T))
(no author)'s avatar
(no author) committed
32
33
# define P99_LIFO_DECLARE(T)                                   \
typedef T P99_PASTE2(p00_lifo_, T);                            \
34
P99_DECLARE_ATOMIC(P99_PASTE2(p00_lifo_, T))
Jens Gustedt's avatar
Jens Gustedt committed
35
# define P99_LIFO_INITIALIZER(VAL) ATOMIC_VAR_INIT((void*)VAL)
36

37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/**
 ** @brief Return a pointer to the top element of an atomic LIFO @a L
 ** @see P99_LIFO_CLEAR
 ** @see P99_LIFO_POP
 ** @see P99_LIFO_PUSH
 **/
P00_DOCUMENT_PERMITTED_ARGUMENT(P99_LIFO_TOP, 0)
#define P99_LIFO_TOP(L)  atomic_load(L)

/**
 ** @brief Push element @a EL into an atomic LIFO @a L
 ** @see P99_LIFO_CLEAR
 ** @see P99_LIFO_POP
 ** @see P99_LIFO_TOP
 **/
P00_DOCUMENT_PERMITTED_ARGUMENT(P99_LIFO_PUSH, 0)
P00_DOCUMENT_PERMITTED_ARGUMENT(P99_LIFO_PUSH, 1)
54
55
56
57
58
59
60
61
62
63
#define P99_LIFO_PUSH(L, EL)                                         \
p99_extension                                                        \
({                                                                   \
  P99_MACRO_VAR(p00_l, (L));                                         \
  P99_MACRO_VAR(p00_el, (EL));                                       \
  P99_MACRO_VAR(p00_prev, atomic_load(p00_l));                       \
  do {                                                               \
    p00_el->p99_lifo = p00_prev;                                     \
  } while (!atomic_compare_exchange_weak(p00_l, &p00_prev, p00_el)); \
})
64
65
66
67
68
69
70
71
72
73
74
75

/**
 ** @brief Pop the top element from an atomic LIFO @a L
 **
 ** This implements a generic interface to an atomic LIFO (Last In -
 ** First Out) data structure. To use it you just have do some
 ** preparatory declarations and add a @c p99_lifo field to your data
 ** structure:
 **
 ** @code
 ** P99_DECLARE_STRUCT(myData);
 ** P99_POINTER_TYPE(myData);
76
 ** P99_FIFO_DECLARE(myData_ptr);
77
78
79
80
81
82
 **
 ** struct myData {
 **   ...
 **   myData_ptr p99_lifo;
 **   ...
 ** };
83
 ** extern P99_LIFO(myData_ptr) head;
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
 ** @endcode
 **
 ** Now @c head can be used as the head of a LIFO:
 **
 ** @code
 ** myData_ptr el = P99_NEW(myData, \/\* your initializer arguments \*\/);
 ** P99_LIFO_PUSH(&head, el);
 ** ...
 ** for (myData_ptr el = P99_LIFO_POP(&head);
 **      el;
 **      el = P99_LIFO_POP(&head)) {
 **        // do something with el and then
 **        free(el);
 ** }
 ** @endcode
 **
 ** @see P99_LIFO_CLEAR
101
102
 ** @see P99_LIFO
 ** @see P99_LIFO_DECLARE
103
104
105
 ** @see P99_LIFO_PUSH
 **/
P00_DOCUMENT_PERMITTED_ARGUMENT(P99_LIFO_POP, 0)
106
107
108
109
110
111
112
113
114
115
116
#define P99_LIFO_POP(L)                                                                      \
p99_extension                                                                                \
({                                                                                           \
  P99_MACRO_VAR(p00_l, (L));                                                                 \
  P99_MACRO_VAR(p00_el, P99_LIFO_TOP(p00_l));                                                \
  while (p00_el && !atomic_compare_exchange_weak(p00_l, &p00_el, p00_el->p99_lifo)) P99_NOP; \
  if (p00_el) p00_el->p99_lifo = 0;                                                          \
  /* be sure that the result can not be used as an lvalue */                                 \
  register __typeof__(p00_el = p00_el) p00_r = p00_el;                                       \
  p00_r;                                                                                     \
})
117

(no author)'s avatar
(no author) committed
118
119
120
121
122
123
124
125
126
127
128
129
130
#define P00_LIFO_REVERT(L)                                     \
p99_extension                                                  \
({                                                             \
  register P99_MACRO_VAR(p00_h, (L));                          \
  register P99_MACRO_VAR(p00_t, P99_PROMOTE_0(p00_h));         \
  while (p00_h) {                                              \
    register P99_MACRO_VAR(p00_n, p00_h->p99_lifo);            \
    p00_h->p99_lifo = p00_t;                                   \
    p00_h = p00_n;                                             \
  }                                                            \
  /* make sure that the result can not be used as an lvalue */ \
  register const __typeof__(p00_t = p00_t) p00_r = p00_t;      \
  p00_r;                                                       \
Jens Gustedt's avatar
Jens Gustedt committed
131
132
})

133
134
135
136
/**
 ** @brief Atomically clear an atomic LIFO @a L and return a pointer
 ** to the start of the list that it previously contained
 **
137
138
 ** @see P99_LIFO
 ** @see P99_LIFO_DECLARE
139
140
141
142
143
144
 ** @see P99_LIFO_PUSH
 ** @see P99_LIFO_TOP
 **/
P00_DOCUMENT_PERMITTED_ARGUMENT(P99_LIFO_CLEAR, 0)
#define P99_LIFO_CLEAR(L) atomic_exchange(L, 0)

145
146
147
148
149
150
151
#else

/* A fall back implementation for the case that there are no atomic
   operations available */

# define P99_LIFO(T) P99_PASTE2(p00_lifo_, T)
# define P99_LIFO_DECLARE(T) typedef T P99_LIFO(T)
Jens Gustedt's avatar
Jens Gustedt committed
152
# define P99_LIFO_INITIALIZER(VAL) ((void*)VAL)
153
154
155

#define P99_LIFO_TOP(L)  (*(L))

(no author)'s avatar
(no author) committed
156
157
158
159
160
161
162
#define P99_LIFO_PUSH(L, EL)                                   \
p99_extension                                                  \
({                                                             \
  P99_MACRO_VAR(p00_l, (L));                                   \
  P99_MACRO_VAR(p00_el, (EL));                                 \
  p00_el->p99_lifo = *p00_l;                                   \
  *p00_l = p00_el;                                             \
163
164
})

(no author)'s avatar
(no author) committed
165
166
167
168
169
170
171
172
173
174
#define P99_LIFO_POP(L)                                        \
p99_extension                                                  \
({                                                             \
  P99_MACRO_VAR(p00_l, (L));                                   \
  P99_MACRO_VAR(p00_el, *p00_l);                               \
  *p00_l = p00_el->p99_lifo;                                   \
  if (p00_el) p00_el->p99_lifo = 0;                            \
  /* be sure that the result can not be used as an lvalue */   \
  register __typeof__(p00_el = p00_el) p00_r = p00_el;         \
  p00_r;                                                       \
175
176
177
178
179
180
181
182
183
184
185
})

/**
 ** @brief Atomically clear an atomic LIFO @a L and return a pointer
 ** to the start of the list that it previously contained
 **
 ** @see P99_LIFO_POP
 ** @see P99_LIFO_PUSH
 ** @see P99_LIFO_TOP
 **/
P00_DOCUMENT_PERMITTED_ARGUMENT(P99_LIFO_CLEAR, 0)
(no author)'s avatar
(no author) committed
186
187
188
189
190
191
#define P99_LIFO_CLEAR(L)                                      \
({                                                             \
  P99_MACRO_VAR(p00_l, (L));                                   \
  register P99_MACRO_VAR(p00_ret, *p00_l);                     \
  *p00_l = 0;                                                  \
  p00_ret;                                                     \
192
193
194
195
})

#endif

196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
P00_DOCUMENT_TYPE_ARGUMENT(P99_LIFO_TABULATE, 0)
P00_DOCUMENT_IDENTIFIER_ARGUMENT(P99_LIFO_TABULATE, 1)
P00_DOCUMENT_PERMITTED_ARGUMENT(P99_LIFO_TABULATE, 2)
#define P99_LIFO_TABULATE(TYPE, TAB, L)                        \
size_t P99_FILEID(TAB, _cnt) = 0;                              \
TYPE * P99_FILEID(TAB, _head) = P99_LIFO_CLEAR(L);             \
for (TYPE * p00_e = P99_FILEID(TAB, _head);                    \
     p00_e;                                                    \
     p00_e = p00_e->p99_lifo)                                  \
  ++P99_FILEID(TAB, _cnt);                                     \
TYPE * TAB[P99_FILEID(TAB, _cnt)];                             \
for (TYPE ** p00_t = &(TAB[0]),                                \
       * p00_e = P99_FILEID(TAB, _head);                       \
     p00_e;                                                    \
     p00_e = p00_e->p99_lifo,                                  \
       ++p00_t)                                                \
  *p00_t = p00_e

/**
 ** @}
 **/

#endif