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

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