1 /***************************************************************************
2 * gh_list.h -- a simple doubly-linked list implementation. *
3 * *
4 ***********************IMPORTANT NSOCK LICENSE TERMS***********************
5 * *
6 * The nsock parallel socket event library is (C) 1999-2017 Insecure.Com *
7 * LLC This library is free software; you may redistribute and/or *
8 * modify it under the terms of the GNU General Public License as *
9 * published by the Free Software Foundation; Version 2. This guarantees *
10 * your right to use, modify, and redistribute this software under certain *
11 * conditions. If this license is unacceptable to you, Insecure.Com LLC *
12 * may be willing to sell alternative licenses (contact *
13 * sales@insecure.com ). *
14 * *
15 * As a special exception to the GPL terms, Insecure.Com LLC grants *
16 * permission to link the code of this program with any version of the *
17 * OpenSSL library which is distributed under a license identical to that *
18 * listed in the included docs/licenses/OpenSSL.txt file, and distribute *
19 * linked combinations including the two. You must obey the GNU GPL in all *
20 * respects for all of the code used other than OpenSSL. If you modify *
21 * this file, you may extend this exception to your version of the file, *
22 * but you are not obligated to do so. *
23 * *
24 * If you received these files with a written license agreement stating *
25 * terms other than the (GPL) terms above, then that alternative license *
26 * agreement takes precedence over this comment. *
27 * *
28 * Source is provided to this software because we believe users have a *
29 * right to know exactly what a program is going to do before they run it. *
30 * This also allows you to audit the software for security holes. *
31 * *
32 * Source code also allows you to port Nmap to new platforms, fix bugs, *
33 * and add new features. You are highly encouraged to send your changes *
34 * to the dev@nmap.org mailing list for possible incorporation into the *
35 * main distribution. By sending these changes to Fyodor or one of the *
36 * Insecure.Org development mailing lists, or checking them into the Nmap *
37 * source code repository, it is understood (unless you specify otherwise) *
38 * that you are offering the Nmap Project (Insecure.Com LLC) the *
39 * unlimited, non-exclusive right to reuse, modify, and relicense the *
40 * code. Nmap will always be available Open Source, but this is important *
41 * because the inability to relicense code has caused devastating problems *
42 * for other Free Software projects (such as KDE and NASM). We also *
43 * occasionally relicense the code to third parties as discussed above. *
44 * If you wish to specify special license conditions of your *
45 * contributions, just say so when you send them. *
46 * *
47 * This program is distributed in the hope that it will be useful, but *
48 * WITHOUT ANY WARRANTY; without even the implied warranty of *
49 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
50 * General Public License v2.0 for more details *
51 * (http://www.gnu.org/licenses/gpl-2.0.html). *
52 * *
53 ***************************************************************************/
54
55 /* $Id$ */
56
57 #ifndef GH_LIST_H
58 #define GH_LIST_H
59
60 #ifdef HAVE_CONFIG_H
61 #include "nsock_config.h"
62 #include "nbase_config.h"
63 #endif
64
65 #ifdef WIN32
66 #include "nbase_winconfig.h"
67 #endif
68
69 #include "error.h"
70 #include <assert.h>
71
72 #define GH_LIST_MAGIC 0xBADFACE
73 #define GH_LIST_PARANOID 0
74
75
76 typedef struct gh_list_node {
77 struct gh_list_node *next;
78 struct gh_list_node *prev;
79 } gh_lnode_t;
80
81 typedef struct gh_list {
82 /* Number of elements in the list */
83 unsigned int count;
84 gh_lnode_t *first;
85 gh_lnode_t *last;
86 } gh_list_t;
87
88
89 /* That one's an efficiency killer but it should reveal
90 * any inconsistency in nsock's lists management. To be
91 * called on every list we get and return. */
paranoid_list_check(gh_list_t * list)92 static inline void paranoid_list_check(gh_list_t *list) {
93 #if GH_LIST_PARANOID
94 switch (list->count) {
95 case 0:
96 assert(list->first == NULL);
97 assert(list->last == NULL);
98 break;
99
100 case 1:
101 assert(list->first);
102 assert(list->last);
103 assert(list->first == list->last);
104 break;
105
106 default:
107 assert(list->first);
108 assert(list->last);
109 assert(list->first != list->last);
110 break;
111 }
112 #endif
113 }
114
gh_list_init(gh_list_t * newlist)115 static inline int gh_list_init(gh_list_t *newlist) {
116 newlist->count = 0;
117 newlist->first = NULL;
118 newlist->last = NULL;
119 return 0;
120 }
121
gh_list_append(gh_list_t * list,gh_lnode_t * lnode)122 static inline int gh_list_append(gh_list_t *list, gh_lnode_t *lnode) {
123 gh_lnode_t *oldlast;
124
125 paranoid_list_check(list);
126
127 oldlast = list->last;
128 if (oldlast)
129 oldlast->next = lnode;
130
131 lnode->prev = oldlast;
132 lnode->next = NULL;
133
134 list->count++;
135 list->last = lnode;
136
137 if (list->count == 1)
138 list->first = lnode;
139
140 paranoid_list_check(list);
141 return 0;
142 }
143
gh_list_prepend(gh_list_t * list,gh_lnode_t * lnode)144 static inline int gh_list_prepend(gh_list_t *list, gh_lnode_t *lnode) {
145 gh_lnode_t *oldfirst;
146
147 paranoid_list_check(list);
148
149 oldfirst = list->first;
150 if (oldfirst)
151 oldfirst->prev = lnode;
152
153 lnode->next = oldfirst;
154 lnode->prev = NULL;
155
156 list->count++;
157 list->first = lnode;
158
159 if (list->count == 1)
160 list->last = lnode;
161
162 paranoid_list_check(list);
163 return 0;
164 }
165
gh_list_insert_before(gh_list_t * list,gh_lnode_t * before,gh_lnode_t * lnode)166 static inline int gh_list_insert_before(gh_list_t *list, gh_lnode_t *before,
167 gh_lnode_t *lnode) {
168 paranoid_list_check(list);
169
170 lnode->prev = before->prev;
171 lnode->next = before;
172
173 if (before->prev)
174 before->prev->next = lnode;
175 else
176 list->first = lnode;
177
178 before->prev = lnode;
179 list->count++;
180
181 paranoid_list_check(list);
182 return 0;
183 }
184
gh_list_pop(gh_list_t * list)185 static inline gh_lnode_t *gh_list_pop(gh_list_t *list) {
186 gh_lnode_t *elem;
187
188 paranoid_list_check(list);
189
190 elem = list->first;
191 if (!elem) {
192 paranoid_list_check(list);
193 return NULL;
194 }
195
196 list->first = list->first->next;
197 if (list->first)
198 list->first->prev = NULL;
199
200 list->count--;
201
202 if (list->count < 2)
203 list->last = list->first;
204
205 elem->prev = NULL;
206 elem->next = NULL;
207
208 paranoid_list_check(list);
209 return elem;
210 }
211
gh_list_remove(gh_list_t * list,gh_lnode_t * lnode)212 static inline int gh_list_remove(gh_list_t *list, gh_lnode_t *lnode) {
213 paranoid_list_check(list);
214
215 if (lnode->prev) {
216 lnode->prev->next = lnode->next;
217 } else {
218 assert(list->first == lnode);
219 list->first = lnode->next;
220 }
221
222 if (lnode->next) {
223 lnode->next->prev = lnode->prev;
224 } else {
225 assert(list->last == lnode);
226 list->last = lnode->prev;
227 }
228
229 lnode->prev = NULL;
230 lnode->next = NULL;
231
232 list->count--;
233
234 paranoid_list_check(list);
235 return 0;
236 }
237
gh_list_free(gh_list_t * list)238 static inline int gh_list_free(gh_list_t *list) {
239 paranoid_list_check(list);
240
241 while (list->count > 0)
242 gh_list_pop(list);
243
244 paranoid_list_check(list);
245 memset(list, 0, sizeof(gh_list_t));
246 return 0;
247 }
248
gh_list_move_front(gh_list_t * list,gh_lnode_t * lnode)249 static inline int gh_list_move_front(gh_list_t *list, gh_lnode_t *lnode) {
250 paranoid_list_check(list);
251 if (list->first == lnode)
252 return 0;
253
254 /* remove element from its current position */
255 lnode->prev->next = lnode->next;
256
257 if (lnode->next) {
258 lnode->next->prev = lnode->prev;
259 } else {
260 assert(list->last == lnode);
261 list->last = lnode->prev;
262 }
263
264 /* add element to the beginning of the list */
265 list->first->prev = lnode;
266 lnode->next = list->first;
267 lnode->prev = NULL;
268 list->first = lnode;
269
270 paranoid_list_check(list);
271 return 0;
272 }
273
274 /* Take a LIST ELEMENT (not just the data) and return the next one */
gh_lnode_next(gh_lnode_t * elem)275 static inline gh_lnode_t *gh_lnode_next(gh_lnode_t *elem) {
276 return elem->next;
277 }
278
279 /* Same as above but return the previous element */
gh_lnode_prev(gh_lnode_t * elem)280 static inline gh_lnode_t *gh_lnode_prev(gh_lnode_t *elem) {
281 return elem->prev;
282 }
283
284 /* Take a LIST (not a list element) and return the first element */
gh_list_first_elem(gh_list_t * list)285 static inline gh_lnode_t *gh_list_first_elem(gh_list_t *list) {
286 return list->first;
287 }
288
289 /* Same as above but return the last element */
gh_list_last_elem(gh_list_t * list)290 static inline gh_lnode_t *gh_list_last_elem(gh_list_t *list) {
291 return list->last;
292 }
293
gh_list_count(gh_list_t * list)294 static inline unsigned int gh_list_count(gh_list_t *list) {
295 return list->count;
296 }
297
298 #endif /* GH_LIST_H */
299