d32eeef58f9eecae9c5f4b614f33eaaddcff36d0
[apps/pfixtools.git] / array.h
1 /******************************************************************************/
2 /*          pfixtools: a collection of postfix related tools                  */
3 /*          ~~~~~~~~~                                                         */
4 /*  ________________________________________________________________________  */
5 /*                                                                            */
6 /*  Redistribution and use in source and binary forms, with or without        */
7 /*  modification, are permitted provided that the following conditions        */
8 /*  are met:                                                                  */
9 /*                                                                            */
10 /*  1. Redistributions of source code must retain the above copyright         */
11 /*     notice, this list of conditions and the following disclaimer.          */
12 /*  2. Redistributions in binary form must reproduce the above copyright      */
13 /*     notice, this list of conditions and the following disclaimer in the    */
14 /*     documentation and/or other materials provided with the distribution.   */
15 /*  3. The names of its contributors may not be used to endorse or promote    */
16 /*     products derived from this software without specific prior written     */
17 /*     permission.                                                            */
18 /*                                                                            */
19 /*  THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND   */
20 /*  ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE     */
21 /*  IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR        */
22 /*  PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS    */
23 /*  BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR    */
24 /*  CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF      */
25 /*  SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS  */
26 /*  INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN   */
27 /*  CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)   */
28 /*  ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF    */
29 /*  THE POSSIBILITY OF SUCH DAMAGE.                                           */
30 /******************************************************************************/
31
32 /*
33  * Copyright © 2008 Florent Bruneau
34  */
35
36 #ifndef PFIXTOOLS_ARRAY_H
37 #define PFIXTOOLS_ARRAY_H
38
39 #include "common.h"
40 #include "mem.h"
41 #include <sys/mman.h>
42
43 #define PRIV_ARRAY(Type)                                                       \
44     struct {                                                                   \
45         Type    *data;                                                         \
46         uint32_t len;                                                          \
47         uint32_t size;                                                         \
48         unsigned locked : 1;                                                   \
49     }
50
51 /** Declare type PA(Type).
52  */
53 #define PARRAY(Type)                                                           \
54     typedef PRIV_ARRAY(Type*) Type ## _ptr_array_t;                            \
55     static inline Type ## _ptr_array_t *Type ## _ptr_array_new(void)           \
56     {                                                                          \
57         return p_new(Type ## _ptr_array_t, 1);                                 \
58     }                                                                          \
59                                                                                \
60     static inline void Type ## _ptr_array_delete(Type ## _ptr_array_t **array) \
61     {                                                                          \
62         if (*array) {                                                          \
63             if ((*array)->locked) {                                            \
64                 array_unlock(**array);                                         \
65             }                                                                  \
66             array_wipe(**array);                                               \
67             p_delete(array);                                                   \
68         }                                                                      \
69     }
70
71 /** Declare types A(Type) and PA(Type).
72  */
73 #define ARRAY(Type)                                                            \
74     typedef PRIV_ARRAY(Type) Type ## _array_t;                                 \
75                                                                                \
76     static inline Type ## _array_t *Type ## _array_new(void)                   \
77     {                                                                          \
78         return p_new(Type ## _array_t, 1);                                     \
79     }                                                                          \
80                                                                                \
81     static inline void Type ## _array_delete(Type ## _array_t **array)         \
82     {                                                                          \
83         if (*array) {                                                          \
84             if ((*array)->locked) {                                            \
85                 array_unlock(**array);                                         \
86             }                                                                  \
87             array_wipe(**array);                                               \
88             p_delete(array);                                                   \
89         }                                                                      \
90     }                                                                          \
91                                                                                \
92     PARRAY(Type)
93
94 /** Type A(Type) is a dynamic array of elements of type @c Type.
95  */
96 #define A(Type) Type ## _array_t
97
98 /** Type PA(Type) is a dynamic array of pointers to type @c Type.
99  */
100 #define PA(Type) Type ## _ptr_array_t
101
102 #define ARRAY_INIT { NULL, 0, 0, false }
103
104 #define array_init(array) (array) = ARRAY_INIT
105
106 #define array_can_edit(array) (!(array).locked)
107
108 #define array_ensure_can_edit(array)                                           \
109     assert(array_can_edit(array) && "Trying to edit array while it is locked")
110
111 #define array_wipe(array)                                                      \
112     do {                                                                       \
113         array_ensure_can_edit(array);                                          \
114         p_delete(&(array).data);                                               \
115         (array).len  = 0;                                                      \
116         (array).size = 0;                                                      \
117     } while (0)
118
119
120 /******* MEMORY MANAGEMENT *******/
121
122 /** Return the len of the array (number of elements contained in the array).
123  */
124 #define array_len(array) ((array).len)
125
126 /** Return the capacity of the array (number of elements the array can contain
127  * without growing its internal buffer).
128  */
129 #define array_size(array) ((array).size)
130
131 /** Return the number of free places in the array.
132  */
133 #define array_free_space(array) (array_size(array) - array_len(array))
134
135 /** Return the size of an element of the array.
136  */
137 #define array_elt_len(array) (sizeof(*(array).data))
138
139 /** Return the number of bytes used by the content of the array.
140  */
141 #define array_byte_len(array) ((array).len * array_elt_len(array))
142
143 /** Ensure the capacity of the array if *at least* @c goal *elements*.
144  */
145 #define array_ensure_capacity(array, goal)                                     \
146     do {                                                                       \
147         array_ensure_can_edit(array);                                          \
148         if ((array).size < (goal)) {                                           \
149             const typeof((array).size) required_size = (goal);                 \
150             typeof((array).size) next_size = (array).size;                     \
151             do {                                                               \
152                 next_size = p_alloc_nr(next_size);                             \
153             } while (next_size < required_size);                               \
154             p_allocgrow(&(array).data, next_size, &(array).size);              \
155         }                                                                      \
156     } while (0)
157
158 /** Ensure the array contains place for *at least* @c delta more elements.
159  */
160 #define array_ensure_capacity_delta(array, delta)                              \
161     array_ensure_capacity(array, (array).len + (delta))
162
163 /** Ensure the array can contain @c goal elements.
164  */
165 #define array_ensure_exact_capacity(array, goal)                               \
166     if ((array).size < (goal)) {                                               \
167         array_ensure_can_edit(array);                                          \
168         p_allocgrow(&(array).data, (goal), &(array).size);                     \
169     }
170
171 /** Shrink capacity of the array to MAX(len, @c cap).
172  */
173 #define array_shrink(array, cap)                                               \
174     do {                                                                       \
175         array_ensure_can_edit(array);                                          \
176         if ((cap) < (array).size && (array).size != (array).len) {             \
177             p_shrink(&(array).data, MAX((array).len, (cap)), &(array).size);   \
178         }                                                                      \
179     } while (0)
180
181 /** Ensure the capacity of the array does not exceed its len.
182  */
183 #define array_adjust(array) array_shrink(array, 0)
184
185 #define array_lock(array)                                                      \
186     ((array).locked                                                            \
187      || (mlock((array).data, array_byte_len(array)) == 0                       \
188          && ((array).locked = true)))
189
190 #define array_unlock(array)                                                    \
191     if ((array).locked) {                                                      \
192         (void)munlock((array).data, array_byte_len(array));                    \
193         (array).locked = false;                                                \
194     }
195
196
197 /******* ADDING ELEMENTS *******/
198
199 #define array_add(array, obj)                                                  \
200     do {                                                                       \
201         array_ensure_capacity_delta(array, 1);                                 \
202         (array).data[(array).len++] = (obj);                                   \
203     } while (0)
204
205 #define array_append(array, objs, Len)                                         \
206     do {                                                                       \
207         const typeof((array).len) __len = (Len);                               \
208         array_ensure_capacity_delta(array, __len);                             \
209         memcpy((array).data + (array).len, objs,                               \
210                __len * sizeof(*(array).data));                                 \
211         (array).len += __len;                                                  \
212     } while (0)
213
214
215 /******* ACCESSSING ELEMENTS ********/
216
217 /** Getting the n'th element of the array.
218  */
219 #define array_elt(array, n) ((array).data[(n)])
220
221 #define array_first(array) array_elt(array, 0)
222 #define array_last(array) array_elt(array, (array).len - 1)
223
224 #define array_pop_last(array) array_elt(array, --((array).len))
225
226 /** Getting a pointer to the n'th element of the array.
227  */
228 #define array_ptr(array, n) ((array).data + (n))
229
230 #define array_start(array) array_ptr((array), 0)
231 #define array_end(array) array_ptr((array), array_len(array))
232
233 /****** TRAVERSING AN ARRAY *******/
234
235 /** Gives the position of pointer ptr in the array.
236  * This macro may only be used withing a loop. @ref foreach.
237  */
238 #define array_pos(array, ptr) ((ptr) - array_start(array))
239
240 /** Build a loop over the elements of an array.
241  *
242  * <code>
243  * A(MyType) array;
244  * ...
245  * foreach (MyType* element, array) {
246  *    do_something(element);
247  * }}
248  * </code>
249  *
250  * Warnings:
251  *  * remember the loop must be ended with }} (the foreach macro contains 
252  *    a not-matched opening brace).
253  *  * the macro uses a counter name __Ai, so you cannot build imbricated
254  *    array enumerations. You SHOULD NOT use this counter in your code since
255  *    it is part of the internal API and may change in the future.
256  */
257
258 #define foreach(var, array)                                                    \
259     for (uint32_t __Ai = 0 ; __Ai < (array).len ; ++__Ai) {                    \
260         var = array_ptr(array, __Ai);
261
262 /** Execute @c action for each element of the array.
263  *
264  * <code>
265  * static void do_something(MyType *element) { ... }
266  *
267  * A(MyType) array;
268  * ...
269  * array_foreach(array, do_something);
270  * </code>
271  */
272 #define array_foreach(array, action)                                           \
273     for (uint32_t __Ai = 0 ; __Ai < (array).len ; ++__Ai) {                    \
274         action(array_ptr(array, __Ai));                                        \
275     }
276
277 /** Wipe each element of the array using @c wipe, then wipe the array.
278  */
279 #define array_deep_wipe(array, wipe)                                           \
280     do {                                                                       \
281         array_foreach(array, wipe);                                            \
282         array_wipe(array);                                                     \
283     } while (0)
284
285
286
287 ARRAY(char)
288 ARRAY(int)
289 ARRAY(bool)
290 ARRAY(uint16_t)
291 ARRAY(uint32_t)
292
293 PARRAY(void)
294
295 #endif