1 /* 2 Copyright (c) 2007-2011, Troy D. Hanson http://uthash.sourceforge.net 3 All rights reserved. 4 5 Redistribution and use in source and binary forms, with or without 6 modification, are permitted provided that the following conditions are met: 7 8 * Redistributions of source code must retain the above copyright 9 notice, this list of conditions and the following disclaimer. 10 11 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS 12 IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 13 TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A 14 PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER 15 OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 16 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 17 PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 18 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 19 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 20 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 21 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 22 */ 23 24 #ifndef UTLIST_H 25 #define UTLIST_H 26 27 #define UTLIST_VERSION 1.9.4 28 29 #include <assert.h> 30 31 /* 32 * This file contains macros to manipulate singly and doubly-linked lists. 33 * 34 * 1. LL_ macros: singly-linked lists. 35 * 2. DL_ macros: doubly-linked lists. 36 * 3. CDL_ macros: circular doubly-linked lists. 37 * 38 * To use singly-linked lists, your structure must have a "next" pointer. 39 * To use doubly-linked lists, your structure must "prev" and "next" pointers. 40 * Either way, the pointer to the head of the list must be initialized to NULL. 41 * 42 * ----------------.EXAMPLE ------------------------- 43 * struct item { 44 * int id; 45 * struct item *prev, *next; 46 * } 47 * 48 * struct item *list = NULL: 49 * 50 * int main() { 51 * struct item *item; 52 * ... allocate and populate item ... 53 * DL_APPEND(list, item); 54 * } 55 * -------------------------------------------------- 56 * 57 * For doubly-linked lists, the append and delete macros are O(1) 58 * For singly-linked lists, append and delete are O(n) but prepend is O(1) 59 */ 60 61 /****************************************************************************** 62 * Singly linked list macros (non-circular). 63 *****************************************************************************/ 64 #define LL_PREPEND(head, add) \ 65 do { \ 66 (add)->next = head; \ 67 head = add; \ 68 } while (0) 69 70 #define LL_CONCAT(head1, head2) \ 71 do { \ 72 __typeof(head1) _tmp; \ 73 if (head1) { \ 74 _tmp = head1; \ 75 while (_tmp->next) \ 76 _tmp = _tmp->next; \ 77 _tmp->next = (head2); \ 78 } else \ 79 (head1) = (head2); \ 80 } while (0) 81 82 #define LL_APPEND(head, add) \ 83 do { \ 84 __typeof(head) _tmp; \ 85 (add)->next = NULL; \ 86 if (head) { \ 87 _tmp = head; \ 88 while (_tmp->next) \ 89 _tmp = _tmp->next; \ 90 _tmp->next = (add); \ 91 } else { \ 92 (head) = (add); \ 93 } \ 94 } while (0) 95 96 #define LL_DELETE(head, del) \ 97 do { \ 98 __typeof(head) _tmp; \ 99 if ((head) == (del)) \ 100 (head) = (head)->next; \ 101 else { \ 102 _tmp = head; \ 103 while (_tmp->next && (_tmp->next != (del))) \ 104 _tmp = _tmp->next; \ 105 if (_tmp->next) \ 106 _tmp->next = ((del)->next); \ 107 } \ 108 } while (0) 109 110 #define LL_FOREACH(head, el) for (el = head; el; el = el->next) 111 112 #define LL_FOREACH_SAFE(head, el, tmp) \ 113 for ((el) = (head); (el) && (tmp = (el)->next, 1); (el) = tmp) 114 115 #define LL_SEARCH_SCALAR(head, out, field, val) \ 116 do { \ 117 LL_FOREACH (head, out) \ 118 if ((out)->field == (val)) \ 119 break; \ 120 } while (0) 121 122 #define LL_SEARCH_SCALAR_WITH_CAST(head, out, nout, field, val) \ 123 do { \ 124 LL_FOREACH (head, out) { \ 125 (nout) = (__typeof(nout))out; \ 126 if ((nout)->field == (val)) \ 127 break; \ 128 (nout) = 0; \ 129 } \ 130 } while (0) 131 132 #define LL_SEARCH(head, out, elt, cmp) \ 133 do { \ 134 LL_FOREACH (head, out) \ 135 if ((cmp(out, elt)) == 0) \ 136 break; \ 137 } while (0) 138 139 /****************************************************************************** 140 * Doubly linked list macros (non-circular). 141 *****************************************************************************/ 142 #define DL_PREPEND(head, add) \ 143 do { \ 144 (add)->next = head; \ 145 if (head) { \ 146 (add)->prev = (head)->prev; \ 147 (head)->prev = (add); \ 148 } else \ 149 (add)->prev = (add); \ 150 (head) = (add); \ 151 } while (0) 152 153 #define DL_APPEND(head, add) \ 154 do { \ 155 if (head) { \ 156 (add)->prev = (head)->prev; \ 157 (head)->prev->next = (add); \ 158 (head)->prev = (add); \ 159 (add)->next = NULL; \ 160 } else { \ 161 (head) = (add); \ 162 (head)->prev = (head); \ 163 (head)->next = NULL; \ 164 } \ 165 } while (0) 166 167 #define DL_INSERT(head, next_node, add) \ 168 do { \ 169 if (head == next_node) \ 170 DL_PREPEND(head, add); \ 171 else if (next_node == NULL) { \ 172 DL_APPEND(head, add); \ 173 } else { \ 174 (add)->prev = (next_node)->prev; \ 175 (next_node)->prev->next = (add); \ 176 (add)->next = (next_node); \ 177 (next_node)->prev = (add); \ 178 } \ 179 } while (0) 180 181 #define DL_CONCAT(head1, head2) \ 182 do { \ 183 __typeof(head1) _tmp; \ 184 if (head2) { \ 185 if (head1) { \ 186 _tmp = (head2)->prev; \ 187 (head2)->prev = (head1)->prev; \ 188 (head1)->prev->next = (head2); \ 189 (head1)->prev = _tmp; \ 190 } else \ 191 (head1) = (head2); \ 192 } \ 193 } while (0) 194 195 #define DL_DELETE(head, del) \ 196 do { \ 197 assert((head) != NULL); \ 198 assert((del)->prev != NULL); \ 199 if ((del)->prev == (del)) { \ 200 (head) = NULL; \ 201 } else if ((del) == (head)) { \ 202 (del)->next->prev = (del)->prev; \ 203 (head) = (del)->next; \ 204 } else { \ 205 (del)->prev->next = (del)->next; \ 206 if ((del)->next) \ 207 (del)->next->prev = (del)->prev; \ 208 else \ 209 (head)->prev = (del)->prev; \ 210 } \ 211 } while (0) 212 213 /* Create a variable name using given prefix and current line number. */ 214 #define MAKE_NAME(prefix) TOKEN_PASTE2(prefix, __LINE__) 215 #define TOKEN_PASTE2(x, y) TOKEN_PASTE(x, y) 216 #define TOKEN_PASTE(x, y) x##y 217 218 /* This version creates a temporary variable to to make it safe for deleting the 219 * elements during iteration. */ 220 #define DL_FOREACH(head, el) \ 221 DL_FOREACH_INTERNAL (head, el, MAKE_NAME(_dl_foreach_)) 222 #define DL_FOREACH_INTERNAL(head, el, tmp) \ 223 __typeof__(el) tmp; \ 224 for ((el) = (head); (el) && (tmp = (el)->next, 1); (el) = tmp) 225 226 /* These are identical to their singly-linked list counterparts. */ 227 #define DL_SEARCH_SCALAR LL_SEARCH_SCALAR 228 #define DL_SEARCH_SCALAR_WITH_CAST LL_SEARCH_SCALAR_WITH_CAST 229 #define DL_SEARCH LL_SEARCH 230 231 #endif /* UTLIST_H */ 232