aboutsummaryrefslogtreecommitdiff
path: root/mem/src/mem.c
diff options
context:
space:
mode:
Diffstat (limited to 'mem/src/mem.c')
-rw-r--r--mem/src/mem.c183
1 files changed, 183 insertions, 0 deletions
diff --git a/mem/src/mem.c b/mem/src/mem.c
new file mode 100644
index 0000000..ff97f0f
--- /dev/null
+++ b/mem/src/mem.c
@@ -0,0 +1,183 @@
1#include "mem.h"
2
3#include <stdlib.h>
4#include <string.h>
5
6bool mem_make_(
7 Memory* mem, Chunk* chunks, void* blocks, size_t num_blocks,
8 size_t block_size_bytes) {
9 assert(mem);
10 assert((chunks && blocks) || (!chunks && !blocks));
11 assert(num_blocks >= 1);
12
13 mem->block_size_bytes = block_size_bytes;
14 mem->num_blocks = num_blocks;
15 mem->next_free_chunk = 0;
16
17 // Allocate chunks and blocks if necessary and zero them out.
18 if (!chunks) {
19 chunks = calloc(num_blocks, sizeof(Chunk));
20 blocks = calloc(num_blocks, block_size_bytes);
21 mem->dynamic = true;
22 if (!chunks || !blocks) {
23 return false;
24 }
25 } else {
26 memset(blocks, 0, num_blocks * block_size_bytes);
27 memset(chunks, 0, num_blocks * sizeof(Chunk));
28 mem->dynamic = false;
29 }
30 mem->chunks = chunks;
31 mem->blocks = blocks;
32
33 // Initialize the head as one large free chunk.
34 Chunk* head = &mem->chunks[0];
35 head->num_blocks = num_blocks;
36
37 return true;
38}
39
40void mem_del_(Memory* mem) {
41 assert(mem);
42 if (mem->dynamic) {
43 if (mem->chunks) {
44 free(mem->chunks);
45 mem->chunks = 0;
46 }
47 if (mem->blocks) {
48 free(mem->blocks);
49 mem->blocks = 0;
50 }
51 }
52}
53
54void mem_clear_(Memory* mem) {
55 assert(mem);
56 mem->next_free_chunk = 0;
57 memset(mem->blocks, 0, mem->num_blocks * mem->block_size_bytes);
58 memset(mem->chunks, 0, mem->num_blocks * sizeof(Chunk));
59
60 // Initialize the head as one large free chunk.
61 Chunk* head = &mem->chunks[0];
62 head->num_blocks = mem->num_blocks;
63}
64
65void* mem_alloc_(Memory* mem, size_t num_blocks) {
66 assert(mem);
67 assert(num_blocks >= 1);
68
69 // Search for the first free chunk that can accommodate num_blocks.
70 const size_t start = mem->next_free_chunk;
71 size_t chunk_idx = start;
72 bool found = false;
73 do {
74 Chunk* chunk = &mem->chunks[chunk_idx];
75 if (!chunk->used) {
76 if (chunk->num_blocks > num_blocks) {
77 // Carve out a smaller chunk when the found chunk is larger than
78 // requested.
79 // [prev] <--> [chunk] <--> [new next] <--> [next]
80 const size_t new_next_idx = chunk_idx + num_blocks;
81 Chunk* new_next = &mem->chunks[new_next_idx];
82 if (chunk->next) {
83 mem->chunks[chunk->next].prev = new_next_idx;
84 }
85 new_next->prev = chunk_idx;
86 new_next->next = chunk->next;
87 chunk->next = new_next_idx;
88
89 new_next->num_blocks = chunk->num_blocks - num_blocks;
90 chunk->num_blocks = num_blocks;
91
92 chunk->used = true;
93 found = true;
94 break;
95 } else if (chunk->num_blocks == num_blocks) {
96 chunk->used = true;
97 found = true;
98 break;
99 }
100 }
101 chunk_idx = chunk->next; // Last chunk points back to 0, which is always the
102 // start of some chunk. 'next' and 'prev' are
103 // always valid pointers.
104 } while (chunk_idx != start);
105
106 if (found) {
107 mem->next_free_chunk = mem->chunks[chunk_idx].next;
108 return &mem->blocks[chunk_idx * mem->block_size_bytes];
109 } else {
110 return 0; // Large-enough free chunk not found.
111 }
112}
113
114// The given pointer is a pointer to this first block of the chunk.
115void mem_free_(Memory* mem, void** chunk_ptr) {
116 assert(mem);
117 assert(chunk_ptr);
118
119 const size_t chunk_idx =
120 ((uint8_t*)*chunk_ptr - mem->blocks) / mem->block_size_bytes;
121 assert(chunk_idx < mem->num_blocks);
122 Chunk* chunk = &mem->chunks[chunk_idx];
123
124 // Disallow double-frees.
125 assert(chunk->used);
126
127 // Zero out the chunk so that we don't get stray values the next time it is
128 // allocated.
129 memset(&mem->blocks[chunk_idx], 0, chunk->num_blocks * mem->block_size_bytes);
130
131 // Free the chunk. If it is contiguous with other free chunks, then merge.
132 // We only need to look at the chunk's immediate neighbours because no two
133 // free chunks are left contiguous after merging.
134 chunk->used = false;
135 if (chunk->next) {
136 Chunk* next = &mem->chunks[chunk->next];
137 if (!next->used) {
138 // Pre: [chunk] <--> [next] <--> [next next]
139 // Post: [ chunk + next ] <--> [next next]
140 chunk->num_blocks += mem->chunks[chunk->next].num_blocks;
141 chunk->next = next->next;
142 if (next->next) {
143 Chunk* next_next = &mem->chunks[next->next];
144 next_next->prev = chunk_idx;
145 }
146 next->prev = next->next = next->num_blocks = 0;
147 }
148 }
149 if (chunk->prev) {
150 Chunk* prev = &mem->chunks[chunk->prev];
151 if (!prev->used) {
152 // Pre: [prev] <--> [chunk] <--> [next]
153 // Post: [ prev + chunk ] <--> [next]
154 prev->num_blocks += chunk->num_blocks;
155 prev->next = chunk->next;
156 if (chunk->next) {
157 Chunk* next = &mem->chunks[chunk->next];
158 next->prev = chunk->prev;
159 }
160 chunk->prev = chunk->next = chunk->num_blocks = 0;
161 }
162 }
163
164 *chunk_ptr = 0;
165}
166
167// The handle is the chunk's index. We don't call it an index in the public API
168// because from the user's perspective, two chunks allocated back-to-back need
169// not be +1 away (the offset depends on how large the first chunk is).
170void* mem_get_chunk_(const Memory* mem, size_t chunk_handle) {
171 assert(mem);
172 assert(chunk_handle < mem->num_blocks);
173 assert(mem->chunks[chunk_handle].used);
174 return &mem->blocks[chunk_handle * mem->block_size_bytes];
175}
176
177// The given chunk pointer is a pointer to the blocks array.
178size_t mem_get_chunk_handle_(const Memory* mem, const void* chunk) {
179 assert(mem);
180 const size_t block_byte_index = (const uint8_t*)chunk - mem->blocks;
181 assert(block_byte_index % mem->block_size_bytes == 0);
182 return block_byte_index / mem->block_size_bytes;
183}