blob: 66c63d1b1fd78277ddbff3394b52c887b2637eec (
plain)
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
|
#include <stdint.h>
#include <stdlib.h>
struct Chunk {
struct Chunk *prev;
struct Chunk *next;
int used;
size_t size;
};
void
Chunk_ctor(struct Chunk *self, size_t size)
{
self->prev = NULL;
self->next = NULL;
self->used = 0;
self->size = size - sizeof(struct Chunk);
}
static struct Chunk *begin = NULL;
void
alloc_init(void *mem, size_t size)
{
if (size < sizeof(struct Chunk)) return;
begin = (struct Chunk *)mem;
Chunk_ctor(begin, size);
}
void *
malloc(size_t size)
{
if (begin == NULL) return NULL;
// find free chunk that is at least (size + sizeof(struct Chunk))
for (struct Chunk *iter = begin; iter != NULL; iter = iter->next) {
if (iter->used != 0 || iter->size < size) continue;
// if there's at least sizeof(struct Chunk) bytes left over, create a new Chunk
if (iter->size >= (size + 2 * sizeof(struct Chunk))) {
struct Chunk *next = (struct Chunk *)((uintptr_t)iter + sizeof(struct Chunk) + size);
Chunk_ctor(next, iter->size - size - sizeof(struct Chunk));
next->prev = iter;
iter->size = size;
iter->next = next;
}
iter->used = 1;
return (void *)((uintptr_t)iter + sizeof(struct Chunk));
}
return NULL;
}
void
free(void *ptr)
{
if (ptr == NULL) return;
struct Chunk *chunk = (struct Chunk *)((uintptr_t)ptr - sizeof(struct Chunk));
chunk->used = 0;
// merge next chunk
if (chunk->next != NULL && chunk->next->used == 0) {
chunk->size += chunk->next->size + sizeof(struct Chunk);
chunk->next = chunk->next->next;
if (chunk->next != NULL) chunk->next->prev = chunk;
}
// merge into prev chunk
if (chunk->prev != NULL && chunk->prev->used == 0) {
chunk->prev->size += chunk->size + sizeof(struct Chunk);
chunk->prev->next = chunk->next;
if (chunk->next != NULL) chunk->next->prev = chunk->prev;
}
}
|
