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

   1 /*
   2  * Copyright (C) 1995-2008 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  * @version   $Id$
  25  */
  26 #ifndef FIRM_ADT_ARRAY_H
  27 #define FIRM_ADT_ARRAY_H
  28
  29 #include <assert.h>
  30 #include <stddef.h>
  31
  32 #include "obst.h"
  33 #include "fourcc.h"
  34 #include "align.h"
  35 #include "xmalloc.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   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.v.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   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) = 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) = ir_arr_setlen((void *)(arr), (n), sizeof(type) * (n)))
 172
 173 /** Set a length smaller than the current length of the array.  Do not
 174  *  resize. len must be <= ARR_LEN(arr). */
 175 #define ARR_SHRINKLEN(arr,len)                                          \
 176    (ARR_VRFY((arr)), assert(ARR_DESCR((arr))->nelts >= len),             \
 177     ARR_DESCR((arr))->nelts = len)
 178
 179 /**
 180  * Resize a flexible array by growing it by delta elements.
 181  *
 182  * @param type     The element type of the array.
 183  * @param arr      The array, which must be an lvalue.
 184  * @param delta    The delta number of elements.
 185  *
 186  * @remark  This macro may change arr, so update all references!
 187  */
 188 #define ARR_EXTEND(type, arr, delta)                    \
 189   ARR_RESIZE(type, (arr), ARR_LEN((arr)) + (delta))
 190
 191 /**
 192  * Resize a flexible array to hold n elements only if it is currently shorter
 193  * than n.
 194  *
 195  * @param type     The element type of the array.
 196  * @param arr      The array, which must be an lvalue.
 197  * @param n        The new size of the array.
 198  *
 199  * @remark  This macro may change arr, so update all references!
 200  */
 201 #define ARR_EXTO(type, arr, n)                                          \
 202   ((n) >= ARR_LEN((arr)) ? ARR_RESIZE(type, (arr), (n)+1) : (arr))
 203
 204 /**
 205  * Append one element to a flexible array.
 206  *
 207  * @param type     The element type of the array.
 208  * @param arr      The array, which must be an lvalue.
 209  * @param elt      The new element, must be of type (type).
 210  */
 211 #define ARR_APP1(type, arr, elt)                                        \
 212   (ARR_EXTEND(type, (arr), 1), (arr)[ARR_LEN((arr))-1] = (elt))
 213
 214 #ifdef NDEBUG
 215 # define ARR_VRFY(arr)          ((void)0)
 216 # define ARR_IDX_VRFY(arr, idx) ((void)0)
 217 #else
 218 # define ARR_VRFY(arr)          ir_verify_arr(arr)
 219 # define ARR_IDX_VRFY(arr, idx)                         \
 220     assert((0 <= (idx)) && ((idx) < ARR_LEN((arr))))
 221 #endif
 222
 223
 224 /**
 225  * Construct an array header.
 226  */
 227 #define ARR_STRUCT(type, rnelts)                    \
 228   struct {                                          \
 229         int magic;                                      \
 230         size_t eltsize;                                 \
 231     union {                                         \
 232       struct obstack *obstack;  /* dynamic: allocated on this obstack */  \
 233       int allocated;                    /* flexible: #slots allocated */          \
 234     } u;                                            \
 235     int nelts;                                      \
 236     union {                                         \
 237       type elts[(rnelts)];                          \
 238       aligned_type align[1];                        \
 239     } v;                                            \
 240   }
 241
 242 /**
 243  * The array descriptor header type.
 244  */
 245 typedef ARR_STRUCT(aligned_type, 1) ir_arr_descr;
 246
 247 extern ir_arr_descr arr_mt_descr;
 248
 249 void *ir_new_arr_f(int nelts, size_t elts_size);
 250 void ir_del_arr_f(void *elts);
 251 void *ir_new_arr_d(struct obstack *obstack, int nelts, size_t elts_size);
 252 void *ir_arr_resize(void *elts, int nelts, size_t elts_size);
 253 void *ir_arr_setlen(void *elts, int nelts, size_t elts_size);
 254 void ir_verify_arr(const void *elts);
 255
 256 #define ARR_ELTS_OFFS offsetof(ir_arr_descr, v.elts)
 257 #define ARR_DESCR(elts) ((ir_arr_descr *)(void *)((char *)(elts) - ARR_ELTS_OFFS))
 258
 259 /*
 260  ____             _           _      _
 261 / ___|  ___  _ __| |_ ___  __| |    / \   _ __ _ __ __ _ _   _ ___
 262 \___ \ / _ \| '__| __/ _ \/ _` |   / _ \ | '__| '__/ _` | | | / __|
 263  ___) | (_) | |  | ||  __/ (_| |  / ___ \| |  | | | (_| | |_| \__ \
 264 |____/ \___/|_|   \__\___|\__,_| /_/   \_\_|  |_|  \__,_|\__, |___/
 265                                                          |___/
 266 */
 267
 268 typedef int (ir_arr_cmp_func_t)(const void *a, const void *b);
 269
 270 /**
 271  * Do a binary search in an array.
 272  * @param arr      The array.
 273  * @param elm_size The size of an array element.
 274  * @param cmp      A comparison function for two array elements (see qsort(3) for example).
 275  * @param elm      A pointer to the element we are looking for.
 276  * @return         This is somewhat tricky. Let <code>res</code> be the return value.
 277  *                 If the return value is negative, then <code>elm</code> was not in the array
 278  *                 but <code>-res - 1</code> gives the proper location where it should be inserted.
 279  *                 If <code>res >= 0</code> then the element is in the array and <code>res</code>
 280  *                 represents its index.
 281  *                 That allows for testing membership and finding proper insertion indices.
 282  * @note           The differences to bsearch(3) which does not give proper insert locations
 283  *                 in the case that the element is not conatined in the array.
 284  */
 285 static inline int ir_arr_bsearch(const void *arr, size_t elm_size, ir_arr_cmp_func_t *cmp, const void *elm)
 286 {
 287         int hi = ARR_LEN(arr);
 288         int lo = 0;
 289
 290         while(lo < hi) {
 291                 int md     = lo + ((hi - lo) >> 1);
 292                 int res    = cmp((char *) arr + md * elm_size, elm);
 293                 if(res < 0)
 294                         lo = md + 1;
 295                 else if(res > 0)
 296                         hi = md;
 297                 else
 298                         return md;
 299         }
 300
 301         return -(lo + 1);
 302 }
 303
 304 #define ARR_SET_INSERT(arr, cmp, elm) \
 305 do { \
 306         int idx = ir_arr_bsearch((arr), sizeof((arr)[0]), (cmp), (elm)); \
 307         if (idx < 0) { \
 308                 idx = -idx - 1; \
 309                 memmove(&(arr)[idx+1], &(arr)[idx], sizeof((arr)[0]) * (ARR_DESCR((arr))->nelts - idx)); \
 310                 (arr)[idx] = *(elm); \
 311                 ++ARR_DESCR((arr))->nelts; \
 312         } \
 313 } while(0)
 314
 315 #define ARR_SET_INSERT_EXT(type, arr, cmp, elm) \
 316 do { \
 317         int idx = ir_arr_bsearch((arr), sizeof((arr)[0]), (cmp), (elm)); \
 318         if (idx < 0) { \
 319                 int len = ARR_LEN(arr); \
 320                 idx = -idx - 1; \
 321                 ARR_EXTO(type, arr, len + 1); \
 322                 memmove(&(arr)[idx+1], &(arr)[idx], sizeof((arr)[0]) * (len - idx)); \
 323                 (arr)[idx] = *(elm); \
 324         } \
 325 } while(0)
 326
 327 #define ARR_SET_REMOVE(arr, cmp, elm) \
 328 do { \
 329         int idx = ir_arr_bsearch((arr), sizeof((arr)[0]), (cmp), (elm)); \
 330         if (idx >= 0) { \
 331                 --ARR_DESCR((arr))->nelts; \
 332                 memmove(&(arr)[idx], &(arr)[idx+1], sizeof((arr)[0]) * (ARR_DESCR((arr))->nelts - idx)); \
 333         } \
 334 } while(0)
 335
 336 /**
 337  * Return the index of an element in an array set.
 338  * To check for containment, use the expression:
 339  *     (ARR_SET_GET_IDX(arr, cmp, elm) >= 0)
 340  *
 341  * @return The index or some value < 0 if the element was not in the set.
 342  */
 343 #define ARR_SET_GET_IDX(arr, cmp, elm) \
 344         (ARR_VRFY((arr)), ir_arr_bsearch((arr), sizeof((arr)[0]), cmp, (elm)))
 345
 346 #ifdef __GNUC__
 347 #define ARR_SET_GET(arr, cmp, elm) \
 348         ({ int idx = ARR_SET_GET_IDX(arr, cmp, elm); idx >= 0 ? &(arr)[idx] : NULL; })
 349 #else
 350 #define ARR_SET_GET(arr, cmp, elm) \
 351         (ARR_SET_GET_IDX(arr, cmp, elm) >= 0 ? &(arr)[ARR_SET_GET_IDX(arr, cmp, elm)] : NULL)
 352 #endif
 353
 354
 355 #define ARR_SET_CONTAINS(arr, cmp, elm) \
 356         (ARR_SET_GET_IDX((arr), (cmp), (elm)) >= 0)
 357
 358 /**
 359  * Reset the array set.
 360  * This just initializes the size to zero but does not wipe out any element.
 361  */
 362 #define ARR_SET_CLEAR(arr) ARR_SHRINKLEN(arr, 0)
 363
 364 #endif /* FIRM_ADT_ARRAY_H */