src/list.h

   1 // Copyright © Tavian Barnes <tavianator@tavianator.com>
   2 // SPDX-License-Identifier: 0BSD
   3
   4 /**
   5  * Intrusive linked lists.
   6  *
   7  * Singly-linked lists are declared like this:
   8  *
   9  *     struct item {
  10  *             struct item *next;
  11  *     };
  12  *
  13  *     struct list {
  14  *             struct item *head;
  15  *             struct item **tail;
  16  *     };
  17  *
  18  * The SLIST_*() macros manipulate singly-linked lists.
  19  *
  20  *     struct list list;
  21  *     SLIST_INIT(&list);
  22  *
  23  *     struct item item;
  24  *     SLIST_ITEM_INIT(&item);
  25  *     SLIST_APPEND(&list, &item);
  26  *
  27  * Doubly linked lists are similar:
  28  *
  29  *     struct item {
  30  *             struct item *next;
  31  *             struct item *prev;
  32  *     };
  33  *
  34  *     struct list {
  35  *             struct item *head;
  36  *             struct item *tail;
  37  *     };
  38  *
  39  *     struct list list;
  40  *     LIST_INIT(&list);
  41  *
  42  *     struct item item;
  43  *     LIST_ITEM_INIT(&item);
  44  *     LIST_APPEND(&list, &item);
  45  *
  46  * Items can be on multiple lists at once:
  47  *
  48  *     struct item {
  49  *             struct {
  50  *                     struct item *next;
  51  *             } chain;
  52  *
  53  *             struct {
  54  *                     struct item *next;
  55  *                     struct item *prev;
  56  *             } lru;
  57  *     };
  58  *
  59  *     struct items {
  60  *             struct {
  61  *                     struct item *head;
  62  *                     struct item **tail;
  63  *             } queue;
  64  *
  65  *             struct {
  66  *                     struct item *head;
  67  *                     struct item *tail;
  68  *             } cache;
  69  *     };
  70  *
  71  *     struct items items;
  72  *     SLIST_INIT(&items.queue);
  73  *     LIST_INIT(&items.cache);
  74  *
  75  *     struct item item;
  76  *     SLIST_ITEM_INIT(&item, chain);
  77  *     SLIST_APPEND(&items.queue, &item, chain);
  78  *     LIST_ITEM_INIT(&item, lru);
  79  *     LIST_APPEND(&items.cache, &item, lru);
  80  */
  81
  82 #ifndef BFS_LIST_H
  83 #define BFS_LIST_H
  84
  85 #include "diag.h"
  86 #include <stddef.h>
  87 #include <string.h>
  88
  89 /**
  90  * Initialize a singly-linked list.
  91  *
  92  * @param list
  93  *         The list to initialize.
  94  *
  95  * ---
  96  *
  97  * Like many macros in this file, this macro delegates the bulk of its work to
  98  * some helper macros.  We explicitly parenthesize (list) here so the helpers
  99  * don't have to.
 100  */
 101 #define SLIST_INIT(list) \
 102         SLIST_INIT_((list))
 103
 104 /**
 105  * Helper for SLIST_INIT().
 106  */
 107 #define SLIST_INIT_(list) LIST_VOID_( \
 108         list->head = NULL, \
 109         list->tail = &list->head)
 110
 111 /**
 112  * Cast a list of expressions to void.
 113  */
 114 #define LIST_VOID_(...) ((void)(__VA_ARGS__))
 115
 116 /**
 117  * Initialize a singly-linked list item.
 118  *
 119  * @param item
 120  *         The item to initialize.
 121  * @param node (optional)
 122  *         If specified, use item->node.next rather than item->next.
 123  *
 124  * ---
 125  *
 126  * We play some tricks with variadic macros to handle the optional parameter:
 127  *
 128  *     SLIST_ITEM_INIT(item)       => item->next = NULL
 129  *     SLIST_ITEM_INIT(item, node) => item->node.next = NULL
 130  *
 131  * The first trick is that
 132  *
 133  *     #define SLIST_ITEM_INIT(item, ...)
 134  *
 135  * won't work because both commas are required (until C23; see N3033). As a
 136  * workaround, we dispatch to another macro and add a trailing comma.
 137  *
 138  *     SLIST_ITEM_INIT(item)       => SLIST_ITEM_INIT_(item, )
 139  *     SLIST_ITEM_INIT(item, node) => SLIST_ITEM_INIT_(item, node, )
 140  */
 141 #define SLIST_ITEM_INIT(...) \
 142         SLIST_ITEM_INIT_(__VA_ARGS__, )
 143
 144 /**
 145  * Now we need a way to generate either ->next or ->node.next depending on
 146  * whether the node parameter was passed.  The approach is based on
 147  *
 148  *     #define FOO(...) BAR(__VA_ARGS__, 1, 2, )
 149  *     #define BAR(x, y, z, ...) z
 150  *
 151  *     FOO(a)    => 2
 152  *     FOO(a, b) => 1
 153  *
 154  * The LIST_NEXT_() macro uses this technique:
 155  *
 156  *     LIST_NEXT_()       => LIST_NODE_(next, )
 157  *     LIST_NEXT_(node, ) => LIST_NODE_(next, node, )
 158  */
 159 #define LIST_NEXT_(...) \
 160         LIST_NODE_(next, __VA_ARGS__)
 161
 162 /**
 163  * LIST_NODE_() dispatches to yet another macro:
 164  *
 165  *     LIST_NODE_(next, )       => LIST_NODE__(next,     , . ,   , )
 166  *     LIST_NODE_(next, node, ) => LIST_NODE__(next, node,   , . , , )
 167  */
 168 #define LIST_NODE_(dir, ...) \
 169         LIST_NODE__(dir, __VA_ARGS__, . , , )
 170
 171 /**
 172  * And finally, LIST_NODE__() adds the node and the dot if necessary.
 173  *
 174  *                 dir   node ignored dot
 175  *                  v     v      v     v
 176  *     LIST_NODE__(next,     ,   .   ,   , )   => next
 177  *     LIST_NODE__(next, node,       , . , , ) => node . next
 178  *                  ^     ^      ^     ^
 179  *                 dir   node ignored dot
 180  */
 181 #define LIST_NODE__(dir, node, ignored, dot, ...) \
 182         node dot dir
 183
 184 /**
 185  * SLIST_ITEM_INIT_() uses LIST_NEXT_() to generate the right name for the list
 186  * node, and finally delegates to the actual implementation.
 187  */
 188 #define SLIST_ITEM_INIT_(item, ...) \
 189         SLIST_ITEM_INIT__((item), LIST_NEXT_(__VA_ARGS__))
 190
 191 #define SLIST_ITEM_INIT__(item, next) \
 192         LIST_VOID_(item->next = NULL)
 193
 194 /**
 195  * Type-checking macro for singly-linked lists.
 196  */
 197 #define SLIST_CHECK_(list) \
 198         (void)sizeof(list->tail - &list->head)
 199
 200 /**
 201  * Check if a singly-linked list is empty.
 202  */
 203 #define SLIST_EMPTY(list) \
 204         SLIST_EMPTY_((list))
 205
 206 #define SLIST_EMPTY_(list) \
 207         (SLIST_CHECK_(list), !list->head)
 208
 209 /**
 210  * Check if an item is attached to a singly-linked list.
 211  *
 212  * @param list
 213  *         The list to check.
 214  * @param item
 215  *         The item to check.
 216  * @param node (optional)
 217  *         If specified, use item->node.next rather than item->next.
 218  * @return
 219  *         Whether the item is attached to the list.
 220  */
 221 #define SLIST_ATTACHED(list, ...) \
 222         SLIST_ATTACHED_(list, __VA_ARGS__, )
 223
 224 #define SLIST_ATTACHED_(list, item, ...) \
 225         SLIST_ATTACHED__((list), (item), LIST_NEXT_(__VA_ARGS__))
 226
 227 #define SLIST_ATTACHED__(list, item, next) \
 228         (item->next || list->tail == &item->next)
 229
 230 /**
 231  * Insert an item into a singly-linked list.
 232  *
 233  * @param list
 234  *         The list to modify.
 235  * @param cursor
 236  *         A pointer to the item to insert after, e.g. &list->head or list->tail.
 237  * @param item
 238  *         The item to insert.
 239  * @param node (optional)
 240  *         If specified, use item->node.next rather than item->next.
 241  */
 242 #define SLIST_INSERT(list, cursor, ...) \
 243         SLIST_INSERT_(list, cursor, __VA_ARGS__, )
 244
 245 #define SLIST_INSERT_(list, cursor, item, ...) \
 246         SLIST_INSERT__((list), (cursor), (item), LIST_NEXT_(__VA_ARGS__))
 247
 248 #define SLIST_INSERT__(list, cursor, item, next) LIST_VOID_( \
 249         bfs_assert(!SLIST_ATTACHED__(list, item, next)), \
 250         item->next = *cursor, \
 251         *cursor = item, \
 252         list->tail = item->next ? list->tail : &item->next)
 253
 254 /**
 255  * Add an item to the tail of a singly-linked list.
 256  *
 257  * @param list
 258  *         The list to modify.
 259  * @param item
 260  *         The item to append.
 261  * @param node (optional)
 262  *         If specified, use item->node.next rather than item->next.
 263  */
 264 #define SLIST_APPEND(list, ...) \
 265         SLIST_APPEND_(list, __VA_ARGS__, )
 266
 267 #define SLIST_APPEND_(list, item, ...) \
 268         SLIST_INSERT_(list, (list)->tail, item, __VA_ARGS__)
 269
 270 /**
 271  * Add an item to the head of a singly-linked list.
 272  *
 273  * @param list
 274  *         The list to modify.
 275  * @param item
 276  *         The item to prepend.
 277  * @param node (optional)
 278  *         If specified, use item->node.next rather than item->next.
 279  */
 280 #define SLIST_PREPEND(list, ...) \
 281         SLIST_PREPEND_(list, __VA_ARGS__, )
 282
 283 #define SLIST_PREPEND_(list, item, ...) \
 284         SLIST_INSERT_(list, &(list)->head, item, __VA_ARGS__)
 285
 286 /**
 287  * Add an entire singly-linked list to the tail of another.
 288  *
 289  * @param dest
 290  *         The destination list.
 291  * @param src
 292  *         The source list.
 293  */
 294 #define SLIST_EXTEND(dest, src) \
 295         SLIST_EXTEND_((dest), (src))
 296
 297 #define SLIST_EXTEND_(dest, src) \
 298         (src->head ? (*dest->tail = src->head, dest->tail = src->tail, SLIST_INIT(src)) : (void)0)
 299
 300 /**
 301  * Remove an item from a singly-linked list.
 302  *
 303  * @param list
 304  *         The list to modify.
 305  * @param cursor
 306  *         A pointer to the item to remove, either &list->head or &prev->next.
 307  * @param node (optional)
 308  *         If specified, use item->node.next rather than item->next.
 309  * @return
 310  *         The removed item.
 311  */
 312 #define SLIST_REMOVE(list, ...) \
 313         SLIST_REMOVE_(list, __VA_ARGS__, )
 314
 315 #define SLIST_REMOVE_(list, cursor, ...) \
 316         SLIST_REMOVE__((list), (cursor), LIST_NEXT_(__VA_ARGS__))
 317
 318 #define SLIST_REMOVE__(list, cursor, next) \
 319         (list->tail = (*cursor)->next ? list->tail : cursor, \
 320          slist_remove_impl(*cursor, cursor, &(*cursor)->next, list->tail, sizeof(*cursor)))
 321
 322 // Helper for SLIST_REMOVE()
 323 static inline void *slist_remove_impl(void *ret, void *cursor, void *next, void *tail, size_t size) {
 324         // ret = *cursor;
 325         // *cursor = ret->next;
 326         memcpy(cursor, next, size);
 327         // ret->next = *list->tail; (NULL)
 328         memcpy(next, tail, size);
 329         return ret;
 330 }
 331
 332 /**
 333  * Pop the head off a singly-linked list.
 334  *
 335  * @param list
 336  *         The list to modify.
 337  * @param node (optional)
 338  *         If specified, use head->node.next rather than head->next.
 339  * @return
 340  *         The popped item, or NULL if the list was empty.
 341  */
 342 #define SLIST_POP(...) \
 343         SLIST_POP_(__VA_ARGS__, )
 344
 345 #define SLIST_POP_(list, ...) \
 346         SLIST_POP__((list), __VA_ARGS__)
 347
 348 #define SLIST_POP__(list, ...) \
 349         (list->head ? SLIST_REMOVE_(list, &list->head, __VA_ARGS__) : NULL)
 350
 351 /**
 352  * Loop over the items in a singly-linked list.
 353  *
 354  * @param type
 355  *         The list item type.
 356  * @param item
 357  *         The induction variable name.
 358  * @param list
 359  *         The list to iterate.
 360  * @param node (optional)
 361  *         If specified, use head->node.next rather than head->next.
 362  */
 363 #define for_slist(type, item, ...) \
 364         for_slist_(type, item, __VA_ARGS__, )
 365
 366 #define for_slist_(type, item, list, ...) \
 367         for_slist__(type, item, (list), LIST_NEXT_(__VA_ARGS__))
 368
 369 #define for_slist__(type, item, list, next) \
 370         for (type *item = list->head, *_next; \
 371              item && (SLIST_CHECK_(list), _next = item->next, true); \
 372              item = _next)
 373
 374 /**
 375  * Initialize a doubly-linked list.
 376  *
 377  * @param list
 378  *         The list to initialize.
 379  */
 380 #define LIST_INIT(list) \
 381         LIST_INIT_((list))
 382
 383 #define LIST_INIT_(list) \
 384         LIST_VOID_(list->head = list->tail = NULL)
 385
 386 /**
 387  * LIST_PREV_()       => prev
 388  * LIST_PREV_(node, ) => node.prev
 389  */
 390 #define LIST_PREV_(...) \
 391         LIST_NODE_(prev, __VA_ARGS__)
 392
 393 /**
 394  * Initialize a doubly-linked list item.
 395  *
 396  * @param item
 397  *         The item to initialize.
 398  * @param node (optional)
 399  *         If specified, use item->node.next rather than item->next.
 400  */
 401 #define LIST_ITEM_INIT(...) \
 402         LIST_ITEM_INIT_(__VA_ARGS__, )
 403
 404 #define LIST_ITEM_INIT_(item, ...) \
 405         LIST_ITEM_INIT__((item), LIST_PREV_(__VA_ARGS__), LIST_NEXT_(__VA_ARGS__))
 406
 407 #define LIST_ITEM_INIT__(item, prev, next) \
 408         LIST_VOID_(item->prev = item->next = NULL)
 409
 410 /**
 411  * Type-checking macro for doubly-linked lists.
 412  */
 413 #define LIST_CHECK_(list) \
 414         (void)sizeof(list->tail - list->head)
 415
 416 /**
 417  * Check if a doubly-linked list is empty.
 418  */
 419 #define LIST_EMPTY(list) \
 420         LIST_EMPTY_((list))
 421
 422 #define LIST_EMPTY_(list) \
 423         (LIST_CHECK_(list), !list->head)
 424
 425 /**
 426  * Add an item to the tail of a doubly-linked list.
 427  *
 428  * @param list
 429  *         The list to modify.
 430  * @param item
 431  *         The item to append.
 432  * @param node (optional)
 433  *         If specified, use item->node.{prev,next} rather than item->{prev,next}.
 434  */
 435 #define LIST_APPEND(list, ...) \
 436         LIST_INSERT(list, (list)->tail, __VA_ARGS__)
 437
 438 /**
 439  * Add an item to the head of a doubly-linked list.
 440  *
 441  * @param list
 442  *         The list to modify.
 443  * @param item
 444  *         The item to prepend.
 445  * @param node (optional)
 446  *         If specified, use item->node.{prev,next} rather than item->{prev,next}.
 447  */
 448 #define LIST_PREPEND(list, ...) \
 449         LIST_INSERT(list, NULL, __VA_ARGS__)
 450
 451 /**
 452  * Check if an item is attached to a doubly-linked list.
 453  *
 454  * @param list
 455  *         The list to check.
 456  * @param item
 457  *         The item to check.
 458  * @param node (optional)
 459  *         If specified, use item->node.{prev,next} rather than item->{prev,next}.
 460  * @return
 461  *         Whether the item is attached to the list.
 462  */
 463 #define LIST_ATTACHED(list, ...) \
 464         LIST_ATTACHED_(list, __VA_ARGS__, )
 465
 466 #define LIST_ATTACHED_(list, item, ...) \
 467         LIST_ATTACHED__((list), (item), LIST_PREV_(__VA_ARGS__), LIST_NEXT_(__VA_ARGS__))
 468
 469 #define LIST_ATTACHED__(list, item, prev, next) \
 470         (item->prev || item->next || list->head == item || list->tail == item)
 471
 472 /**
 473  * Insert into a doubly-linked list after the given cursor.
 474  *
 475  * @param list
 476  *         The list to modify.
 477  * @param cursor
 478  *         Insert after this element.
 479  * @param item
 480  *         The item to insert.
 481  * @param node (optional)
 482  *         If specified, use item->node.{prev,next} rather than item->{prev,next}.
 483  */
 484 #define LIST_INSERT(list, cursor, ...) \
 485         LIST_INSERT_(list, cursor, __VA_ARGS__, )
 486
 487 #define LIST_INSERT_(list, cursor, item, ...) \
 488         LIST_INSERT__((list), (cursor), (item), LIST_PREV_(__VA_ARGS__), LIST_NEXT_(__VA_ARGS__))
 489
 490 #define LIST_INSERT__(list, cursor, item, prev, next) LIST_VOID_( \
 491         bfs_assert(!LIST_ATTACHED__(list, item, prev, next)), \
 492         item->prev = cursor, \
 493         item->next = cursor ? cursor->next : list->head, \
 494         *(item->prev ? &item->prev->next : &list->head) = item, \
 495         *(item->next ? &item->next->prev : &list->tail) = item)
 496
 497 /**
 498  * Remove an item from a doubly-linked list.
 499  *
 500  * @param list
 501  *         The list to modify.
 502  * @param item
 503  *         The item to remove.
 504  * @param node (optional)
 505  *         If specified, use item->node.{prev,next} rather than item->{prev,next}.
 506  */
 507 #define LIST_REMOVE(list, ...) \
 508         LIST_REMOVE_(list, __VA_ARGS__, )
 509
 510 #define LIST_REMOVE_(list, item, ...) \
 511         LIST_REMOVE__((list), (item), LIST_PREV_(__VA_ARGS__), LIST_NEXT_(__VA_ARGS__))
 512
 513 #define LIST_REMOVE__(list, item, prev, next) LIST_VOID_( \
 514         *(item->prev ? &item->prev->next : &list->head) = item->next, \
 515         *(item->next ? &item->next->prev : &list->tail) = item->prev, \
 516         item->prev = item->next = NULL)
 517
 518 /**
 519  * Loop over the items in a doubly-linked list.
 520  *
 521  * @param type
 522  *         The list item type.
 523  * @param item
 524  *         The induction variable name.
 525  * @param list
 526  *         The list to iterate.
 527  * @param node (optional)
 528  *         If specified, use head->node.next rather than head->next.
 529  */
 530 #define for_list(type, item, ...) \
 531         for_list_(type, item, __VA_ARGS__, )
 532
 533 #define for_list_(type, item, list, ...) \
 534         for_list__(type, item, (list), LIST_NEXT_(__VA_ARGS__))
 535
 536 #define for_list__(type, item, list, next) \
 537         for (type *item = list->head, *_next; \
 538              item && (LIST_CHECK_(list), _next = item->next, true); \
 539              item = _next)
 540
 541 #endif // BFS_LIST_H