ESAPI-C 1.0
The OWASP Enterprise Security API for C

utlist.h

Go to the documentation of this file.
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 
 All Data Structures Files Functions Variables Typedefs Defines