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) \ 111 for (el = head; el; el = el->next) 112 113 #define LL_FOREACH_SAFE(head, el, tmp) \ 114 for ((el) = (head); (el) && (tmp = (el)->next, 1); (el) = tmp) 115 116 #define LL_SEARCH_SCALAR(head, out, field, val) \ 117 do { \ 118 LL_FOREACH(head, out) \ 119 if ((out)->field == (val)) \ 120 break; \ 121 } while (0) 122 123 #define LL_SEARCH_SCALAR_WITH_CAST(head, out, nout, field, val) \ 124 do { \ 125 LL_FOREACH(head, out) { \ 126 (nout) = (__typeof(nout))out; \ 127 if ((nout)->field == (val)) \ 128 break; \ 129 (nout) = 0; \ 130 } \ 131 } while (0) 132 133 #define LL_SEARCH(head, out, elt, cmp) \ 134 do { \ 135 LL_FOREACH(head, out) \ 136 if ((cmp(out, elt)) == 0) \ 137 break; \ 138 } while (0) 139 140 /****************************************************************************** 141 * Doubly linked list macros (non-circular). 142 *****************************************************************************/ 143 #define DL_PREPEND(head, add) \ 144 do { \ 145 (add)->next = head; \ 146 if (head) { \ 147 (add)->prev = (head)->prev; \ 148 (head)->prev = (add); \ 149 } else \ 150 (add)->prev = (add); \ 151 (head) = (add); \ 152 } while (0) 153 154 #define DL_APPEND(head, add) \ 155 do { \ 156 if (head) { \ 157 (add)->prev = (head)->prev; \ 158 (head)->prev->next = (add); \ 159 (head)->prev = (add); \ 160 (add)->next = NULL; \ 161 } else { \ 162 (head) = (add); \ 163 (head)->prev = (head); \ 164 (head)->next = NULL; \ 165 } \ 166 } while (0) 167 168 #define DL_INSERT(head, next_node, add) \ 169 do { \ 170 if (head == next_node) \ 171 DL_PREPEND(head, add); \ 172 else if (next_node == NULL) { \ 173 DL_APPEND(head, add); \ 174 } else { \ 175 (add)->prev = (next_node)->prev; \ 176 (next_node)->prev->next = (add); \ 177 (add)->next = (next_node); \ 178 (next_node)->prev = (add); \ 179 } \ 180 } while (0) 181 182 #define DL_CONCAT(head1, head2) \ 183 do { \ 184 __typeof(head1) _tmp; \ 185 if (head2) { \ 186 if (head1) { \ 187 _tmp = (head2)->prev; \ 188 (head2)->prev = (head1)->prev; \ 189 (head1)->prev->next = (head2); \ 190 (head1)->prev = _tmp; \ 191 } else \ 192 (head1) = (head2); \ 193 } \ 194 } while (0) 195 196 #define DL_DELETE(head, del) \ 197 do { \ 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 214 /* Create a variable name using given prefix and current line number. */ 215 #define MAKE_NAME(prefix) TOKEN_PASTE2(prefix, __LINE__) 216 #define TOKEN_PASTE2(x, y) TOKEN_PASTE(x, y) 217 #define TOKEN_PASTE(x, y) x ## y 218 219 /* This version creates a temporary variable to to make it safe for deleting the 220 * elements during iteration. */ 221 #define DL_FOREACH(head, el) \ 222 DL_FOREACH_INTERNAL(head, el, MAKE_NAME(_dl_foreach_)) 223 #define DL_FOREACH_INTERNAL(head, el, tmp) \ 224 __typeof__(el) tmp; \ 225 for ((el) = (head); (el) && (tmp = (el)->next, 1); (el) = tmp) 226 227 /* These are identical to their singly-linked list counterparts. */ 228 #define DL_SEARCH_SCALAR LL_SEARCH_SCALAR 229 #define DL_SEARCH_SCALAR_WITH_CAST LL_SEARCH_SCALAR_WITH_CAST 230 #define DL_SEARCH LL_SEARCH 231 232 #endif /* UTLIST_H */ 233 234