-
Notifications
You must be signed in to change notification settings - Fork 2
/
Copy pathkvec.h
146 lines (133 loc) · 5.94 KB
/
kvec.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
/* The MIT License
Copyright (c) 2008, by Attractive Chaos <[email protected]>
Permission is hereby granted, free of charge, to any person obtaining
a copy of this software and associated documentation files (the
"Software"), to deal in the Software without restriction, including
without limitation the rights to use, copy, modify, merge, publish,
distribute, sublicense, and/or sell copies of the Software, and to
permit persons to whom the Software is furnished to do so, subject to
the following conditions:
The above copyright notice and this permission notice shall be
included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.
*/
/*
An example:
#include <stdlib.h>
#define mem_malloc malloc
#define mem_realloc realloc
#include "kvec.h"
int main()
{
int i, j;
vector(int) *array = 0; // initialization
vec_push(array, 10); // append
for (i = 0, j = vec_size(array); i < j; i++) // size
printf("array[%d] = %d\n", i, vec_at(array, i)); // access
vec_destroy(array); // destructor
return 0;
}
*/
/*
module : kvec.h
version : 1.2
date : 01/20/20
1. Change type of n, m from size_t to unsigned. Reason: takes less memory.
2. Remove (type*) casts. Reason: not needed for C.
3. Replace sizeof(type) with sizeof(*a). Reason: no need to specify type.
4. Remove kv_a. Reason: compiler complains about lvalue required.
5. Rename kv_A to kv_at. Reason: looks like a better name.
6. Remove roundup32. Reason: not used anymore.
7. Change initial value of m to 1 instead of 2. Reason: takes less memory.
8. Change vector type to pointer. Reason: more convenient to pass around.
9. Remove protection against multiple inclusion. Reason: it must be possible
to have vectors of different types within the same source file. Undone.
10. Remove stdlib.h. Reason: it should be possible to have different memory
allocaters for different vectors.
11. Protect kv_size against NULL parameter. Reason: more convenient interface.
12. Change type from kvec_t to vector. Reason: _t is in the compiler namespace.
13. Change memory allocator to mem_malloc and mem_realloc. Reason: this allows
those vectors to be garbage collected.
14. Add macros stk_init and stk_push. Reason: they allow checks on NULL pointer
and statistics.
15. Change prefix kv_ into vec_. Reason: easier when changing existing code.
16. Add macro vec_setsize. Reason: vec_size cannot be used for this purpose.
17. Add vec_back macro. Reason: sometimes a value needs to be read, not popped.
18. Macro vec_pushp is not used. Maybe it should be removed? Done.
19. Add automatic initialization in vec_push. Reason: more convenient interface.
20. Add macro vec_equal. Reason: part of the requirements of the vector type.
21. Add macro vec_reverse. Reason: more convenient than as function.
22. Add automatic initialization in vec_copy. Reason: more convenient interface.
23. Rename vec_resize to vec_grow. Reason: vector can only grow.
24. Add vec_shrink macro. Reason: reduce memory footprint of large vectors.
25. Add vec_end macro. Reason: can be used as stack pointer.
2008-09-22 (0.1.0):
* The initial version.
*/
#ifndef AC_KVEC_H
#define AC_KVEC_H
#define vector(type) struct { unsigned n, m; type *a; }
#define vec_init(v) do { (v) = mem_malloc(sizeof(*(v))); \
(v)->n = (v)->m = 0; (v)->a = 0; } while (0)
#define vec_destroy(v) do { free((v)->a); free((v)); } while (0)
#define vec_at(v, i) ((v)->a[(i)])
#define vec_pop(v) ((v)->a[--(v)->n])
#define vec_back(v) ((v)->a[(v)->n - 1])
#define vec_end(v) ((v)->a + (v)->n)
#define vec_size(v) ((v) ? (v)->n : 0)
#define vec_setsize(v, s) ((v)->n = (s))
#define vec_max(v) ((v)->m)
#define vec_grow(v, s) ((v)->m = (s), (v)->a = mem_realloc((v)->a, \
sizeof(*(v)->a) * (v)->m))
#define vec_shrink(v) do { if ((v)->n) { ((v)->m = (v)->n; (v)->a = \
mem_realloc((v)->a, sizeof(*(v)->a) * (v)->m));\
} } while (0)
#define vec_equal(v, w) ((v)->n == (w)->n && !memcmp((v)->a, (w)->a, \
sizeof(*(v)) * (v)->n))
/* vec_copy assumes that v1 does not exist yet and needs to be created */
#define vec_copy(v1, v0) \
do { \
vec_init((v1)); \
if ((v1)->m < (v0)->n) vec_grow(v1, (v0)->n); \
(v1)->n = (v0)->n; \
memcpy((v1)->a, (v0)->a, sizeof(*(v0)->a) * (v0)->n); \
} while (0)
/* vec_push assumes that v has been initialized to 0 before its called */
#define vec_push(v, x) \
do { \
if (!(v)) vec_init((v)); \
if ((v)->n == (v)->m) { \
(v)->m = (v)->m ? (v)->m << 1 : 1; \
(v)->a = mem_realloc((v)->a, sizeof(*(v)->a) * (v)->m); \
} (v)->a[(v)->n++] = (x); \
} while (0)
/* vec_reverse assumes that an extra element has been added as scratch */
#define vec_reverse(v) \
do { \
int i, j, k = vec_size((v)) - 1; \
for (i = 0, j = k - 1; i < j; i++, j--) { \
vec_at((v), k) = vec_at((v), i); \
vec_at((v), i) = vec_at((v), j); \
vec_at((v), j) = vec_at((v), k); \
} vec_pop((v)); \
} while (0)
/* stk_init -- non-garbage collecting memory allocator unlike vec_init */
#define stk_init(v) do { (v) = chk_malloc(sizeof(*(v))); \
(v)->n = (v)->m = 0; (v)->a = 0; } while (0)
/* stk_push does not check whether v needs to be initialized -- faster */
#define stk_push(v, x) \
do { \
if ((v)->n == (v)->m) { \
(v)->m = (v)->m ? (v)->m << 1 : 1; \
(v)->a = chk_realloc((v)->a, sizeof(*(v)->a) * (v)->m); \
} \
(v)->a[(v)->n++] = (x); \
} while (0)
#endif