aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--CMakeLists.txt5
-rw-r--r--cstring/CMakeLists.txt5
-rw-r--r--cstring/include/cstring.h52
-rw-r--r--cstring/src/cstring.c10
-rw-r--r--error/CMakeLists.txt2
-rw-r--r--filesystem/CMakeLists.txt2
-rw-r--r--filesystem/include/filesystem.h20
-rw-r--r--filesystem/src/filesystem.c65
-rw-r--r--filesystem/src/path.c2
-rw-r--r--hash/CMakeLists.txt14
-rw-r--r--hash/include/fnv1a.h9
-rw-r--r--hash/src/fnv1a.c23
-rw-r--r--list/CMakeLists.txt2
-rw-r--r--list/include/list.h28
-rw-r--r--list/test/list_test.c2
-rw-r--r--log/CMakeLists.txt2
-rw-r--r--mem/CMakeLists.txt4
-rw-r--r--mem/include/mem.h7
-rw-r--r--mem/src/mem.c30
-rw-r--r--mem/test/mem_test.c36
-rw-r--r--mempool/CMakeLists.txt4
-rw-r--r--mempool/README.md23
-rw-r--r--mempool/include/mempool.h11
-rw-r--r--mempool/src/mempool.c24
-rw-r--r--mempool/test/mempool_test.c34
-rw-r--r--memstack/CMakeLists.txt30
-rw-r--r--memstack/README.md15
-rw-r--r--memstack/include/memstack.h66
-rw-r--r--memstack/src/memstack.c119
-rw-r--r--memstack/test/memstack_test.c171
-rw-r--r--memstack/test/test.h185
-rw-r--r--plugin/CMakeLists.txt8
-rw-r--r--plugin/src/plugin.c18
-rw-r--r--random/CMakeLists.txt2
-rw-r--r--simloop/CMakeLists.txt29
-rw-r--r--simloop/README.md99
-rw-r--r--simloop/include/simloop.h40
-rw-r--r--simloop/src/simloop.c78
-rw-r--r--simloop/test/simloop_test.c306
-rw-r--r--test/CMakeLists.txt4
-rw-r--r--timer/CMakeLists.txt4
-rw-r--r--timer/include/timer.h24
-rw-r--r--timer/src/timer.c45
-rw-r--r--timer/test/timer_test.c12
44 files changed, 1490 insertions, 181 deletions
diff --git a/CMakeLists.txt b/CMakeLists.txt
index 04e0e4e..62ee1a8 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -8,10 +8,13 @@ add_subdirectory(cassert)
8add_subdirectory(cstring) 8add_subdirectory(cstring)
9add_subdirectory(error) 9add_subdirectory(error)
10add_subdirectory(filesystem) 10add_subdirectory(filesystem)
11add_subdirectory(hash)
11add_subdirectory(list) 12add_subdirectory(list)
12add_subdirectory(mem)
13add_subdirectory(log) 13add_subdirectory(log)
14add_subdirectory(mem)
14add_subdirectory(mempool) 15add_subdirectory(mempool)
16add_subdirectory(memstack)
15add_subdirectory(plugin) 17add_subdirectory(plugin)
16add_subdirectory(random) 18add_subdirectory(random)
19add_subdirectory(simloop)
17add_subdirectory(timer) 20add_subdirectory(timer)
diff --git a/cstring/CMakeLists.txt b/cstring/CMakeLists.txt
index a1abde2..92fe5a7 100644
--- a/cstring/CMakeLists.txt
+++ b/cstring/CMakeLists.txt
@@ -15,8 +15,3 @@ target_include_directories(cstring PUBLIC
15 15
16target_link_libraries(cstring PUBLIC 16target_link_libraries(cstring PUBLIC
17 cassert) 17 cassert)
18
19if(LINUX)
20 target_link_libraries(cstring PUBLIC
21 -lbsd)
22endif()
diff --git a/cstring/include/cstring.h b/cstring/include/cstring.h
index b07dad6..419b604 100644
--- a/cstring/include/cstring.h
+++ b/cstring/include/cstring.h
@@ -3,14 +3,23 @@
3 3
4#include <cassert.h> 4#include <cassert.h>
5 5
6#ifdef __linux__
7#include <bsd/string.h>
8#else
9#include <string.h>
10#endif
11#include <stdbool.h> 6#include <stdbool.h>
12#include <stdint.h> 7#include <stdint.h>
13#include <stdio.h> 8#include <stdio.h>
9#include <string.h>
10
11// -----------------------------------------------------------------------------
12// C-string helpers.
13
14/// Return a hash of the given string.
15uint64_t cstring_hash(const char* str);
16
17/// Copy 'count' characters from the source to the destination, null-terminating
18/// the destination.
19static inline void cstring_copy(char* dst, const char* src, size_t count) {
20 memcpy(dst, src, count * sizeof(char));
21 dst[count] = '\0';
22}
14 23
15// ----------------------------------------------------------------------------- 24// -----------------------------------------------------------------------------
16// Fix-sized strings. 25// Fix-sized strings.
@@ -38,11 +47,14 @@
38 return (STRING){0}; \ 47 return (STRING){0}; \
39 } else { \ 48 } else { \
40 STRING str = (STRING){0}; \ 49 STRING str = (STRING){0}; \
41 str.length = strlcpy(str.str, cstr, SIZE); \ 50 str.length = strlen(cstr); \
51 cstring_copy(str.str, cstr, str.length); \
42 return str; \ 52 return str; \
43 } \ 53 } \
44 } \ 54 } \
45 \ 55 \
56 static inline STRING STRING##_make_empty(void) { return (STRING){0}; } \
57 \
46 static inline STRING STRING##_dirname(const STRING path) { \ 58 static inline STRING STRING##_dirname(const STRING path) { \
47 STRING str = path; \ 59 STRING str = path; \
48 for (int i = str.length - 1; i >= 0; --i) { \ 60 for (int i = str.length - 1; i >= 0; --i) { \
@@ -63,7 +75,7 @@
63 static inline void STRING##_append_cstr_len( \ 75 static inline void STRING##_append_cstr_len( \
64 STRING* a, const char* b, const size_t b_length) { \ 76 STRING* a, const char* b, const size_t b_length) { \
65 ASSERT(a->length + b_length + 1 <= SIZE); \ 77 ASSERT(a->length + b_length + 1 <= SIZE); \
66 strlcpy(a->str + a->length, b, SIZE - a->length); \ 78 cstring_copy(a->str + a->length, b, b_length); \
67 a->length += b_length; \ 79 a->length += b_length; \
68 } \ 80 } \
69 \ 81 \
@@ -79,9 +91,8 @@
79 const STRING a, const char* b, const size_t b_length) { \ 91 const STRING a, const char* b, const size_t b_length) { \
80 ASSERT(a.length + b_length + 1 <= SIZE); \ 92 ASSERT(a.length + b_length + 1 <= SIZE); \
81 STRING str = {0}; \ 93 STRING str = {0}; \
82 strlcpy(str.str, a.str, SIZE); \ 94 STRING##_append_cstr_len(&str, a.str, a.length); \
83 strlcpy(str.str + a.length, b, SIZE - a.length); \ 95 STRING##_append_cstr_len(&str, b, b_length); \
84 str.length = a.length + b_length; \
85 return str; \ 96 return str; \
86 } \ 97 } \
87 \ 98 \
@@ -97,6 +108,15 @@
97 return STRING##_concat(STRING##_concat_cstr(a, "/"), b); \ 108 return STRING##_concat(STRING##_concat_cstr(a, "/"), b); \
98 } \ 109 } \
99 \ 110 \
111 static inline STRING STRING##_slice( \
112 const STRING a, const size_t start, const size_t end) { \
113 ASSERT(start < a.length); \
114 ASSERT(end <= a.length); \
115 STRING str = {0}; \
116 cstring_copy(str.str, &a.str[start], end - start); \
117 return str; \
118 } \
119 \
100 static inline bool STRING##_eq_cstr_len( \ 120 static inline bool STRING##_eq_cstr_len( \
101 const STRING a, const char* b, size_t b_length) { \ 121 const STRING a, const char* b, size_t b_length) { \
102 return (a.length == b_length) && strncmp(a.str, b, a.length) == 0; \ 122 return (a.length == b_length) && strncmp(a.str, b, a.length) == 0; \
@@ -124,15 +144,6 @@
124 return cstring_hash(str.str); \ 144 return cstring_hash(str.str); \
125 } 145 }
126 146
127/// Return a hash of the given string.
128static inline uint64_t cstring_hash(const char* str) {
129 uint64_t hash = 0;
130 for (size_t i = 0; i < strlen(str); ++i) {
131 hash = (uint64_t)str[i] + (hash << 6) + (hash << 16) - hash;
132 }
133 return hash;
134}
135
136DEF_STRING(sstring, 32) // Small. 147DEF_STRING(sstring, 32) // Small.
137DEF_STRING(mstring, 256) // Medium. 148DEF_STRING(mstring, 256) // Medium.
138DEF_STRING(lstring, 1024) // Large. 149DEF_STRING(lstring, 1024) // Large.
@@ -158,6 +169,9 @@ static inline size_t string_length(const string str) { return str.length; }
158/// Get the string's data. 169/// Get the string's data.
159static inline const char* string_data(const string str) { return str.data; } 170static inline const char* string_data(const string str) { return str.data; }
160 171
172/// Get the string's data.
173static inline const char* string_cstr(const string* str) { return str->data; }
174
161/// Concatenate two strings. 175/// Concatenate two strings.
162string string_concat(string left, string right); 176string string_concat(string left, string right);
163 177
diff --git a/cstring/src/cstring.c b/cstring/src/cstring.c
index 832cb85..100c130 100644
--- a/cstring/src/cstring.c
+++ b/cstring/src/cstring.c
@@ -23,7 +23,7 @@ string string_new(const char* cstr) {
23void string_del(string* str) { 23void string_del(string* str) {
24 if (str->data) { 24 if (str->data) {
25 free((void*)str->data); 25 free((void*)str->data);
26 str->data = 0; 26 str->data = nullptr;
27 str->length = 0; 27 str->length = 0;
28 } 28 }
29} 29}
@@ -101,3 +101,11 @@ string string_format_size(size_t size) {
101 .length = length, 101 .length = length,
102 }; 102 };
103} 103}
104
105uint64_t cstring_hash(const char* str) {
106 uint64_t hash = 0;
107 for (size_t i = 0; i < strlen(str); ++i) {
108 hash = (uint64_t)str[i] + (hash << 6) + (hash << 16) - hash;
109 }
110 return hash;
111}
diff --git a/error/CMakeLists.txt b/error/CMakeLists.txt
index fbbc945..c74921f 100644
--- a/error/CMakeLists.txt
+++ b/error/CMakeLists.txt
@@ -15,4 +15,4 @@ target_include_directories(error PUBLIC
15target_link_libraries(error 15target_link_libraries(error
16 cstring) 16 cstring)
17 17
18target_compile_options(error PRIVATE -Wall -Wextra) 18target_compile_options(error PRIVATE -Wall -Wextra -Wpedantic)
diff --git a/filesystem/CMakeLists.txt b/filesystem/CMakeLists.txt
index 508f99d..56cc870 100644
--- a/filesystem/CMakeLists.txt
+++ b/filesystem/CMakeLists.txt
@@ -16,4 +16,4 @@ target_include_directories(filesystem PUBLIC
16target_link_libraries(filesystem PRIVATE 16target_link_libraries(filesystem PRIVATE
17 cassert) 17 cassert)
18 18
19target_compile_options(filesystem PRIVATE -Wall -Wextra) 19target_compile_options(filesystem PRIVATE -Wall -Wextra -Wpedantic)
diff --git a/filesystem/include/filesystem.h b/filesystem/include/filesystem.h
index 1c354b7..bc7f953 100644
--- a/filesystem/include/filesystem.h
+++ b/filesystem/include/filesystem.h
@@ -6,8 +6,26 @@
6#include <stddef.h> 6#include <stddef.h>
7#include <stdio.h> 7#include <stdio.h>
8 8
9#define WITH_FILE(FILEPATH, BODY) \
10 { \
11 assert(FILEPATH); \
12 FILE* file = fopen(FILEPATH, "rb"); \
13 if (file) { \
14 BODY; \
15 fclose(file); \
16 } \
17 }
18
19/// Get the file's size.
20size_t get_file_size(const char* filename);
21
9/// Get the file's size. 22/// Get the file's size.
10size_t get_file_size(FILE* file); 23size_t get_file_size_f(FILE* file);
11 24
12/// Read the entire contents of the file into memory. 25/// Read the entire contents of the file into memory.
13void* read_file(const char* filepath); 26void* read_file(const char* filepath);
27
28/// Read the entire contents of the file into memory.
29///
30/// The given buffer must be large enough to hold the file's contents.
31bool read_file_f(FILE*, void* buffer);
diff --git a/filesystem/src/filesystem.c b/filesystem/src/filesystem.c
index b228e85..b30c072 100644
--- a/filesystem/src/filesystem.c
+++ b/filesystem/src/filesystem.c
@@ -5,21 +5,27 @@
5#include <stdlib.h> 5#include <stdlib.h>
6#include <string.h> 6#include <string.h>
7 7
8size_t get_file_size(FILE* file) { 8size_t get_file_size(const char* filename) {
9 size_t size = 0;
10 WITH_FILE(filename, size = get_file_size_f(file));
11 return size;
12}
13
14size_t get_file_size_f(FILE* file) {
9 assert(file); 15 assert(file);
10 const long int starting_pos = ftell(file); 16 const long int starting_pos = ftell(file);
11 if (starting_pos == -1) { 17 if (starting_pos == -1) {
12 return (size_t)-1; 18 return 0;
13 } 19 }
14 if (fseek(file, 0, SEEK_END) != 0) { 20 if (fseek(file, 0, SEEK_END) != 0) {
15 return (size_t)-1; 21 return 0;
16 } 22 }
17 const size_t file_size = ftell(file); 23 const size_t file_size = ftell(file);
18 if (file_size == (size_t)-1) { 24 if (file_size == (size_t)-1) {
19 return (size_t)-1; 25 return 0;
20 } 26 }
21 if (fseek(file, starting_pos, SEEK_SET) != 0) { 27 if (fseek(file, starting_pos, SEEK_SET) != 0) {
22 return (size_t)-1; 28 return 0;
23 } 29 }
24 return file_size; 30 return file_size;
25} 31}
@@ -27,31 +33,38 @@ size_t get_file_size(FILE* file) {
27void* read_file(const char* filepath) { 33void* read_file(const char* filepath) {
28 assert(filepath); 34 assert(filepath);
29 35
30 void* data = 0; 36 void* data = nullptr;
37 bool success = false;
31 38
32 FILE* file = fopen(filepath, "rb"); 39 WITH_FILE(filepath, {
33 if (!file) { 40 const size_t file_size = get_file_size_f(file);
34 return 0; 41 if (file_size > 0) {
35 } 42 data = calloc(1, file_size);
36 const size_t file_size = get_file_size(file); 43 if (data != nullptr) {
37 if (file_size == (size_t)-1) { 44 if (fread(data, 1, file_size, file) == file_size) {
38 goto cleanup; 45 success = true;
39 } 46 }
47 }
48 }
49 });
40 50
41 data = calloc(1, file_size); 51 if (!success) {
42 if (!data) { 52 free(data);
43 goto cleanup; 53 data = nullptr;
44 }
45 if (fread(data, 1, file_size, file) != file_size) {
46 goto cleanup;
47 } 54 }
48
49 return data; 55 return data;
56}
50 57
51cleanup: 58bool read_file_f(FILE* file, void* buffer) {
52 fclose(file); 59 assert(file);
53 if (data) { 60 assert(buffer);
54 free(data); 61
62 bool success = false;
63 const size_t file_size = get_file_size_f(file);
64 if (file_size > 0) {
65 if (fread(buffer, 1, file_size, file) == file_size) {
66 success = true;
67 }
55 } 68 }
56 return 0; 69 return success;
57} 70}
diff --git a/filesystem/src/path.c b/filesystem/src/path.c
index 2ce5a04..544a5d1 100644
--- a/filesystem/src/path.c
+++ b/filesystem/src/path.c
@@ -21,7 +21,7 @@ path path_new(const char* str) {
21void path_del(path* path) { 21void path_del(path* path) {
22 if (path) { 22 if (path) {
23 free(path->data); 23 free(path->data);
24 path->data = 0; 24 path->data = nullptr;
25 path->size = 0; 25 path->size = 0;
26 } 26 }
27} 27}
diff --git a/hash/CMakeLists.txt b/hash/CMakeLists.txt
new file mode 100644
index 0000000..f0a5e55
--- /dev/null
+++ b/hash/CMakeLists.txt
@@ -0,0 +1,14 @@
1cmake_minimum_required(VERSION 3.5)
2
3project(hash)
4
5set(CMAKE_C_STANDARD 23)
6set(CMAKE_C_STANDARD_REQUIRED On)
7set(CMAKE_C_EXTENSIONS Off)
8
9add_library(hash
10 src/fnv1a.c)
11
12target_include_directories(hash PUBLIC include)
13
14target_compile_options(hash PRIVATE -Wall -Wextra -Wpedantic)
diff --git a/hash/include/fnv1a.h b/hash/include/fnv1a.h
new file mode 100644
index 0000000..0d2e7cf
--- /dev/null
+++ b/hash/include/fnv1a.h
@@ -0,0 +1,9 @@
1#pragma once
2
3#include <stddef.h>
4#include <stdint.h>
5
6uint32_t fnv1a32(const void* buffer, size_t size_bytes);
7
8uint32_t fnv1a32_begin();
9uint32_t fnv1a32_update(uint32_t hash, const void* buffer, size_t size_bytes);
diff --git a/hash/src/fnv1a.c b/hash/src/fnv1a.c
new file mode 100644
index 0000000..32cb538
--- /dev/null
+++ b/hash/src/fnv1a.c
@@ -0,0 +1,23 @@
1#include <fnv1a.h>
2
3#include <assert.h>
4
5#define FNV_PRIME 2166136261
6#define FNV_OFFSET_BASIS 16777619
7
8uint32_t fnv1a_32(const void* buffer, size_t size) {
9 assert(buffer);
10 return fnv1a32_update(fnv1a32_begin(), buffer, size);
11}
12
13uint32_t fnv1a32_begin() { return FNV_PRIME; }
14
15uint32_t fnv1a32_update(uint32_t hash, const void* buffer, size_t size) {
16 assert(buffer);
17 const uint8_t* bytes = buffer;
18 for (size_t i = 0; i < size; i++) {
19 hash = hash ^ bytes[i];
20 hash = hash * FNV_OFFSET_BASIS;
21 }
22 return hash;
23}
diff --git a/list/CMakeLists.txt b/list/CMakeLists.txt
index 7e1df38..23361cf 100644
--- a/list/CMakeLists.txt
+++ b/list/CMakeLists.txt
@@ -21,4 +21,4 @@ add_executable(list_test
21target_link_libraries(list_test 21target_link_libraries(list_test
22 list) 22 list)
23 23
24target_compile_options(list_test PRIVATE -DUNIT_TEST -Wall -Wextra) 24target_compile_options(list_test PRIVATE -DUNIT_TEST -Wall -Wextra -Wpedantic)
diff --git a/list/include/list.h b/list/include/list.h
index 24291e1..92f30f7 100644
--- a/list/include/list.h
+++ b/list/include/list.h
@@ -23,7 +23,7 @@ static inline void* alloc(size_t size) {
23 23
24/// Create a new empty list. 24/// Create a new empty list.
25#define make_list(type) \ 25#define make_list(type) \
26 (type##_list) { 0 } 26 (type##_list) { nullptr }
27 27
28/// Delete the list. 28/// Delete the list.
29#define del_list(list) \ 29#define del_list(list) \
@@ -32,7 +32,10 @@ static inline void* alloc(size_t size) {
32 node = node->next; \ 32 node = node->next; \
33 free(cur); \ 33 free(cur); \
34 } \ 34 } \
35 list.head = 0; 35 list.head = nullptr;
36
37/// Whether the list is empty.
38#define list_empty(list) (!list.head)
36 39
37/// Prepend a value to the list. 40/// Prepend a value to the list.
38#define list_add(list, value) \ 41#define list_add(list, value) \
@@ -46,6 +49,23 @@ static inline void* alloc(size_t size) {
46 list.head = node; \ 49 list.head = node; \
47 } 50 }
48 51
52/// Append a value to the list.
53#define list_push(list, value) \
54 { \
55 __typeof__(list.head) node = alloc(sizeof(*list.head)); \
56 node->val = value; \
57 node->next = 0; \
58 if (!list.head) { \
59 list.head = node; \
60 } else { \
61 __typeof__(list.head) next = list.head; \
62 while (next && next->next) { \
63 next = next->next; \
64 } \
65 next->next = node; \
66 } \
67 }
68
49/// Delete the first occurrence of the value from the list. 69/// Delete the first occurrence of the value from the list.
50#define list_remove(list, search_value) \ 70#define list_remove(list, search_value) \
51 for (__typeof__(list.head) iter = list.head; iter; iter = iter->next) { \ 71 for (__typeof__(list.head) iter = list.head; iter; iter = iter->next) { \
@@ -76,10 +96,10 @@ static inline void* alloc(size_t size) {
76 node->next->prev = node->prev; \ 96 node->next->prev = node->prev; \
77 } \ 97 } \
78 if (list.head == node) { \ 98 if (list.head == node) { \
79 list.head = 0; \ 99 list.head = nullptr; \
80 } \ 100 } \
81 free(node); \ 101 free(node); \
82 node = 0; \ 102 node = nullptr; \
83 } 103 }
84 104
85/// Iterate over all the items in the list. 105/// Iterate over all the items in the list.
diff --git a/list/test/list_test.c b/list/test/list_test.c
index 418e156..4ac5b5b 100644
--- a/list/test/list_test.c
+++ b/list/test/list_test.c
@@ -52,7 +52,7 @@ TEST_CASE(list_remove_by_value) {
52TEST_CASE(list_remove_by_address) { 52TEST_CASE(list_remove_by_address) {
53 const int N = 3; 53 const int N = 3;
54 54
55 int* ptrs[3] = {0}; 55 int* ptrs[3] = {nullptr};
56 56
57 int_list list = make_list(int); 57 int_list list = make_list(int);
58 for (int i = 0; i < N; ++i) { 58 for (int i = 0; i < N; ++i) {
diff --git a/log/CMakeLists.txt b/log/CMakeLists.txt
index 615e200..1aa96ee 100644
--- a/log/CMakeLists.txt
+++ b/log/CMakeLists.txt
@@ -12,4 +12,4 @@ add_library(log
12target_include_directories(log PUBLIC 12target_include_directories(log PUBLIC
13 include) 13 include)
14 14
15target_compile_options(log PRIVATE -Wall -Wextra) 15target_compile_options(log PRIVATE -Wall -Wextra -Wpedantic)
diff --git a/mem/CMakeLists.txt b/mem/CMakeLists.txt
index 89bf444..d4f065b 100644
--- a/mem/CMakeLists.txt
+++ b/mem/CMakeLists.txt
@@ -18,7 +18,7 @@ target_link_libraries(mem
18 cassert 18 cassert
19 list) 19 list)
20 20
21target_compile_options(mem PRIVATE -Wall -Wextra) 21target_compile_options(mem PRIVATE -Wall -Wextra -Wpedantic)
22 22
23# Test 23# Test
24 24
@@ -28,4 +28,4 @@ add_executable(mem_test
28target_link_libraries(mem_test 28target_link_libraries(mem_test
29 mem) 29 mem)
30 30
31target_compile_options(mem_test PRIVATE -DUNIT_TEST -DNDEBUG -Wall -Wextra) 31target_compile_options(mem_test PRIVATE -DUNIT_TEST -DNDEBUG -Wall -Wextra -Wpedantic)
diff --git a/mem/include/mem.h b/mem/include/mem.h
index 224b069..d669f2d 100644
--- a/mem/include/mem.h
+++ b/mem/include/mem.h
@@ -68,13 +68,14 @@
68/// Allocate a new chunk of N blocks. 68/// Allocate a new chunk of N blocks.
69/// Return a pointer to the first block of the chunk. 69/// Return a pointer to the first block of the chunk.
70/// When there is no space left in the allocator, allocation can either trap 70/// When there is no space left in the allocator, allocation can either trap
71/// (default) or gracefully return 0. Call mem_enable_traps() to toggle this 71/// (default) or gracefully return null. Call mem_enable_traps() to toggle this
72/// behaviour. 72/// behaviour.
73/// New chunks are conveniently zeroed out. 73/// New chunks are conveniently zeroed out.
74#define mem_alloc(MEM, num_blocks) mem_alloc_(&(MEM)->mem, num_blocks) 74#define mem_alloc(MEM, num_blocks) \
75 (__typeof__((MEM)->object[0])*)mem_alloc_(&(MEM)->mem, num_blocks)
75 76
76/// Free the chunk. 77/// Free the chunk.
77/// The chunk pointer is conveniently set to 0. 78/// The chunk pointer is conveniently set to null.
78#define mem_free(MEM, CHUNK) mem_free_(&(MEM)->mem, (void**)CHUNK) 79#define mem_free(MEM, CHUNK) mem_free_(&(MEM)->mem, (void**)CHUNK)
79 80
80/// Return a pointer to a chunk given the chunk's handle. 81/// Return a pointer to a chunk given the chunk's handle.
diff --git a/mem/src/mem.c b/mem/src/mem.c
index 4f5e5ef..70648c9 100644
--- a/mem/src/mem.c
+++ b/mem/src/mem.c
@@ -46,24 +46,27 @@ void mem_del_(Memory* mem) {
46 if (mem->dynamic) { 46 if (mem->dynamic) {
47 if (mem->chunks) { 47 if (mem->chunks) {
48 free(mem->chunks); 48 free(mem->chunks);
49 mem->chunks = 0; 49 mem->chunks = nullptr;
50 } 50 }
51 if (mem->blocks) { 51 if (mem->blocks) {
52 free(mem->blocks); 52 free(mem->blocks);
53 mem->blocks = 0; 53 mem->blocks = nullptr;
54 } 54 }
55 } 55 }
56} 56}
57 57
58void mem_clear_(Memory* mem) { 58void mem_clear_(Memory* mem) {
59 assert(mem); 59 assert(mem);
60 mem->next_free_chunk = 0; 60 if (mem->num_blocks > 0) {
61 memset(mem->blocks, 0, mem->num_blocks * mem->block_size_bytes); 61 mem->num_used_blocks = 0;
62 memset(mem->chunks, 0, mem->num_blocks * sizeof(Chunk)); 62 mem->next_free_chunk = 0;
63 63 memset(mem->blocks, 0, mem->num_blocks * mem->block_size_bytes);
64 // Initialize the head as one large free chunk. 64 memset(mem->chunks, 0, mem->num_blocks * sizeof(Chunk));
65 Chunk* head = &mem->chunks[0]; 65
66 head->num_blocks = mem->num_blocks; 66 // Initialize the head as one large free chunk.
67 Chunk* head = &mem->chunks[0];
68 head->num_blocks = mem->num_blocks;
69 }
67} 70}
68 71
69void* mem_alloc_(Memory* mem, size_t num_blocks) { 72void* mem_alloc_(Memory* mem, size_t num_blocks) {
@@ -113,10 +116,11 @@ void* mem_alloc_(Memory* mem, size_t num_blocks) {
113 return &mem->blocks[chunk_idx * mem->block_size_bytes]; 116 return &mem->blocks[chunk_idx * mem->block_size_bytes];
114 } else { 117 } else {
115 if (mem->trap) { 118 if (mem->trap) {
116 FAIL("Memory allocation failed, increase the allocator's capacity or " 119 FAIL(
117 "avoid fragmentation."); 120 "Memory allocation failed, increase the allocator's capacity or "
121 "avoid fragmentation.");
118 } 122 }
119 return 0; // Large-enough free chunk not found. 123 return nullptr; // Large-enough free chunk not found.
120 } 124 }
121} 125}
122 126
@@ -172,7 +176,7 @@ void mem_free_(Memory* mem, void** chunk_ptr) {
172 176
173 mem->num_used_blocks--; 177 mem->num_used_blocks--;
174 178
175 *chunk_ptr = 0; 179 *chunk_ptr = nullptr;
176} 180}
177 181
178// The handle is the chunk's index. We don't call it an index in the public API 182// The handle is the chunk's index. We don't call it an index in the public API
diff --git a/mem/test/mem_test.c b/mem/test/mem_test.c
index 14718a5..52ce5a9 100644
--- a/mem/test/mem_test.c
+++ b/mem/test/mem_test.c
@@ -32,6 +32,12 @@ TEST_CASE(mem_create_dyn) {
32 mem_make_dyn(&mem, NUM_BLOCKS, sizeof(int)); 32 mem_make_dyn(&mem, NUM_BLOCKS, sizeof(int));
33} 33}
34 34
35// Clear an uninitialized allocator.
36TEST_CASE(mem_clear_uninitialized) {
37 test_mem mem = {0};
38 mem_clear(&mem);
39}
40
35// Allocate N chunks of 1 block each. 41// Allocate N chunks of 1 block each.
36TEST_CASE(mem_fully_allocate) { 42TEST_CASE(mem_fully_allocate) {
37 test_mem mem; 43 test_mem mem;
@@ -39,7 +45,7 @@ TEST_CASE(mem_fully_allocate) {
39 45
40 for (int i = 0; i < NUM_BLOCKS; ++i) { 46 for (int i = 0; i < NUM_BLOCKS; ++i) {
41 const int* block = mem_alloc(&mem, 1); 47 const int* block = mem_alloc(&mem, 1);
42 TEST_TRUE(block != 0); 48 TEST_TRUE(block != nullptr);
43 } 49 }
44 50
45 TEST_TRUE(mem_size(&mem) == NUM_BLOCKS); 51 TEST_TRUE(mem_size(&mem) == NUM_BLOCKS);
@@ -50,15 +56,15 @@ TEST_CASE(mem_fill_then_free) {
50 test_mem mem; 56 test_mem mem;
51 mem_make(&mem); 57 mem_make(&mem);
52 58
53 int* blocks[NUM_BLOCKS] = {0}; 59 int* blocks[NUM_BLOCKS] = {nullptr};
54 for (int i = 0; i < NUM_BLOCKS; i++) { 60 for (int i = 0; i < NUM_BLOCKS; i++) {
55 blocks[i] = mem_alloc(&mem, 1); 61 blocks[i] = mem_alloc(&mem, 1);
56 TEST_TRUE(blocks[i] != 0); 62 TEST_TRUE(blocks[i] != nullptr);
57 } 63 }
58 64
59 for (int i = 0; i < NUM_BLOCKS; i++) { 65 for (int i = 0; i < NUM_BLOCKS; i++) {
60 mem_free(&mem, &blocks[i]); 66 mem_free(&mem, &blocks[i]);
61 TEST_EQUAL(blocks[i], 0); // Pointer should be set to 0 on free. 67 TEST_EQUAL(blocks[i], nullptr); // Pointer should be set to 0 on free.
62 } 68 }
63 69
64 TEST_EQUAL(count(&mem), 0); 70 TEST_EQUAL(count(&mem), 0);
@@ -74,12 +80,12 @@ TEST_CASE(mem_allocate_beyond_max_size) {
74 80
75 // Fully allocate the mem. 81 // Fully allocate the mem.
76 for (int i = 0; i < NUM_BLOCKS; ++i) { 82 for (int i = 0; i < NUM_BLOCKS; ++i) {
77 TEST_TRUE(mem_alloc(&mem, 1) != 0); 83 TEST_TRUE(mem_alloc(&mem, 1) != nullptr);
78 } 84 }
79 85
80 // Past the end. 86 // Past the end.
81 for (int i = 0; i < NUM_BLOCKS; ++i) { 87 for (int i = 0; i < NUM_BLOCKS; ++i) {
82 TEST_EQUAL(mem_alloc(&mem, 1), 0); 88 TEST_EQUAL(mem_alloc(&mem, 1), nullptr);
83 } 89 }
84 90
85 TEST_TRUE(mem_size(&mem) == NUM_BLOCKS); 91 TEST_TRUE(mem_size(&mem) == NUM_BLOCKS);
@@ -105,7 +111,7 @@ TEST_CASE(mem_zero_free_block_after_free) {
105 mem_make(&mem); 111 mem_make(&mem);
106 112
107 int* val = mem_alloc(&mem, 1); 113 int* val = mem_alloc(&mem, 1);
108 TEST_TRUE(val != 0); 114 TEST_TRUE(val != nullptr);
109 *val = 177; 115 *val = 177;
110 116
111 int* old_val = val; 117 int* old_val = val;
@@ -131,7 +137,7 @@ TEST_CASE(mem_traverse_partially_full) {
131 137
132 for (int i = 0; i < N; ++i) { 138 for (int i = 0; i < N; ++i) {
133 int* val = mem_alloc(&mem, 1); 139 int* val = mem_alloc(&mem, 1);
134 TEST_TRUE(val != 0); 140 TEST_TRUE(val != nullptr);
135 *val = i + 1; 141 *val = i + 1;
136 } 142 }
137 143
@@ -146,7 +152,7 @@ TEST_CASE(mem_traverse_full) {
146 152
147 for (int i = 0; i < NUM_BLOCKS; ++i) { 153 for (int i = 0; i < NUM_BLOCKS; ++i) {
148 int* val = mem_alloc(&mem, 1); 154 int* val = mem_alloc(&mem, 1);
149 TEST_TRUE(val != 0); 155 TEST_TRUE(val != nullptr);
150 *val = i + 1; 156 *val = i + 1;
151 } 157 }
152 158
@@ -161,7 +167,7 @@ TEST_CASE(mem_get_block) {
161 167
162 for (int i = 0; i < NUM_BLOCKS; ++i) { 168 for (int i = 0; i < NUM_BLOCKS; ++i) {
163 int* block = mem_alloc(&mem, 1); 169 int* block = mem_alloc(&mem, 1);
164 TEST_TRUE(block != 0); 170 TEST_TRUE(block != nullptr);
165 *block = i; 171 *block = i;
166 TEST_EQUAL(mem_get_chunk_handle(&mem, block), (size_t)i); 172 TEST_EQUAL(mem_get_chunk_handle(&mem, block), (size_t)i);
167 } 173 }
@@ -179,7 +185,7 @@ TEST_CASE(mem_fragmentation) {
179 test_mem mem; 185 test_mem mem;
180 mem_make(&mem); 186 mem_make(&mem);
181 187
182 int* blocks[NUM_BLOCKS] = {0}; 188 int* blocks[NUM_BLOCKS] = {nullptr};
183 int next_block = 0; 189 int next_block = 0;
184 190
185#define ALLOC(num_blocks) \ 191#define ALLOC(num_blocks) \
@@ -205,7 +211,7 @@ TEST_CASE(mem_fragmentation) {
205 211
206 // Should be able to allocate 1 chunk of N blocks. 212 // Should be able to allocate 1 chunk of N blocks.
207 const void* chunk = mem_alloc(&mem, NUM_BLOCKS); 213 const void* chunk = mem_alloc(&mem, NUM_BLOCKS);
208 TEST_TRUE(chunk != 0); 214 TEST_TRUE(chunk != nullptr);
209} 215}
210 216
211// Clear and re-use an allocator. 217// Clear and re-use an allocator.
@@ -216,15 +222,17 @@ TEST_CASE(mem_clear_then_reuse) {
216 // Allocate chunks, contents not important. 222 // Allocate chunks, contents not important.
217 for (int i = 0; i < NUM_BLOCKS; ++i) { 223 for (int i = 0; i < NUM_BLOCKS; ++i) {
218 int* chunk = mem_alloc(&mem, 1); 224 int* chunk = mem_alloc(&mem, 1);
219 TEST_TRUE(chunk != 0); 225 TEST_TRUE(chunk != nullptr);
220 } 226 }
221 227
222 mem_clear(&mem); 228 mem_clear(&mem);
229 TEST_EQUAL(mem_size(&mem), 0);
230 TEST_EQUAL(mem_capacity(&mem), NUM_BLOCKS);
223 231
224 // Allocate chunks and assign values 0..N. 232 // Allocate chunks and assign values 0..N.
225 for (int i = 0; i < NUM_BLOCKS; ++i) { 233 for (int i = 0; i < NUM_BLOCKS; ++i) {
226 int* chunk = mem_alloc(&mem, 1); 234 int* chunk = mem_alloc(&mem, 1);
227 TEST_TRUE(chunk != 0); 235 TEST_TRUE(chunk != nullptr);
228 *chunk = i + 1; 236 *chunk = i + 1;
229 } 237 }
230 238
diff --git a/mempool/CMakeLists.txt b/mempool/CMakeLists.txt
index 31ff0e1..d6a9772 100644
--- a/mempool/CMakeLists.txt
+++ b/mempool/CMakeLists.txt
@@ -17,7 +17,7 @@ target_include_directories(mempool PUBLIC
17target_link_libraries(mempool PRIVATE 17target_link_libraries(mempool PRIVATE
18 cassert) 18 cassert)
19 19
20target_compile_options(mempool PRIVATE -Wall -Wextra) 20target_compile_options(mempool PRIVATE -Wall -Wextra -Wpedantic)
21 21
22# Test 22# Test
23 23
@@ -27,4 +27,4 @@ add_executable(mempool_test
27target_link_libraries(mempool_test 27target_link_libraries(mempool_test
28 mempool) 28 mempool)
29 29
30target_compile_options(mempool_test PRIVATE -DUNIT_TEST -DNDEBUG -Wall -Wextra) 30target_compile_options(mempool_test PRIVATE -DUNIT_TEST -DNDEBUG -Wall -Wextra -Wpedantic)
diff --git a/mempool/README.md b/mempool/README.md
index ed2935e..7eb950e 100644
--- a/mempool/README.md
+++ b/mempool/README.md
@@ -1,20 +1,15 @@
1# Mempool 1# Mempool
2 2
3A memory pool implementation. 3A memory pool of fixed-sized blocks with O(1) allocation and deallocation.
4 4
5Each block in the pool is tagged with a boolean value that indicates whether the 5Each block in the pool is tagged with a boolean value that indicates whether the
6block is free or in use. The allocator otherwise maintains little additional 6block is free or in use, as well as a pointer to the next free/used block.
7information. Therefore, some operations have linear-time complexity. 7Blocks thus form two lists, a free list and a used list. The allocator
8Specifically: 8maintains the two lists when allocating/deallocating blocks.
9 9
10- Allocating a block scans the pool for the next free block in linear time. 10The allocator's internal data is stored separately from the block data so that
11- Freeing a block runs in constant time. 11the data remains tightly packed.
12- Iterating over the pool's used blocks is linear over the number of blocks in
13 the pool, as opposed to just the number of used blocks.
14 12
15The allocator's internal data is also stored separately from the main array of 13Free blocks in the mempool always remain zeroed out for convenience of
16blocks so that the block data remains tightly packed. 14programming and debugging. If the application's data structures are valid when
17 15zeroed out, then they do not need to be explicitly initialized.
18For convenience of programming and debugging, free blocks in the mempool always
19remain zeroed out. If your data structures are valid when zeroed out, then you
20do not need to explicitly initialize them.
diff --git a/mempool/include/mempool.h b/mempool/include/mempool.h
index 245173b..ad25614 100644
--- a/mempool/include/mempool.h
+++ b/mempool/include/mempool.h
@@ -64,15 +64,16 @@
64#define mempool_clear(POOL) mempool_clear_(&(POOL)->pool) 64#define mempool_clear(POOL) mempool_clear_(&(POOL)->pool)
65 65
66/// Allocate a new block. 66/// Allocate a new block.
67/// Return 0 if there is no memory left. 67/// Return null if there is no memory left.
68/// When there is no space left in the pool, allocation can either trap 68/// When there is no space left in the pool, allocation can either trap
69/// (default) or gracefully return 0. Call mem_enable_traps() to toggle this 69/// (default) or gracefully return null. Call mem_enable_traps() to toggle this
70/// behaviour. 70/// behaviour.
71/// New blocks are conveniently zeroed out. 71/// New blocks are conveniently zeroed out.
72#define mempool_alloc(POOL) mempool_alloc_(&(POOL)->pool) 72#define mempool_alloc(POOL) \
73 (__typeof__((POOL)->object[0])*)mempool_alloc_(&(POOL)->pool)
73 74
74/// Free the block. 75/// Free the block.
75/// The block pointer is conveniently set to 0. 76/// The block pointer is conveniently set to null.
76#define mempool_free(POOL, BLOCK_PTR) \ 77#define mempool_free(POOL, BLOCK_PTR) \
77 assert(*BLOCK_PTR); \ 78 assert(*BLOCK_PTR); \
78 mempool_free_(&(POOL)->pool, (void**)BLOCK_PTR) 79 mempool_free_(&(POOL)->pool, (void**)BLOCK_PTR)
@@ -106,8 +107,8 @@
106/// It is valid to mempool_free() the object at each step of the iteration. 107/// It is valid to mempool_free() the object at each step of the iteration.
107#define mempool_foreach(POOL, ITER, BODY) \ 108#define mempool_foreach(POOL, ITER, BODY) \
108 { \ 109 { \
109 size_t i = (POOL)->pool.used; \
110 if ((POOL)->pool.num_used_blocks > 0) { \ 110 if ((POOL)->pool.num_used_blocks > 0) { \
111 size_t i = (POOL)->pool.used; \
111 do { \ 112 do { \
112 if ((POOL)->pool.block_info[i].used) { \ 113 if ((POOL)->pool.block_info[i].used) { \
113 __typeof__((POOL)->object[0])* ITER = \ 114 __typeof__((POOL)->object[0])* ITER = \
diff --git a/mempool/src/mempool.c b/mempool/src/mempool.c
index 46f1053..2c3c725 100644
--- a/mempool/src/mempool.c
+++ b/mempool/src/mempool.c
@@ -9,6 +9,7 @@
9/// All of the blocks in the pool are assumed free. 9/// All of the blocks in the pool are assumed free.
10static void init_free_list(mempool* pool) { 10static void init_free_list(mempool* pool) {
11 assert(pool); 11 assert(pool);
12 assert(pool->num_blocks > 0);
12 for (size_t i = 0; i < pool->num_blocks - 1; ++i) { 13 for (size_t i = 0; i < pool->num_blocks - 1; ++i) {
13 pool->block_info[i].next_free = i + 1; 14 pool->block_info[i].next_free = i + 1;
14 } 15 }
@@ -34,7 +35,7 @@ bool mempool_make_(
34 block_info = calloc(num_blocks, sizeof(BlockInfo)); 35 block_info = calloc(num_blocks, sizeof(BlockInfo));
35 blocks = calloc(num_blocks, block_size_bytes); 36 blocks = calloc(num_blocks, block_size_bytes);
36 pool->dynamic = true; 37 pool->dynamic = true;
37 if ((block_info == 0) || (blocks == 0)) { 38 if ((block_info == nullptr) || (blocks == nullptr)) {
38 return false; 39 return false;
39 } 40 }
40 } else { 41 } else {
@@ -55,22 +56,25 @@ void mempool_del_(mempool* pool) {
55 if (pool->dynamic) { 56 if (pool->dynamic) {
56 if (pool->block_info) { 57 if (pool->block_info) {
57 free(pool->block_info); 58 free(pool->block_info);
58 pool->block_info = 0; 59 pool->block_info = nullptr;
59 } 60 }
60 if (pool->blocks) { 61 if (pool->blocks) {
61 free(pool->blocks); 62 free(pool->blocks);
62 pool->blocks = 0; 63 pool->blocks = nullptr;
63 } 64 }
64 } 65 }
65} 66}
66 67
67void mempool_clear_(mempool* pool) { 68void mempool_clear_(mempool* pool) {
68 assert(pool); 69 assert(pool);
69 pool->head = 0; 70 if (pool->num_blocks > 0) {
70 pool->used = 0; 71 pool->head = 0;
71 memset(pool->blocks, 0, pool->num_blocks * pool->block_size_bytes); 72 pool->used = 0;
72 memset(pool->block_info, 0, pool->num_blocks * sizeof(BlockInfo)); 73 pool->num_used_blocks = 0;
73 init_free_list(pool); 74 memset(pool->blocks, 0, pool->num_blocks * pool->block_size_bytes);
75 memset(pool->block_info, 0, pool->num_blocks * sizeof(BlockInfo));
76 init_free_list(pool);
77 }
74} 78}
75 79
76void* mempool_alloc_(mempool* pool) { 80void* mempool_alloc_(mempool* pool) {
@@ -81,7 +85,7 @@ void* mempool_alloc_(mempool* pool) {
81 if (pool->trap) { 85 if (pool->trap) {
82 FAIL("mempool allocation failed, increase the pool's capacity."); 86 FAIL("mempool allocation failed, increase the pool's capacity.");
83 } 87 }
84 return 0; // Pool is full. 88 return nullptr; // Pool is full.
85 } 89 }
86 90
87 // Allocate the block. 91 // Allocate the block.
@@ -124,7 +128,7 @@ void mempool_free_(mempool* pool, void** block_ptr) {
124 128
125 pool->num_used_blocks--; 129 pool->num_used_blocks--;
126 130
127 *block_ptr = 0; 131 *block_ptr = nullptr;
128} 132}
129 133
130void* mempool_get_block_(const mempool* pool, size_t block_index) { 134void* mempool_get_block_(const mempool* pool, size_t block_index) {
diff --git a/mempool/test/mempool_test.c b/mempool/test/mempool_test.c
index 843f7e7..69658b9 100644
--- a/mempool/test/mempool_test.c
+++ b/mempool/test/mempool_test.c
@@ -25,13 +25,19 @@ TEST_CASE(mempool_create) {
25} 25}
26 26
27// Create a dynamically-backed pool. 27// Create a dynamically-backed pool.
28TEST_CASE(mem_create_dyn) { 28TEST_CASE(mempool_create_dyn) {
29 DEF_MEMPOOL_DYN(dyn_pool, int); 29 DEF_MEMPOOL_DYN(dyn_pool, int);
30 30
31 dyn_pool pool; 31 dyn_pool pool;
32 mempool_make_dyn(&pool, NUM_BLOCKS, sizeof(int)); 32 mempool_make_dyn(&pool, NUM_BLOCKS, sizeof(int));
33} 33}
34 34
35// Clear an uninitialized pool.
36TEST_CASE(mempool_clear_uninitialized) {
37 test_pool pool = {0};
38 mempool_clear(&pool);
39}
40
35// Allocate all N blocks. 41// Allocate all N blocks.
36TEST_CASE(mempool_allocate_until_full) { 42TEST_CASE(mempool_allocate_until_full) {
37 test_pool pool; 43 test_pool pool;
@@ -39,7 +45,7 @@ TEST_CASE(mempool_allocate_until_full) {
39 45
40 for (int i = 0; i < NUM_BLOCKS; ++i) { 46 for (int i = 0; i < NUM_BLOCKS; ++i) {
41 const int* block = mempool_alloc(&pool); 47 const int* block = mempool_alloc(&pool);
42 TEST_TRUE(block != 0); 48 TEST_TRUE(block != nullptr);
43 } 49 }
44 50
45 TEST_TRUE(mempool_size(&pool) == NUM_BLOCKS); 51 TEST_TRUE(mempool_size(&pool) == NUM_BLOCKS);
@@ -50,10 +56,10 @@ TEST_CASE(mempool_fill_then_free) {
50 test_pool pool; 56 test_pool pool;
51 mempool_make(&pool); 57 mempool_make(&pool);
52 58
53 int* blocks[NUM_BLOCKS] = {0}; 59 int* blocks[NUM_BLOCKS] = {nullptr};
54 for (int i = 0; i < NUM_BLOCKS; ++i) { 60 for (int i = 0; i < NUM_BLOCKS; ++i) {
55 blocks[i] = mempool_alloc(&pool); 61 blocks[i] = mempool_alloc(&pool);
56 TEST_TRUE(blocks[i] != 0); 62 TEST_TRUE(blocks[i] != nullptr);
57 } 63 }
58 64
59 for (int i = 0; i < NUM_BLOCKS; ++i) { 65 for (int i = 0; i < NUM_BLOCKS; ++i) {
@@ -74,7 +80,7 @@ TEST_CASE(mempool_allocate_beyond_max_size) {
74 80
75 // Fully allocate the pool. 81 // Fully allocate the pool.
76 for (int i = 0; i < NUM_BLOCKS; ++i) { 82 for (int i = 0; i < NUM_BLOCKS; ++i) {
77 TEST_TRUE(mempool_alloc(&pool) != 0); 83 TEST_TRUE(mempool_alloc(&pool) != nullptr);
78 } 84 }
79 85
80 // Past the end. 86 // Past the end.
@@ -105,7 +111,7 @@ TEST_CASE(mempool_zero_free_block_after_free) {
105 mempool_make(&pool); 111 mempool_make(&pool);
106 112
107 int* val = mempool_alloc(&pool); 113 int* val = mempool_alloc(&pool);
108 TEST_TRUE(val != 0); 114 TEST_TRUE(val != nullptr);
109 *val = 177; 115 *val = 177;
110 116
111 int* old_val = val; 117 int* old_val = val;
@@ -131,7 +137,7 @@ TEST_CASE(mempool_traverse_partially_full) {
131 137
132 for (int i = 0; i < N; ++i) { 138 for (int i = 0; i < N; ++i) {
133 int* val = mempool_alloc(&pool); 139 int* val = mempool_alloc(&pool);
134 TEST_TRUE(val != 0); 140 TEST_TRUE(val != nullptr);
135 *val = i + 1; 141 *val = i + 1;
136 } 142 }
137 143
@@ -146,7 +152,7 @@ TEST_CASE(mempool_traverse_full) {
146 152
147 for (int i = 0; i < NUM_BLOCKS; ++i) { 153 for (int i = 0; i < NUM_BLOCKS; ++i) {
148 int* val = mempool_alloc(&pool); 154 int* val = mempool_alloc(&pool);
149 TEST_TRUE(val != 0); 155 TEST_TRUE(val != nullptr);
150 *val = i + 1; 156 *val = i + 1;
151 } 157 }
152 158
@@ -161,7 +167,7 @@ TEST_CASE(mempool_get_block) {
161 167
162 for (int i = 0; i < NUM_BLOCKS; ++i) { 168 for (int i = 0; i < NUM_BLOCKS; ++i) {
163 int* block = mempool_alloc(&pool); 169 int* block = mempool_alloc(&pool);
164 TEST_TRUE(block != 0); 170 TEST_TRUE(block != nullptr);
165 *block = i; 171 *block = i;
166 TEST_EQUAL(mempool_get_block_index(&pool, block), (size_t)i); 172 TEST_EQUAL(mempool_get_block_index(&pool, block), (size_t)i);
167 } 173 }
@@ -172,22 +178,24 @@ TEST_CASE(mempool_get_block) {
172} 178}
173 179
174// Clear and re-use an allocator. 180// Clear and re-use an allocator.
175TEST_CASE(mem_clear_then_reuse) { 181TEST_CASE(mempool_clear_then_reuse) {
176 test_pool mem; 182 test_pool mem;
177 mempool_make(&mem); 183 mempool_make(&mem);
178 184
179 // Allocate chunks, contents not important. 185 // Allocate chunks, contents not important.
180 for (int i = 0; i < NUM_BLOCKS; ++i) { 186 for (int i = 0; i < NUM_BLOCKS; ++i) {
181 int* chunk = mempool_alloc(&mem); 187 const int* chunk = mempool_alloc(&mem);
182 TEST_TRUE(chunk != 0); 188 TEST_TRUE(chunk != nullptr);
183 } 189 }
184 190
185 mempool_clear(&mem); 191 mempool_clear(&mem);
192 TEST_EQUAL(mempool_size(&mem), 0);
193 TEST_EQUAL(mempool_capacity(&mem), NUM_BLOCKS);
186 194
187 // Allocate chunks and assign values 0..N. 195 // Allocate chunks and assign values 0..N.
188 for (int i = 0; i < NUM_BLOCKS; ++i) { 196 for (int i = 0; i < NUM_BLOCKS; ++i) {
189 int* chunk = mempool_alloc(&mem); 197 int* chunk = mempool_alloc(&mem);
190 TEST_TRUE(chunk != 0); 198 TEST_TRUE(chunk != nullptr);
191 *chunk = i + 1; 199 *chunk = i + 1;
192 } 200 }
193 201
diff --git a/memstack/CMakeLists.txt b/memstack/CMakeLists.txt
new file mode 100644
index 0000000..6846e87
--- /dev/null
+++ b/memstack/CMakeLists.txt
@@ -0,0 +1,30 @@
1cmake_minimum_required(VERSION 3.5)
2
3project(memstack)
4
5set(CMAKE_C_STANDARD 23)
6set(CMAKE_C_STANDARD_REQUIRED On)
7set(CMAKE_C_EXTENSIONS Off)
8
9# Library
10
11add_library(memstack
12 src/memstack.c)
13
14target_include_directories(memstack PUBLIC
15 include)
16
17target_link_libraries(memstack PRIVATE
18 cassert)
19
20target_compile_options(memstack PRIVATE -Wall -Wextra -Wpedantic)
21
22# Test
23
24add_executable(memstack_test
25 test/memstack_test.c)
26
27target_link_libraries(memstack_test
28 memstack)
29
30target_compile_options(memstack_test PRIVATE -DUNIT_TEST -DNDEBUG -Wall -Wextra -Wpedantic)
diff --git a/memstack/README.md b/memstack/README.md
new file mode 100644
index 0000000..7eb950e
--- /dev/null
+++ b/memstack/README.md
@@ -0,0 +1,15 @@
1# Mempool
2
3A memory pool of fixed-sized blocks with O(1) allocation and deallocation.
4
5Each block in the pool is tagged with a boolean value that indicates whether the
6block is free or in use, as well as a pointer to the next free/used block.
7Blocks thus form two lists, a free list and a used list. The allocator
8maintains the two lists when allocating/deallocating blocks.
9
10The allocator's internal data is stored separately from the block data so that
11the data remains tightly packed.
12
13Free blocks in the mempool always remain zeroed out for convenience of
14programming and debugging. If the application's data structures are valid when
15zeroed out, then they do not need to be explicitly initialized.
diff --git a/memstack/include/memstack.h b/memstack/include/memstack.h
new file mode 100644
index 0000000..93cd2e6
--- /dev/null
+++ b/memstack/include/memstack.h
@@ -0,0 +1,66 @@
1/*
2 * Stack-based allocator.
3 */
4#pragma once
5
6#include <stddef.h>
7#include <stdint.h>
8
9/// Stack-based allocator.
10typedef struct memstack {
11 size_t capacity; // Total size available.
12 uint8_t* base; // Base pointer to memory.
13 uint8_t* watermark; // Pointer to next free area of memory.
14 bool owned; // True if memory is owned by the memstack.
15 bool trap; // Whether to trap when allocating beyond capacity.
16} memstack;
17
18/// Create a stack-based allocator.
19///
20/// `stack` may be user-provided or null.
21/// - If null, the allocator malloc()s the memory for them.
22/// - If given, `stack` must be at least `capacity` bytes.
23///
24/// The memory is zeroed out for convenience.
25bool memstack_make(memstack*, size_t capacity, void* memory);
26
27/// Destroy the stack.
28///
29/// If the allocator owns the memory, then this function frees it.
30void memstack_del(memstack*);
31
32/// Clear the stack.
33void memstack_clear(memstack*);
34
35/// Return the top of the stack.
36size_t memstack_watermark(const memstack*);
37
38/// Set the top of the stack.
39void memstack_set_watermark(memstack*, size_t watermark);
40
41/// Allocate a new block.
42///
43/// Return null if the block does not fit in the remaining memory.
44///
45/// When there is no space left in the stack, allocation can either trap
46/// (default) or gracefully return null. Call mem_enable_traps() to toggle this
47/// behaviour.
48///
49/// Newly allocated blocks are conveniently zeroed out.
50void* memstack_alloc(memstack*, size_t bytes);
51
52/// Allocate a new aligned block.
53///
54/// An alignment of 0 is allowed for convenience and has the same effect as 1.
55///
56/// Has the same properties as memstack_alloc().
57void* memstack_alloc_aligned(memstack*, size_t bytes, size_t alignment);
58
59/// Return the stack's used size in bytes.
60size_t memstack_size(const memstack*);
61
62/// Return the stack's total capacity in bytes.
63size_t memstack_capacity(const memstack*);
64
65/// Set whether to trap when attempting to allocate beyond capacity.
66void memstack_enable_traps(memstack*, bool);
diff --git a/memstack/src/memstack.c b/memstack/src/memstack.c
new file mode 100644
index 0000000..84131ef
--- /dev/null
+++ b/memstack/src/memstack.c
@@ -0,0 +1,119 @@
1#include "memstack.h"
2
3#include <cassert.h>
4
5#include <stdlib.h>
6#include <string.h>
7
8static bool is_pow2_or_0(size_t x) { return (x & (x - 1)) == 0; }
9
10/// Align the given address to the next address that is a multiple of the
11/// alignment. If the given address is already aligned, return the address.
12static uint8_t* align(uint8_t* address, size_t alignment) {
13 assert(is_pow2_or_0(alignment));
14 const size_t mask = alignment - 1;
15 return (uint8_t*)(((uintptr_t)address + mask) & ~mask);
16}
17
18bool memstack_make(memstack* stack, size_t capacity, void* memory) {
19 assert(stack);
20 assert(capacity >= 1);
21
22 // Allocate memory if not user-provided.
23 uint8_t* stack_memory = memory;
24 if (!stack_memory) {
25 stack_memory = calloc(1, capacity);
26 if (stack_memory == nullptr) {
27 return false;
28 }
29 }
30 assert(stack_memory);
31
32 stack->capacity = capacity;
33 stack->base = stack_memory;
34 stack->watermark = stack_memory;
35 stack->owned = (stack_memory != memory);
36 stack->trap = true;
37
38 return true;
39}
40
41void memstack_del(memstack* stack) {
42 assert(stack);
43
44 if (stack->owned && (stack->base != nullptr)) {
45 free(stack->base);
46 stack->base = nullptr;
47 stack->owned = false;
48 }
49
50 stack->capacity = 0;
51 stack->watermark = stack->base;
52}
53
54void memstack_clear(memstack* stack) {
55 assert(stack);
56
57 stack->watermark = stack->base;
58 memset(stack->base, 0, stack->capacity);
59}
60
61size_t memstack_watermark(const memstack* stack) {
62 assert(stack);
63 return stack->watermark - stack->base;
64}
65
66void memstack_set_watermark(memstack* stack, size_t watermark) {
67 assert(stack);
68 const bool fits = (watermark < stack->capacity);
69 if (stack->trap && !fits) {
70 FAIL("memstack watermark update failed, bad watermark");
71 }
72 assert(fits);
73 stack->watermark = stack->base + watermark;
74}
75
76void* memstack_alloc(memstack* stack, size_t bytes) {
77 assert(stack);
78
79 if ((memstack_size(stack) + bytes) > stack->capacity) {
80 if (stack->trap) {
81 FAIL("memstack allocation failed, increase the stack's capacity.");
82 }
83 return nullptr; // Block does not fit in remaining memory.
84 }
85
86 // Allocate the block.
87 uint8_t* const block = stack->watermark;
88 stack->watermark += bytes;
89 assert(memstack_size(stack) <= stack->capacity);
90
91 return block;
92}
93
94void* memstack_alloc_aligned(memstack* stack, size_t bytes, size_t alignment) {
95 assert(stack);
96
97 uint8_t* const new_watermark = align(stack->watermark, alignment);
98 assert(new_watermark >= stack->watermark);
99 assert((size_t)(new_watermark - stack->base) <= stack->capacity);
100 stack->capacity -= (new_watermark - stack->watermark);
101 stack->watermark = new_watermark;
102
103 return memstack_alloc(stack, bytes);
104}
105
106size_t memstack_size(const memstack* stack) {
107 assert(stack);
108 return stack->watermark - stack->base;
109}
110
111size_t memstack_capacity(const memstack* stack) {
112 assert(stack);
113 return stack->capacity;
114}
115
116void memstack_enable_traps(memstack* stack, bool enable) {
117 assert(stack);
118 stack->trap = enable;
119}
diff --git a/memstack/test/memstack_test.c b/memstack/test/memstack_test.c
new file mode 100644
index 0000000..2bcffcd
--- /dev/null
+++ b/memstack/test/memstack_test.c
@@ -0,0 +1,171 @@
1#include "memstack.h"
2
3#include "test.h"
4
5#define NUM_INTS 10
6#define CAPACITY (NUM_INTS * sizeof(int))
7
8// Create and destroy a statically-backed stack.
9TEST_CASE(memstack_create) {
10 int memory[CAPACITY];
11
12 memstack stack = {0};
13 memstack_make(&stack, CAPACITY, memory);
14 memstack_del(&stack);
15}
16
17// Create and destroy a dynamically-backed stack.
18TEST_CASE(memstack_create_dyn) {
19 memstack stack = {0};
20 memstack_make(&stack, CAPACITY, nullptr);
21 memstack_del(&stack);
22}
23
24// Clear an uninitialized stack.
25TEST_CASE(memstack_clear_uninitialized) {
26 memstack stack = {0};
27 memstack_clear(&stack);
28}
29
30// Allocate all N ints.
31TEST_CASE(memstack_allocate_until_full) {
32 memstack stack = {0};
33 memstack_make(&stack, CAPACITY, nullptr);
34
35 for (int i = 0; i < NUM_INTS; ++i) {
36 const int* block = memstack_alloc(&stack, sizeof(int));
37 TEST_TRUE(block != nullptr);
38 }
39
40 TEST_TRUE(memstack_size(&stack) == CAPACITY);
41
42 memstack_del(&stack);
43}
44
45// Allocate all N ints, then free them.
46TEST_CASE(memstack_fill_then_free) {
47 memstack stack = {0};
48 memstack_make(&stack, CAPACITY, nullptr);
49
50 int* blocks[NUM_INTS] = {nullptr};
51 for (int i = 0; i < NUM_INTS; ++i) {
52 blocks[i] = memstack_alloc(&stack, sizeof(int));
53 TEST_TRUE(blocks[i] != nullptr);
54 }
55
56 memstack_clear(&stack);
57
58 TEST_EQUAL(memstack_size(&stack), 0);
59
60 memstack_del(&stack);
61}
62
63// Attempt to allocate blocks past the maximum stack size.
64// The stack should handle the failed allocations gracefully.
65TEST_CASE(memstack_allocate_beyond_max_size) {
66 memstack stack = {0};
67 memstack_make(&stack, CAPACITY, nullptr);
68 memstack_enable_traps(&stack, false);
69
70 // Fully allocate the stack.
71 for (int i = 0; i < NUM_INTS; ++i) {
72 TEST_TRUE(memstack_alloc(&stack, sizeof(int)) != nullptr);
73 }
74
75 // Past the end.
76 for (int i = 0; i < NUM_INTS; ++i) {
77 TEST_EQUAL(memstack_alloc(&stack, sizeof(int)), nullptr);
78 }
79
80 TEST_TRUE(memstack_size(&stack) == CAPACITY);
81
82 memstack_del(&stack);
83}
84
85// Free blocks should always remain zeroed out.
86// This tests the invariant right after creating the stack.
87TEST_CASE(memstack_zero_free_blocks_after_creation) {
88 memstack stack = {0};
89 memstack_make(&stack, CAPACITY, nullptr);
90
91 for (int i = 0; i < NUM_INTS; ++i) {
92 const int* block = memstack_alloc(&stack, sizeof(int));
93 TEST_TRUE(block != nullptr);
94 TEST_EQUAL(*block, 0);
95 }
96
97 memstack_del(&stack);
98}
99
100// Free blocks should always remain zeroed out.
101// This tests the invariant after clearing the stack and allocating a new block.
102TEST_CASE(memstack_zero_free_block_after_free) {
103 memstack stack = {0};
104 memstack_make(&stack, CAPACITY, nullptr);
105
106 for (int i = 0; i < NUM_INTS; ++i) {
107 const int* block = memstack_alloc(&stack, sizeof(int));
108 TEST_TRUE(block != nullptr);
109 TEST_EQUAL(*block, 0);
110 }
111
112 memstack_clear(&stack);
113
114 for (int i = 0; i < NUM_INTS; ++i) {
115 const int* block = memstack_alloc(&stack, sizeof(int));
116 TEST_TRUE(block != nullptr);
117 TEST_EQUAL(*block, 0);
118 }
119
120 memstack_del(&stack);
121}
122
123// Aligned allocations should be properly aligned.
124TEST_CASE(memstack_alloc_aligned) {
125 memstack stack = {0};
126 memstack_make(&stack, CAPACITY, nullptr);
127
128 // -1 because the base address of the memory storage might be unaligned.
129 for (int i = 0; i < NUM_INTS - 1; ++i) {
130 const int* block =
131 memstack_alloc_aligned(&stack, sizeof(int), alignof(int));
132 TEST_TRUE(block != nullptr);
133 TEST_EQUAL(*block, 0);
134 TEST_EQUAL((uintptr_t)block % alignof(int), 0);
135 }
136
137 memstack_del(&stack);
138}
139
140// Get and set the watermark.
141TEST_CASE(memstack_watermark) {
142 memstack stack = {0};
143 memstack_make(&stack, CAPACITY, nullptr);
144
145 // Allocate N/2 ints.
146 for (int i = 0; i < NUM_INTS / 2; ++i) {
147 const int* block = memstack_alloc(&stack, sizeof(int));
148 TEST_TRUE(block != nullptr);
149 }
150
151 const size_t watermark = memstack_watermark(&stack);
152
153 // Allocate the remaining N/2 ints.
154 for (int i = 0; i < NUM_INTS / 2; ++i) {
155 const int* block = memstack_alloc(&stack, sizeof(int));
156 TEST_TRUE(block != nullptr);
157 }
158
159 // Now reset the watermark halfway through.
160 memstack_set_watermark(&stack, watermark);
161
162 // Allocate the remaining N/2 ints (again).
163 for (int i = 0; i < NUM_INTS / 2; ++i) {
164 const int* block = memstack_alloc(&stack, sizeof(int));
165 TEST_TRUE(block != nullptr);
166 }
167
168 memstack_del(&stack);
169}
170
171int main() { return 0; }
diff --git a/memstack/test/test.h b/memstack/test/test.h
new file mode 100644
index 0000000..fd8dc22
--- /dev/null
+++ b/memstack/test/test.h
@@ -0,0 +1,185 @@
1// SPDX-License-Identifier: MIT
2#pragma once
3
4#ifdef UNIT_TEST
5
6#include <stdbool.h>
7#include <stdio.h>
8#include <stdlib.h>
9#include <string.h>
10
11#if defined(__DragonFly__) || defined(__FreeBSD__) || defined(__FreeBSD_kernel__) || \
12 defined(__NetBSD__) || defined(__OpenBSD__)
13#define USE_SYSCTL_FOR_ARGS 1
14// clang-format off
15#include <sys/types.h>
16#include <sys/sysctl.h>
17// clang-format on
18#include <unistd.h> // getpid
19#endif
20
21struct test_file_metadata;
22
23struct test_failure {
24 bool present;
25 const char *message;
26 const char *file;
27 int line;
28};
29
30struct test_case_metadata {
31 void (*fn)(struct test_case_metadata *, struct test_file_metadata *);
32 struct test_failure failure;
33 const char *name;
34 struct test_case_metadata *next;
35};
36
37struct test_file_metadata {
38 bool registered;
39 const char *name;
40 struct test_file_metadata *next;
41 struct test_case_metadata *tests;
42};
43
44struct test_file_metadata __attribute__((weak)) * test_file_head;
45
46#define SET_FAILURE(_message) \
47 metadata->failure = (struct test_failure) { \
48 .message = _message, .file = __FILE__, .line = __LINE__, .present = true, \
49 }
50
51#define TEST_EQUAL(a, b) \
52 do { \
53 if ((a) != (b)) { \
54 SET_FAILURE(#a " != " #b); \
55 return; \
56 } \
57 } while (0)
58
59#define TEST_TRUE(a) \
60 do { \
61 if (!(a)) { \
62 SET_FAILURE(#a " is not true"); \
63 return; \
64 } \
65 } while (0)
66
67#define TEST_STREQUAL(a, b) \
68 do { \
69 if (strcmp(a, b) != 0) { \
70 SET_FAILURE(#a " != " #b); \
71 return; \
72 } \
73 } while (0)
74
75#define TEST_CASE(_name) \
76 static void __test_h_##_name(struct test_case_metadata *, \
77 struct test_file_metadata *); \
78 static struct test_file_metadata __test_h_file; \
79 static struct test_case_metadata __test_h_meta_##_name = { \
80 .name = #_name, \
81 .fn = __test_h_##_name, \
82 }; \
83 static void __attribute__((constructor(101))) __test_h_##_name##_register(void) { \
84 __test_h_meta_##_name.next = __test_h_file.tests; \
85 __test_h_file.tests = &__test_h_meta_##_name; \
86 if (!__test_h_file.registered) { \
87 __test_h_file.name = __FILE__; \
88 __test_h_file.next = test_file_head; \
89 test_file_head = &__test_h_file; \
90 __test_h_file.registered = true; \
91 } \
92 } \
93 static void __test_h_##_name( \
94 struct test_case_metadata *metadata __attribute__((unused)), \
95 struct test_file_metadata *file_metadata __attribute__((unused)))
96
97extern void __attribute__((weak)) (*test_h_unittest_setup)(void);
98/// Run defined tests, return true if all tests succeeds
99/// @param[out] tests_run if not NULL, set to whether tests were run
100static inline void __attribute__((constructor(102))) run_tests(void) {
101 bool should_run = false;
102#ifdef USE_SYSCTL_FOR_ARGS
103 int mib[] = {
104 CTL_KERN,
105#if defined(__NetBSD__) || defined(__OpenBSD__)
106 KERN_PROC_ARGS,
107 getpid(),
108 KERN_PROC_ARGV,
109#else
110 KERN_PROC,
111 KERN_PROC_ARGS,
112 getpid(),
113#endif
114 };
115 char *arg = NULL;
116 size_t arglen;
117 sysctl(mib, sizeof(mib) / sizeof(mib[0]), NULL, &arglen, NULL, 0);
118 arg = malloc(arglen);
119 sysctl(mib, sizeof(mib) / sizeof(mib[0]), arg, &arglen, NULL, 0);
120#else
121 FILE *cmdlinef = fopen("/proc/self/cmdline", "r");
122 char *arg = NULL;
123 int arglen;
124 fscanf(cmdlinef, "%ms%n", &arg, &arglen);
125 fclose(cmdlinef);
126#endif
127 for (char *pos = arg; pos < arg + arglen; pos += strlen(pos) + 1) {
128 if (strcmp(pos, "--unittest") == 0) {
129 should_run = true;
130 break;
131 }
132 }
133 free(arg);
134
135 if (!should_run) {
136 return;
137 }
138
139 if (&test_h_unittest_setup) {
140 test_h_unittest_setup();
141 }
142
143 struct test_file_metadata *i = test_file_head;
144 int failed = 0, success = 0;
145 while (i) {
146 fprintf(stderr, "Running tests from %s:\n", i->name);
147 struct test_case_metadata *j = i->tests;
148 while (j) {
149 fprintf(stderr, "\t%s ... ", j->name);
150 j->failure.present = false;
151 j->fn(j, i);
152 if (j->failure.present) {
153 fprintf(stderr, "failed (%s at %s:%d)\n", j->failure.message,
154 j->failure.file, j->failure.line);
155 failed++;
156 } else {
157 fprintf(stderr, "passed\n");
158 success++;
159 }
160 j = j->next;
161 }
162 fprintf(stderr, "\n");
163 i = i->next;
164 }
165 int total = failed + success;
166 fprintf(stderr, "Test results: passed %d/%d, failed %d/%d\n", success, total,
167 failed, total);
168 exit(failed == 0 ? EXIT_SUCCESS : EXIT_FAILURE);
169}
170
171#else
172
173#include <stdbool.h>
174
175#define TEST_CASE(name) static void __attribute__((unused)) __test_h_##name(void)
176
177#define TEST_EQUAL(a, b) \
178 (void)(a); \
179 (void)(b)
180#define TEST_TRUE(a) (void)(a)
181#define TEST_STREQUAL(a, b) \
182 (void)(a); \
183 (void)(b)
184
185#endif
diff --git a/plugin/CMakeLists.txt b/plugin/CMakeLists.txt
index 2c34228..c132c0a 100644
--- a/plugin/CMakeLists.txt
+++ b/plugin/CMakeLists.txt
@@ -19,20 +19,20 @@ target_link_libraries(plugin PRIVATE
19 list 19 list
20 log) 20 log)
21 21
22target_compile_options(plugin PRIVATE -Wall -Wextra) 22target_compile_options(plugin PRIVATE -Wall -Wextra -Wpedantic)
23 23
24# Test 24# Test
25 25
26add_library(hello_plugin SHARED 26add_library(hello_plugin SHARED
27 test/hello_plugin.c) 27 test/hello_plugin.c)
28 28
29target_compile_options(hello_plugin PRIVATE -Wall -Wextra) 29target_compile_options(hello_plugin PRIVATE -Wall -Wextra -Wpedantic)
30 30
31add_executable(plugin_test 31add_executable(plugin_test
32 test/plugin_test.c) 32 test/plugin_test.c)
33 33
34target_link_libraries(plugin_test 34target_link_libraries(plugin_test
35 plugin 35 plugin
36 test) 36 ctest)
37 37
38target_compile_options(plugin_test PRIVATE -DUNIT_TEST -DNDEBUG -Wall -Wextra) 38target_compile_options(plugin_test PRIVATE -DUNIT_TEST -DNDEBUG -Wall -Wextra -Wpedantic)
diff --git a/plugin/src/plugin.c b/plugin/src/plugin.c
index e2aae1f..3a0ef5d 100644
--- a/plugin/src/plugin.c
+++ b/plugin/src/plugin.c
@@ -64,14 +64,14 @@ static bool load_library(Plugin* plugin) {
64 // Handle reloading a previously-loaded library. 64 // Handle reloading a previously-loaded library.
65 if (plugin->handle) { 65 if (plugin->handle) {
66 dlclose(plugin->handle); 66 dlclose(plugin->handle);
67 plugin->handle = 0; 67 plugin->handle = nullptr;
68 } 68 }
69 69
70 const mstring lib = plugin_lib_path(plugin); 70 const mstring lib = plugin_lib_path(plugin);
71 71
72 // If the plugin fails to load, make sure to keep the plugin's old handle to 72 // If the plugin fails to load, make sure to keep the plugin's old handle to
73 // handle the error gracefully. This handles reload failures, specifically. 73 // handle the error gracefully. This handles reload failures, specifically.
74 void* handle = 0; 74 void* handle = nullptr;
75 if ((handle = dlopen(mstring_cstr(&lib), RTLD_NOW))) { 75 if ((handle = dlopen(mstring_cstr(&lib), RTLD_NOW))) {
76 LOGD("Plugin [%s] loaded successfully", mstring_cstr(&plugin->filename)); 76 LOGD("Plugin [%s] loaded successfully", mstring_cstr(&plugin->filename));
77 plugin->handle = handle; 77 plugin->handle = handle;
@@ -86,7 +86,7 @@ static bool load_library(Plugin* plugin) {
86static void delete_plugin_state(Plugin* plugin) { 86static void delete_plugin_state(Plugin* plugin) {
87 if (plugin->state) { 87 if (plugin->state) {
88 free(plugin->state); 88 free(plugin->state);
89 plugin->state = 0; 89 plugin->state = nullptr;
90 } 90 }
91} 91}
92 92
@@ -105,7 +105,7 @@ static void destroy_plugin(Plugin* plugin) {
105 if (plugin) { 105 if (plugin) {
106 if (plugin->handle) { 106 if (plugin->handle) {
107 dlclose(plugin->handle); 107 dlclose(plugin->handle);
108 plugin->handle = 0; 108 plugin->handle = nullptr;
109 } 109 }
110 delete_plugin_state(plugin); 110 delete_plugin_state(plugin);
111 } 111 }
@@ -118,7 +118,7 @@ Plugin* load_plugin(PluginEngine* eng, const char* filename) {
118 Plugin plugin = (Plugin){.eng = eng, .filename = mstring_make(filename)}; 118 Plugin plugin = (Plugin){.eng = eng, .filename = mstring_make(filename)};
119 119
120 if (!load_library(&plugin)) { 120 if (!load_library(&plugin)) {
121 return 0; 121 return nullptr;
122 } 122 }
123 123
124 list_add(eng->plugins, plugin); 124 list_add(eng->plugins, plugin);
@@ -132,7 +132,7 @@ void delete_plugin(Plugin** pPlugin) {
132 assert(plugin->eng); 132 assert(plugin->eng);
133 destroy_plugin(plugin); 133 destroy_plugin(plugin);
134 list_remove_ptr(plugin->eng->plugins, plugin); 134 list_remove_ptr(plugin->eng->plugins, plugin);
135 *pPlugin = 0; 135 *pPlugin = nullptr;
136 } 136 }
137} 137}
138 138
@@ -148,7 +148,7 @@ bool plugin_reloaded(Plugin* plugin) {
148// ----------------------------------------------------------------------------- 148// -----------------------------------------------------------------------------
149 149
150PluginEngine* new_plugin_engine(const PluginEngineDesc* desc) { 150PluginEngine* new_plugin_engine(const PluginEngineDesc* desc) {
151 PluginEngine* eng = 0; 151 PluginEngine* eng = nullptr;
152 152
153 if (!(eng = calloc(1, sizeof(PluginEngine)))) { 153 if (!(eng = calloc(1, sizeof(PluginEngine)))) {
154 goto cleanup; 154 goto cleanup;
@@ -173,7 +173,7 @@ PluginEngine* new_plugin_engine(const PluginEngineDesc* desc) {
173 173
174cleanup: 174cleanup:
175 delete_plugin_engine(&eng); 175 delete_plugin_engine(&eng);
176 return 0; 176 return nullptr;
177} 177}
178 178
179void delete_plugin_engine(PluginEngine** pEng) { 179void delete_plugin_engine(PluginEngine** pEng) {
@@ -191,7 +191,7 @@ void delete_plugin_engine(PluginEngine** pEng) {
191 close(eng->inotify_instance); 191 close(eng->inotify_instance);
192 } 192 }
193 free(eng); 193 free(eng);
194 *pEng = 0; 194 *pEng = nullptr;
195 } 195 }
196} 196}
197 197
diff --git a/random/CMakeLists.txt b/random/CMakeLists.txt
index 3c4b2dc..c759ef8 100644
--- a/random/CMakeLists.txt
+++ b/random/CMakeLists.txt
@@ -12,4 +12,4 @@ add_library(random
12 12
13target_include_directories(random PUBLIC include) 13target_include_directories(random PUBLIC include)
14 14
15target_compile_options(random PRIVATE -Wall -Wextra) 15target_compile_options(random PRIVATE -Wall -Wextra -Wpedantic)
diff --git a/simloop/CMakeLists.txt b/simloop/CMakeLists.txt
new file mode 100644
index 0000000..2e0114b
--- /dev/null
+++ b/simloop/CMakeLists.txt
@@ -0,0 +1,29 @@
1cmake_minimum_required(VERSION 3.5)
2
3project(simloop)
4
5set(CMAKE_C_STANDARD 23)
6set(CMAKE_C_STANDARD_REQUIRED On)
7set(CMAKE_C_EXTENSIONS Off)
8
9add_library(simloop
10 include/simloop.h
11 src/simloop.c)
12
13target_include_directories(simloop PUBLIC
14 include)
15
16target_compile_options(simloop PRIVATE -Wall -Wextra -Wpedantic)
17
18# Test
19
20add_executable(simloop_test
21 test/simloop_test.c)
22
23target_link_libraries(simloop_test
24 simloop
25 ctest)
26
27target_compile_options(simloop_test PRIVATE -DUNIT_TEST -DNDEBUG -Wall -Wextra -pedantic)
28
29add_test(NAME simloop_test COMMAND simloop_test --unittest)
diff --git a/simloop/README.md b/simloop/README.md
new file mode 100644
index 0000000..f45ca05
--- /dev/null
+++ b/simloop/README.md
@@ -0,0 +1,99 @@
1# Simulation loop module
2
3Simulation loop for games and graphics applications.
4
5## Features
6
7- Client retains control flow.
8- Client-controlled time axis.
9- Updates are frame-rate capped and use a fixed time step for determinism.
10- Rendering is optionally frame-rate capped.
11- Interpolation factor for smooth animation and rendering between frames.
12
13Control flow: the client steps the loop and then checks whether the simulation
14must be updated and/or the result rendered. Time readings are external to the
15library and provided by the client.
16
17## Invariants
18
19- An initial render of the initial application state is always triggered.
20- The same frame is not re-rendered if time does not advance.
21- Animation interpolation factor in [0,1].
22
23## Handling Time Spikes
24
25Generally, the simulation's update logic should be able to keep up with the
26requested frame rate; it is the application's responsibility to ensure this.
27Specifically, the frequency with which the application loops must be higher
28than the requested update frequency, given by the update delta time.
29
30However, occasional time spikes may occur, for example when switching to the
31desktop or when pausing the application in a debugger. The library handles this
32simply by requesting an update from the application. Under the assumption that
33the loop frequency is higher than the update frequency, the simulation will
34catch up with the real-time clock.
35
36### Time Spikes in Detail
37
38When a time spike occurs, the simulation clock falls significantly behind the
39real-time clock. Ideally, the simulation should be able to recover and catch up
40to the real-time clock when this occurs.
41
42Under a variable time delta, the loop could simply update the simulation with
43a large delta that puts the simulation back into the current clock time.
44Under a fixed time delta, this isn't possible, and we seem to have the
45following choices instead:
46
47- a) Queue as many updates as necessary to bring the simulation back to the
48 current clock time (time_difference / fixed_delta).
49- b) Queue a single update.
50- c) Some middle ground between the two.
51
52The issue with (a) is that, if the simulation is never able to catch up, then
53the number of requested updates at every loop iteration diverges and the
54simulation eventually appears to freeze.
55
56(b) only works if:
57
58- clock time added per iter < desired update delta time
59
60Where:
61
62- clock time added per iter = update time + render time + vsync + etc
63- desired delta time = 1 / update frequency
64
65If the clock time added per iteration is greater or equal to the desired delta,
66then the simulation can never "catch up" and recover from the spike.
67
68The middle ground is to perform only some number of updates in each loop
69iteration N. The simulation catches up only if:
70
71- clock time added per iter < N * desired update delta time
72
73The ideal value of N depends on how many frames the application can actually
74render. For example, if the application is vsync'ed to a 240hz monitor and is
75able to render that many frames, then:
76
77- N = ceil(1/240hz / desired update delta time)
78
79Realistically, the actual frame rate will be variable. Moreover, if we queued
80as many frames as possible, then we would risk the freeze in option (a) if the
81actual update time were too large for the application to catch up. So the
82library can only guess the value of N.
83
84The library picks a small constant value of N, implementation-defined, that the
85application can override.
86
87### Example: Spike Handling with Option (A)
88
89- desired delta = 10ms (100 fps)
90- actual delta = 20ms ( 50 fps)
91
92| iter | sim time | clock time | comment |
93|------|----------|------------|-------------------------------|
94| 0 | 0 | 0 | initial state |
95| 1 | 0 | 10 | queue 1 update |
96| 2 | 10 | 30 | queue (30-10)/10 = 2 updates |
97| 3 | 30 | 70 | queue (70-30)/10 = 4 updates |
98| 4 | 70 | 150 | queue (150-70)/10 = 8 updates |
99| ... |
diff --git a/simloop/include/simloop.h b/simloop/include/simloop.h
new file mode 100644
index 0000000..6a83b23
--- /dev/null
+++ b/simloop/include/simloop.h
@@ -0,0 +1,40 @@
1#pragma once
2
3#include <stdint.h>
4
5typedef uint64_t simloop_time_t; ///< Time delta in nanoseconds.
6
7typedef struct SimloopArgs {
8 int update_fps; ///< Update frame rate. Must be >0.
9 int max_render_fps; ///< Render frame rate cap. 0 to disable.
10} SimloopArgs;
11
12typedef struct SimloopOut {
13 uint64_t frame; ///< Frame counter.
14 simloop_time_t update_elapsed; ///< Amount of time elapsed in the simulation.
15 simloop_time_t update_dt; ///< Delta time for simulation updates.
16 simloop_time_t throttle; ///< Render throttle if max render fps is given.
17 double percent_frame; ///< Percent progress between this frame and
18 ///< the next. Used for smooth animation.
19 bool should_update; ///< Whether the simulation should update.
20} SimloopOut;
21
22typedef struct SimloopTimeline {
23 simloop_time_t ddt; ///< Desired delta time.
24 simloop_time_t time; ///< Time point of the last simulation step.
25} SimloopTimeline;
26
27typedef struct Simloop {
28 simloop_time_t clock; ///< Tracks simulation time.
29 uint64_t frame; ///< Frame counter, number of updates done.
30 SimloopTimeline update; ///< Update timeline.
31 simloop_time_t render_ddt; ///< Desired render delta time.
32} Simloop;
33
34/// Create a simulation loop.
35Simloop simloop_make(const SimloopArgs*);
36
37/// Step the simulation loop.
38///
39/// The simulation always triggers a render of the initial state of simulation.
40void simloop_update(Simloop*, simloop_time_t dt, SimloopOut*);
diff --git a/simloop/src/simloop.c b/simloop/src/simloop.c
new file mode 100644
index 0000000..4fa5f62
--- /dev/null
+++ b/simloop/src/simloop.c
@@ -0,0 +1,78 @@
1#include <simloop.h>
2
3#include <assert.h>
4
5static double min(double a, double b) { return a <= b ? a : b; }
6
7static simloop_time_t ddt_from_fps(int fps) {
8 static constexpr double NANOSECONDS = 1e9;
9 return (fps == 0) ? 0 : (simloop_time_t)(NANOSECONDS / (double)fps);
10}
11
12Simloop simloop_make(const SimloopArgs* args) {
13 assert(args);
14 assert(args->update_fps > 0);
15
16 return (Simloop){
17 .frame = 0,
18 .update =
19 (SimloopTimeline){
20 .ddt = ddt_from_fps(args->update_fps),
21 .time = 0,
22 },
23 .render_ddt = ddt_from_fps(args->max_render_fps),
24 };
25}
26
27void simloop_update(Simloop* sim, simloop_time_t dt, SimloopOut* out) {
28 assert(sim);
29 assert(out);
30
31 sim->clock += dt;
32
33 // Simulation update.
34 // If the simulation falls behind the clock, we advance by a single ddt
35 // increment per loop iteration here and give it a chance to catch up over
36 // subsequent iterations.
37 // This has the implication that percent_frame can fall out of range (>1) if
38 // we are not careful with how it is defined. See the logic below.
39 // If the delta is too large, then we simply warp the simulation to the wall
40 // clock. This avoids the appearance of the simulation playing in fast-forward
41 // as it tries to catch up. Large time spikes can typically occur at the start
42 // of the simulation when the application loads assets, compiles shaders, etc.
43 static const uint64_t max_catchup_frames = 10;
44 const simloop_time_t delta = sim->clock - sim->update.time;
45 const uint64_t delta_frames = delta / sim->update.ddt;
46 const bool update_this_tick = delta >= sim->update.ddt;
47 const bool warp = delta_frames > max_catchup_frames;
48 sim->update.time =
49 warp ? sim->clock
50 : (sim->update.time + (update_this_tick ? sim->update.ddt : 0));
51
52 // Loop-state update.
53 sim->frame += (update_this_tick ? 1 : 0);
54
55 // Interpolator for smooth animation.
56 // If the update falls behind the clock, then percent_frame can fall out of
57 // range (>1) if we are not careful. We impose that it is strictly never >1
58 // to account for this case.
59 assert(sim->update.ddt > 0);
60 assert(sim->update.time <= sim->clock);
61 out->percent_frame = min(
62 1., (double)(sim->clock - sim->update.time) / (double)sim->update.ddt);
63 assert((0. <= out->percent_frame) && (out->percent_frame <= 1.));
64
65 // Render frame rate throttle.
66 // Note that if no max render fps is given, then render_ddt is 0. The logic
67 // works for both render_ddt>0 and =0.
68 // Need to be careful with subtraction since the quantities are unsigned.
69 // Subtract an epsilon to account for delays in thread scheduling.
70 static const simloop_time_t eps = 50'000; // 50us
71 out->throttle =
72 (sim->render_ddt > (dt - eps)) ? (sim->render_ddt - eps - dt) : 0;
73
74 out->frame = sim->frame;
75 out->update_elapsed = sim->update.time;
76 out->update_dt = sim->update.ddt;
77 out->should_update = update_this_tick;
78}
diff --git a/simloop/test/simloop_test.c b/simloop/test/simloop_test.c
new file mode 100644
index 0000000..bcf9d57
--- /dev/null
+++ b/simloop/test/simloop_test.c
@@ -0,0 +1,306 @@
1#include <simloop.h>
2
3#include <test.h>
4
5#include <stdint.h>
6
7// -----------------------------------------------------------------------------
8// Time.
9
10static simloop_time_t time_delta_from_sec(double seconds) {
11 static constexpr double NANOS_PER_SEC = 1e9;
12 return (simloop_time_t)(seconds * NANOS_PER_SEC);
13}
14
15// -----------------------------------------------------------------------------
16// Randomness.
17
18typedef struct {
19 uint64_t a;
20} XorShift64State;
21
22static uint64_t xorshift64(XorShift64State* state) {
23 uint64_t x = state->a;
24 x ^= x << 7;
25 x ^= x >> 9;
26 return state->a = x;
27}
28
29// -----------------------------------------------------------------------------
30// Tests.
31
32/// At time/frame 0, no update is triggered (not enough time passed).
33TEST_CASE(simloop_initial_render) {
34 Simloop simloop = simloop_make(&(SimloopArgs){.update_fps = 10});
35 SimloopOut simout;
36
37 simloop_update(&simloop, 0, &simout);
38
39 TEST_TRUE(!simout.should_update);
40 TEST_EQUAL(simout.frame, 0);
41}
42
43/// The simulation is not updated if time does not advance.
44/// This applies generally to any time > 0.
45TEST_CASE(simloop_render_not_retriggered) {
46 Simloop simloop = simloop_make(&(SimloopArgs){.update_fps = 10});
47 SimloopOut simout;
48
49 // Advance time by some amount to get past t=0.
50 simloop_update(&simloop, 1, &simout);
51
52 // Now "advance" by 0.
53 const uint64_t frame_before = simout.frame;
54 simloop_update(&simloop, 0, &simout);
55 const uint64_t frame_after = simout.frame;
56
57 TEST_TRUE(!simout.should_update);
58 TEST_EQUAL(frame_before, frame_after);
59}
60
61/// A simulation loop with no render frame cap:
62/// 1. Updates based on the desired update frame rate.
63/// 2. Does not throttle rendering.
64TEST_CASE(simloop_no_render_frame_cap) {
65 constexpr int UPDATE_FPS = 10; // 100ms delta
66 const simloop_time_t UPDATE_DDT =
67 time_delta_from_sec(1.0 / (double)UPDATE_FPS);
68 const simloop_time_t STEP = time_delta_from_sec(0.05); // 50ms
69 const simloop_time_t SIM_DURATION_SEC = time_delta_from_sec(30);
70
71 // We need simulation time to be an exact multiple of the desired deltas for
72 // the modulo comparison below.
73 TEST_TRUE((UPDATE_DDT % STEP) == 0);
74
75 Simloop simloop = simloop_make(&(SimloopArgs){.update_fps = UPDATE_FPS});
76 SimloopOut simout;
77
78 simloop_update(&simloop, 0, &simout);
79 TEST_TRUE(!simout.should_update); // Time has not advanced.
80 TEST_EQUAL(simout.throttle, 0); // No throttling with no render frame cap.
81
82 for (simloop_time_t t = STEP; t <= SIM_DURATION_SEC; t += STEP) {
83 simloop_update(&simloop, STEP, &simout);
84 const bool expect_update = (t % UPDATE_DDT) == 0;
85 TEST_EQUAL(simout.should_update, expect_update);
86 TEST_EQUAL(simout.throttle, 0);
87 }
88}
89
90/// A simulation loop with a render frame cap:
91/// 1. Updates based on the desired update frame rate.
92/// 2. Throttles rendering based on the desired render frame rate.
93TEST_CASE(simloop_with_render_frame_cap) {
94 constexpr int UPDATE_FPS = 10; // 100ms delta
95 constexpr int RENDER_FPS = 5; // 200ms delta
96 const simloop_time_t UPDATE_DDT =
97 time_delta_from_sec(1.0 / (double)UPDATE_FPS);
98 const simloop_time_t RENDER_DDT =
99 time_delta_from_sec(1.0 / (double)RENDER_FPS);
100 const simloop_time_t STEP = time_delta_from_sec(0.1); // 100ms
101 const simloop_time_t SIM_DURATION_SEC = time_delta_from_sec(30);
102
103 // We need simulation time to be an exact multiple of the desired deltas for
104 // the modulo comparisons below.
105 TEST_TRUE((UPDATE_DDT % STEP) == 0);
106
107 Simloop simloop = simloop_make(
108 &(SimloopArgs){.update_fps = UPDATE_FPS, .max_render_fps = RENDER_FPS});
109 SimloopOut simout;
110
111 simloop_update(&simloop, 0, &simout);
112 TEST_TRUE(!simout.should_update); // Time has not advanced.
113 TEST_EQUAL(simout.throttle, 0); // No throttle since time has not advanced.
114
115 for (simloop_time_t t = STEP; t <= SIM_DURATION_SEC; t += STEP) {
116 simloop_update(&simloop, STEP, &simout);
117 TEST_EQUAL(simout.should_update, (t % UPDATE_DDT) == 0);
118 TEST_NOTEQUAL(simout.throttle, 0);
119 }
120}
121
122/// If the update falls behind the clock, then percent_frame can fall out of
123/// range (>1) if we are not careful. This tests for this condition.
124TEST_CASE(simloop_percent_frame_01_large_jump) {
125 constexpr int UPDATE_FPS = 10; // 100ms delta
126 const simloop_time_t UPDATE_DDT =
127 time_delta_from_sec(1.0 / (double)UPDATE_FPS);
128 const simloop_time_t STEP = time_delta_from_sec(1);
129 const simloop_time_t SIM_DURATION_SEC = time_delta_from_sec(30);
130
131 // We need simulation time to be an exact multiple of the desired deltas for
132 // the modulo comparison below.
133 TEST_TRUE((STEP % UPDATE_DDT) == 0);
134
135 Simloop simloop = simloop_make(&(SimloopArgs){.update_fps = UPDATE_FPS});
136 SimloopOut simout;
137
138 simloop_update(&simloop, 0, &simout);
139 TEST_TRUE(!simout.should_update); // Time has not advanced.
140
141 for (simloop_time_t t = STEP; t <= SIM_DURATION_SEC; t += STEP) {
142 simloop_update(&simloop, STEP, &simout);
143 TEST_TRUE(simout.should_update); // Tries to catch up to clock.
144 TEST_TRUE(0. <= simout.percent_frame);
145 TEST_TRUE(simout.percent_frame <= 1.);
146 }
147}
148
149/// One benefit of fixed over variable time deltas is determinism. Test for
150/// this by getting to t=10 by different clock time increments.
151///
152/// Note that the time increments must be able to keep up with the desired frame
153/// delta, otherwise determinism is not maintained. We can guarantee determinism
154/// at the expense of re-introducing divergence.
155/// TODO: Perhaps the API should return an update count instead of a boolean,
156/// advance simulation time per the number of updates, then leave it up to
157/// the client to decide whether to update just once or as many times as
158/// requested, depending on whether they want determinism or convergence.
159TEST_CASE(simloop_determinism) {
160 constexpr int UPDATE_FPS = 100; // 10ms delta
161 const simloop_time_t RANDOM_STEPS[] = {
162 time_delta_from_sec(0.007), // 7ms
163 time_delta_from_sec(0.005), // 5ms
164 time_delta_from_sec(0.003), // 3ms
165 };
166 constexpr uint64_t NUM_RANDOM_STEPS =
167 sizeof(RANDOM_STEPS) / sizeof(RANDOM_STEPS[0]);
168 const simloop_time_t SIM_DURATION_SEC = time_delta_from_sec(10);
169 constexpr float ADD = 0.123f;
170
171 typedef struct Simulation {
172 int iter_count;
173 float sum;
174 } Simulation;
175
176#define UPDATE_SIMULATION(SIM) \
177 { \
178 SIM.sum += ADD; \
179 SIM.iter_count++; \
180 }
181
182 Simulation sim[2] = {0};
183 XorShift64State xss = (XorShift64State){12069019817132197873ULL};
184
185 // Perform two simulations with random clock-time steps.
186 for (int s = 0; s < 2; ++s) {
187 simloop_time_t dt = 0;
188 Simloop simloop = simloop_make(&(SimloopArgs){.update_fps = UPDATE_FPS});
189 SimloopOut simout;
190
191 for (simloop_time_t t = 0; t <= SIM_DURATION_SEC;) {
192 simloop_update(&simloop, dt, &simout);
193
194 if (simout.should_update) {
195 UPDATE_SIMULATION(sim[s]);
196 }
197
198 // Advance time with a random step.
199 const simloop_time_t step =
200 RANDOM_STEPS[xorshift64(&xss) % NUM_RANDOM_STEPS];
201 t += step;
202 dt = step;
203 }
204 }
205
206 // Make sure the simulations have advanced by the same number of updates so
207 // that we can compare them. They may not have had the same update count
208 // depending on the clock-time steps.
209 while (sim[0].iter_count < sim[1].iter_count) {
210 UPDATE_SIMULATION(sim[0]);
211 }
212 while (sim[1].iter_count < sim[0].iter_count) {
213 UPDATE_SIMULATION(sim[1]);
214 }
215 TEST_EQUAL(sim[0].iter_count, sim[1].iter_count);
216
217 // The sums should be exactly equal if determinism holds.
218 // Check also that they are non-zero to make sure the simulation actually
219 // advanced.
220 TEST_TRUE(sim[0].sum > 0.f);
221 TEST_EQUAL(sim[0].sum, sim[1].sum);
222}
223
224/// The simulation loop attempts to catch up with the clock in the event of a
225/// time spike.
226///
227/// Catch-up is possible only if the simulation loops with a frequency higher
228/// than the requested update frequency given by the update delta time.
229///
230/// Catch-up is performed only for sufficiently small time spikes. For large
231/// time spikes, the simulation clock is warped. This test is for the small
232/// time spike case.
233static void simloop_catch_up(
234 struct test_case_metadata* metadata, int update_ddt_ms, int loop_step_ms,
235 bool expect_catchup) {
236 const int UPDATE_FPS = 1000 / update_ddt_ms;
237 const simloop_time_t UPDATE_DDT =
238 time_delta_from_sec(1.0 / (double)UPDATE_FPS);
239 const simloop_time_t STEP =
240 time_delta_from_sec((double)loop_step_ms / 1000.0);
241 const simloop_time_t SIM_DURATION_SEC = time_delta_from_sec(30);
242 const int EXPECTED_TOTAL_FRAMES_WITH_CATCHUP =
243 (int)(SIM_DURATION_SEC / UPDATE_DDT);
244
245 Simloop simloop = simloop_make(&(SimloopArgs){.update_fps = UPDATE_FPS});
246 SimloopOut simout;
247 int frames = 0;
248
249 // Simulate a time spike.
250 // Advance time to t=1s. That is a lag of 1,000ms / 100ms = 10 frames.
251 // 10 frames is the maximum allowed catch-up.
252 // The simulation now has 29s to catch up.
253 simloop_time_t dt = time_delta_from_sec(1);
254 for (simloop_time_t t = dt; t <= SIM_DURATION_SEC;) {
255 simloop_update(&simloop, dt, &simout);
256
257 if (simout.should_update) {
258 frames++;
259 }
260
261 // New delta is as usual.
262 dt = STEP;
263 t += dt;
264 }
265
266 if (expect_catchup) {
267 TEST_EQUAL(frames, EXPECTED_TOTAL_FRAMES_WITH_CATCHUP);
268 } else {
269 TEST_TRUE(frames < EXPECTED_TOTAL_FRAMES_WITH_CATCHUP);
270 }
271}
272/// (Loop frequency > update frequency) => successful catch-up.
273TEST_CASE(simloop_catch_up_success) {
274 constexpr int UPDATE_DDT_MS = 100;
275 constexpr int LOOP_DDT_MS = 10;
276 simloop_catch_up(metadata, UPDATE_DDT_MS, LOOP_DDT_MS, true);
277}
278/// (Loop frequency < update frequency) => failed catch-up.
279TEST_CASE(simloop_catch_up_failure) {
280 constexpr int UPDATE_DDT_MS = 10;
281 constexpr int LOOP_DDT_MS = 100;
282 simloop_catch_up(metadata, UPDATE_DDT_MS, LOOP_DDT_MS, false);
283}
284
285/// This tests the large time spike case, where the simulation clock is warped
286/// to the wall clock.
287TEST_CASE(simloop_warp) {
288 const int UPDATE_FPS = 50;
289 const simloop_time_t UPDATE_DDT =
290 time_delta_from_sec(1.0 / (double)UPDATE_FPS);
291
292 Simloop simloop = simloop_make(&(SimloopArgs){.update_fps = UPDATE_FPS});
293 SimloopOut simout;
294
295 // The maximum allowed catch-up is 10 frames. Simulate a time spike larger
296 // than that.
297 const simloop_time_t TIME_SPIKE = UPDATE_DDT * 20;
298 simloop_update(&simloop, TIME_SPIKE, &simout);
299 TEST_TRUE(simout.should_update); // Warp should still request update.
300
301 // Now "advance" by 0.
302 simloop_update(&simloop, 0, &simout);
303 TEST_TRUE(!simout.should_update); // No more updates after warp.
304}
305
306int main() { return 0; }
diff --git a/test/CMakeLists.txt b/test/CMakeLists.txt
index a35fde4..9fe9a9c 100644
--- a/test/CMakeLists.txt
+++ b/test/CMakeLists.txt
@@ -6,8 +6,8 @@ set(CMAKE_C_STANDARD 23)
6set(CMAKE_C_STANDARD_REQUIRED On) 6set(CMAKE_C_STANDARD_REQUIRED On)
7set(CMAKE_C_EXTENSIONS Off) 7set(CMAKE_C_EXTENSIONS Off)
8 8
9add_library(test INTERFACE 9add_library(ctest INTERFACE
10 test.h) 10 test.h)
11 11
12target_include_directories(test INTERFACE 12target_include_directories(ctest INTERFACE
13 .) 13 .)
diff --git a/timer/CMakeLists.txt b/timer/CMakeLists.txt
index fb300a0..55f4d79 100644
--- a/timer/CMakeLists.txt
+++ b/timer/CMakeLists.txt
@@ -15,7 +15,7 @@ add_library(timer ${SRC})
15 15
16target_include_directories(timer PUBLIC include) 16target_include_directories(timer PUBLIC include)
17 17
18target_compile_options(timer PRIVATE -Wall -Wextra) 18target_compile_options(timer PRIVATE -Wall -Wextra -Wpedantic)
19 19
20# Test 20# Test
21 21
@@ -24,4 +24,4 @@ add_executable(timer_test
24 24
25target_link_libraries(timer_test timer) 25target_link_libraries(timer_test timer)
26 26
27target_compile_options(timer_test PRIVATE -DUNIT_TEST -DNDEBUG -Wall -Wextra) 27target_compile_options(timer_test PRIVATE -DUNIT_TEST -DNDEBUG -Wall -Wextra -Wpedantic)
diff --git a/timer/include/timer.h b/timer/include/timer.h
index 94781d6..05f6009 100644
--- a/timer/include/timer.h
+++ b/timer/include/timer.h
@@ -20,11 +20,11 @@ typedef struct timespec time_point;
20typedef uint64_t time_delta; 20typedef uint64_t time_delta;
21 21
22/// A high resolution timer. 22/// A high resolution timer.
23typedef struct { 23typedef struct Timer {
24 time_point start_time; // The instant the timer was last started. 24 time_point start_time; ///< The instant the timer was last started.
25 time_point last_tick; // The instant the timer was last ticked. 25 time_point last_tick; ///< The instant the timer was last ticked.
26 time_delta running_time; // Time elapsed since the timer was last started. 26 time_delta running_time; ///< Time elapsed since the timer was last started.
27 time_delta delta_time; // Time elapsed since the last tick. 27 time_delta delta_time; ///< Time elapsed since the last tick.
28} Timer; 28} Timer;
29 29
30/// Construct a new timer. 30/// Construct a new timer.
@@ -38,6 +38,15 @@ void timer_start(Timer*);
38/// Update the timer's running and delta times. 38/// Update the timer's running and delta times.
39void timer_tick(Timer*); 39void timer_tick(Timer*);
40 40
41/// Advance the timer.
42///
43/// This is used for simulations that wish control over time. It should not be
44/// used together with timer_tick().
45///
46/// The input time is relative to the timer's start time. Successive calls to
47/// this function must use increasing values of time.
48void timer_advance(Timer* timer, time_delta t);
49
41/// Get the current time. 50/// Get the current time.
42time_point time_now(void); 51time_point time_now(void);
43 52
@@ -48,11 +57,14 @@ time_delta time_diff(time_point start, time_point end);
48double time_delta_to_sec(time_delta dt); 57double time_delta_to_sec(time_delta dt);
49 58
50/// Convert the time elapsed in seconds to a time delta. 59/// Convert the time elapsed in seconds to a time delta.
51time_delta sec_to_time_delta(double seconds); 60time_delta time_delta_from_sec(double seconds);
52 61
53/// Convert the time point to nanoseconds. 62/// Convert the time point to nanoseconds.
54uint64_t time_point_to_ns(time_point); 63uint64_t time_point_to_ns(time_point);
55 64
65/// Add a time delta to a timestamp.
66time_point time_add(time_point, time_delta);
67
56/// Put the caller thread to sleep for the given amount of time. 68/// Put the caller thread to sleep for the given amount of time.
57void time_sleep(time_delta dt); 69void time_sleep(time_delta dt);
58 70
diff --git a/timer/src/timer.c b/timer/src/timer.c
index da3485b..b845491 100644
--- a/timer/src/timer.c
+++ b/timer/src/timer.c
@@ -7,9 +7,9 @@
7#endif 7#endif
8 8
9#ifdef _WIN32 9#ifdef _WIN32
10static const int64_t microseconds = 1000000; 10static constexpr uint64_t microseconds = 1000000;
11#endif 11#endif
12static const int64_t nanoseconds = 1000000000; 12static constexpr uint64_t nanoseconds = 1000000000;
13 13
14#ifdef _WIN32 14#ifdef _WIN32
15static double seconds_per_count; 15static double seconds_per_count;
@@ -37,11 +37,20 @@ void timer_start(Timer* timer) {
37 timer->delta_time = 0; 37 timer->delta_time = 0;
38} 38}
39 39
40static void timer_update(Timer* timer, time_point this_tick) {
41 timer->running_time = time_diff(timer->start_time, this_tick);
42 timer->delta_time = time_diff(timer->last_tick, this_tick);
43 timer->last_tick = this_tick;
44}
45
40void timer_tick(Timer* timer) { 46void timer_tick(Timer* timer) {
41 const time_point this_tick = time_now(); 47 const time_point this_tick = time_now();
42 timer->running_time = time_diff(timer->start_time, this_tick); 48 timer_update(timer, this_tick);
43 timer->delta_time = time_diff(timer->last_tick, this_tick); 49}
44 timer->last_tick = this_tick; 50
51void timer_advance(Timer* timer, time_delta t) {
52 const time_point this_tick = time_add(timer->start_time, t);
53 timer_update(timer, this_tick);
45} 54}
46 55
47time_point time_now(void) { 56time_point time_now(void) {
@@ -49,7 +58,7 @@ time_point time_now(void) {
49#ifdef _WIN32 58#ifdef _WIN32
50 QueryPerformanceCounter((LARGE_INTEGER*)&t); 59 QueryPerformanceCounter((LARGE_INTEGER*)&t);
51#else 60#else
52 clock_gettime(CLOCK_REALTIME, &t); 61 clock_gettime(CLOCK_MONOTONIC_RAW, &t);
53#endif 62#endif
54 return t; 63 return t;
55} 64}
@@ -61,7 +70,8 @@ time_delta time_diff(time_point start, time_point end) {
61 // another processor, then the delta time can be negative. 70 // another processor, then the delta time can be negative.
62 return std::max(0, end - start); 71 return std::max(0, end - start);
63#else 72#else
64 return (end.tv_sec - start.tv_sec) * 1e9 + (end.tv_nsec - start.tv_nsec); 73 return (end.tv_sec - start.tv_sec) * nanoseconds +
74 (end.tv_nsec - start.tv_nsec);
65#endif 75#endif
66} 76}
67 77
@@ -73,7 +83,7 @@ double time_delta_to_sec(time_delta dt) {
73#endif 83#endif
74} 84}
75 85
76time_delta sec_to_time_delta(double seconds) { 86time_delta time_delta_from_sec(double seconds) {
77#ifdef _WIN32 87#ifdef _WIN32
78 return (time_delta)(seconds / seconds_per_count); 88 return (time_delta)(seconds / seconds_per_count);
79#else 89#else
@@ -85,19 +95,30 @@ uint64_t time_point_to_ns(time_point t) {
85#ifdef _WIN32 95#ifdef _WIN32
86 return (uint64_t)((double)t * seconds_per_count * 1.0e+9); 96 return (uint64_t)((double)t * seconds_per_count * 1.0e+9);
87#else 97#else
88 return (uint64_t)t.tv_sec * 1e+9 + (uint64_t)t.tv_nsec; 98 return (uint64_t)t.tv_sec * nanoseconds + (uint64_t)t.tv_nsec;
99#endif
100}
101
102time_point time_add(time_point t, time_delta dt) {
103 time_point out;
104#ifdef _WIN32
105 out = t + dt;
106#else
107 out.tv_sec = t.tv_sec + (__time_t)(dt / nanoseconds);
108 out.tv_nsec = t.tv_nsec + (__time_t)(dt % nanoseconds);
89#endif 109#endif
110 return out;
90} 111}
91 112
92void time_sleep(time_delta dt) { 113void time_sleep(time_delta dt) {
93#ifdef _WIN32 114#ifdef _WIN32
94 const int64_t ms = dt / microseconds; 115 const uint64_t ms = dt / microseconds;
95 Sleep((DWORD)(ms)); 116 Sleep((DWORD)(ms));
96#else 117#else
97 const int64_t sec = dt / nanoseconds; 118 const uint64_t sec = dt / nanoseconds;
98 struct timespec ts; 119 struct timespec ts;
99 ts.tv_sec = (long)sec; 120 ts.tv_sec = (long)sec;
100 ts.tv_nsec = (long)(dt % nanoseconds); 121 ts.tv_nsec = (long)(dt % nanoseconds);
101 nanosleep(&ts, NULL); 122 nanosleep(&ts, nullptr);
102#endif 123#endif
103} 124}
diff --git a/timer/test/timer_test.c b/timer/test/timer_test.c
index a220ead..7fa102a 100644
--- a/timer/test/timer_test.c
+++ b/timer/test/timer_test.c
@@ -9,7 +9,7 @@ TEST_CASE(sleep) {
9 const double sleep_time_sec = 0.1; 9 const double sleep_time_sec = 0.1;
10 10
11 const time_point start = time_now(); 11 const time_point start = time_now();
12 time_sleep(sec_to_time_delta(sleep_time_sec)); 12 time_sleep(time_delta_from_sec(sleep_time_sec));
13 const time_point end = time_now(); 13 const time_point end = time_now();
14 14
15 TEST_TRUE(time_delta_to_sec(time_diff(start, end)) >= sleep_time_sec); 15 TEST_TRUE(time_delta_to_sec(time_diff(start, end)) >= sleep_time_sec);
@@ -28,7 +28,7 @@ TEST_CASE(tick_updates_last_tick_time) {
28 const double sleep_time_sec = 0.1; 28 const double sleep_time_sec = 0.1;
29 29
30 Timer timer = timer_make(); 30 Timer timer = timer_make();
31 time_sleep(sec_to_time_delta(sleep_time_sec)); 31 time_sleep(time_delta_from_sec(sleep_time_sec));
32 timer_tick(&timer); 32 timer_tick(&timer);
33 33
34 TEST_TRUE(time_delta_to_sec(time_diff(timer.start_time, timer.last_tick)) >= 34 TEST_TRUE(time_delta_to_sec(time_diff(timer.start_time, timer.last_tick)) >=
@@ -40,7 +40,7 @@ TEST_CASE(tick_updates_delta_time) {
40 const double sleep_time_sec = 0.1; 40 const double sleep_time_sec = 0.1;
41 41
42 Timer timer = timer_make(); 42 Timer timer = timer_make();
43 time_sleep(sec_to_time_delta(sleep_time_sec)); 43 time_sleep(time_delta_from_sec(sleep_time_sec));
44 timer_tick(&timer); 44 timer_tick(&timer);
45 45
46 TEST_TRUE(time_delta_to_sec(timer.delta_time) >= sleep_time_sec); 46 TEST_TRUE(time_delta_to_sec(timer.delta_time) >= sleep_time_sec);
@@ -50,7 +50,7 @@ TEST_CASE(tick_updates_delta_time) {
50TEST_CASE(tick_does_not_change_start_time) { 50TEST_CASE(tick_does_not_change_start_time) {
51 Timer timer = timer_make(); 51 Timer timer = timer_make();
52 const time_point start_time = timer.start_time; 52 const time_point start_time = timer.start_time;
53 time_sleep(sec_to_time_delta(0.1)); 53 time_sleep(time_delta_from_sec(0.1));
54 timer_tick(&timer); 54 timer_tick(&timer);
55 TEST_TRUE(time_delta_to_sec(time_diff(start_time, timer.start_time)) == 0.0); 55 TEST_TRUE(time_delta_to_sec(time_diff(start_time, timer.start_time)) == 0.0);
56} 56}
@@ -60,7 +60,7 @@ TEST_CASE(start_restarts_start_time) {
60 const double sleep_time_seconds = 0.1; 60 const double sleep_time_seconds = 0.1;
61 Timer timer = timer_make(); 61 Timer timer = timer_make();
62 const time_point start_time = timer.start_time; 62 const time_point start_time = timer.start_time;
63 time_sleep(sec_to_time_delta(sleep_time_seconds)); 63 time_sleep(time_delta_from_sec(sleep_time_seconds));
64 timer_start(&timer); 64 timer_start(&timer);
65 TEST_TRUE(time_delta_to_sec(time_diff(start_time, timer.start_time)) >= 65 TEST_TRUE(time_delta_to_sec(time_diff(start_time, timer.start_time)) >=
66 sleep_time_seconds); 66 sleep_time_seconds);
@@ -75,7 +75,7 @@ TEST_CASE(count) {
75 { 75 {
76 while (time_delta_to_sec(timer.running_time) <= 1.0) { 76 while (time_delta_to_sec(timer.running_time) <= 1.0) {
77 hundred_seconds++; 77 hundred_seconds++;
78 time_sleep(sec_to_time_delta(0.1)); 78 time_sleep(time_delta_from_sec(0.1));
79 timer_tick(&timer); 79 timer_tick(&timer);
80 TEST_TRUE(time_delta_to_sec(timer.delta_time) >= 0.1); 80 TEST_TRUE(time_delta_to_sec(timer.delta_time) >= 0.1);
81 } 81 }