diff options
Diffstat (limited to 'contrib/libucl/uthash/utlist.h')
| -rw-r--r-- | contrib/libucl/uthash/utlist.h | 749 |
1 files changed, 534 insertions, 215 deletions
diff --git a/contrib/libucl/uthash/utlist.h b/contrib/libucl/uthash/utlist.h index c82dd916e2ed..7cda1ca0ecac 100644 --- a/contrib/libucl/uthash/utlist.h +++ b/contrib/libucl/uthash/utlist.h @@ -1,5 +1,5 @@ /* -Copyright (c) 2007-2013, Troy D. Hanson http://troydhanson.github.com/uthash/ +Copyright (c) 2007-2022, Troy D. Hanson https://troydhanson.github.io/uthash/ All rights reserved. Redistribution and use in source and binary forms, with or without @@ -24,11 +24,11 @@ SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. #ifndef UTLIST_H #define UTLIST_H -#define UTLIST_VERSION 1.9.8 +#define UTLIST_VERSION 2.3.0 #include <assert.h> -/* +/* * This file contains macros to manipulate singly and doubly-linked lists. * * 1. LL_ macros: singly-linked lists. @@ -38,7 +38,7 @@ SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * To use singly-linked lists, your structure must have a "next" pointer. * To use doubly-linked lists, your structure must "prev" and "next" pointers. * Either way, the pointer to the head of the list must be initialized to NULL. - * + * * ----------------.EXAMPLE ------------------------- * struct item { * int id; @@ -61,41 +61,46 @@ SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. /* These macros use decltype or the earlier __typeof GNU extension. As decltype is only available in newer compilers (VS2010 or gcc 4.3+ - when compiling c++ code), this code uses whatever method is needed + when compiling c++ source) this code uses whatever method is needed or, for VS2008 where neither is available, uses casting workarounds. */ -#ifdef _MSC_VER /* MS compiler */ +#if !defined(LDECLTYPE) && !defined(NO_DECLTYPE) +#if defined(_MSC_VER) /* MS compiler */ #if _MSC_VER >= 1600 && defined(__cplusplus) /* VS2010 or newer in C++ mode */ #define LDECLTYPE(x) decltype(x) -#else /* VS2008 or older (or VS2010 in C mode) */ +#else /* VS2008 or older (or VS2010 in C mode) */ #define NO_DECLTYPE -#define LDECLTYPE(x) char* #endif -#elif defined(__ICCARM__) +#elif defined(__MCST__) /* Elbrus C Compiler */ +#define LDECLTYPE(x) __typeof(x) +#elif defined(__BORLANDC__) || defined(__ICCARM__) || defined(__LCC__) || defined(__WATCOMC__) #define NO_DECLTYPE -#define LDECLTYPE(x) char* -#else /* GNU, Sun and other compilers */ +#else /* GNU, Sun and other compilers */ #define LDECLTYPE(x) __typeof(x) #endif +#endif /* for VS2008 we use some workarounds to get around the lack of decltype, * namely, we always reassign our tmp variable to the list head if we need * to dereference its prev/next pointers, and save/restore the real head.*/ #ifdef NO_DECLTYPE -#define _SV(elt,list) _tmp = (char*)(list); {char **_alias = (char**)&(list); *_alias = (elt); } -#define _NEXT(elt,list,next) ((char*)((list)->next)) -#define _NEXTASGN(elt,list,to,next) { char **_alias = (char**)&((list)->next); *_alias=(char*)(to); } -/* #define _PREV(elt,list,prev) ((char*)((list)->prev)) */ -#define _PREVASGN(elt,list,to,prev) { char **_alias = (char**)&((list)->prev); *_alias=(char*)(to); } -#define _RS(list) { char **_alias = (char**)&(list); *_alias=_tmp; } -#define _CASTASGN(a,b) { char **_alias = (char**)&(a); *_alias=(char*)(b); } -#else -#define _SV(elt,list) -#define _NEXT(elt,list,next) ((elt)->next) -#define _NEXTASGN(elt,list,to,next) ((elt)->next)=(to) -/* #define _PREV(elt,list,prev) ((elt)->prev) */ -#define _PREVASGN(elt,list,to,prev) ((elt)->prev)=(to) -#define _RS(list) -#define _CASTASGN(a,b) (a)=(b) +#define IF_NO_DECLTYPE(x) x +#define LDECLTYPE(x) char* +#define UTLIST_SV(elt,list) _tmp = (char*)(list); {char **_alias = (char**)&(list); *_alias = (elt); } +#define UTLIST_NEXT(elt,list,next) ((char*)((list)->next)) +#define UTLIST_NEXTASGN(elt,list,to,next) { char **_alias = (char**)&((list)->next); *_alias=(char*)(to); } +/* #define UTLIST_PREV(elt,list,prev) ((char*)((list)->prev)) */ +#define UTLIST_PREVASGN(elt,list,to,prev) { char **_alias = (char**)&((list)->prev); *_alias=(char*)(to); } +#define UTLIST_RS(list) { char **_alias = (char**)&(list); *_alias=_tmp; } +#define UTLIST_CASTASGN(a,b) { char **_alias = (char**)&(a); *_alias=(char*)(b); } +#else +#define IF_NO_DECLTYPE(x) +#define UTLIST_SV(elt,list) +#define UTLIST_NEXT(elt,list,next) ((elt)->next) +#define UTLIST_NEXTASGN(elt,list,to,next) ((elt)->next)=(to) +/* #define UTLIST_PREV(elt,list,prev) ((elt)->prev) */ +#define UTLIST_PREVASGN(elt,list,to,prev) ((elt)->prev)=(to) +#define UTLIST_RS(list) +#define UTLIST_CASTASGN(a,b) (a)=(b) #endif /****************************************************************************** @@ -111,13 +116,14 @@ do { LDECLTYPE(list) _ls_q; \ LDECLTYPE(list) _ls_e; \ LDECLTYPE(list) _ls_tail; \ + IF_NO_DECLTYPE(LDECLTYPE(list) _tmp;) \ int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \ if (list) { \ _ls_insize = 1; \ _ls_looping = 1; \ while (_ls_looping) { \ - _CASTASGN(_ls_p,list); \ - list = NULL; \ + UTLIST_CASTASGN(_ls_p,list); \ + (list) = NULL; \ _ls_tail = NULL; \ _ls_nmerges = 0; \ while (_ls_p) { \ @@ -126,35 +132,35 @@ do { _ls_psize = 0; \ for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \ _ls_psize++; \ - _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list,next); _RS(list); \ + UTLIST_SV(_ls_q,list); _ls_q = UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); \ if (!_ls_q) break; \ } \ _ls_qsize = _ls_insize; \ while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \ if (_ls_psize == 0) { \ - _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \ - _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \ + _ls_e = _ls_q; UTLIST_SV(_ls_q,list); _ls_q = \ + UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); _ls_qsize--; \ } else if (_ls_qsize == 0 || !_ls_q) { \ - _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \ - _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \ + _ls_e = _ls_p; UTLIST_SV(_ls_p,list); _ls_p = \ + UTLIST_NEXT(_ls_p,list,next); UTLIST_RS(list); _ls_psize--; \ } else if (cmp(_ls_p,_ls_q) <= 0) { \ - _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \ - _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \ + _ls_e = _ls_p; UTLIST_SV(_ls_p,list); _ls_p = \ + UTLIST_NEXT(_ls_p,list,next); UTLIST_RS(list); _ls_psize--; \ } else { \ - _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \ - _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \ + _ls_e = _ls_q; UTLIST_SV(_ls_q,list); _ls_q = \ + UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); _ls_qsize--; \ } \ if (_ls_tail) { \ - _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \ + UTLIST_SV(_ls_tail,list); UTLIST_NEXTASGN(_ls_tail,list,_ls_e,next); UTLIST_RS(list); \ } else { \ - _CASTASGN(list,_ls_e); \ + UTLIST_CASTASGN(list,_ls_e); \ } \ _ls_tail = _ls_e; \ } \ _ls_p = _ls_q; \ } \ if (_ls_tail) { \ - _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL,next); _RS(list); \ + UTLIST_SV(_ls_tail,list); UTLIST_NEXTASGN(_ls_tail,list,NULL,next); UTLIST_RS(list); \ } \ if (_ls_nmerges <= 1) { \ _ls_looping=0; \ @@ -174,13 +180,14 @@ do { LDECLTYPE(list) _ls_q; \ LDECLTYPE(list) _ls_e; \ LDECLTYPE(list) _ls_tail; \ + IF_NO_DECLTYPE(LDECLTYPE(list) _tmp;) \ int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \ if (list) { \ _ls_insize = 1; \ _ls_looping = 1; \ while (_ls_looping) { \ - _CASTASGN(_ls_p,list); \ - list = NULL; \ + UTLIST_CASTASGN(_ls_p,list); \ + (list) = NULL; \ _ls_tail = NULL; \ _ls_nmerges = 0; \ while (_ls_p) { \ @@ -189,36 +196,36 @@ do { _ls_psize = 0; \ for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \ _ls_psize++; \ - _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list,next); _RS(list); \ + UTLIST_SV(_ls_q,list); _ls_q = UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); \ if (!_ls_q) break; \ } \ _ls_qsize = _ls_insize; \ - while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \ + while ((_ls_psize > 0) || ((_ls_qsize > 0) && _ls_q)) { \ if (_ls_psize == 0) { \ - _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \ - _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \ - } else if (_ls_qsize == 0 || !_ls_q) { \ - _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \ - _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \ + _ls_e = _ls_q; UTLIST_SV(_ls_q,list); _ls_q = \ + UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); _ls_qsize--; \ + } else if ((_ls_qsize == 0) || (!_ls_q)) { \ + _ls_e = _ls_p; UTLIST_SV(_ls_p,list); _ls_p = \ + UTLIST_NEXT(_ls_p,list,next); UTLIST_RS(list); _ls_psize--; \ } else if (cmp(_ls_p,_ls_q) <= 0) { \ - _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \ - _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \ + _ls_e = _ls_p; UTLIST_SV(_ls_p,list); _ls_p = \ + UTLIST_NEXT(_ls_p,list,next); UTLIST_RS(list); _ls_psize--; \ } else { \ - _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \ - _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \ + _ls_e = _ls_q; UTLIST_SV(_ls_q,list); _ls_q = \ + UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); _ls_qsize--; \ } \ if (_ls_tail) { \ - _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \ + UTLIST_SV(_ls_tail,list); UTLIST_NEXTASGN(_ls_tail,list,_ls_e,next); UTLIST_RS(list); \ } else { \ - _CASTASGN(list,_ls_e); \ + UTLIST_CASTASGN(list,_ls_e); \ } \ - _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail,prev); _RS(list); \ + UTLIST_SV(_ls_e,list); UTLIST_PREVASGN(_ls_e,list,_ls_tail,prev); UTLIST_RS(list); \ _ls_tail = _ls_e; \ } \ _ls_p = _ls_q; \ } \ - _CASTASGN(list->prev, _ls_tail); \ - _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL,next); _RS(list); \ + UTLIST_CASTASGN((list)->prev, _ls_tail); \ + UTLIST_SV(_ls_tail,list); UTLIST_NEXTASGN(_ls_tail,list,NULL,next); UTLIST_RS(list); \ if (_ls_nmerges <= 1) { \ _ls_looping=0; \ } \ @@ -243,9 +250,9 @@ do { _ls_insize = 1; \ _ls_looping = 1; \ while (_ls_looping) { \ - _CASTASGN(_ls_p,list); \ - _CASTASGN(_ls_oldhead,list); \ - list = NULL; \ + UTLIST_CASTASGN(_ls_p,list); \ + UTLIST_CASTASGN(_ls_oldhead,list); \ + (list) = NULL; \ _ls_tail = NULL; \ _ls_nmerges = 0; \ while (_ls_p) { \ @@ -254,47 +261,47 @@ do { _ls_psize = 0; \ for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \ _ls_psize++; \ - _SV(_ls_q,list); \ - if (_NEXT(_ls_q,list,next) == _ls_oldhead) { \ + UTLIST_SV(_ls_q,list); \ + if (UTLIST_NEXT(_ls_q,list,next) == _ls_oldhead) { \ _ls_q = NULL; \ } else { \ - _ls_q = _NEXT(_ls_q,list,next); \ + _ls_q = UTLIST_NEXT(_ls_q,list,next); \ } \ - _RS(list); \ + UTLIST_RS(list); \ if (!_ls_q) break; \ } \ _ls_qsize = _ls_insize; \ while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \ if (_ls_psize == 0) { \ - _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \ - _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \ + _ls_e = _ls_q; UTLIST_SV(_ls_q,list); _ls_q = \ + UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); _ls_qsize--; \ if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \ } else if (_ls_qsize == 0 || !_ls_q) { \ - _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \ - _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \ + _ls_e = _ls_p; UTLIST_SV(_ls_p,list); _ls_p = \ + UTLIST_NEXT(_ls_p,list,next); UTLIST_RS(list); _ls_psize--; \ if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \ } else if (cmp(_ls_p,_ls_q) <= 0) { \ - _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = \ - _NEXT(_ls_p,list,next); _RS(list); _ls_psize--; \ + _ls_e = _ls_p; UTLIST_SV(_ls_p,list); _ls_p = \ + UTLIST_NEXT(_ls_p,list,next); UTLIST_RS(list); _ls_psize--; \ if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \ } else { \ - _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = \ - _NEXT(_ls_q,list,next); _RS(list); _ls_qsize--; \ + _ls_e = _ls_q; UTLIST_SV(_ls_q,list); _ls_q = \ + UTLIST_NEXT(_ls_q,list,next); UTLIST_RS(list); _ls_qsize--; \ if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \ } \ if (_ls_tail) { \ - _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e,next); _RS(list); \ + UTLIST_SV(_ls_tail,list); UTLIST_NEXTASGN(_ls_tail,list,_ls_e,next); UTLIST_RS(list); \ } else { \ - _CASTASGN(list,_ls_e); \ + UTLIST_CASTASGN(list,_ls_e); \ } \ - _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail,prev); _RS(list); \ + UTLIST_SV(_ls_e,list); UTLIST_PREVASGN(_ls_e,list,_ls_tail,prev); UTLIST_RS(list); \ _ls_tail = _ls_e; \ } \ _ls_p = _ls_q; \ } \ - _CASTASGN(list->prev,_ls_tail); \ - _CASTASGN(_tmp,list); \ - _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_tmp,next); _RS(list); \ + UTLIST_CASTASGN((list)->prev,_ls_tail); \ + UTLIST_CASTASGN(_tmp,list); \ + UTLIST_SV(_ls_tail,list); UTLIST_NEXTASGN(_ls_tail,list,_tmp,next); UTLIST_RS(list); \ if (_ls_nmerges <= 1) { \ _ls_looping=0; \ } \ @@ -311,8 +318,8 @@ do { #define LL_PREPEND2(head,add,next) \ do { \ - (add)->next = head; \ - head = add; \ + (add)->next = (head); \ + (head) = (add); \ } while (0) #define LL_CONCAT(head1,head2) \ @@ -322,7 +329,7 @@ do { do { \ LDECLTYPE(head1) _tmp; \ if (head1) { \ - _tmp = head1; \ + _tmp = (head1); \ while (_tmp->next) { _tmp = _tmp->next; } \ _tmp->next=(head2); \ } else { \ @@ -338,7 +345,7 @@ do { LDECLTYPE(head) _tmp; \ (add)->next=NULL; \ if (head) { \ - _tmp = head; \ + _tmp = (head); \ while (_tmp->next) { _tmp = _tmp->next; } \ _tmp->next=(add); \ } else { \ @@ -346,96 +353,76 @@ do { } \ } while (0) -#define LL_DELETE(head,del) \ - LL_DELETE2(head,del,next) +#define LL_INSERT_INORDER(head,add,cmp) \ + LL_INSERT_INORDER2(head,add,cmp,next) -#define LL_DELETE2(head,del,next) \ +#define LL_INSERT_INORDER2(head,add,cmp,next) \ do { \ LDECLTYPE(head) _tmp; \ - if ((head) == (del)) { \ - (head)=(head)->next; \ + if (head) { \ + LL_LOWER_BOUND2(head, _tmp, add, cmp, next); \ + LL_APPEND_ELEM2(head, _tmp, add, next); \ } else { \ - _tmp = head; \ - while (_tmp->next && (_tmp->next != (del))) { \ - _tmp = _tmp->next; \ - } \ - if (_tmp->next) { \ - _tmp->next = ((del)->next); \ - } \ + (head) = (add); \ + (head)->next = NULL; \ } \ } while (0) -/* Here are VS2008 replacements for LL_APPEND and LL_DELETE */ -#define LL_APPEND_VS2008(head,add) \ - LL_APPEND2_VS2008(head,add,next) +#define LL_LOWER_BOUND(head,elt,like,cmp) \ + LL_LOWER_BOUND2(head,elt,like,cmp,next) -#define LL_APPEND2_VS2008(head,add,next) \ -do { \ - if (head) { \ - (add)->next = head; /* use add->next as a temp variable */ \ - while ((add)->next->next) { (add)->next = (add)->next->next; } \ - (add)->next->next=(add); \ - } else { \ - (head)=(add); \ - } \ - (add)->next=NULL; \ -} while (0) +#define LL_LOWER_BOUND2(head,elt,like,cmp,next) \ + do { \ + if ((head) == NULL || (cmp(head, like)) >= 0) { \ + (elt) = NULL; \ + } else { \ + for ((elt) = (head); (elt)->next != NULL; (elt) = (elt)->next) { \ + if (cmp((elt)->next, like) >= 0) { \ + break; \ + } \ + } \ + } \ + } while (0) -#define LL_DELETE_VS2008(head,del) \ - LL_DELETE2_VS2008(head,del,next) +#define LL_DELETE(head,del) \ + LL_DELETE2(head,del,next) -#define LL_DELETE2_VS2008(head,del,next) \ +#define LL_DELETE2(head,del,next) \ do { \ + LDECLTYPE(head) _tmp; \ if ((head) == (del)) { \ (head)=(head)->next; \ } else { \ - char *_tmp = (char*)(head); \ - while ((head)->next && ((head)->next != (del))) { \ - head = (head)->next; \ - } \ - if ((head)->next) { \ - (head)->next = ((del)->next); \ + _tmp = (head); \ + while (_tmp->next && (_tmp->next != (del))) { \ + _tmp = _tmp->next; \ } \ - { \ - char **_head_alias = (char**)&(head); \ - *_head_alias = _tmp; \ + if (_tmp->next) { \ + _tmp->next = (del)->next; \ } \ } \ } while (0) -#ifdef NO_DECLTYPE -#undef LL_APPEND -#define LL_APPEND LL_APPEND_VS2008 -#undef LL_DELETE -#define LL_DELETE LL_DELETE_VS2008 -#undef LL_DELETE2 -#define LL_DELETE2 LL_DELETE2_VS2008 -#undef LL_APPEND2 -#define LL_APPEND2 LL_APPEND2_VS2008 -#undef LL_CONCAT /* no LL_CONCAT_VS2008 */ -#undef DL_CONCAT /* no DL_CONCAT_VS2008 */ -#endif -/* end VS2008 replacements */ #define LL_COUNT(head,el,counter) \ LL_COUNT2(head,el,counter,next) \ #define LL_COUNT2(head,el,counter,next) \ -{ \ - counter = 0; \ - LL_FOREACH2(head,el,next){ ++counter; } \ -} +do { \ + (counter) = 0; \ + LL_FOREACH2(head,el,next) { ++(counter); } \ +} while (0) #define LL_FOREACH(head,el) \ LL_FOREACH2(head,el,next) #define LL_FOREACH2(head,el,next) \ - for(el=head;el;el=(el)->next) + for ((el) = (head); el; (el) = (el)->next) #define LL_FOREACH_SAFE(head,el,tmp) \ LL_FOREACH_SAFE2(head,el,tmp,next) #define LL_FOREACH_SAFE2(head,el,tmp,next) \ - for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp) + for ((el) = (head); (el) && ((tmp) = (el)->next, 1); (el) = (tmp)) #define LL_SEARCH_SCALAR(head,out,field,val) \ LL_SEARCH_SCALAR2(head,out,field,val,next) @@ -445,7 +432,7 @@ do { LL_FOREACH2(head,out,next) { \ if ((out)->field == (val)) break; \ } \ -} while(0) +} while (0) #define LL_SEARCH(head,out,elt,cmp) \ LL_SEARCH2(head,out,elt,cmp,next) @@ -455,19 +442,19 @@ do { LL_FOREACH2(head,out,next) { \ if ((cmp(out,elt))==0) break; \ } \ -} while(0) +} while (0) -#define LL_REPLACE_ELEM(head, el, add) \ +#define LL_REPLACE_ELEM2(head, el, add, next) \ do { \ LDECLTYPE(head) _tmp; \ - assert(head != NULL); \ - assert(el != NULL); \ - assert(add != NULL); \ + assert((head) != NULL); \ + assert((el) != NULL); \ + assert((add) != NULL); \ (add)->next = (el)->next; \ if ((head) == (el)) { \ (head) = (add); \ } else { \ - _tmp = head; \ + _tmp = (head); \ while (_tmp->next && (_tmp->next != (el))) { \ _tmp = _tmp->next; \ } \ @@ -477,26 +464,158 @@ do { } \ } while (0) +#define LL_REPLACE_ELEM(head, el, add) \ + LL_REPLACE_ELEM2(head, el, add, next) + +#define LL_PREPEND_ELEM2(head, el, add, next) \ +do { \ + if (el) { \ + LDECLTYPE(head) _tmp; \ + assert((head) != NULL); \ + assert((add) != NULL); \ + (add)->next = (el); \ + if ((head) == (el)) { \ + (head) = (add); \ + } else { \ + _tmp = (head); \ + while (_tmp->next && (_tmp->next != (el))) { \ + _tmp = _tmp->next; \ + } \ + if (_tmp->next) { \ + _tmp->next = (add); \ + } \ + } \ + } else { \ + LL_APPEND2(head, add, next); \ + } \ +} while (0) \ + #define LL_PREPEND_ELEM(head, el, add) \ + LL_PREPEND_ELEM2(head, el, add, next) + +#define LL_APPEND_ELEM2(head, el, add, next) \ do { \ - LDECLTYPE(head) _tmp; \ - assert(head != NULL); \ - assert(el != NULL); \ - assert(add != NULL); \ - (add)->next = (el); \ - if ((head) == (el)) { \ - (head) = (add); \ + if (el) { \ + assert((head) != NULL); \ + assert((add) != NULL); \ + (add)->next = (el)->next; \ + (el)->next = (add); \ } else { \ - _tmp = head; \ - while (_tmp->next && (_tmp->next != (el))) { \ - _tmp = _tmp->next; \ + LL_PREPEND2(head, add, next); \ + } \ +} while (0) \ + +#define LL_APPEND_ELEM(head, el, add) \ + LL_APPEND_ELEM2(head, el, add, next) + +#ifdef NO_DECLTYPE +/* Here are VS2008 / NO_DECLTYPE replacements for a few functions */ + +#undef LL_CONCAT2 +#define LL_CONCAT2(head1,head2,next) \ +do { \ + char *_tmp; \ + if (head1) { \ + _tmp = (char*)(head1); \ + while ((head1)->next) { (head1) = (head1)->next; } \ + (head1)->next = (head2); \ + UTLIST_RS(head1); \ + } else { \ + (head1)=(head2); \ } \ - if (_tmp->next) { \ - _tmp->next = (add); \ +} while (0) + +#undef LL_APPEND2 +#define LL_APPEND2(head,add,next) \ +do { \ + if (head) { \ + (add)->next = head; /* use add->next as a temp variable */ \ + while ((add)->next->next) { (add)->next = (add)->next->next; } \ + (add)->next->next=(add); \ + } else { \ + (head)=(add); \ + } \ + (add)->next=NULL; \ +} while (0) + +#undef LL_INSERT_INORDER2 +#define LL_INSERT_INORDER2(head,add,cmp,next) \ +do { \ + if ((head) == NULL || (cmp(head, add)) >= 0) { \ + (add)->next = (head); \ + (head) = (add); \ + } else { \ + char *_tmp = (char*)(head); \ + while ((head)->next != NULL && (cmp((head)->next, add)) < 0) { \ + (head) = (head)->next; \ + } \ + (add)->next = (head)->next; \ + (head)->next = (add); \ + UTLIST_RS(head); \ + } \ +} while (0) + +#undef LL_DELETE2 +#define LL_DELETE2(head,del,next) \ +do { \ + if ((head) == (del)) { \ + (head)=(head)->next; \ + } else { \ + char *_tmp = (char*)(head); \ + while ((head)->next && ((head)->next != (del))) { \ + (head) = (head)->next; \ + } \ + if ((head)->next) { \ + (head)->next = ((del)->next); \ + } \ + UTLIST_RS(head); \ + } \ +} while (0) + +#undef LL_REPLACE_ELEM2 +#define LL_REPLACE_ELEM2(head, el, add, next) \ +do { \ + assert((head) != NULL); \ + assert((el) != NULL); \ + assert((add) != NULL); \ + if ((head) == (el)) { \ + (head) = (add); \ + } else { \ + (add)->next = head; \ + while ((add)->next->next && ((add)->next->next != (el))) { \ + (add)->next = (add)->next->next; \ + } \ + if ((add)->next->next) { \ + (add)->next->next = (add); \ + } \ + } \ + (add)->next = (el)->next; \ +} while (0) + +#undef LL_PREPEND_ELEM2 +#define LL_PREPEND_ELEM2(head, el, add, next) \ +do { \ + if (el) { \ + assert((head) != NULL); \ + assert((add) != NULL); \ + if ((head) == (el)) { \ + (head) = (add); \ + } else { \ + (add)->next = (head); \ + while ((add)->next->next && ((add)->next->next != (el))) { \ + (add)->next = (add)->next->next; \ + } \ + if ((add)->next->next) { \ + (add)->next->next = (add); \ + } \ + } \ + (add)->next = (el); \ + } else { \ + LL_APPEND2(head, add, next); \ } \ - } \ } while (0) \ +#endif /* NO_DECLTYPE */ /****************************************************************************** * doubly linked list macros (non-circular) * @@ -506,7 +625,7 @@ do { #define DL_PREPEND2(head,add,prev,next) \ do { \ - (add)->next = head; \ + (add)->next = (head); \ if (head) { \ (add)->prev = (head)->prev; \ (head)->prev = (add); \ @@ -531,7 +650,39 @@ do { (head)->prev = (head); \ (head)->next = NULL; \ } \ -} while (0) +} while (0) + +#define DL_INSERT_INORDER(head,add,cmp) \ + DL_INSERT_INORDER2(head,add,cmp,prev,next) + +#define DL_INSERT_INORDER2(head,add,cmp,prev,next) \ +do { \ + LDECLTYPE(head) _tmp; \ + if (head) { \ + DL_LOWER_BOUND2(head, _tmp, add, cmp, next); \ + DL_APPEND_ELEM2(head, _tmp, add, prev, next); \ + } else { \ + (head) = (add); \ + (head)->prev = (head); \ + (head)->next = NULL; \ + } \ +} while (0) + +#define DL_LOWER_BOUND(head,elt,like,cmp) \ + DL_LOWER_BOUND2(head,elt,like,cmp,next) + +#define DL_LOWER_BOUND2(head,elt,like,cmp,next) \ +do { \ + if ((head) == NULL || (cmp(head, like)) >= 0) { \ + (elt) = NULL; \ + } else { \ + for ((elt) = (head); (elt)->next != NULL; (elt) = (elt)->next) { \ + if ((cmp((elt)->next, like)) >= 0) { \ + break; \ + } \ + } \ + } \ +} while (0) #define DL_CONCAT(head1,head2) \ DL_CONCAT2(head1,head2,prev,next) @@ -541,25 +692,27 @@ do { LDECLTYPE(head1) _tmp; \ if (head2) { \ if (head1) { \ - _tmp = (head2)->prev; \ + UTLIST_CASTASGN(_tmp, (head2)->prev); \ (head2)->prev = (head1)->prev; \ (head1)->prev->next = (head2); \ - (head1)->prev = _tmp; \ + UTLIST_CASTASGN((head1)->prev, _tmp); \ } else { \ (head1)=(head2); \ } \ } \ -} while (0) +} while (0) #define DL_DELETE(head,del) \ DL_DELETE2(head,del,prev,next) #define DL_DELETE2(head,del,prev,next) \ do { \ + assert((head) != NULL); \ assert((del)->prev != NULL); \ if ((del)->prev == (del)) { \ (head)=NULL; \ - } else if ((del)==(head)) { \ + } else if ((del) == (head)) { \ + assert((del)->next != NULL); \ (del)->next->prev = (del)->prev; \ (head) = (del)->next; \ } else { \ @@ -570,29 +723,29 @@ do { (head)->prev = (del)->prev; \ } \ } \ -} while (0) +} while (0) #define DL_COUNT(head,el,counter) \ DL_COUNT2(head,el,counter,next) \ #define DL_COUNT2(head,el,counter,next) \ -{ \ - counter = 0; \ - DL_FOREACH2(head,el,next){ ++counter; } \ -} +do { \ + (counter) = 0; \ + DL_FOREACH2(head,el,next) { ++(counter); } \ +} while (0) #define DL_FOREACH(head,el) \ DL_FOREACH2(head,el,next) #define DL_FOREACH2(head,el,next) \ - for(el=head;el;el=(el)->next) + for ((el) = (head); el; (el) = (el)->next) /* this version is safe for deleting the elements during iteration */ #define DL_FOREACH_SAFE(head,el,tmp) \ DL_FOREACH_SAFE2(head,el,tmp,next) #define DL_FOREACH_SAFE2(head,el,tmp,next) \ - for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp) + for ((el) = (head); (el) && ((tmp) = (el)->next, 1); (el) = (tmp)) /* these are identical to their singly-linked list counterparts */ #define DL_SEARCH_SCALAR LL_SEARCH_SCALAR @@ -600,11 +753,11 @@ do { #define DL_SEARCH_SCALAR2 LL_SEARCH_SCALAR2 #define DL_SEARCH2 LL_SEARCH2 -#define DL_REPLACE_ELEM(head, el, add) \ +#define DL_REPLACE_ELEM2(head, el, add, prev, next) \ do { \ - assert(head != NULL); \ - assert(el != NULL); \ - assert(add != NULL); \ + assert((head) != NULL); \ + assert((el) != NULL); \ + assert((add) != NULL); \ if ((head) == (el)) { \ (head) = (add); \ (add)->next = (el)->next; \ @@ -626,25 +779,104 @@ do { } \ } while (0) +#define DL_REPLACE_ELEM(head, el, add) \ + DL_REPLACE_ELEM2(head, el, add, prev, next) + +#define DL_PREPEND_ELEM2(head, el, add, prev, next) \ +do { \ + if (el) { \ + assert((head) != NULL); \ + assert((add) != NULL); \ + (add)->next = (el); \ + (add)->prev = (el)->prev; \ + (el)->prev = (add); \ + if ((head) == (el)) { \ + (head) = (add); \ + } else { \ + (add)->prev->next = (add); \ + } \ + } else { \ + DL_APPEND2(head, add, prev, next); \ + } \ +} while (0) \ + #define DL_PREPEND_ELEM(head, el, add) \ + DL_PREPEND_ELEM2(head, el, add, prev, next) + +#define DL_APPEND_ELEM2(head, el, add, prev, next) \ do { \ - assert(head != NULL); \ - assert(el != NULL); \ - assert(add != NULL); \ - (add)->next = (el); \ - (add)->prev = (el)->prev; \ - (el)->prev = (add); \ - if ((head) == (el)) { \ - (head) = (add); \ + if (el) { \ + assert((head) != NULL); \ + assert((add) != NULL); \ + (add)->next = (el)->next; \ + (add)->prev = (el); \ + (el)->next = (add); \ + if ((add)->next) { \ + (add)->next->prev = (add); \ + } else { \ + (head)->prev = (add); \ + } \ } else { \ - (add)->prev->next = (add); \ + DL_PREPEND2(head, add, prev, next); \ } \ } while (0) \ +#define DL_APPEND_ELEM(head, el, add) \ + DL_APPEND_ELEM2(head, el, add, prev, next) + +#ifdef NO_DECLTYPE +/* Here are VS2008 / NO_DECLTYPE replacements for a few functions */ + +#undef DL_INSERT_INORDER2 +#define DL_INSERT_INORDER2(head,add,cmp,prev,next) \ +do { \ + if ((head) == NULL) { \ + (add)->prev = (add); \ + (add)->next = NULL; \ + (head) = (add); \ + } else if ((cmp(head, add)) >= 0) { \ + (add)->prev = (head)->prev; \ + (add)->next = (head); \ + (head)->prev = (add); \ + (head) = (add); \ + } else { \ + char *_tmp = (char*)(head); \ + while ((head)->next && (cmp((head)->next, add)) < 0) { \ + (head) = (head)->next; \ + } \ + (add)->prev = (head); \ + (add)->next = (head)->next; \ + (head)->next = (add); \ + UTLIST_RS(head); \ + if ((add)->next) { \ + (add)->next->prev = (add); \ + } else { \ + (head)->prev = (add); \ + } \ + } \ +} while (0) +#endif /* NO_DECLTYPE */ /****************************************************************************** * circular doubly linked list macros * *****************************************************************************/ +#define CDL_APPEND(head,add) \ + CDL_APPEND2(head,add,prev,next) + +#define CDL_APPEND2(head,add,prev,next) \ +do { \ + if (head) { \ + (add)->prev = (head)->prev; \ + (add)->next = (head); \ + (head)->prev = (add); \ + (add)->prev->next = (add); \ + } else { \ + (add)->prev = (add); \ + (add)->next = (add); \ + (head) = (add); \ + } \ +} while (0) + #define CDL_PREPEND(head,add) \ CDL_PREPEND2(head,add,prev,next) @@ -659,7 +891,39 @@ do { (add)->prev = (add); \ (add)->next = (add); \ } \ -(head)=(add); \ + (head) = (add); \ +} while (0) + +#define CDL_INSERT_INORDER(head,add,cmp) \ + CDL_INSERT_INORDER2(head,add,cmp,prev,next) + +#define CDL_INSERT_INORDER2(head,add,cmp,prev,next) \ +do { \ + LDECLTYPE(head) _tmp; \ + if (head) { \ + CDL_LOWER_BOUND2(head, _tmp, add, cmp, next); \ + CDL_APPEND_ELEM2(head, _tmp, add, prev, next); \ + } else { \ + (head) = (add); \ + (head)->next = (head); \ + (head)->prev = (head); \ + } \ +} while (0) + +#define CDL_LOWER_BOUND(head,elt,like,cmp) \ + CDL_LOWER_BOUND2(head,elt,like,cmp,next) + +#define CDL_LOWER_BOUND2(head,elt,like,cmp,next) \ +do { \ + if ((head) == NULL || (cmp(head, like)) >= 0) { \ + (elt) = NULL; \ + } else { \ + for ((elt) = (head); (elt)->next != (head); (elt) = (elt)->next) { \ + if ((cmp((elt)->next, like)) >= 0) { \ + break; \ + } \ + } \ + } \ } while (0) #define CDL_DELETE(head,del) \ @@ -667,37 +931,37 @@ do { #define CDL_DELETE2(head,del,prev,next) \ do { \ - if ( ((head)==(del)) && ((head)->next == (head))) { \ - (head) = 0L; \ + if (((head)==(del)) && ((head)->next == (head))) { \ + (head) = NULL; \ } else { \ (del)->next->prev = (del)->prev; \ (del)->prev->next = (del)->next; \ if ((del) == (head)) (head)=(del)->next; \ } \ -} while (0) +} while (0) #define CDL_COUNT(head,el,counter) \ CDL_COUNT2(head,el,counter,next) \ #define CDL_COUNT2(head, el, counter,next) \ -{ \ - counter = 0; \ - CDL_FOREACH2(head,el,next){ ++counter; } \ -} +do { \ + (counter) = 0; \ + CDL_FOREACH2(head,el,next) { ++(counter); } \ +} while (0) #define CDL_FOREACH(head,el) \ CDL_FOREACH2(head,el,next) #define CDL_FOREACH2(head,el,next) \ - for(el=head;el;el=((el)->next==head ? 0L : (el)->next)) + for ((el)=(head);el;(el)=(((el)->next==(head)) ? NULL : (el)->next)) #define CDL_FOREACH_SAFE(head,el,tmp1,tmp2) \ CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next) #define CDL_FOREACH_SAFE2(head,el,tmp1,tmp2,prev,next) \ - for((el)=(head), ((tmp1)=(head)?((head)->prev):NULL); \ - (el) && ((tmp2)=(el)->next, 1); \ - ((el) = (((el)==(tmp1)) ? 0L : (tmp2)))) + for ((el) = (head), (tmp1) = (head) ? (head)->prev : NULL; \ + (el) && ((tmp2) = (el)->next, 1); \ + (el) = ((el) == (tmp1) ? NULL : (tmp2))) #define CDL_SEARCH_SCALAR(head,out,field,val) \ CDL_SEARCH_SCALAR2(head,out,field,val,next) @@ -707,7 +971,7 @@ do { CDL_FOREACH2(head,out,next) { \ if ((out)->field == (val)) break; \ } \ -} while(0) +} while (0) #define CDL_SEARCH(head,out,elt,cmp) \ CDL_SEARCH2(head,out,elt,cmp,next) @@ -717,13 +981,13 @@ do { CDL_FOREACH2(head,out,next) { \ if ((cmp(out,elt))==0) break; \ } \ -} while(0) +} while (0) -#define CDL_REPLACE_ELEM(head, el, add) \ +#define CDL_REPLACE_ELEM2(head, el, add, prev, next) \ do { \ - assert(head != NULL); \ - assert(el != NULL); \ - assert(add != NULL); \ + assert((head) != NULL); \ + assert((el) != NULL); \ + assert((add) != NULL); \ if ((el)->next == (el)) { \ (add)->next = (add); \ (add)->prev = (add); \ @@ -739,19 +1003,74 @@ do { } \ } while (0) +#define CDL_REPLACE_ELEM(head, el, add) \ + CDL_REPLACE_ELEM2(head, el, add, prev, next) + +#define CDL_PREPEND_ELEM2(head, el, add, prev, next) \ +do { \ + if (el) { \ + assert((head) != NULL); \ + assert((add) != NULL); \ + (add)->next = (el); \ + (add)->prev = (el)->prev; \ + (el)->prev = (add); \ + (add)->prev->next = (add); \ + if ((head) == (el)) { \ + (head) = (add); \ + } \ + } else { \ + CDL_APPEND2(head, add, prev, next); \ + } \ +} while (0) + #define CDL_PREPEND_ELEM(head, el, add) \ + CDL_PREPEND_ELEM2(head, el, add, prev, next) + +#define CDL_APPEND_ELEM2(head, el, add, prev, next) \ do { \ - assert(head != NULL); \ - assert(el != NULL); \ - assert(add != NULL); \ - (add)->next = (el); \ - (add)->prev = (el)->prev; \ - (el)->prev = (add); \ - (add)->prev->next = (add); \ - if ((head) == (el)) { \ - (head) = (add); \ + if (el) { \ + assert((head) != NULL); \ + assert((add) != NULL); \ + (add)->next = (el)->next; \ + (add)->prev = (el); \ + (el)->next = (add); \ + (add)->next->prev = (add); \ + } else { \ + CDL_PREPEND2(head, add, prev, next); \ } \ -} while (0) \ +} while (0) -#endif /* UTLIST_H */ +#define CDL_APPEND_ELEM(head, el, add) \ + CDL_APPEND_ELEM2(head, el, add, prev, next) + +#ifdef NO_DECLTYPE +/* Here are VS2008 / NO_DECLTYPE replacements for a few functions */ +#undef CDL_INSERT_INORDER2 +#define CDL_INSERT_INORDER2(head,add,cmp,prev,next) \ +do { \ + if ((head) == NULL) { \ + (add)->prev = (add); \ + (add)->next = (add); \ + (head) = (add); \ + } else if ((cmp(head, add)) >= 0) { \ + (add)->prev = (head)->prev; \ + (add)->next = (head); \ + (add)->prev->next = (add); \ + (head)->prev = (add); \ + (head) = (add); \ + } else { \ + char *_tmp = (char*)(head); \ + while ((char*)(head)->next != _tmp && (cmp((head)->next, add)) < 0) { \ + (head) = (head)->next; \ + } \ + (add)->prev = (head); \ + (add)->next = (head)->next; \ + (add)->next->prev = (add); \ + (head)->next = (add); \ + UTLIST_RS(head); \ + } \ +} while (0) +#endif /* NO_DECLTYPE */ + +#endif /* UTLIST_H */ |