summary refs log tree commit diff stats
path: root/libs/cocos2d/Support/utlist.h
diff options
context:
space:
mode:
Diffstat (limited to 'libs/cocos2d/Support/utlist.h')
-rwxr-xr-xlibs/cocos2d/Support/utlist.h490
1 files changed, 490 insertions, 0 deletions
diff --git a/libs/cocos2d/Support/utlist.h b/libs/cocos2d/Support/utlist.h new file mode 100755 index 0000000..34c725b --- /dev/null +++ b/libs/cocos2d/Support/utlist.h
@@ -0,0 +1,490 @@
1/*
2Copyright (c) 2007-2010, Troy D. Hanson http://uthash.sourceforge.net
3All rights reserved.
4
5Redistribution and use in source and binary forms, with or without
6modification, 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
11THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
12IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
13TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
14PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
15OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
16EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
17PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
18PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
19LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
20NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
21SOFTWARE, 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 && defined(__cplusplus) /* VS2010 or 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) \
101do { \
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) \
157do { \
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) \
215do { \
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) \
288do { \
289 (add)->next = head; \
290 head = add; \
291} while (0)
292
293#define LL_APPEND(head,add) \
294do { \
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) \
307do { \
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) \
324do { \
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) \
336do { \
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) \
368do { \
369 LL_FOREACH(head,out) { \
370 if ((out)->field == (val)) break; \
371 } \
372} while(0)
373
374#define LL_SEARCH(head,out,elt,cmp) \
375do { \
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) \
385do { \
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) \
397do { \
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) \
411do { \
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) \
443do { \
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) \
457do { \
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) \
476do { \
477 CDL_FOREACH(head,out) { \
478 if ((out)->field == (val)) break; \
479 } \
480} while(0)
481
482#define CDL_SEARCH(head,out,elt,cmp) \
483do { \
484 CDL_FOREACH(head,out) { \
485 if ((cmp(out,elt))==0) break; \
486 } \
487} while(0)
488
489#endif /* UTLIST_H */
490
generated by cgit-pink 1.4.1 (git 2.36.1) at 2024-11-21 21:10:05 +0000