aboutsummaryrefslogtreecommitdiff
path: root/list
diff options
context:
space:
mode:
author3gg <3gg@shellblade.net>2023-06-12 08:52:15 -0700
committer3gg <3gg@shellblade.net>2023-06-12 08:52:15 -0700
commitbfabb435e5c5bf313005c4636747fce59eb4ca6f (patch)
treea32248966dd2cfa851a1bc731c3b240ebfaf9110 /list
parent0c1eb2535676a6fb2e1def08f9681b2a8b49f6e4 (diff)
Add list library.
Diffstat (limited to 'list')
-rw-r--r--list/CMakeLists.txt7
-rw-r--r--list/include/list.h118
-rw-r--r--list/src/list.c14
-rw-r--r--list/test/list_test.c76
4 files changed, 166 insertions, 49 deletions
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)
4 4
5# Library 5# Library
6 6
7add_library(list 7add_library(list INTERFACE)
8 src/list.c)
9 8
10target_include_directories(list PUBLIC 9target_include_directories(list INTERFACE
11 include) 10 include)
12 11
13target_compile_options(list PRIVATE -Wall -Wextra)
14
15# Test 12# Test
16 13
17add_executable(list_test 14add_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 @@
1/// A doubly linked list. 1/// Doubly-linked list.
2///
3/// This list does not hold user data. Instead, the list can be used as an
4/// intrusive list or as part as a more complex data structure.
5#pragma once 2#pragma once
6 3
4#include <assert.h>
7#include <stddef.h> 5#include <stddef.h>
6#include <stdlib.h>
7
8#define DEF_LIST(type) \
9 typedef struct type##_node { \
10 type val; \
11 struct type##_node* prev; \
12 struct type##_node* next; \
13 } type##_node; \
14 typedef struct type##_list { \
15 type##_node* head; \
16 } type##_list;
17
18static inline void* alloc(size_t size) {
19 void* ptr = calloc(1, size);
20 assert(ptr);
21 return ptr;
22}
23
24/// Create a new empty list.
25#define make_list(type) \
26 (type##_list) { 0 }
27
28/// Delete the list.
29#define del_list(list) \
30 for (__typeof__(list.head) node = list.head; node;) { \
31 __typeof__(node) cur = node; \
32 node = node->next; \
33 free(cur); \
34 } \
35 list.head = 0;
8 36
9typedef struct list list; 37/// Prepend a value to the list.
38#define list_push(list, value) \
39 { \
40 __typeof__(list.head) node = alloc(sizeof(*list.head)); \
41 node->val = value; \
42 node->next = list.head; \
43 if (list.head) { \
44 list.head->prev = node; \
45 } \
46 list.head = node; \
47 }
10 48
11typedef struct list { 49/// Delete the first occurrence of the value from the list.
12 list* prev; 50#define list_remove(list, search_value) \
13 list* next; 51 for (__typeof__(list.head) iter = list.head; iter; iter = iter->next) { \
14} list; 52 if (iter->val == (search_value)) { \
53 del_node(list, iter); \
54 break; \
55 } \
56 }
15 57
16/// Create a new list from an array of `size` items. 58/// Delete the node that contains the value at the given address from the
17void list_make(list* list, size_t size); 59/// list.
60#define list_remove_ptr(list, value_ptr) \
61 for (__typeof__(list.head) iter = list.head; iter; iter = iter->next) { \
62 if (&iter->val == value_ptr) { \
63 del_node(list, iter); \
64 break; \
65 } \
66 }
18 67
19/// Iterates over all the items in the list. 68/// Delete the list node.
20#define list_foreach(LIST, iter) \ 69#define del_node(list, node) \
21 for (struct list* iter = LIST; iter; iter = iter->next) 70 { \
71 assert(node); \
72 if (node->prev) { \
73 node->prev->next = node->next; \
74 } \
75 if (node->next) { \
76 node->next->prev = node->prev; \
77 } \
78 if (list.head == node) { \
79 list.head = 0; \
80 } \
81 free(node); \
82 node = 0; \
83 }
84
85/// Iterate over all the items in the list.
86///
87/// Use 'value' to refer to the address of the current node's value during
88/// iteration.
89#define list_foreach(list, body) \
90 { \
91 __typeof__(list.head) node = list.head; \
92 while (node) { \
93 const __typeof__(node->val)* value = &node->val; \
94 body; \
95 node = node->next; \
96 } \
97 }
98
99/// Iterate over all the items in the list.
100///
101/// Use 'value' to refer to the address of the current node's value during
102/// iteration.
103#define list_foreach_mut(list, body) \
104 { \
105 __typeof__(list.head) node = list.head; \
106 while (node) { \
107 __typeof__(node->val)* value = &node->val; \
108 body; \
109 node = node->next; \
110 } \
111 }
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 @@
1#include "list.h"
2
3#include <assert.h>
4
5void list_make(list* list, size_t size) {
6 if (size == 0) {
7 return;
8 }
9 assert(list);
10 for (size_t i = 0; i < size; ++i) {
11 list[i].prev = (i == 0 ? 0 : &list[i - 1]);
12 list[i].next = (i == size - 1 ? 0 : &list[i + 1]);
13 }
14}
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 @@
4 4
5#define TEST_LIST_SIZE 10 5#define TEST_LIST_SIZE 10
6 6
7// Create an empty list. 7DEF_LIST(int);
8TEST_CASE(list_create_empty) { list_make(0, 0); }
9
10// Create a list of a given size.
11TEST_CASE(list_create) {
12 struct list list[TEST_LIST_SIZE];
13 list_make(list, TEST_LIST_SIZE);
14}
15 8
16// Iterate over a list. 9// Iterate over a list.
17TEST_CASE(list_traverse) { 10TEST_CASE(list_traverse) {
18 int numbers[TEST_LIST_SIZE] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; 11 int_list list = make_list(int);
19 12 for (int i = 0; i < TEST_LIST_SIZE; ++i) {
20 struct list list[TEST_LIST_SIZE]; 13 list_push(list, i + 1);
21 list_make(list, TEST_LIST_SIZE); 14 }
22 15
23 int count = 0; 16 int count = 0;
24 int sum = 0; 17 int sum = 0;
25 list_foreach(list, item) { 18 list_foreach(list, {
26 count++; 19 count++;
27 sum += numbers[item - list]; 20 sum += *value;
28 } 21 });
29 22
30 TEST_EQUAL(count, TEST_LIST_SIZE); 23 TEST_EQUAL(count, TEST_LIST_SIZE);
31 TEST_EQUAL(sum, TEST_LIST_SIZE * (TEST_LIST_SIZE + 1) / 2); 24 TEST_EQUAL(sum, TEST_LIST_SIZE * (TEST_LIST_SIZE + 1) / 2);
25
26 del_list(list);
27}
28
29// Delete by value.
30TEST_CASE(list_remove_by_value) {
31 int_list list = make_list(int);
32 for (int i = 0; i < TEST_LIST_SIZE; ++i) {
33 list_push(list, i + 1);
34 }
35
36 list_remove(list, 5);
37
38 int count = 0;
39 int sum = 0;
40 list_foreach(list, {
41 count++;
42 sum += *value;
43 });
44
45 TEST_EQUAL(count, TEST_LIST_SIZE - 1);
46 TEST_EQUAL(sum, (TEST_LIST_SIZE * (TEST_LIST_SIZE + 1) / 2) - 5);
47
48 del_list(list);
49}
50
51// Delete by address.
52TEST_CASE(list_remove_by_address) {
53 const int N = 3;
54
55 int* ptrs[3] = {0};
56
57 int_list list = make_list(int);
58 for (int i = 0; i < N; ++i) {
59 list_push(list, i + 1);
60 ptrs[i] = &list.head->val;
61 }
62
63 list_remove_ptr(list, ptrs[1]); // Value 2.
64
65 int count = 0;
66 int sum = 0;
67 list_foreach(list, {
68 count++;
69 sum += *value;
70 });
71
72 TEST_EQUAL(count, 2);
73 TEST_EQUAL(sum, 1 + 3);
74
75 del_list(list);
32} 76}
33 77
34int main() { return 0; } 78int main() { return 0; }