1 /**************************************************************************
2 *
3 * Copyright 2010 Luca Barbieri
4 *
5 * Permission is hereby granted, free of charge, to any person obtaining
6 * a copy of this software and associated documentation files (the
7 * "Software"), to deal in the Software without restriction, including
8 * without limitation the rights to use, copy, modify, merge, publish,
9 * distribute, sublicense, and/or sell copies of the Software, and to
10 * permit persons to whom the Software is furnished to do so, subject to
11 * the following conditions:
12 *
13 * The above copyright notice and this permission notice (including the
14 * next paragraph) shall be included in all copies or substantial
15 * portions of the Software.
16 *
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
18 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
19 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
20 * IN NO EVENT SHALL THE COPYRIGHT OWNER(S) AND/OR ITS SUPPLIERS BE
21 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
22 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
23 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
24 *
25 **************************************************************************/
26
27 #ifndef U_DYNARRAY_H
28 #define U_DYNARRAY_H
29
30 #include <stdlib.h>
31 #include <string.h>
32 #include <limits.h>
33 #include "ralloc.h"
34
35 #ifdef __cplusplus
36 extern "C" {
37 #endif
38
39 extern unsigned util_dynarray_is_data_stack_allocated;
40
41 /* A zero-initialized version of this is guaranteed to represent an
42 * empty array.
43 *
44 * Also, size <= capacity and data != 0 if and only if capacity != 0
45 * capacity will always be the allocation size of data
46 */
47 struct util_dynarray
48 {
49 void *mem_ctx;
50 void *data;
51 unsigned size;
52 unsigned capacity;
53 };
54
55 static inline void
util_dynarray_init(struct util_dynarray * buf,void * mem_ctx)56 util_dynarray_init(struct util_dynarray *buf, void *mem_ctx)
57 {
58 memset(buf, 0, sizeof(*buf));
59 buf->mem_ctx = mem_ctx;
60 }
61
62 static inline void
util_dynarray_init_from_stack(struct util_dynarray * buf,void * data,unsigned capacity)63 util_dynarray_init_from_stack(struct util_dynarray *buf, void *data, unsigned capacity)
64 {
65 memset(buf, 0, sizeof(*buf));
66 buf->mem_ctx = &util_dynarray_is_data_stack_allocated;
67 buf->data = data;
68 buf->capacity = capacity;
69 }
70
71 static inline void
util_dynarray_fini(struct util_dynarray * buf)72 util_dynarray_fini(struct util_dynarray *buf)
73 {
74 if (buf->data) {
75 if (buf->mem_ctx == &util_dynarray_is_data_stack_allocated) {
76 } else if (buf->mem_ctx) {
77 ralloc_free(buf->data);
78 } else {
79 free(buf->data);
80 }
81 util_dynarray_init(buf, buf->mem_ctx);
82 }
83 }
84
85 static inline void
util_dynarray_clear(struct util_dynarray * buf)86 util_dynarray_clear(struct util_dynarray *buf)
87 {
88 buf->size = 0;
89 }
90
91 #define DYN_ARRAY_INITIAL_SIZE 64
92
93 MUST_CHECK static inline void *
util_dynarray_ensure_cap(struct util_dynarray * buf,unsigned newcap)94 util_dynarray_ensure_cap(struct util_dynarray *buf, unsigned newcap)
95 {
96 if (newcap > buf->capacity) {
97 unsigned capacity = MAX3(DYN_ARRAY_INITIAL_SIZE, buf->capacity * 2, newcap);
98 void *data;
99
100 if (buf->mem_ctx == &util_dynarray_is_data_stack_allocated) {
101 data = malloc(capacity);
102 if (data) {
103 memcpy(data, buf->data, buf->size);
104 buf->mem_ctx = NULL;
105 }
106 } else if (buf->mem_ctx) {
107 data = reralloc_size(buf->mem_ctx, buf->data, capacity);
108 } else {
109 data = realloc(buf->data, capacity);
110 }
111 if (!data)
112 return NULL;
113
114 buf->data = data;
115 buf->capacity = capacity;
116 }
117
118 return (void *)((char *)buf->data + buf->size);
119 }
120
121 /* use util_dynarray_trim to reduce the allocated storage */
122 MUST_CHECK static inline void *
util_dynarray_resize_bytes(struct util_dynarray * buf,unsigned nelts,size_t eltsize)123 util_dynarray_resize_bytes(struct util_dynarray *buf, unsigned nelts, size_t eltsize)
124 {
125 if (unlikely(nelts > UINT_MAX / eltsize))
126 return NULL;
127
128 unsigned newsize = nelts * eltsize;
129 void *p = util_dynarray_ensure_cap(buf, newsize);
130 if (!p)
131 return NULL;
132
133 buf->size = newsize;
134
135 return p;
136 }
137
138 static inline void
util_dynarray_clone(struct util_dynarray * buf,void * mem_ctx,struct util_dynarray * from_buf)139 util_dynarray_clone(struct util_dynarray *buf, void *mem_ctx,
140 struct util_dynarray *from_buf)
141 {
142 util_dynarray_init(buf, mem_ctx);
143 if (util_dynarray_resize_bytes(buf, from_buf->size, 1))
144 memcpy(buf->data, from_buf->data, from_buf->size);
145 }
146
147 MUST_CHECK static inline void *
util_dynarray_grow_bytes(struct util_dynarray * buf,unsigned ngrow,size_t eltsize)148 util_dynarray_grow_bytes(struct util_dynarray *buf, unsigned ngrow, size_t eltsize)
149 {
150 unsigned growbytes = ngrow * eltsize;
151
152 if (unlikely(ngrow > (UINT_MAX / eltsize) ||
153 growbytes > UINT_MAX - buf->size))
154 return NULL;
155
156 unsigned newsize = buf->size + growbytes;
157 void *p = util_dynarray_ensure_cap(buf, newsize);
158 if (!p)
159 return NULL;
160
161 buf->size = newsize;
162
163 return p;
164 }
165
166 static inline void
util_dynarray_trim(struct util_dynarray * buf)167 util_dynarray_trim(struct util_dynarray *buf)
168 {
169 if (buf->mem_ctx == &util_dynarray_is_data_stack_allocated)
170 return;
171
172 if (buf->size != buf->capacity) {
173 if (buf->size) {
174 if (buf->mem_ctx) {
175 buf->data = reralloc_size(buf->mem_ctx, buf->data, buf->size);
176 } else {
177 buf->data = realloc(buf->data, buf->size);
178 }
179 buf->capacity = buf->size;
180 } else {
181 if (buf->mem_ctx) {
182 ralloc_free(buf->data);
183 } else {
184 free(buf->data);
185 }
186 buf->data = NULL;
187 buf->capacity = 0;
188 }
189 }
190 }
191
192 static inline void
util_dynarray_append_dynarray(struct util_dynarray * buf,const struct util_dynarray * other)193 util_dynarray_append_dynarray(struct util_dynarray *buf,
194 const struct util_dynarray *other)
195 {
196 if (other->size > 0) {
197 void *p = util_dynarray_grow_bytes(buf, 1, other->size);
198 memcpy(p, other->data, other->size);
199 }
200 }
201
202 #define util_dynarray_append(buf, type, v) do {type __v = (v); memcpy(util_dynarray_grow_bytes((buf), 1, sizeof(type)), &__v, sizeof(type));} while(0)
203 /* Returns a pointer to the space of the first new element (in case of growth) or NULL on failure. */
204 #define util_dynarray_resize(buf, type, nelts) util_dynarray_resize_bytes(buf, (nelts), sizeof(type))
205 #define util_dynarray_grow(buf, type, ngrow) util_dynarray_grow_bytes(buf, (ngrow), sizeof(type))
206 #define util_dynarray_top_ptr(buf, type) (type*)((char*)(buf)->data + (buf)->size - sizeof(type))
207 #define util_dynarray_top(buf, type) *util_dynarray_top_ptr(buf, type)
208 #define util_dynarray_pop_ptr(buf, type) (type*)((char*)(buf)->data + ((buf)->size -= sizeof(type)))
209 #define util_dynarray_pop(buf, type) *util_dynarray_pop_ptr(buf, type)
210 #define util_dynarray_contains(buf, type) ((buf)->size >= sizeof(type))
211 #define util_dynarray_element(buf, type, idx) ((type*)(buf)->data + (idx))
212 #define util_dynarray_begin(buf) ((buf)->data)
213 #define util_dynarray_end(buf) ((void*)util_dynarray_element((buf), char, (buf)->size))
214 #define util_dynarray_num_elements(buf, type) ((buf)->size / sizeof(type))
215
216 #define util_dynarray_foreach(buf, type, elem) \
217 for (type *elem = (type *)(buf)->data; \
218 elem < (type *)((char *)(buf)->data + (buf)->size); elem++)
219
220 #define util_dynarray_foreach_reverse(buf, type, elem) \
221 if ((buf)->size > 0) \
222 for (type *elem = util_dynarray_top_ptr(buf, type); \
223 elem; \
224 elem = elem > (type *)(buf)->data ? elem - 1 : NULL)
225
226 #define util_dynarray_delete_unordered(buf, type, v) \
227 do { \
228 unsigned num_elements = (buf)->size / sizeof(type); \
229 unsigned i; \
230 for (i = 0; i < num_elements; i++) { \
231 type __v = *util_dynarray_element((buf), type, (i)); \
232 if (v == __v) { \
233 memcpy(util_dynarray_element((buf), type, (i)), \
234 util_dynarray_pop_ptr((buf), type), sizeof(type)); \
235 break; \
236 } \
237 } \
238 } while (0)
239
240 #ifdef __cplusplus
241 }
242 #endif
243
244 #endif /* U_DYNARRAY_H */
245
246