aboutsummaryrefslogtreecommitdiff
path: root/listpool
diff options
context:
space:
mode:
Diffstat (limited to 'listpool')
-rw-r--r--listpool/CMakeLists.txt26
-rw-r--r--listpool/README.md14
-rw-r--r--listpool/include/listpool.h100
-rw-r--r--listpool/src/listpool.c92
-rw-r--r--listpool/test/listpool_test.c183
-rw-r--r--listpool/test/test.h185
6 files changed, 0 insertions, 600 deletions
diff --git a/listpool/CMakeLists.txt b/listpool/CMakeLists.txt
deleted file mode 100644
index 2dcd983..0000000
--- a/listpool/CMakeLists.txt
+++ /dev/null
@@ -1,26 +0,0 @@
1cmake_minimum_required(VERSION 3.0)
2
3project(listpool)
4
5# Library
6
7add_library(listpool
8 src/listpool.c)
9
10target_include_directories(listpool PUBLIC
11 include)
12
13target_link_libraries(listpool
14 list)
15
16target_compile_options(listpool PRIVATE -Wall -Wextra)
17
18# Test
19
20add_executable(listpool_test
21 test/listpool_test.c)
22
23target_link_libraries(listpool_test
24listpool)
25
26target_compile_options(listpool_test PRIVATE -DUNIT_TEST -DNDEBUG -Wall -Wextra)
diff --git a/listpool/README.md b/listpool/README.md
deleted file mode 100644
index ed38980..0000000
--- a/listpool/README.md
+++ /dev/null
@@ -1,14 +0,0 @@
1# Listpool
2
3A block allocator built from a single, contiguous array of memory that maintains
4free and used blocks in doubly linked lists.
5
6A `listpool` is similar to a `mempool`, but the additional structure allows it
7to:
8
9- Allocate and free blocks in constant time.
10- Traverse used blocks in linear time in the number of used blocks, as opposed
11 to the total number of blocks like in a `mempool`.
12
13A `listpool` otherwise provides the same guarantees and characteristics as a
14`mempool`.
diff --git a/listpool/include/listpool.h b/listpool/include/listpool.h
deleted file mode 100644
index 85a3b27..0000000
--- a/listpool/include/listpool.h
+++ /dev/null
@@ -1,100 +0,0 @@
1#pragma once
2
3#include "list.h"
4
5#include <assert.h>
6#include <stddef.h>
7#include <stdint.h>
8
9/// Define a typed listpool of a given size.
10#define DEF_LISTPOOL(POOL, TYPE, NUM_BLOCKS) \
11 typedef struct POOL { \
12 listpool pool; \
13 list nodes[NUM_BLOCKS]; \
14 TYPE blocks[NUM_BLOCKS]; \
15 } POOL;
16
17/// Creates a new listpool.
18#define listpool_make(POOL) \
19 { \
20 assert(POOL); \
21 const size_t block_size = sizeof((POOL)->blocks[0]); \
22 const size_t num_blocks = sizeof((POOL)->blocks) / block_size; \
23 listpool_make_( \
24 &(POOL)->pool, (POOL)->nodes, (POOL)->blocks, num_blocks, block_size); \
25 }
26
27/// Allocate a new block.
28/// Return 0 if there is no memory left.
29#define listpool_alloc(POOL) listpool_alloc_(&(POOL)->pool)
30
31/// Free the block.
32/// The block pointer is conveniently set to 0.
33#define listpool_free(POOL, ITEM) listpool_free_(&(POOL)->pool, (void**)ITEM)
34
35/// Remove a value from the list.
36/// Defined here instead of DEF_LISTPOOL_IMPL() because not all types may have
37/// an operator==.
38#define listpool_remove(POOL, VAL) \
39 { \
40 listpool_foreach(POOL, iter, { \
41 if (*iter == VAL) { \
42 listpool_free(POOL, &iter); \
43 break; \
44 } \
45 }); \
46 }
47
48/// Return the ith block.
49/// The block must have been allocated.
50#define listpool_get_block(POOL, INDEX) \
51 ((typeof((POOL)->blocks[0])*)listpool_get_block_(&(POOL)->pool, INDEX))
52
53/// Get the index to the given block.
54#define listpool_get_block_index(POOL, BLOCK_PTR) \
55 listpool_get_block_index_(&(POOL)->pool, BLOCK_PTR)
56
57/// Iterate over the used items of the pool.
58///
59/// The caller can use 'i' as the index of the current block.
60///
61/// It is valid to mempool_free() the object at each step of the iteration.
62#define listpool_foreach(POOL, ITER, BODY) \
63 for (list* it_ = (POOL)->pool.used; it_; it_ = it_->next) { \
64 const size_t i = it_ - (POOL)->pool.nodes; \
65 typeof((POOL)->blocks[0])* ITER = &(POOL)->blocks[i]; \
66 (void)ITER; \
67 BODY; \
68 }
69
70typedef struct listpool {
71 size_t block_size_bytes;
72 size_t num_blocks;
73 list* free; // Head of the free list.
74 list* used; // Head of the used list.
75 list* nodes; // Array of nodes.
76 uint8_t* blocks; // Array of blocks;
77} listpool;
78
79/// Create a new list pool from a user-provided array of memory.
80/// `nodes` must have at least `num_blocks` nodes.
81/// `blocks` must be at least `num_blocks` * `block_size_bytes` bytes.
82/// All blocks are zeroed out for convenience.
83void listpool_make_(
84 listpool* pool, list* nodes, void* blocks, size_t num_blocks,
85 size_t block_size_bytes);
86
87/// Allocate a new block.
88/// Return 0 if there is no memory left.
89void* listpool_alloc_(listpool* pool);
90
91/// Free the block.
92/// The block pointer is conveniently set to 0.
93void listpool_free_(listpool* pool, void** block_ptr);
94
95/// Return the ith block.
96/// The block must have been allocated.
97void* listpool_get_block_(const listpool*, size_t block_index);
98
99/// Get the index to the given block.
100size_t listpool_get_block_index_(const listpool*, const void* block);
diff --git a/listpool/src/listpool.c b/listpool/src/listpool.c
deleted file mode 100644
index 758062c..0000000
--- a/listpool/src/listpool.c
+++ /dev/null
@@ -1,92 +0,0 @@
1#include "listpool.h"
2
3#include <string.h>
4
5void listpool_make_(
6 listpool* pool, list* nodes, void* blocks, size_t num_blocks,
7 size_t block_size_bytes) {
8 assert(pool);
9 pool->block_size_bytes = block_size_bytes;
10 pool->num_blocks = num_blocks;
11 pool->free = &nodes[0];
12 pool->used = 0;
13 pool->nodes = nodes;
14 pool->blocks = blocks;
15 list_make(nodes, num_blocks);
16 memset(blocks, 0, num_blocks * block_size_bytes);
17}
18
19void* listpool_alloc_(listpool* pool) {
20 assert(pool);
21 if (!pool->free) {
22 return 0;
23 }
24
25 const size_t index = pool->free - pool->nodes;
26 assert(index < pool->num_blocks);
27
28 list* free = pool->free;
29 pool->free = pool->free->next;
30
31 // pool->used is always the head of the used list, so prepend the new item to
32 // the list.
33 list* new_used = free;
34 new_used->prev = 0;
35 new_used->next = pool->used;
36 if (pool->used) {
37 pool->used->prev = new_used;
38 }
39 pool->used = new_used;
40
41 return pool->blocks + index * pool->block_size_bytes;
42}
43
44void listpool_free_(listpool* pool, void** block_ptr) {
45 assert(pool);
46 assert(block_ptr);
47
48 memset(*block_ptr, 0, pool->block_size_bytes);
49
50 const size_t index =
51 ((uint8_t*)*block_ptr - pool->blocks) / pool->block_size_bytes;
52 assert(index < pool->num_blocks);
53
54 list* item = &pool->nodes[index];
55
56 // We must remove the item from the used list first.
57 if (item->prev) {
58 item->prev->next = item->next;
59 }
60 if (item->next) {
61 item->next->prev = item->prev;
62 }
63 if (item == pool->used) {
64 pool->used = item->next;
65 }
66
67 // pool->free is always the head of the free list, so prepend the new item to
68 // the list. The item is now free to wire after removing it from the used
69 // list.
70 if (!pool->free) {
71 pool->free = item;
72 } else {
73 item->next = pool->free;
74 pool->free->prev = item;
75 pool->free = item;
76 }
77
78 *block_ptr = 0;
79}
80
81void* listpool_get_block_(const listpool* pool, size_t block_index) {
82 assert(pool);
83 assert(block_index < pool->num_blocks);
84 return pool->blocks + block_index * pool->block_size_bytes;
85}
86
87size_t listpool_get_block_index_(const listpool* pool, const void* block) {
88 assert(pool);
89 const size_t block_byte_index = (const uint8_t*)block - pool->blocks;
90 assert(block_byte_index % pool->block_size_bytes == 0);
91 return block_byte_index / pool->block_size_bytes;
92}
diff --git a/listpool/test/listpool_test.c b/listpool/test/listpool_test.c
deleted file mode 100644
index 7a7b0cf..0000000
--- a/listpool/test/listpool_test.c
+++ /dev/null
@@ -1,183 +0,0 @@
1#include "listpool.h"
2
3#include "test.h"
4
5#define NUM_BLOCKS 10
6
7DEF_LISTPOOL(test_pool, int, NUM_BLOCKS);
8
9static int count(test_pool* pool) {
10 int count = 0;
11 listpool_foreach(pool, n, { count++; });
12 return count;
13}
14
15static int sum(test_pool* pool) {
16 int sum = 0;
17 listpool_foreach(pool, n, { sum += *n; });
18 return sum;
19}
20
21// Create a pool.
22TEST_CASE(listpool_create) {
23 test_pool pool;
24 listpool_make(&pool);
25}
26
27// Allocate all N blocks.
28TEST_CASE(listpool_fully_allocate) {
29 test_pool pool;
30 listpool_make(&pool);
31
32 for (int i = 0; i < NUM_BLOCKS; ++i) {
33 const int* block = listpool_alloc(&pool);
34 TEST_TRUE(block != 0);
35 }
36}
37
38// Allocate all N blocks, then free them.
39TEST_CASE(listpool_fill_then_free) {
40 test_pool pool;
41 listpool_make(&pool);
42
43 int* blocks[NUM_BLOCKS] = {0};
44 for (int i = 0; i < NUM_BLOCKS; i++) {
45 blocks[i] = listpool_alloc(&pool);
46 TEST_TRUE(blocks[i] != 0);
47 }
48
49 for (int i = 0; i < NUM_BLOCKS; i++) {
50 listpool_free(&pool, &blocks[i]);
51 TEST_EQUAL(blocks[i], 0); // Pointer should be set to 0 on free.
52 }
53
54 TEST_EQUAL(count(&pool), 0);
55}
56
57// Attempt to allocate blocks past the maximum pool size.
58// The pool should handle the failed allocations gracefully.
59TEST_CASE(listpool_allocate_beyond_max_size) {
60 test_pool pool;
61 listpool_make(&pool);
62
63 // Fully allocate the pool.
64 for (int i = 0; i < NUM_BLOCKS; ++i) {
65 TEST_TRUE(listpool_alloc(&pool) != 0);
66 }
67
68 // Past the end.
69 for (int i = 0; i < NUM_BLOCKS; ++i) {
70 TEST_EQUAL(listpool_alloc(&pool), 0);
71 }
72}
73
74// Free blocks should always remain zeroed out.
75// This tests the invariant right after creating the pool.
76TEST_CASE(listpool_zero_free_blocks_after_creation) {
77 test_pool pool;
78 listpool_make(&pool);
79
80 const int zero = 0;
81 for (int i = 0; i < NUM_BLOCKS; ++i) {
82 const int* block = (const int*)(pool.blocks) + i;
83 TEST_EQUAL(memcmp(block, &zero, sizeof(int)), 0);
84 }
85}
86
87// Free blocks should always remain zeroed out.
88// This tests the invariant after freeing a block.
89TEST_CASE(listpool_zero_free_block_after_free) {
90 test_pool pool;
91 listpool_make(&pool);
92
93 int* val = listpool_alloc(&pool);
94 TEST_TRUE(val != 0);
95 *val = 177;
96
97 int* old_val = val;
98 listpool_free(&pool, &val); // val pointer is set to 0.
99 TEST_EQUAL(*old_val, 0); // Block is zeroed out after free.
100}
101
102// Traverse an empty pool.
103TEST_CASE(listpool_traverse_empty) {
104 test_pool pool;
105 listpool_make(&pool);
106
107 TEST_EQUAL(count(&pool), 0);
108}
109
110// Traverse a partially full pool.
111TEST_CASE(listpool_traverse_partially_full) {
112 const int N = NUM_BLOCKS / 2;
113
114 test_pool pool;
115 listpool_make(&pool);
116
117 for (int i = 0; i < N; ++i) {
118 int* val = listpool_alloc(&pool);
119 TEST_TRUE(val != 0);
120 *val = i + 1;
121 }
122
123 TEST_EQUAL(sum(&pool), (N) * (N + 1) / 2);
124}
125
126// Traverse a full pool.
127TEST_CASE(listpool_traverse_full) {
128 test_pool pool;
129 listpool_make(&pool);
130
131 for (int i = 0; i < NUM_BLOCKS; ++i) {
132 int* val = listpool_alloc(&pool);
133 TEST_TRUE(val != 0);
134 *val = i + 1;
135 }
136
137 TEST_EQUAL(sum(&pool), (NUM_BLOCKS) * (NUM_BLOCKS + 1) / 2);
138}
139
140// Get the ith (allocated) block.
141TEST_CASE(listpool_get_block) {
142 test_pool pool;
143 listpool_make(&pool);
144
145 for (int i = 0; i < NUM_BLOCKS; ++i) {
146 int* block = listpool_alloc(&pool);
147 TEST_TRUE(block != 0);
148 *block = i;
149 TEST_EQUAL(listpool_get_block_index(&pool, block), (size_t)i);
150 }
151
152 for (int i = 0; i < NUM_BLOCKS; ++i) {
153 TEST_EQUAL(*listpool_get_block(&pool, i), i);
154 }
155}
156
157// Remove a value from the list.
158TEST_CASE(listpool_remove_value) {
159 test_pool pool;
160 listpool_make(&pool);
161
162 int* x = listpool_alloc(&pool);
163 int* y = listpool_alloc(&pool);
164 TEST_TRUE(x != 0);
165 TEST_TRUE(y != 0);
166
167 *x = 155;
168 *y = 177;
169
170 listpool_remove(&pool, 155); // x
171
172 TEST_EQUAL(count(&pool), 1);
173 TEST_EQUAL(sum(&pool), *y);
174}
175
176// Stress test.
177//
178// 1. Allocate the pool, either fully or partially. If fully, attempt to
179// allocate some items past the end.
180//
181// 2. Free all allocated items in some random order.
182
183int main() { return 0; }
diff --git a/listpool/test/test.h b/listpool/test/test.h
deleted file mode 100644
index fd8dc22..0000000
--- a/listpool/test/test.h
+++ /dev/null
@@ -1,185 +0,0 @@
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
generated by cgit v1.2.3 (git 2.25.1) at 2024-10-17 22:03:18 +0000