-
Notifications
You must be signed in to change notification settings - Fork 113
/
cvector.h
479 lines (438 loc) · 20.5 KB
/
cvector.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
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
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
/*
* Copyright (c) 2015 Evan Teran
*
* License: The MIT License (MIT)
*/
#ifndef CVECTOR_H_
#define CVECTOR_H_
/* cvector heap implemented using C library malloc() */
/* in case C library malloc() needs extra protection,
* allow these defines to be overridden.
*/
#ifndef cvector_clib_free
#include <stdlib.h> /* for free */
#define cvector_clib_free free
#endif
#ifndef cvector_clib_malloc
#include <stdlib.h> /* for malloc */
#define cvector_clib_malloc malloc
#endif
#ifndef cvector_clib_calloc
#include <stdlib.h> /* for calloc */
#define cvector_clib_calloc calloc
#endif
#ifndef cvector_clib_realloc
#include <stdlib.h> /* for realloc */
#define cvector_clib_realloc realloc
#endif
#ifndef cvector_clib_assert
#include <assert.h> /* for assert */
#define cvector_clib_assert assert
#endif
#ifndef cvector_clib_memcpy
#include <string.h> /* for memcpy */
#define cvector_clib_memcpy memcpy
#endif
#ifndef cvector_clib_memmove
#include <string.h> /* for memmove */
#define cvector_clib_memmove memmove
#endif
/* NOTE: Similar to C's qsort and bsearch, you will receive a T*
* for a vector of Ts. This means that you cannot use `free` directly
* as a destructor. Instead if you have for example a cvector_vector_type(int *)
* you will need to supply a function which casts `elem_ptr` to an `int**`
* and then does a free on what that pointer points to:
*
* ex:
*
* void free_int(void *p) { free(*(int **)p); }
*/
typedef void (*cvector_elem_destructor_t)(void *elem_ptr);
typedef struct cvector_metadata_t {
size_t size;
size_t capacity;
cvector_elem_destructor_t elem_destructor;
} cvector_metadata_t;
/**
* @brief cvector_vector_type - The vector type used in this library
*/
#define cvector_vector_type(type) type *
/**
* @brief cvector - Syntactic sugar to retrieve a vector type
*
* @param type The type of vector to act on.
*/
#define cvector(type) cvector_vector_type(type)
/*
* @brief cvector_iterator - The iterator type used for cvector
*/
#define cvector_iterator(type) cvector_vector_type(type)
/**
* @brief cvector_vec_to_base - For internal use, converts a vector pointer to a metadata pointer
* @param vec - the vector
* @return the metadata pointer of the vector
* @internal
*/
#define cvector_vec_to_base(vec) \
(&((cvector_metadata_t *)(vec))[-1])
/**
* @brief cvector_base_to_vec - For internal use, converts a metadata pointer to a vector pointer
* @param ptr - pointer to the metadata
* @return the vector
* @internal
*/
#define cvector_base_to_vec(ptr) \
((void *)&((cvector_metadata_t *)(ptr))[1])
/**
* @brief cvector_capacity - gets the current capacity of the vector
* @param vec - the vector
* @return the capacity as a size_t
*/
#define cvector_capacity(vec) \
((vec) ? cvector_vec_to_base(vec)->capacity : (size_t)0)
/**
* @brief cvector_size - gets the current size of the vector
* @param vec - the vector
* @return the size as a size_t
*/
#define cvector_size(vec) \
((vec) ? cvector_vec_to_base(vec)->size : (size_t)0)
/**
* @brief cvector_elem_destructor - get the element destructor function used
* to clean up elements
* @param vec - the vector
* @return the function pointer as cvector_elem_destructor_t
*/
#define cvector_elem_destructor(vec) \
((vec) ? cvector_vec_to_base(vec)->elem_destructor : NULL)
/**
* @brief cvector_empty - returns non-zero if the vector is empty
* @param vec - the vector
* @return non-zero if empty, zero if non-empty
*/
#define cvector_empty(vec) \
(cvector_size(vec) == 0)
/**
* @brief cvector_reserve - Requests that the vector capacity be at least enough
* to contain n elements. If n is greater than the current vector capacity, the
* function causes the container to reallocate its storage increasing its
* capacity to n (or greater).
* @param vec - the vector
* @param n - Minimum capacity for the vector.
* @return void
*/
#define cvector_reserve(vec, n) \
do { \
size_t cv_cap__ = cvector_capacity(vec); \
if (cv_cap__ < (n)) { \
cvector_grow((vec), (n)); \
} \
} while (0)
/*
* @brief cvector_init - Initialize a vector. The vector must be NULL for this to do anything.
* @param vec - the vector
* @param capacity - vector capacity to reserve
* @param elem_destructor_fn - element destructor function
* @return void
*/
#define cvector_init(vec, capacity, elem_destructor_fn) \
do { \
if (!(vec)) { \
cvector_reserve((vec), capacity); \
cvector_set_elem_destructor((vec), (elem_destructor_fn)); \
} \
} while (0)
/**
* @brief cvector_erase - removes the element at index i from the vector
* @param vec - the vector
* @param i - index of element to remove
* @return void
*/
#define cvector_erase(vec, i) \
do { \
if (vec) { \
const size_t cv_sz__ = cvector_size(vec); \
if ((i) < cv_sz__) { \
cvector_elem_destructor_t elem_destructor__ = cvector_elem_destructor(vec); \
if (elem_destructor__) { \
elem_destructor__(&(vec)[i]); \
} \
cvector_set_size((vec), cv_sz__ - 1); \
cvector_clib_memmove( \
(vec) + (i), \
(vec) + (i) + 1, \
sizeof(*(vec)) * (cv_sz__ - 1 - (i))); \
} \
} \
} while (0)
/**
* @brief cvector_clear - erase all of the elements in the vector
* @param vec - the vector
* @return void
*/
#define cvector_clear(vec) \
do { \
if (vec) { \
cvector_elem_destructor_t elem_destructor__ = cvector_elem_destructor(vec); \
if (elem_destructor__) { \
size_t i__; \
for (i__ = 0; i__ < cvector_size(vec); ++i__) { \
elem_destructor__(&(vec)[i__]); \
} \
} \
cvector_set_size(vec, 0); \
} \
} while (0)
/**
* @brief cvector_free - frees all memory associated with the vector
* @param vec - the vector
* @return void
*/
#define cvector_free(vec) \
do { \
if (vec) { \
void *p1__ = cvector_vec_to_base(vec); \
cvector_elem_destructor_t elem_destructor__ = cvector_elem_destructor(vec); \
if (elem_destructor__) { \
size_t i__; \
for (i__ = 0; i__ < cvector_size(vec); ++i__) { \
elem_destructor__(&(vec)[i__]); \
} \
} \
cvector_clib_free(p1__); \
} \
} while (0)
/**
* @brief cvector_begin - returns an iterator to first element of the vector
* @param vec - the vector
* @return a pointer to the first element (or NULL)
*/
#define cvector_begin(vec) \
(vec)
/**
* @brief cvector_end - returns an iterator to one past the last element of the vector
* @param vec - the vector
* @return a pointer to one past the last element (or NULL)
*/
#define cvector_end(vec) \
((vec) ? &((vec)[cvector_size(vec)]) : NULL)
/* user request to use logarithmic growth algorithm */
#ifdef CVECTOR_LOGARITHMIC_GROWTH
/**
* @brief cvector_compute_next_grow - returns an the computed size in next vector grow
* size is increased by multiplication of 2
* @param size - current size
* @return size after next vector grow
*/
#define cvector_compute_next_grow(size) \
((size) ? ((size) << 1) : 1)
#else
/**
* @brief cvector_compute_next_grow - returns an the computed size in next vector grow
* size is increased by 1
* @param size - current size
* @return size after next vector grow
*/
#define cvector_compute_next_grow(size) \
((size) + 1)
#endif /* CVECTOR_LOGARITHMIC_GROWTH */
/**
* @brief cvector_push_back - adds an element to the end of the vector
* @param vec - the vector
* @param value - the value to add
* @return void
*/
#define cvector_push_back(vec, value) \
do { \
size_t cv_cap__ = cvector_capacity(vec); \
if (cv_cap__ <= cvector_size(vec)) { \
cvector_grow((vec), cvector_compute_next_grow(cv_cap__)); \
} \
(vec)[cvector_size(vec)] = (value); \
cvector_set_size((vec), cvector_size(vec) + 1); \
} while (0)
/**
* @brief cvector_insert - insert element at position pos to the vector
* @param vec - the vector
* @param pos - position in the vector where the new elements are inserted.
* @param val - value to be copied (or moved) to the inserted elements.
* @return void
*/
#define cvector_insert(vec, pos, val) \
do { \
size_t cv_cap__ = cvector_capacity(vec); \
if (cv_cap__ <= cvector_size(vec)) { \
cvector_grow((vec), cvector_compute_next_grow(cv_cap__)); \
} \
if ((pos) < cvector_size(vec)) { \
cvector_clib_memmove( \
(vec) + (pos) + 1, \
(vec) + (pos), \
sizeof(*(vec)) * ((cvector_size(vec)) - (pos))); \
} \
(vec)[(pos)] = (val); \
cvector_set_size((vec), cvector_size(vec) + 1); \
} while (0)
/**
* @brief cvector_pop_back - removes the last element from the vector
* @param vec - the vector
* @return void
*/
#define cvector_pop_back(vec) \
do { \
cvector_elem_destructor_t elem_destructor__ = cvector_elem_destructor(vec); \
if (elem_destructor__) { \
elem_destructor__(&(vec)[cvector_size(vec) - 1]); \
} \
cvector_set_size((vec), cvector_size(vec) - 1); \
} while (0)
/**
* @brief cvector_copy - copy a vector
* @param from - the original vector
* @param to - destination to which the function copy to
* @return void
*/
#define cvector_copy(from, to) \
do { \
if ((from)) { \
cvector_grow(to, cvector_size(from)); \
cvector_set_size(to, cvector_size(from)); \
cvector_clib_memcpy((to), (from), cvector_size(from) * sizeof(*(from))); \
} \
} while (0)
/**
* @brief cvector_swap - exchanges the content of the vector by the content of another vector of the same type
* @param vec - the original vector
* @param other - the other vector to swap content with
* @param type - the type of both vectors
* @return void
*/
#define cvector_swap(vec, other, type) \
do { \
if (vec && other) { \
cvector_vector_type(type) cv_swap__ = vec; \
vec = other; \
other = cv_swap__; \
} \
} while (0)
/**
* @brief cvector_set_capacity - For internal use, sets the capacity variable of the vector
* @param vec - the vector
* @param size - the new capacity to set
* @return void
* @internal
*/
#define cvector_set_capacity(vec, size) \
do { \
if (vec) { \
cvector_vec_to_base(vec)->capacity = (size); \
} \
} while (0)
/**
* @brief cvector_set_size - For internal use, sets the size variable of the vector
* @param vec - the vector
* @param size - the new capacity to set
* @return void
* @internal
*/
#define cvector_set_size(vec, _size) \
do { \
if (vec) { \
cvector_vec_to_base(vec)->size = (_size); \
} \
} while (0)
/**
* @brief cvector_set_elem_destructor - set the element destructor function
* used to clean up removed elements. The vector must NOT be NULL for this to do anything.
* @param vec - the vector
* @param elem_destructor_fn - function pointer of type cvector_elem_destructor_t used to destroy elements
* @return void
*/
#define cvector_set_elem_destructor(vec, elem_destructor_fn) \
do { \
if (vec) { \
cvector_vec_to_base(vec)->elem_destructor = (elem_destructor_fn); \
} \
} while (0)
/**
* @brief cvector_grow - For internal use, ensures that the vector is at least <count> elements big
* @param vec - the vector
* @param count - the new capacity to set
* @return void
* @internal
*/
#define cvector_grow(vec, count) \
do { \
const size_t cv_sz__ = (count) * sizeof(*(vec)) + sizeof(cvector_metadata_t); \
if (vec) { \
void *cv_p1__ = cvector_vec_to_base(vec); \
void *cv_p2__ = cvector_clib_realloc(cv_p1__, cv_sz__); \
cvector_clib_assert(cv_p2__); \
(vec) = cvector_base_to_vec(cv_p2__); \
} else { \
void *cv_p__ = cvector_clib_malloc(cv_sz__); \
cvector_clib_assert(cv_p__); \
(vec) = cvector_base_to_vec(cv_p__); \
cvector_set_size((vec), 0); \
cvector_set_elem_destructor((vec), NULL); \
} \
cvector_set_capacity((vec), (count)); \
} while (0)
/**
* @brief cvector_shrink_to_fit - requests the container to reduce its capacity to fit its size
* @param vec - the vector
* @return void
*/
#define cvector_shrink_to_fit(vec) \
do { \
if (vec) { \
const size_t cv_sz___ = cvector_size(vec); \
cvector_grow(vec, cv_sz___); \
} \
} while (0)
/**
* @brief cvector_at - returns a reference to the element at position n in the vector.
* @param vec - the vector
* @param n - position of an element in the vector.
* @return the element at the specified position in the vector.
*/
#define cvector_at(vec, n) \
((vec) ? (((int)(n) < 0 || (size_t)(n) >= cvector_size(vec)) ? NULL : &(vec)[n]) : NULL)
/**
* @brief cvector_front - returns a reference to the first element in the vector. Unlike member cvector_begin, which returns an iterator to this same element, this function returns a direct reference.
* @return a reference to the first element in the vector container.
*/
#define cvector_front(vec) \
((vec) ? ((cvector_size(vec) > 0) ? cvector_at(vec, 0) : NULL) : NULL)
/**
* @brief cvector_back - returns a reference to the last element in the vector.Unlike member cvector_end, which returns an iterator just past this element, this function returns a direct reference.
* @return a reference to the last element in the vector.
*/
#define cvector_back(vec) \
((vec) ? ((cvector_size(vec) > 0) ? cvector_at(vec, cvector_size(vec) - 1) : NULL) : NULL)
/**
* @brief cvector_resize - resizes the container to contain count elements.
* @param vec - the vector
* @param count - new size of the vector
* @param value - the value to initialize new elements with
* @return void
*/
#define cvector_resize(vec, count, value) \
do { \
if (vec) { \
size_t cv_sz_count__ = (size_t)(count); \
size_t cv_sz__ = cvector_vec_to_base(vec)->size; \
if (cv_sz_count__ > cv_sz__) { \
cvector_reserve((vec), cv_sz_count__); \
cvector_set_size((vec), cv_sz_count__); \
do { \
(vec)[cv_sz__++] = (value); \
} while (cv_sz__ < cv_sz_count__); \
} else { \
while (cv_sz_count__ < cv_sz__--) { \
cvector_pop_back(vec); \
} \
} \
} \
} while (0)
#endif /* CVECTOR_H_ */