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
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
|
// buffer.h - Dynamic buffer with metadata
//
// Thread safety: Not thread-safe. External synchronization required.
// Memory safety: NULL-safe on all operations. buffer_resize returns
// original pointer on failure; use buffer_resize_ok for NULL on failure.
// Resize policy: doubles when usage > 80%, halves when < 20% (min 32).
#ifndef BUFFER_H
#define BUFFER_H
#include "type.h"
typedef struct {
u64 n; // Array capacity
u64 i; // Element count
u64 s; // Element size
} buffer_meta_t;
#define _buffer_from_meta(x) ((void *)((u8 *)(x) + sizeof(buffer_meta_t)))
#define _buffer_to_meta(x) ((void *)((u8 *)(x) - sizeof(buffer_meta_t)))
void *buffer_malloc(u64 num, u64 size);
void buffer_free(void *);
void *buffer_resize(void *);
void *buffer_resize_ok(void *);
u64 buffer_count(const void *);
u64 buffer_byte_count(const void *);
u64 buffer_capacity(const void *);
u64 buffer_element_size(const void *);
#endif // BUFFER_H
#ifdef BUFFER_IMPLEMENTATION
#ifndef BUFFER_IMPLEMENTED
#define BUFFER_IMPLEMENTED
#include <stdint.h>
#include <stdlib.h>
// buffer_malloc()
//
// Allocate a dynamic buffer with embedded metadata
//
// n - Initial element capacity
// s - Element size in bytes
//
// return - Pointer to data region, or NULL on failure
void *buffer_malloc(u64 n, u64 s) {
if (n == 0 || s == 0)
return NULL;
if (n > (SIZE_MAX - sizeof(buffer_meta_t)) / s)
return NULL;
void *x = malloc((n * s) + sizeof(buffer_meta_t));
if (!x)
return NULL;
buffer_meta_t *meta = (buffer_meta_t *)x;
meta->i = 0;
meta->n = n;
meta->s = s;
return _buffer_from_meta(x);
}
// buffer_free()
//
// Release a dynamic buffer and its metadata
//
// buffer - Pointer returned by buffer_malloc
void buffer_free(void *buffer) {
if (buffer == NULL)
return;
buffer_meta_t *meta = (buffer_meta_t *)_buffer_to_meta(buffer);
meta->n = 0;
meta->i = 0;
meta->s = 0;
free(_buffer_to_meta(buffer));
}
// buffer_count()
//
// Return the number of elements currently in use
//
// buffer - Pointer to buffer data region
//
// return - Element count, or 0 if buffer is NULL
u64 buffer_count(const void *buffer) {
if (!buffer)
return 0;
buffer_meta_t *meta = (buffer_meta_t *)_buffer_to_meta(buffer);
return meta->i;
}
// buffer_byte_count()
//
// Return the number of bytes currently in use
//
// buffer - Pointer to buffer data region
//
// return - Byte count (count * element size), or 0 if buffer is NULL
u64 buffer_byte_count(const void *buffer) {
if (!buffer)
return 0;
buffer_meta_t *meta = (buffer_meta_t *)_buffer_to_meta(buffer);
if (meta->s == 0 || meta->i > UINT64_MAX / meta->s)
return 0;
return meta->i * meta->s;
}
// buffer_element_size()
//
// Return the size of each element in bytes
//
// buffer - Pointer to buffer data region
//
// return - Element size, or 0 if buffer is NULL
u64 buffer_element_size(const void *buffer) {
if (!buffer)
return 0;
buffer_meta_t *meta = (buffer_meta_t *)_buffer_to_meta(buffer);
return meta->s;
}
// buffer_capacity()
//
// Return the total element capacity
//
// buffer - Pointer to buffer data region
//
// return - Capacity, or 0 if buffer is NULL
u64 buffer_capacity(const void *buffer) {
if (!buffer)
return 0;
buffer_meta_t *meta = (buffer_meta_t *)_buffer_to_meta(buffer);
return meta->n;
}
// buffer_resize()
//
// Automatically resize buffer based on usage ratio. Doubles capacity when
// usage > 80%, halves when < 20% (min 32). Returns original pointer on
// realloc failure — use buffer_resize_ok for NULL on failure.
//
// buffer - Pointer to buffer data region
//
// return - New data pointer (may differ from input), or original on failure
void *buffer_resize(void *buffer) {
if (!buffer)
return NULL;
buffer_meta_t *meta = (buffer_meta_t *)_buffer_to_meta(buffer);
u64 new_n = meta->n;
if (meta->n == 0)
return buffer;
f64 ratio = (f64)meta->i / (f64)meta->n;
if (ratio > 0.8) {
if (new_n > UINT64_MAX / 2)
return buffer;
new_n *= 2;
} else if (ratio < 0.2 && new_n > 32) {
new_n /= 2;
}
if (new_n == meta->n)
return buffer;
if (meta->s == 0 || new_n > (SIZE_MAX - sizeof(buffer_meta_t)) / meta->s)
return buffer;
void *new_meta = realloc(meta, sizeof(buffer_meta_t) + new_n * meta->s);
if (!new_meta)
return buffer;
meta = (buffer_meta_t *)new_meta;
meta->n = new_n;
return _buffer_from_meta(new_meta);
}
// buffer_resize_ok()
//
// Same as buffer_resize, but returns NULL on realloc failure instead of
// the original pointer. Caller must check return value.
//
// buffer - Pointer to buffer data region
//
// return - New data pointer, original if no resize needed, or NULL on failure
void *buffer_resize_ok(void *buffer) {
if (!buffer)
return NULL;
buffer_meta_t *meta = (buffer_meta_t *)_buffer_to_meta(buffer);
u64 old_n = meta->n;
u64 new_n = meta->n;
if (meta->n == 0)
return buffer;
f64 ratio = (f64)meta->i / (f64)meta->n;
if (ratio > 0.8) {
if (new_n > UINT64_MAX / 2)
return buffer;
new_n *= 2;
} else if (ratio < 0.2 && new_n > 32) {
new_n /= 2;
}
if (new_n == old_n)
return buffer;
if (meta->s == 0 || new_n > (SIZE_MAX - sizeof(buffer_meta_t)) / meta->s)
return buffer;
void *new_meta = realloc(meta, sizeof(buffer_meta_t) + new_n * meta->s);
if (!new_meta)
return NULL;
meta = (buffer_meta_t *)new_meta;
meta->n = new_n;
return _buffer_from_meta(meta);
}
#endif /* BUFFER_IMPLEMENTED */
#endif // BUFFER_IMPLEMENTATION
|