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