p99_lifo.h 10.4 KB
Newer Older
1 2 3 4
/* 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                           */
Jens Gustedt's avatar
Jens Gustedt committed
5
/* (C) copyright  2012-2013 Jens Gustedt, INRIA, France                       */
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 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
#if defined(P99_DECLARE_ATOMIC) || P00_DOXYGEN
31

32
#include "p99_tp.h"
33

34
# define P99_LIFO(T) P99_PASTE2(p00_lifo_, T)
Jens Gustedt's avatar
Jens Gustedt committed
35 36
# define P99_LIFO_DECLARE(T)                                      \
typedef struct P99_PASTE2(p00_lifo_, T) P99_PASTE2(p00_lifo_, T); \
37
_Alignas(sizeof(p00_tp_state)) struct P99_PASTE2(p00_lifo_, T) {   \
Jens Gustedt's avatar
Jens Gustedt committed
38 39
  p99_tp p00_tp;                                                  \
  T p00_dum; /* we only need this for its type */                 \
40 41
}

Jens Gustedt's avatar
Jens Gustedt committed
42 43
# define P99_LIFO_INITIALIZER(VAL) {                           \
    .p00_tp = P99_TP_INITIALIZER((uintptr_t)(void*)VAL),       \
44 45
}

46 47 48 49 50 51 52
/**
 ** @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)
Jens Gustedt's avatar
Jens Gustedt committed
53 54 55 56
#define P99_LIFO_TOP(L)                                                         \
({                                                                              \
  register const P99_MACRO_VAR(p00_l, (L));                                     \
  /* be sure that the result can not be used as an lvalue */                    \
57
  register const __typeof__(p00_l->p00_dum) p00_r = p99_tp_get(&p00_l->p00_tp); \
Jens Gustedt's avatar
Jens Gustedt committed
58
  p00_r;                                                                        \
59 60
 })

61 62 63 64 65 66 67 68 69

/**
 ** @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)
Jens Gustedt's avatar
Jens Gustedt committed
70 71 72 73 74
#define P99_LIFO_PUSH(L, EL)                                           \
p99_extension                                                          \
({                                                                     \
  register const P99_MACRO_VAR(p00_l, (L));                            \
  register __typeof__(p00_l->p00_dum) p00_rr = (EL);                   \
75
  p99_tp_state p00_state = p99_tp_state_initializer(&(p00_l)->p00_tp, p00_rr); \
Jens Gustedt's avatar
Jens Gustedt committed
76 77 78
  do {                                                                 \
    p00_rr->p99_lifo = p99_tp_state_get(&p00_state);                   \
  } while (!p99_tp_state_commit(&p00_state));                          \
79
})
80 81 82 83 84 85 86 87 88 89 90 91

/**
 ** @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);
92
 ** P99_FIFO_DECLARE(myData_ptr);
93 94 95 96 97 98
 **
 ** struct myData {
 **   ...
 **   myData_ptr p99_lifo;
 **   ...
 ** };
99
 ** extern P99_LIFO(myData_ptr) head;
100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116
 ** @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
117 118
 ** @see P99_LIFO
 ** @see P99_LIFO_DECLARE
119 120 121
 ** @see P99_LIFO_PUSH
 **/
P00_DOCUMENT_PERMITTED_ARGUMENT(P99_LIFO_POP, 0)
Jens Gustedt's avatar
Jens Gustedt committed
122 123 124 125
#define P99_LIFO_POP(L)                                                     \
p99_extension                                                               \
({                                                                          \
  register const P99_MACRO_VAR(p00_l, (L));                                 \
126
  p99_tp_state p00_state = p99_tp_state_initializer(&(p00_l)->p00_tp, 0);   \
Jens Gustedt's avatar
Jens Gustedt committed
127 128 129 130 131 132 133 134 135
  /* be sure that the result can not be used as an lvalue */                \
  register __typeof__(p00_l->p00_dum) p00_r = p99_tp_state_get(&p00_state); \
  for (; p00_r; p00_r = p99_tp_state_get(&p00_state)) {                     \
    p99_tp_state_set(&p00_state, p00_r->p99_lifo);                          \
    if (p99_tp_state_commit(&p00_state))                                    \
      break;                                                                \
  }                                                                         \
  if (p00_r) p00_r->p99_lifo = 0;                                           \
  p00_r;                                                                    \
136
})
137

(no author)'s avatar
(no author) committed
138 139 140 141 142 143 144 145 146 147 148 149 150
#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
151 152
})

153 154 155 156
/**
 ** @brief Atomically clear an atomic LIFO @a L and return a pointer
 ** to the start of the list that it previously contained
 **
157 158
 ** @see P99_LIFO
 ** @see P99_LIFO_DECLARE
159 160 161 162
 ** @see P99_LIFO_PUSH
 ** @see P99_LIFO_TOP
 **/
P00_DOCUMENT_PERMITTED_ARGUMENT(P99_LIFO_CLEAR, 0)
Jens Gustedt's avatar
Jens Gustedt committed
163 164 165 166
#define P99_LIFO_CLEAR(L)                                                   \
p99_extension                                                               \
({                                                                          \
  register const P99_MACRO_VAR(p00_l, (L));                                 \
167
  p99_tp_state p00_state = p99_tp_state_initializer(&(p00_l)->p00_tp, 0);   \
Jens Gustedt's avatar
Jens Gustedt committed
168
  /* be sure that the result can not be used as an lvalue */                \
169
  register __typeof__(p00_l->p00_dum) p00_r = p99_tp_state_get(&p00_state); \
Jens Gustedt's avatar
Jens Gustedt committed
170 171 172 173 174
  for (; p00_r; p00_r = p99_tp_state_get(&p00_state)) {                     \
    if (p99_tp_state_commit(&p00_state))                                    \
      break;                                                                \
  }                                                                         \
  p00_r;                                                                    \
175
})
176

177 178 179 180 181 182 183
#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
184
# define P99_LIFO_INITIALIZER(VAL) ((void*)VAL)
185 186 187

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

(no author)'s avatar
(no author) committed
188 189 190 191 192 193 194
#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;                                             \
195 196
})

(no author)'s avatar
(no author) committed
197 198 199 200 201 202 203 204 205 206
#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;                                                       \
207 208 209 210 211 212 213 214 215 216 217
})

/**
 ** @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
218 219 220 221 222 223
#define P99_LIFO_CLEAR(L)                                      \
({                                                             \
  P99_MACRO_VAR(p00_l, (L));                                   \
  register P99_MACRO_VAR(p00_ret, *p00_l);                     \
  *p00_l = 0;                                                  \
  p00_ret;                                                     \
224 225 226 227
})

#endif

228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250
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