2 Copyright (c) 2009 Joseph A. Adams
5 Redistribution and use in source and binary forms, with or without
6 modification, are permitted provided that the following conditions
8 1. Redistributions of source code must retain the above copyright
9 notice, this list of conditions and the following disclaimer.
10 2. Redistributions in binary form must reproduce the above copyright
11 notice, this list of conditions and the following disclaimer in the
12 documentation and/or other materials provided with the distribution.
13 3. The name of the author may not be used to endorse or promote products
14 derived from this software without specific prior written permission.
16 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
17 IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
18 OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
19 IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
20 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
21 NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
25 THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
38 * Life cycle of a darray (dynamically-allocated array):
40 * darray(int) a = darray_new();
43 * struct {darray(int) a;} foo;
47 * Typedefs for darrays of common types:
49 * darray_char, darray_schar, darray_uchar
50 * darray_short, darray_int, darray_long
51 * darray_ushort, darray_uint, darray_ulong
55 * T darray_item(darray(T) arr, size_t index);
56 * size_t darray_size(darray(T) arr);
57 * size_t darray_alloc(darray(T) arr);
58 * bool darray_empty(darray(T) arr);
60 * Insertion (single item):
62 * void darray_append(darray(T) arr, T item);
63 * void darray_prepend(darray(T) arr, T item);
64 * void darray_push(darray(T) arr, T item); // same as darray_append
66 * Insertion (multiple items):
68 * void darray_append_items(darray(T) arr, T *items, size_t count);
69 * void darray_prepend_items(darray(T) arr, T *items, size_t count);
71 * void darray_appends(darray(T) arr, [T item, [...]]);
72 * void darray_prepends(darray(T) arr, [T item, [...]]);
74 * // Same functionality as above, but does not require typeof.
75 * void darray_appends_t(darray(T) arr, #T, [T item, [...]]);
76 * void darray_prepends_t(darray(T) arr, #T, [T item, [...]]);
80 * T darray_pop(darray(T) arr | darray_size(arr) != 0);
81 * T* darray_pop_check(darray(T*) arr);
85 * void darray_from_items(darray(T) arr, T *items, size_t count);
86 * void darray_from_c(darray(T) arr, T c_array[N]);
90 * void darray_append_string(darray(char) arr, const char *str);
91 * void darray_append_lit(darray(char) arr, char stringLiteral[N+1]);
93 * void darray_prepend_string(darray(char) arr, const char *str);
94 * void darray_prepend_lit(darray(char) arr, char stringLiteral[N+1]);
96 * void darray_from_string(darray(T) arr, const char *str);
97 * void darray_from_lit(darray(char) arr, char stringLiteral[N+1]);
101 * void darray_resize(darray(T) arr, size_t newSize);
102 * void darray_resize0(darray(T) arr, size_t newSize);
104 * void darray_realloc(darray(T) arr, size_t newAlloc);
105 * void darray_growalloc(darray(T) arr, size_t newAlloc);
107 * void darray_make_room(darray(T) arr, size_t room);
111 * darray_foreach(T *&i, darray(T) arr) {...}
112 * darray_foreach_reverse(T *&i, darray(T) arr) {...}
114 * Except for darray_foreach and darray_foreach_reverse,
115 * all macros evaluate their non-darray arguments only once.
120 #define darray(type) struct {type *item; size_t size; size_t alloc;}
122 #define darray_new() {0,0,0}
123 #define darray_init(arr) do {(arr).item=0; (arr).size=0; (arr).alloc=0;} while(0)
124 #define darray_free(arr) do {free((arr).item);} while(0)
128 * Typedefs for darrays of common types. These are useful
129 * when you want to pass a pointer to an darray(T) around.
131 * The following will produce an incompatible pointer warning:
133 * void foo(darray(int) *arr);
134 * darray(int) arr = darray_new();
139 * void foo(darray_int *arr);
140 * darray_int arr = darray_new();
144 typedef darray(char) darray_char;
145 typedef darray(signed char) darray_schar;
146 typedef darray(unsigned char) darray_uchar;
148 typedef darray(short) darray_short;
149 typedef darray(int) darray_int;
150 typedef darray(long) darray_long;
152 typedef darray(unsigned short) darray_ushort;
153 typedef darray(unsigned int) darray_uint;
154 typedef darray(unsigned long) darray_ulong;
159 #define darray_item(arr, i) ((arr).item[i])
160 #define darray_size(arr) ((arr).size)
161 #define darray_alloc(arr) ((arr).alloc)
162 #define darray_empty(arr) ((arr).size == 0)
165 /*** Insertion (single item) ***/
167 #define darray_append(arr, ...) do { \
168 darray_resize(arr, (arr).size+1); \
169 (arr).item[(arr).size-1] = (__VA_ARGS__); \
171 #define darray_prepend(arr, ...) do { \
172 darray_resize(arr, (arr).size+1); \
173 memmove((arr).item+1, (arr).item, ((arr).size-1)*sizeof(*(arr).item)); \
174 (arr).item[0] = (__VA_ARGS__); \
176 #define darray_push(arr, ...) darray_append(arr, __VA_ARGS__)
179 /*** Insertion (multiple items) ***/
181 #define darray_append_items(arr, items, count) do { \
182 size_t __count = (count), __oldSize = (arr).size; \
183 darray_resize(arr, __oldSize + __count); \
184 memcpy((arr).item + __oldSize, items, __count * sizeof(*(arr).item)); \
187 #define darray_prepend_items(arr, items, count) do { \
188 size_t __count = (count), __oldSize = (arr).size; \
189 darray_resize(arr, __count + __oldSize); \
190 memmove((arr).item + __count, (arr).item, __oldSize * sizeof(*(arr).item)); \
191 memcpy((arr).item, items, __count * sizeof(*(arr).item)); \
194 #define darray_append_items_nullterminate(arr, items, count) do { \
195 size_t __count = (count), __oldSize = (arr).size; \
196 darray_resize(arr, __oldSize + __count + 1); \
197 memcpy((arr).item + __oldSize, items, __count * sizeof(*(arr).item)); \
198 (arr).item[--(arr).size] = 0; \
201 #define darray_prepend_items_nullterminate(arr, items, count) do { \
202 size_t __count = (count), __oldSize = (arr).size; \
203 darray_resize(arr, __count + __oldSize + 1); \
204 memmove((arr).item + __count, (arr).item, __oldSize * sizeof(*(arr).item)); \
205 memcpy((arr).item, items, __count * sizeof(*(arr).item)); \
206 (arr).item[--(arr).size] = 0; \
210 #define darray_appends(arr, ...) darray_appends_t(arr, typeof((*(arr).item)), __VA_ARGS__)
211 #define darray_prepends(arr, ...) darray_prepends_t(arr, typeof((*(arr).item)), __VA_ARGS__)
214 #define darray_appends_t(arr, type, ...) do { \
215 type __src[] = {__VA_ARGS__}; \
216 darray_append_items(arr, __src, sizeof(__src)/sizeof(*__src)); \
218 #define darray_prepends_t(arr, type, ...) do { \
219 type __src[] = {__VA_ARGS__}; \
220 darray_prepend_items(arr, __src, sizeof(__src)/sizeof(*__src)); \
226 /* Warning: Do not call darray_pop on an empty darray. */
227 #define darray_pop(arr) ((arr).item[--(arr).size])
228 #define darray_pop_check(arr) ((arr).size ? darray_pop(arr) : NULL)
231 /*** Replacement ***/
233 #define darray_from_items(arr, items, count) do {size_t __count = (count); darray_resize(arr, __count); memcpy((arr).item, items, __count*sizeof(*(arr).item));} while(0)
234 #define darray_from_c(arr, c_array) darray_from_items(arr, c_array, sizeof(c_array)/sizeof(*(c_array)))
237 /*** String buffer ***/
239 #define darray_append_string(arr, str) do {const char *__str = (str); darray_append_items(arr, __str, strlen(__str)+1); (arr).size--;} while(0)
240 #define darray_append_lit(arr, stringLiteral) do {darray_append_items(arr, stringLiteral, sizeof(stringLiteral)); (arr).size--;} while(0)
242 #define darray_prepend_string(arr, str) do { \
243 const char *__str = (str); \
244 darray_prepend_items_nullterminate(arr, __str, strlen(__str)); \
246 #define darray_prepend_lit(arr, stringLiteral) \
247 darray_prepend_items_nullterminate(arr, stringLiteral, sizeof(stringLiteral) - 1)
249 #define darray_from_string(arr, str) do {const char *__str = (str); darray_from_items(arr, __str, strlen(__str)+1); (arr).size--;} while(0)
250 #define darray_from_lit(arr, stringLiteral) do {darray_from_items(arr, stringLiteral, sizeof(stringLiteral)); (arr).size--;} while(0)
253 /*** Size management ***/
255 #define darray_resize(arr, newSize) darray_growalloc(arr, (arr).size = (newSize))
256 #define darray_resize0(arr, newSize) do { \
257 size_t __oldSize = (arr).size, __newSize = (newSize); \
258 (arr).size = __newSize; \
259 if (__newSize > __oldSize) { \
260 darray_growalloc(arr, __newSize); \
261 memset(&(arr).item[__oldSize], 0, (__newSize - __oldSize) * sizeof(*(arr).item)); \
265 #define darray_realloc(arr, newAlloc) do { \
266 (arr).item = realloc((arr).item, ((arr).alloc = (newAlloc)) * sizeof(*(arr).item)); \
268 #define darray_growalloc(arr, need) do { \
269 size_t __need = (need); \
270 if (__need > (arr).alloc) \
271 darray_realloc(arr, darray_next_alloc((arr).alloc, __need)); \
274 #if HAVE_STATEMENT_EXPR==1
275 #define darray_make_room(arr, room) ({size_t newAlloc = (arr).size+(room); if ((arr).alloc<newAlloc) darray_realloc(arr, newAlloc); (arr).item+(arr).size; })
278 static inline size_t darray_next_alloc(size_t alloc, size_t need)
291 * darray_foreach(T *&i, darray(T) arr) {...}
293 * Traverse a darray. `i` must be declared in advance as a pointer to an item.
295 #define darray_foreach(i, arr) \
296 for ((i) = &(arr).item[0]; (i) < &(arr).item[(arr).size]; (i)++)
299 * darray_foreach_reverse(T *&i, darray(T) arr) {...}
301 * Like darray_foreach, but traverse in reverse order.
303 #define darray_foreach_reverse(i, arr) \
304 for ((i) = &(arr).item[(arr).size]; (i)-- > &(arr).item[0]; )
307 #endif /* CCAN_DARRAY_H */
311 darray_growalloc(arr, newAlloc) sees if the darray can currently hold newAlloc items;
312 if not, it increases the alloc to satisfy this requirement, allocating slack
313 space to avoid having to reallocate for every size increment.
315 darray_from_string(arr, str) copies a string to an darray_char.
317 darray_push(arr, item) pushes an item to the end of the darray.
318 darray_pop(arr) pops it back out. Be sure there is at least one item in the darray before calling.
319 darray_pop_check(arr) does the same as darray_pop, but returns NULL if there are no more items left in the darray.
321 darray_make_room(arr, room) ensures there's 'room' elements of space after the end of the darray, and it returns a pointer to this space.
322 Currently requires HAVE_STATEMENT_EXPR, but I plan to remove this dependency by creating an inline function.
324 The following require HAVE_TYPEOF==1 :
326 darray_appends(arr, item0, item1...) appends a collection of comma-delimited items to the darray.
327 darray_prepends(arr, item0, item1...) prepends a collection of comma-delimited items to the darray.\
335 darray_appends(arr, 0,1,2,3,4);
336 darray_appends(arr, -5,-4,-3,-2,-1);
337 darray_foreach(i, arr)
344 typedef struct {int n,d;} Fraction;
345 darray(Fraction) fractions;
348 darray_appends(fractions, {3,4}, {3,5}, {2,1});
349 darray_foreach(i, fractions)
350 printf("%d/%d\n", i->n, i->d);
352 darray_free(fractions);