array.h 15.1 KB
Newer Older
Götz Lindenmaier's avatar
Götz Lindenmaier committed
1
/*
Michael Beck's avatar
Michael Beck committed
2
 * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 *
 * This file is part of libFirm.
 *
 * This file may be distributed and/or modified under the terms of the
 * GNU General Public License version 2 as published by the Free Software
 * Foundation and appearing in the file LICENSE.GPL included in the
 * packaging of this file.
 *
 * Licensees holding valid libFirm Professional Edition licenses may use
 * this file in accordance with the libFirm Commercial License.
 * Agreement provided with the Software.
 *
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
18
 */
Boris Boesler's avatar
Boris Boesler committed
19

Michael Beck's avatar
Michael Beck committed
20
/**
21
22
 * @file
 * @brief     Dynamic and flexible arrays for C.
23
 * @author    Markus Armbruster, Michael Beck, Matthias Braun, Sebastian Hack
24
 * @version   $Id$
Michael Beck's avatar
Michael Beck committed
25
 */
26
27
#ifndef FIRM_ADT_ARRAY_H
#define FIRM_ADT_ARRAY_H
Christian Schäfer's avatar
Christian Schäfer committed
28
29
30

#include <assert.h>
#include <stddef.h>
31

32
#include "firm_config.h"
33
#include "obst.h"
Michael Beck's avatar
Michael Beck committed
34
35
#include "fourcc.h"
#include "align.h"
36
#include "xmalloc.h"
Christian Schäfer's avatar
Christian Schäfer committed
37

Michael Beck's avatar
Michael Beck committed
38
39
40
#define ARR_D_MAGIC	FOURCC('A','R','R','D')
#define ARR_A_MAGIC	FOURCC('A','R','R','A')
#define ARR_F_MAGIC	FOURCC('A','R','R','F')
Christian Schäfer's avatar
Christian Schäfer committed
41

Michael Beck's avatar
Michael Beck committed
42
43
44
45
46
47
48
49
50
51
52
53
/**
 * Creates a flexible array.
 *
 * @param type     The element type of the new array.
 * @param nelts    a size_t expression evaluating to the number of elements
 *
 * This macro creates a flexible array of a given type at runtime.
 * The size of the array can be changed later.
 *
 * @return A pointer to the flexible array (can be used as a pointer to the
 *         first element of this array).
 */
Christian Schäfer's avatar
Christian Schäfer committed
54
#define NEW_ARR_F(type, nelts)						\
Michael Beck's avatar
Michael Beck committed
55
  ((type *)_new_arr_f ((nelts), sizeof(type) * (nelts)))
Michael Beck's avatar
Michael Beck committed
56
57

/**
58
 * Creates a new flexible array with the same number of elements as a
Michael Beck's avatar
Michael Beck committed
59
60
61
62
63
64
65
66
67
68
69
 * given one.
 *
 * @param type     The element type of the new array.
 * @param arr      An array from which the number of elements will be taken
 *
 * This macro creates a flexible array of a given type at runtime.
 * The size of the array can be changed later.
 *
 * @return A pointer to the flexible array (can be used as a pointer to the
 *         first element of this array).
 */
Christian Schäfer's avatar
Christian Schäfer committed
70
71
#define CLONE_ARR_F(type, arr)			\
  NEW_ARR_F (type, ARR_LEN ((arr)))
Michael Beck's avatar
Michael Beck committed
72
73
74
75
76
77
78
79
80
81
82
83
84

/**
 * Duplicates an array and returns the new flexible one.
 *
 * @param type     The element type of the new array.
 * @param arr      An array from which the elements will be duplicated
 *
 * This macro creates a flexible array of a given type at runtime.
 * The size of the array can be changed later.
 *
 * @return A pointer to the flexible array (can be used as a pointer to the
 *         first element of this array).
 */
Christian Schäfer's avatar
Christian Schäfer committed
85
86
#define DUP_ARR_F(type, arr)							\
  memcpy (CLONE_ARR_F (type, (arr)), (arr), sizeof(type) * ARR_LEN((arr)))
Michael Beck's avatar
Michael Beck committed
87
88
89
90
91
92

/**
 * Delete a flexible array.
 *
 * @param arr    The flexible array.
 */
Michael Beck's avatar
Michael Beck committed
93
#define DEL_ARR_F(arr) (_del_arr_f ((arr)))
Christian Schäfer's avatar
Christian Schäfer committed
94

