check_type: fix incorrect documentation.
[ccan] / ccan / nfs / dlinklist.h
1 /*
2    Unix SMB/CIFS implementation.
3    some simple double linked list macros
4
5    Copyright (C) Andrew Tridgell 1998-2010
6    
7    This program is free software; you can redistribute it and/or modify
8    it under the terms of the GNU General Public License as published by
9    the Free Software Foundation; either version 3 of the License, or
10    (at your option) any later version.
11    
12    This program is distributed in the hope that it will be useful,
13    but WITHOUT ANY WARRANTY; without even the implied warranty of
14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15    GNU General Public License for more details.
16    
17    You should have received a copy of the GNU General Public License
18    along with this program.  If not, see <http://www.gnu.org/licenses/>.
19 */
20
21 /* To use these macros you must have a structure containing a next and
22    prev pointer */
23
24 #ifndef _DLINKLIST_H
25 #define _DLINKLIST_H
26
27 /*
28   February 2010 - changed list format to have a prev pointer from the
29   list head. This makes DLIST_ADD_END() O(1) even though we only have
30   one list pointer.
31
32   The scheme is as follows:
33
34      1) with no entries in the list:
35           list_head == NULL
36
37      2) with 1 entry in the list:
38           list_head->next == NULL
39           list_head->prev == list_head
40
41      3) with 2 entries in the list:
42           list_head->next == element2
43           list_head->prev == element2
44           element2->prev == list_head
45           element2->next == NULL
46
47      4) with N entries in the list:
48           list_head->next == element2
49           list_head->prev == elementN
50           elementN->prev == element{N-1}
51           elementN->next == NULL
52
53   This allows us to find the tail of the list by using
54   list_head->prev, which means we can add to the end of the list in
55   O(1) time
56
57
58   Note that the 'type' arguments below are no longer needed, but
59   are kept for now to prevent an incompatible argument change
60  */
61
62
63 /*
64    add an element at the front of a list
65 */
66 #define DLIST_ADD(list, p) \
67 do { \
68         if (!(list)) { \
69                 (p)->prev = (list) = (p);  \
70                 (p)->next = NULL; \
71         } else { \
72                 (p)->prev = (list)->prev; \
73                 (list)->prev = (p); \
74                 (p)->next = (list); \
75                 (list) = (p); \
76         } \
77 } while (0)
78
79 /*
80    remove an element from a list
81    Note that the element doesn't have to be in the list. If it
82    isn't then this is a no-op
83 */
84 #define DLIST_REMOVE(list, p) \
85 do { \
86         if ((p) == (list)) { \
87                 if ((p)->next) (p)->next->prev = (p)->prev; \
88                 (list) = (p)->next; \
89         } else if ((list) && (p) == (list)->prev) {     \
90                 (p)->prev->next = NULL; \
91                 (list)->prev = (p)->prev; \
92         } else { \
93                 if ((p)->prev) (p)->prev->next = (p)->next; \
94                 if ((p)->next) (p)->next->prev = (p)->prev; \
95         } \
96         if ((p) != (list)) (p)->next = (p)->prev = NULL;        \
97 } while (0)
98
99 /*
100    find the head of the list given any element in it.
101    Note that this costs O(N), so you should avoid this macro
102    if at all possible!
103 */
104 #define DLIST_HEAD(p, result_head) \
105 do { \
106        (result_head) = (p); \
107        while (DLIST_PREV(result_head)) (result_head) = (result_head)->prev; \
108 } while(0)
109
110 /* return the last element in the list */
111 #define DLIST_TAIL(list) ((list)?(list)->prev:NULL)
112
113 /* return the previous element in the list. */
114 #define DLIST_PREV(p) (((p)->prev && (p)->prev->next != NULL)?(p)->prev:NULL)
115
116 /* insert 'p' after the given element 'el' in a list. If el is NULL then
117    this is the same as a DLIST_ADD() */
118 #define DLIST_ADD_AFTER(list, p, el) \
119 do { \
120         if (!(list) || !(el)) { \
121                 DLIST_ADD(list, p); \
122         } else { \
123                 (p)->prev = (el);   \
124                 (p)->next = (el)->next;         \
125                 (el)->next = (p);               \
126                 if ((p)->next) (p)->next->prev = (p);   \
127                 if ((list)->prev == (el)) (list)->prev = (p); \
128         }\
129 } while (0)
130
131
132 /*
133    add to the end of a list.
134    Note that 'type' is ignored
135 */
136 #define DLIST_ADD_END(list, p, type)                    \
137 do { \
138         if (!(list)) { \
139                 DLIST_ADD(list, p); \
140         } else { \
141                 DLIST_ADD_AFTER(list, p, (list)->prev); \
142         } \
143 } while (0)
144
145 /* promote an element to the from of a list */
146 #define DLIST_PROMOTE(list, p) \
147 do { \
148           DLIST_REMOVE(list, p); \
149           DLIST_ADD(list, p); \
150 } while (0)
151
152 /*
153    demote an element to the end of a list.
154    Note that 'type' is ignored
155 */
156 #define DLIST_DEMOTE(list, p, type)                     \
157 do { \
158         DLIST_REMOVE(list, p); \
159         DLIST_ADD_END(list, p, NULL);           \
160 } while (0)
161
162 /*
163    concatenate two lists - putting all elements of the 2nd list at the
164    end of the first list.
165    Note that 'type' is ignored
166 */
167 #define DLIST_CONCATENATE(list1, list2, type)   \
168 do { \
169         if (!(list1)) { \
170                 (list1) = (list2); \
171         } else { \
172                 (list1)->prev->next = (list2); \
173                 if (list2) { \
174                         void *_tmplist = (void *)(list1)->prev; \
175                         (list1)->prev = (list2)->prev; \
176                         (list2)->prev = _tmplist; \
177                 } \
178         } \
179 } while (0)
180
181 #endif /* _DLINKLIST_H */