From 782e4282841fae59d60b16ddfc00bb45cf40771e Mon Sep 17 00:00:00 2001 From: wm4 Date: Fri, 18 May 2018 20:30:56 +0200 Subject: misc: add linked list helpers This provides macros for managing intrusive doubly linked lists. There are many ways how to do those in a "generic" way in C. For example Solaris style lists are pretty nice: https://github.com/illumos/illumos-gate/blob/master/usr/src/uts/common/sys/list.h https://github.com/illumos/illumos-gate/blob/master/usr/src/common/list/list.c I even have an independent implementation of this, which could be ISC licensed. But I think it's easier to vomit ~100 lines of preprocessor garbage, which has a lower footprint, and I think it wins slightly on the side of type safety, simplicity, and ease of use, even if it doesn't look as magically nice. --- misc/linked_list.h | 107 +++++++++++++++++++++++++++++++++++ test/linked_list.c | 162 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 269 insertions(+) create mode 100644 misc/linked_list.h create mode 100644 test/linked_list.c diff --git a/misc/linked_list.h b/misc/linked_list.h new file mode 100644 index 0000000000..b43b227d90 --- /dev/null +++ b/misc/linked_list.h @@ -0,0 +1,107 @@ +#pragma once + +#include + +/* + * Doubly linked list macros. All of these require that each list item is a + * struct, that contains a field, that is another struct with prev/next fields: + * + * struct example_item { + * struct { + * struct example_item *prev, *next; + * } mylist; + * }; + * + * And a struct somewhere that represents the "list" and has head/tail fields: + * + * struct { + * struct example_item *head, *tail; + * } mylist_var; + * + * Then you can e.g. insert elements like this: + * + * struct example_item item; + * LL_APPEND(mylist, &mylist_var, &item); + * + * The first macro argument is always the name if the field in the item that + * contains the prev/next pointers, in this case struct example_item.mylist. + * This was done so that a single item can be in multiple lists. + * + * The list is started/terminated with NULL. Nothing ever points _to_ the + * list head, so the list head memory location can be safely moved. + * + * General rules are: + * - list head is initialized by setting head/tail to NULL + * - list items do not need to be initialized before inserting them + * - next/prev fields of list items are not cleared when they are removed + * - there's no way to know whether an item is in the list or not (unless + * you clear prev/next on init/removal, _and_ check whether items with + * prev/next==NULL are referenced by head/tail) + */ + +// Insert item at the end of the list (list->tail == item). +// Undefined behavior if item is already in the list. +#define LL_APPEND(field, list, item) do { \ + (item)->field.prev = (list)->tail; \ + (item)->field.next = NULL; \ + LL_RELINK_(field, list, item) \ +} while (0) + +// Insert item enew after eprev (i.e. eprev->next == enew). If eprev is NULL, +// then insert it as head (list->head == enew). +// Undefined behavior if enew is already in the list, or eprev isn't. +#define LL_INSERT_AFTER(field, list, eprev, enew) do { \ + (enew)->field.prev = (eprev); \ + (enew)->field.next = (eprev) ? (eprev)->field.next : (list)->head; \ + LL_RELINK_(field, list, enew) \ +} while (0) + +// Insert item at the start of the list (list->head == item). +// Undefined behavior if item is already in the list. +#define LL_PREPEND(field, list, item) do { \ + (item)->field.prev = NULL; \ + (item)->field.next = (list)->head; \ + LL_RELINK_(field, list, item) \ +} while (0) + +// Insert item enew before enext (i.e. enew->next == enext). If enext is NULL, +// then insert it as tail (list->tail == enew). +// Undefined behavior if enew is already in the list, or enext isn't. +#define LL_INSERT_BEFORE(field, list, enext, enew) do { \ + (enew)->field.prev = (enext) ? (enext)->field.prev : (list)->tail; \ + (enew)->field.next = (enext); \ + LL_RELINK_(field, list, enew) \ +} while (0) + +// Remove the item from the list. +// Undefined behavior if item is not in the list. +#define LL_REMOVE(field, list, item) do { \ + if ((item)->field.prev) { \ + (item)->field.prev->field.next = (item)->field.next; \ + } else { \ + (list)->head = (item)->field.next; \ + } \ + if ((item)->field.next) { \ + (item)->field.next->field.prev = (item)->field.prev; \ + } else { \ + (list)->tail = (item)->field.prev; \ + } \ +} while (0) + +// Remove all items from the list. +#define LL_CLEAR(field, list) do { \ + (list)->head = (list)->tail = NULL; \ +} while (0) + +// Internal helper. +#define LL_RELINK_(field, list, item) \ + if ((item)->field.prev) { \ + (item)->field.prev->field.next = (item); \ + } else { \ + (list)->head = (item); \ + } \ + if ((item)->field.next) { \ + (item)->field.next->field.prev = (item); \ + } else { \ + (list)->tail = (item); \ + } diff --git a/test/linked_list.c b/test/linked_list.c new file mode 100644 index 0000000000..6ad61f36ec --- /dev/null +++ b/test/linked_list.c @@ -0,0 +1,162 @@ +#include "test_helpers.h" + +#include "common/common.h" +#include "misc/linked_list.h" + +struct list_item { + int v; + struct { + struct list_item *prev, *next; + } list_node; +}; + +struct the_list { + struct list_item *head, *tail; +}; + +static bool do_check_list(struct the_list *lst, int *c, int num_c) +{ + if (!lst->head) + assert_true(!lst->tail); + if (!lst->tail) + assert_true(!lst->head); + + for (struct list_item *cur = lst->head; cur; cur = cur->list_node.next) { + if (cur->list_node.prev) { + assert_true(cur->list_node.prev->list_node.next == cur); + assert_true(lst->head != cur); + } else { + assert_true(lst->head == cur); + } + if (cur->list_node.next) { + assert_true(cur->list_node.next->list_node.prev == cur); + assert_true(lst->tail != cur); + } else { + assert_true(lst->tail == cur); + } + + if (num_c < 1) + return false; + if (c[0] != cur->v) + return false; + + num_c--; + c++; + } + + if (num_c) + return false; + + return true; +} + +static void test_linked_list(void **state) +{ + struct the_list lst = {0}; + struct list_item e1 = {1}; + struct list_item e2 = {2}; + struct list_item e3 = {3}; + struct list_item e4 = {4}; + struct list_item e5 = {5}; + struct list_item e6 = {6}; + +#define check_list(...) \ + assert_true(do_check_list(&lst, (int[]){__VA_ARGS__}, \ + sizeof((int[]){__VA_ARGS__}) / sizeof(int))); +#define check_list_empty() \ + assert_true(do_check_list(&lst, NULL, 0)); + + check_list_empty(); + LL_APPEND(list_node, &lst, &e1); + + check_list(1); + LL_APPEND(list_node, &lst, &e2); + + check_list(1, 2); + LL_APPEND(list_node, &lst, &e4); + + check_list(1, 2, 4); + LL_CLEAR(list_node, &lst); + + check_list_empty(); + LL_PREPEND(list_node, &lst, &e4); + + check_list(4); + LL_PREPEND(list_node, &lst, &e2); + + check_list(2, 4); + LL_PREPEND(list_node, &lst, &e1); + + check_list(1, 2, 4); + LL_CLEAR(list_node, &lst); + + check_list_empty(); + LL_INSERT_BEFORE(list_node, &lst, (struct list_item *)NULL, &e6); + + check_list(6); + LL_INSERT_BEFORE(list_node, &lst, (struct list_item *)NULL, &e1); + + check_list(6, 1); + LL_INSERT_BEFORE(list_node, &lst, (struct list_item *)NULL, &e2); + + check_list(6, 1, 2); + LL_INSERT_BEFORE(list_node, &lst, &e6, &e3); + + check_list(3, 6, 1, 2); + LL_INSERT_BEFORE(list_node, &lst, &e6, &e5); + + check_list(3, 5, 6, 1, 2); + LL_INSERT_BEFORE(list_node, &lst, &e2, &e4); + + check_list(3, 5, 6, 1, 4, 2); + LL_REMOVE(list_node, &lst, &e6); + + check_list(3, 5, 1, 4, 2); + LL_REMOVE(list_node, &lst, &e3); + + check_list(5, 1, 4, 2); + LL_REMOVE(list_node, &lst, &e2); + + check_list(5, 1, 4); + LL_REMOVE(list_node, &lst, &e4); + + check_list(5, 1); + LL_REMOVE(list_node, &lst, &e5); + + check_list(1); + LL_REMOVE(list_node, &lst, &e1); + + check_list_empty(); + LL_APPEND(list_node, &lst, &e2); + + check_list(2); + LL_REMOVE(list_node, &lst, &e2); + + check_list_empty(); + LL_INSERT_AFTER(list_node, &lst, (struct list_item *)NULL, &e1); + + check_list(1); + LL_INSERT_AFTER(list_node, &lst, (struct list_item *)NULL, &e2); + + check_list(2, 1); + LL_INSERT_AFTER(list_node, &lst, (struct list_item *)NULL, &e3); + + check_list(3, 2, 1); + LL_INSERT_AFTER(list_node, &lst, &e3, &e4); + + check_list(3, 4, 2, 1); + LL_INSERT_AFTER(list_node, &lst, &e4, &e5); + + check_list(3, 4, 5, 2, 1); + LL_INSERT_AFTER(list_node, &lst, &e1, &e6); + + check_list(3, 4, 5, 2, 1, 6); +} + +int main(void) { + const struct CMUnitTest tests[] = { + cmocka_unit_test(test_linked_list), + }; + return cmocka_run_group_tests(tests, NULL, NULL); +} + -- cgit v1.2.3