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
|
/* Copyright (c) 2012-2013 Yoran Heling
Permission is hereby granted, free of charge, to any person obtaining
a copy of this software and associated documentation files (the
"Software"), to deal in the Software without restriction, including
without limitation the rights to use, copy, modify, merge, publish,
distribute, sublicense, and/or sell copies of the Software, and to
permit persons to whom the Software is furnished to do so, subject to
the following conditions:
The above copyright notice and this permission notice shall be included
in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*/
#ifndef UTIL_LIST_H
#define UTIL_LIST_H
/* All macros assume that the next/prev pointers are embedded in the structure
* of each node, and that they are named 'next' and 'prev'. All macros take a
* `list' argument, which is a struct that contains a `head' and `tail'
* pointer.
*
* All macros starting with 's' (e.g. slist_ instead of list_) operate on
* singly-linked lists. The nodes only need to have a 'next' pointer.
*
* All macros containing the 'h' (hlist_, shlist_) flag take only a single
* pointer variable as list argument rather than a struct. This pointer is
* treated as the `head' of a list.
*
* All macros containing the 'p' flag (plist_, splist_) accept an additional
* prefix argument. This argument specifies the name of the struct in which the
* 'next' and 'prev' pointers reside. This allows the same element to be in
* multiple lists:
*
* struct element {
* struct { struct element *next, *prev } list_a, list_b;
* };
*
* The additional prefix argument can then be used to select between list_a and
* list_b.
*
* All pointers point directly to the outer-most structure of the node and not
* to some specially-embedded structure. The latter is the approach taken, for
* example, in the Linux kernel. (https://lwn.net/Articles/336255/)
*
* Circular lists are not supported. Lists should be zero-initialized (i.e.
* NULL,NULL) before use. These macros do not keep a count of the number of
* items in the list.
*
* Note that only the macros have been implemented that I actually use, which
* isn't much. This header file isn't really suitable for generic use at the
* moment.
*/
/* Insert an element in the list before _next, or at the tail if _next is NULL.
* To insert an element at the head of the list: list_insert(l, n, l.head)
* To insert an element at the tail of the list: list_insert(l, n, NULL)
* To insert an element before element x: list_insert(l, n, x)
* To insert an element after element x: list_insert(l, n, x->next)
*/
#define list__insert(_l, _p, _n, _next) do {\
(_n)-> _p next = (_next);\
(_n)-> _p prev = (_n)-> _p next ? (_n)-> _p next-> _p prev : (_l).tail;\
if((_n)-> _p next) (_n)-> _p next-> _p prev = (_n);\
else (_l).tail = (_n);\
if((_n)-> _p prev) (_n)-> _p prev-> _p next = (_n);\
else (_l).head = (_n);\
} while(0)
#define plist_insert(_l, _p, _n, _next) list__insert(_l, _p.,_n,_next)
#define list_insert(_l, _n, _next) list__insert(_l,,_n,_next)
/* Remove an element from the list.
* To remove the first element: list_remove(l, l.head);
* To remove the last element: list_remove(l, l.tail);
*/
#define list__remove(_l, _p, _n) do {\
if((_n)-> _p next) (_n)-> _p next-> _p prev = (_n)-> _p prev;\
if((_n)-> _p prev) (_n)-> _p prev-> _p next = (_n)-> _p next;\
if((_n) == (_l).head) (_l).head = (_n)-> _p next;\
if((_n) == (_l).tail) (_l).tail = (_n)-> _p prev;\
} while(0)
#define plist_remove(_l, _p, _n) list__remove(_l, _p., _n)
#define list_remove(_l, _n) list__remove(_l,,_n)
/* Like list_insert(), but does not support inserting at the tail of the list.
*/
#define hlist__insert_before(_l, _p, _n, _next) do {\
(_n)-> _p next = (_next);\
(_n)-> _p prev = (_n)-> _p next ? (_n)-> _p next -> _p prev : NULL;\
if((_n)-> _p next) (_n)-> _p next-> _p prev = (_n);\
if((_n)-> _p prev) (_n)-> _p prev-> _p next = (_n);\
else (_l) = (_n);\
} while(0)
#define hplist_insert_before(_l,_p,_n,_next) hlist__insert_before(_l,_p.,_n,_next)
#define hlist_insert_before(_l,_n,_next) hlist__insert_before(_l,,_n,_next)
/* Like list_remove() */
#define hlist__remove(_l, _p, _n) do {\
if((_n)-> _p next) (_n)-> _p next-> _p prev = (_n)-> _p prev;\
if((_n)-> _p prev) (_n)-> _p prev-> _p next = (_n)-> _p next;\
if((_n) == (_l)) (_l) = (_n)-> _p next;\
} while(0)
#define hplist_remove(_l, _p, _n) hlist__remove(_l, _p., _n)
#define hlist_remove(_l, _n) hlist__remove(_l,,_n)
#endif
/* vim: set noet sw=4 ts=4: */
|
