Back to home page

Enduro/X
 
 

     

0001 /*
0002 Copyright (c) 2007-2010, Troy D. Hanson   http://exhash.sourceforge.net
0003 All rights reserved.
0004 
0005 Redistribution and use in source and binary forms, with or without
0006 modification, are permitted provided that the following conditions are met:
0007 
0008     * Redistributions of source code must retain the above copyright
0009       notice, this list of conditions and the following disclaimer.
0010 
0011 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
0012 IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
0013 TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
0014 PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
0015 OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
0016 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
0017 PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
0018 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
0019 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
0020 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
0021 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
0022 */
0023 
0024 #ifndef UTLIST_INT_H
0025 #define UTLIST_INT_H
0026 
0027 #define UTLIST_VERSION 1.9.1
0028 
0029 /* 
0030  * This file contains macros to manipulate singly and doubly-linked lists.
0031  *
0032  * 1. LL_ macros:  singly-linked lists.
0033  * 2. DL_ macros:  doubly-linked lists.
0034  * 3. CDL_ macros: circular doubly-linked lists.
0035  *
0036  * To use singly-linked lists, your structure must have a "NDRX_NEXT" pointer.
0037  * To use doubly-linked lists, your structure must "NDRX_PREV" and "NDRX_NEXT" pointers.
0038  * Either way, the pointer to the head of the list must be initialized to NULL.
0039  * 
0040  * ----------------.EXAMPLE -------------------------
0041  * struct item {
0042  *      int id;
0043  *      struct item *NDRX_PREV, *NDRX_NEXT;
0044  * }
0045  *
0046  * struct item *list = NULL:
0047  *
0048  * int main() {
0049  *      struct item *item;
0050  *      ... allocate and populate item ...
0051  *      DL_APPEND(list, item);
0052  * }
0053  * --------------------------------------------------
0054  *
0055  * For doubly-linked lists, the append and delete macros are O(1)
0056  * For singly-linked lists, append and delete are O(n) but prepend is O(1)
0057  * The sort macro is O(n log(n)) for all types of single/double/circular lists.
0058  */
0059 
0060 /* These macros use decltype or the earlier __typeof GNU extension.
0061    As decltype is only available in newer compilers (VS2010 or gcc 4.3+
0062    when compiling c++ code), this code uses whatever method is needed
0063    or, for VS2008 where neither is available, uses casting workarounds. */
0064 #ifdef _MSC_VER            /* MS compiler */
0065 #if _MSC_VER >= 1600 && defined(__cplusplus)  /* VS2010 or newer in C++ mode */
0066 #define LDECLTYPE(x) decltype(x)
0067 #else                     /* VS2008 or older (or VS2010 in C mode) */
0068 #define NO_DECLTYPE
0069 #define LDECLTYPE(x) char*
0070 #endif
0071 #else                      /* GNU, Sun and other compilers */
0072 #define LDECLTYPE(x) __typeof(x)
0073 #endif
0074 
0075 /* for VS2008 we use some workarounds to get around the lack of decltype,
0076  * namely, we always reassign our tmp variable to the list head if we need
0077  * to dereference its NDRX_PREV/NDRX_NEXT pointers, and save/restore the real head.*/
0078 #ifdef NO_DECLTYPE
0079 #define _SV(elt,list) _tmp = (char*)(list); {char **_alias = (char**)&(list); *_alias = (elt); }
0080 #define _NEXT(elt,list) ((char*)((list)->NDRX_NEXT))
0081 #define _NEXTASGN(elt,list,to) { char **_alias = (char**)&((list)->NDRX_NEXT); *_alias=(char*)(to); }
0082 #define _PREV(elt,list) ((char*)((list)->NDRX_PREV))
0083 #define _PREVASGN(elt,list,to) { char **_alias = (char**)&((list)->NDRX_PREV); *_alias=(char*)(to); }
0084 #define _RS(list) { char **_alias = (char**)&(list); *_alias=_tmp; }
0085 #define _CASTASGN(a,b) { char **_alias = (char**)&(a); *_alias=(char*)(b); }
0086 #else 
0087 #define _SV(elt,list)
0088 #define _NEXT(elt,list) ((elt)->NDRX_NEXT)
0089 #define _NEXTASGN(elt,list,to) ((elt)->NDRX_NEXT)=(to)
0090 #define _PREV(elt,list) ((elt)->NDRX_PREV)
0091 #define _PREVASGN(elt,list,to) ((elt)->NDRX_PREV)=(to)
0092 #define _RS(list)
0093 #define _CASTASGN(a,b) (a)=(b)
0094 #endif
0095 
0096 /******************************************************************************
0097  * The sort macro is an adaptation of Simon Tatham's O(n log(n)) mergesort    *
0098  * Unwieldy variable names used here to avoid shadowing passed-in variables.  *
0099  *****************************************************************************/
0100 #define LL_SORT(list, cmp)                                                                     \
0101 do {                                                                                           \
0102   LDECLTYPE(list) _ls_p;                                                                       \
0103   LDECLTYPE(list) _ls_q;                                                                       \
0104   LDECLTYPE(list) _ls_e;                                                                       \
0105   LDECLTYPE(list) _ls_tail;                                                                    \
0106   LDECLTYPE(list) _ls_oldhead;                                                                 \
0107   LDECLTYPE(list) _tmp;                                                                        \
0108   int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping;                       \
0109   if (list) {                                                                                  \
0110     _ls_insize = 1;                                                                            \
0111     _ls_looping = 1;                                                                           \
0112     while (_ls_looping) {                                                                      \
0113       _CASTASGN(_ls_p,list);                                                                   \
0114       _CASTASGN(_ls_oldhead,list);                                                             \
0115       list = NULL;                                                                             \
0116       _ls_tail = NULL;                                                                         \
0117       _ls_nmerges = 0;                                                                         \
0118       while (_ls_p) {                                                                          \
0119         _ls_nmerges++;                                                                         \
0120         _ls_q = _ls_p;                                                                         \
0121         _ls_psize = 0;                                                                         \
0122         for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) {                                         \
0123           _ls_psize++;                                                                         \
0124           _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list);                               \
0125           if (!_ls_q) break;                                                                   \
0126         }                                                                                      \
0127         _ls_qsize = _ls_insize;                                                                \
0128         while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) {                                    \
0129           if (_ls_psize == 0) {                                                                \
0130             _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \
0131           } else if (_ls_qsize == 0 || !_ls_q) {                                               \
0132             _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \
0133           } else if (cmp(_ls_p,_ls_q) <= 0) {                                                  \
0134             _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \
0135           } else {                                                                             \
0136             _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \
0137           }                                                                                    \
0138           if (_ls_tail) {                                                                      \
0139             _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e); _RS(list);                     \
0140           } else {                                                                             \
0141             _CASTASGN(list,_ls_e);                                                             \
0142           }                                                                                    \
0143           _ls_tail = _ls_e;                                                                    \
0144         }                                                                                      \
0145         _ls_p = _ls_q;                                                                         \
0146       }                                                                                        \
0147       _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL); _RS(list);                            \
0148       if (_ls_nmerges <= 1) {                                                                  \
0149         _ls_looping=0;                                                                         \
0150       }                                                                                        \
0151       _ls_insize *= 2;                                                                         \
0152     }                                                                                          \
0153   } else _tmp=NULL; /* quiet gcc unused variable warning */                                    \
0154 } while (0)
0155 
0156 #define DL_SORT(list, cmp)                                                                     \
0157 do {                                                                                           \
0158   LDECLTYPE(list) _ls_p;                                                                       \
0159   LDECLTYPE(list) _ls_q;                                                                       \
0160   LDECLTYPE(list) _ls_e;                                                                       \
0161   LDECLTYPE(list) _ls_tail;                                                                    \
0162   LDECLTYPE(list) _ls_oldhead;                                                                 \
0163   LDECLTYPE(list) _tmp;                                                                        \
0164   int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping;                       \
0165   if (list) {                                                                                  \
0166     _ls_insize = 1;                                                                            \
0167     _ls_looping = 1;                                                                           \
0168     while (_ls_looping) {                                                                      \
0169       _CASTASGN(_ls_p,list);                                                                   \
0170       _CASTASGN(_ls_oldhead,list);                                                             \
0171       list = NULL;                                                                             \
0172       _ls_tail = NULL;                                                                         \
0173       _ls_nmerges = 0;                                                                         \
0174       while (_ls_p) {                                                                          \
0175         _ls_nmerges++;                                                                         \
0176         _ls_q = _ls_p;                                                                         \
0177         _ls_psize = 0;                                                                         \
0178         for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) {                                         \
0179           _ls_psize++;                                                                         \
0180           _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list);                               \
0181           if (!_ls_q) break;                                                                   \
0182         }                                                                                      \
0183         _ls_qsize = _ls_insize;                                                                \
0184         while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) {                                    \
0185           if (_ls_psize == 0) {                                                                \
0186             _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \
0187           } else if (_ls_qsize == 0 || !_ls_q) {                                               \
0188             _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \
0189           } else if (cmp(_ls_p,_ls_q) <= 0) {                                                  \
0190             _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \
0191           } else {                                                                             \
0192             _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \
0193           }                                                                                    \
0194           if (_ls_tail) {                                                                      \
0195             _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e); _RS(list);                     \
0196           } else {                                                                             \
0197             _CASTASGN(list,_ls_e);                                                             \
0198           }                                                                                    \
0199           _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail); _RS(list);                          \
0200           _ls_tail = _ls_e;                                                                    \
0201         }                                                                                      \
0202         _ls_p = _ls_q;                                                                         \
0203       }                                                                                        \
0204       _CASTASGN(list->NDRX_PREV, _ls_tail);                                                    \
0205       _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL); _RS(list);                            \
0206       if (_ls_nmerges <= 1) {                                                                  \
0207         _ls_looping=0;                                                                         \
0208       }                                                                                        \
0209       _ls_insize *= 2;                                                                         \
0210     }                                                                                          \
0211   } else _tmp=NULL; /* quiet gcc unused variable warning */                                    \
0212 } while (0)
0213 
0214 #define CDL_SORT(list, cmp)                                                                    \
0215 do {                                                                                           \
0216   LDECLTYPE(list) _ls_p;                                                                       \
0217   LDECLTYPE(list) _ls_q;                                                                       \
0218   LDECLTYPE(list) _ls_e;                                                                       \
0219   LDECLTYPE(list) _ls_tail;                                                                    \
0220   LDECLTYPE(list) _ls_oldhead;                                                                 \
0221   LDECLTYPE(list) _tmp;                                                                        \
0222   LDECLTYPE(list) _tmp2;                                                                       \
0223   int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping;                       \
0224   if (list) {                                                                                  \
0225     _ls_insize = 1;                                                                            \
0226     _ls_looping = 1;                                                                           \
0227     while (_ls_looping) {                                                                      \
0228       _CASTASGN(_ls_p,list);                                                                   \
0229       _CASTASGN(_ls_oldhead,list);                                                             \
0230       list = NULL;                                                                             \
0231       _ls_tail = NULL;                                                                         \
0232       _ls_nmerges = 0;                                                                         \
0233       while (_ls_p) {                                                                          \
0234         _ls_nmerges++;                                                                         \
0235         _ls_q = _ls_p;                                                                         \
0236         _ls_psize = 0;                                                                         \
0237         for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) {                                         \
0238           _ls_psize++;                                                                         \
0239           _SV(_ls_q,list);                                                                     \
0240           if (_NEXT(_ls_q,list) == _ls_oldhead) {                                              \
0241             _ls_q = NULL;                                                                      \
0242           } else {                                                                             \
0243             _ls_q = _NEXT(_ls_q,list);                                                         \
0244           }                                                                                    \
0245           _RS(list);                                                                           \
0246           if (!_ls_q) break;                                                                   \
0247         }                                                                                      \
0248         _ls_qsize = _ls_insize;                                                                \
0249         while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) {                                    \
0250           if (_ls_psize == 0) {                                                                \
0251             _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \
0252             if (_ls_q == _ls_oldhead) { _ls_q = NULL; }                                        \
0253           } else if (_ls_qsize == 0 || !_ls_q) {                                               \
0254             _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \
0255             if (_ls_p == _ls_oldhead) { _ls_p = NULL; }                                        \
0256           } else if (cmp(_ls_p,_ls_q) <= 0) {                                                  \
0257             _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \
0258             if (_ls_p == _ls_oldhead) { _ls_p = NULL; }                                        \
0259           } else {                                                                             \
0260             _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \
0261             if (_ls_q == _ls_oldhead) { _ls_q = NULL; }                                        \
0262           }                                                                                    \
0263           if (_ls_tail) {                                                                      \
0264             _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e); _RS(list);                     \
0265           } else {                                                                             \
0266             _CASTASGN(list,_ls_e);                                                             \
0267           }                                                                                    \
0268           _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail); _RS(list);                          \
0269           _ls_tail = _ls_e;                                                                    \
0270         }                                                                                      \
0271         _ls_p = _ls_q;                                                                         \
0272       }                                                                                        \
0273       _CASTASGN(list->NDRX_PREV,_ls_tail);                                                     \
0274       _CASTASGN(_tmp2,list);                                                                   \
0275       _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_tmp2); _RS(list);                           \
0276       if (_ls_nmerges <= 1) {                                                                  \
0277         _ls_looping=0;                                                                         \
0278       }                                                                                        \
0279       _ls_insize *= 2;                                                                         \
0280     }                                                                                          \
0281   } else _tmp=NULL; /* quiet gcc unused variable warning */                                    \
0282 } while (0)
0283 
0284 /******************************************************************************
0285  * singly linked list macros (non-circular)                                   *
0286  *****************************************************************************/
0287 #define LL_PREPEND(head,add)                                                                   \
0288 do {                                                                                           \
0289   (add)->NDRX_NEXT = head;                                                                     \
0290   head = add;                                                                                  \
0291 } while (0)
0292 
0293 #define LL_APPEND(head,add)                                                                    \
0294 do {                                                                                           \
0295   LDECLTYPE(head) _tmp;                                                                        \
0296   (add)->NDRX_NEXT=NULL;                                                                       \
0297   if (head) {                                                                                  \
0298     _tmp = head;                                                                               \
0299     while (_tmp->NDRX_NEXT) { _tmp = _tmp->NDRX_NEXT; }                                        \
0300     _tmp->NDRX_NEXT=(add);                                                                     \
0301   } else {                                                                                     \
0302     (head)=(add);                                                                              \
0303   }                                                                                            \
0304 } while (0)
0305 
0306 #define LL_DELETE(head,del)                                                                    \
0307 do {                                                                                           \
0308   LDECLTYPE(head) _tmp;                                                                        \
0309   if ((head) == (del)) {                                                                       \
0310     (head)=(head)->NDRX_NEXT;                                                                  \
0311   } else {                                                                                     \
0312     _tmp = head;                                                                               \
0313     while (_tmp->NDRX_NEXT && (_tmp->NDRX_NEXT != (del))) {                                    \
0314       _tmp = _tmp->NDRX_NEXT;                                                                  \
0315     }                                                                                          \
0316     if (_tmp->NDRX_NEXT) {                                                                     \
0317       _tmp->NDRX_NEXT = ((del)->NDRX_NEXT);                                                    \
0318     }                                                                                          \
0319   }                                                                                            \
0320 } while (0)
0321 
0322 /* Here are VS2008 replacements for LL_APPEND and LL_DELETE */
0323 #define LL_APPEND_VS2008(head,add)                                                             \
0324 do {                                                                                           \
0325   if (head) {                                                                                  \
0326     (add)->NDRX_NEXT = head;     /* use add->NDRX_NEXT as a temp variable */                   \
0327     while ((add)->NDRX_NEXT->NDRX_NEXT) { (add)->NDRX_NEXT = (add)->NDRX_NEXT->NDRX_NEXT; }    \
0328     (add)->NDRX_NEXT->NDRX_NEXT=(add);                                                         \
0329   } else {                                                                                     \
0330     (head)=(add);                                                                              \
0331   }                                                                                            \
0332   (add)->NDRX_NEXT=NULL;                                                                       \
0333 } while (0)
0334 
0335 #define LL_DELETE_VS2008(head,del)                                                             \
0336 do {                                                                                           \
0337   if ((head) == (del)) {                                                                       \
0338     (head)=(head)->NDRX_NEXT;                                                                  \
0339   } else {                                                                                     \
0340     char *_tmp = (char*)(head);                                                                \
0341     while (head->NDRX_NEXT && (head->NDRX_NEXT != (del))) {                                    \
0342       head = head->NDRX_NEXT;                                                                  \
0343     }                                                                                          \
0344     if (head->NDRX_NEXT) {                                                                     \
0345       head->NDRX_NEXT = ((del)->NDRX_NEXT);                                                    \
0346     }                                                                                          \
0347     {                                                                                          \
0348       char **_head_alias = (char**)&(head);                                                    \
0349       *_head_alias = _tmp;                                                                     \
0350     }                                                                                          \
0351   }                                                                                            \
0352 } while (0)
0353 #ifdef NO_DECLTYPE
0354 #undef LL_APPEND
0355 #define LL_APPEND LL_APPEND_VS2008
0356 #undef LL_DELETE
0357 #define LL_DELETE LL_DELETE_VS2008
0358 #endif
0359 /* end VS2008 replacements */
0360 
0361 #define LL_FOREACH(head,el)                                                                    \
0362     for(el=head;el;el=el->NDRX_NEXT)
0363 
0364 #define LL_FOREACH_SAFE(head,el,tmp)                                                           \
0365   for((el)=(head);(el) && (tmp = (el)->NDRX_NEXT, 1); (el) = tmp)
0366 
0367 #define LL_SEARCH_SCALAR(head,out,field,val)                                                   \
0368 do {                                                                                           \
0369     LL_FOREACH(head,out) {                                                                     \
0370       if ((out)->field == (val)) break;                                                        \
0371     }                                                                                          \
0372 } while(0) 
0373 
0374 #define LL_SEARCH(head,out,elt,cmp)                                                            \
0375 do {                                                                                           \
0376     LL_FOREACH(head,out) {                                                                     \
0377       if ((cmp(out,elt))==0) break;                                                            \
0378     }                                                                                          \
0379 } while(0) 
0380 
0381 /******************************************************************************
0382  * doubly linked list macros (non-circular)                                   *
0383  *****************************************************************************/
0384 #define DL_PREPEND(head,add)                                                                   \
0385 do {                                                                                           \
0386  (add)->NDRX_NEXT = head;                                                                      \
0387  if (head) {                                                                                   \
0388    (add)->NDRX_PREV = (head)->NDRX_PREV;                                                       \
0389    (head)->NDRX_PREV = (add);                                                                  \
0390  } else {                                                                                      \
0391    (add)->NDRX_PREV = (add);                                                                   \
0392  }                                                                                             \
0393  (head) = (add);                                                                               \
0394 } while (0)
0395 
0396 #define DL_APPEND(head,add)                                                                    \
0397 do {                                                                                           \
0398   if (head) {                                                                                  \
0399       (add)->NDRX_PREV = (head)->NDRX_PREV;                                                    \
0400       (head)->NDRX_PREV->NDRX_NEXT = (add);                                                    \
0401       (head)->NDRX_PREV = (add);                                                               \
0402       (add)->NDRX_NEXT = NULL;                                                                 \
0403   } else {                                                                                     \
0404       (head)=(add);                                                                            \
0405       (head)->NDRX_PREV = (head);                                                              \
0406       (head)->NDRX_NEXT = NULL;                                                                \
0407   }                                                                                            \
0408 } while (0);
0409 
0410 #define DL_DELETE(head,del)                                                                    \
0411 do {                                                                                           \
0412   if ((del)->NDRX_PREV == (del)) {                                                             \
0413       (head)=NULL;                                                                             \
0414   } else if ((del)==(head)) {                                                                  \
0415       (del)->NDRX_NEXT->NDRX_PREV = (del)->NDRX_PREV;                                          \
0416       (head) = (del)->NDRX_NEXT;                                                               \
0417   } else {                                                                                     \
0418       (del)->NDRX_PREV->NDRX_NEXT = (del)->NDRX_NEXT;                                          \
0419       if ((del)->NDRX_NEXT) {                                                                  \
0420           (del)->NDRX_NEXT->NDRX_PREV = (del)->NDRX_PREV;                                      \
0421       } else {                                                                                 \
0422           (head)->NDRX_PREV = (del)->NDRX_PREV;                                                \
0423       }                                                                                        \
0424   }                                                                                            \
0425 } while (0);
0426 
0427 
0428 #define DL_FOREACH(head,el)                                                                    \
0429     for(el=head;el;el=el->NDRX_NEXT)
0430 
0431 /* For Each in reverse order, i is int*/
0432 #define DL_REVFOREACH(head,el,i)                                                               \
0433     for(el=(head)->NDRX_PREV,i=1; (el) && (el->NDRX_NEXT || i); el=(el)->NDRX_PREV, i=0)
0434 
0435 /* this version is safe for deleting the elements during iteration */
0436 #define DL_FOREACH_SAFE(head,el,tmp)                                                           \
0437   for((el)=(head);(el) && (tmp = (el)->NDRX_NEXT, 1); (el) = tmp)
0438 
0439 /* these are identical to their singly-linked list counterparts */
0440 #define DL_SEARCH_SCALAR LL_SEARCH_SCALAR
0441 #define DL_SEARCH LL_SEARCH
0442 
0443 /******************************************************************************
0444  * circular doubly linked list macros                                         *
0445  *****************************************************************************/
0446 #define CDL_PREPEND(head,add)                                                                  \
0447 do {                                                                                           \
0448  if (head) {                                                                                   \
0449    (add)->NDRX_PREV = (head)->NDRX_PREV;                                                       \
0450    (add)->NDRX_NEXT = (head);                                                                  \
0451    (head)->NDRX_PREV = (add);                                                                  \
0452    (add)->NDRX_PREV->NDRX_NEXT = (add);                                                        \
0453  } else {                                                                                      \
0454    (add)->NDRX_PREV = (add);                                                                   \
0455    (add)->NDRX_NEXT = (add);                                                                   \
0456  }                                                                                             \
0457  (head)=(add);                                                                                 \
0458 } while (0)
0459 /* Added for Enduro/X Queues: */
0460 #define CDL_APPEND(head,add)                                                                   \
0461 do {                                                                                           \
0462  if (head) {                                                                                   \
0463    (add)->NDRX_PREV = (head)->NDRX_PREV;                                                       \
0464    (add)->NDRX_NEXT = (head);                                                                  \
0465    (head)->NDRX_PREV = (add);                                                                  \
0466    (add)->NDRX_PREV->NDRX_NEXT = (add);                                                        \
0467  } else {                                                                                      \
0468    (add)->NDRX_PREV = (add);                                                                   \
0469    (add)->NDRX_NEXT = (add);                                                                   \
0470    (head)=(add);                                                                               \
0471  }                                                                                             \
0472 } while (0)
0473 
0474 #define CDL_DELETE(head,del)                                                                   \
0475 do {                                                                                           \
0476   if ( ((head)==(del)) && ((head)->NDRX_NEXT == (head))) {                                     \
0477       (head) = 0L;                                                                             \
0478   } else {                                                                                     \
0479      (del)->NDRX_NEXT->NDRX_PREV = (del)->NDRX_PREV;                                           \
0480      (del)->NDRX_PREV->NDRX_NEXT = (del)->NDRX_NEXT;                                           \
0481      if ((del) == (head)) (head)=(del)->NDRX_NEXT;                                             \
0482   }                                                                                            \
0483 } while (0);
0484 
0485 #define CDL_FOREACH(head,el)                                                                   \
0486     for(el=head;el;el=(el->NDRX_NEXT==head ? 0L : el->NDRX_NEXT)) 
0487 
0488 #define CDL_FOREACH_SAFE(head,el,tmp1,tmp2)                                                    \
0489   for((el)=(head), ((tmp1)=(head)?((head)->NDRX_PREV):NULL);                                   \
0490       (el) && ((tmp2)=(el)->NDRX_NEXT, 1);                                                     \
0491       ((el) = (((el)==(tmp1)) ? 0L : (tmp2))))
0492 
0493 #define CDL_SEARCH_SCALAR(head,out,field,val)                                                  \
0494 do {                                                                                           \
0495     CDL_FOREACH(head,out) {                                                                    \
0496       if ((out)->field == (val)) break;                                                        \
0497     }                                                                                          \
0498 } while(0) 
0499 
0500 #define CDL_SEARCH(head,out,elt,cmp)                                                           \
0501 do {                                                                                           \
0502     CDL_FOREACH(head,out) {                                                                    \
0503       if ((cmp(out,elt))==0) break;                                                            \
0504     }                                                                                          \
0505 } while(0) 
0506 
0507 #endif /* UTLIST_INT_H */
0508
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.1.0 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!