nsz Git - libfirm/blob - include/libfirm/adt/array.h

   1 /*
   2  * This file is part of libFirm.
   3  * Copyright (C) 2012 University of Karlsruhe.
   4  */
   5
   6 /**
   7  * @file
   8  * @brief     Dynamic and flexible arrays for C.
   9  * @author    Markus Armbruster, Michael Beck, Matthias Braun, Sebastian Hack
  10  */
  11 #ifndef FIRM_ADT_ARRAY_H
  12 #define FIRM_ADT_ARRAY_H
  13
  14 #include <assert.h>
  15 #include <stddef.h>
  16
  17 #include "obst.h"
  18
  19 #include "../begin.h"
  20
  21 /**
  22  * @ingroup adt
  23  * @defgroup array Arrays
  24  * @{
  25  */
  26
  27 /**
  28  * Creates a flexible array.
  29  *
  30  * @param type     The element type of the new array.
  31  * @param nelts    a size_t expression evaluating to the number of elements
  32  *
  33  * This macro creates a flexible array of a given type at runtime.
  34  * The size of the array can be changed later.
  35  *
  36  * @return A pointer to the flexible array (can be used as a pointer to the
  37  *         first element of this array).
  38  */
  39 #define NEW_ARR_F(type, nelts) \
  40   ((type *)ir_new_arr_f((nelts), sizeof(type) * (nelts)))
  41
  42 /**
  43  * Create a flexible array and null its contents.
  44  */
  45 #define NEW_ARR_FZ(type, nelts) \
  46         ((type*)memset(NEW_ARR_F(type, (nelts)), 0, sizeof(type) * (nelts)))
  47
  48 /**
  49  * Creates a new flexible array with the same number of elements as a
  50  * given one.
  51  *
  52  * @param type     The element type of the new array.
  53  * @param arr      An array from which the number of elements will be taken
  54  *
  55  * This macro creates a flexible array of a given type at runtime.
  56  * The size of the array can be changed later.
  57  *
  58  * @return A pointer to the flexible array (can be used as a pointer to the
  59  *         first element of this array).
  60  */
  61 #define CLONE_ARR_F(type, arr) \
  62   NEW_ARR_F(type, ARR_LEN((arr)))
  63
  64 /**
  65  * Duplicates an array and returns the new flexible one.
  66  *
  67  * @param type     The element type of the new array.
  68  * @param arr      An array from which the elements will be duplicated
  69  *
  70  * This macro creates a flexible array of a given type at runtime.
  71  * The size of the array can be changed later.
  72  *
  73  * @return A pointer to the flexible array (can be used as a pointer to the
  74  *         first element of this array).
  75  */
  76 #define DUP_ARR_F(type, arr) \
  77   ((type*) memcpy(CLONE_ARR_F(type, (arr)), (arr), sizeof(type) * ARR_LEN((arr))))
  78
  79 /**
  80  * Delete a flexible array.
  81  *
  82  * @param arr    The flexible array.
  83  */
  84 #define DEL_ARR_F(arr) (ir_del_arr_f((void *)(arr)))
  85
  86 /**
  87  * Creates a dynamic array on an obstack.
  88  *
  89  * @param type     The element type of the new array.
  90  * @param obstack  A struct obstack * were the data will be allocated
  91  * @param nelts    A size_t expression evaluating to the number of elements
  92  *
  93  * This macro creates a dynamic array of a given type at runtime.
  94  * The size of the array cannot be changed later.
  95  *
  96  * @return A pointer to the dynamic array (can be used as a pointer to the
  97  *         first element of this array).
  98  */
  99 #define NEW_ARR_D(type, obstack, nelts)                                 \
 100   (  nelts                                                              \
 101    ? (type *)ir_new_arr_d((obstack), (nelts), sizeof(type) * (nelts))   \
 102    : (type *)arr_mt_descr.elts)
 103
 104 /**
 105  * Create a dynamic array on an obstack and null its contents.
 106  */
 107 #define NEW_ARR_DZ(type, obstack, nelts) \
 108         ((type*)memset(NEW_ARR_D(type, (obstack), (nelts)), 0, sizeof(type) * (nelts)))
 109
 110 /**
 111  * Creates a new dynamic array with the same number of elements as a
 112  * given one.
 113  *
 114  * @param type     The element type of the new array.
 115  * @param obstack  An struct obstack * were the data will be allocated
 116  * @param arr      An array from which the number of elements will be taken
 117  *
 118  * This macro creates a dynamic array of a given type at runtime.
 119  * The size of the array cannot be changed later.
 120  *
 121  * @return A pointer to the dynamic array (can be used as a pointer to the
 122  *         first element of this array).
 123  */
 124 #define CLONE_ARR_D(type, obstack, arr) \
 125   NEW_ARR_D(type, (obstack), ARR_LEN((arr)))
 126
 127 /**
 128  * Duplicates an array and returns the new dynamic one.
 129  *
 130  * @param type     The element type of the new array.
 131  * @param obstack  An struct obstack * were the data will be allocated
 132  * @param arr      An array from which the elements will be duplicated
 133  *
 134  * This macro creates a dynamic array of a given type at runtime.
 135  * The size of the array cannot be changed later.
 136  *
 137  * @return A pointer to the dynamic array (can be used as a pointer to the
 138  *         first element of this array).
 139  */
 140 #define DUP_ARR_D(type, obstack, arr) \
 141   ((type*)memcpy(CLONE_ARR_D(type, (obstack), (arr)), (arr), sizeof(type) * ARR_LEN ((arr))))
 142
 143 /**
 144  * Returns the length of an array
 145  *
 146  * @param arr  a flexible, dynamic, automatic or static array.
 147  */
 148 #define ARR_LEN(arr) (ARR_VRFY((arr)), ARR_DESCR((arr))->nelts)
 149
 150 /**
 151  * Resize a flexible array, allocate more data if needed but do NOT
 152  * reduce.
 153  *
 154  * @param type     The element type of the array.
 155  * @param arr      The array, which must be an lvalue.
 156  * @param n        The new size of the array.
 157  *
 158  * @remark  This macro may change arr, so update all references!
 159  */
 160 #define ARR_RESIZE(type, arr, n) \
 161   ((arr) = (type*) ir_arr_resize((void *)(arr), (n), sizeof(type)))
 162
 163 /**
 164  * Resize a flexible array, always reallocate data.
 165  *
 166  * @param type     The element type of the array.
 167  * @param arr      The array, which must be an lvalue.
 168  * @param n        The new size of the array.
 169  *
 170  * @remark  This macro may change arr, so update all references!
 171  */
 172 #define ARR_SETLEN(type, arr, n) \
 173   ((arr) = (type*) ir_arr_setlen((void *)(arr), (n), sizeof(type) * (n)))
 174
 175 /**
 176  * Resize a flexible array by growing it by delta elements.
 177  *
 178  * @param type     The element type of the array.
 179  * @param arr      The array, which must be an lvalue.
 180  * @param delta    The delta number of elements.
 181  *
 182  * @remark  This macro may change arr, so update all references!
 183  */
 184 #define ARR_EXTEND(type, arr, delta) \
 185   ARR_RESIZE(type, (arr), ARR_LEN((arr)) + (delta))
 186
 187 /**
 188  * Resize a flexible array to hold n elements only if it is currently shorter
 189  * than n.
 190  *
 191  * @param type     The element type of the array.
 192  * @param arr      The array, which must be an lvalue.
 193  * @param n        The new size of the array.
 194  *
 195  * @remark  This macro may change arr, so update all references!
 196  */
 197 #define ARR_EXTO(type, arr, n) \
 198         do { \
 199                 if ((n) >= ARR_LEN(arr)) { ARR_RESIZE(type, arr, (n)+1); } \
 200         } while(0)
 201
 202 /**
 203  * Append one element to a flexible array.
 204  *
 205  * @param type     The element type of the array.
 206  * @param arr      The array, which must be an lvalue.
 207  * @param elt      The new element, must be of type (type).
 208  */
 209 #define ARR_APP1(type, arr, elt) \
 210   (ARR_EXTEND(type, (arr), 1), (arr)[ARR_LEN((arr))-1] = (elt))
 211
 212 #ifdef NDEBUG
 213 # define ARR_VRFY(arr)          ((void)0)
 214 # define ARR_IDX_VRFY(arr, idx) ((void)0)
 215 #else
 216 /** Check array for consistency */
 217 # define ARR_VRFY(arr)          ir_verify_arr(arr)
 218 /** Check if index is within array bounds */
 219 # define ARR_IDX_VRFY(arr, idx) \
 220     assert((0 <= (idx)) && ((idx) < ARR_LEN((arr))))
 221 #endif
 222
 223 /** @cond PRIVATE */
 224
 225 /** A type that has most constrained alignment.  */
 226 typedef union {
 227   long double d;
 228   void *p;
 229   long l;
 230 } aligned_type;
 231
 232 /**
 233  * The array descriptor header type.
 234  */
 235 typedef struct {
 236         int magic;                    /**< array magic. */
 237         size_t allocated;         /**< number of allocated elements. */
 238         size_t nelts;                 /**< current length of the array. */
 239         aligned_type elts[1];         /**< start of the array data. */
 240 } ir_arr_descr;
 241
 242 extern ir_arr_descr arr_mt_descr;
 243
 244 FIRM_API void *ir_new_arr_f(size_t nelts, size_t elts_size);
 245 FIRM_API void ir_del_arr_f(void *elts);
 246 FIRM_API void *ir_new_arr_d(struct obstack *obstack, size_t nelts, size_t elts_size);
 247 FIRM_API void *ir_arr_resize(void *elts, size_t nelts, size_t elts_size);
 248 FIRM_API void *ir_arr_setlen(void *elts, size_t nelts, size_t elts_size);
 249 FIRM_API void ir_verify_arr(const void *elts);
 250
 251 #define ARR_ELTS_OFFS offsetof(ir_arr_descr, elts)
 252 #define ARR_DESCR(elts) ((ir_arr_descr *)(void *)((char *)(elts) - ARR_ELTS_OFFS))
 253
 254 /** Set a length smaller than the current length of the array.  Do not
 255  *  resize. len must be <= ARR_LEN(arr). */
 256 static inline void ARR_SHRINKLEN(void *arr, size_t new_len)
 257 {
 258         ARR_VRFY(arr);
 259         assert(ARR_DESCR(arr)->nelts >= new_len);
 260         ARR_DESCR(arr)->nelts = new_len;
 261 }
 262
 263 /** @endcond */
 264
 265 /** @} */
 266
 267 #include "../end.h"
 268
 269 #endif