From bfabb435e5c5bf313005c4636747fce59eb4ca6f Mon Sep 17 00:00:00 2001 From: 3gg <3gg@shellblade.net> Date: Mon, 12 Jun 2023 08:52:15 -0700 Subject: Add list library. --- list/CMakeLists.txt | 7 +-- list/include/list.h | 118 ++++++++++++++++++++++++++++++++++++++++++++------ list/src/list.c | 14 ------ list/test/list_test.c | 76 +++++++++++++++++++++++++------- 4 files changed, 166 insertions(+), 49 deletions(-) delete mode 100644 list/src/list.c diff --git a/list/CMakeLists.txt b/list/CMakeLists.txt index 8caeabc..6e76ec6 100644 --- a/list/CMakeLists.txt +++ b/list/CMakeLists.txt @@ -4,14 +4,11 @@ project(list) # Library -add_library(list - src/list.c) +add_library(list INTERFACE) -target_include_directories(list PUBLIC +target_include_directories(list INTERFACE include) -target_compile_options(list PRIVATE -Wall -Wextra) - # Test add_executable(list_test diff --git a/list/include/list.h b/list/include/list.h index 945de28..facf820 100644 --- a/list/include/list.h +++ b/list/include/list.h @@ -1,21 +1,111 @@ -/// A doubly linked list. -/// -/// This list does not hold user data. Instead, the list can be used as an -/// intrusive list or as part as a more complex data structure. +/// Doubly-linked list. #pragma once +#include #include +#include + +#define DEF_LIST(type) \ + typedef struct type##_node { \ + type val; \ + struct type##_node* prev; \ + struct type##_node* next; \ + } type##_node; \ + typedef struct type##_list { \ + type##_node* head; \ + } type##_list; + +static inline void* alloc(size_t size) { + void* ptr = calloc(1, size); + assert(ptr); + return ptr; +} + +/// Create a new empty list. +#define make_list(type) \ + (type##_list) { 0 } + +/// Delete the list. +#define del_list(list) \ + for (__typeof__(list.head) node = list.head; node;) { \ + __typeof__(node) cur = node; \ + node = node->next; \ + free(cur); \ + } \ + list.head = 0; -typedef struct list list; +/// Prepend a value to the list. +#define list_push(list, value) \ + { \ + __typeof__(list.head) node = alloc(sizeof(*list.head)); \ + node->val = value; \ + node->next = list.head; \ + if (list.head) { \ + list.head->prev = node; \ + } \ + list.head = node; \ + } -typedef struct list { - list* prev; - list* next; -} list; +/// Delete the first occurrence of the value from the list. +#define list_remove(list, search_value) \ + for (__typeof__(list.head) iter = list.head; iter; iter = iter->next) { \ + if (iter->val == (search_value)) { \ + del_node(list, iter); \ + break; \ + } \ + } -/// Create a new list from an array of `size` items. -void list_make(list* list, size_t size); +/// Delete the node that contains the value at the given address from the +/// list. +#define list_remove_ptr(list, value_ptr) \ + for (__typeof__(list.head) iter = list.head; iter; iter = iter->next) { \ + if (&iter->val == value_ptr) { \ + del_node(list, iter); \ + break; \ + } \ + } -/// Iterates over all the items in the list. -#define list_foreach(LIST, iter) \ - for (struct list* iter = LIST; iter; iter = iter->next) +/// Delete the list node. +#define del_node(list, node) \ + { \ + assert(node); \ + if (node->prev) { \ + node->prev->next = node->next; \ + } \ + if (node->next) { \ + node->next->prev = node->prev; \ + } \ + if (list.head == node) { \ + list.head = 0; \ + } \ + free(node); \ + node = 0; \ + } + +/// Iterate over all the items in the list. +/// +/// Use 'value' to refer to the address of the current node's value during +/// iteration. +#define list_foreach(list, body) \ + { \ + __typeof__(list.head) node = list.head; \ + while (node) { \ + const __typeof__(node->val)* value = &node->val; \ + body; \ + node = node->next; \ + } \ + } + +/// Iterate over all the items in the list. +/// +/// Use 'value' to refer to the address of the current node's value during +/// iteration. +#define list_foreach_mut(list, body) \ + { \ + __typeof__(list.head) node = list.head; \ + while (node) { \ + __typeof__(node->val)* value = &node->val; \ + body; \ + node = node->next; \ + } \ + } diff --git a/list/src/list.c b/list/src/list.c deleted file mode 100644 index f5b6507..0000000 --- a/list/src/list.c +++ /dev/null @@ -1,14 +0,0 @@ -#include "list.h" - -#include - -void list_make(list* list, size_t size) { - if (size == 0) { - return; - } - assert(list); - for (size_t i = 0; i < size; ++i) { - list[i].prev = (i == 0 ? 0 : &list[i - 1]); - list[i].next = (i == size - 1 ? 0 : &list[i + 1]); - } -} diff --git a/list/test/list_test.c b/list/test/list_test.c index a11c713..9ff10c1 100644 --- a/list/test/list_test.c +++ b/list/test/list_test.c @@ -4,31 +4,75 @@ #define TEST_LIST_SIZE 10 -// Create an empty list. -TEST_CASE(list_create_empty) { list_make(0, 0); } - -// Create a list of a given size. -TEST_CASE(list_create) { - struct list list[TEST_LIST_SIZE]; - list_make(list, TEST_LIST_SIZE); -} +DEF_LIST(int); // Iterate over a list. TEST_CASE(list_traverse) { - int numbers[TEST_LIST_SIZE] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; - - struct list list[TEST_LIST_SIZE]; - list_make(list, TEST_LIST_SIZE); + int_list list = make_list(int); + for (int i = 0; i < TEST_LIST_SIZE; ++i) { + list_push(list, i + 1); + } int count = 0; - int sum = 0; - list_foreach(list, item) { + int sum = 0; + list_foreach(list, { count++; - sum += numbers[item - list]; - } + sum += *value; + }); TEST_EQUAL(count, TEST_LIST_SIZE); TEST_EQUAL(sum, TEST_LIST_SIZE * (TEST_LIST_SIZE + 1) / 2); + + del_list(list); +} + +// Delete by value. +TEST_CASE(list_remove_by_value) { + int_list list = make_list(int); + for (int i = 0; i < TEST_LIST_SIZE; ++i) { + list_push(list, i + 1); + } + + list_remove(list, 5); + + int count = 0; + int sum = 0; + list_foreach(list, { + count++; + sum += *value; + }); + + TEST_EQUAL(count, TEST_LIST_SIZE - 1); + TEST_EQUAL(sum, (TEST_LIST_SIZE * (TEST_LIST_SIZE + 1) / 2) - 5); + + del_list(list); +} + +// Delete by address. +TEST_CASE(list_remove_by_address) { + const int N = 3; + + int* ptrs[3] = {0}; + + int_list list = make_list(int); + for (int i = 0; i < N; ++i) { + list_push(list, i + 1); + ptrs[i] = &list.head->val; + } + + list_remove_ptr(list, ptrs[1]); // Value 2. + + int count = 0; + int sum = 0; + list_foreach(list, { + count++; + sum += *value; + }); + + TEST_EQUAL(count, 2); + TEST_EQUAL(sum, 1 + 3); + + del_list(list); } int main() { return 0; } -- cgit v1.2.3