2 * Copyright (C) 1995-2011 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @brief Dynamic and flexible arrays for C.
23 * @author Markus Armbruster, Michael Beck, Matthias Braun, Sebastian Hack
25 #ifndef FIRM_ADT_ARRAY_H
26 #define FIRM_ADT_ARRAY_H
37 * @defgroup array Arrays
42 * Creates a flexible array.
44 * @param type The element type of the new array.
45 * @param nelts a size_t expression evaluating to the number of elements
47 * This macro creates a flexible array of a given type at runtime.
48 * The size of the array can be changed later.
50 * @return A pointer to the flexible array (can be used as a pointer to the
51 * first element of this array).
53 #define NEW_ARR_F(type, nelts) \
54 ((type *)ir_new_arr_f((nelts), sizeof(type) * (nelts)))
57 * Create a flexible array and null its contents.
59 #define NEW_ARR_FZ(type, nelts) \
60 ((type*)memset(NEW_ARR_F(type, (nelts)), 0, sizeof(type) * (nelts)))
63 * Creates a new flexible array with the same number of elements as a
66 * @param type The element type of the new array.
67 * @param arr An array from which the number of elements will be taken
69 * This macro creates a flexible array of a given type at runtime.
70 * The size of the array can be changed later.
72 * @return A pointer to the flexible array (can be used as a pointer to the
73 * first element of this array).
75 #define CLONE_ARR_F(type, arr) \
76 NEW_ARR_F(type, ARR_LEN((arr)))
79 * Duplicates an array and returns the new flexible one.
81 * @param type The element type of the new array.
82 * @param arr An array from which the elements will be duplicated
84 * This macro creates a flexible array of a given type at runtime.
85 * The size of the array can be changed later.
87 * @return A pointer to the flexible array (can be used as a pointer to the
88 * first element of this array).
90 #define DUP_ARR_F(type, arr) \
91 ((type*) memcpy(CLONE_ARR_F(type, (arr)), (arr), sizeof(type) * ARR_LEN((arr))))
94 * Delete a flexible array.
96 * @param arr The flexible array.
98 #define DEL_ARR_F(arr) (ir_del_arr_f((void *)(arr)))
101 * Creates a dynamic array on an obstack.
103 * @param type The element type of the new array.
104 * @param obstack A struct obstack * were the data will be allocated
105 * @param nelts A size_t expression evaluating to the number of elements
107 * This macro creates a dynamic array of a given type at runtime.
108 * The size of the array cannot be changed later.
110 * @return A pointer to the dynamic array (can be used as a pointer to the
111 * first element of this array).
113 #define NEW_ARR_D(type, obstack, nelts) \
115 ? (type *)ir_new_arr_d((obstack), (nelts), sizeof(type) * (nelts)) \
116 : (type *)arr_mt_descr.elts)
119 * Create a dynamic array on an obstack and null its contents.
121 #define NEW_ARR_DZ(type, obstack, nelts) \
122 ((type*)memset(NEW_ARR_D(type, (obstack), (nelts)), 0, sizeof(type) * (nelts)))
125 * Creates a new dynamic array with the same number of elements as a
128 * @param type The element type of the new array.
129 * @param obstack An struct obstack * were the data will be allocated
130 * @param arr An array from which the number of elements will be taken
132 * This macro creates a dynamic array of a given type at runtime.
133 * The size of the array cannot be changed later.
135 * @return A pointer to the dynamic array (can be used as a pointer to the
136 * first element of this array).
138 #define CLONE_ARR_D(type, obstack, arr) \
139 NEW_ARR_D(type, (obstack), ARR_LEN((arr)))
142 * Duplicates an array and returns the new dynamic one.
144 * @param type The element type of the new array.
145 * @param obstack An struct obstack * were the data will be allocated
146 * @param arr An array from which the elements will be duplicated
148 * This macro creates a dynamic array of a given type at runtime.
149 * The size of the array cannot be changed later.
151 * @return A pointer to the dynamic array (can be used as a pointer to the
152 * first element of this array).
154 #define DUP_ARR_D(type, obstack, arr) \
155 ((type*)memcpy(CLONE_ARR_D(type, (obstack), (arr)), (arr), sizeof(type) * ARR_LEN ((arr))))
158 * Returns the length of an array
160 * @param arr a flexible, dynamic, automatic or static array.
162 #define ARR_LEN(arr) (ARR_VRFY((arr)), ARR_DESCR((arr))->nelts)
165 * Resize a flexible array, allocate more data if needed but do NOT
168 * @param type The element type of the array.
169 * @param arr The array, which must be an lvalue.
170 * @param n The new size of the array.
172 * @remark This macro may change arr, so update all references!
174 #define ARR_RESIZE(type, arr, n) \
175 ((arr) = (type*) ir_arr_resize((void *)(arr), (n), sizeof(type)))
178 * Resize a flexible array, always reallocate data.
180 * @param type The element type of the array.
181 * @param arr The array, which must be an lvalue.
182 * @param n The new size of the array.
184 * @remark This macro may change arr, so update all references!
186 #define ARR_SETLEN(type, arr, n) \
187 ((arr) = (type*) ir_arr_setlen((void *)(arr), (n), sizeof(type) * (n)))
190 * Resize a flexible array by growing it by delta elements.
192 * @param type The element type of the array.
193 * @param arr The array, which must be an lvalue.
194 * @param delta The delta number of elements.
196 * @remark This macro may change arr, so update all references!
198 #define ARR_EXTEND(type, arr, delta) \
199 ARR_RESIZE(type, (arr), ARR_LEN((arr)) + (delta))
202 * Resize a flexible array to hold n elements only if it is currently shorter
205 * @param type The element type of the array.
206 * @param arr The array, which must be an lvalue.
207 * @param n The new size of the array.
209 * @remark This macro may change arr, so update all references!
211 #define ARR_EXTO(type, arr, n) \
213 if ((n) >= ARR_LEN(arr)) { ARR_RESIZE(type, arr, (n)+1); } \
217 * Append one element to a flexible array.
219 * @param type The element type of the array.
220 * @param arr The array, which must be an lvalue.
221 * @param elt The new element, must be of type (type).
223 #define ARR_APP1(type, arr, elt) \
224 (ARR_EXTEND(type, (arr), 1), (arr)[ARR_LEN((arr))-1] = (elt))
227 # define ARR_VRFY(arr) ((void)0)
228 # define ARR_IDX_VRFY(arr, idx) ((void)0)
230 /** Check array for consistency */
231 # define ARR_VRFY(arr) ir_verify_arr(arr)
232 /** Check if index is within array bounds */
233 # define ARR_IDX_VRFY(arr, idx) \
234 assert((0 <= (idx)) && ((idx) < ARR_LEN((arr))))
239 /** A type that has most constrained alignment. */
247 * The array descriptor header type.
250 int magic; /**< array magic. */
251 size_t allocated; /**< number of allocated elements. */
252 size_t nelts; /**< current length of the array. */
253 aligned_type elts[1]; /**< start of the array data. */
256 extern ir_arr_descr arr_mt_descr;
258 FIRM_API void *ir_new_arr_f(size_t nelts, size_t elts_size);
259 FIRM_API void ir_del_arr_f(void *elts);
260 FIRM_API void *ir_new_arr_d(struct obstack *obstack, size_t nelts, size_t elts_size);
261 FIRM_API void *ir_arr_resize(void *elts, size_t nelts, size_t elts_size);
262 FIRM_API void *ir_arr_setlen(void *elts, size_t nelts, size_t elts_size);
263 FIRM_API void ir_verify_arr(const void *elts);
265 #define ARR_ELTS_OFFS offsetof(ir_arr_descr, elts)
266 #define ARR_DESCR(elts) ((ir_arr_descr *)(void *)((char *)(elts) - ARR_ELTS_OFFS))
268 /** Set a length smaller than the current length of the array. Do not
269 * resize. len must be <= ARR_LEN(arr). */
270 static inline void ARR_SHRINKLEN(void *arr, size_t new_len)
273 assert(ARR_DESCR(arr)->nelts >= new_len);
274 ARR_DESCR(arr)->nelts = new_len;