summaryrefslogtreecommitdiff
path: root/cesar/lib/slist.h
blob: a773a4cef8839db8ad96ce3bdd953d73ec8dbf9d (plain)
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
#ifndef lib_slist_h
#define lib_slist_h
/* Cesar project {{{
 *
 * Copyright (C) 2009 Spidcom
 *
 * <<<Licence>>>
 *
 * }}} */
/**
 * \file    lib/slist.h
 * \brief   Single linked lists.
 * \ingroup lib
 *
 * Provide a set of macro to help single linked list manipulation.
 *
 * A single linked list is defined as two node pointers (head and tail) and an
 * optional size.  Macros defined in this file can handle several kind of
 * definitions types:
 *
 * Type paste (default):
 *
 * \code
 * struct {
 *   node_t *mylist_head, *mylist_tail;
 * } s;
 * slist_init (s.mylist_);
 * \endcode
 *
 * Type paste_size:
 *
 * \code
 * struct {
 *   node_t *mylist_head, *mylist_tail;
 *   uint mylist_size
 * } s;
 * slist_init (s.mylist_, paste_size);
 * \endcode
 *
 * Type bare:
 *
 * \code
 * struct {
 *   node_t *head, *tail;
 * } s;
 * slist_init (s., bare);
 * \endcode
 *
 * Type bare_size:
 *
 * \code
 * struct {
 *   node_t *head, *tail;
 *   uint size
 * } s;
 * slist_init (s., bare_size);
 * \endcode
 */

/* Internal macros to evaluate type. */
#define SLIST_HEAD(prefix, type) (SLIST_HEAD_ ## type (prefix))
#define SLIST_TAIL(prefix, type) (SLIST_TAIL_ ## type (prefix))
#define SLIST_SIZE(prefix, type) (SLIST_SIZE_ ## type (prefix))
#define SLIST_SIZE_DO(smth, type) SLIST_SIZE_DO_ ## type (smth)

/* Default type is paste. */
#define SLIST_HEAD_ SLIST_HEAD_paste
#define SLIST_TAIL_ SLIST_TAIL_paste
#define SLIST_SIZE_ SLIST_SIZE_paste
#define SLIST_SIZE_DO_ SLIST_SIZE_DO_paste

/* Type paste: append head or tail to prefix, no size. */
#define SLIST_HEAD_paste(prefix) PASTE (prefix, head)
#define SLIST_TAIL_paste(prefix) PASTE (prefix, tail)
#define SLIST_SIZE_paste(prefix) @undef@
#define SLIST_SIZE_DO_paste(smth)

/* Type paste_size: append head, tail or size to prefix. */
#define SLIST_HEAD_paste_size(prefix) PASTE (prefix, head)
#define SLIST_TAIL_paste_size(prefix) PASTE (prefix, tail)
#define SLIST_SIZE_paste_size(prefix) PASTE (prefix, size)
#define SLIST_SIZE_DO_paste_size(smth) smth

/* Type bare: use head or tail with no prefix, no size. */
#define SLIST_HEAD_bare(prefix) prefix head
#define SLIST_TAIL_bare(prefix) prefix tail
#define SLIST_SIZE_bare(prefix) @undef@
#define SLIST_SIZE_DO_bare(smth)

/* Type bare_size: use head, tail or size with no prefix. */
#define SLIST_HEAD_bare_size(prefix) prefix head
#define SLIST_TAIL_bare_size(prefix) prefix tail
#define SLIST_SIZE_bare_size(prefix) prefix size
#define SLIST_SIZE_DO_bare_size(smth) smth

#define SLIST_ASSERT dbg_claim
#define SLIST_ASSERT_PTR dbg_claim_ptr

/**
 * Initialise a single linked list.
 * \param  prefix  list prefix
 * \param  type  optional list type
 */
#define slist_init(prefix, type...) \
    do { \
        SLIST_HEAD (prefix, type) = NULL; \
        dbg_invalid_ptr (SLIST_TAIL (prefix, type)); \
        SLIST_SIZE_DO (SLIST_SIZE (prefix, type) = 0;, type) \
    } while (0)

/**
 * Test whether a list is empty.
 * \param  prefix  list prefix
 * \param  type  optional list type
 * \return  true if empty
 */
