Ashley Mills / tinydtls

Version 0.5.0 of tinydtls

Dependents:   tinydtls_test_cellular tinydtls_test_ethernet tiny-dtls

utlist.h@1:598a56fe116e, 2014-02-12 (annotated)

Committer:
ashleymills
Date:
Wed Feb 12 09:30:16 2014 +0000
Revision:
1:598a56fe116e
Parent:
0:ff9ebe0cf0e9 
Explicitly removed something instead of relying on MACRO to disable it. Mbed can't use it.

Who changed what in which revision?

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