1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
|
/*
* Block/Pool Allocator.
*
* Clients should use the macros to define and use pools. They make the API
* type-safe.
*
* The pool allocator works on one big chunk of memory, which can be statically
* or dynamically allocated. This chunk is divided into fixed-sized blocks.
* Allocation/deallocation happens with block granularity.
*
* Block information is stored in a separate array so that client data is
* contiguous in the main pool of memory and better cached.
*/
#pragma once
#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
/// Define a statically-allocated, typed pool of the given number of blocks.
#define DEF_MEMPOOL(POOL, TYPE, NUM_BLOCKS) \
typedef struct POOL { \
mempool pool; \
BlockInfo block_info[NUM_BLOCKS]; \
TYPE blocks[NUM_BLOCKS]; \
/* For uniformity with the dynamically-allocated pool. */ \
TYPE* object; \
} POOL;
/// Define a dynamically-allocated, typed pool.
#define DEF_MEMPOOL_DYN(POOL, TYPE) \
typedef struct POOL { \
mempool pool; \
/* Does not point anywhere. Storing a pointer here so that we can recall \
* the type. */ \
TYPE* object; \
} POOL;
/// Initialize a statically-allocated pool.
#define mempool_make(POOL) \
{ \
assert(POOL); \
const size_t block_size = sizeof((POOL)->blocks[0]); \
const size_t num_blocks = sizeof((POOL)->blocks) / block_size; \
mempool_make_( \
&(POOL)->pool, (POOL)->block_info, (POOL)->blocks, num_blocks, \
block_size); \
}
/// Initialize a dynamically-allocated pool.
#define mempool_make_dyn(POOL, num_blocks, block_size) \
mempool_make_(&(POOL)->pool, 0, 0, num_blocks, block_size)
/// Destroy the pool.
///
/// If the pool is dynamically allocated, then this function frees its memory.
#define mempool_del(POOL) mempool_del_(&(POOL)->pool)
/// Clear the pool.
///
/// This function frees all of the pool's blocks. The resulting pool is as if it
/// were newly created.
#define mempool_clear(POOL) mempool_clear_(&(POOL)->pool)
/// Allocate a new block.
/// Return 0 if there is no memory left.
/// When there is no space left in the pool, allocation can either trap
/// (default) or gracefully return 0. Call mem_enable_traps() to toggle this
/// behaviour.
/// New blocks are conveniently zeroed out.
#define mempool_alloc(POOL) mempool_alloc_(&(POOL)->pool)
/// Free the block.
/// The block pointer is conveniently set to 0.
#define mempool_free(POOL, BLOCK_PTR) \
assert(*BLOCK_PTR); \
mempool_free_(&(POOL)->pool, (void**)BLOCK_PTR)
/// Return the ith block.
/// The block must have been allocated.
#define mempool_get_block(POOL, INDEX) \
((__typeof__((POOL)->object[0])*)mempool_get_block_(&(POOL)->pool, INDEX))
/// Get the index to the given block.
#define mempool_get_block_index(POOL, BLOCK_PTR) \
mempool_get_block_index_(&(POOL)->pool, BLOCK_PTR)
/// Return the block size in bytes.
#define mempool_block_size_bytes(POOL) mempool_block_size_bytes_(&(POOL)->pool)
/// Return the total capacity of the mempool.
#define mempool_capacity(POOL) mempool_capacity_(&(POOL)->pool)
/// Return the number of used blocks in the mempool.
#define mempool_size(POOL) mempool_size_(&(POOL)->pool)
/// Set whether to trap when attempting to allocate beyond capacity.
#define mempool_enable_traps(POOL, enable) \
mempool_enable_traps_(&(POOL)->pool, enable)
/// Iterate over the used blocks of the pool.
///
/// The caller can use 'i' as the index of the current block.
///
/// It is valid to mempool_free() the object at each step of the iteration.
#define mempool_foreach(POOL, ITER, BODY) \
{ \
size_t i = (POOL)->pool.used; \
if ((POOL)->pool.num_used_blocks > 0) { \
do { \
if ((POOL)->pool.block_info[i].used) { \
__typeof__((POOL)->object[0])* ITER = \
&(((__typeof__((POOL)->object[0])*)(POOL)->pool.blocks))[i]; \
(void)ITER; \
BODY; \
} \
const size_t next = (POOL)->pool.block_info[i].next_used; \
if (next == i) { \
break; \
} \
i = next; \
} while (true); \
} \
}
// -----------------------------------------------------------------------------
typedef struct BlockInfo {
size_t next_free; /// For free blocks, points to the next free block.
size_t next_used; /// For used blocks, points to the next used block.
bool used;
} BlockInfo;
/// Memory pool.
///
/// 'head' and 'used' always points to a valid block (e.g., 0).
/// The implementation must check whether the head of the lists are used/free.
/// For example, iteration must stop when it finds the first unused block
/// (BlockInfo.used == 0).
typedef struct mempool {
size_t block_size_bytes;
size_t num_blocks;
size_t num_used_blocks;
size_t head; /// Points to the first block in the free list.
size_t used; /// Points to the first block in the used list.
bool dynamic; /// True if blocks and info are dynamically-allocated.
bool trap; /// Whether to trap when allocating beyond capacity.
BlockInfo* block_info;
uint8_t* blocks;
} mempool;
/// Create a pool allocator.
///
/// 'BlockInfo' and 'blocks' may be user-provided (static pool) or null (dynamic
/// pool).
/// - If null, the pool malloc()s the memory for them.
/// - If given:
/// - `BlockInfo` must hold at least `num_blocks` entries.
/// - `blocks` must be at least `num_blocks` * `block_size_bytes` bytes.
///
/// All blocks are zeroed out for convenience.
bool mempool_make_(
mempool*, BlockInfo*, void* blocks, size_t num_blocks,
size_t block_size_bytes);
void mempool_del_(mempool*);
void mempool_clear_(mempool*);
void* mempool_alloc_(mempool*);
void mempool_free_(mempool*, void** block_ptr);
void* mempool_get_block_(const mempool*, size_t block_index);
size_t mempool_get_block_index_(const mempool*, const void* block);
size_t mempool_block_size_bytes_(const mempool*);
size_t mempool_capacity_(const mempool*);
size_t mempool_size_(const mempool*);
void mempool_enable_traps_(mempool*, bool);
|
