-
Notifications
You must be signed in to change notification settings - Fork 0
/
ds.h
150 lines (116 loc) · 3.03 KB
/
ds.h
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
#ifndef DS_H
#define DS_H
#ifndef CUSTOM_ASSERT
#include <assert.h>
#define CUSTOM_ASSERT(c) assert(c)
#endif
#include <stdlib.h>
#include <math.h>
#include <stdint.h>
#include <stddef.h>
typedef ptrdiff_t size;
#define arrlen(...) (size)(sizeof(__VA_ARGS__) / sizeof(*__VA_ARGS__))
#define pool_header(xs) (((PoolHeader *)xs)[-1])
typedef struct {
size pos; // not including header
void *free, *iter;
} PoolHeader;
typedef struct {
char *buf;
size cap, pos;
} Arena;
typedef struct {
char *buf;
size cap;
size chunk_len;
PoolHeader *free, *iter;
} Pool;
Arena arena_init(size cap);
void *arena_alloc(Arena *al, size len);
Pool pool_init(size num_chunks, size chunk_len);
void *pool_alloc(Pool *al);
void pool_free(Pool *al, void *men);
#define da_header(xs) (((ListHeader *)xs)[-1])
typedef struct {
size len, cap;
} ListHeader;
#define List(T) T *
#define da_cap(xs) (da_header(xs).cap)
#define da_len(xs) (da_header(xs).len)
#define da_init(xs, cap) \
do { \
CUSTOM_ASSERT(cap > 0); \
(xs) = malloc((cap) * sizeof((xs)[0]) + sizeof(ListHeader)); \
CUSTOM_ASSERT((xs) && "Malloc failed!"); \
(xs) += (size) ceil(sizeof(ListHeader) / sizeof((xs)[0])); \
da_cap(xs) = (cap); \
da_len(xs) = 0; \
} while (0);
#define da_push(xs, ...) \
do { \
if (da_len(xs) >= da_cap(xs)) { \
size ncap = da_cap(xs) * 2; \
size c = (size) ceil(sizeof(ListHeader) / sizeof((xs)[0])); \
(xs) -= c; \
(xs) = realloc((xs), ncap * sizeof((xs)[0]) + sizeof(ListHeader)); \
CUSTOM_ASSERT((xs) && "Realloc failed!"); \
(xs) += c; \
da_cap(xs) = ncap; \
} \
(xs)[da_len(xs)++] = __VA_ARGS__; \
} while (0);
#define da_pop(xs) \
do { \
CUSTOM_ASSERT(da_len(xs) > 0); \
da_len(xs) -= 1; \
} while (0);
#define da_last(xs) (xs[da_len(xs) - 1])
#ifdef DS_IMPL
#define DS_IMPL
Arena arena_init(size cap) {
CUSTOM_ASSERT(cap > 0);
Arena al = { .cap = cap, };
al.buf = malloc(al.cap);
return al;
}
void *arena_alloc(Arena *al, size len) {
CUSTOM_ASSERT(al->pos + len <= al->cap && "Not enough memory in arena");
CUSTOM_ASSERT(len > 0);
void *mem = &al->buf[al->pos];
al->pos += len;
return mem;
}
Pool pool_init(size num_chunks, size chunk_len) {
CUSTOM_ASSERT(num_chunks > 0);
CUSTOM_ASSERT(chunk_len > 0);
Pool al = {
.cap = num_chunks * (chunk_len + sizeof(PoolHeader)),
.chunk_len = chunk_len,
};
al.buf = malloc(al.cap);
al.free = (PoolHeader *)(&al.buf[0]);
al.free->pos = sizeof(PoolHeader);
return al;
}
void *pool_alloc(Pool *al) {
CUSTOM_ASSERT(
al->free->pos + al->chunk_len + sizeof(PoolHeader) <= al->cap &&
"Not enough memory in pool"
);
PoolHeader *header = al->free;
if (al->free->free == NULL) {
size pos = header->pos + al->chunk_len;
al->free = (PoolHeader *)(&al->buf[pos]);
al->free->pos = pos;
} else {
al->free = (PoolHeader *)al->free->free;
}
return &al->buf[header->pos];
}
void pool_free(Pool *al, void *mem) {
CUSTOM_ASSERT(mem != NULL);
pool_header(mem).free = al->free;
al->free = &pool_header(mem);
}
#endif
#endif