| 1 |
#pragma once |
| 2 |
|
| 3 |
/* |
| 4 |
* Circular Intrusive Double Linked List Collection in ISO-C11 |
| 5 |
* |
| 6 |
* This implements a generic circular double linked list. List entries must |
| 7 |
* embed the CList object, which provides pointers to the next and previous |
| 8 |
* element. Insertion and removal can be done in O(1) due to the double links. |
| 9 |
* Furthermore, the list is circular, thus allows access to front/tail in O(1) |
| 10 |
* as well, even if you only have a single head pointer (which is not how the |
| 11 |
* list is usually operated, though). |
| 12 |
* |
| 13 |
* Note that you are free to use the list implementation without a head |
| 14 |
* pointer. However, usual operation uses a single CList object as head, which |
| 15 |
* is itself linked in the list and as such must be identified as list head. |
| 16 |
* This allows very simply list operations and avoids a lot of special cases. |
| 17 |
* Most importantly, you can unlink entries without requiring a head pointer. |
| 18 |
*/ |
| 19 |
|
| 20 |
#ifdef __cplusplus |
| 21 |
extern "C" { |
| 22 |
#endif |
| 23 |
|
| 24 |
#include <stddef.h> |
| 25 |
#include <stdint.h> |
| 26 |
|
| 27 |
typedef struct CList CList; |
| 28 |
|
| 29 |
/** |
| 30 |
* struct CList - Entry of a circular double linked list |
| 31 |
* @next: next entry |
| 32 |
* @prev: previous entry |
| 33 |
* |
| 34 |
* Each entry in a list must embed a CList object. This object contains |
| 35 |
* pointers to its next and previous elements, which can be freely accessed by |
| 36 |
* the API user at any time. Note that the list is circular, and the list head |
| 37 |
* is linked in the list as well. |
| 38 |
* |
| 39 |
* The list head must be initialized via C_LIST_INIT before use. There is no |
| 40 |
* reason to initialize entry objects before linking them. However, if you need |
| 41 |
* a boolean state that tells you whether the entry is linked or not, you should |
| 42 |
* initialize the entry via C_LIST_INIT as well. |
| 43 |
*/ |
| 44 |
struct CList { |
| 45 |
CList *next; |
| 46 |
CList *prev; |
| 47 |
}; |
| 48 |
|
| 49 |
#define C_LIST_INIT(_var) { .next = &(_var), .prev = &(_var) } |
| 50 |
|
| 51 |
/** |
| 52 |
* c_list_init() - initialize list entry |
| 53 |
* @what: list entry to initialize |
| 54 |
* |
| 55 |
* Return: @what is returned. |
| 56 |
*/ |
| 57 |
static inline CList *c_list_init(CList *what) { |
| 58 |
*what = (CList)C_LIST_INIT(*what); |
| 59 |
return what; |
| 60 |
} |
| 61 |
|
| 62 |
/** |
| 63 |
* c_list_entry_offset() - get parent container of list entry |
| 64 |
* @what: list entry, or NULL |
| 65 |
* @offset: offset of the list member in its surrounding type |
| 66 |
* |
| 67 |
* If the list entry @what is embedded into a surrounding structure, this will |
| 68 |
* turn the list entry pointer @what into a pointer to the parent container |
| 69 |
* (sometimes called container_of(3)). Use the `c_list_entry()` macro for an |
| 70 |
* easier API. |
| 71 |
* |
| 72 |
* If @what is NULL, this will also return NULL. |
| 73 |
* |
| 74 |
* Return: Pointer to parent container, or NULL. |
| 75 |
*/ |
| 76 |
static inline void *c_list_entry_offset(const CList *what, size_t offset) { |
| 77 |
if (what) { |
| 78 |
/* |
| 79 |
* We allow calling "c_list_entry()" on the list head, which is |
| 80 |
* commonly a plain CList struct. The returned entry pointer is |
| 81 |
* thus invalid. For instance, this is used by the |
| 82 |
* c_list_for_each_entry*() macros. Gcc correctly warns about that |
| 83 |
* with "-Warray-bounds". However, as long as the value is never |
| 84 |
* dereferenced, this is fine. We explicitly use integer arithmetic |
| 85 |
* to circumvent the Gcc warning. |
| 86 |
*/ |
| 87 |
return (void *)(((uintptr_t)(void *)what) - offset); |
| 88 |
} |
| 89 |
return NULL; |
| 90 |
} |
| 91 |
|
| 92 |
/** |
| 93 |
* c_list_entry() - get parent container of list entry |
| 94 |
* @_what: list entry, or NULL |
| 95 |
* @_t: type of parent container |
| 96 |
* @_m: member name of list entry in @_t |
| 97 |
* |
| 98 |
* If the list entry @_what is embedded into a surrounding structure, this will |
| 99 |
* turn the list entry pointer @_what into a pointer to the parent container |
| 100 |
* (using offsetof(3), or sometimes called container_of(3)). |
| 101 |
* |
| 102 |
* If @_what is NULL, this will also return NULL. |
| 103 |
* |
| 104 |
* Return: Pointer to parent container, or NULL. |
| 105 |
*/ |
| 106 |
#define c_list_entry(_what, _t, _m) \ |
| 107 |
((_t *)c_list_entry_offset((_what), offsetof(_t, _m))) |
| 108 |
|
| 109 |
/** |
| 110 |
* c_list_is_linked() - check whether an entry is linked |
| 111 |
* @what: entry to check, or NULL |
| 112 |
* |
| 113 |
* Return: True if @what is linked in a list, false if not. |
| 114 |
*/ |
| 115 |
static inline _Bool c_list_is_linked(const CList *what) { |
| 116 |
return what && what->next != what; |
| 117 |
} |
| 118 |
|
| 119 |
/** |
| 120 |
* c_list_is_empty() - check whether a list is empty |
| 121 |
* @list: list to check, or NULL |
| 122 |
* |
| 123 |
* This is the same as !c_list_is_linked(). |
| 124 |
* |
| 125 |
* Return: True if @list is empty, false if not. |
| 126 |
*/ |
| 127 |
static inline _Bool c_list_is_empty(const CList *list) { |
| 128 |
return !c_list_is_linked(list); |
| 129 |
} |
| 130 |
|
| 131 |
/** |
| 132 |
* c_list_link_before() - link entry into list |
| 133 |
* @where: linked list entry used as anchor |
| 134 |
* @what: entry to link |
| 135 |
* |
| 136 |
* This links @what directly in front of @where. @where can either be a list |
| 137 |
* head or any entry in the list. |
| 138 |
* |
| 139 |
* If @where points to the list head, this effectively links @what as new tail |
| 140 |
* element. Hence, the macro c_list_link_tail() is an alias to this. |
| 141 |
* |
| 142 |
* @what is not inspected prior to being linked. Hence, it better not be linked |
| 143 |
* into another list, or the other list will be corrupted. |
| 144 |
*/ |
| 145 |
static inline void c_list_link_before(CList *where, CList *what) { |
| 146 |
CList *prev = where->prev, *next = where; |
| 147 |
|
| 148 |
next->prev = what; |
| 149 |
what->next = next; |
| 150 |
what->prev = prev; |
| 151 |
prev->next = what; |
| 152 |
} |
| 153 |
#define c_list_link_tail(_list, _what) c_list_link_before((_list), (_what)) |
| 154 |
|
| 155 |
/** |
| 156 |
* c_list_link_after() - link entry into list |
| 157 |
* @where: linked list entry used as anchor |
| 158 |
* @what: entry to link |
| 159 |
* |
| 160 |
* This links @what directly after @where. @where can either be a list head or |
| 161 |
* any entry in the list. |
| 162 |
* |
| 163 |
* If @where points to the list head, this effectively links @what as new front |
| 164 |
* element. Hence, the macro c_list_link_front() is an alias to this. |
| 165 |
* |
| 166 |
* @what is not inspected prior to being linked. Hence, it better not be linked |
| 167 |
* into another list, or the other list will be corrupted. |
| 168 |
*/ |
| 169 |
static inline void c_list_link_after(CList *where, CList *what) { |
| 170 |
CList *prev = where, *next = where->next; |
| 171 |
|
| 172 |
next->prev = what; |
| 173 |
what->next = next; |
| 174 |
what->prev = prev; |
| 175 |
prev->next = what; |
| 176 |
} |
| 177 |
#define c_list_link_front(_list, _what) c_list_link_after((_list), (_what)) |
| 178 |
|
| 179 |
/** |
| 180 |
* c_list_unlink_stale() - unlink element from list |
| 181 |
* @what: element to unlink |
| 182 |
* |
| 183 |
* This unlinks @what. If @what was initialized via C_LIST_INIT(), it has no |
| 184 |
* effect. If @what was never linked, nor initialized, behavior is undefined. |
| 185 |
* |
| 186 |
* Note that this does not modify @what. It just modifies the previous and next |
| 187 |
* elements in the list to no longer reference @what. If you want to make sure |
| 188 |
* @what is re-initialized after removal, use c_list_unlink(). |
| 189 |
*/ |
| 190 |
static inline void c_list_unlink_stale(CList *what) { |
| 191 |
CList *prev = what->prev, *next = what->next; |
| 192 |
|
| 193 |
next->prev = prev; |
| 194 |
prev->next = next; |
| 195 |
} |
| 196 |
|
| 197 |
/** |
| 198 |
* c_list_unlink() - unlink element from list and re-initialize |
| 199 |
* @what: element to unlink |
| 200 |
* |
| 201 |
* This is like c_list_unlink_stale() but re-initializes @what after removal. |
| 202 |
*/ |
| 203 |
static inline void c_list_unlink(CList *what) { |
| 204 |
/* condition is not needed, but avoids STOREs in fast-path */ |
| 205 |
if (c_list_is_linked(what)) { |
| 206 |
c_list_unlink_stale(what); |
| 207 |
*what = (CList)C_LIST_INIT(*what); |
| 208 |
} |
| 209 |
} |
| 210 |
|
| 211 |
/** |
| 212 |
* c_list_swap() - exchange the contents of two lists |
| 213 |
* @list1: the list to operate on |
| 214 |
* @list2: the list to operate on |
| 215 |
* |
| 216 |
* This replaces the contents of the list @list1 with the contents |
| 217 |
* of @list2, and vice versa. |
| 218 |
*/ |
| 219 |
static inline void c_list_swap(CList *list1, CList *list2) { |
| 220 |
CList t; |
| 221 |
|
| 222 |
/* make neighbors of list1 point to list2, and vice versa */ |
| 223 |
t = *list1; |
| 224 |
t.next->prev = list2; |
| 225 |
t.prev->next = list2; |
| 226 |
t = *list2; |
| 227 |
t.next->prev = list1; |
| 228 |
t.prev->next = list1; |
| 229 |
|
| 230 |
/* swap list1 and list2 now that their neighbors were fixed up */ |
| 231 |
t = *list1; |
| 232 |
*list1 = *list2; |
| 233 |
*list2 = t; |
| 234 |
} |
| 235 |
|
| 236 |
/** |
| 237 |
* c_list_splice() - splice one list into another |
| 238 |
* @target: the list to splice into |
| 239 |
* @source: the list to splice |
| 240 |
* |
| 241 |
* This removes all the entries from @source and splice them into @target. |
| 242 |
* The order of the two lists is preserved and the source is appended |
| 243 |
* to the end of target. |
| 244 |
* |
| 245 |
* On return, the source list will be empty. |
| 246 |
*/ |
| 247 |
static inline void c_list_splice(CList *target, CList *source) { |
| 248 |
if (!c_list_is_empty(source)) { |
| 249 |
/* attach the front of @source to the tail of @target */ |
| 250 |
source->next->prev = target->prev; |
| 251 |
target->prev->next = source->next; |
| 252 |
|
| 253 |
/* attach the tail of @source to the front of @target */ |
| 254 |
source->prev->next = target; |
| 255 |
target->prev = source->prev; |
| 256 |
|
| 257 |
/* clear source */ |
| 258 |
*source = (CList)C_LIST_INIT(*source); |
| 259 |
} |
| 260 |
} |
| 261 |
|
| 262 |
/** |
| 263 |
* c_list_split() - split one list in two |
| 264 |
* @source: the list to split |
| 265 |
* @where: new starting element of newlist |
| 266 |
* @target: new list |
| 267 |
* |
| 268 |
* This splits @source in two. All elements following @where (including @where) |
| 269 |
* are moved to @target, replacing any old list. If @where points to @source |
| 270 |
* (i.e., the end of the list), @target will be empty. |
| 271 |
*/ |
| 272 |
static inline void c_list_split(CList *source, CList *where, CList *target) { |
| 273 |
if (where == source) { |
| 274 |
*target = (CList)C_LIST_INIT(*target); |
| 275 |
} else { |
| 276 |
target->next = where; |
| 277 |
target->prev = source->prev; |
| 278 |
|
| 279 |
where->prev->next = source; |
| 280 |
source->prev = where->prev; |
| 281 |
|
| 282 |
where->prev = target; |
| 283 |
target->prev->next = target; |
| 284 |
} |
| 285 |
} |
| 286 |
|
| 287 |
/** |
| 288 |
* c_list_first() - return pointer to first element, or NULL if empty |
| 289 |
* @list: list to operate on, or NULL |
| 290 |
* |
| 291 |
* This returns a pointer to the first element, or NULL if empty. This never |
| 292 |
* returns a pointer to the list head. |
| 293 |
* |
| 294 |
* Return: Pointer to first list element, or NULL if empty. |
| 295 |
*/ |
| 296 |
static inline CList *c_list_first(CList *list) { |
| 297 |
return c_list_is_empty(list) ? NULL : list->next; |
| 298 |
} |
| 299 |
|
| 300 |
/** |
| 301 |
* c_list_last() - return pointer to last element, or NULL if empty |
| 302 |
* @list: list to operate on, or NULL |
| 303 |
* |
| 304 |
* This returns a pointer to the last element, or NULL if empty. This never |
| 305 |
* returns a pointer to the list head. |
| 306 |
* |
| 307 |
* Return: Pointer to last list element, or NULL if empty. |
| 308 |
*/ |
| 309 |
static inline CList *c_list_last(CList *list) { |
| 310 |
return c_list_is_empty(list) ? NULL : list->prev; |
| 311 |
} |
| 312 |
|
| 313 |
/** |
| 314 |
* c_list_first_entry() - return pointer to first entry, or NULL if empty |
| 315 |
* @_list: list to operate on, or NULL |
| 316 |
* @_t: type of list entries |
| 317 |
* @_m: name of CList member in @_t |
| 318 |
* |
| 319 |
* This is like c_list_first(), but also applies c_list_entry() on the result. |
| 320 |
* |
| 321 |
* Return: Pointer to first list entry, or NULL if empty. |
| 322 |
*/ |
| 323 |
#define c_list_first_entry(_list, _t, _m) \ |
| 324 |
c_list_entry(c_list_first(_list), _t, _m) |
| 325 |
|
| 326 |
/** |
| 327 |
* c_list_last_entry() - return pointer to last entry, or NULL if empty |
| 328 |
* @_list: list to operate on, or NULL |
| 329 |
* @_t: type of list entries |
| 330 |
* @_m: name of CList member in @_t |
| 331 |
* |
| 332 |
* This is like c_list_last(), but also applies c_list_entry() on the result. |
| 333 |
* |
| 334 |
* Return: Pointer to last list entry, or NULL if empty. |
| 335 |
*/ |
| 336 |
#define c_list_last_entry(_list, _t, _m) \ |
| 337 |
c_list_entry(c_list_last(_list), _t, _m) |
| 338 |
|
| 339 |
/** |
| 340 |
* c_list_for_each*() - iterators |
| 341 |
* |
| 342 |
* The c_list_for_each*() macros provide simple for-loop wrappers to iterate |
| 343 |
* a linked list. They come in a set of flavours: |
| 344 |
* |
| 345 |
* - "entry": This combines c_list_entry() with the loop iterator, so the |
| 346 |
* iterator always has the type of the surrounding object, rather |
| 347 |
* than CList. |
| 348 |
* |
| 349 |
* - "safe": The loop iterator always keeps track of the next element to |
| 350 |
* visit. This means, you can safely modify the current element, |
| 351 |
* while retaining loop-integrity. |
| 352 |
* You still must not touch any other entry of the list. Otherwise, |
| 353 |
* the loop-iterator will be corrupted. |
| 354 |
* |
| 355 |
* - "continue": Rather than starting the iteration at the front of the list, |
| 356 |
* use the current value of the iterator as starting position. |
| 357 |
* Note that the first loop iteration will be the following |
| 358 |
* element, not the given element. |
| 359 |
* |
| 360 |
* - "unlink": This unlinks the current element from the list before the loop |
| 361 |
* code is run. Note that this only does a partial unlink, since |
| 362 |
* it assumes the entire list will be unlinked. You must not |
| 363 |
* break out of the loop, or the list will be in an inconsistent |
| 364 |
* state. |
| 365 |
*/ |
| 366 |
|
| 367 |
/* direct/raw iterators */ |
| 368 |
|
| 369 |
#define c_list_for_each(_iter, _list) \ |
| 370 |
for (_iter = (_list)->next; \ |
| 371 |
(_iter) != (_list); \ |
| 372 |
_iter = (_iter)->next) |
| 373 |
|
| 374 |
#define c_list_for_each_safe(_iter, _safe, _list) \ |
| 375 |
for (_iter = (_list)->next, _safe = (_iter)->next; \ |
| 376 |
(_iter) != (_list); \ |
| 377 |
_iter = (_safe), _safe = (_safe)->next) |
| 378 |
|
| 379 |
#define c_list_for_each_continue(_iter, _list) \ |
| 380 |
for (_iter = (_iter) ? (_iter)->next : (_list)->next; \ |
| 381 |
(_iter) != (_list); \ |
| 382 |
_iter = (_iter)->next) |
| 383 |
|
| 384 |
#define c_list_for_each_safe_continue(_iter, _safe, _list) \ |
| 385 |
for (_iter = (_iter) ? (_iter)->next : (_list)->next, \ |
| 386 |
_safe = (_iter)->next; \ |
| 387 |
(_iter) != (_list); \ |
| 388 |
_iter = (_safe), _safe = (_safe)->next) |
| 389 |
|
| 390 |
#define c_list_for_each_safe_unlink(_iter, _safe, _list) \ |
| 391 |
for (_iter = (_list)->next, _safe = (_iter)->next; \ |
| 392 |
c_list_init(_iter) != (_list); \ |
| 393 |
_iter = (_safe), _safe = (_safe)->next) |
| 394 |
|
| 395 |
/* c_list_entry() based iterators */ |
| 396 |
|
| 397 |
#define c_list_for_each_entry(_iter, _list, _m) \ |
| 398 |
for (_iter = c_list_entry((_list)->next, __typeof__(*_iter), _m); \ |
| 399 |
&(_iter)->_m != (_list); \ |
| 400 |
_iter = c_list_entry((_iter)->_m.next, __typeof__(*_iter), _m)) |
| 401 |
|
| 402 |
#define c_list_for_each_entry_safe(_iter, _safe, _list, _m) \ |
| 403 |
for (_iter = c_list_entry((_list)->next, __typeof__(*_iter), _m), \ |
| 404 |
_safe = c_list_entry((_iter)->_m.next, __typeof__(*_iter), _m); \ |
| 405 |
&(_iter)->_m != (_list); \ |
| 406 |
_iter = (_safe), \ |
| 407 |
_safe = c_list_entry((_safe)->_m.next, __typeof__(*_iter), _m)) |
| 408 |
|
| 409 |
#define c_list_for_each_entry_continue(_iter, _list, _m) \ |
| 410 |
for (_iter = c_list_entry((_iter) ? (_iter)->_m.next : (_list)->next, \ |
| 411 |
__typeof__(*_iter), \ |
| 412 |
_m); \ |
| 413 |
&(_iter)->_m != (_list); \ |
| 414 |
_iter = c_list_entry((_iter)->_m.next, __typeof__(*_iter), _m)) |
| 415 |
|
| 416 |
#define c_list_for_each_entry_safe_continue(_iter, _safe, _list, _m) \ |
| 417 |
for (_iter = c_list_entry((_iter) ? (_iter)->_m.next : (_list)->next, \ |
| 418 |
__typeof__(*_iter), \ |
| 419 |
_m), \ |
| 420 |
_safe = c_list_entry((_iter)->_m.next, __typeof__(*_iter), _m); \ |
| 421 |
&(_iter)->_m != (_list); \ |
| 422 |
_iter = (_safe), \ |
| 423 |
_safe = c_list_entry((_safe)->_m.next, __typeof__(*_iter), _m)) |
| 424 |
|
| 425 |
#define c_list_for_each_entry_safe_unlink(_iter, _safe, _list, _m) \ |
| 426 |
for (_iter = c_list_entry((_list)->next, __typeof__(*_iter), _m), \ |
| 427 |
_safe = c_list_entry((_iter)->_m.next, __typeof__(*_iter), _m); \ |
| 428 |
c_list_init(&(_iter)->_m) != (_list); \ |
| 429 |
_iter = (_safe), \ |
| 430 |
_safe = c_list_entry((_safe)->_m.next, __typeof__(*_iter), _m)) |
| 431 |
|
| 432 |
/** |
| 433 |
* c_list_flush() - flush all entries from a list |
| 434 |
* @list: list to flush |
| 435 |
* |
| 436 |
* This unlinks all entries from the given list @list and reinitializes their |
| 437 |
* link-nodes via C_LIST_INIT(). |
| 438 |
* |
| 439 |
* Note that the entries are not modified in any other way, nor is their memory |
| 440 |
* released. This function just unlinks them and resets all the list nodes. It |
| 441 |
* is particularly useful with temporary lists on the stack in combination with |
| 442 |
* the GCC-extension __attribute__((__cleanup__(arg))). |
| 443 |
*/ |
| 444 |
static inline void c_list_flush(CList *list) { |
| 445 |
CList *iter, *safe; |
| 446 |
|
| 447 |
c_list_for_each_safe_unlink(iter, safe, list) |
| 448 |
/* empty */ ; |
| 449 |
} |
| 450 |
|
| 451 |
/** |
| 452 |
* c_list_length() - return number of linked entries, excluding the head |
| 453 |
* @list: list to operate on |
| 454 |
* |
| 455 |
* Returns the number of entries in the list, excluding the list head @list. |
| 456 |
* That is, for a list that is empty according to c_list_is_empty(), the |
| 457 |
* returned length is 0. This requires to iterate the list and has thus O(n) |
| 458 |
* runtime. |
| 459 |
* |
| 460 |
* Note that this function is meant for debugging purposes only. If you need |
| 461 |
* the list size during normal operation, you should maintain a counter |
| 462 |
* separately. |
| 463 |
* |
| 464 |
* Return: Number of items in @list. |
| 465 |
*/ |
| 466 |
static inline size_t c_list_length(const CList *list) { |
| 467 |
size_t n = 0; |
| 468 |
const CList *iter; |
| 469 |
|
| 470 |
c_list_for_each(iter, list) |
| 471 |
++n; |
| 472 |
|
| 473 |
return n; |
| 474 |
} |
| 475 |
|
| 476 |
/** |
| 477 |
* c_list_contains() - check whether an entry is linked in a certain list |
| 478 |
* @list: list to operate on |
| 479 |
* @what: entry to look for |
| 480 |
* |
| 481 |
* This checks whether @what is linked into @list. This requires a linear |
| 482 |
* search through the list, as such runs in O(n). Note that the list-head is |
| 483 |
* considered part of the list, and hence this returns true if @what equals |
| 484 |
* @list. |
| 485 |
* |
| 486 |
* Note that this function is meant for debugging purposes, and consistency |
| 487 |
* checks. You should always be aware whether your objects are linked in a |
| 488 |
* specific list. |
| 489 |
* |
| 490 |
* Return: True if @what is in @list, false otherwise. |
| 491 |
*/ |
| 492 |
static inline _Bool c_list_contains(const CList *list, const CList *what) { |
| 493 |
const CList *iter; |
| 494 |
|
| 495 |
c_list_for_each(iter, list) |
| 496 |
if (what == iter) |
| 497 |
return 1; |
| 498 |
|
| 499 |
return what == list; |
| 500 |
} |
| 501 |
|
| 502 |
#ifdef __cplusplus |
| 503 |
} |
| 504 |
#endif |