|
cocos2d for iPhone 1.0.0
2D engine for iOS and OS X
|
/Users/rquesada/progs/cocos2d-iphone/cocos2d/Support/utlist.h
00001 /* 00002 Copyright (c) 2007-2010, Troy D. Hanson http://uthash.sourceforge.net 00003 All rights reserved. 00004 00005 Redistribution and use in source and binary forms, with or without 00006 modification, are permitted provided that the following conditions are met: 00007 00008 * Redistributions of source code must retain the above copyright 00009 notice, this list of conditions and the following disclaimer. 00010 00011 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS 00012 IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 00013 TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A 00014 PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER 00015 OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 00016 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 00017 PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 00018 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 00019 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 00020 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 00021 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 00022 */ 00023 00024 #ifndef UTLIST_H 00025 #define UTLIST_H 00026 00027 #define UTLIST_VERSION 1.9.1 00028 00029 /* 00030 * This file contains macros to manipulate singly and doubly-linked lists. 00031 * 00032 * 1. LL_ macros: singly-linked lists. 00033 * 2. DL_ macros: doubly-linked lists. 00034 * 3. CDL_ macros: circular doubly-linked lists. 00035 * 00036 * To use singly-linked lists, your structure must have a "next" pointer. 00037 * To use doubly-linked lists, your structure must "prev" and "next" pointers. 00038 * Either way, the pointer to the head of the list must be initialized to NULL. 00039 * 00040 * ----------------.EXAMPLE ------------------------- 00041 * struct item { 00042 * int id; 00043 * struct item *prev, *next; 00044 * } 00045 * 00046 * struct item *list = NULL: 00047 * 00048 * int main() { 00049 * struct item *item; 00050 * ... allocate and populate item ... 00051 * DL_APPEND(list, item); 00052 * } 00053 * -------------------------------------------------- 00054 * 00055 * For doubly-linked lists, the append and delete macros are O(1) 00056 * For singly-linked lists, append and delete are O(n) but prepend is O(1) 00057 * The sort macro is O(n log(n)) for all types of single/double/circular lists. 00058 */ 00059 00060 /* These macros use decltype or the earlier __typeof GNU extension. 00061 As decltype is only available in newer compilers (VS2010 or gcc 4.3+ 00062 when compiling c++ code), this code uses whatever method is needed 00063 or, for VS2008 where neither is available, uses casting workarounds. */ 00064 #ifdef _MSC_VER /* MS compiler */ 00065 #if _MSC_VER >= 1600 && defined(__cplusplus) /* VS2010 or newer in C++ mode */ 00066 #define LDECLTYPE(x) decltype(x) 00067 #else /* VS2008 or older (or VS2010 in C mode) */ 00068 #define NO_DECLTYPE 00069 #define LDECLTYPE(x) char* 00070 #endif 00071 #else /* GNU, Sun and other compilers */ 00072 #define LDECLTYPE(x) __typeof(x) 00073 #endif 00074 00075 /* for VS2008 we use some workarounds to get around the lack of decltype, 00076 * namely, we always reassign our tmp variable to the list head if we need 00077 * to dereference its prev/next pointers, and save/restore the real head.*/ 00078 #ifdef NO_DECLTYPE 00079 #define _SV(elt,list) _tmp = (char*)(list); {char **_alias = (char**)&(list); *_alias = (elt); } 00080 #define _NEXT(elt,list) ((char*)((list)->next)) 00081 #define _NEXTASGN(elt,list,to) { char **_alias = (char**)&((list)->next); *_alias=(char*)(to); } 00082 #define _PREV(elt,list) ((char*)((list)->prev)) 00083 #define _PREVASGN(elt,list,to) { char **_alias = (char**)&((list)->prev); *_alias=(char*)(to); } 00084 #define _RS(list) { char **_alias = (char**)&(list); *_alias=_tmp; } 00085 #define _CASTASGN(a,b) { char **_alias = (char**)&(a); *_alias=(char*)(b); } 00086 #else 00087 #define _SV(elt,list) 00088 #define _NEXT(elt,list) ((elt)->next) 00089 #define _NEXTASGN(elt,list,to) ((elt)->next)=(to) 00090 #define _PREV(elt,list) ((elt)->prev) 00091 #define _PREVASGN(elt,list,to) ((elt)->prev)=(to) 00092 #define _RS(list) 00093 #define _CASTASGN(a,b) (a)=(b) 00094 #endif 00095 00096 /****************************************************************************** 00097 * The sort macro is an adaptation of Simon Tatham's O(n log(n)) mergesort * 00098 * Unwieldy variable names used here to avoid shadowing passed-in variables. * 00099 *****************************************************************************/ 00100 #define LL_SORT(list, cmp) \ 00101 do { \ 00102 LDECLTYPE(list) _ls_p; \ 00103 LDECLTYPE(list) _ls_q; \ 00104 LDECLTYPE(list) _ls_e; \ 00105 LDECLTYPE(list) _ls_tail; \ 00106 LDECLTYPE(list) _ls_oldhead; \ 00107 LDECLTYPE(list) _tmp; \ 00108 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \ 00109 if (list) { \ 00110 _ls_insize = 1; \ 00111 _ls_looping = 1; \ 00112 while (_ls_looping) { \ 00113 _CASTASGN(_ls_p,list); \ 00114 _CASTASGN(_ls_oldhead,list); \ 00115 list = NULL; \ 00116 _ls_tail = NULL; \ 00117 _ls_nmerges = 0; \ 00118 while (_ls_p) { \ 00119 _ls_nmerges++; \ 00120 _ls_q = _ls_p; \ 00121 _ls_psize = 0; \ 00122 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \ 00123 _ls_psize++; \ 00124 _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); \ 00125 if (!_ls_q) break; \ 00126 } \ 00127 _ls_qsize = _ls_insize; \ 00128 while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \ 00129 if (_ls_psize == 0) { \ 00130 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \ 00131 } else if (_ls_qsize == 0 || !_ls_q) { \ 00132 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \ 00133 } else if (cmp(_ls_p,_ls_q) <= 0) { \ 00134 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \ 00135 } else { \ 00136 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \ 00137 } \ 00138 if (_ls_tail) { \ 00139 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e); _RS(list); \ 00140 } else { \ 00141 _CASTASGN(list,_ls_e); \ 00142 } \ 00143 _ls_tail = _ls_e; \ 00144 } \ 00145 _ls_p = _ls_q; \ 00146 } \ 00147 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL); _RS(list); \ 00148 if (_ls_nmerges <= 1) { \ 00149 _ls_looping=0; \ 00150 } \ 00151 _ls_insize *= 2; \ 00152 } \ 00153 } else _tmp=NULL; /* quiet gcc unused variable warning */ \ 00154 } while (0) 00155 00156 #define DL_SORT(list, cmp) \ 00157 do { \ 00158 LDECLTYPE(list) _ls_p; \ 00159 LDECLTYPE(list) _ls_q; \ 00160 LDECLTYPE(list) _ls_e; \ 00161 LDECLTYPE(list) _ls_tail; \ 00162 LDECLTYPE(list) _ls_oldhead; \ 00163 LDECLTYPE(list) _tmp; \ 00164 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \ 00165 if (list) { \ 00166 _ls_insize = 1; \ 00167 _ls_looping = 1; \ 00168 while (_ls_looping) { \ 00169 _CASTASGN(_ls_p,list); \ 00170 _CASTASGN(_ls_oldhead,list); \ 00171 list = NULL; \ 00172 _ls_tail = NULL; \ 00173 _ls_nmerges = 0; \ 00174 while (_ls_p) { \ 00175 _ls_nmerges++; \ 00176 _ls_q = _ls_p; \ 00177 _ls_psize = 0; \ 00178 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \ 00179 _ls_psize++; \ 00180 _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); \ 00181 if (!_ls_q) break; \ 00182 } \ 00183 _ls_qsize = _ls_insize; \ 00184 while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \ 00185 if (_ls_psize == 0) { \ 00186 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \ 00187 } else if (_ls_qsize == 0 || !_ls_q) { \ 00188 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \ 00189 } else if (cmp(_ls_p,_ls_q) <= 0) { \ 00190 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \ 00191 } else { \ 00192 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \ 00193 } \ 00194 if (_ls_tail) { \ 00195 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e); _RS(list); \ 00196 } else { \ 00197 _CASTASGN(list,_ls_e); \ 00198 } \ 00199 _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail); _RS(list); \ 00200 _ls_tail = _ls_e; \ 00201 } \ 00202 _ls_p = _ls_q; \ 00203 } \ 00204 _CASTASGN(list->prev, _ls_tail); \ 00205 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL); _RS(list); \ 00206 if (_ls_nmerges <= 1) { \ 00207 _ls_looping=0; \ 00208 } \ 00209 _ls_insize *= 2; \ 00210 } \ 00211 } else _tmp=NULL; /* quiet gcc unused variable warning */ \ 00212 } while (0) 00213 00214 #define CDL_SORT(list, cmp) \ 00215 do { \ 00216 LDECLTYPE(list) _ls_p; \ 00217 LDECLTYPE(list) _ls_q; \ 00218 LDECLTYPE(list) _ls_e; \ 00219 LDECLTYPE(list) _ls_tail; \ 00220 LDECLTYPE(list) _ls_oldhead; \ 00221 LDECLTYPE(list) _tmp; \ 00222 LDECLTYPE(list) _tmp2; \ 00223 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \ 00224 if (list) { \ 00225 _ls_insize = 1; \ 00226 _ls_looping = 1; \ 00227 while (_ls_looping) { \ 00228 _CASTASGN(_ls_p,list); \ 00229 _CASTASGN(_ls_oldhead,list); \ 00230 list = NULL; \ 00231 _ls_tail = NULL; \ 00232 _ls_nmerges = 0; \ 00233 while (_ls_p) { \ 00234 _ls_nmerges++; \ 00235 _ls_q = _ls_p; \ 00236 _ls_psize = 0; \ 00237 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \ 00238 _ls_psize++; \ 00239 _SV(_ls_q,list); \ 00240 if (_NEXT(_ls_q,list) == _ls_oldhead) { \ 00241 _ls_q = NULL; \ 00242 } else { \ 00243 _ls_q = _NEXT(_ls_q,list); \ 00244 } \ 00245 _RS(list); \ 00246 if (!_ls_q) break; \ 00247 } \ 00248 _ls_qsize = _ls_insize; \ 00249 while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \ 00250 if (_ls_psize == 0) { \ 00251 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \ 00252 if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \ 00253 } else if (_ls_qsize == 0 || !_ls_q) { \ 00254 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \ 00255 if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \ 00256 } else if (cmp(_ls_p,_ls_q) <= 0) { \ 00257 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \ 00258 if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \ 00259 } else { \ 00260 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \ 00261 if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \ 00262 } \ 00263 if (_ls_tail) { \ 00264 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e); _RS(list); \ 00265 } else { \ 00266 _CASTASGN(list,_ls_e); \ 00267 } \ 00268 _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail); _RS(list); \ 00269 _ls_tail = _ls_e; \ 00270 } \ 00271 _ls_p = _ls_q; \ 00272 } \ 00273 _CASTASGN(list->prev,_ls_tail); \ 00274 _CASTASGN(_tmp2,list); \ 00275 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_tmp2); _RS(list); \ 00276 if (_ls_nmerges <= 1) { \ 00277 _ls_looping=0; \ 00278 } \ 00279 _ls_insize *= 2; \ 00280 } \ 00281 } else _tmp=NULL; /* quiet gcc unused variable warning */ \ 00282 } while (0) 00283 00284 /****************************************************************************** 00285 * singly linked list macros (non-circular) * 00286 *****************************************************************************/ 00287 #define LL_PREPEND(head,add) \ 00288 do { \ 00289 (add)->next = head; \ 00290 head = add; \ 00291 } while (0) 00292 00293 #define LL_APPEND(head,add) \ 00294 do { \ 00295 LDECLTYPE(head) _tmp; \ 00296 (add)->next=NULL; \ 00297 if (head) { \ 00298 _tmp = head; \ 00299 while (_tmp->next) { _tmp = _tmp->next; } \ 00300 _tmp->next=(add); \ 00301 } else { \ 00302 (head)=(add); \ 00303 } \ 00304 } while (0) 00305 00306 #define LL_DELETE(head,del) \ 00307 do { \ 00308 LDECLTYPE(head) _tmp; \ 00309 if ((head) == (del)) { \ 00310 (head)=(head)->next; \ 00311 } else { \ 00312 _tmp = head; \ 00313 while (_tmp->next && (_tmp->next != (del))) { \ 00314 _tmp = _tmp->next; \ 00315 } \ 00316 if (_tmp->next) { \ 00317 _tmp->next = ((del)->next); \ 00318 } \ 00319 } \ 00320 } while (0) 00321 00322 /* Here are VS2008 replacements for LL_APPEND and LL_DELETE */ 00323 #define LL_APPEND_VS2008(head,add) \ 00324 do { \ 00325 if (head) { \ 00326 (add)->next = head; /* use add->next as a temp variable */ \ 00327 while ((add)->next->next) { (add)->next = (add)->next->next; } \ 00328 (add)->next->next=(add); \ 00329 } else { \ 00330 (head)=(add); \ 00331 } \ 00332 (add)->next=NULL; \ 00333 } while (0) 00334 00335 #define LL_DELETE_VS2008(head,del) \ 00336 do { \ 00337 if ((head) == (del)) { \ 00338 (head)=(head)->next; \ 00339 } else { \ 00340 char *_tmp = (char*)(head); \ 00341 while (head->next && (head->next != (del))) { \ 00342 head = head->next; \ 00343 } \ 00344 if (head->next) { \ 00345 head->next = ((del)->next); \ 00346 } \ 00347 { \ 00348 char **_head_alias = (char**)&(head); \ 00349 *_head_alias = _tmp; \ 00350 } \ 00351 } \ 00352 } while (0) 00353 #ifdef NO_DECLTYPE 00354 #undef LL_APPEND 00355 #define LL_APPEND LL_APPEND_VS2008 00356 #undef LL_DELETE 00357 #define LL_DELETE LL_DELETE_VS2008 00358 #endif 00359 /* end VS2008 replacements */ 00360 00361 #define LL_FOREACH(head,el) \ 00362 for(el=head;el;el=el->next) 00363 00364 #define LL_FOREACH_SAFE(head,el,tmp) \ 00365 for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp) 00366 00367 #define LL_SEARCH_SCALAR(head,out,field,val) \ 00368 do { \ 00369 LL_FOREACH(head,out) { \ 00370 if ((out)->field == (val)) break; \ 00371 } \ 00372 } while(0) 00373 00374 #define LL_SEARCH(head,out,elt,cmp) \ 00375 do { \ 00376 LL_FOREACH(head,out) { \ 00377 if ((cmp(out,elt))==0) break; \ 00378 } \ 00379 } while(0) 00380 00381 /****************************************************************************** 00382 * doubly linked list macros (non-circular) * 00383 *****************************************************************************/ 00384 #define DL_PREPEND(head,add) \ 00385 do { \ 00386 (add)->next = head; \ 00387 if (head) { \ 00388 (add)->prev = (head)->prev; \ 00389 (head)->prev = (add); \ 00390 } else { \ 00391 (add)->prev = (add); \ 00392 } \ 00393 (head) = (add); \ 00394 } while (0) 00395 00396 #define DL_APPEND(head,add) \ 00397 do { \ 00398 if (head) { \ 00399 (add)->prev = (head)->prev; \ 00400 (head)->prev->next = (add); \ 00401 (head)->prev = (add); \ 00402 (add)->next = NULL; \ 00403 } else { \ 00404 (head)=(add); \ 00405 (head)->prev = (head); \ 00406 (head)->next = NULL; \ 00407 } \ 00408 } while (0); 00409 00410 #define DL_DELETE(head,del) \ 00411 do { \ 00412 if ((del)->prev == (del)) { \ 00413 (head)=NULL; \ 00414 } else if ((del)==(head)) { \ 00415 (del)->next->prev = (del)->prev; \ 00416 (head) = (del)->next; \ 00417 } else { \ 00418 (del)->prev->next = (del)->next; \ 00419 if ((del)->next) { \ 00420 (del)->next->prev = (del)->prev; \ 00421 } else { \ 00422 (head)->prev = (del)->prev; \ 00423 } \ 00424 } \ 00425 } while (0); 00426 00427 00428 #define DL_FOREACH(head,el) \ 00429 for(el=head;el;el=el->next) 00430 00431 /* this version is safe for deleting the elements during iteration */ 00432 #define DL_FOREACH_SAFE(head,el,tmp) \ 00433 for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp) 00434 00435 /* these are identical to their singly-linked list counterparts */ 00436 #define DL_SEARCH_SCALAR LL_SEARCH_SCALAR 00437 #define DL_SEARCH LL_SEARCH 00438 00439 /****************************************************************************** 00440 * circular doubly linked list macros * 00441 *****************************************************************************/ 00442 #define CDL_PREPEND(head,add) \ 00443 do { \ 00444 if (head) { \ 00445 (add)->prev = (head)->prev; \ 00446 (add)->next = (head); \ 00447 (head)->prev = (add); \ 00448 (add)->prev->next = (add); \ 00449 } else { \ 00450 (add)->prev = (add); \ 00451 (add)->next = (add); \ 00452 } \ 00453 (head)=(add); \ 00454 } while (0) 00455 00456 #define CDL_DELETE(head,del) \ 00457 do { \ 00458 if ( ((head)==(del)) && ((head)->next == (head))) { \ 00459 (head) = 0L; \ 00460 } else { \ 00461 (del)->next->prev = (del)->prev; \ 00462 (del)->prev->next = (del)->next; \ 00463 if ((del) == (head)) (head)=(del)->next; \ 00464 } \ 00465 } while (0); 00466 00467 #define CDL_FOREACH(head,el) \ 00468 for(el=head;el;el=(el->next==head ? 0L : el->next)) 00469 00470 #define CDL_FOREACH_SAFE(head,el,tmp1,tmp2) \ 00471 for((el)=(head), ((tmp1)=(head)?((head)->prev):NULL); \ 00472 (el) && ((tmp2)=(el)->next, 1); \ 00473 ((el) = (((el)==(tmp1)) ? 0L : (tmp2)))) 00474 00475 #define CDL_SEARCH_SCALAR(head,out,field,val) \ 00476 do { \ 00477 CDL_FOREACH(head,out) { \ 00478 if ((out)->field == (val)) break; \ 00479 } \ 00480 } while(0) 00481 00482 #define CDL_SEARCH(head,out,elt,cmp) \ 00483 do { \ 00484 CDL_FOREACH(head,out) { \ 00485 if ((cmp(out,elt))==0) break; \ 00486 } \ 00487 } while(0) 00488 00489 #endif /* UTLIST_H */ 00490