-
Notifications
You must be signed in to change notification settings - Fork 0
/
dlb_vector.h
176 lines (157 loc) · 6.73 KB
/
dlb_vector.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
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
#ifndef DLB_VECTOR_H
#define DLB_VECTOR_H
//------------------------------------------------------------------------------
// Copyright 2018 Dan Bechard
//------------------------------------------------------------------------------
//-- header --------------------------------------------------------------------
#include "dlb_memory.h"
typedef struct dlb_vec__hdr {
size_t len; // current # of elements
size_t cap; // capacity in # of elements
size_t elem_size; // size of each element
size_t fixed; // 0 = dynamic allocation (min 16, 2x resize), 1 = fixed-size array (assert/no-op on resize)
} dlb_vec__hdr;
#define dlb_vec_hdr(b) ((b) ? ((dlb_vec__hdr *)((u8 *)(b) - sizeof(dlb_vec__hdr))) : 0)
//#define dlb_vec_hdr(b) ((b) ? (((dlb_vec__hdr *)(b)) - 1) : 0)
#define dlb_vec_len(b) ((b) ? dlb_vec_hdr(b)->len : 0)
#define dlb_vec_cap(b) ((b) ? dlb_vec_hdr(b)->cap : 0)
#define dlb_vec_elem_size(b) ((b) ? dlb_vec_hdr(b)->elem_size : 0)
#define dlb_vec_fixed(b) ((b) ? dlb_vec_hdr(b)->fixed : 0)
#define dlb_vec_empty(b) (dlb_vec_len(b) == 0)
#define dlb_vec_size(b) ((b) ? dlb_vec_len(b) * dlb_vec_elem_size(b) : 0)
#define dlb_vec_end(b) ((b) + dlb_vec_len(b))
#define dlb_vec_end_size(b, s) (void *)((char *)(b) + dlb_vec_len(b) * s)
#define dlb_vec_each(t, i, b) for (t (i) = (b); (i) != dlb_vec_end(((t)b)); (i)++)
#define dlb_vec_range(t, i, s, e) for (t (i) = (s); (i) != (e); (i)++)
#define dlb_vec_last(b) (dlb_vec_len(b) ? &(b)[dlb_vec_len(b) - 1] : 0)
#define dlb_vec_last_size(b, s) (dlb_vec_len(b) ? (void *)((char *)(b) + (s) * (dlb_vec_len(b) - 1)) : 0)
#define dlb_vec_index_size(b, i, s) (dlb_vec_len(b) ? (void *)((char *)(b) + (s) * (i)) : 0)
#define dlb_vec_reserved_bytes(b) ((b) ? dlb_vec_cap(b) * dlb_vec_elem_size(b) : 0)
#define dlb_vec_reserve(b, n) \
((n) <= dlb_vec_cap(b) ? 0 : ((b) = dlb_vec__grow((b), (n), sizeof(*(b)), 0)))
#define dlb_vec_reserve_size(b, n, s) \
((n) <= dlb_vec_cap(b) ? 0 : ((b) = dlb_vec__grow((b), (n), (s), 0)))
#define dlb_vec_reserve_fixed(b, n) \
((n) <= dlb_vec_cap(b) ? 0 : ((b) = dlb_vec__grow((b), (n), sizeof(*(b)), 1)))
#define dlb_vec_push(b, v) \
(dlb_vec_reserve((b), 1 + dlb_vec_len(b)), \
((b)[dlb_vec_hdr(b)->len++] = (v)), \
dlb_vec_last(b))
#define dlb_vec_alloc(b) \
(dlb_vec_reserve((b), 1 + dlb_vec_len(b)), \
dlb_vec_hdr(b)->len++, \
dlb_vec_last(b))
#define dlb_vec_alloc_size(b, s) \
(dlb_vec_reserve_size((b), 1 + dlb_vec_len(b), (s)), \
dlb_vec_hdr(b)->len++, \
dlb_vec_last_size(b, s))
#define dlb_vec_alloc_count(b, n) \
(dlb_vec_reserve((b), n + dlb_vec_len(b)), \
dlb_vec_hdr(b)->len += n)
#define dlb_vec_alloc_count_size(b, n, s) \
(dlb_vec_reserve_size((b), n + dlb_vec_len(b), (s)), \
dlb_vec_hdr(b)->len += n)
// Pop & return pointer to last element, returns 0 if empty
// TODO: Why would you return pointer to something that was just removed? It should return
// a copy of the object, or force the caller to use dlb_vec_last() before calling this.
#define dlb_vec_pop(b) \
(dlb_vec_len(b) > 0 ? \
dlb_vec_hdr(b)->len--, \
(&(b)[dlb_vec_len(b)]) \
: 0)
// Pop & zero last element, returns true on success, false if empty
#define dlb_vec_popz(b) \
(dlb_vec_len(b) > 0 ? \
(dlb_memset(dlb_vec_last(b), 0, sizeof(*(b))), \
dlb_vec_hdr(b)->len--, \
1) \
: 0)
#define dlb_vec_popz_size(b, s) \
(dlb_vec_len(b) > 0 ? \
(dlb_memset(dlb_vec_last_size((b), (s)), 0, (s)), \
dlb_vec_hdr(b)->len--, \
1) \
: 0)
#define dlb_vec_clear(b) (dlb_vec_len(b) > 0 ? dlb_vec_hdr(b)->len = 0 : 0)
#define dlb_vec_zero(b) \
(dlb_vec_cap(b) > 0 ? \
(dlb_memset(b, 0, dlb_vec_reserved_bytes(b)), \
dlb_vec_hdr(b)->len = 0) \
: 0)
#define dlb_vec_free(b) ((b) ? (dlb_free(dlb_vec_hdr(b)), (b) = NULL) : 0)
// NOTE: This will obviously resize the buffer, so it's not really const, but if I remove the const from the decl then
// for some reason MSVC whines about all of the dlb_vec_push calls that operate on `const char **` vectors. *shrugs*
void *dlb_vec__grow(const void *buf, size_t len, size_t elem_size, size_t fixed);
#endif
//-- end of header -------------------------------------------------------------
#ifdef __INTELLISENSE__
/* This makes MSVC intellisense work. */
#define DLB_VECTOR_IMPLEMENTATION
#endif
//-- implementation ------------------------------------------------------------
#ifdef DLB_VECTOR_IMPLEMENTATION
#ifndef DLB_VECTOR_IMPL_INTERNAL
#define DLB_VECTOR_IMPL_INTERNAL
#include "dlb_types.h"
#define DLB_MEMORY_IMPLEMENTATION
#include "dlb_memory.h"
#include <assert.h>
void *dlb_vec__grow(const void *buf, size_t len, size_t elem_size, size_t fixed) {
dlb_vec__hdr *hdr = dlb_vec_hdr(buf);
if (hdr && hdr->fixed) {
assert(!hdr->fixed); // don't allow resize of fixed arrays
// TODO: Make this safer in release mode; this just returns the same buffer with no resize
return (void *)buf;
}
size_t cap = dlb_vec_cap(buf);
assert(cap <= (SIZE_MAX - 1) / 2);
size_t new_cap = MAX(!fixed * 16, MAX(2 * cap, len));
assert(len <= new_cap);
assert(new_cap);
assert(new_cap <= (SIZE_MAX - sizeof(dlb_vec__hdr))/elem_size);
size_t new_size = sizeof(dlb_vec__hdr) + new_cap * elem_size;
if (hdr) {
size_t old_size = sizeof(dlb_vec__hdr) + hdr->cap * elem_size;
hdr = (dlb_vec__hdr *)dlb_realloc(hdr, new_size);
dlb_memset((char *)hdr + old_size, 0, new_size - old_size);
} else {
hdr = (dlb_vec__hdr *)dlb_calloc(1, new_size);
hdr->len = 0;
hdr->fixed = fixed;
}
hdr->cap = new_cap;
hdr->elem_size = elem_size;
char *new_buf = (char *)hdr + sizeof(dlb_vec__hdr);
assert(new_buf);
return new_buf;
}
#endif
#endif
//-- end of implementation -----------------------------------------------------
//-- tests ---------------------------------------------------------------------
#ifdef DLB_VECTOR_TEST
static void *dlb_vec_test()
{
int *store = NULL;
for (int i = 0; i < 1024; i++) {
dlb_vec_push(store, i);
}
assert(dlb_vec_len(store) == 1024);
for (u32 i = 0; i < dlb_vec_len(store); i++) {
assert(store[i] == i);
}
dlb_vec_free(store);
}
#endif
//-- end of tests --------------------------------------------------------------
#if 0
//-- notes ---------------------------------------------------------------------
// Consider instrusive array for the first 16 elements if cache is bottleneck?
typedef struct cc_vector {
void *begin; // dlb_vec
void *end; // dlb_vec
size_t capacity; // current capacity
char buffer[16]; // C++: sizeof(T) * count
} cc_vector;
//-- end of tests --------------------------------------------------------------
#endif