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
|
/*
* Block-based Memory Allocator.
*
* Clients should use the macros to define and use allocators. They make the API
* type-safe.
*
* Like a pool/block-based allocator, this allocator stores data in fixed-size
* blocks. However, this allocator also supports allocation of contiguous chunks
* of a variable number of blocks.
*
* Chunk 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 typed memory allocator backed by a statically-allocated array.
#define DEF_MEM(MEM, TYPE, NUM_BLOCKS) \
typedef struct MEM { \
Memory mem; \
Chunk chunks[NUM_BLOCKS]; \
TYPE blocks[NUM_BLOCKS]; \
} MEM;
/// Define a typed memory allocator backed by a dynamically-allocated array.
#define DEF_MEM_DYN(MEM, TYPE) \
typedef struct MEM { \
Memory mem; \
Chunk* chunks; \
TYPE* blocks; \
} MEM;
/// Initialize a statically-backed memory allocator.
#define mem_make(MEM) \
{ \
assert(MEM); \
const size_t block_size = sizeof((MEM)->blocks[0]); \
const size_t num_blocks = sizeof((MEM)->blocks) / block_size; \
mem_make_( \
&(MEM)->mem, (MEM)->chunks, (MEM)->blocks, num_blocks, block_size); \
}
/// Initialize a dynamically-backed memory allocator.
#define mem_make_dyn(MEM, num_blocks, block_size) \
mem_make_(&(MEM)->mem, 0, 0, num_blocks, block_size)
/// Destroy the allocator.
///
/// If the allocator is dynamically-backed, then this function frees the
/// underlying memory.
#define mem_del(MEM) mem_del_(&(MEM)->mem)
/// Clear the allocator.
///
/// This function frees all of the allocator's blocks. The resulting allocator
/// is as if it were newly created.
#define mem_clear(MEM) mem_clear_(&(MEM)->mem)
/// Allocate a new chunk of N blocks.
/// Return a pointer to the first block of the chunk, or 0 if there is no memory
/// left.
/// New chunks are conveniently zeroed out.
#define mem_alloc(MEM, num_blocks) mem_alloc_(&(MEM)->mem, num_blocks)
/// Free the chunk.
/// The chunk pointer is conveniently set to 0.
#define mem_free(MEM, CHUNK) mem_free_(&(MEM)->mem, (void**)CHUNK)
/// Return a pointer to a chunk given the chunk's handle.
/// The chunk must have been allocated.
#define mem_get_chunk(MEM, HANDLE) \
((__typeof__((MEM)->blocks[0])*)mem_get_chunk_(&(MEM)->mem, HANDLE))
/// Get the handle to the given chunk.
#define mem_get_chunk_handle(MEM, CHUNK_PTR) \
mem_get_chunk_handle_(&(MEM)->mem, CHUNK_PTR)
/// Iterate over the used chunks of the allocator.
///
/// The caller can use 'i' as the index of the current chunk.
///
/// It is valid to mem_free() the chunk at each step of the iteration.
#define mem_foreach(MEM, ITER, BODY) \
size_t i = 0; \
do { \
if ((MEM)->chunks[i].used) { \
__typeof__((MEM)->blocks[0])* ITER = &(MEM)->blocks[i]; \
(void)ITER; \
BODY; \
} \
i = (MEM)->chunks[i].next; \
} while (i);
// -----------------------------------------------------------------------------
/// Chunk information.
///
/// Every chunk represents a contiguous array of some number of blocks. The
/// allocator begins as one big unused chunk.
///
/// Allocation looks for a free chunk large enough to hold to requested number
/// of blocks. If the free chunk is larger than the requested chunk size, then
/// the requested chunk is carved out of the larger block.
///
/// Deallocation frees the chunk back and merges it with free neighbouring
/// chunks. Two free chunks are never contiguous in memory.
///
/// 'next' and 'prev' always point to a valid chunk (e.g., 0). Allocation stops
/// looking for free chunks when it loops over.
typedef struct Chunk {
size_t num_blocks;
size_t prev;
size_t next;
bool used;
} Chunk;
typedef struct Memory {
size_t block_size_bytes;
size_t num_blocks;
size_t next_free_chunk;
bool dynamic; /// True if blocks and chunks are dynamically-allocated.
Chunk* chunks; /// Array of chunk information.
uint8_t* blocks; /// Array of blocks;
} Memory;
/// Create a memory allocator.
///
/// 'chunks' and 'blocks' may be user-provided (statically-backed allocator) or
/// null (dynamically-backed allocator).
/// - If null, the allocator malloc()s the memory for them.
/// - If given:
/// - `chunks` must be at least `num_blocks` chunks.
/// - `blocks` must be at least `num_blocks` * `block_size_bytes` bytes.
///
/// All blocks are zeroed out for convenience.
bool mem_make_(
Memory* mem, Chunk* chunks, void* blocks, size_t num_blocks,
size_t block_size_bytes);
void mem_del_(Memory*);
void mem_clear_(Memory*);
void* mem_alloc_(Memory*, size_t num_blocks);
void mem_free_(Memory*, void** chunk_ptr);
void* mem_get_chunk_(const Memory*, size_t chunk_handle);
size_t mem_get_chunk_handle_(const Memory*, const void* chunk);
|