Michael Beck's avatar
Michael Beck committed
95
/**
Götz Lindenmaier's avatar
Götz Lindenmaier committed
96
 * Creates a dynamic array on an obstack.
Michael Beck's avatar
Michael Beck committed
97
98
 *
 * @param type     The element type of the new array.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
99
100
 * @param obstack  A struct obstack * were the data will be allocated
 * @param nelts    A size_t expression evaluating to the number of elements
Michael Beck's avatar
Michael Beck committed
101
102
103
104
105
106
107
 *
 * This macro creates a dynamic array of a given type at runtime.
 * The size of the array cannot be changed later.
 *
 * @return A pointer to the dynamic array (can be used as a pointer to the
 *         first element of this array).
 */
Christian Schäfer's avatar
Christian Schäfer committed
108
109
110
111
#define NEW_ARR_D(type, obstack, nelts)					\
  (  nelts								\
   ? (type *)_new_arr_d ((obstack), (nelts), sizeof(type) * (nelts))	\
   : (type *)arr_mt_descr.v.elts)
Michael Beck's avatar
Michael Beck committed
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

/**
 * Creates a new dynamic array with the same number of elements as a
 * given one.
 *
 * @param type     The element type of the new array.
 * @param obstack  An struct obstack * were the data will be allocated
 * @param arr      An array from which the number of elements will be taken
 *
 * This macro creates a dynamic array of a given type at runtime.
 * The size of the array cannot be changed later.
 *
 * @return A pointer to the dynamic array (can be used as a pointer to the
 *         first element of this array).
 */
Christian Schäfer's avatar
Christian Schäfer committed
127
128
#define CLONE_ARR_D(type, obstack, arr)		\
  NEW_ARR_D (type, (obstack), ARR_LEN ((arr)))
Michael Beck's avatar
Michael Beck committed
129
130
131
132
133
134
135
136
137
138
139
140
141
142

/**
 * Duplicates an array and returns the new dynamic one.
 *
 * @param type     The element type of the new array.
 * @param obstack  An struct obstack * were the data will be allocated
 * @param arr      An array from which the elements will be duplicated
 *
 * This macro creates a dynamic array of a given type at runtime.
 * The size of the array cannot be changed later.
 *
 * @return A pointer to the dynamic array (can be used as a pointer to the
 *         first element of this array).
 */
Christian Schäfer's avatar
Christian Schäfer committed
143
144
145
#define DUP_ARR_D(type, obstack, arr)							\
  memcpy (CLONE_ARR_D (type, (obstack), (arr)), (arr), sizeof(type) * ARR_LEN ((arr)))

Michael Beck's avatar
Michael Beck committed
146
147
/**
 * Create an automatic array which will be deleted at return from function.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
148
 * Beware, the data will be allocated on the function stack!
Michael Beck's avatar
Michael Beck committed
149
150
151
152
153
154
155
156
 *
 * @param type     The element type of the new array.
 * @param var      A lvalue of type (type *) which will hold the new array.
 * @param n        number of elements in this array.
 *
 * This macro creates a dynamic array on the functions stack of a given type at runtime.
 * The size of the array cannot be changed later.
 */
Christian Schäfer's avatar
Christian Schäfer committed
157
158
159
160
161
162
163
164
#define NEW_ARR_A(type, var, n)									\
  do {												\
    int _nelts = (n);										\
    assert (_nelts >= 0);									\
    (var) = (void *)((_arr_descr *)alloca (_ARR_ELTS_OFFS + sizeof(type) * _nelts))->v.elts;	\
    _ARR_SET_DBGINF (_ARR_DESCR ((var)), ARR_A_MAGIC, sizeof (type));				\
    (void)(_ARR_DESCR ((var))->nelts = _nelts);							\
  } while (0)
Michael Beck's avatar
Michael Beck committed
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179

/**
 * Creates a new automatic array with the same number of elements as a
 * given one.
 *
 * @param type     The element type of the new array.
 * @param var      A lvalue of type (type *) which will hold the new array.
 * @param arr      An array from which the elements will be duplicated
 *
 * This macro creates a dynamic array of a given type at runtime.
 * The size of the array cannot be changed later.
 *
 * @return A pointer to the dynamic array (can be used as a pointer to the
 *         first element of this array).
 */
Christian Schäfer's avatar
Christian Schäfer committed
180
181
182
#define CLONE_ARR_A(type, var, arr)		\
  NEW_ARR_A (type, (var), ARR_LEN ((arr)))

Michael Beck's avatar
Michael Beck committed
183
184
185
186
187
188
189
190
191
192
193
194
195
/**
 * Duplicates an array and returns a new automatic one.
 *
 * @param type     The element type of the new array.
 * @param var      A lvalue of type (type *) which will hold the new array.
 * @param arr      An array from with the number of elements will be taken
 *
 * This macro creates a dynamic array of a given type at runtime.
 * The size of the array cannot be changed later.
 *
 * @return A pointer to the dynamic array (can be used as a pointer to the
 *         first element of this array).
 */
