libsignal-protocol-c
master
utlist.h
1
/*
2
Copyright (c) 2007-2016, Troy D. Hanson http://troydhanson.github.com/uthash/
3
All rights reserved.
4
5
Redistribution and use in source and binary forms, with or without
6
modification, are permitted provided that the following conditions are met:
7
8
* Redistributions of source code must retain the above copyright
9
notice, this list of conditions and the following disclaimer.
10
11
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
12
IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
13
TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
14
PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
15
OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
16
EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
17
PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
18
PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
19
LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
20
NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
21
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
22
*/
23
24
#ifndef UTLIST_H
25
#define UTLIST_H
26
27
#define UTLIST_VERSION 2.0.1
28
29
#include <assert.h>
30
31
/*
32
* This file contains macros to manipulate singly and doubly-linked lists.
33
*
34
* 1. LL_ macros: singly-linked lists.
35
* 2. DL_ macros: doubly-linked lists.
36
* 3. CDL_ macros: circular doubly-linked lists.
37
*
38
* To use singly-linked lists, your structure must have a "next" pointer.
39
* To use doubly-linked lists, your structure must "prev" and "next" pointers.
40
* Either way, the pointer to the head of the list must be initialized to NULL.
41
*
42
* ----------------.EXAMPLE -------------------------
43
* struct item {
44
* int id;
45
* struct item *prev, *next;
46
* }
47
*
48
* struct item *list = NULL:
49
*
50
* int main() {
51
* struct item *item;
52
* ... allocate and populate item ...
53
* DL_APPEND(list, item);
54
* }
55
* --------------------------------------------------
56
*
57
* For doubly-linked lists, the append and delete macros are O(1)
58
* For singly-linked lists, append and delete are O(n) but prepend is O(1)
59
* The sort macro is O(n log(n)) for all types of single/double/circular lists.
60
*/
61
62
/* These macros use decltype or the earlier __typeof GNU extension.
63
As decltype is only available in newer compilers (VS2010 or gcc 4.3+
64
when compiling c++ code), this code uses whatever method is needed
65
or, for VS2008 where neither is available, uses casting workarounds. */
66
#ifdef _MSC_VER
/* MS compiler */
67
#if _MSC_VER >= 1600 && defined(__cplusplus)
/* VS2010 or newer in C++ mode */
68
#define LDECLTYPE(x) decltype(x)
69
#else
/* VS2008 or older (or VS2010 in C mode) */
70
#define NO_DECLTYPE
71
#endif
72
#elif defined(__ICCARM__)
73
#define NO_DECLTYPE
74
#else
/* GNU, Sun and other compilers */
75
#define LDECLTYPE(x) __typeof(x)
76
#endif
77
78
/* for VS2008 we use some workarounds to get around the lack of decltype,
79
* namely, we always reassign our tmp variable to the list head if we need
80
* to dereference its prev/next pointers, and save/restore the real head.*/
81
#ifdef NO_DECLTYPE
82
#define IF_NO_DECLTYPE(x) x
83
#define LDECLTYPE(x) char*
84
#define _SV(elt,list) _tmp = (char*)(list); {char **_alias = (char**)&(list); *_alias = (elt); }
85
#define _NEXT(elt,list,next) ((char*)((list)->next))
86
#define _NEXTASGN(elt,list,to,next) { char **_alias = (char**)&((list)->next); *_alias=(char*)(to); }
87
/* #define _PREV(elt,list,prev) ((char*)((list)->prev)) */
88
#define _PREVASGN(elt,list,to,prev) { char **_alias = (char**)&((list)->prev); *_alias=(char*)(to); }
89
#define _RS(list) { char **_alias = (char**)&(list); *_alias=_tmp; }
90
#define _CASTASGN(a,b) { char **_alias = (char**)&(a); *_alias=(char*)(b); }
91
#else
92
#define IF_NO_DECLTYPE(x)
93
#define _SV(elt,list)
94
#define _NEXT(elt,list,next) ((elt)->next)
95
#define _NEXTASGN(elt,list,to,next) ((elt)->next)=(to)
96
/* #define _PREV(elt,list,prev) ((elt)->prev) */
97
#define _PREVASGN(elt,list,to,prev) ((elt)->prev)=(to)
98
#define _RS(list)
99
#define _CASTASGN(a,b) (a)=(b)
100
#endif
101
102
/******************************************************************************
103
* The sort macro is an adaptation of Simon Tatham's O(n log(n)) mergesort *
104
* Unwieldy variable names used here to avoid shadowing passed-in variables. *
105
*****************************************************************************/
106
#define LL_SORT(list, cmp) \
107
LL_SORT2(list, cmp, next)
108
109
#define LL_SORT2(list, cmp, next) \
110
do { \
111
LDECLTYPE(list) _ls_p; \
112
LDECLTYPE(list) _ls_q; \
113
LDECLTYPE(list) _ls_e; \
114
LDECLTYPE(list) _ls_tail; \
115
IF_NO_DECLTYPE(LDECLTYPE(list) _tmp;) \
116
int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
117
if (list) { \
118
_ls_insize = 1; \
119
_ls_looping = 1; \
120
while (_ls_looping) { \
121
_CASTASGN(_ls_p,list); \
122
(list) = NULL; \
123
_ls_tail = NULL; \
124
_ls_nmerges = 0; \
125
while (_ls_p) { \
126
_ls_nmerges++; \
127
_ls_q = _ls_p; \
128
_ls_psize = 0; \
129
for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
130
_ls_psize++; \
131
_SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list,next); _RS(list); \
132
if (!_ls_q) break; \
133
} \
134
_ls_qsize = _ls_insize; \
135
while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \
136
if (_ls_psize == 0) { \
137
_ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
138
_NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
139
} else if (_ls_qsize == 0 || !_ls_q) { \
140
_ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
141
_NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
142
} else if (cmp(_ls_p,_ls_q) <= 0) { \
143
_ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
144
_NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
145
} else { \
146
_ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
147
_NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
148
} \
149
if (_ls_tail) { \
150
_SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \
151
} else { \
152
_CASTASGN(list,_ls_e); \
153
} \
154
_ls_tail = _ls_e; \
155
} \
156
_ls_p = _ls_q; \
157
} \
158
if (_ls_tail) { \
159
_SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL,next); _RS(list); \
160
} \
161
if (_ls_nmerges <= 1) { \
162
_ls_looping=0; \
163
} \
164
_ls_insize *= 2; \
165
} \
166
} \
167
} while (0)
168
169
170
#define DL_SORT(list, cmp) \
171
DL_SORT2(list, cmp, prev, next)
172
173
#define DL_SORT2(list, cmp, prev, next) \
174
do { \
175
LDECLTYPE(list) _ls_p; \
176
LDECLTYPE(list) _ls_q; \
177
LDECLTYPE(list) _ls_e; \
178
LDECLTYPE(list) _ls_tail; \
179
IF_NO_DECLTYPE(LDECLTYPE(list) _tmp;) \
180
int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
181
if (list) { \
182
_ls_insize = 1; \
183
_ls_looping = 1; \
184
while (_ls_looping) { \
185
_CASTASGN(_ls_p,list); \
186
(list) = NULL; \
187
_ls_tail = NULL; \
188
_ls_nmerges = 0; \
189
while (_ls_p) { \
190
_ls_nmerges++; \
191
_ls_q = _ls_p; \
192
_ls_psize = 0; \
193
for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
194
_ls_psize++; \
195
_SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list,next); _RS(list); \
196
if (!_ls_q) break; \
197
} \
198
_ls_qsize = _ls_insize; \
199
while ((_ls_psize > 0) || ((_ls_qsize > 0) && _ls_q)) { \
200
if (_ls_psize == 0) { \
201
_ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
202
_NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
203
} else if ((_ls_qsize == 0) || (!_ls_q)) { \
204
_ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
205
_NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
206
} else if (cmp(_ls_p,_ls_q) <= 0) { \
207
_ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
208
_NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
209
} else { \
210
_ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
211
_NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
212
} \
213
if (_ls_tail) { \
214
_SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \
215
} else { \
216
_CASTASGN(list,_ls_e); \
217
} \
218
_SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail,prev); _RS(list); \
219
_ls_tail = _ls_e; \
220
} \
221
_ls_p = _ls_q; \
222
} \
223
_CASTASGN((list)->prev, _ls_tail); \
224
_SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL,next); _RS(list); \
225
if (_ls_nmerges <= 1) { \
226
_ls_looping=0; \
227
} \
228
_ls_insize *= 2; \
229
} \
230
} \
231
} while (0)
232
233
#define CDL_SORT(list, cmp) \
234
CDL_SORT2(list, cmp, prev, next)
235
236
#define CDL_SORT2(list, cmp, prev, next) \
237
do { \
238
LDECLTYPE(list) _ls_p; \
239
LDECLTYPE(list) _ls_q; \
240
LDECLTYPE(list) _ls_e; \
241
LDECLTYPE(list) _ls_tail; \
242
LDECLTYPE(list) _ls_oldhead; \
243
LDECLTYPE(list) _tmp; \
244
int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
245
if (list) { \
246
_ls_insize = 1; \
247
_ls_looping = 1; \
248
while (_ls_looping) { \
249
_CASTASGN(_ls_p,list); \
250
_CASTASGN(_ls_oldhead,list); \
251
(list) = NULL; \
252
_ls_tail = NULL; \
253
_ls_nmerges = 0; \
254
while (_ls_p) { \
255
_ls_nmerges++; \
256
_ls_q = _ls_p; \
257
_ls_psize = 0; \
258
for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
259
_ls_psize++; \
260
_SV(_ls_q,list); \
261
if (_NEXT(_ls_q,list,next) == _ls_oldhead) { \
262
_ls_q = NULL; \
263
} else { \
264
_ls_q = _NEXT(_ls_q,list,next); \
265
} \
266
_RS(list); \
267
if (!_ls_q) break; \
268
} \
269
_ls_qsize = _ls_insize; \
270
while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \
271
if (_ls_psize == 0) { \
272
_ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
273
_NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
274
if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \
275
} else if (_ls_qsize == 0 || !_ls_q) { \
276
_ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
277
_NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
278
if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \
279
} else if (cmp(_ls_p,_ls_q) <= 0) { \
280
_ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \
281
_NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \
282
if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \
283
} else { \
284
_ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \
285
_NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \
286
if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \
287
} \
288
if (_ls_tail) { \
289
_SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \
290
} else { \
291
_CASTASGN(list,_ls_e); \
292
} \
293
_SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail,prev); _RS(list); \
294
_ls_tail = _ls_e; \
295
} \
296
_ls_p = _ls_q; \
297
} \
298
_CASTASGN((list)->prev,_ls_tail); \
299
_CASTASGN(_tmp,list); \
300
_SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_tmp,next); _RS(list); \
301
if (_ls_nmerges <= 1) { \
302
_ls_looping=0; \
303
} \
304
_ls_insize *= 2; \
305
} \
306
} \
307
} while (0)
308
309
/******************************************************************************
310
* singly linked list macros (non-circular) *
311
*****************************************************************************/
312
#define LL_PREPEND(head,add) \
313
LL_PREPEND2(head,add,next)
314
315
#define LL_PREPEND2(head,add,next) \
316
do { \
317
(add)->next = (head); \
318
(head) = (add); \
319
} while (0)
320
321
#define LL_CONCAT(head1,head2) \
322
LL_CONCAT2(head1,head2,next)
323
324
#define LL_CONCAT2(head1,head2,next) \
325
do { \
326
LDECLTYPE(head1) _tmp; \
327
if (head1) { \
328
_tmp = (head1); \
329
while (_tmp->next) { _tmp = _tmp->next; } \
330
_tmp->next=(head2); \
331
} else { \
332
(head1)=(head2); \
333
} \
334
} while (0)
335
336
#define LL_APPEND(head,add) \
337
LL_APPEND2(head,add,next)
338
339
#define LL_APPEND2(head,add,next) \
340
do { \
341
LDECLTYPE(head) _tmp; \
342
(add)->next=NULL; \
343
if (head) { \
344
_tmp = (head); \
345
while (_tmp->next) { _tmp = _tmp->next; } \
346
_tmp->next=(add); \
347
} else { \
348
(head)=(add); \
349
} \
350
} while (0)
351
352
#define LL_DELETE(head,del) \
353
LL_DELETE2(head,del,next)
354
355
#define LL_DELETE2(head,del,next) \
356
do { \
357
LDECLTYPE(head) _tmp; \
358
if ((head) == (del)) { \
359
(head)=(head)->next; \
360
} else { \
361
_tmp = (head); \
362
while (_tmp->next && (_tmp->next != (del))) { \
363
_tmp = _tmp->next; \
364
} \
365
if (_tmp->next) { \
366
_tmp->next = (del)->next; \
367
} \
368
} \
369
} while (0)
370
371
#define LL_COUNT(head,el,counter) \
372
LL_COUNT2(head,el,counter,next) \
373
374
#define LL_COUNT2(head,el,counter,next) \
375
do { \
376
(counter) = 0; \
377
LL_FOREACH2(head,el,next) { ++(counter); } \
378
} while (0)
379
380
#define LL_FOREACH(head,el) \
381
LL_FOREACH2(head,el,next)
382
383
#define LL_FOREACH2(head,el,next) \
384
for ((el) = (head); el; (el) = (el)->next)
385
386
#define LL_FOREACH_SAFE(head,el,tmp) \
387
LL_FOREACH_SAFE2(head,el,tmp,next)
388
389
#define LL_FOREACH_SAFE2(head,el,tmp,next) \
390
for ((el) = (head); (el) && ((tmp) = (el)->next, 1); (el) = (tmp))
391
392
#define LL_SEARCH_SCALAR(head,out,field,val) \
393
LL_SEARCH_SCALAR2(head,out,field,val,next)
394
395
#define LL_SEARCH_SCALAR2(head,out,field,val,next) \
396
do { \
397
LL_FOREACH2(head,out,next) { \
398
if ((out)->field == (val)) break; \
399
} \
400
} while (0)
401
402
#define LL_SEARCH(head,out,elt,cmp) \
403
LL_SEARCH2(head,out,elt,cmp,next)
404
405
#define LL_SEARCH2(head,out,elt,cmp,next) \
406
do { \
407
LL_FOREACH2(head,out,next) { \
408
if ((cmp(out,elt))==0) break; \
409
} \
410
} while (0)
411
412
#define LL_REPLACE_ELEM2(head, el, add, next) \
413
do { \
414
LDECLTYPE(head) _tmp; \
415
assert((head) != NULL); \
416
assert((el) != NULL); \
417
assert((add) != NULL); \
418
(add)->next = (el)->next; \
419
if ((head) == (el)) { \
420
(head) = (add); \
421
} else { \
422
_tmp = (head); \
423
while (_tmp->next && (_tmp->next != (el))) { \
424
_tmp = _tmp->next; \
425
} \
426
if (_tmp->next) { \
427
_tmp->next = (add); \
428
} \
429
} \
430
} while (0)
431
432
#define LL_REPLACE_ELEM(head, el, add) \
433
LL_REPLACE_ELEM2(head, el, add, next)
434
435
#define LL_PREPEND_ELEM2(head, el, add, next) \
436
do { \
437
if (el) { \
438
LDECLTYPE(head) _tmp; \
439
assert((head) != NULL); \
440
assert((add) != NULL); \
441
(add)->next = (el); \
442
if ((head) == (el)) { \
443
(head) = (add); \
444
} else { \
445
_tmp = (head); \
446
while (_tmp->next && (_tmp->next != (el))) { \
447
_tmp = _tmp->next; \
448
} \
449
if (_tmp->next) { \
450
_tmp->next = (add); \
451
} \
452
} \
453
} else { \
454
LL_APPEND2(head, add, next); \
455
} \
456
} while (0) \
457
458
#define LL_PREPEND_ELEM(head, el, add) \
459
LL_PREPEND_ELEM2(head, el, add, next)
460
461
#define LL_APPEND_ELEM2(head, el, add, next) \
462
do { \
463
if (el) { \
464
assert((head) != NULL); \
465
assert((add) != NULL); \
466
(add)->next = (el)->next; \
467
(el)->next = (add); \
468
} else { \
469
LL_PREPEND2(head, add, next); \
470
} \
471
} while (0) \
472
473
#define LL_APPEND_ELEM(head, el, add) \
474
LL_APPEND_ELEM2(head, el, add, next)
475
476
#ifdef NO_DECLTYPE
477
/* Here are VS2008 / NO_DECLTYPE replacements for a few functions */
478
479
#undef LL_CONCAT2
480
#define LL_CONCAT2(head1,head2,next) \
481
do { \
482
char *_tmp; \
483
if (head1) { \
484
_tmp = (char*)(head1); \
485
while ((head1)->next) { (head1) = (head1)->next; } \
486
(head1)->next = (head2); \
487
_RS(head1); \
488
} else { \
489
(head1)=(head2); \
490
} \
491
} while (0)
492
493
#undef LL_APPEND2
494
#define LL_APPEND2(head,add,next) \
495
do { \
496
if (head) { \
497
(add)->next = head;
/* use add->next as a temp variable */
\
498
while ((add)->next->next) { (add)->next = (add)->next->next; } \
499
(add)->next->next=(add); \
500
} else { \
501
(head)=(add); \
502
} \
503
(add)->next=NULL; \
504
} while (0)
505
506
#undef LL_DELETE2
507
#define LL_DELETE2(head,del,next) \
508
do { \
509
if ((head) == (del)) { \
510
(head)=(head)->next; \
511
} else { \
512
char *_tmp = (char*)(head); \
513
while ((head)->next && ((head)->next != (del))) { \
514
(head) = (head)->next; \
515
} \
516
if ((head)->next) { \
517
(head)->next = ((del)->next); \
518
} \
519
_RS(head); \
520
} \
521
} while (0)
522
523
#undef LL_REPLACE_ELEM2
524
#define LL_REPLACE_ELEM2(head, el, add, next) \
525
do { \
526
assert((head) != NULL); \
527
assert((el) != NULL); \
528
assert((add) != NULL); \
529
if ((head) == (el)) { \
530
(head) = (add); \
531
} else { \
532
(add)->next = head; \
533
while ((add)->next->next && ((add)->next->next != (el))) { \
534
(add)->next = (add)->next->next; \
535
} \
536
if ((add)->next->next) { \
537
(add)->next->next = (add); \
538
} \
539
} \
540
(add)->next = (el)->next; \
541
} while (0)
542
543
#undef LL_PREPEND_ELEM2
544
#define LL_PREPEND_ELEM2(head, el, add, next) \
545
do { \
546
if (el) { \
547
assert((head) != NULL); \
548
assert((add) != NULL); \
549
if ((head) == (el)) { \
550
(head) = (add); \
551
} else { \
552
(add)->next = (head); \
553
while ((add)->next->next && ((add)->next->next != (el))) { \
554
(add)->next = (add)->next->next; \
555
} \
556
if ((add)->next->next) { \
557
(add)->next->next = (add); \
558
} \
559
} \
560
(add)->next = (el); \
561
} else { \
562
LL_APPEND2(head, add, next); \
563
} \
564
} while (0) \
565
566
#endif
/* NO_DECLTYPE */
567
568
/******************************************************************************
569
* doubly linked list macros (non-circular) *
570
*****************************************************************************/
571
#define DL_PREPEND(head,add) \
572
DL_PREPEND2(head,add,prev,next)
573
574
#define DL_PREPEND2(head,add,prev,next) \
575
do { \
576
(add)->next = (head); \
577
if (head) { \
578
(add)->prev = (head)->prev; \
579
(head)->prev = (add); \
580
} else { \
581
(add)->prev = (add); \
582
} \
583
(head) = (add); \
584
} while (0)
585
586
#define DL_APPEND(head,add) \
587
DL_APPEND2(head,add,prev,next)
588
589
#define DL_APPEND2(head,add,prev,next) \
590
do { \
591
if (head) { \
592
(add)->prev = (head)->prev; \
593
(head)->prev->next = (add); \
594
(head)->prev = (add); \
595
(add)->next = NULL; \
596
} else { \
597
(head)=(add); \
598
(head)->prev = (head); \
599
(head)->next = NULL; \
600
} \
601
} while (0)
602
603
#define DL_CONCAT(head1,head2) \
604
DL_CONCAT2(head1,head2,prev,next)
605
606
#define DL_CONCAT2(head1,head2,prev,next) \
607
do { \
608
LDECLTYPE(head1) _tmp; \
609
if (head2) { \
610
if (head1) { \
611
_CASTASGN(_tmp, (head2)->prev); \
612
(head2)->prev = (head1)->prev; \
613
(head1)->prev->next = (head2); \
614
_CASTASGN((head1)->prev, _tmp); \
615
} else { \
616
(head1)=(head2); \
617
} \
618
} \
619
} while (0)
620
621
#define DL_DELETE(head,del) \
622
DL_DELETE2(head,del,prev,next)
623
624
#define DL_DELETE2(head,del,prev,next) \
625
do { \
626
assert((del)->prev != NULL); \
627
if ((del)->prev == (del)) { \
628
(head)=NULL; \
629
} else if ((del)==(head)) { \
630
(del)->next->prev = (del)->prev; \
631
(head) = (del)->next; \
632
} else { \
633
(del)->prev->next = (del)->next; \
634
if ((del)->next) { \
635
(del)->next->prev = (del)->prev; \
636
} else { \
637
(head)->prev = (del)->prev; \
638
} \
639
} \
640
} while (0)
641
642
#define DL_COUNT(head,el,counter) \
643
DL_COUNT2(head,el,counter,next) \
644
645
#define DL_COUNT2(head,el,counter,next) \
646
do { \
647
(counter) = 0; \
648
DL_FOREACH2(head,el,next) { ++(counter); } \
649
} while (0)
650
651
#define DL_FOREACH(head,el) \
652
DL_FOREACH2(head,el,next)
653
654
#define DL_FOREACH2(head,el,next) \
655
for ((el) = (head); el; (el) = (el)->next)
656
657
/* this version is safe for deleting the elements during iteration */
658
#define DL_FOREACH_SAFE(head,el,tmp) \
659
DL_FOREACH_SAFE2(head,el,tmp,next)
660
661
#define DL_FOREACH_SAFE2(head,el,tmp,next) \
662
for ((el) = (head); (el) && ((tmp) = (el)->next, 1); (el) = (tmp))
663
664
/* these are identical to their singly-linked list counterparts */
665
#define DL_SEARCH_SCALAR LL_SEARCH_SCALAR
666
#define DL_SEARCH LL_SEARCH
667
#define DL_SEARCH_SCALAR2 LL_SEARCH_SCALAR2
668
#define DL_SEARCH2 LL_SEARCH2
669
670
#define DL_REPLACE_ELEM2(head, el, add, prev, next) \
671
do { \
672
assert((head) != NULL); \
673
assert((el) != NULL); \
674
assert((add) != NULL); \
675
if ((head) == (el)) { \
676
(head) = (add); \
677
(add)->next = (el)->next; \
678
if ((el)->next == NULL) { \
679
(add)->prev = (add); \
680
} else { \
681
(add)->prev = (el)->prev; \
682
(add)->next->prev = (add); \
683
} \
684
} else { \
685
(add)->next = (el)->next; \
686
(add)->prev = (el)->prev; \
687
(add)->prev->next = (add); \
688
if ((el)->next == NULL) { \
689
(head)->prev = (add); \
690
} else { \
691
(add)->next->prev = (add); \
692
} \
693
} \
694
} while (0)
695
696
#define DL_REPLACE_ELEM(head, el, add) \
697
DL_REPLACE_ELEM2(head, el, add, prev, next)
698
699
#define DL_PREPEND_ELEM2(head, el, add, prev, next) \
700
do { \
701
if (el) { \
702
assert((head) != NULL); \
703
assert((add) != NULL); \
704
(add)->next = (el); \
705
(add)->prev = (el)->prev; \
706
(el)->prev = (add); \
707
if ((head) == (el)) { \
708
(head) = (add); \
709
} else { \
710
(add)->prev->next = (add); \
711
} \
712
} else { \
713
DL_APPEND2(head, add, prev, next); \
714
} \
715
} while (0) \
716
717
#define DL_PREPEND_ELEM(head, el, add) \
718
DL_PREPEND_ELEM2(head, el, add, prev, next)
719
720
#define DL_APPEND_ELEM2(head, el, add, prev, next) \
721
do { \
722
if (el) { \
723
assert((head) != NULL); \
724
assert((add) != NULL); \
725
(add)->next = (el)->next; \
726
(add)->prev = (el); \
727
(el)->next = (add); \
728
if ((add)->next) { \
729
(add)->next->prev = (add); \
730
} else { \
731
(head)->prev = (add); \
732
} \
733
} else { \
734
DL_PREPEND2(head, add, prev, next); \
735
} \
736
} while (0) \
737
738
#define DL_APPEND_ELEM(head, el, add) \
739
DL_APPEND_ELEM2(head, el, add, prev, next)
740
741
/******************************************************************************
742
* circular doubly linked list macros *
743
*****************************************************************************/
744
#define CDL_APPEND(head,add) \
745
CDL_APPEND2(head,add,prev,next)
746
747
#define CDL_APPEND2(head,add,prev,next) \
748
do { \
749
if (head) { \
750
(add)->prev = (head)->prev; \
751
(add)->next = (head); \
752
(head)->prev = (add); \
753
(add)->prev->next = (add); \
754
} else { \
755
(add)->prev = (add); \
756
(add)->next = (add); \
757
(head) = (add); \
758
} \
759
} while (0)
760
761
#define CDL_PREPEND(head,add) \
762
CDL_PREPEND2(head,add,prev,next)
763
764
#define CDL_PREPEND2(head,add,prev,next) \
765
do { \
766
if (head) { \
767
(add)->prev = (head)->prev; \
768
(add)->next = (head); \
769
(head)->prev = (add); \
770
(add)->prev->next = (add); \
771
} else { \
772
(add)->prev = (add); \
773
(add)->next = (add); \
774
} \
775
(head) = (add); \
776
} while (0)
777
778
#define CDL_DELETE(head,del) \
779
CDL_DELETE2(head,del,prev,next)
780
781
#define CDL_DELETE2(head,del,prev,next) \
782
do { \
783
if (((head)==(del)) && ((head)->next == (head))) { \
784
(head) = NULL; \
785
} else { \
786
(del)->next->prev = (del)->prev; \
787
(del)->prev->next = (del)->next; \
788
if ((del) == (head)) (head)=(del)->next; \
789
} \
790
} while (0)
791
792
#define CDL_COUNT(head,el,counter) \
793
CDL_COUNT2(head,el,counter,next) \
794
795
#define CDL_COUNT2(head, el, counter,next) \
796
do { \
797
(counter) = 0; \
798
CDL_FOREACH2(head,el,next) { ++(counter); } \
799
} while (0)
800
801
#define CDL_FOREACH(head,el) \
802
CDL_FOREACH2(head,el,next)
803
804
#define CDL_FOREACH2(head,el,next) \
805
for ((el)=(head);el;(el)=(((el)->next==(head)) ? NULL : (el)->next))
806
807
#define CDL_FOREACH_SAFE(head,el,tmp1,tmp2) \
808
CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next)
809
810
#define CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next) \
811
for ((el) = (head), (tmp1) = (head) ? (head)->prev : NULL; \
812
(el) && ((tmp2) = (el)->next, 1); \
813
(el) = ((el) == (tmp1) ? NULL : (tmp2)))
814
815
#define CDL_SEARCH_SCALAR(head,out,field,val) \
816
CDL_SEARCH_SCALAR2(head,out,field,val,next)
817
818
#define CDL_SEARCH_SCALAR2(head,out,field,val,next) \
819
do { \
820
CDL_FOREACH2(head,out,next) { \
821
if ((out)->field == (val)) break; \
822
} \
823
} while (0)
824
825
#define CDL_SEARCH(head,out,elt,cmp) \
826
CDL_SEARCH2(head,out,elt,cmp,next)
827
828
#define CDL_SEARCH2(head,out,elt,cmp,next) \
829
do { \
830
CDL_FOREACH2(head,out,next) { \
831
if ((cmp(out,elt))==0) break; \
832
} \
833
} while (0)
834
835
#define CDL_REPLACE_ELEM2(head, el, add, prev, next) \
836
do { \
837
assert((head) != NULL); \
838
assert((el) != NULL); \
839
assert((add) != NULL); \
840
if ((el)->next == (el)) { \
841
(add)->next = (add); \
842
(add)->prev = (add); \
843
(head) = (add); \
844
} else { \
845
(add)->next = (el)->next; \
846
(add)->prev = (el)->prev; \
847
(add)->next->prev = (add); \
848
(add)->prev->next = (add); \
849
if ((head) == (el)) { \
850
(head) = (add); \
851
} \
852
} \
853
} while (0)
854
855
#define CDL_REPLACE_ELEM(head, el, add) \
856
CDL_REPLACE_ELEM2(head, el, add, prev, next)
857
858
#define CDL_PREPEND_ELEM2(head, el, add, prev, next) \
859
do { \
860
if (el) { \
861
assert((head) != NULL); \
862
assert((add) != NULL); \
863
(add)->next = (el); \
864
(add)->prev = (el)->prev; \
865
(el)->prev = (add); \
866
(add)->prev->next = (add); \
867
if ((head) == (el)) { \
868
(head) = (add); \
869
} \
870
} else { \
871
CDL_APPEND2(head, add, prev, next); \
872
} \
873
} while (0)
874
875
#define CDL_PREPEND_ELEM(head, el, add) \
876
CDL_PREPEND_ELEM2(head, el, add, prev, next)
877
878
#define CDL_APPEND_ELEM2(head, el, add, prev, next) \
879
do { \
880
if (el) { \
881
assert((head) != NULL); \
882
assert((add) != NULL); \
883
(add)->next = (el)->next; \
884
(add)->prev = (el); \
885
(el)->next = (add); \
886
(add)->next->prev = (add); \
887
} else { \
888
CDL_PREPEND2(head, add, prev, next); \
889
} \
890
} while (0)
891
892
#define CDL_APPEND_ELEM(head, el, add) \
893
CDL_APPEND_ELEM2(head, el, add, prev, next)
894
895
#endif
/* UTLIST_H */
src
utlist.h
Generated by
1.8.13
1.8.13 1.8.13