#define slist_empty(prefix, type...) \
    (!(SLIST_HEAD (prefix, type)))

/**
 * Push a single element at end of list.
 * \param  prefix  list prefix
 * \param  node  node to push
 * \param  type  optional list type
 */
#define slist_push_back(prefix, node, type...) \
    slist_push_back_range (prefix, node, node, 1, type)

/**
 * Push multiple elements at end of list.
 * \param  prefix  list prefix
 * \param  first  first element to push
 * \param  last  last element to push
 * \param  size  if type includes size, number of element pushed
 * \param  type  optional list type
 */
#define slist_push_back_range(prefix, first, last, size_type...) \
    PASTE_EXPAND (_slist_push_back_range_, PREPROC_NARG (size_type)) \
        (prefix, first, last, ## size_type)

/* As both size and type is optional, here is some trickery: */
#define _slist_push_back_range_0(prefix, first, last) \
    _slist_push_back_range_n (prefix, first, last, @unused@)
#define _slist_push_back_range_1(prefix, first, last, type) \
    _slist_push_back_range_n (prefix, first, last, @unused@, type)
#define _slist_push_back_range_2(prefix, first, last, size, type) \
    _slist_push_back_range_n (prefix, first, last, size, type)

#define _slist_push_back_range_n(prefix, first, last, size, type...) \
    do { \
        if (SLIST_HEAD (prefix, type)) \
        { \
            SLIST_ASSERT_PTR (SLIST_TAIL (prefix, type)); \
            SLIST_SIZE_DO (SLIST_ASSERT (SLIST_SIZE (prefix, type));, type) \
            SLIST_TAIL (prefix, type)->next = (first); \
        } \
        else \
        { \
            SLIST_SIZE_DO (SLIST_ASSERT (!SLIST_SIZE (prefix, type));, type) \
            SLIST_HEAD (prefix, type) = (first); \
        } \
        SLIST_TAIL (prefix, type) = (last); \
        SLIST_SIZE_DO (SLIST_SIZE (prefix, type) += (size);, type) \
    } while (0)

/**
 * Push a single element at begin of list.
 * \param  prefix  list prefix
 * \param  node  node to push
 * \param  type  optional list type
 */
#define slist_push_front(prefix, node, type...) \
    slist_push_front_range (prefix, node, node, 1, type)

/**
 * Push multiple elements at begin of list.
 * \param  prefix  list prefix
 * \param  first  first element to push_front
 * \param  last  last element to push_front
 * \param  size  if type includes size, number of element pushed
 * \param  type  optional list type
 */
#define slist_push_front_range(prefix, first, last, size_type...) \
    PASTE_EXPAND (_slist_push_front_range_, PREPROC_NARG (size_type)) \
        (prefix, first, last, ## size_type)

/* As both size and type is optional, here is some trickery: */
#define _slist_push_front_range_0(prefix, first, last) \
    _slist_push_front_range_n (prefix, first, last, @unused@)
#define _slist_push_front_range_1(prefix, first, last, type) \
    _slist_push_front_range_n (prefix, first, last, @unused@, type)
#define _slist_push_front_range_2(prefix, first, last, size, type) \
    _slist_push_front_range_n (prefix, first, last, size, type)

#define _slist_push_front_range_n(prefix, first, last, size, type...) \
    do { \
        if (SLIST_HEAD (prefix, type)) \
        { \
            SLIST_ASSERT_PTR (SLIST_TAIL (prefix, type)); \
            SLIST_SIZE_DO (SLIST_ASSERT (SLIST_SIZE (prefix, type));, type) \
            (last)->next = SLIST_HEAD (prefix, type); \
        } \
        else \
        { \
            SLIST_SIZE_DO (SLIST_ASSERT (!SLIST_SIZE (prefix, type));, type) \
            SLIST_TAIL (prefix, type) = (last); \
        } \
        SLIST_HEAD (prefix, type) = (first); \
        SLIST_SIZE_DO (SLIST_SIZE (prefix, type) += (size);, type) \
    } while (0)

/**
 * Pop a single element from begin of list.
 * \param  prefix  list prefix
 * \param  type  optional list type
 * \return  popped element
 */
#define slist_pop_front(prefix, type...) \
    ({ \
        typeof (SLIST_HEAD (prefix, type)) popped = \
            SLIST_HEAD (prefix, type); \
        SLIST_ASSERT (popped); \
        SLIST_SIZE_DO (SLIST_ASSERT (SLIST_SIZE (prefix, type));, type) \
        if (popped == SLIST_TAIL (prefix, type)) \
        { \
            SLIST_HEAD (prefix, type) = NULL; \
            dbg_invalid_ptr (SLIST_TAIL (prefix, type)); \
        } \
        else \
        { \
            SLIST_HEAD (prefix, type) = popped->next; \
        } \
        SLIST_SIZE_DO (SLIST_SIZE (prefix, type) -= 1;, type) \
        popped; \
    })

/**
 * Slice a list at given element.
 * \param  prefix  list prefix
 * \param  at  element to slice at
 * \param  size  if type includes size, number of element removed
 * \param  type  optional list type
 *
 * Every elements before given element included will be removed from the list.
 */
#define slist_slice(prefix, at, size_type...) \
    PASTE_EXPAND (_slist_slice_, PREPROC_NARG (size_type)) \
        (prefix, at, ## size_type)

/* As both size and type is optional, here is some trickery: */
#define _slist_slice_0(prefix, at) \
    _slist_slice_n (prefix, at, @unused@)
#define _slist_slice_1(prefix, at, type) \
    _slist_slice_n (prefix, at, @unused@, type)
#define _slist_slice_2(prefix, at, size, type) \
    _slist_slice_n (prefix, at, size, type)

#define _slist_slice_n(prefix, at, size, type...) \
    do { \
        if (SLIST_TAIL (prefix, type) == (at)) \
        { \
            SLIST_SIZE_DO (SLIST_ASSERT (SLIST_SIZE (prefix, type) \
                                         == (size));, type) \
            dbg_invalid_ptr (SLIST_TAIL (prefix, type)); \
            SLIST_HEAD (prefix, type) = NULL; \
        } \
        else \
        { \
            SLIST_SIZE_DO (SLIST_ASSERT (SLIST_SIZE (prefix, type) \
                                         >= (size));, type) \
            SLIST_HEAD (prefix, type) = (at)->next; \
        } \
        SLIST_SIZE_DO (SLIST_SIZE (prefix, type) -= (size);, type) \
    } while (0)

/**
 * Sever a list in the middle.
 * \param  prefix  list prefix
 * \param  after  element to sever after, or NULL for begin of list
 * \param  until  element until which to sever, included
 * \param  size  if type includes size, number of element removed
 * \param  type  optional list type
 *
 * Every elements after first given element excluded and before second given
 * element included will be removed from the list.
 */
#define slist_sever(prefix, after, until, size_type...) \
    PASTE_EXPAND (_slist_sever_, PREPROC_NARG (size_type)) \
        (prefix, after, until, ## size_type)

/* As both size and type is optional, here is some trickery: */
#define _slist_sever_0(prefix, after, until) \
    _slist_sever_n (prefix, after, until, @unused@)
#define _slist_sever_1(prefix, after, until, type) \
    _slist_sever_n (prefix, after, until, @unused@, type)
#define _slist_sever_2(prefix, after, until, size, type) \
    _slist_sever_n (prefix, after, until, size, type)

#define _slist_sever_n(prefix, after, until, size, type...) \
    do { \
        SLIST_SIZE_DO (SLIST_ASSERT (SLIST_SIZE (prefix, type) \
                                     >= (size));, type) \
        if (!after) \
        { \
            if (SLIST_TAIL (prefix, type) == (until)) \
            { \
                dbg_invalid_ptr (SLIST_TAIL (prefix, type)); \
                SLIST_HEAD (prefix, type) = NULL; \
            } \
            else \
            { \
                SLIST_HEAD (prefix, type) = (until)->next; \
            } \
        } \
        else \
        { \
            if (SLIST_TAIL (prefix, type) == (until)) \
            { \
                SLIST_TAIL (prefix, type) = (after); \
            } \
            else \
            { \
                (after)->next = (until)->next; \
            } \
        } \
        SLIST_SIZE_DO (SLIST_SIZE (prefix, type) -= (size);, type) \
    } while (0)

#endif /* lib_slist_h */