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 <assert.h>
#include <stddef.h>
+#include <stdlib.h>
+
+#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 <assert.h>
-
-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