Christian Schäfer's avatar
Christian Schäfer committed
196
197
198
199
200
#define DUP_ARR_A(type, var, arr)					\
  do { CLONE_ARR_A(type, (var), (arr));					\
       memcpy ((var), (arr), sizeof (type) * ARR_LEN ((arr))); }	\
  while (0)

Michael Beck's avatar
Michael Beck committed
201
202
203
204
205
206
207
208
/**
 * Declare an initialized (zero'ed) array of fixed size.
 * This macro should be used at file scope only.
 *
 * @param type     The element type of the new array.
 * @param var      A lvalue of type (type *) which will hold the new array.
 * @param _nelts   Number of elements in this new array.
 */
Christian Schäfer's avatar
Christian Schäfer committed
209
210
211
212
213
214
#define DECL_ARR_S(type, var, _nelts)					\
  ARR_STRUCT(type, (_nelts) ? (_nelts) : 1) _##var;			\
  type *var = (_ARR_SET_DBGINF (&_##var, ARR_A_MAGIC, sizeof (type)),	\
	       _##var.nelts = _nelts,					\
	       _##var.v.elts)

Michael Beck's avatar
Michael Beck committed
215
216
217
218
219
/**
 * Returns the length of an array
 *
 * @param arr  a flexible, dynamic, automatic or static array.
 */
Christian Schäfer's avatar
Christian Schäfer committed
220
221
#define ARR_LEN(arr) (ARR_VRFY ((arr)), _ARR_DESCR((arr))->nelts)

Michael Beck's avatar
Michael Beck committed
222
223
224
225
226
227
228
229
230
231
/**
 * Resize a flexible array, allocate more data if needed but do NOT
 * reduce.
 *
 * @param type     The element type of the array.
 * @param arr      The array, which must be an lvalue.
 * @param n        The new size of the array.
 *
 * @remark  This macro may change arr, so update all references!
 */
Christian Schäfer's avatar
Christian Schäfer committed
232
#define ARR_RESIZE(type, arr, n)					\
Michael Beck's avatar
Michael Beck committed
233
  ((arr) = _arr_resize ((arr), (n), sizeof(type)))
Michael Beck's avatar
Michael Beck committed
234
235
236
237
238
239
240
241
242
243

/**
 * Resize a flexible array, always reallocate data.
 *
 * @param type     The element type of the array.
 * @param arr      The array, which must be an lvalue.
 * @param n        The new size of the array.
 *
 * @remark  This macro may change arr, so update all references!
 */
Christian Schäfer's avatar
Christian Schäfer committed
244
#define ARR_SETLEN(type, arr, n)					\
Michael Beck's avatar
Michael Beck committed
245
  ((arr) = _arr_setlen ((arr), (n), sizeof(type) * (n)))
Michael Beck's avatar
Michael Beck committed
246

247
248
249
250
251
252
/** Set a length smaller than the current length of the array.  Do not
 *  resize. len must be <= ARR_LEN(arr). */
#define ARR_SHRINKLEN(arr,len)                                          \
   (ARR_VRFY ((arr)), assert(_ARR_DESCR((arr))->nelts >= len),             \
    _ARR_DESCR((arr))->nelts = len)

Michael Beck's avatar
Michael Beck committed
253
254
255
256
257
258
259
260
261
/**
 * Resize a flexible array by growing it by delta elements.
 *
 * @param type     The element type of the array.
 * @param arr      The array, which must be an lvalue.
 * @param delta    The delta number of elements.
 *
 * @remark  This macro may change arr, so update all references!
 */
Christian Schäfer's avatar
Christian Schäfer committed
262
263
#define ARR_EXTEND(type, arr, delta)			\
  ARR_RESIZE (type, (arr), ARR_LEN ((arr)) + (delta))
Michael Beck's avatar
Michael Beck committed
264
265
266
267
268
269
270
271
272
273
274

/**
 * Resize a flexible array to hold n elements only if it is currently shorter
 * than n.
 *
 * @param type     The element type of the array.
 * @param arr      The array, which must be an lvalue.
 * @param n        The new size of the array.
 *
 * @remark  This macro may change arr, so update all references!
 */
Christian Schäfer's avatar
Christian Schäfer committed
275
276
#define ARR_EXTO(type, arr, n)						\
  ((n) >= ARR_LEN ((arr)) ? ARR_RESIZE (type, (arr), (n)+1) : (arr))
Michael Beck's avatar
Michael Beck committed
277
278
279
280
281
282
283
284

/**
 * Append one element to a flexible array.
 *
 * @param type     The element type of the array.
 * @param arr      The array, which must be an lvalue.
 * @param elt      The new element, must be of type (type).
 */
Christian Schäfer's avatar
Christian Schäfer committed
285
286
287
288
289
290
291
292
#define ARR_APP1(type, arr, elt)					\
  (ARR_EXTEND (type, (arr), 1), (arr)[ARR_LEN ((arr))-1] = (elt))

#ifdef NDEBUG
# define ARR_VRFY(arr) ((void)0)
# define ARR_IDX_VRFY(arr, idx) ((void)0)
#else
# define ARR_VRFY(arr)									\
Michael Beck's avatar
Michael Beck committed
293
294
295
296
    assert (   (   (_ARR_DESCR((arr))->magic == ARR_D_MAGIC)				\
		|| (_ARR_DESCR((arr))->magic == ARR_A_MAGIC)				\
		|| (_ARR_DESCR((arr))->magic == ARR_F_MAGIC))				\
	    && (   (_ARR_DESCR((arr))->magic != ARR_F_MAGIC)				\
Christian Schäfer's avatar
Christian Schäfer committed
297
298
299
300
301
302
303
		|| (_ARR_DESCR((arr))->u.allocated >= _ARR_DESCR((arr))->nelts))	\
	    && (_ARR_DESCR((arr))->nelts >= 0))
# define ARR_IDX_VRFY(arr, idx)				\
    assert ((0 <= (idx)) && ((idx) < ARR_LEN ((arr))))
#endif


304
305
306
/* Private !!!
   Don't try this at home, kids, we're trained professionals ;->
   ... or at the IPD, either. */
Christian Schäfer's avatar
Christian Schäfer committed
307
308
#ifdef NDEBUG
# define _ARR_DBGINF_DECL
309
# define _ARR_SET_DBGINF(descr, co, es)
Christian Schäfer's avatar
Christian Schäfer committed
310
#else
Michael Beck's avatar
Michael Beck committed
311
# define _ARR_DBGINF_DECL int magic; size_t eltsize;
Christian Schäfer's avatar
Christian Schäfer committed
312
# define _ARR_SET_DBGINF(descr, co, es)					\
Michael Beck's avatar
Michael Beck committed
313
    ( (descr)->magic = (co), (descr)->eltsize = (es) )
Christian Schäfer's avatar
Christian Schäfer committed
314
315
#endif

Michael Beck's avatar
Michael Beck committed
316
317
318
/**
 * Construct an array header.
 */
Christian Schäfer's avatar
Christian Schäfer committed
319
320
321
322
323
324
325
326
327
328
329
330
331
332
#define ARR_STRUCT(type, _nelts)						\
  struct {									\
    _ARR_DBGINF_DECL								\
    union {									\
      struct obstack *obstack;	/* dynamic: allocated on this obstack */	\
      int allocated;			/* flexible: #slots allocated */	\
    } u;									\
    int nelts;									\
    union {									\
      type elts[(_nelts)];							\
      aligned_type align[1];							\
    } v;									\
  }

Michael Beck's avatar
Michael Beck committed
333
334
335
/**
 * The array descriptor header type.
 */
Christian Schäfer's avatar
Christian Schäfer committed
336
337
338
339
typedef ARR_STRUCT (aligned_type, 1) _arr_descr;

extern _arr_descr arr_mt_descr;

340
341
void *_new_arr_f (int nelts, size_t elts_size);
void _del_arr_f (void *elts);
Michael Beck's avatar
Michael Beck committed
342
void *_new_arr_d (struct obstack *obstack, int nelts, size_t elts_size);
343
344
void *_arr_resize (void *elts, int nelts, size_t elts_size);
void *_arr_setlen (void *elts, int nelts, size_t elts_size);
Christian Schäfer's avatar
Christian Schäfer committed
345
346
347
348

#define _ARR_ELTS_OFFS offsetof (_arr_descr, v.elts)
#define _ARR_DESCR(elts) ((_arr_descr *)(void *)((char *)(elts) - _ARR_ELTS_OFFS))

349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
/*
 ____             _           _      _
/ ___|  ___  _ __| |_ ___  __| |    / \   _ __ _ __ __ _ _   _ ___
\___ \ / _ \| '__| __/ _ \/ _` |   / _ \ | '__| '__/ _` | | | / __|
 ___) | (_) | |  | ||  __/ (_| |  / ___ \| |  | | | (_| | |_| \__ \
|____/ \___/|_|   \__\___|\__,_| /_/   \_\_|  |_|  \__,_|\__, |___/
                                                         |___/
*/

typedef int (_arr_cmp_func_t)(const void *a, const void *b);

/**
 * Do a binary search in an array.
 * @param arr      The array.
 * @param elm_size The size of an array element.
 * @param cmp      A comparison function for two array elements (see qsort(3) for example).
 * @param elm      A pointer to the element we are looking for.
 * @return         This is somewhat tricky. Let <code>res</code> be the return value.
 *                 If the return value is negative, then <code>elm</code> was not in the array
 *                 but <code>-res - 1</code> gives the proper location where it should be inserted.
 *                 If <code>res >= 0</code> then the element is in the array and <code>res</code>
 *                 represents its index.
 *                 That allows for testing membership and finding proper insertion indices.
 * @note           The differences to bsearch(3) which does not give proper insert locations
 *                 in the case that the element is not conatined in the array.
 */
static INLINE __attribute__((const, unused)) int
_arr_bsearch(const void *arr, size_t elm_size, _arr_cmp_func_t *cmp, const void *elm)
{
	int hi = ARR_LEN(arr);
	int lo = 0;

	while(lo < hi) {
		int md     = lo + ((hi - lo) >> 1);
		int res    = cmp((char *) arr + md * elm_size, elm);
		if(res < 0)
			lo = md + 1;
		else if(res > 0)
			hi = md;
		else
			return md;
	}

	return -(lo + 1);
}

#define ARR_SET_INSERT(arr, cmp, elm) \
do { \
	int idx = _arr_bsearch((arr), sizeof((arr)[0]), (cmp), (elm)); \
	if (idx < 0) { \
		idx = -idx - 1; \
		memmove(&(arr)[idx+1], &(arr)[idx], sizeof((arr)[0]) * (_ARR_DESCR((arr))->nelts - idx)); \
Sebastian Hack's avatar
Sebastian Hack committed
401
		(arr)[idx] = *(elm); \
402
403
404
405
		++_ARR_DESCR((arr))->nelts; \
	} \
} while(0)

Sebastian Hack's avatar
Sebastian Hack committed
406
407
408
409
410
411
412
413
414
415
416
417
#define ARR_SET_INSERT_EXT(type, arr, cmp, elm) \
do { \
	int idx = _arr_bsearch((arr), sizeof((arr)[0]), (cmp), (elm)); \
	if (idx < 0) { \
		int len = ARR_LEN(arr); \
		idx = -idx - 1; \
		ARR_EXTO(type, arr, len + 1); \
		memmove(&(arr)[idx+1], &(arr)[idx], sizeof((arr)[0]) * (len - idx)); \
		(arr)[idx] = *(elm); \
	} \
} while(0)

418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
#define ARR_SET_REMOVE(arr, cmp, elm) \
do { \
	int idx = _arr_bsearch((arr), sizeof((arr)[0]), (cmp), (elm)); \
	if (idx >= 0) { \
		--_ARR_DESCR((arr))->nelts; \
		memmove(&(arr)[idx], &(arr)[idx+1], sizeof((arr)[0]) * (_ARR_DESCR((arr))->nelts - idx)); \
	} \
} while(0)

/**
 * Return the index of an element in an array set.
 * To check for containment, use the expression:
 *     (ARR_SET_GET_IDX(arr, cmp, elm) >= 0)
 *
 * @return The index or some value < 0 if the element was not in the set.
 */
#define ARR_SET_GET_IDX(arr, cmp, elm) \
Sebastian Hack's avatar
Sebastian Hack committed
435
436
437
438
439
440
441
442
443
444
	(ARR_VRFY((arr)), _arr_bsearch((arr), sizeof((arr)[0]), cmp, (elm)))

#ifdef __GNUC__
#define ARR_SET_GET(arr, cmp, elm) \
	({ int idx = ARR_SET_GET_IDX(arr, cmp, elm); idx >= 0 ? &(arr)[idx] : NULL; })
#else
#define ARR_SET_GET(arr, cmp, elm) \
	(ARR_SET_GET_IDX(arr, cmp, elm) >= 0 ? &(arr)[ARR_SET_GET_IDX(arr, cmp, elm)] : NULL)
#endif

445
446
447
448
449
450
451
452
453
454
455

#define ARR_SET_CONTAINS(arr, cmp, elm) \
	(ARR_SET_GET_IDX((arr), (cmp), (elm)) >= 0)

/**
 * Reset the array set.
 * This just initializes the size to zero but does not wipe out any element.
 */
#define ARR_SET_CLEAR(arr) ARR_SHRINKLEN(arr, 0)


456
#endif /* FIRM_ADT_ARRAY_H */