diff options
| -rw-r--r-- | CMakeLists.txt | 3 | ||||
| -rw-r--r-- | cstring/CMakeLists.txt | 5 | ||||
| -rw-r--r-- | cstring/include/cstring.h | 49 | ||||
| -rw-r--r-- | cstring/src/cstring.c | 10 | ||||
| -rw-r--r-- | filesystem/include/filesystem.h | 20 | ||||
| -rw-r--r-- | filesystem/src/filesystem.c | 65 | ||||
| -rw-r--r-- | filesystem/src/path.c | 2 | ||||
| -rw-r--r-- | list/include/list.h | 8 | ||||
| -rw-r--r-- | list/test/list_test.c | 2 | ||||
| -rw-r--r-- | mem/include/mem.h | 4 | ||||
| -rw-r--r-- | mem/src/mem.c | 30 | ||||
| -rw-r--r-- | mem/test/mem_test.c | 36 | ||||
| -rw-r--r-- | mempool/README.md | 23 | ||||
| -rw-r--r-- | mempool/include/mempool.h | 8 | ||||
| -rw-r--r-- | mempool/src/mempool.c | 24 | ||||
| -rw-r--r-- | mempool/test/mempool_test.c | 34 | ||||
| -rw-r--r-- | memstack/CMakeLists.txt | 30 | ||||
| -rw-r--r-- | memstack/README.md | 15 | ||||
| -rw-r--r-- | memstack/include/memstack.h | 66 | ||||
| -rw-r--r-- | memstack/src/memstack.c | 119 | ||||
| -rw-r--r-- | memstack/test/memstack_test.c | 171 | ||||
| -rw-r--r-- | memstack/test/test.h | 185 | ||||
| -rw-r--r-- | plugin/src/plugin.c | 18 | ||||
| -rw-r--r-- | timer/include/timer.h | 5 | ||||
| -rw-r--r-- | timer/src/timer.c | 28 |
25 files changed, 813 insertions, 147 deletions
diff --git a/CMakeLists.txt b/CMakeLists.txt index 04e0e4e..d1fb3ab 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt | |||
| @@ -9,9 +9,10 @@ add_subdirectory(cstring) | |||
| 9 | add_subdirectory(error) | 9 | add_subdirectory(error) |
| 10 | add_subdirectory(filesystem) | 10 | add_subdirectory(filesystem) |
| 11 | add_subdirectory(list) | 11 | add_subdirectory(list) |
| 12 | add_subdirectory(mem) | ||
| 13 | add_subdirectory(log) | 12 | add_subdirectory(log) |
| 13 | add_subdirectory(mem) | ||
| 14 | add_subdirectory(mempool) | 14 | add_subdirectory(mempool) |
| 15 | add_subdirectory(memstack) | ||
| 15 | add_subdirectory(plugin) | 16 | add_subdirectory(plugin) |
| 16 | add_subdirectory(random) | 17 | add_subdirectory(random) |
| 17 | add_subdirectory(timer) | 18 | add_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 | ||
| 16 | target_link_libraries(cstring PUBLIC | 16 | target_link_libraries(cstring PUBLIC |
| 17 | cassert) | 17 | cassert) |
| 18 | |||
| 19 | if(LINUX) | ||
| 20 | target_link_libraries(cstring PUBLIC | ||
| 21 | -lbsd) | ||
| 22 | endif() | ||
diff --git a/cstring/include/cstring.h b/cstring/include/cstring.h index b07dad6..c24cd35 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. | ||
| 15 | uint64_t cstring_hash(const char* str); | ||
| 16 | |||
| 17 | /// Copy 'count' characters from the source to the destination, null-terminating | ||
| 18 | /// the destination. | ||
| 19 | static 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() { 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. | ||
| 128 | static 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 | |||
| 136 | DEF_STRING(sstring, 32) // Small. | 147 | DEF_STRING(sstring, 32) // Small. |
| 137 | DEF_STRING(mstring, 256) // Medium. | 148 | DEF_STRING(mstring, 256) // Medium. |
| 138 | DEF_STRING(lstring, 1024) // Large. | 149 | DEF_STRING(lstring, 1024) // Large. |
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) { | |||
| 23 | void string_del(string* str) { | 23 | void 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 | |||
| 105 | uint64_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/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. | ||
| 20 | size_t get_file_size(const char* filename); | ||
| 21 | |||
| 9 | /// Get the file's size. | 22 | /// Get the file's size. |
| 10 | size_t get_file_size(FILE* file); | 23 | size_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. |
| 13 | void* read_file(const char* filepath); | 26 | void* 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. | ||
| 31 | bool 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 | ||
| 8 | size_t get_file_size(FILE* file) { | 8 | size_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 | |||
| 14 | size_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) { | |||
| 27 | void* read_file(const char* filepath) { | 33 | void* 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 | ||
| 51 | cleanup: | 58 | bool 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) { | |||
| 21 | void path_del(path* path) { | 21 | void 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/list/include/list.h b/list/include/list.h index 24291e1..aadcb88 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,7 @@ 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 | 36 | ||
| 37 | /// Prepend a value to the list. | 37 | /// Prepend a value to the list. |
| 38 | #define list_add(list, value) \ | 38 | #define list_add(list, value) \ |
| @@ -76,10 +76,10 @@ static inline void* alloc(size_t size) { | |||
| 76 | node->next->prev = node->prev; \ | 76 | node->next->prev = node->prev; \ |
| 77 | } \ | 77 | } \ |
| 78 | if (list.head == node) { \ | 78 | if (list.head == node) { \ |
| 79 | list.head = 0; \ | 79 | list.head = nullptr; \ |
| 80 | } \ | 80 | } \ |
| 81 | free(node); \ | 81 | free(node); \ |
| 82 | node = 0; \ | 82 | node = nullptr; \ |
| 83 | } | 83 | } |
| 84 | 84 | ||
| 85 | /// Iterate over all the items in the list. | 85 | /// 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) { | |||
| 52 | TEST_CASE(list_remove_by_address) { | 52 | TEST_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/mem/include/mem.h b/mem/include/mem.h index 224b069..3050ba8 100644 --- a/mem/include/mem.h +++ b/mem/include/mem.h | |||
| @@ -68,13 +68,13 @@ | |||
| 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) mem_alloc_(&(MEM)->mem, num_blocks) |
| 75 | 75 | ||
| 76 | /// Free the chunk. | 76 | /// Free the chunk. |
| 77 | /// The chunk pointer is conveniently set to 0. | 77 | /// The chunk pointer is conveniently set to null. |
| 78 | #define mem_free(MEM, CHUNK) mem_free_(&(MEM)->mem, (void**)CHUNK) | 78 | #define mem_free(MEM, CHUNK) mem_free_(&(MEM)->mem, (void**)CHUNK) |
| 79 | 79 | ||
| 80 | /// Return a pointer to a chunk given the chunk's handle. | 80 | /// 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 | ||
| 58 | void mem_clear_(Memory* mem) { | 58 | void 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 | ||
| 69 | void* mem_alloc_(Memory* mem, size_t num_blocks) { | 72 | void* 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. | ||
| 36 | TEST_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. |
| 36 | TEST_CASE(mem_fully_allocate) { | 42 | TEST_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/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 | ||
| 3 | A memory pool implementation. | 3 | A memory pool of fixed-sized blocks with O(1) allocation and deallocation. |
| 4 | 4 | ||
| 5 | Each block in the pool is tagged with a boolean value that indicates whether the | 5 | Each block in the pool is tagged with a boolean value that indicates whether the |
| 6 | block is free or in use. The allocator otherwise maintains little additional | 6 | block is free or in use, as well as a pointer to the next free/used block. |
| 7 | information. Therefore, some operations have linear-time complexity. | 7 | Blocks thus form two lists, a free list and a used list. The allocator |
| 8 | Specifically: | 8 | maintains the two lists when allocating/deallocating blocks. |
| 9 | 9 | ||
| 10 | - Allocating a block scans the pool for the next free block in linear time. | 10 | The allocator's internal data is stored separately from the block data so that |
| 11 | - Freeing a block runs in constant time. | 11 | the 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 | ||
| 15 | The allocator's internal data is also stored separately from the main array of | 13 | Free blocks in the mempool always remain zeroed out for convenience of |
| 16 | blocks so that the block data remains tightly packed. | 14 | programming and debugging. If the application's data structures are valid when |
| 17 | 15 | zeroed out, then they do not need to be explicitly initialized. | |
| 18 | For convenience of programming and debugging, free blocks in the mempool always | ||
| 19 | remain zeroed out. If your data structures are valid when zeroed out, then you | ||
| 20 | do not need to explicitly initialize them. | ||
diff --git a/mempool/include/mempool.h b/mempool/include/mempool.h index 245173b..0de7ac6 100644 --- a/mempool/include/mempool.h +++ b/mempool/include/mempool.h | |||
| @@ -64,15 +64,15 @@ | |||
| 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) mempool_alloc_(&(POOL)->pool) |
| 73 | 73 | ||
| 74 | /// Free the block. | 74 | /// Free the block. |
| 75 | /// The block pointer is conveniently set to 0. | 75 | /// The block pointer is conveniently set to null. |
| 76 | #define mempool_free(POOL, BLOCK_PTR) \ | 76 | #define mempool_free(POOL, BLOCK_PTR) \ |
| 77 | assert(*BLOCK_PTR); \ | 77 | assert(*BLOCK_PTR); \ |
| 78 | mempool_free_(&(POOL)->pool, (void**)BLOCK_PTR) | 78 | mempool_free_(&(POOL)->pool, (void**)BLOCK_PTR) |
| @@ -106,8 +106,8 @@ | |||
| 106 | /// It is valid to mempool_free() the object at each step of the iteration. | 106 | /// It is valid to mempool_free() the object at each step of the iteration. |
| 107 | #define mempool_foreach(POOL, ITER, BODY) \ | 107 | #define mempool_foreach(POOL, ITER, BODY) \ |
| 108 | { \ | 108 | { \ |
| 109 | size_t i = (POOL)->pool.used; \ | ||
| 110 | if ((POOL)->pool.num_used_blocks > 0) { \ | 109 | if ((POOL)->pool.num_used_blocks > 0) { \ |
| 110 | size_t i = (POOL)->pool.used; \ | ||
| 111 | do { \ | 111 | do { \ |
| 112 | if ((POOL)->pool.block_info[i].used) { \ | 112 | if ((POOL)->pool.block_info[i].used) { \ |
| 113 | __typeof__((POOL)->object[0])* ITER = \ | 113 | __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. |
| 10 | static void init_free_list(mempool* pool) { | 10 | static 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 | ||
| 67 | void mempool_clear_(mempool* pool) { | 68 | void 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 | ||
| 76 | void* mempool_alloc_(mempool* pool) { | 80 | void* 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 | ||
| 130 | void* mempool_get_block_(const mempool* pool, size_t block_index) { | 134 | void* 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. |
| 28 | TEST_CASE(mem_create_dyn) { | 28 | TEST_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. | ||
| 36 | TEST_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. |
| 36 | TEST_CASE(mempool_allocate_until_full) { | 42 | TEST_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. |
| 175 | TEST_CASE(mem_clear_then_reuse) { | 181 | TEST_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..9ad1aa1 --- /dev/null +++ b/memstack/CMakeLists.txt | |||
| @@ -0,0 +1,30 @@ | |||
| 1 | cmake_minimum_required(VERSION 3.5) | ||
| 2 | |||
| 3 | project(memstack) | ||
| 4 | |||
| 5 | set(CMAKE_C_STANDARD 23) | ||
| 6 | set(CMAKE_C_STANDARD_REQUIRED On) | ||
| 7 | set(CMAKE_C_EXTENSIONS Off) | ||
| 8 | |||
| 9 | # Library | ||
| 10 | |||
| 11 | add_library(memstack | ||
| 12 | src/memstack.c) | ||
| 13 | |||
| 14 | target_include_directories(memstack PUBLIC | ||
| 15 | include) | ||
| 16 | |||
| 17 | target_link_libraries(memstack PRIVATE | ||
| 18 | cassert) | ||
| 19 | |||
| 20 | target_compile_options(memstack PRIVATE -Wall -Wextra) | ||
| 21 | |||
| 22 | # Test | ||
| 23 | |||
| 24 | add_executable(memstack_test | ||
| 25 | test/memstack_test.c) | ||
| 26 | |||
| 27 | target_link_libraries(memstack_test | ||
| 28 | memstack) | ||
| 29 | |||
| 30 | target_compile_options(memstack_test PRIVATE -DUNIT_TEST -DNDEBUG -Wall -Wextra) | ||
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 | |||
| 3 | A memory pool of fixed-sized blocks with O(1) allocation and deallocation. | ||
| 4 | |||
| 5 | Each block in the pool is tagged with a boolean value that indicates whether the | ||
| 6 | block is free or in use, as well as a pointer to the next free/used block. | ||
| 7 | Blocks thus form two lists, a free list and a used list. The allocator | ||
| 8 | maintains the two lists when allocating/deallocating blocks. | ||
| 9 | |||
| 10 | The allocator's internal data is stored separately from the block data so that | ||
| 11 | the data remains tightly packed. | ||
| 12 | |||
| 13 | Free blocks in the mempool always remain zeroed out for convenience of | ||
| 14 | programming and debugging. If the application's data structures are valid when | ||
| 15 | zeroed 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. | ||
| 10 | typedef 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. | ||
| 25 | bool 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. | ||
| 30 | void memstack_del(memstack*); | ||
| 31 | |||
| 32 | /// Clear the stack. | ||
| 33 | void memstack_clear(memstack*); | ||
| 34 | |||
| 35 | /// Return the top of the stack. | ||
| 36 | size_t memstack_watermark(const memstack*); | ||
| 37 | |||
| 38 | /// Set the top of the stack. | ||
| 39 | void 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. | ||
| 50 | void* 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(). | ||
| 57 | void* memstack_alloc_aligned(memstack*, size_t bytes, size_t alignment); | ||
| 58 | |||
| 59 | /// Return the stack's used size in bytes. | ||
| 60 | size_t memstack_size(const memstack*); | ||
| 61 | |||
| 62 | /// Return the stack's total capacity in bytes. | ||
| 63 | size_t memstack_capacity(const memstack*); | ||
| 64 | |||
| 65 | /// Set whether to trap when attempting to allocate beyond capacity. | ||
| 66 | void 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 | |||
| 8 | static 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. | ||
| 12 | static 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 | |||
| 18 | bool 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 | |||
| 41 | void 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 | |||
| 54 | void memstack_clear(memstack* stack) { | ||
| 55 | assert(stack); | ||
| 56 | |||
| 57 | stack->watermark = stack->base; | ||
| 58 | memset(stack->base, 0, stack->capacity); | ||
| 59 | } | ||
| 60 | |||
| 61 | size_t memstack_watermark(const memstack* stack) { | ||
| 62 | assert(stack); | ||
| 63 | return stack->watermark - stack->base; | ||
| 64 | } | ||
| 65 | |||
| 66 | void 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 | |||
| 76 | void* 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 | |||
| 94 | void* 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 | |||
| 106 | size_t memstack_size(const memstack* stack) { | ||
| 107 | assert(stack); | ||
| 108 | return stack->watermark - stack->base; | ||
| 109 | } | ||
| 110 | |||
| 111 | size_t memstack_capacity(const memstack* stack) { | ||
| 112 | assert(stack); | ||
| 113 | return stack->capacity; | ||
| 114 | } | ||
| 115 | |||
| 116 | void 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. | ||
| 9 | TEST_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. | ||
| 18 | TEST_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. | ||
| 25 | TEST_CASE(memstack_clear_uninitialized) { | ||
| 26 | memstack stack = {0}; | ||
| 27 | memstack_clear(&stack); | ||
| 28 | } | ||
| 29 | |||
| 30 | // Allocate all N ints. | ||
| 31 | TEST_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. | ||
| 46 | TEST_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. | ||
| 65 | TEST_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. | ||
| 87 | TEST_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. | ||
| 102 | TEST_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. | ||
| 124 | TEST_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. | ||
| 141 | TEST_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 | |||
| 171 | int 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 | |||
| 21 | struct test_file_metadata; | ||
| 22 | |||
| 23 | struct test_failure { | ||
| 24 | bool present; | ||
| 25 | const char *message; | ||
| 26 | const char *file; | ||
| 27 | int line; | ||
| 28 | }; | ||
| 29 | |||
| 30 | struct 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 | |||
| 37 | struct test_file_metadata { | ||
| 38 | bool registered; | ||
| 39 | const char *name; | ||
| 40 | struct test_file_metadata *next; | ||
| 41 | struct test_case_metadata *tests; | ||
| 42 | }; | ||
| 43 | |||
| 44 | struct 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 | |||
| 97 | extern 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 | ||
| 100 | static 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/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) { | |||
| 86 | static void delete_plugin_state(Plugin* plugin) { | 86 | static 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 | ||
| 150 | PluginEngine* new_plugin_engine(const PluginEngineDesc* desc) { | 150 | PluginEngine* 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 | ||
| 174 | cleanup: | 174 | cleanup: |
| 175 | delete_plugin_engine(&eng); | 175 | delete_plugin_engine(&eng); |
| 176 | return 0; | 176 | return nullptr; |
| 177 | } | 177 | } |
| 178 | 178 | ||
| 179 | void delete_plugin_engine(PluginEngine** pEng) { | 179 | void 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/timer/include/timer.h b/timer/include/timer.h index 94781d6..6dc87d9 100644 --- a/timer/include/timer.h +++ b/timer/include/timer.h | |||
| @@ -20,7 +20,7 @@ typedef struct timespec time_point; | |||
| 20 | typedef uint64_t time_delta; | 20 | typedef uint64_t time_delta; |
| 21 | 21 | ||
| 22 | /// A high resolution timer. | 22 | /// A high resolution timer. |
| 23 | typedef struct { | 23 | typedef 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. |
| @@ -53,6 +53,9 @@ time_delta sec_to_time_delta(double seconds); | |||
| 53 | /// Convert the time point to nanoseconds. | 53 | /// Convert the time point to nanoseconds. |
| 54 | uint64_t time_point_to_ns(time_point); | 54 | uint64_t time_point_to_ns(time_point); |
| 55 | 55 | ||
| 56 | /// Add a time delta to a timestamp. | ||
| 57 | time_point time_add(time_point, time_delta); | ||
| 58 | |||
| 56 | /// Put the caller thread to sleep for the given amount of time. | 59 | /// Put the caller thread to sleep for the given amount of time. |
| 57 | void time_sleep(time_delta dt); | 60 | void time_sleep(time_delta dt); |
| 58 | 61 | ||
diff --git a/timer/src/timer.c b/timer/src/timer.c index da3485b..d886f59 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 |
| 10 | static const int64_t microseconds = 1000000; | 10 | static constexpr uint64_t microseconds = 1000000; |
| 11 | #endif | 11 | #endif |
| 12 | static const int64_t nanoseconds = 1000000000; | 12 | static constexpr uint64_t nanoseconds = 1000000000; |
| 13 | 13 | ||
| 14 | #ifdef _WIN32 | 14 | #ifdef _WIN32 |
| 15 | static double seconds_per_count; | 15 | static double seconds_per_count; |
| @@ -49,7 +49,7 @@ time_point time_now(void) { | |||
| 49 | #ifdef _WIN32 | 49 | #ifdef _WIN32 |
| 50 | QueryPerformanceCounter((LARGE_INTEGER*)&t); | 50 | QueryPerformanceCounter((LARGE_INTEGER*)&t); |
| 51 | #else | 51 | #else |
| 52 | clock_gettime(CLOCK_REALTIME, &t); | 52 | clock_gettime(CLOCK_MONOTONIC_RAW, &t); |
| 53 | #endif | 53 | #endif |
| 54 | return t; | 54 | return t; |
| 55 | } | 55 | } |
| @@ -61,7 +61,8 @@ time_delta time_diff(time_point start, time_point end) { | |||
| 61 | // another processor, then the delta time can be negative. | 61 | // another processor, then the delta time can be negative. |
| 62 | return std::max(0, end - start); | 62 | return std::max(0, end - start); |
| 63 | #else | 63 | #else |
| 64 | return (end.tv_sec - start.tv_sec) * 1e9 + (end.tv_nsec - start.tv_nsec); | 64 | return (end.tv_sec - start.tv_sec) * nanoseconds + |
| 65 | (end.tv_nsec - start.tv_nsec); | ||
| 65 | #endif | 66 | #endif |
| 66 | } | 67 | } |
| 67 | 68 | ||
| @@ -85,19 +86,30 @@ uint64_t time_point_to_ns(time_point t) { | |||
| 85 | #ifdef _WIN32 | 86 | #ifdef _WIN32 |
| 86 | return (uint64_t)((double)t * seconds_per_count * 1.0e+9); | 87 | return (uint64_t)((double)t * seconds_per_count * 1.0e+9); |
| 87 | #else | 88 | #else |
| 88 | return (uint64_t)t.tv_sec * 1e+9 + (uint64_t)t.tv_nsec; | 89 | return (uint64_t)t.tv_sec * nanoseconds + (uint64_t)t.tv_nsec; |
| 89 | #endif | 90 | #endif |
| 90 | } | 91 | } |
| 91 | 92 | ||
| 93 | time_point time_add(time_point t, time_delta dt) { | ||
| 94 | time_point out; | ||
| 95 | #ifdef _WIN32 | ||
| 96 | out = t + dt; | ||
| 97 | #else | ||
| 98 | out.tv_sec = t.tv_sec + (__time_t)(dt / nanoseconds); | ||
| 99 | out.tv_nsec = t.tv_nsec + (__time_t)(dt % nanoseconds); | ||
| 100 | #endif | ||
| 101 | return out; | ||
| 102 | } | ||
| 103 | |||
| 92 | void time_sleep(time_delta dt) { | 104 | void time_sleep(time_delta dt) { |
| 93 | #ifdef _WIN32 | 105 | #ifdef _WIN32 |
| 94 | const int64_t ms = dt / microseconds; | 106 | const uint64_t ms = dt / microseconds; |
| 95 | Sleep((DWORD)(ms)); | 107 | Sleep((DWORD)(ms)); |
| 96 | #else | 108 | #else |
| 97 | const int64_t sec = dt / nanoseconds; | 109 | const uint64_t sec = dt / nanoseconds; |
| 98 | struct timespec ts; | 110 | struct timespec ts; |
| 99 | ts.tv_sec = (long)sec; | 111 | ts.tv_sec = (long)sec; |
| 100 | ts.tv_nsec = (long)(dt % nanoseconds); | 112 | ts.tv_nsec = (long)(dt % nanoseconds); |
| 101 | nanosleep(&ts, NULL); | 113 | nanosleep(&ts, nullptr); |
| 102 | #endif | 114 | #endif |
| 103 | } | 115 | } |
