nsz Git - cparser/blob - adt/array.h

   1 /*
   2  * This file is part of cparser.
   3  * Copyright (C) 2007-2008 Matthias Braun <matze@braunis.de>
   4  *
   5  * This program is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU General Public License
   7  * as published by the Free Software Foundation; either version 2
   8  * of the License, or (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program; if not, write to the Free Software
  17  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  18  * 02111-1307, USA.
  19  */
  20
  21 /*
  22  * Project:     libFIRM
  23  * File name:   ir/adt/array.h
  24  * Purpose:     Declarations for Array.
  25  * Author:      Markus Armbruster
  26  * Modified by:
  27  * Created:     1999 by getting from fiasco
  28  * CVS-ID:      $Id$
  29  * Copyright:   (c) 1995, 1996 Markus Armbruster
  30  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  31  */
  32
  33 /**
  34  * @file array.h   Dynamic and flexible arrays for C.
  35  */
  36
  37 #ifndef _ARRAY_H
  38 #define _ARRAY_H
  39
  40 #include <assert.h>
  41 #include <stddef.h>
  42
  43 #include "fourcc.h"
  44 #include "align.h"
  45 #include "obst.h"
  46 #include "xmalloc.h"
  47
  48 #define ARR_D_MAGIC     FOURCC('A','R','R','D')
  49 #define ARR_A_MAGIC     FOURCC('A','R','R','A')
  50 #define ARR_F_MAGIC     FOURCC('A','R','R','F')
  51
  52 /**
  53  * Creates a flexible array.
  54  *
  55  * @param type     The element type of the new array.
  56  * @param nelts    a size_t expression evaluating to the number of elements
  57  *
  58  * This macro creates a flexible array of a given type at runtime.
  59  * The size of the array can be changed later.
  60  *
  61  * @return A pointer to the flexible array (can be used as a pointer to the
  62  *         first element of this array).
  63  */
  64 #define NEW_ARR_F(type, nelts)                                          \
  65   ((type *)_new_arr_f ((nelts), sizeof(type) * (nelts)))
  66
  67 /**
  68  * Creates a new flxible array with the same number of elements as a
  69  * given one.
  70  *
  71  * @param type     The element type of the new array.
  72  * @param arr      An array from which the number of elements will be taken
  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 #ifdef __GNUC__
  81 #define CLONE_ARR_F(type, arr)                  \
  82   NEW_ARR_F (__typeof__(arr[0]), ARR_LEN ((arr)))
  83 #else
  84 #define CLONE_ARR_F(type, arr)                  \
  85         NEW_ARR_F (type, ARR_LEN ((arr)))
  86 #endif
  87
  88 /**
  89  * Duplicates an array and returns the new flexible one.
  90  *
  91  * @param type     The element type of the new array.
  92  * @param arr      An array from which the elements will be duplicated
  93  *
  94  * This macro creates a flexible array of a given type at runtime.
  95  * The size of the array can be changed later.
  96  *
  97  * @return A pointer to the flexible array (can be used as a pointer to the
  98  *         first element of this array).
  99  */
 100 #ifdef __GNUC__
 101 #define DUP_ARR_F(type, arr)                                                    \
 102   memcpy (CLONE_ARR_F (__typeof__(arr[0]), (arr)), (arr), sizeof(__typeof__(arr[0])) * ARR_LEN((arr)))
 103 #else
 104 #define DUP_ARR_F(type, arr)                                                    \
 105         memcpy (CLONE_ARR_F (type, (arr)), (arr), sizeof(type) * ARR_LEN((arr)))
 106 #endif
 107
 108 /**
 109  * Delete a flexible array.
 110  *
 111  * @param arr    The flexible array.
 112  */
 113 #define DEL_ARR_F(arr) (_del_arr_f ((arr)))
 114
 115 /**
 116  * Creates a dynamic array on an obstack.
 117  *
 118  * @param type     The element type of the new array.
 119  * @param obstack  A struct obstack * were the data will be allocated
 120  * @param nelts    A size_t expression evaluating to the number of elements
 121  *
 122  * This macro creates a dynamic array of a given type at runtime.
 123  * The size of the array cannot be changed later.
 124  *
 125  * @return A pointer to the dynamic array (can be used as a pointer to the
 126  *         first element of this array).
 127  */
 128 #define NEW_ARR_D(type, obstack, nelts)                                 \
 129   (  nelts                                                              \
 130    ? (type *)_new_arr_d((obstack), (nelts), sizeof(type) * (nelts))     \
 131    : (type *)arr_mt_descr.v.elts)
 132
 133 /**
 134  * Creates a new dynamic array with the same number of elements as a
 135  * given one.
 136  *
 137  * @param type     The element type of the new array.
 138  * @param obstack  An struct obstack * were the data will be allocated
 139  * @param arr      An array from which the number of elements will be taken
 140  *
 141  * This macro creates a dynamic array of a given type at runtime.
 142  * The size of the array cannot be changed later.
 143  *
 144  * @return A pointer to the dynamic array (can be used as a pointer to the
 145  *         first element of this array).
 146  */
 147 #ifdef __GNUC__
 148 #define CLONE_ARR_D(type, obstack, arr)         \
 149   NEW_ARR_D(__typeof__(arr[0]), (obstack), ARR_LEN((arr)))
 150 #else
 151 #define CLONE_ARR_D(type, obstack, arr)         \
 152         NEW_ARR_D(type, (obstack), ARR_LEN((arr)))
 153 #endif
 154
 155 /**
 156  * Duplicates an array and returns the new dynamic one.
 157  *
 158  * @param type     The element type of the new array.
 159  * @param obstack  An struct obstack * were the data will be allocated
 160  * @param arr      An array from which the elements will be duplicated
 161  *
 162  * This macro creates a dynamic array of a given type at runtime.
 163  * The size of the array cannot be changed later.
 164  *
 165  * @return A pointer to the dynamic array (can be used as a pointer to the
 166  *         first element of this array).
 167  */
 168 #ifdef __GNUC__
 169 #define DUP_ARR_D(type, obstack, arr)                                                   \
 170   memcpy(CLONE_ARR_D(__typeof__(arr[0]), (obstack), (arr)), (arr), sizeof(__typeof__(arr[0])) * ARR_LEN((arr)))
 171 #else
 172 #define DUP_ARR_D(type, obstack, arr)                                                   \
 173         memcpy(CLONE_ARR_D(type, (obstack), (arr)), (arr), sizeof(type) * ARR_LEN((arr)))
 174 #endif
 175
 176 /**
 177  * Create an automatic array which will be deleted at return from function.
 178  * Beware, the data will be allocated on the function stack!
 179  *
 180  * @param type     The element type of the new array.
 181  * @param var      A lvalue of type (type *) which will hold the new array.
 182  * @param n        number of elements in this array.
 183  *
 184  * This macro creates a dynamic array on the functions stack of a given type at runtime.
 185  * The size of the array cannot be changed later.
 186  */
 187 #define NEW_ARR_A(type, var, n)                                                                 \
 188   do {                                                                                          \
 189     int _nelts = (n);                                                                           \
 190     assert (_nelts >= 0);                                                                       \
 191     (var) = (void *)((_arr_descr *)alloca (_ARR_ELTS_OFFS + sizeof(type) * _nelts))->v.elts;    \
 192     _ARR_SET_DBGINF (_ARR_DESCR ((var)), ARR_A_MAGIC, sizeof (type));                           \
 193     (void)(_ARR_DESCR ((var))->nelts = _nelts);                                                 \
 194   } while (0)
 195
 196 /**
 197  * Creates a new automatic array with the same number of elements as a
 198  * given one.
 199  *
 200  * @param type     The element type of the array.
 201  * @param var      A lvalue of type (type *) which will hold the new array.
 202  * @param arr      An array from which the elements will be duplicated
 203  *
 204  * This macro creates a dynamic array of a given type at runtime.
 205  * The size of the array cannot be changed later.
 206  *
 207  * @return A pointer to the dynamic array (can be used as a pointer to the
 208  *         first element of this array).
 209  */
 210 #ifdef __GNUC__
 211 #define CLONE_ARR_A(type, var, arr)             \
 212   NEW_ARR_A(__typeof__(arr[0]), (var), ARR_LEN((arr)))
 213 #else
 214 #define CLONE_ARR_A(type, var, arr)             \
 215         NEW_ARR_A(type, (var), ARR_LEN((arr)))
 216 #endif
 217
 218 /**
 219  * Duplicates an array and returns a new automatic one.
 220  *
 221  * @param type     The element type of the new array.
 222  * @param var      A lvalue of type (type *) which will hold the new array.
 223  * @param arr      An array from with the number of elements will be taken
 224  *
 225  * This macro creates a dynamic array of a given type at runtime.
 226  * The size of the array cannot be changed later.
 227  *
 228  * @return A pointer to the dynamic array (can be used as a pointer to the
 229  *         first element of this array).
 230  */
 231 #ifdef __GNUC__
 232 #define DUP_ARR_A(type, var, arr)                                       \
 233   do { CLONE_ARR_A(__typeof__(arr[0]), (var), (arr));                                   \
 234        memcpy((var), (arr), sizeof(__typeof__(arr[0])) * ARR_LEN((arr))); }     \
 235   while (0)
 236 #else
 237 #define DUP_ARR_A(type, var, arr)                                       \
 238   do { CLONE_ARR_A(type, (var), (arr));                                 \
 239     memcpy((var), (arr), sizeof(type) * ARR_LEN((arr))); }      \
 240   while (0)
 241 #endif
 242
 243 /**
 244  * Declare an initialized (zero'ed) array of fixed size.
 245  * This macro should be used at file scope only.
 246  *
 247  * @param type     The element type of the new array.
 248  * @param var      A lvalue of type (type *) which will hold the new array.
 249  * @param _nelts   Number of elements in this new array.
 250  */
 251 #define DECL_ARR_S(type, var, _nelts)                                   \
 252   ARR_STRUCT(type, (_nelts) ? (_nelts) : 1) _##var;                     \
 253   type *var = (_ARR_SET_DBGINF (&_##var, ARR_A_MAGIC, sizeof (type)),   \
 254                _##var.nelts = _nelts,                                   \
 255                _##var.v.elts)
 256
 257 /**
 258  * Returns the length of an array
 259  *
 260  * @param arr  a flexible, dynamic, automatic or static array.
 261  */
 262 #define ARR_LEN(arr) (ARR_VRFY ((arr)), _ARR_DESCR((arr))->nelts)
 263
 264 /**
 265  * Resize a flexible array, allocate more data if needed but do NOT
 266  * reduce.
 267  *
 268  * @param type     The element type of the array.
 269  * @param arr      The array, which must be an lvalue.
 270  * @param n        The new size of the array.
 271  *
 272  * @remark  This macro may change arr, so update all references!
 273  */
 274 #ifdef __GNUC__
 275 #define ARR_RESIZE(type, arr, n)                                        \
 276   ((arr) = _arr_resize((arr), (n), sizeof(__typeof__(arr[0]))))
 277 #else
 278 #define ARR_RESIZE(type, arr, n)                                        \
 279         ((arr) = _arr_resize((arr), (n), sizeof(type)))
 280 #endif
 281
 282 /**
 283  * Resize a flexible array, always reallocate data.
 284  *
 285  * @param type     The element type of the array.
 286  * @param arr      The array, which must be an lvalue.
 287  * @param n        The new size of the array.
 288  *
 289  * @remark  This macro may change arr, so update all references!
 290  */
 291 #ifdef __GNUC__
 292 #define ARR_SETLEN(type, arr, n)                                        \
 293   ((arr) = _arr_setlen ((arr), (n), sizeof(__typeof__(arr[0])) * (n)))
 294 #else
 295 #define ARR_SETLEN(type, arr, n)                                        \
 296   ((arr) = _arr_setlen ((arr), (n), sizeof(type) * (n)))
 297 #endif
 298
 299 /** Set a length smaller than the current length of the array.  Do not
 300  *  resize. len must be <= ARR_LEN(arr). */
 301 #define ARR_SHRINKLEN(arr,len)                                          \
 302    (ARR_VRFY ((arr)), assert(_ARR_DESCR((arr))->nelts >= len),             \
 303     _ARR_DESCR((arr))->nelts = len)
 304
 305 /**
 306  * Resize a flexible array by growing it by delta elements.
 307  *
 308  * @param type     The element type of the array.
 309  * @param arr      The array, which must be an lvalue.
 310  * @param delta    The delta number of elements.
 311  *
 312  * @remark  This macro may change arr, so update all references!
 313  */
 314 #define ARR_EXTEND(type, arr, delta)                    \
 315   ARR_RESIZE(type, (arr), ARR_LEN((arr)) + (delta))
 316
 317 /**
 318  * Resize a flexible array to hold n elements only if it is currently shorter
 319  * than n.
 320  *
 321  * @param type     The element type of the array.
 322  * @param arr      The array, which must be an lvalue.
 323  * @param n        The new size of the array.
 324  *
 325  * @remark  This macro may change arr, so update all references!
 326  */
 327 #define ARR_EXTO(type, arr, n)                                          \
 328   ((n) >= ARR_LEN((arr)) ? ARR_RESIZE(type, (arr), (n)+1) : (arr))
 329
 330 /**
 331  * Append one element to a flexible array.
 332  *
 333  * @param type     The element type of the array.
 334  * @param arr      The array, which must be an lvalue.
 335  * @param elt      The new element, must be of type (type).
 336  */
 337 #define ARR_APP1(type, arr, elt)                                        \
 338   (ARR_EXTEND(type, (arr), 1), (arr)[ARR_LEN((arr))-1] = (elt))
 339
 340
 341 #ifdef NDEBUG
 342 # define ARR_VRFY(arr) ((void)0)
 343 # define ARR_IDX_VRFY(arr, idx) ((void)0)
 344 #else
 345 # define ARR_VRFY(arr)                                                                  \
 346     assert (   (   (_ARR_DESCR((arr))->magic == ARR_D_MAGIC)                            \
 347                 || (_ARR_DESCR((arr))->magic == ARR_A_MAGIC)                            \
 348                 || (_ARR_DESCR((arr))->magic == ARR_F_MAGIC))                           \
 349             && (   (_ARR_DESCR((arr))->magic != ARR_F_MAGIC)                            \
 350                 || (_ARR_DESCR((arr))->u.allocated >= _ARR_DESCR((arr))->nelts))        \
 351             && (_ARR_DESCR((arr))->nelts >= 0))
 352 # define ARR_IDX_VRFY(arr, idx)                         \
 353     assert ((0 <= (idx)) && ((idx) < ARR_LEN ((arr))))
 354 #endif
 355
 356
 357 /* Private !!!
 358    Don't try this at home, kids, we're trained professionals ;->
 359    ... or at the IPD, either. */
 360 #ifdef NDEBUG
 361 # define _ARR_DBGINF_DECL
 362 # define _ARR_SET_DBGINF(descr, co, es)
 363 #else
 364 # define _ARR_DBGINF_DECL int magic; size_t eltsize;
 365 # define _ARR_SET_DBGINF(descr, co, es)                                 \
 366     ( (descr)->magic = (co), (descr)->eltsize = (es) )
 367 #endif
 368
 369 /**
 370  * Construct an array header.
 371  */
 372 #define ARR_STRUCT(type, _nelts)                                                \
 373   struct {                                                                      \
 374     _ARR_DBGINF_DECL                                                            \
 375     union {                                                                     \
 376       struct obstack *obstack;  /* dynamic: allocated on this obstack */        \
 377       int allocated;                    /* flexible: #slots allocated */        \
 378     } u;                                                                        \
 379     int nelts;                                                                  \
 380     union {                                                                     \
 381       type elts[(_nelts)];                                                      \
 382       aligned_type align[1];                                                    \
 383     } v;                                                                        \
 384   }
 385
 386 /**
 387  * The array descriptor header type.
 388  */
 389 typedef ARR_STRUCT (aligned_type, 1) _arr_descr;
 390
 391 extern _arr_descr arr_mt_descr;
 392
 393 void *_new_arr_f (int, size_t);
 394 void _del_arr_f (void *);
 395 void *_new_arr_d (struct obstack *obstack, int nelts, size_t elts_size);
 396 void *_arr_resize (void *, int, size_t);
 397 void *_arr_setlen (void *, int, size_t);
 398
 399 #define _ARR_ELTS_OFFS offsetof (_arr_descr, v.elts)
 400 #define _ARR_DESCR(elts) ((_arr_descr *)(void *)((char *)(elts) - _ARR_ELTS_OFFS))
 401
 402 #endif