darray: Renamed array module to darray and made several improvements.
[ccan] / ccan / darray / darray.h
1 /*
2         Copyright (c) 2009  Joseph A. Adams
3         All rights reserved.
4         
5         Redistribution and use in source and binary forms, with or without
6         modification, are permitted provided that the following conditions
7         are met:
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.
15         
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.
26 */
27
28 #ifndef CCAN_DARRAY_H
29 #define CCAN_DARRAY_H
30
31 #include <stdlib.h>
32 #include <string.h>
33 #include "config.h"
34
35 /*
36  * SYNOPSIS
37  *
38  * Life cycle of a darray (dynamically-allocated array):
39  *
40  *     darray(int) a = darray_new();
41  *     darray_free(a);
42  *
43  *     struct {darray(int) a;} foo;
44  *     darray_init(foo.a);
45  *     darray_free(foo.a);
46  *
47  * Typedefs for darrays of common types:
48  *
49  *     darray_char, darray_schar, darray_uchar
50  *     darray_short, darray_int, darray_long
51  *     darray_ushort, darray_uint, darray_ulong
52  *
53  * Access:
54  *
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);
59  *
60  * Insertion (single item):
61  *
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
65  *
66  * Insertion (multiple items):
67  *
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);
70  *
71  *     void   darray_appends(darray(T) arr, [T item, [...]]);
72  *     void   darray_prepends(darray(T) arr, [T item, [...]]);
73  *
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, [...]]);
77  *
78  * Removal:
79  *
80  *     T      darray_pop(darray(T) arr | darray_size(arr) != 0);
81  *     T*     darray_pop_check(darray(T*) arr);
82  *
83  * Replacement:
84  *
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]);
87  *
88  * String buffer:
89  *
90  *     void   darray_append_string(darray(char) arr, const char *str);
91  *     void   darray_append_lit(darray(char) arr, char stringLiteral[N+1]);
92  *
93  *     void   darray_prepend_string(darray(char) arr, const char *str);
94  *     void   darray_prepend_lit(darray(char) arr, char stringLiteral[N+1]);
95  *
96  *     void   darray_from_string(darray(T) arr, const char *str);
97  *     void   darray_from_lit(darray(char) arr, char stringLiteral[N+1]);
98  *
99  * Size management:
100  *
101  *     void   darray_resize(darray(T) arr, size_t newSize);
102  *     void   darray_resize0(darray(T) arr, size_t newSize);
103  *
104  *     void   darray_realloc(darray(T) arr, size_t newAlloc);
105  *     void   darray_growalloc(darray(T) arr, size_t newAlloc);
106  *
107  *     void   darray_make_room(darray(T) arr, size_t room);
108  *
109  * Traversal:
110  *
111  *     darray_foreach(T *&i, darray(T) arr) {...}
112  *     darray_foreach_reverse(T *&i, darray(T) arr) {...}
113  *
114  * Except for darray_foreach and darray_foreach_reverse,
115  * all macros evaluate their non-darray arguments only once.
116  */
117
118 /*** Life cycle ***/
119
120 #define darray(type) struct {type *item; size_t size; size_t alloc;}
121
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)
125
126
127 /*
128  * Typedefs for darrays of common types.  These are useful
129  * when you want to pass a pointer to an darray(T) around.
130  *
131  * The following will produce an incompatible pointer warning:
132  *
133  *     void foo(darray(int) *arr);
134  *     darray(int) arr = darray_new();
135  *     foo(&arr);
136  *
137  * The workaround:
138  *
139  *     void foo(darray_int *arr);
140  *     darray_int arr = darray_new();
141  *     foo(&arr);
142  */
143
144 typedef darray(char)           darray_char;
145 typedef darray(signed char)    darray_schar;
146 typedef darray(unsigned char)  darray_uchar;
147
148 typedef darray(short)          darray_short;
149 typedef darray(int)            darray_int;
150 typedef darray(long)           darray_long;
151
152 typedef darray(unsigned short) darray_ushort;
153 typedef darray(unsigned int)   darray_uint;
154 typedef darray(unsigned long)  darray_ulong;
155
156
157 /*** Access ***/
158
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)
163
164
165 /*** Insertion (single item) ***/
166
167 #define darray_append(arr, ...) do { \
168                 darray_resize(arr, (arr).size+1); \
169                 (arr).item[(arr).size-1] = (__VA_ARGS__); \
170         } while(0)
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__); \
175         } while(0)
176 #define darray_push(arr, ...) darray_append(arr, __VA_ARGS__)
177
178
179 /*** Insertion (multiple items) ***/
180
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)); \
185         } while(0)
186
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)); \
192         } while(0)
193
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; \
199         } while(0)
200
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; \
207         } while(0)
208
209 #if HAVE_TYPEOF
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__)
212 #endif
213
214 #define darray_appends_t(arr, type, ...) do { \
215                 type __src[] = {__VA_ARGS__}; \
216                 darray_append_items(arr, __src, sizeof(__src)/sizeof(*__src)); \
217         } while(0)
218 #define darray_prepends_t(arr, type, ...) do { \
219                 type __src[] = {__VA_ARGS__}; \
220                 darray_prepend_items(arr, __src, sizeof(__src)/sizeof(*__src)); \
221         } while(0)
222
223
224 /*** Removal ***/
225
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)
229
230
231 /*** Replacement ***/
232
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)))
235
236
237 /*** String buffer ***/
238
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)
241
242 #define darray_prepend_string(arr, str) do { \
243                 const char *__str = (str); \
244                 darray_prepend_items_nullterminate(arr, __str, strlen(__str)); \
245         } while(0)
246 #define darray_prepend_lit(arr, stringLiteral) \
247         darray_prepend_items_nullterminate(arr, stringLiteral, sizeof(stringLiteral) - 1)
248
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)
251
252
253 /*** Size management ***/
254
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)); \
262                 } \
263         } while(0)
264
265 #define darray_realloc(arr, newAlloc) do { \
266                 (arr).item = realloc((arr).item, ((arr).alloc = (newAlloc)) * sizeof(*(arr).item)); \
267         } while(0)
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)); \
272         } while(0)
273
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; })
276 #endif
277
278 static inline size_t darray_next_alloc(size_t alloc, size_t need)
279 {
280         if (alloc == 0)
281                 alloc = 1;
282         while (alloc < need)
283                 alloc *= 2;
284         return alloc;
285 }
286
287
288 /*** Traversal ***/
289
290 /*
291  * darray_foreach(T *&i, darray(T) arr) {...}
292  *
293  * Traverse a darray.  `i` must be declared in advance as a pointer to an item.
294  */
295 #define darray_foreach(i, arr) \
296         for ((i) = &(arr).item[0]; (i) < &(arr).item[(arr).size]; (i)++)
297
298 /*
299  * darray_foreach_reverse(T *&i, darray(T) arr) {...}
300  *
301  * Like darray_foreach, but traverse in reverse order.
302  */
303 #define darray_foreach_reverse(i, arr) \
304         for ((i) = &(arr).item[(arr).size]; (i)-- > &(arr).item[0]; )
305
306
307 #endif /* CCAN_DARRAY_H */
308
309 /*
310
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.
314
315 darray_from_string(arr, str) copies a string to an darray_char.
316
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.
320
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.
323
324 The following require HAVE_TYPEOF==1 :
325
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.\
328
329
330 Examples:
331
332         darray(int)  arr;
333         int        *i;
334         
335         darray_appends(arr, 0,1,2,3,4);
336         darray_appends(arr, -5,-4,-3,-2,-1);
337         darray_foreach(i, arr)
338                 printf("%d ", *i);
339         printf("\n");
340         
341         darray_free(arr);
342         
343
344         typedef struct {int n,d;} Fraction;
345         darray(Fraction) fractions;
346         Fraction        *i;
347         
348         darray_appends(fractions, {3,4}, {3,5}, {2,1});
349         darray_foreach(i, fractions)
350                 printf("%d/%d\n", i->n, i->d);
351         
352         darray_free(fractions);
353 */