CVector 4.3.0
A C++ style vector library in strict ANSI C (C89)
Loading...
Searching...
No Matches
cvector_template2.h
Go to the documentation of this file.
1#ifndef CVECTOR_TYPE_H
2#define CVECTOR_TYPE_H
3
4#ifndef CVEC_SIZE_T
5#include <stdlib.h>
6#define CVEC_SIZE_T size_t
7#endif
8
9#ifndef CVEC_SZ
10#define CVEC_SZ
12#endif
13
14#ifdef __cplusplus
15extern "C" {
16#endif
17
18
19typedef struct cvector_TYPE
20{
21 TYPE* a;
24 void (*elem_free)(void*);
25 int (*elem_init)(void*, void*);
27
29
30int cvec_TYPE(cvector_TYPE* vec, cvec_sz size, cvec_sz capacity, void(*elem_free)(void*), int(*elem_init)(void*, void*));
31int cvec_init_TYPE(cvector_TYPE* vec, TYPE* vals, cvec_sz num, void(*elem_free)(void*), int(*elem_init)(void*, void*));
32
33cvector_TYPE* cvec_TYPE_heap(cvec_sz size, cvec_sz capacity, void (*elem_free)(void*), int(*elem_init)(void*, void*));
34cvector_TYPE* cvec_init_TYPE_heap(TYPE* vals, cvec_sz num, void (*elem_free)(void*), int(*elem_init)(void*, void*));
35
36int cvec_copyc_TYPE(void* dest, void* src);
38
39int cvec_push_TYPE(cvector_TYPE* vec, TYPE* val);
40void cvec_pop_TYPE(cvector_TYPE* vec, TYPE* ret);
41
42int cvec_pushm_TYPE(cvector_TYPE* vec, TYPE* a);
43void cvec_popm_TYPE(cvector_TYPE* vec, TYPE* ret);
46void cvec_replacem_TYPE(cvector_TYPE* vec, cvec_sz i, TYPE* a, TYPE* ret);
47
51int cvec_replace_TYPE(cvector_TYPE* vec, cvec_sz i, TYPE* a, TYPE* ret);
55#define cvec_shrink_to_fit_TYPE(vec) cvec_set_cap_TYPE((vec), (vec)->size)
59
61
63void cvec_free_TYPE_heap(void* vec);
64void cvec_free_TYPE(void* vec);
65
66#ifdef __cplusplus
67}
68#endif
69
70/* CVECTOR_TYPE_H */
71#endif
72
73
74#ifdef CVECTOR_TYPE_IMPLEMENTATION
75
77
78#define CVEC_TYPE_ALLOCATOR(x) ((x+1) * 2)
79
80#if defined(CVEC_MALLOC) && defined(CVEC_FREE) && defined(CVEC_REALLOC)
81/* ok */
82#elif !defined(CVEC_MALLOC) && !defined(CVEC_FREE) && !defined(CVEC_REALLOC)
83/* ok */
84#else
85#error "Must define all or none of CVEC_MALLOC, CVEC_FREE, and CVEC_REALLOC."
86#endif
87
88#ifndef CVEC_MALLOC
89#include <stdlib.h>
90#define CVEC_MALLOC(sz) malloc(sz)
91#define CVEC_REALLOC(p, sz) realloc(p, sz)
92#define CVEC_FREE(p) free(p)
93#endif
94
95#ifndef CVEC_MEMMOVE
96#include <string.h>
97#define CVEC_MEMMOVE(dst, src, sz) memmove(dst, src, sz)
98#endif
99
100#ifndef CVEC_ASSERT
101#include <assert.h>
102#define CVEC_ASSERT(x) assert(x)
103#endif
104
105
106/* general vector */
107
108cvector_TYPE* cvec_TYPE_heap(cvec_sz size, cvec_sz capacity, void(*elem_free)(void*), int(*elem_init)(void*, void*))
109{
110 cvector_TYPE* vec;
111 if (!(vec = (cvector_TYPE*)CVEC_MALLOC(sizeof(cvector_TYPE)))) {
112 CVEC_ASSERT(vec != NULL);
113 return NULL;
114 }
115
116 vec->size = size;
117 vec->capacity = (capacity > vec->size || (vec->size && capacity == vec->size)) ? capacity : vec->size + CVEC_TYPE_SZ;
118
119 if (!(vec->a = (TYPE*)CVEC_MALLOC(vec->capacity * sizeof(TYPE)))) {
120 CVEC_ASSERT(vec->a != NULL);
121 CVEC_FREE(vec);
122 return NULL;
123 }
124
125 vec->elem_free = elem_free;
126 vec->elem_init = elem_init;
127
128 return vec;
129}
130
131cvector_TYPE* cvec_init_TYPE_heap(TYPE* vals, cvec_sz num, void(*elem_free)(void*), int(*elem_init)(void*, void*))
132{
133 cvector_TYPE* vec;
134 cvec_sz i;
135
136 if (!(vec = (cvector_TYPE*)CVEC_MALLOC(sizeof(cvector_TYPE)))) {
137 CVEC_ASSERT(vec != NULL);
138 return NULL;
139 }
140
141 vec->capacity = num + CVEC_TYPE_SZ;
142 vec->size = num;
143 if (!(vec->a = (TYPE*)CVEC_MALLOC(vec->capacity * sizeof(TYPE)))) {
144 CVEC_ASSERT(vec->a != NULL);
145 CVEC_FREE(vec);
146 return NULL;
147 }
148
149 if (elem_init) {
150 for (i=0; i<num; ++i) {
151 if (!elem_init(&vec->a[i], &vals[i])) {
152 CVEC_ASSERT(0);
153 CVEC_FREE(vec->a);
154 CVEC_FREE(vec);
155 return NULL;
156 }
157 }
158 } else {
159 CVEC_MEMMOVE(vec->a, vals, sizeof(TYPE)*num);
160 }
161
162 vec->elem_free = elem_free;
163 vec->elem_init = elem_init;
164
165 return vec;
166}
167
168int cvec_TYPE(cvector_TYPE* vec, cvec_sz size, cvec_sz capacity, void(*elem_free)(void*), int(*elem_init)(void*, void*))
169{
170 vec->size = size;
171 vec->capacity = (capacity > vec->size || (vec->size && capacity == vec->size)) ? capacity : vec->size + CVEC_TYPE_SZ;
172
173 if (!(vec->a = (TYPE*)CVEC_MALLOC(vec->capacity * sizeof(TYPE)))) {
174 CVEC_ASSERT(vec->a != NULL);
175 vec->size = vec->capacity = 0;
176 return 0;
177 }
178
179 vec->elem_free = elem_free;
180 vec->elem_init = elem_init;
181
182 return 1;
183}
184
185int cvec_init_TYPE(cvector_TYPE* vec, TYPE* vals, cvec_sz num, void(*elem_free)(void*), int(*elem_init)(void*, void*))
186{
187 cvec_sz i;
188
189 vec->capacity = num + CVEC_TYPE_SZ;
190 vec->size = num;
191 if (!(vec->a = (TYPE*)CVEC_MALLOC(vec->capacity * sizeof(TYPE)))) {
192 CVEC_ASSERT(vec->a != NULL);
193 vec->size = vec->capacity = 0;
194 return 0;
195 }
196
197 if (elem_init) {
198 for (i=0; i<num; ++i) {
199 if (!elem_init(&vec->a[i], &vals[i])) {
200 CVEC_ASSERT(0);
201 return 0;
202 }
203 }
204 } else {
205 CVEC_MEMMOVE(vec->a, vals, sizeof(TYPE)*num);
206 }
207
208 vec->elem_free = elem_free;
209 vec->elem_init = elem_init;
210
211 return 1;
212}
213
214int cvec_copyc_TYPE(void* dest, void* src)
215{
216 cvector_TYPE* vec1 = (cvector_TYPE*)dest;
217 cvector_TYPE* vec2 = (cvector_TYPE*)src;
218
219 vec1->a = NULL;
220 vec1->size = 0;
221 vec1->capacity = 0;
222
223 return cvec_copy_TYPE(vec1, vec2);
224}
225
227{
228 int i;
229 TYPE* tmp = NULL;
230 if (!(tmp = (TYPE*)CVEC_REALLOC(dest->a, src->capacity*sizeof(TYPE)))) {
231 CVEC_ASSERT(tmp != NULL);
232 return 0;
233 }
234 dest->a = tmp;
235
236 if (src->elem_init) {
237 for (i=0; i<src->size; ++i) {
238 if (!src->elem_init(&dest->a[i], &src->a[i])) {
239 CVEC_ASSERT(0);
240 return 0;
241 }
242 }
243 } else {
244 /* could use memcpy here since we know we just allocated dest->a */
245 CVEC_MEMMOVE(dest->a, src->a, src->size*sizeof(TYPE));
246 }
247
248 dest->size = src->size;
249 dest->capacity = src->capacity;
250 dest->elem_free = src->elem_free;
251 dest->elem_init = src->elem_init;
252 return 1;
253}
254
255int cvec_push_TYPE(cvector_TYPE* vec, TYPE* a)
256{
257 TYPE* tmp;
258 cvec_sz tmp_sz;
259 if (vec->capacity == vec->size) {
260 tmp_sz = CVEC_TYPE_ALLOCATOR(vec->capacity);
261 if (!(tmp = (TYPE*)CVEC_REALLOC(vec->a, sizeof(TYPE)*tmp_sz))) {
262 CVEC_ASSERT(tmp != NULL);
263 return 0;
264 }
265 vec->a = tmp;
266 vec->capacity = tmp_sz;
267 }
268 if (vec->elem_init) {
269 if (!vec->elem_init(&vec->a[vec->size], a)) {
270 CVEC_ASSERT(0);
271 return 0;
272 }
273 } else {
274 CVEC_MEMMOVE(&vec->a[vec->size], a, sizeof(TYPE));
275 }
276
277 vec->size++;
278 return 1;
279}
280
281int cvec_pushm_TYPE(cvector_TYPE* vec, TYPE* a)
282{
283 TYPE* tmp;
284 cvec_sz tmp_sz;
285 if (vec->capacity == vec->size) {
286 tmp_sz = CVEC_TYPE_ALLOCATOR(vec->capacity);
287 if (!(tmp = (TYPE*)CVEC_REALLOC(vec->a, sizeof(TYPE)*tmp_sz))) {
288 CVEC_ASSERT(tmp != NULL);
289 return 0;
290 }
291 vec->a = tmp;
292 vec->capacity = tmp_sz;
293 }
294 CVEC_MEMMOVE(&vec->a[vec->size], a, sizeof(TYPE));
295
296 vec->size++;
297 return 1;
298}
299
300void cvec_pop_TYPE(cvector_TYPE* vec, TYPE* ret)
301{
302 vec->size--;
303 if (ret) {
304 CVEC_MEMMOVE(ret, &vec->a[vec->size], sizeof(TYPE));
305 }
306
307 if (vec->elem_free) {
308 vec->elem_free(&vec->a[vec->size]);
309 }
310}
311
312void cvec_popm_TYPE(cvector_TYPE* vec, TYPE* ret)
313{
314 vec->size--;
315 if (ret) {
316 CVEC_MEMMOVE(ret, &vec->a[vec->size], sizeof(TYPE));
317 }
318}
319
322{
323 return &vec->a[vec->size-1];
324}
325
327{
328 TYPE* tmp;
329 cvec_sz tmp_sz;
330 if (vec->capacity < vec->size + num) {
331 tmp_sz = vec->capacity + num + CVEC_TYPE_SZ;
332 if (!(tmp = (TYPE*)CVEC_REALLOC(vec->a, sizeof(TYPE)*tmp_sz))) {
333 CVEC_ASSERT(tmp != NULL);
334 return 0;
335 }
336 vec->a = tmp;
337 vec->capacity = tmp_sz;
338 }
339
340 vec->size += num;
341 return 1;
342}
343
344int cvec_insert_TYPE(cvector_TYPE* vec, cvec_sz i, TYPE* a)
345{
346 TYPE* tmp;
347 cvec_sz tmp_sz;
348 if (vec->capacity == vec->size) {
349 tmp_sz = CVEC_TYPE_ALLOCATOR(vec->capacity);
350 if (!(tmp = (TYPE*)CVEC_REALLOC(vec->a, sizeof(TYPE)*tmp_sz))) {
351 CVEC_ASSERT(tmp != NULL);
352 return 0;
353 }
354
355 vec->a = tmp;
356 vec->capacity = tmp_sz;
357 }
358 CVEC_MEMMOVE(&vec->a[i+1], &vec->a[i], (vec->size-i)*sizeof(TYPE));
359
360 if (vec->elem_init) {
361 if (!vec->elem_init(&vec->a[i], a)) {
362 CVEC_ASSERT(0);
363 return 0;
364 }
365 } else {
366 CVEC_MEMMOVE(&vec->a[i], a, sizeof(TYPE));
367 }
368
369 vec->size++;
370 return 1;
371}
372
373int cvec_insertm_TYPE(cvector_TYPE* vec, cvec_sz i, TYPE* a)
374{
375 TYPE* tmp;
376 cvec_sz tmp_sz;
377 if (vec->capacity == vec->size) {
378 tmp_sz = CVEC_TYPE_ALLOCATOR(vec->capacity);
379 if (!(tmp = (TYPE*)CVEC_REALLOC(vec->a, sizeof(TYPE)*tmp_sz))) {
380 CVEC_ASSERT(tmp != NULL);
381 return 0;
382 }
383
384 vec->a = tmp;
385 vec->capacity = tmp_sz;
386 }
387 CVEC_MEMMOVE(&vec->a[i+1], &vec->a[i], (vec->size-i)*sizeof(TYPE));
388
389 CVEC_MEMMOVE(&vec->a[i], a, sizeof(TYPE));
390
391 vec->size++;
392 return 1;
393}
394
395int cvec_insert_array_TYPE(cvector_TYPE* vec, cvec_sz i, TYPE* a, cvec_sz num)
396{
397 TYPE* tmp;
398 cvec_sz tmp_sz, j;
399 if (vec->capacity < vec->size + num) {
400 tmp_sz = vec->capacity + num + CVEC_TYPE_SZ;
401 if (!(tmp = (TYPE*)CVEC_REALLOC(vec->a, sizeof(TYPE)*tmp_sz))) {
402 CVEC_ASSERT(tmp != NULL);
403 return 0;
404 }
405 vec->a = tmp;
406 vec->capacity = tmp_sz;
407 }
408
409 CVEC_MEMMOVE(&vec->a[i+num], &vec->a[i], (vec->size-i)*sizeof(TYPE));
410 if (vec->elem_init) {
411 for (j=0; j<num; ++j) {
412 if (!vec->elem_init(&vec->a[j+i], &a[j])) {
413 CVEC_ASSERT(0);
414 return 0;
415 }
416 }
417 } else {
418 CVEC_MEMMOVE(&vec->a[i], a, num*sizeof(TYPE));
419 }
420 vec->size += num;
421 return 1;
422}
423
424int cvec_insert_arraym_TYPE(cvector_TYPE* vec, cvec_sz i, TYPE* a, cvec_sz num)
425{
426 TYPE* tmp;
427 cvec_sz tmp_sz;
428 if (vec->capacity < vec->size + num) {
429 tmp_sz = vec->capacity + num + CVEC_VOID_START_SZ;
430 if (!(tmp = (TYPE*)CVEC_REALLOC(vec->a, sizeof(TYPE)*tmp_sz))) {
431 CVEC_ASSERT(tmp != NULL);
432 return 0;
433 }
434 vec->a = tmp;
435 vec->capacity = tmp_sz;
436 }
437
438 CVEC_MEMMOVE(&vec->a[i+num], &vec->a[i], (vec->size-i)*sizeof(TYPE));
439
440 CVEC_MEMMOVE(&vec->a[i], a, num*sizeof(TYPE));
441 vec->size += num;
442 return 1;
443}
444
445int cvec_replace_TYPE(cvector_TYPE* vec, cvec_sz i, TYPE* a, TYPE* ret)
446{
447 if (ret) {
448 CVEC_MEMMOVE(ret, &vec->a[i], sizeof(TYPE));
449 } else if (vec->elem_free) {
450 vec->elem_free(&vec->a[i]);
451 }
452
453 if (vec->elem_init) {
454 if (!vec->elem_init(&vec->a[i], a)) {
455 CVEC_ASSERT(0);
456 return 0;
457 }
458 } else {
459 CVEC_MEMMOVE(&vec->a[i], a, sizeof(TYPE));
460 }
461 return 1;
462}
463
464void cvec_replacem_TYPE(cvector_TYPE* vec, cvec_sz i, TYPE* a, TYPE* ret)
465{
466 if (ret) {
467 CVEC_MEMMOVE(ret, &vec->a[i], sizeof(TYPE));
468 }
469
470 CVEC_MEMMOVE(&vec->a[i], a, sizeof(TYPE));
471}
472
473void cvec_erase_TYPE(cvector_TYPE* vec, cvec_sz start, cvec_sz end)
474{
475 cvec_sz i;
476 cvec_sz d = end - start + 1;
477 if (vec->elem_free) {
478 for (i=start; i<=end; i++) {
479 vec->elem_free(&vec->a[i]);
480 }
481 }
482 CVEC_MEMMOVE(&vec->a[start], &vec->a[end+1], (vec->size-1-end)*sizeof(TYPE));
483 vec->size -= d;
484}
485
486void cvec_remove_TYPE(cvector_TYPE* vec, cvec_sz start, cvec_sz end)
487{
488 cvec_sz d = end - start + 1;
489 CVEC_MEMMOVE(&vec->a[start], &vec->a[end+1], (vec->size-1-end)*sizeof(TYPE));
490 vec->size -= d;
491}
492
494{
495 TYPE* tmp;
496 if (vec->capacity < size) {
497 if (!(tmp = (TYPE*)CVEC_REALLOC(vec->a, sizeof(TYPE)*(size+CVEC_TYPE_SZ)))) {
498 CVEC_ASSERT(tmp != NULL);
499 return 0;
500 }
501 vec->a = tmp;
502 vec->capacity = size + CVEC_TYPE_SZ;
503 }
504 return 1;
505}
506
508{
509 cvec_sz i;
510 TYPE* tmp;
511 if (size < vec->size) {
512 if (vec->elem_free) {
513 for (i=vec->size-1; i>=size; i--) {
514 vec->elem_free(&vec->a[i]);
515 }
516 }
517 vec->size = size;
518 }
519
520 vec->capacity = size;
521
522 if (!(tmp = (TYPE*)CVEC_REALLOC(vec->a, sizeof(TYPE)*size))) {
523 CVEC_ASSERT(tmp != NULL);
524 return 0;
525 }
526 vec-> a = tmp;
527 return 1;
528}
529
530int cvec_set_val_sz_TYPE(cvector_TYPE* vec, TYPE* val)
531{
532 cvec_sz i;
533
534 if (vec->elem_free) {
535 for(i=0; i<vec->size; i++) {
536 vec->elem_free(&vec->a[i]);
537 }
538 }
539
540 if (vec->elem_init) {
541 for (i=0; i<vec->size; i++) {
542 if (!vec->elem_init(&vec->a[i], val)) {
543 CVEC_ASSERT(0);
544 return 0;
545 }
546 }
547 } else {
548 for (i=0; i<vec->size; i++) {
549 CVEC_MEMMOVE(&vec->a[i], val, sizeof(TYPE));
550 }
551 }
552 return 1;
553}
554
555int cvec_set_val_cap_TYPE(cvector_TYPE* vec, TYPE* val)
556{
557 cvec_sz i;
558 if (vec->elem_free) {
559 for (i=0; i<vec->size; i++) {
560 vec->elem_free(&vec->a[i]);
561 }
562 vec->size = vec->capacity;
563 }
564
565 if (vec->elem_init) {
566 for (i=0; i<vec->capacity; i++) {
567 if (!vec->elem_init(&vec->a[i], val)) {
568 CVEC_ASSERT(0);
569 return 0;
570 }
571 }
572 } else {
573 for (i=0; i<vec->capacity; i++) {
574 CVEC_MEMMOVE(&vec->a[i], val, sizeof(TYPE));
575 }
576 }
577 return 1;
578}
579
581{
582 cvec_sz i;
583 if (vec->elem_free) {
584 for (i=0; i<vec->size; ++i) {
585 vec->elem_free(&vec->a[i]);
586 }
587 }
588 vec->size = 0;
589}
590
591void cvec_free_TYPE_heap(void* vec)
592{
593 cvec_sz i;
594 cvector_TYPE* tmp = (cvector_TYPE*)vec;
595 if (!tmp) return;
596 if (tmp->elem_free) {
597 for (i=0; i<tmp->size; i++) {
598 tmp->elem_free(&tmp->a[i]);
599 }
600 }
601 CVEC_FREE(tmp->a);
602 CVEC_FREE(tmp);
603}
604
605void cvec_free_TYPE(void* vec)
606{
607 cvec_sz i;
608 cvector_TYPE* tmp = (cvector_TYPE*)vec;
609 if (tmp->elem_free) {
610 for (i=0; i<tmp->size; i++) {
611 tmp->elem_free(&tmp->a[i]);
612 }
613 }
614
615 CVEC_FREE(tmp->a);
616 tmp->a = NULL;
617 tmp->size = 0;
618 tmp->capacity = 0;
619}
620
621
622#endif
#define CVEC_FREE(p)
Definition cvector.h:68
#define CVEC_REALLOC(p, sz)
Definition cvector.h:67
#define CVEC_MEMMOVE(dst, src, sz)
Definition cvector.h:73
#define CVEC_MALLOC(sz)
Definition cvector.h:66
#define CVEC_ASSERT(x)
Definition cvector.h:78
CVEC_SIZE_T cvec_sz
Definition cvector.h:88
cvec_sz CVEC_VOID_START_SZ
int cvec_set_cap_TYPE(cvector_TYPE *vec, cvec_sz size)
int cvec_reserve_TYPE(cvector_TYPE *vec, cvec_sz size)
int cvec_copy_TYPE(cvector_TYPE *dest, cvector_TYPE *src)
int cvec_set_val_cap_TYPE(cvector_TYPE *vec, TYPE *val)
void cvec_erase_TYPE(cvector_TYPE *vec, cvec_sz start, cvec_sz end)
int cvec_insertm_TYPE(cvector_TYPE *vec, cvec_sz i, TYPE *a)
int cvec_insert_TYPE(cvector_TYPE *vec, cvec_sz i, TYPE *a)
void cvec_free_TYPE(void *vec)
void cvec_popm_TYPE(cvector_TYPE *vec, TYPE *ret)
int cvec_pushm_TYPE(cvector_TYPE *vec, TYPE *a)
int cvec_push_TYPE(cvector_TYPE *vec, TYPE *val)
TYPE * cvec_back_TYPE(cvector_TYPE *vec)
void cvec_pop_TYPE(cvector_TYPE *vec, TYPE *ret)
int cvec_set_val_sz_TYPE(cvector_TYPE *vec, TYPE *val)
int cvec_init_TYPE(cvector_TYPE *vec, TYPE *vals, cvec_sz num, void(*elem_free)(void *), int(*elem_init)(void *, void *))
cvector_TYPE * cvec_init_TYPE_heap(TYPE *vals, cvec_sz num, void(*elem_free)(void *), int(*elem_init)(void *, void *))
int cvec_insert_arraym_TYPE(cvector_TYPE *vec, cvec_sz i, TYPE *a, cvec_sz num)
void cvec_replacem_TYPE(cvector_TYPE *vec, cvec_sz i, TYPE *a, TYPE *ret)
int cvec_replace_TYPE(cvector_TYPE *vec, cvec_sz i, TYPE *a, TYPE *ret)
void cvec_free_TYPE_heap(void *vec)
int cvec_TYPE(cvector_TYPE *vec, cvec_sz size, cvec_sz capacity, void(*elem_free)(void *), int(*elem_init)(void *, void *))
CVEC_SIZE_T cvec_sz
void cvec_clear_TYPE(cvector_TYPE *vec)
int cvec_insert_array_TYPE(cvector_TYPE *vec, cvec_sz i, TYPE *a, cvec_sz num)
int cvec_copyc_TYPE(void *dest, void *src)
#define CVEC_SIZE_T
cvector_TYPE * cvec_TYPE_heap(cvec_sz size, cvec_sz capacity, void(*elem_free)(void *), int(*elem_init)(void *, void *))
cvec_sz CVEC_TYPE_SZ
void cvec_remove_TYPE(cvector_TYPE *vec, cvec_sz start, cvec_sz end)
int cvec_extend_TYPE(cvector_TYPE *vec, cvec_sz num)
Data structure for TYPE vector.
TYPE * a
Array.
int(* elem_init)(void *, void *)
cvec_sz size
Current size (amount you use when manipulating array directly).
void(* elem_free)(void *)
cvec_sz capacity
Allocated size of array; always >= size.