aboutsummaryrefslogtreecommitdiff
path: root/mempool
diff options
context:
space:
mode:
Diffstat (limited to 'mempool')
-rw-r--r--mempool/README.md23
-rw-r--r--mempool/include/mempool.h8
-rw-r--r--mempool/src/mempool.c24
-rw-r--r--mempool/test/mempool_test.c34
4 files changed, 48 insertions, 41 deletions
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..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.
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
generated by cgit v1.2.3 (git 2.25.1) at 2025-09-19 04:12:09 +0000