Ashley Mills / tinydtls_0_4_0

mbed port of tinydtls

utlist.h@1:bc8a649bad13, 2013-10-11 (annotated)

Committer:
ashleymills
Date:
Fri Oct 11 08:46:21 2013 +0000
Revision:
1:bc8a649bad13
Parent:
0:04990d454f45 
Cleaned up all the debug stuff I added finding the hash table bug.

Who changed what in which revision?

UserRevisionLine numberNew contents of line
ashleymills 0:04990d454f45 1 /*
ashleymills 0:04990d454f45 2 Copyright (c) 2007-2010, Troy D. Hanson http://uthash.sourceforge.net
ashleymills 0:04990d454f45 3 All rights reserved.
ashleymills 0:04990d454f45 4
ashleymills 0:04990d454f45 5 Redistribution and use in source and binary forms, with or without
ashleymills 0:04990d454f45 6 modification, are permitted provided that the following conditions are met:
ashleymills 0:04990d454f45 7
ashleymills 0:04990d454f45 8 * Redistributions of source code must retain the above copyright
ashleymills 0:04990d454f45 9 notice, this list of conditions and the following disclaimer.
ashleymills 0:04990d454f45 10
ashleymills 0:04990d454f45 11 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
ashleymills 0:04990d454f45 12 IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
ashleymills 0:04990d454f45 13 TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
ashleymills 0:04990d454f45 14 PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
ashleymills 0:04990d454f45 15 OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
ashleymills 0:04990d454f45 16 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
ashleymills 0:04990d454f45 17 PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
ashleymills 0:04990d454f45 18 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
ashleymills 0:04990d454f45 19 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
ashleymills 0:04990d454f45 20 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
ashleymills 0:04990d454f45 21 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
ashleymills 0:04990d454f45 22 */
ashleymills 0:04990d454f45 23
ashleymills 0:04990d454f45 24 #ifndef UTLIST_H
ashleymills 0:04990d454f45 25 #define UTLIST_H
ashleymills 0:04990d454f45 26
ashleymills 0:04990d454f45 27 #define UTLIST_VERSION 1.9.1
ashleymills 0:04990d454f45 28
ashleymills 0:04990d454f45 29 /*
ashleymills 0:04990d454f45 30 * This file contains macros to manipulate singly and doubly-linked lists.
ashleymills 0:04990d454f45 31 *
ashleymills 0:04990d454f45 32 * 1. LL_ macros: singly-linked lists.
ashleymills 0:04990d454f45 33 * 2. DL_ macros: doubly-linked lists.
ashleymills 0:04990d454f45 34 * 3. CDL_ macros: circular doubly-linked lists.
ashleymills 0:04990d454f45 35 *
ashleymills 0:04990d454f45 36 * To use singly-linked lists, your structure must have a "next" pointer.
ashleymills 0:04990d454f45 37 * To use doubly-linked lists, your structure must "prev" and "next" pointers.
ashleymills 0:04990d454f45 38 * Either way, the pointer to the head of the list must be initialized to NULL.
ashleymills 0:04990d454f45 39 *
ashleymills 0:04990d454f45 40 * ----------------.EXAMPLE -------------------------
ashleymills 0:04990d454f45 41 * struct item {
ashleymills 0:04990d454f45 42 * int id;
ashleymills 0:04990d454f45 43 * struct item *prev, *next;
ashleymills 0:04990d454f45 44 * }
ashleymills 0:04990d454f45 45 *
ashleymills 0:04990d454f45 46 * struct item *list = NULL:
ashleymills 0:04990d454f45 47 *
ashleymills 0:04990d454f45 48 * int main() {
ashleymills 0:04990d454f45 49 * struct item *item;
ashleymills 0:04990d454f45 50 * ... allocate and populate item ...
ashleymills 0:04990d454f45 51 * DL_APPEND(list, item);
ashleymills 0:04990d454f45 52 * }
ashleymills 0:04990d454f45 53 * --------------------------------------------------
ashleymills 0:04990d454f45 54 *
ashleymills 0:04990d454f45 55 * For doubly-linked lists, the append and delete macros are O(1)
ashleymills 0:04990d454f45 56 * For singly-linked lists, append and delete are O(n) but prepend is O(1)
ashleymills 0:04990d454f45 57 * The sort macro is O(n log(n)) for all types of single/double/circular lists.
ashleymills 0:04990d454f45 58 */
ashleymills 0:04990d454f45 59
ashleymills 0:04990d454f45 60 /* These macros use decltype or the earlier __typeof GNU extension.
ashleymills 0:04990d454f45 61 As decltype is only available in newer compilers (VS2010 or gcc 4.3+
ashleymills 0:04990d454f45 62 when compiling c++ code), this code uses whatever method is needed
ashleymills 0:04990d454f45 63 or, for VS2008 where neither is available, uses casting workarounds. */
ashleymills 0:04990d454f45 64 #ifdef _MSC_VER /* MS compiler */
ashleymills 0:04990d454f45 65 #if _MSC_VER >= 1600 && __cplusplus /* VS2010 and newer in C++ mode */
ashleymills 0:04990d454f45 66 #define LDECLTYPE(x) decltype(x)
ashleymills 0:04990d454f45 67 #else /* VS2008 or older (or VS2010 in C mode) */
ashleymills 0:04990d454f45 68 #define NO_DECLTYPE
ashleymills 0:04990d454f45 69 #define LDECLTYPE(x) char*
ashleymills 0:04990d454f45 70 #endif
ashleymills 0:04990d454f45 71 #else /* GNU, Sun and other compilers */
ashleymills 0:04990d454f45 72 #define LDECLTYPE(x) __typeof(x)
ashleymills 0:04990d454f45 73 #endif
ashleymills 0:04990d454f45 74
ashleymills 0:04990d454f45 75 /* for VS2008 we use some workarounds to get around the lack of decltype,
ashleymills 0:04990d454f45 76 * namely, we always reassign our tmp variable to the list head if we need
ashleymills 0:04990d454f45 77 * to dereference its prev/next pointers, and save/restore the real head.*/
ashleymills 0:04990d454f45 78 #ifdef NO_DECLTYPE
ashleymills 0:04990d454f45 79 #define _SV(elt,list) _tmp = (char*)(list); {char **_alias = (char**)&(list); *_alias = (elt); }
ashleymills 0:04990d454f45 80 #define _NEXT(elt,list) ((char*)((list)->next))
ashleymills 0:04990d454f45 81 #define _NEXTASGN(elt,list,to) { char **_alias = (char**)&((list)->next); *_alias=(char*)(to); }
ashleymills 0:04990d454f45 82 #define _PREV(elt,list) ((char*)((list)->prev))
ashleymills 0:04990d454f45 83 #define _PREVASGN(elt,list,to) { char **_alias = (char**)&((list)->prev); *_alias=(char*)(to); }
ashleymills 0:04990d454f45 84 #define _RS(list) { char **_alias = (char**)&(list); *_alias=_tmp; }
ashleymills 0:04990d454f45 85 #define _CASTASGN(a,b) { char **_alias = (char**)&(a); *_alias=(char*)(b); }
ashleymills 0:04990d454f45 86 #else
ashleymills 0:04990d454f45 87 #define _SV(elt,list)
ashleymills 0:04990d454f45 88 #define _NEXT(elt,list) ((elt)->next)
ashleymills 0:04990d454f45 89 #define _NEXTASGN(elt,list,to) ((elt)->next)=(to)
ashleymills 0:04990d454f45 90 #define _PREV(elt,list) ((elt)->prev)
ashleymills 0:04990d454f45 91 #define _PREVASGN(elt,list,to) ((elt)->prev)=(to)
ashleymills 0:04990d454f45 92 #define _RS(list)
ashleymills 0:04990d454f45 93 #define _CASTASGN(a,b) (a)=(b)
ashleymills 0:04990d454f45 94 #endif
ashleymills 0:04990d454f45 95
ashleymills 0:04990d454f45 96 /******************************************************************************
ashleymills 0:04990d454f45 97 * The sort macro is an adaptation of Simon Tatham's O(n log(n)) mergesort *
ashleymills 0:04990d454f45 98 * Unwieldy variable names used here to avoid shadowing passed-in variables. *
ashleymills 0:04990d454f45 99 *****************************************************************************/
ashleymills 0:04990d454f45 100 #define LL_SORT(list, cmp) \
ashleymills 0:04990d454f45 101 do { \
ashleymills 0:04990d454f45 102 LDECLTYPE(list) _ls_p; \
ashleymills 0:04990d454f45 103 LDECLTYPE(list) _ls_q; \
ashleymills 0:04990d454f45 104 LDECLTYPE(list) _ls_e; \
ashleymills 0:04990d454f45 105 LDECLTYPE(list) _ls_tail; \
ashleymills 0:04990d454f45 106 LDECLTYPE(list) _ls_oldhead; \
ashleymills 0:04990d454f45 107 LDECLTYPE(list) _tmp; \
ashleymills 0:04990d454f45 108 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
ashleymills 0:04990d454f45 109 if (list) { \
ashleymills 0:04990d454f45 110 _ls_insize = 1; \
ashleymills 0:04990d454f45 111 _ls_looping = 1; \
ashleymills 0:04990d454f45 112 while (_ls_looping) { \
ashleymills 0:04990d454f45 113 _CASTASGN(_ls_p,list); \
ashleymills 0:04990d454f45 114 _CASTASGN(_ls_oldhead,list); \
ashleymills 0:04990d454f45 115 list = NULL; \
ashleymills 0:04990d454f45 116 _ls_tail = NULL; \
ashleymills 0:04990d454f45 117 _ls_nmerges = 0; \
ashleymills 0:04990d454f45 118 while (_ls_p) { \
ashleymills 0:04990d454f45 119 _ls_nmerges++; \
ashleymills 0:04990d454f45 120 _ls_q = _ls_p; \
ashleymills 0:04990d454f45 121 _ls_psize = 0; \
ashleymills 0:04990d454f45 122 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
ashleymills 0:04990d454f45 123 _ls_psize++; \
ashleymills 0:04990d454f45 124 _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); \
ashleymills 0:04990d454f45 125 if (!_ls_q) break; \
ashleymills 0:04990d454f45 126 } \
ashleymills 0:04990d454f45 127 _ls_qsize = _ls_insize; \
ashleymills 0:04990d454f45 128 while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \
ashleymills 0:04990d454f45 129 if (_ls_psize == 0) { \
ashleymills 0:04990d454f45 130 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \
ashleymills 0:04990d454f45 131 } else if (_ls_qsize == 0 || !_ls_q) { \
ashleymills 0:04990d454f45 132 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \
ashleymills 0:04990d454f45 133 } else if (cmp(_ls_p,_ls_q) <= 0) { \
ashleymills 0:04990d454f45 134 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \
ashleymills 0:04990d454f45 135 } else { \
ashleymills 0:04990d454f45 136 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \
ashleymills 0:04990d454f45 137 } \
ashleymills 0:04990d454f45 138 if (_ls_tail) { \
ashleymills 0:04990d454f45 139 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e); _RS(list); \
ashleymills 0:04990d454f45 140 } else { \
ashleymills 0:04990d454f45 141 _CASTASGN(list,_ls_e); \
ashleymills 0:04990d454f45 142 } \
ashleymills 0:04990d454f45 143 _ls_tail = _ls_e; \
ashleymills 0:04990d454f45 144 } \
ashleymills 0:04990d454f45 145 _ls_p = _ls_q; \
ashleymills 0:04990d454f45 146 } \
ashleymills 0:04990d454f45 147 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL); _RS(list); \
ashleymills 0:04990d454f45 148 if (_ls_nmerges <= 1) { \
ashleymills 0:04990d454f45 149 _ls_looping=0; \
ashleymills 0:04990d454f45 150 } \
ashleymills 0:04990d454f45 151 _ls_insize *= 2; \
ashleymills 0:04990d454f45 152 } \
ashleymills 0:04990d454f45 153 } else _tmp=NULL; /* quiet gcc unused variable warning */ \
ashleymills 0:04990d454f45 154 } while (0)
ashleymills 0:04990d454f45 155
ashleymills 0:04990d454f45 156 #define DL_SORT(list, cmp) \
ashleymills 0:04990d454f45 157 do { \
ashleymills 0:04990d454f45 158 LDECLTYPE(list) _ls_p; \
ashleymills 0:04990d454f45 159 LDECLTYPE(list) _ls_q; \
ashleymills 0:04990d454f45 160 LDECLTYPE(list) _ls_e; \
ashleymills 0:04990d454f45 161 LDECLTYPE(list) _ls_tail; \
ashleymills 0:04990d454f45 162 LDECLTYPE(list) _ls_oldhead; \
ashleymills 0:04990d454f45 163 LDECLTYPE(list) _tmp; \
ashleymills 0:04990d454f45 164 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
ashleymills 0:04990d454f45 165 if (list) { \
ashleymills 0:04990d454f45 166 _ls_insize = 1; \
ashleymills 0:04990d454f45 167 _ls_looping = 1; \
ashleymills 0:04990d454f45 168 while (_ls_looping) { \
ashleymills 0:04990d454f45 169 _CASTASGN(_ls_p,list); \
ashleymills 0:04990d454f45 170 _CASTASGN(_ls_oldhead,list); \
ashleymills 0:04990d454f45 171 list = NULL; \
ashleymills 0:04990d454f45 172 _ls_tail = NULL; \
ashleymills 0:04990d454f45 173 _ls_nmerges = 0; \
ashleymills 0:04990d454f45 174 while (_ls_p) { \
ashleymills 0:04990d454f45 175 _ls_nmerges++; \
ashleymills 0:04990d454f45 176 _ls_q = _ls_p; \
ashleymills 0:04990d454f45 177 _ls_psize = 0; \
ashleymills 0:04990d454f45 178 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
ashleymills 0:04990d454f45 179 _ls_psize++; \
ashleymills 0:04990d454f45 180 _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); \
ashleymills 0:04990d454f45 181 if (!_ls_q) break; \
ashleymills 0:04990d454f45 182 } \
ashleymills 0:04990d454f45 183 _ls_qsize = _ls_insize; \
ashleymills 0:04990d454f45 184 while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \
ashleymills 0:04990d454f45 185 if (_ls_psize == 0) { \
ashleymills 0:04990d454f45 186 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \
ashleymills 0:04990d454f45 187 } else if (_ls_qsize == 0 || !_ls_q) { \
ashleymills 0:04990d454f45 188 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \
ashleymills 0:04990d454f45 189 } else if (cmp(_ls_p,_ls_q) <= 0) { \
ashleymills 0:04990d454f45 190 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \
ashleymills 0:04990d454f45 191 } else { \
ashleymills 0:04990d454f45 192 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \
ashleymills 0:04990d454f45 193 } \
ashleymills 0:04990d454f45 194 if (_ls_tail) { \
ashleymills 0:04990d454f45 195 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e); _RS(list); \
ashleymills 0:04990d454f45 196 } else { \
ashleymills 0:04990d454f45 197 _CASTASGN(list,_ls_e); \
ashleymills 0:04990d454f45 198 } \
ashleymills 0:04990d454f45 199 _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail); _RS(list); \
ashleymills 0:04990d454f45 200 _ls_tail = _ls_e; \
ashleymills 0:04990d454f45 201 } \
ashleymills 0:04990d454f45 202 _ls_p = _ls_q; \
ashleymills 0:04990d454f45 203 } \
ashleymills 0:04990d454f45 204 _CASTASGN(list->prev, _ls_tail); \
ashleymills 0:04990d454f45 205 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,NULL); _RS(list); \
ashleymills 0:04990d454f45 206 if (_ls_nmerges <= 1) { \
ashleymills 0:04990d454f45 207 _ls_looping=0; \
ashleymills 0:04990d454f45 208 } \
ashleymills 0:04990d454f45 209 _ls_insize *= 2; \
ashleymills 0:04990d454f45 210 } \
ashleymills 0:04990d454f45 211 } else _tmp=NULL; /* quiet gcc unused variable warning */ \
ashleymills 0:04990d454f45 212 } while (0)
ashleymills 0:04990d454f45 213
ashleymills 0:04990d454f45 214 #define CDL_SORT(list, cmp) \
ashleymills 0:04990d454f45 215 do { \
ashleymills 0:04990d454f45 216 LDECLTYPE(list) _ls_p; \
ashleymills 0:04990d454f45 217 LDECLTYPE(list) _ls_q; \
ashleymills 0:04990d454f45 218 LDECLTYPE(list) _ls_e; \
ashleymills 0:04990d454f45 219 LDECLTYPE(list) _ls_tail; \
ashleymills 0:04990d454f45 220 LDECLTYPE(list) _ls_oldhead; \
ashleymills 0:04990d454f45 221 LDECLTYPE(list) _tmp; \
ashleymills 0:04990d454f45 222 LDECLTYPE(list) _tmp2; \
ashleymills 0:04990d454f45 223 int _ls_insize, _ls_nmerges, _ls_psize, _ls_qsize, _ls_i, _ls_looping; \
ashleymills 0:04990d454f45 224 if (list) { \
ashleymills 0:04990d454f45 225 _ls_insize = 1; \
ashleymills 0:04990d454f45 226 _ls_looping = 1; \
ashleymills 0:04990d454f45 227 while (_ls_looping) { \
ashleymills 0:04990d454f45 228 _CASTASGN(_ls_p,list); \
ashleymills 0:04990d454f45 229 _CASTASGN(_ls_oldhead,list); \
ashleymills 0:04990d454f45 230 list = NULL; \
ashleymills 0:04990d454f45 231 _ls_tail = NULL; \
ashleymills 0:04990d454f45 232 _ls_nmerges = 0; \
ashleymills 0:04990d454f45 233 while (_ls_p) { \
ashleymills 0:04990d454f45 234 _ls_nmerges++; \
ashleymills 0:04990d454f45 235 _ls_q = _ls_p; \
ashleymills 0:04990d454f45 236 _ls_psize = 0; \
ashleymills 0:04990d454f45 237 for (_ls_i = 0; _ls_i < _ls_insize; _ls_i++) { \
ashleymills 0:04990d454f45 238 _ls_psize++; \
ashleymills 0:04990d454f45 239 _SV(_ls_q,list); \
ashleymills 0:04990d454f45 240 if (_NEXT(_ls_q,list) == _ls_oldhead) { \
ashleymills 0:04990d454f45 241 _ls_q = NULL; \
ashleymills 0:04990d454f45 242 } else { \
ashleymills 0:04990d454f45 243 _ls_q = _NEXT(_ls_q,list); \
ashleymills 0:04990d454f45 244 } \
ashleymills 0:04990d454f45 245 _RS(list); \
ashleymills 0:04990d454f45 246 if (!_ls_q) break; \
ashleymills 0:04990d454f45 247 } \
ashleymills 0:04990d454f45 248 _ls_qsize = _ls_insize; \
ashleymills 0:04990d454f45 249 while (_ls_psize > 0 || (_ls_qsize > 0 && _ls_q)) { \
ashleymills 0:04990d454f45 250 if (_ls_psize == 0) { \
ashleymills 0:04990d454f45 251 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \
ashleymills 0:04990d454f45 252 if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \
ashleymills 0:04990d454f45 253 } else if (_ls_qsize == 0 || !_ls_q) { \
ashleymills 0:04990d454f45 254 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \
ashleymills 0:04990d454f45 255 if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \
ashleymills 0:04990d454f45 256 } else if (cmp(_ls_p,_ls_q) <= 0) { \
ashleymills 0:04990d454f45 257 _ls_e = _ls_p; _SV(_ls_p,list); _ls_p = _NEXT(_ls_p,list); _RS(list); _ls_psize--; \
ashleymills 0:04990d454f45 258 if (_ls_p == _ls_oldhead) { _ls_p = NULL; } \
ashleymills 0:04990d454f45 259 } else { \
ashleymills 0:04990d454f45 260 _ls_e = _ls_q; _SV(_ls_q,list); _ls_q = _NEXT(_ls_q,list); _RS(list); _ls_qsize--; \
ashleymills 0:04990d454f45 261 if (_ls_q == _ls_oldhead) { _ls_q = NULL; } \
ashleymills 0:04990d454f45 262 } \
ashleymills 0:04990d454f45 263 if (_ls_tail) { \
ashleymills 0:04990d454f45 264 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_ls_e); _RS(list); \
ashleymills 0:04990d454f45 265 } else { \
ashleymills 0:04990d454f45 266 _CASTASGN(list,_ls_e); \
ashleymills 0:04990d454f45 267 } \
ashleymills 0:04990d454f45 268 _SV(_ls_e,list); _PREVASGN(_ls_e,list,_ls_tail); _RS(list); \
ashleymills 0:04990d454f45 269 _ls_tail = _ls_e; \
ashleymills 0:04990d454f45 270 } \
ashleymills 0:04990d454f45 271 _ls_p = _ls_q; \
ashleymills 0:04990d454f45 272 } \
ashleymills 0:04990d454f45 273 _CASTASGN(list->prev,_ls_tail); \
ashleymills 0:04990d454f45 274 _CASTASGN(_tmp2,list); \
ashleymills 0:04990d454f45 275 _SV(_ls_tail,list); _NEXTASGN(_ls_tail,list,_tmp2); _RS(list); \
ashleymills 0:04990d454f45 276 if (_ls_nmerges <= 1) { \
ashleymills 0:04990d454f45 277 _ls_looping=0; \
ashleymills 0:04990d454f45 278 } \
ashleymills 0:04990d454f45 279 _ls_insize *= 2; \
ashleymills 0:04990d454f45 280 } \
ashleymills 0:04990d454f45 281 } else _tmp=NULL; /* quiet gcc unused variable warning */ \
ashleymills 0:04990d454f45 282 } while (0)
ashleymills 0:04990d454f45 283
ashleymills 0:04990d454f45 284 /******************************************************************************
ashleymills 0:04990d454f45 285 * singly linked list macros (non-circular) *
ashleymills 0:04990d454f45 286 *****************************************************************************/
ashleymills 0:04990d454f45 287 #define LL_PREPEND(head,add) \
ashleymills 0:04990d454f45 288 do { \
ashleymills 0:04990d454f45 289 (add)->next = head; \
ashleymills 0:04990d454f45 290 head = add; \
ashleymills 0:04990d454f45 291 } while (0)
ashleymills 0:04990d454f45 292
ashleymills 0:04990d454f45 293 #define LL_APPEND(head,add) \
ashleymills 0:04990d454f45 294 do { \
ashleymills 0:04990d454f45 295 LDECLTYPE(head) _tmp; \
ashleymills 0:04990d454f45 296 (add)->next=NULL; \
ashleymills 0:04990d454f45 297 if (head) { \
ashleymills 0:04990d454f45 298 _tmp = head; \
ashleymills 0:04990d454f45 299 while (_tmp->next) { _tmp = _tmp->next; } \
ashleymills 0:04990d454f45 300 _tmp->next=(add); \
ashleymills 0:04990d454f45 301 } else { \
ashleymills 0:04990d454f45 302 (head)=(add); \
ashleymills 0:04990d454f45 303 } \
ashleymills 0:04990d454f45 304 } while (0)
ashleymills 0:04990d454f45 305
ashleymills 0:04990d454f45 306 #define LL_DELETE(head,del) \
ashleymills 0:04990d454f45 307 do { \
ashleymills 0:04990d454f45 308 LDECLTYPE(head) _tmp; \
ashleymills 0:04990d454f45 309 if ((head) == (del)) { \
ashleymills 0:04990d454f45 310 (head)=(head)->next; \
ashleymills 0:04990d454f45 311 } else { \
ashleymills 0:04990d454f45 312 _tmp = head; \
ashleymills 0:04990d454f45 313 while (_tmp->next && (_tmp->next != (del))) { \
ashleymills 0:04990d454f45 314 _tmp = _tmp->next; \
ashleymills 0:04990d454f45 315 } \
ashleymills 0:04990d454f45 316 if (_tmp->next) { \
ashleymills 0:04990d454f45 317 _tmp->next = ((del)->next); \
ashleymills 0:04990d454f45 318 } \
ashleymills 0:04990d454f45 319 } \
ashleymills 0:04990d454f45 320 } while (0)
ashleymills 0:04990d454f45 321
ashleymills 0:04990d454f45 322 /* Here are VS2008 replacements for LL_APPEND and LL_DELETE */
ashleymills 0:04990d454f45 323 #define LL_APPEND_VS2008(head,add) \
ashleymills 0:04990d454f45 324 do { \
ashleymills 0:04990d454f45 325 if (head) { \
ashleymills 0:04990d454f45 326 (add)->next = head; /* use add->next as a temp variable */ \
ashleymills 0:04990d454f45 327 while ((add)->next->next) { (add)->next = (add)->next->next; } \
ashleymills 0:04990d454f45 328 (add)->next->next=(add); \
ashleymills 0:04990d454f45 329 } else { \
ashleymills 0:04990d454f45 330 (head)=(add); \
ashleymills 0:04990d454f45 331 } \
ashleymills 0:04990d454f45 332 (add)->next=NULL; \
ashleymills 0:04990d454f45 333 } while (0)
ashleymills 0:04990d454f45 334
ashleymills 0:04990d454f45 335 #define LL_DELETE_VS2008(head,del) \
ashleymills 0:04990d454f45 336 do { \
ashleymills 0:04990d454f45 337 if ((head) == (del)) { \
ashleymills 0:04990d454f45 338 (head)=(head)->next; \
ashleymills 0:04990d454f45 339 } else { \
ashleymills 0:04990d454f45 340 char *_tmp = (char*)(head); \
ashleymills 0:04990d454f45 341 while (head->next && (head->next != (del))) { \
ashleymills 0:04990d454f45 342 head = head->next; \
ashleymills 0:04990d454f45 343 } \
ashleymills 0:04990d454f45 344 if (head->next) { \
ashleymills 0:04990d454f45 345 head->next = ((del)->next); \
ashleymills 0:04990d454f45 346 } \
ashleymills 0:04990d454f45 347 { \
ashleymills 0:04990d454f45 348 char **_head_alias = (char**)&(head); \
ashleymills 0:04990d454f45 349 *_head_alias = _tmp; \
ashleymills 0:04990d454f45 350 } \
ashleymills 0:04990d454f45 351 } \
ashleymills 0:04990d454f45 352 } while (0)
ashleymills 0:04990d454f45 353 #ifdef NO_DECLTYPE
ashleymills 0:04990d454f45 354 #undef LL_APPEND
ashleymills 0:04990d454f45 355 #define LL_APPEND LL_APPEND_VS2008
ashleymills 0:04990d454f45 356 #undef LL_DELETE
ashleymills 0:04990d454f45 357 #define LL_DELETE LL_DELETE_VS2008
ashleymills 0:04990d454f45 358 #endif
ashleymills 0:04990d454f45 359 /* end VS2008 replacements */
ashleymills 0:04990d454f45 360
ashleymills 0:04990d454f45 361 #define LL_FOREACH(head,el) \
ashleymills 0:04990d454f45 362 for(el=head;el;el=el->next)
ashleymills 0:04990d454f45 363
ashleymills 0:04990d454f45 364 #define LL_FOREACH_SAFE(head,el,tmp) \
ashleymills 0:04990d454f45 365 for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp)
ashleymills 0:04990d454f45 366
ashleymills 0:04990d454f45 367 #define LL_SEARCH_SCALAR(head,out,field,val) \
ashleymills 0:04990d454f45 368 do { \
ashleymills 0:04990d454f45 369 LL_FOREACH(head,out) { \
ashleymills 0:04990d454f45 370 if ((out)->field == (val)) break; \
ashleymills 0:04990d454f45 371 } \
ashleymills 0:04990d454f45 372 } while(0)
ashleymills 0:04990d454f45 373
ashleymills 0:04990d454f45 374 #define LL_SEARCH(head,out,elt,cmp) \
ashleymills 0:04990d454f45 375 do { \
ashleymills 0:04990d454f45 376 LL_FOREACH(head,out) { \
ashleymills 0:04990d454f45 377 if ((cmp(out,elt))==0) break; \
ashleymills 0:04990d454f45 378 } \
ashleymills 0:04990d454f45 379 } while(0)
ashleymills 0:04990d454f45 380
ashleymills 0:04990d454f45 381 /******************************************************************************
ashleymills 0:04990d454f45 382 * doubly linked list macros (non-circular) *
ashleymills 0:04990d454f45 383 *****************************************************************************/
ashleymills 0:04990d454f45 384 #define DL_PREPEND(head,add) \
ashleymills 0:04990d454f45 385 do { \
ashleymills 0:04990d454f45 386 (add)->next = head; \
ashleymills 0:04990d454f45 387 if (head) { \
ashleymills 0:04990d454f45 388 (add)->prev = (head)->prev; \
ashleymills 0:04990d454f45 389 (head)->prev = (add); \
ashleymills 0:04990d454f45 390 } else { \
ashleymills 0:04990d454f45 391 (add)->prev = (add); \
ashleymills 0:04990d454f45 392 } \
ashleymills 0:04990d454f45 393 (head) = (add); \
ashleymills 0:04990d454f45 394 } while (0)
ashleymills 0:04990d454f45 395
ashleymills 0:04990d454f45 396 #define DL_APPEND(head,add) \
ashleymills 0:04990d454f45 397 do { \
ashleymills 0:04990d454f45 398 if (head) { \
ashleymills 0:04990d454f45 399 (add)->prev = (head)->prev; \
ashleymills 0:04990d454f45 400 (head)->prev->next = (add); \
ashleymills 0:04990d454f45 401 (head)->prev = (add); \
ashleymills 0:04990d454f45 402 (add)->next = NULL; \
ashleymills 0:04990d454f45 403 } else { \
ashleymills 0:04990d454f45 404 (head)=(add); \
ashleymills 0:04990d454f45 405 (head)->prev = (head); \
ashleymills 0:04990d454f45 406 (head)->next = NULL; \
ashleymills 0:04990d454f45 407 } \
ashleymills 0:04990d454f45 408 } while (0);
ashleymills 0:04990d454f45 409
ashleymills 0:04990d454f45 410 #define DL_DELETE(head,del) \
ashleymills 0:04990d454f45 411 do { \
ashleymills 0:04990d454f45 412 if ((del)->prev == (del)) { \
ashleymills 0:04990d454f45 413 (head)=NULL; \
ashleymills 0:04990d454f45 414 } else if ((del)==(head)) { \
ashleymills 0:04990d454f45 415 (del)->next->prev = (del)->prev; \
ashleymills 0:04990d454f45 416 (head) = (del)->next; \
ashleymills 0:04990d454f45 417 } else { \
ashleymills 0:04990d454f45 418 (del)->prev->next = (del)->next; \
ashleymills 0:04990d454f45 419 if ((del)->next) { \
ashleymills 0:04990d454f45 420 (del)->next->prev = (del)->prev; \
ashleymills 0:04990d454f45 421 } else { \
ashleymills 0:04990d454f45 422 (head)->prev = (del)->prev; \
ashleymills 0:04990d454f45 423 } \
ashleymills 0:04990d454f45 424 } \
ashleymills 0:04990d454f45 425 } while (0);
ashleymills 0:04990d454f45 426
ashleymills 0:04990d454f45 427
ashleymills 0:04990d454f45 428 #define DL_FOREACH(head,el) \
ashleymills 0:04990d454f45 429 for(el=head;el;el=el->next)
ashleymills 0:04990d454f45 430
ashleymills 0:04990d454f45 431 /* this version is safe for deleting the elements during iteration */
ashleymills 0:04990d454f45 432 #define DL_FOREACH_SAFE(head,el,tmp) \
ashleymills 0:04990d454f45 433 for((el)=(head);(el) && (tmp = (el)->next, 1); (el) = tmp)
ashleymills 0:04990d454f45 434
ashleymills 0:04990d454f45 435 /* these are identical to their singly-linked list counterparts */
ashleymills 0:04990d454f45 436 #define DL_SEARCH_SCALAR LL_SEARCH_SCALAR
ashleymills 0:04990d454f45 437 #define DL_SEARCH LL_SEARCH
ashleymills 0:04990d454f45 438
ashleymills 0:04990d454f45 439 /******************************************************************************
ashleymills 0:04990d454f45 440 * circular doubly linked list macros *
ashleymills 0:04990d454f45 441 *****************************************************************************/
ashleymills 0:04990d454f45 442 #define CDL_PREPEND(head,add) \
ashleymills 0:04990d454f45 443 do { \
ashleymills 0:04990d454f45 444 if (head) { \
ashleymills 0:04990d454f45 445 (add)->prev = (head)->prev; \
ashleymills 0:04990d454f45 446 (add)->next = (head); \
ashleymills 0:04990d454f45 447 (head)->prev = (add); \
ashleymills 0:04990d454f45 448 (add)->prev->next = (add); \
ashleymills 0:04990d454f45 449 } else { \
ashleymills 0:04990d454f45 450 (add)->prev = (add); \
ashleymills 0:04990d454f45 451 (add)->next = (add); \
ashleymills 0:04990d454f45 452 } \
ashleymills 0:04990d454f45 453 (head)=(add); \
ashleymills 0:04990d454f45 454 } while (0)
ashleymills 0:04990d454f45 455
ashleymills 0:04990d454f45 456 #define CDL_DELETE(head,del) \
ashleymills 0:04990d454f45 457 do { \
ashleymills 0:04990d454f45 458 if ( ((head)==(del)) && ((head)->next == (head))) { \
ashleymills 0:04990d454f45 459 (head) = 0L; \
ashleymills 0:04990d454f45 460 } else { \
ashleymills 0:04990d454f45 461 (del)->next->prev = (del)->prev; \
ashleymills 0:04990d454f45 462 (del)->prev->next = (del)->next; \
ashleymills 0:04990d454f45 463 if ((del) == (head)) (head)=(del)->next; \
ashleymills 0:04990d454f45 464 } \
ashleymills 0:04990d454f45 465 } while (0);
ashleymills 0:04990d454f45 466
ashleymills 0:04990d454f45 467 #define CDL_FOREACH(head,el) \
ashleymills 0:04990d454f45 468 for(el=head;el;el=(el->next==head ? 0L : el->next))
ashleymills 0:04990d454f45 469
ashleymills 0:04990d454f45 470 #define CDL_FOREACH_SAFE(head,el,tmp1,tmp2) \
ashleymills 0:04990d454f45 471 for((el)=(head), ((tmp1)=(head)?((head)->prev):NULL); \
ashleymills 0:04990d454f45 472 (el) && ((tmp2)=(el)->next, 1); \
ashleymills 0:04990d454f45 473 ((el) = (((el)==(tmp1)) ? 0L : (tmp2))))
ashleymills 0:04990d454f45 474
ashleymills 0:04990d454f45 475 #define CDL_SEARCH_SCALAR(head,out,field,val) \
ashleymills 0:04990d454f45 476 do { \
ashleymills 0:04990d454f45 477 CDL_FOREACH(head,out) { \
ashleymills 0:04990d454f45 478 if ((out)->field == (val)) break; \
ashleymills 0:04990d454f45 479 } \
ashleymills 0:04990d454f45 480 } while(0)
ashleymills 0:04990d454f45 481
ashleymills 0:04990d454f45 482 #define CDL_SEARCH(head,out,elt,cmp) \
ashleymills 0:04990d454f45 483 do { \
ashleymills 0:04990d454f45 484 CDL_FOREACH(head,out) { \
ashleymills 0:04990d454f45 485 if ((cmp(out,elt))==0) break; \
ashleymills 0:04990d454f45 486 } \
ashleymills 0:04990d454f45 487 } while(0)
ashleymills 0:04990d454f45 488
ashleymills 0:04990d454f45 489 #endif /* UTLIST_H */
ashleymills 0:04990d454f45 490