libcoap  4.1.1
 All Data Structures Files Functions Variables Typedefs Macros Groups Pages
utlist.h
Go to the documentation of this file.
1 /*
2 Copyright (c) 2007-2010, Troy D. Hanson http://uthash.sourceforge.net
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 1.9.1
28 
29 /*
30  * This file contains macros to manipulate singly and doubly-linked lists.
31  *
32  * 1. LL_ macros: singly-linked lists.
33  * 2. DL_ macros: doubly-linked lists.
34  * 3. CDL_ macros: circular doubly-linked lists.
35  *
36  * To use singly-linked lists, your structure must have a "next" pointer.
37  * To use doubly-linked lists, your structure must "prev" and "next" pointers.
38  * Either way, the pointer to the head of the list must be initialized to NULL.
39  *
40  * ----------------.EXAMPLE -------------------------
41  * struct item {
42  * int id;
43  * struct item *prev, *next;
44  * }
45  *
46  * struct item *list = NULL:
47  *
48  * int main() {
49  * struct item *item;
50  * ... allocate and populate item ...
51  * DL_APPEND(list, item);
52  * }
53  * --------------------------------------------------
54  *
55  * For doubly-linked lists, the append and delete macros are O(1)
56  * For singly-linked lists, append and delete are O(n) but prepend is O(1)
57  * The sort macro is O(n log(n)) for all types of single/double/circular lists.
58  */
59 
60 /* These macros use decltype or the earlier __typeof GNU extension.
61  As decltype is only available in newer compilers (VS2010 or gcc 4.3+
62  when compiling c++ code), this code uses whatever method is needed
63  or, for VS2008 where neither is available, uses casting workarounds. */
64 #ifdef _MSC_VER /* MS compiler */
65 #if _MSC_VER >= 1600 && __cplusplus /* VS2010 and newer in C++ mode */
66 #define LDECLTYPE(x) decltype(x)
67 #else /* VS2008 or older (or VS2010 in C mode) */
68 #define NO_DECLTYPE
69 #define LDECLTYPE(x) char*
70 #endif
71 #else /* GNU, Sun and other compilers */
72 #define LDECLTYPE(x) __typeof(x)
73 #endif
74 
75 /* for VS2008 we use some workarounds to get around the lack of decltype,
76  * namely, we always reassign our tmp variable to the list head if we need
77  * to dereference its prev/next pointers, and save/restore the real head.*/
78 #ifdef NO_DECLTYPE
79 #define _SV(elt,list) _tmp = (char*)(list); {char **_alias = (char**)&(list); *_alias = (elt); }
80 #define _NEXT(elt,list) ((char*)((list)->next))
81 #define _NEXTASGN(elt,list,to) { char **_alias = (char**)&((list)->next); *_alias=(char*)(to); }
82 #define _PREV(elt,list) ((char*)((list)->prev))
83 #define _PREVASGN(elt,list,to) { char **_alias = (char**)&((list)->prev); *_alias=(char*)(to); }
84 #define _RS(list) { char **_alias = (char**)&(list); *_alias=_tmp; }
85 #define _CASTASGN(a,b) { char **_alias = (char**)&(a); *_alias=(char*)(b); }
86 #else
87 #define _SV(elt,list)
88 #define _NEXT(elt,list) ((elt)->next)
89 #define _NEXTASGN(elt,list,to) ((elt)->next)=(to)
90 #define _PREV(elt,list) ((elt)->prev)
91 #define _PREVASGN(elt,list,to) ((elt)->prev)=(to)
92 #define _RS(list)
93 #define _CASTASGN(a,b) (a)=(b)
94 #endif
95 
96 /******************************************************************************
97  * The sort macro is an adaptation of Simon Tatham's O(n log(n)) mergesort *
98  * Unwieldy variable names used here to avoid shadowing passed-in variables. *
99  *****************************************************************************/
100 #define LL_SORT(list, cmp) \
101 do { \
102  LDECLTYPE(list) _ls_p; \
103  LDECLTYPE(list) _ls_q; \
104  LDECLTYPE(list) _ls_e; \
105  LDECLTYPE(list) _ls_tail; \
106  LDECLTYPE(list) _ls_oldhead; \
107  LDECLTYPE(list) _tmp; \
108  int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
109  if (list) { \
110  _ls_insize = 1; \
111  _ls_looping = 1; \
112  while (_ls_looping) { \
113  _CASTASGN(_ls_p,list); \
114  _CASTASGN(_ls_oldhead,list); \
115  list = NULL; \
116  _ls_tail = NULL; \
117  _ls_nmerges = 0; \
118  while (_ls_p) { \
119  _ls_nmerges++; \
120  _ls_q = _ls_p; \
121  _ls_psize = 0; \
122  for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
123  _ls_psize++; \
124  _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); \
125  if (!_ls_q) break; \
126  } \
127  _ls_qsize = _ls_insize; \
128  while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \
129  if (_ls_psize == 0) { \
130  _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \
131  } else if (_ls_qsize == 0 || !_ls_q) { \
132  _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \
133  } else if (cmp(_ls_p,_ls_q) <= 0) { \
134  _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \
135  } else { \
136  _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \
137  } \
138  if (_ls_tail) { \
139  _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e); _RS(list); \
140  } else { \
141  _CASTASGN(list,_ls_e); \
142  } \
143  _ls_tail = _ls_e; \
144  } \
145  _ls_p = _ls_q; \
146  } \
147  _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL); _RS(list); \
148  if (_ls_nmerges <= 1) { \
149  _ls_looping=0; \
150  } \
151  _ls_insize *= 2; \
152  } \
153  } else _tmp=NULL; /* quiet gcc unused variable warning */ \
154 } while (0)
155 
156 #define DL_SORT(list, cmp) \
157 do { \
158  LDECLTYPE(list) _ls_p; \
159  LDECLTYPE(list) _ls_q; \
160  LDECLTYPE(list) _ls_e; \
161  LDECLTYPE(list) _ls_tail; \
162  LDECLTYPE(list) _ls_oldhead; \
163  LDECLTYPE(list) _tmp; \
164  int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
165  if (list) { \
166  _ls_insize = 1; \
167  _ls_looping = 1; \
168  while (_ls_looping) { \
169  _CASTASGN(_ls_p,list); \
170  _CASTASGN(_ls_oldhead,list); \
171  list = NULL; \
172  _ls_tail = NULL; \
173  _ls_nmerges = 0; \
174  while (_ls_p) { \
175  _ls_nmerges++; \
176  _ls_q = _ls_p; \
177  _ls_psize = 0; \
178  for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
179  _ls_psize++; \
180  _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); \
181  if (!_ls_q) break; \
182  } \
183  _ls_qsize = _ls_insize; \
184  while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \
185  if (_ls_psize == 0) { \
186  _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \
187  } else if (_ls_qsize == 0 || !_ls_q) { \
188  _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \
189  } else if (cmp(_ls_p,_ls_q) <= 0) { \
190  _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \
191  } else { \
192  _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \
193  } \
194  if (_ls_tail) { \
195  _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e); _RS(list); \
196  } else { \
197  _CASTASGN(list,_ls_e); \
198  } \
199  _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail); _RS(list); \
200  _ls_tail = _ls_e; \
201  } \
202  _ls_p = _ls_q; \
203  } \
204  _CASTASGN(list->prev, _ls_tail); \
205  _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL); _RS(list); \
206  if (_ls_nmerges <= 1) { \
207  _ls_looping=0; \
208  } \
209  _ls_insize *= 2; \
210  } \
211  } else _tmp=NULL; /* quiet gcc unused variable warning */ \
212 } while (0)
213 
214 #define CDL_SORT(list, cmp) \
215 do { \
216  LDECLTYPE(list) _ls_p; \
217  LDECLTYPE(list) _ls_q; \
218  LDECLTYPE(list) _ls_e; \
219  LDECLTYPE(list) _ls_tail; \
220  LDECLTYPE(list) _ls_oldhead; \
221  LDECLTYPE(list) _tmp; \
222  LDECLTYPE(list) _tmp2; \
223  int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
224  if (list) { \
225  _ls_insize = 1; \
226  _ls_looping = 1; \
227  while (_ls_looping) { \
228  _CASTASGN(_ls_p,list); \
229  _CASTASGN(_ls_oldhead,list); \
230  list = NULL; \
231  _ls_tail = NULL; \
232  _ls_nmerges = 0; \
233  while (_ls_p) { \
234  _ls_nmerges++; \
235  _ls_q = _ls_p; \
236  _ls_psize = 0; \
237  for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
238  _ls_psize++; \
239  _SV(_ls_q,list); \
240  if (_NEXT(_ls_q,list) == _ls_oldhead) { \
241  _ls_q = NULL; \
242  } else { \
243  _ls_q = _NEXT(_ls_q,list); \
244  } \
245  _RS(list); \
246  if (!_ls_q) break; \
247  } \
248  _ls_qsize = _ls_insize; \
249  while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \
250  if (_ls_psize == 0) { \
251  _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \
252  if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \
253  } else if (_ls_qsize == 0 || !_ls_q) { \
254  _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \
255  if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \
256  } else if (cmp(_ls_p,_ls_q) <= 0) { \
257  _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \
258  if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \
259  } else { \
260  _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \
261  if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \
262  } \
263  if (_ls_tail) { \
264  _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e); _RS(list); \
265  } else { \
266  _CASTASGN(list,_ls_e); \
267  } \
268  _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail); _RS(list); \
269  _ls_tail = _ls_e; \
270  } \
271  _ls_p = _ls_q; \
272  } \
273  _CASTASGN(list->prev,_ls_tail); \
274  _CASTASGN(_tmp2,list); \
275  _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_tmp2); _RS(list); \
276  if (_ls_nmerges <= 1) { \
277  _ls_looping=0; \
278  } \
279  _ls_insize *= 2; \
280  } \
281  } else _tmp=NULL; /* quiet gcc unused variable warning */ \
282 } while (0)
283 
284 /******************************************************************************
285  * singly linked list macros (non-circular) *
286  *****************************************************************************/
287 #define LL_PREPEND(head,add) \
288 do { \
289  (add)->next = head; \
290  head = add; \
291 } while (0)
292 
293 #define LL_APPEND(head,add) \
294 do { \
295  LDECLTYPE(head) _tmp; \
296  (add)->next=NULL; \
297  if (head) { \
298  _tmp = head; \
299  while (_tmp->next) { _tmp = _tmp->next; } \
300  _tmp->next=(add); \
301  } else { \
302  (head)=(add); \
303  } \
304 } while (0)
305 
306 #define LL_DELETE(head,del) \
307 do { \
308  LDECLTYPE(head) _tmp; \
309  if ((head) == (del)) { \
310  (head)=(head)->next; \
311  } else { \
312  _tmp = head; \
313  while (_tmp->next && (_tmp->next != (del))) { \
314  _tmp = _tmp->next; \
315  } \
316  if (_tmp->next) { \
317  _tmp->next = ((del)->next); \
318  } \
319  } \
320 } while (0)
321 
322 /* Here are VS2008 replacements for LL_APPEND and LL_DELETE */
323 #define LL_APPEND_VS2008(head,add) \
324 do { \
325  if (head) { \
326  (add)->next = head; /* use add->next as a temp variable */ \
327  while ((add)->next->next) { (add)->next = (add)->next->next; } \
328  (add)->next->next=(add); \
329  } else { \
330  (head)=(add); \
331  } \
332  (add)->next=NULL; \
333 } while (0)
334 
335 #define LL_DELETE_VS2008(head,del) \
336 do { \
337  if ((head) == (del)) { \
338  (head)=(head)->next; \
339  } else { \
340  char *_tmp = (char*)(head); \
341  while (head->next && (head->next != (del))) { \
342  head = head->next; \
343  } \
344  if (head->next) { \
345  head->next = ((del)->next); \
346  } \
347  { \
348  char **_head_alias = (char**)&(head); \
349  *_head_alias = _tmp; \
350  } \
351  } \
352 } while (0)
353 #ifdef NO_DECLTYPE
354 #undef LL_APPEND
355 #define LL_APPEND LL_APPEND_VS2008
356 #undef LL_DELETE
357 #define LL_DELETE LL_DELETE_VS2008
358 #endif
359 /* end VS2008 replacements */
360 
361 #define LL_FOREACH(head,el) \
362  for(el=head;el;el=el->next)
363 
364 #define LL_FOREACH_SAFE(head,el,tmp) \
365  for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp)
366 
367 #define LL_SEARCH_SCALAR(head,out,field,val) \
368 do { \
369  LL_FOREACH(head,out) { \
370  if ((out)->field == (val)) break; \
371  } \
372 } while(0)
373 
374 #define LL_SEARCH(head,out,elt,cmp) \
375 do { \
376  LL_FOREACH(head,out) { \
377  if ((cmp(out,elt))==0) break; \
378  } \
379 } while(0)
380 
381 /******************************************************************************
382  * doubly linked list macros (non-circular) *
383  *****************************************************************************/
384 #define DL_PREPEND(head,add) \
385 do { \
386  (add)->next = head; \
387  if (head) { \
388  (add)->prev = (head)->prev; \
389  (head)->prev = (add); \
390  } else { \
391  (add)->prev = (add); \
392  } \
393  (head) = (add); \
394 } while (0)
395 
396 #define DL_APPEND(head,add) \
397 do { \
398  if (head) { \
399  (add)->prev = (head)->prev; \
400  (head)->prev->next = (add); \
401  (head)->prev = (add); \
402  (add)->next = NULL; \
403  } else { \
404  (head)=(add); \
405  (head)->prev = (head); \
406  (head)->next = NULL; \
407  } \
408 } while (0);
409 
410 #define DL_DELETE(head,del) \
411 do { \
412  if ((del)->prev == (del)) { \
413  (head)=NULL; \
414  } else if ((del)==(head)) { \
415  (del)->next->prev = (del)->prev; \
416  (head) = (del)->next; \
417  } else { \
418  (del)->prev->next = (del)->next; \
419  if ((del)->next) { \
420  (del)->next->prev = (del)->prev; \
421  } else { \
422  (head)->prev = (del)->prev; \
423  } \
424  } \
425 } while (0);
426 
427 
428 #define DL_FOREACH(head,el) \
429  for(el=head;el;el=el->next)
430 
431 /* this version is safe for deleting the elements during iteration */
432 #define DL_FOREACH_SAFE(head,el,tmp) \
433  for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp)
434 
435 /* these are identical to their singly-linked list counterparts */
436 #define DL_SEARCH_SCALAR LL_SEARCH_SCALAR
437 #define DL_SEARCH LL_SEARCH
438 
439 /******************************************************************************
440  * circular doubly linked list macros *
441  *****************************************************************************/
442 #define CDL_PREPEND(head,add) \
443 do { \
444  if (head) { \
445  (add)->prev = (head)->prev; \
446  (add)->next = (head); \
447  (head)->prev = (add); \
448  (add)->prev->next = (add); \
449  } else { \
450  (add)->prev = (add); \
451  (add)->next = (add); \
452  } \
453 (head)=(add); \
454 } while (0)
455 
456 #define CDL_DELETE(head,del) \
457 do { \
458  if ( ((head)==(del)) && ((head)->next == (head))) { \
459  (head) = 0L; \
460  } else { \
461  (del)->next->prev = (del)->prev; \
462  (del)->prev->next = (del)->next; \
463  if ((del) == (head)) (head)=(del)->next; \
464  } \
465 } while (0);
466 
467 #define CDL_FOREACH(head,el) \
468  for(el=head;el;el=(el->next==head ? 0L : el->next))
469 
470 #define CDL_FOREACH_SAFE(head,el,tmp1,tmp2) \
471  for((el)=(head), ((tmp1)=(head)?((head)->prev):NULL); \
472  (el) && ((tmp2)=(el)->next, 1); \
473  ((el) = (((el)==(tmp1)) ? 0L : (tmp2))))
474 
475 #define CDL_SEARCH_SCALAR(head,out,field,val) \
476 do { \
477  CDL_FOREACH(head,out) { \
478  if ((out)->field == (val)) break; \
479  } \
480 } while(0)
481 
482 #define CDL_SEARCH(head,out,elt,cmp) \
483 do { \
484  CDL_FOREACH(head,out) { \
485  if ((cmp(out,elt))==0) break; \
486  } \
487 } while(0)
488 
489 #endif /* UTLIST_H */
490 
Generated on Thu May 7 2015 19:23:26 for libcoap by   doxygen 1.8.6