ESAPI-C 1.0
The OWASP Enterprise Security API for C
|
00001 00032 #ifndef UTLIST_H 00033 #define UTLIST_H 00034 00035 #define UTLIST_VERSION 1.9.1 00036 00068 /* These macros use decltype or the earlier __typeof GNU extension. 00069 As decltype is only available in newer compilers (VS2010 or gcc 4.3+ 00070 when compiling c++ code), this code uses whatever method is needed 00071 or, for VS2008 where neither is available, uses casting workarounds. */ 00072 #ifdef _MSC_VER /* MS compiler */ 00073 #if _MSC_VER >= 1600 && defined(__cplusplus) /* VS2010 or newer in C++ mode */ 00074 #define LDECLTYPE(x) decltype(x) 00075 #else /* VS2008 or older (or VS2010 in C mode) */ 00076 #define NO_DECLTYPE 00077 #define LDECLTYPE(x) char* 00078 #endif 00079 #else /* GNU, Sun and other compilers */ 00080 #define LDECLTYPE(x) __typeof(x) 00081 #endif 00082 00083 /* for VS2008 we use some workarounds to get around the lack of decltype, 00084 * namely, we always reassign our tmp variable to the list head if we need 00085 * to dereference its prev/next pointers, and save/restore the real head.*/ 00086 #ifdef NO_DECLTYPE 00087 #define _SV(elt,list) _tmp = (char*)(list); {char **_alias = (char**)&(list); *_alias = (elt); } 00088 #define _NEXT(elt,list) ((char*)((list)->next)) 00089 #define _NEXTASGN(elt,list,to) { char **_alias = (char**)&((list)->next); *_alias=(char*)(to); } 00090 #define _PREV(elt,list) ((char*)((list)->prev)) 00091 #define _PREVASGN(elt,list,to) { char **_alias = (char**)&((list)->prev); *_alias=(char*)(to); } 00092 #define _RS(list) { char **_alias = (char**)&(list); *_alias=_tmp; } 00093 #define _CASTASGN(a,b) { char **_alias = (char**)&(a); *_alias=(char*)(b); } 00094 #else 00095 #define _SV(elt,list) 00096 #define _NEXT(elt,list) ((elt)->next) 00097 #define _NEXTASGN(elt,list,to) ((elt)->next)=(to) 00098 #define _PREV(elt,list) ((elt)->prev) 00099 #define _PREVASGN(elt,list,to) ((elt)->prev)=(to) 00100 #define _RS(list) 00101 #define _CASTASGN(a,b) (a)=(b) 00102 #endif 00103 00104 /****************************************************************************** 00105 * The sort macro is an adaptation of Simon Tatham's O(n log(n)) mergesort * 00106 * Unwieldy variable names used here to avoid shadowing passed-in variables. * 00107 *****************************************************************************/ 00108 #define LL_SORT(list, cmp) \ 00109 do { \ 00110 LDECLTYPE(list) _ls_p; \ 00111 LDECLTYPE(list) _ls_q; \ 00112 LDECLTYPE(list) _ls_e; \ 00113 LDECLTYPE(list) _ls_tail; \ 00114 LDECLTYPE(list) _ls_oldhead; \ 00115 LDECLTYPE(list) _tmp; \ 00116 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \ 00117 if (list) { \ 00118 _ls_insize = 1; \ 00119 _ls_looping = 1; \ 00120 while (_ls_looping) { \ 00121 _CASTASGN(_ls_p,list); \ 00122 _CASTASGN(_ls_oldhead,list); \ 00123 list = NULL; \ 00124 _ls_tail = NULL; \ 00125 _ls_nmerges = 0; \ 00126 while (_ls_p) { \ 00127 _ls_nmerges++; \ 00128 _ls_q = _ls_p; \ 00129 _ls_psize = 0; \ 00130 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \ 00131 _ls_psize++; \ 00132 _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); \ 00133 if (!_ls_q) break; \ 00134 } \ 00135 _ls_qsize = _ls_insize; \ 00136 while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \ 00137 if (_ls_psize == 0) { \ 00138 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \ 00139 } else if (_ls_qsize == 0 || !_ls_q) { \ 00140 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \ 00141 } else if (cmp(_ls_p,_ls_q) <= 0) { \ 00142 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \ 00143 } else { \ 00144 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \ 00145 } \ 00146 if (_ls_tail) { \ 00147 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e); _RS(list); \ 00148 } else { \ 00149 _CASTASGN(list,_ls_e); \ 00150 } \ 00151 _ls_tail = _ls_e; \ 00152 } \ 00153 _ls_p = _ls_q; \ 00154 } \ 00155 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL); _RS(list); \ 00156 if (_ls_nmerges <= 1) { \ 00157 _ls_looping=0; \ 00158 } \ 00159 _ls_insize *= 2; \ 00160 } \ 00161 } else _tmp=NULL; /* quiet gcc unused variable warning */ \ 00162 } while (0) 00163 00164 #define DL_SORT(list, cmp) \ 00165 do { \ 00166 LDECLTYPE(list) _ls_p; \ 00167 LDECLTYPE(list) _ls_q; \ 00168 LDECLTYPE(list) _ls_e; \ 00169 LDECLTYPE(list) _ls_tail; \ 00170 LDECLTYPE(list) _ls_oldhead; \ 00171 LDECLTYPE(list) _tmp; \ 00172 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \ 00173 if (list) { \ 00174 _ls_insize = 1; \ 00175 _ls_looping = 1; \ 00176 while (_ls_looping) { \ 00177 _CASTASGN(_ls_p,list); \ 00178 _CASTASGN(_ls_oldhead,list); \ 00179 list = NULL; \ 00180 _ls_tail = NULL; \ 00181 _ls_nmerges = 0; \ 00182 while (_ls_p) { \ 00183 _ls_nmerges++; \ 00184 _ls_q = _ls_p; \ 00185 _ls_psize = 0; \ 00186 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \ 00187 _ls_psize++; \ 00188 _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); \ 00189 if (!_ls_q) break; \ 00190 } \ 00191 _ls_qsize = _ls_insize; \ 00192 while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \ 00193 if (_ls_psize == 0) { \ 00194 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \ 00195 } else if (_ls_qsize == 0 || !_ls_q) { \ 00196 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \ 00197 } else if (cmp(_ls_p,_ls_q) <= 0) { \ 00198 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \ 00199 } else { \ 00200 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \ 00201 } \ 00202 if (_ls_tail) { \ 00203 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e); _RS(list); \ 00204 } else { \ 00205 _CASTASGN(list,_ls_e); \ 00206 } \ 00207 _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail); _RS(list); \ 00208 _ls_tail = _ls_e; \ 00209 } \ 00210 _ls_p = _ls_q; \ 00211 } \ 00212 _CASTASGN(list->prev, _ls_tail); \ 00213 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL); _RS(list); \ 00214 if (_ls_nmerges <= 1) { \ 00215 _ls_looping=0; \ 00216 } \ 00217 _ls_insize *= 2; \ 00218 } \ 00219 } else _tmp=NULL; /* quiet gcc unused variable warning */ \ 00220 } while (0) 00221 00222 #define CDL_SORT(list, cmp) \ 00223 do { \ 00224 LDECLTYPE(list) _ls_p; \ 00225 LDECLTYPE(list) _ls_q; \ 00226 LDECLTYPE(list) _ls_e; \ 00227 LDECLTYPE(list) _ls_tail; \ 00228 LDECLTYPE(list) _ls_oldhead; \ 00229 LDECLTYPE(list) _tmp; \ 00230 LDECLTYPE(list) _tmp2; \ 00231 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \ 00232 if (list) { \ 00233 _ls_insize = 1; \ 00234 _ls_looping = 1; \ 00235 while (_ls_looping) { \ 00236 _CASTASGN(_ls_p,list); \ 00237 _CASTASGN(_ls_oldhead,list); \ 00238 list = NULL; \ 00239 _ls_tail = NULL; \ 00240 _ls_nmerges = 0; \ 00241 while (_ls_p) { \ 00242 _ls_nmerges++; \ 00243 _ls_q = _ls_p; \ 00244 _ls_psize = 0; \ 00245 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \ 00246 _ls_psize++; \ 00247 _SV(_ls_q,list); \ 00248 if (_NEXT(_ls_q,list) == _ls_oldhead) { \ 00249 _ls_q = NULL; \ 00250 } else { \ 00251 _ls_q = _NEXT(_ls_q,list); \ 00252 } \ 00253 _RS(list); \ 00254 if (!_ls_q) break; \ 00255 } \ 00256 _ls_qsize = _ls_insize; \ 00257 while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \ 00258 if (_ls_psize == 0) { \ 00259 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \ 00260 if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \ 00261 } else if (_ls_qsize == 0 || !_ls_q) { \ 00262 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \ 00263 if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \ 00264 } else if (cmp(_ls_p,_ls_q) <= 0) { \ 00265 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \ 00266 if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \ 00267 } else { \ 00268 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \ 00269 if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \ 00270 } \ 00271 if (_ls_tail) { \ 00272 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e); _RS(list); \ 00273 } else { \ 00274 _CASTASGN(list,_ls_e); \ 00275 } \ 00276 _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail); _RS(list); \ 00277 _ls_tail = _ls_e; \ 00278 } \ 00279 _ls_p = _ls_q; \ 00280 } \ 00281 _CASTASGN(list->prev,_ls_tail); \ 00282 _CASTASGN(_tmp2,list); \ 00283 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_tmp2); _RS(list); \ 00284 if (_ls_nmerges <= 1) { \ 00285 _ls_looping=0; \ 00286 } \ 00287 _ls_insize *= 2; \ 00288 } \ 00289 } else _tmp=NULL; /* quiet gcc unused variable warning */ \ 00290 } while (0) 00291 00292 /****************************************************************************** 00293 * singly linked list macros (non-circular) * 00294 *****************************************************************************/ 00295 #define LL_PREPEND(head,add) \ 00296 do { \ 00297 (add)->next = head; \ 00298 head = add; \ 00299 } while (0) 00300 00301 #define LL_APPEND(head,add) \ 00302 do { \ 00303 LDECLTYPE(head) _tmp; \ 00304 (add)->next=NULL; \ 00305 if (head) { \ 00306 _tmp = head; \ 00307 while (_tmp->next) { _tmp = _tmp->next; } \ 00308 _tmp->next=(add); \ 00309 } else { \ 00310 (head)=(add); \ 00311 } \ 00312 } while (0) 00313 00314 #define LL_DELETE(head,del) \ 00315 do { \ 00316 LDECLTYPE(head) _tmp; \ 00317 if ((head) == (del)) { \ 00318 (head)=(head)->next; \ 00319 } else { \ 00320 _tmp = head; \ 00321 while (_tmp->next && (_tmp->next != (del))) { \ 00322 _tmp = _tmp->next; \ 00323 } \ 00324 if (_tmp->next) { \ 00325 _tmp->next = ((del)->next); \ 00326 } \ 00327 } \ 00328 } while (0) 00329 00330 /* Here are VS2008 replacements for LL_APPEND and LL_DELETE */ 00331 #define LL_APPEND_VS2008(head,add) \ 00332 do { \ 00333 if (head) { \ 00334 (add)->next = head; /* use add->next as a temp variable */ \ 00335 while ((add)->next->next) { (add)->next = (add)->next->next; } \ 00336 (add)->next->next=(add); \ 00337 } else { \ 00338 (head)=(add); \ 00339 } \ 00340 (add)->next=NULL; \ 00341 } while (0) 00342 00343 #define LL_DELETE_VS2008(head,del) \ 00344 do { \ 00345 if ((head) == (del)) { \ 00346 (head)=(head)->next; \ 00347 } else { \ 00348 char *_tmp = (char*)(head); \ 00349 while (head->next && (head->next != (del))) { \ 00350 head = head->next; \ 00351 } \ 00352 if (head->next) { \ 00353 head->next = ((del)->next); \ 00354 } \ 00355 { \ 00356 char **_head_alias = (char**)&(head); \ 00357 *_head_alias = _tmp; \ 00358 } \ 00359 } \ 00360 } while (0) 00361 #ifdef NO_DECLTYPE 00362 #undef LL_APPEND 00363 #define LL_APPEND LL_APPEND_VS2008 00364 #undef LL_DELETE 00365 #define LL_DELETE LL_DELETE_VS2008 00366 #endif 00367 /* end VS2008 replacements */ 00368 00369 #define LL_FOREACH(head,el) \ 00370 for(el=head;el;el=el->next) 00371 00372 #define LL_FOREACH_SAFE(head,el,tmp) \ 00373 for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp) 00374 00375 #define LL_SEARCH_SCALAR(head,out,field,val) \ 00376 do { \ 00377 LL_FOREACH(head,out) { \ 00378 if ((out)->field == (val)) break; \ 00379 } \ 00380 } while(0) 00381 00382 #define LL_SEARCH(head,out,elt,cmp) \ 00383 do { \ 00384 LL_FOREACH(head,out) { \ 00385 if ((cmp(out,elt))==0) break; \ 00386 } \ 00387 } while(0) 00388 00389 /****************************************************************************** 00390 * doubly linked list macros (non-circular) * 00391 *****************************************************************************/ 00392 #define DL_PREPEND(head,add) \ 00393 do { \ 00394 (add)->next = head; \ 00395 if (head) { \ 00396 (add)->prev = (head)->prev; \ 00397 (head)->prev = (add); \ 00398 } else { \ 00399 (add)->prev = (add); \ 00400 } \ 00401 (head) = (add); \ 00402 } while (0) 00403 00404 #define DL_APPEND(head,add) \ 00405 do { \ 00406 if (head) { \ 00407 (add)->prev = (head)->prev; \ 00408 (head)->prev->next = (add); \ 00409 (head)->prev = (add); \ 00410 (add)->next = NULL; \ 00411 } else { \ 00412 (head)=(add); \ 00413 (head)->prev = (head); \ 00414 (head)->next = NULL; \ 00415 } \ 00416 } while (0); 00417 00418 #define DL_DELETE(head,del) \ 00419 do { \ 00420 if ((del)->prev == (del)) { \ 00421 (head)=NULL; \ 00422 } else if ((del)==(head)) { \ 00423 (del)->next->prev = (del)->prev; \ 00424 (head) = (del)->next; \ 00425 } else { \ 00426 (del)->prev->next = (del)->next; \ 00427 if ((del)->next) { \ 00428 (del)->next->prev = (del)->prev; \ 00429 } else { \ 00430 (head)->prev = (del)->prev; \ 00431 } \ 00432 } \ 00433 } while (0); 00434 00435 00436 #define DL_FOREACH(head,el) \ 00437 for(el=head;el;el=el->next) 00438 00439 /* this version is safe for deleting the elements during iteration */ 00440 #define DL_FOREACH_SAFE(head,el,tmp) \ 00441 for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp) 00442 00443 /* these are identical to their singly-linked list counterparts */ 00444 #define DL_SEARCH_SCALAR LL_SEARCH_SCALAR 00445 #define DL_SEARCH LL_SEARCH 00446 00447 /****************************************************************************** 00448 * circular doubly linked list macros * 00449 *****************************************************************************/ 00450 #define CDL_PREPEND(head,add) \ 00451 do { \ 00452 if (head) { \ 00453 (add)->prev = (head)->prev; \ 00454 (add)->next = (head); \ 00455 (head)->prev = (add); \ 00456 (add)->prev->next = (add); \ 00457 } else { \ 00458 (add)->prev = (add); \ 00459 (add)->next = (add); \ 00460 } \ 00461 (head)=(add); \ 00462 } while (0) 00463 00464 #define CDL_DELETE(head,del) \ 00465 do { \ 00466 if ( ((head)==(del)) && ((head)->next == (head))) { \ 00467 (head) = 0L; \ 00468 } else { \ 00469 (del)->next->prev = (del)->prev; \ 00470 (del)->prev->next = (del)->next; \ 00471 if ((del) == (head)) (head)=(del)->next; \ 00472 } \ 00473 } while (0); 00474 00475 #define CDL_FOREACH(head,el) \ 00476 for(el=head;el;el=(el->next==head ? 0L : el->next)) 00477 00478 #define CDL_FOREACH_SAFE(head,el,tmp1,tmp2) \ 00479 for((el)=(head), ((tmp1)=(head)?((head)->prev):NULL); \ 00480 (el) && ((tmp2)=(el)->next, 1); \ 00481 ((el) = (((el)==(tmp1)) ? 0L : (tmp2)))) 00482 00483 #define CDL_SEARCH_SCALAR(head,out,field,val) \ 00484 do { \ 00485 CDL_FOREACH(head,out) { \ 00486 if ((out)->field == (val)) break; \ 00487 } \ 00488 } while(0) 00489 00490 #define CDL_SEARCH(head,out,elt,cmp) \ 00491 do { \ 00492 CDL_FOREACH(head,out) { \ 00493 if ((cmp(out,elt))==0) break; \ 00494 } \ 00495 } while(0) 00496 00497 #endif /* UTLIST_H */ 00498