1 /*! 2 * \file sccp_dllists.h 3 * \brief SCCP Double Linked Lists Header 4 * \note Double Linked List Code derived from Asterisk 1.6.1 "dlinkedlists.h" 5 * \author Mark Spencer <markster@digium.com> 6 * Kevin P. Fleming <kpfleming@digium.com> 7 * \note File is not directly included to get benefit of lists also in previous Asterisk releases (like 1.2) 8 * \note This program is free software and may be modified and distributed under the terms of the GNU Public License. 9 * See the LICENSE file at the top of the source tree. 10 * 11 */ 12 #pragma once 13 14 /* Lock Macro for Lists */ 15 #define SCCP_LIST_LOCK(x) pbx_mutex_lock(&(x)->lock) 16 #define SCCP_LIST_UNLOCK(x) pbx_mutex_unlock(&(x)->lock) 17 #define SCCP_LIST_TRYLOCK(x) pbx_mutex_trylock(&(x)->lock) 18 19 /* Lock Macro for read/write Lists */ 20 #define SCCP_RWLIST_RDLOCK(x) pbx_rwlock_rdlock(&(x)->lock) 21 #define SCCP_RWLIST_WRLOCK(x) pbx_rwlock_wrlock(&(x)->lock) 22 #define SCCP_RWLIST_UNLOCK(x) pbx_rwlock_unlock(&(x)->lock) 23 #define SCCP_RWLIST_TRYRDLOCK(x) pbx_rwlock_tryrdlock(&(x)->lock) 24 #define SCCP_RWLIST_TRYWRLOCK(x) pbx_rwlock_trywrlock(&(x)->lock) 25 26 /* Main list head */ 27 #define SCCP_LIST_HEAD(name, type) \ 28 struct name { \ 29 pbx_mutex_t lock; \ 30 type * first; \ 31 type * last; \ 32 uint32_t size; \ 33 } 34 35 #define SCCP_RWLIST_HEAD(name, type) \ 36 struct name { \ 37 pbx_rwlock_t lock; \ 38 type * first; \ 39 type * last; \ 40 uint32_t size; \ 41 } 42 43 /* Initialize list head */ 44 #define SCCP_LIST_HEAD_SET(head, entry) \ 45 do { \ 46 (head)->first = (entry); \ 47 (head)->last = (entry); \ 48 if (entry) \ 49 (head)->size = 1; \ 50 pbx_mutex_init(&(head)->lock); \ 51 } while (0) 52 53 /* Initialize rwlist head */ 54 #define SCCP_RWLIST_HEAD_SET(head, entry) \ 55 do { \ 56 (head)->first = (entry); \ 57 (head)->last = (entry); \ 58 if (entry) \ 59 (head)->size = 1; \ 60 pbx_rwlock_init(&(head)->lock); \ 61 } while (0) 62 63 /* List Item */ 64 #define SCCP_LIST_ENTRY(type) \ 65 struct { \ 66 type * prev; \ 67 type * next; \ 68 } 69 #define SCCP_RWLIST_ENTRY SCCP_LIST_ENTRY 70 71 /* List First Item */ 72 #define SCCP_LIST_FIRST(head) ((head)->first) 73 #define SCCP_RWLIST_FIRST SCCP_LIST_FIRST 74 75 /* List Last Item */ 76 #define SCCP_LIST_LAST(head) ((head)->last) 77 #define SCCP_RWLIST_LAST SCCP_LIST_LAST 78 79 /* List Next Item */ 80 #define SCCP_LIST_NEXT(elm, field) ((elm)->field.next) 81 #define SCCP_RWLIST_NEXT SCCP_LIST_NEXT 82 83 /* List Prev Item */ 84 #define SCCP_LIST_PREV(elm, field) ((elm)->field.prev) 85 #define SCCP_RWLIST_PREV SCCP_LIST_PREV 86 87 /* List Clear */ 88 #define SCCP_LIST_EMPTY(head) (SCCP_LIST_FIRST(head) == NULL) 89 #define SCCP_RWLIST_EMPTY SCCP_LIST_EMPTY 90 91 /* List Explore Routine */ 92 #define SCCP_LIST_TRAVERSE(head, var, field) for ((var) = (head)->first; (var); (var) = (var)->field.next) 93 #define SCCP_RWLIST_TRAVERSE SCCP_LIST_TRAVERSE 94 95 /* List Safe Explore Routine */ 96 #define SCCP_LIST_TRAVERSE_SAFE_BEGIN(head, var, field) \ 97 { \ 98 typeof((head)) __list_head = head; \ 99 typeof(__list_head->first) __list_next; \ 100 typeof(__list_head->first) __list_prev = NULL; \ 101 typeof(__list_head->first) __new_prev = NULL; \ 102 for ((var) = __list_head->first, __new_prev = (var), __list_next = (var) ? (var)->field.next : NULL; (var); \ 103 __list_prev = __new_prev, (var) = __list_next, __new_prev = (var), __list_next = (var) ? (var)->field.next : NULL) 104 #define SCCP_RWLIST_TRAVERSE_SAFE_BEGIN SCCP_LIST_TRAVERSE_SAFE_BEGIN 105 106 /* Current List Item Removal */ 107 #define SCCP_LIST_REMOVE_CURRENT(field) \ 108 do { \ 109 __new_prev->field.next = NULL; \ 110 __new_prev->field.prev = NULL; \ 111 if (__list_next) \ 112 __new_prev = __list_prev; \ 113 else \ 114 __new_prev = NULL; \ 115 if (__list_prev) { \ 116 if (__list_next) \ 117 __list_next->field.prev = __list_prev; \ 118 __list_prev->field.next = __list_next; \ 119 } else { \ 120 __list_head->first = __list_next; \ 121 if (__list_next) \ 122 __list_next->field.prev = NULL; \ 123 } \ 124 if (!__list_next) \ 125 __list_head->last = __list_prev; \ 126 __list_head->size--; \ 127 } while (0) 128 #define SCCP_RWLIST_REMOVE_CURRENT SCCP_LIST_REMOVE_CURRENT 129 130 /* Move Current List Item */ 131 #define SCCP_LIST_MOVE_CURRENT(newhead, field) \ 132 do { \ 133 typeof((newhead)->first) __list_cur = __new_prev; \ 134 SCCP_LIST_REMOVE_CURRENT(field); \ 135 SCCP_LIST_INSERT_TAIL((newhead), __list_cur, field); \ 136 } while (0) 137 #define SCCP_RWLIST_MOVE_CURRENT SCCP_LIST_MOVE_CURRENT 138 139 /* Move Current List Item Backward */ 140 #define SCCP_LIST_MOVE_CURRENT_BACKWARDS(newhead, field) \ 141 do { \ 142 typeof((newhead)->first) __list_cur = __new_prev; \ 143 if (!__list_next) { \ 144 SCCP_LIST_REMOVE_CURRENT(field); \ 145 __new_prev = NULL; \ 146 SCCP_LIST_INSERT_HEAD((newhead), __list_cur, field); \ 147 } else { \ 148 SCCP_LIST_REMOVE_CURRENT(field); \ 149 SCCP_LIST_INSERT_HEAD((newhead), __list_cur, field); \ 150 } \ 151 } while (0) 152 #define SCCP_RWLIST_MOVE_CURRENT_BACKWARDS SCCP_LIST_MOVE_CURRENT_BACKWARDS 153 154 /* List Item Insertion before element */ 155 #define SCCP_LIST_INSERT_BEFORE(head, listelm, elm, field) \ 156 do { \ 157 (elm)->field.next = (listelm); \ 158 (elm)->field.prev = (listelm)->field.prev; \ 159 if ((listelm)->field.prev) \ 160 (listelm)->field.prev->field.next = (elm); \ 161 (listelm)->field.prev = (elm); \ 162 if ((head)->first == (listelm)) \ 163 (head)->first = (elm); \ 164 (head)->size++; \ 165 } while (0) 166 #define SCCP_RWLIST_INSERT_BEFORE SCCP_LIST_INSERT_BEFORE 167 168 /* List Item Insertion before Current */ 169 #define SCCP_LIST_INSERT_BEFORE_CURRENT(elm, field) \ 170 do { \ 171 if (__list_prev) { \ 172 (elm)->field.next = __list_prev->field.next; \ 173 (elm)->field.prev = __list_prev; \ 174 if (__list_prev->field.next) \ 175 __list_prev->field.next->field.prev = (elm); \ 176 __list_prev->field.next = (elm); \ 177 } else { \ 178 (elm)->field.next = __list_head->first; \ 179 __list_head->first->field.prev = (elm); \ 180 (elm)->field.prev = NULL; \ 181 __list_head->first = (elm); \ 182 } \ 183 (head)->size++; \ 184 } while (0) 185 #define SCCP_RWLIST_INSERT_BEFORE_CURRENT SCCP_LIST_INSERT_BEFORE_CURRENT 186 187 /* List Item Insertion before Current Backwards */ 188 #define SCCP_LIST_INSERT_BEFORE_CURRENT_BACKWARDS(elm, field) \ 189 do { \ 190 if (__list_next) { \ 191 (elm)->field.next = __list_next; \ 192 (elm)->field.prev = __new_prev; \ 193 __new_prev->field.next = (elm); \ 194 __list_next->field.prev = (elm); \ 195 } else { \ 196 (elm)->field.prev = __list_head->last; \ 197 (elm)->field.next = NULL; \ 198 __list_head->last->field.next = (elm); \ 199 __list_head->last = (elm); \ 200 } \ 201 (head)->size++; \ 202 } while (0) 203 #define SCCP_RWLIST_INSERT_BEFORE_CURRENT_BACKWARDS SCCP_LIST_INSERT_BEFORE_CURRENT_BACKWARDS 204 205 /* List Traverse End (Parentesis) */ 206 #define SCCP_LIST_TRAVERSE_SAFE_END \ 207 (void)__list_prev; /* to quiet compiler */ \ 208 } 209 #define SCCP_RWLIST_TRAVERSE_SAFE_END SCCP_LIST_TRAVERSE_SAFE_END 210 211 /* List Backward Explore Routine */ 212 #define SCCP_LIST_TRAVERSE_BACKWARDS(head, var, field) for ((var) = (head)->last; (var); (var) = (var)->field.prev) 213 #define SCCP_RWLIST_TRAVERSE_BACKWARDS SCCP_LIST_TRAVERSE_BACKWARDS 214 215 /* List Safe Backward Explore Routine */ 216 #define SCCP_LIST_TRAVERSE_BACKWARDS_SAFE_BEGIN(head, var, field) \ 217 { \ 218 typeof((head)) __list_head = head; \ 219 typeof(__list_head->first) __list_prev; \ 220 typeof(__list_head->first) __list_next = NULL; \ 221 typeof(__list_head->first) __new_next = NULL; \ 222 for ((var) = __list_head->last, __new_next = (var), __list_prev = (var) ? (var)->field.prev : NULL; (var); \ 223 __list_next = __new_next, (var) = __list_prev, __new_next = (var), __list_prev = (var) ? (var)->field.prev : NULL) 224 #define SCCP_RWLIST_TRAVERSE_BACKWARDS_SAFE_BEGIN SCCP_LIST_TRAVERSE_BACKWARDS_SAFE_BEGIN 225 226 /* List Backward Traverse End (Parentesis) */ 227 #define SCCP_LIST_TRAVERSE_BACKWARDS_SAFE_END \ 228 (void)__list_next; /* to quiet compiler */ \ 229 } 230 #define SCCP_RWLIST_TRAVERSE_BACKWARDS_SAFE_END SCCP_LIST_TRAVERSE_BACKWARDS_SAFE_END 231 232 /* List Head Init */ 233 #define SCCP_LIST_HEAD_INIT(head) \ 234 { \ 235 (head)->first = NULL; \ 236 (head)->last = NULL; \ 237 pbx_mutex_init_notracking(&(head)->lock); \ 238 (head)->size = 0; \ 239 } 240 #define SCCP_RWLIST_HEAD_INIT(head) \ 241 { \ 242 (head)->first = NULL; \ 243 (head)->last = NULL; \ 244 pbx_rwlock_init_notracking(&(head)->lock); \ 245 (head)->size = 0; \ 246 } 247 248 /* List Head Destroy */ 249 #define SCCP_LIST_HEAD_DESTROY(head) \ 250 { \ 251 (head)->first = NULL; \ 252 (head)->last = NULL; \ 253 pbx_mutex_destroy(&(head)->lock); \ 254 (head)->size = 0; \ 255 } 256 #define SCCP_RWLIST_HEAD_DESTROY(head) \ 257 { \ 258 (head)->first = NULL; \ 259 (head)->last = NULL; \ 260 pbx_rwlock_destroy(&(head)->lock); \ 261 (head)->size = 0; \ 262 } 263 264 /* List Item Insertion After */ 265 #define SCCP_LIST_INSERT_AFTER(head, listelm, elm, field) \ 266 do { \ 267 (elm)->field.next = (listelm)->field.next; \ 268 (elm)->field.prev = (listelm); \ 269 if ((listelm)->field.next) \ 270 (listelm)->field.next->field.prev = (elm); \ 271 (listelm)->field.next = (elm); \ 272 if ((head)->last == (listelm)) \ 273 (head)->last = (elm); \ 274 (head)->size++; \ 275 } while (0) 276 #define SCCP_RWLIST_INSERT_AFTER SCCP_LIST_INSERT_AFTER 277 278 /* List Insertion in Alphanumeric Order */ 279 #define SCCP_LIST_INSERT_SORTALPHA(head, elm, field, sortfield) \ 280 do { \ 281 if (!(head)->first) { \ 282 (head)->first = (elm); \ 283 (head)->last = (elm); \ 284 } else { \ 285 typeof((head)->first) cur = (head)->first, prev = NULL; \ 286 while (cur && sccp_strversioncmp((cur)->sortfield, (elm)->sortfield) < 0) { \ 287 prev = cur; \ 288 cur = cur->field.next; \ 289 } \ 290 if (!prev) { \ 291 SCCP_LIST_INSERT_HEAD(head, elm, field); \ 292 } else if (!cur) { \ 293 SCCP_LIST_INSERT_TAIL(head, elm, field); \ 294 } else { \ 295 SCCP_LIST_INSERT_AFTER(head, prev, elm, field); \ 296 } \ 297 } \ 298 (head)->size++; \ 299 } while (0) 300 #define SCCP_RWLIST_INSERT_SORTALPHA SCCP_LIST_INSERT_SORTALPHA 301 302 /* Inserts a list item at the head of a list. */ 303 #define SCCP_LIST_INSERT_HEAD(head, elm, field) \ 304 do { \ 305 (elm)->field.next = (head)->first; \ 306 if ((head)->first) \ 307 (head)->first->field.prev = (elm); \ 308 (elm)->field.prev = NULL; \ 309 (head)->first = (elm); \ 310 if (!(head)->last) \ 311 (head)->last = (elm); \ 312 (head)->size++; \ 313 } while (0) 314 #define SCCP_RWLIST_INSERT_HEAD SCCP_LIST_INSERT_HEAD 315 316 /* Inserts a list item at the tail of a list */ 317 #define SCCP_LIST_INSERT_TAIL(head, elm, field) \ 318 do { \ 319 if (!(head)->first) { \ 320 (head)->first = (elm); \ 321 (head)->last = (elm); \ 322 (elm)->field.next = NULL; \ 323 (elm)->field.prev = NULL; \ 324 } else { \ 325 (head)->last->field.next = (elm); \ 326 (elm)->field.prev = (head)->last; \ 327 (elm)->field.next = NULL; \ 328 (head)->last = (elm); \ 329 } \ 330 (head)->size++; \ 331 } while (0) 332 #define SCCP_RWLIST_INSERT_TAIL SCCP_LIST_INSERT_TAIL 333 334 /* Append a whole list to another */ 335 #define SCCP_LIST_APPEND_LIST(head, list, field) \ 336 do { \ 337 if (!(head)->first) { \ 338 (head)->first = (list)->first; \ 339 (head)->last = (list)->last; \ 340 (head)->size = (list)->size; \ 341 } else { \ 342 (head)->last->field.next = (list)->first; \ 343 (list)->first->field.prev = (head)->last; \ 344 (head)->last = (list)->last; \ 345 (head)->size += (list)->size; \ 346 } \ 347 (list)->first = NULL; \ 348 (list)->last = NULL; \ 349 } while (0) 350 #define SCCP_RWLIST_APPEND_LIST SCCP_LIST_APPEND_LIST 351 352 /* Remove the head item from a list giving back a pointer to it. */ 353 #define SCCP_LIST_REMOVE_HEAD(head, field) \ 354 ({ \ 355 typeof((head)->first) cur = (head)->first; \ 356 if (cur) { \ 357 (head)->first = cur->field.next; \ 358 if (cur->field.next) \ 359 cur->field.next->field.prev = NULL; \ 360 cur->field.next = NULL; \ 361 if ((head)->last == cur) \ 362 (head)->last = NULL; \ 363 (head)->size--; \ 364 } \ 365 cur; \ 366 }) 367 #define SCCP_RWLIST_REMOVE_HEAD SCCP_LIST_REMOVE_HEAD 368 369 /* Remove an item from a list */ 370 #define SCCP_LIST_REMOVE(head, elm, field) \ 371 ({ \ 372 __typeof(elm) __res = (elm); \ 373 if ((head)->first == (elm)) { \ 374 (head)->first = (elm)->field.next; \ 375 if ((elm)->field.next) \ 376 (elm)->field.next->field.prev = NULL; \ 377 if ((head)->last == (elm)) \ 378 (head)->last = NULL; \ 379 (head)->size--; \ 380 } else if ((elm)->field.prev != NULL) { \ 381 (elm)->field.prev->field.next = (elm)->field.next; \ 382 if ((elm)->field.next) \ 383 (elm)->field.next->field.prev = (elm)->field.prev; \ 384 if ((head)->last == (elm)) \ 385 (head)->last = (elm)->field.prev; \ 386 (head)->size--; \ 387 } \ 388 (elm)->field.next = NULL; \ 389 (elm)->field.prev = NULL; \ 390 (__res); \ 391 }) 392 #define SCCP_RWLIST_REMOVE SCCP_LIST_REMOVE 393 394 /* Expensive SCCP_LIST_FIND version: only used during refcount issue finding */ 395 /* 396 #define SCCP_LIST_FIND(_head, _type, _var, _field, _compare, _retain, _file, _line, _func) ({ \ 397 _type *_var; \ 398 _type *__tmp_##_var##_line; \ 399 for((_var) = (_head)->first; (_var); (_var) = (_var)->_field.next) { \ 400 __tmp_##_var##_line = sccp_refcount_retain((_var), _file, _line, _func); \ 401 if (__tmp_##_var##_line) { \ 402 if (_compare) { \ 403 if (!_retain) { \ 404 sccp_refcount_release(__tmp_##_var##_line, _file, _line, _func);\ 405 } \ 406 break; \ 407 } \ 408 sccp_refcount_release(__tmp_##_var##_line, _file, _line, _func); \ 409 } else { \ 410 pbx_log(LOG_ERROR, "SCCP (%s:%d:%s): Failed to get reference to variable during SCCP_LIST_FIND\n", _file, _line, _func);\ 411 (_var) = NULL; \ 412 } \ 413 } \ 414 (_var); \ 415 }) 416 */ 417 #define SCCP_LIST_FIND(_head, _type, _var, _field, _compare, _retain, _file, _line, _func) \ 418 ({ \ 419 _type * _var; \ 420 for ((_var) = (_head)->first; (_var); (_var) = (_var)->_field.next) { \ 421 if (_compare) { \ 422 if (_retain) { \ 423 sccp_refcount_retain((_var), _file, _line, _func); \ 424 } \ 425 break; \ 426 } \ 427 } \ 428 (_var); \ 429 }) 430 431 #define SCCP_RWLIST_FIND SCCP_LIST_FIND 432 433 #define SCCP_LIST_GETSIZE(head) (head)->size 434 #define SCCP_RWLIST_GETSIZE SCCP_LIST_GETSIZE 435 // kate: indent-width 8; replace-tabs off; indent-mode cstyle; auto-insert-doxygen on; line-numbers on; tab-indents on; keep-extra-spaces off; auto-brackets off; 436