nsz Git - libfirm/blob - ir/adt/array.c

   1 /*
   2  * Copyright (C) 1995-2007 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       Array --- dynamic & flexible arrays.
  23  * @author      Markus Armbruster
  24  * @version     $Id$
  25  */
  26
  27 #ifdef HAVE_CONFIG_H
  28 # include "config.h"
  29 #endif
  30
  31 #ifdef HAVE_STDLIB_H
  32 # include <stdlib.h>
  33 #endif
  34
  35 #include "array.h"
  36 #include "xmalloc.h"
  37
  38 /* Undefine the macros to get the functions instead, cf tmalloc.c.  */
  39 #undef xmalloc
  40 #undef xrealloc
  41 #undef xstrdup
  42 #undef xfree
  43
  44 #ifndef MAX
  45 # define MAX(a,b) ((a) > (b) ? (a) : (b))
  46 #endif
  47 #ifndef MIN
  48 # define MIN(a,b) ((a) > (b) ? (b) : (a))
  49 #endif
  50
  51 /**
  52  * An empty dynamic array
  53  */
  54 _arr_descr arr_mt_descr
  55 #ifndef NDEBUG
  56   = { ARR_D_MAGIC, 0, {0}, 0, {{}} }
  57 #endif
  58 ;
  59
  60 /**
  61  * Creates a dynamic array on a obstack.
  62  *
  63  * @param obstack    An struct obstack * were the data will be allocated
  64  * @param nelts      The number of elements
  65  * @param elts_size  The size of the array elements.
  66  *
  67  * @return A pointer to the dynamic array (can be used as a pointer to the
  68  *         first element of this array).
  69  *
  70  * @remark Helper function, use NEW_ARR_D() instead.
  71  */
  72 void *
  73 _new_arr_d (struct obstack *obstack, int nelts, size_t elts_size)
  74 {
  75   _arr_descr *new;
  76
  77   assert (obstack && (nelts >= 0));
  78
  79   new = obstack_alloc (obstack, _ARR_ELTS_OFFS+elts_size);
  80   _ARR_SET_DBGINF (new, ARR_D_MAGIC, elts_size/nelts);
  81   new->u.obstack = obstack;
  82   new->nelts = nelts;
  83   return new->v.elts;
  84 }
  85
  86 /**
  87  * Creates a flexible array.
  88  *
  89  * @param nelts      The number of elements
  90  * @param elts_size  The size of the array elements.
  91  *
  92  * @return A pointer to the flexible array (can be used as a pointer to the
  93  *         first element of this array).
  94  *
  95  * @remark Helper function, use NEW_ARR_F() instead.
  96  */
  97 void *
  98 _new_arr_f (int nelts, size_t elts_size)
  99 {
 100   _arr_descr *new;
 101
 102   assert (nelts >= 0);
 103   new = xmalloc (_ARR_ELTS_OFFS+elts_size);
 104   _ARR_SET_DBGINF (new, ARR_F_MAGIC, nelts ? elts_size/nelts : 0);
 105   new->u.allocated = new->nelts = nelts;
 106   return new->v.elts;
 107 }
 108
 109 /**
 110  * Delete a flexible array.
 111  *
 112  * @param elts    The flexible array (pointer to the first element).
 113  *
 114  * @remark Helper function, use DEL_ARR_F() instead.
 115  */
 116 void
 117 _del_arr_f (void *elts)
 118 {
 119   _arr_descr *dp = _ARR_DESCR (elts);
 120
 121   ARR_VRFY (elts);
 122   assert (dp->magic == ARR_F_MAGIC);
 123
 124 #ifndef NDEBUG
 125   dp->magic = 0xdeadbeef;
 126 #endif
 127   free (dp);
 128 }
 129
 130 /**
 131  * Resize a flexible array, always reallocate data.
 132  *
 133  * @param elts       The flexible array (pointer to the first element).
 134  * @param nelts      The new number of elements.
 135  * @param elts_size  The size of the array elements.
 136  *
 137  * @return A resized flexible array, possibly other address than
 138  *         elts.
 139  *
 140  * @remark Helper function, use ARR_SETLEN() instead.
 141  */
 142 void *
 143 _arr_setlen (void *elts, int nelts, size_t elts_size)
 144 {
 145   _arr_descr *dp = _ARR_DESCR (elts);
 146
 147   assert ((dp->magic == ARR_F_MAGIC) && (nelts >= 0));
 148   ARR_VRFY (elts);
 149   assert (!dp->eltsize || !nelts || (dp->eltsize == elts_size/nelts));
 150
 151   dp = xrealloc (dp, _ARR_ELTS_OFFS+elts_size);
 152   dp->u.allocated = dp->nelts = nelts;
 153
 154   return dp->v.elts;
 155 }
 156
 157 /**
 158  * Resize a flexible array, allocate more data if needed but do NOT
 159  * reduce.
 160  *
 161  * @param elts     The flexible array (pointer to the first element).
 162  * @param nelts    The new number of elements.
 163  * @param eltsize  The size of the array elements.
 164  *
 165  * @return A resized flexible array, possibly other address than
 166  *         elts.
 167  *
 168  * @remark Helper function, use ARR_RESIZE() instead.
 169  */
 170 void *
 171 _arr_resize (void *elts, int nelts, size_t eltsize)
 172 {
 173   _arr_descr *dp = _ARR_DESCR (elts);
 174   int n;
 175
 176   assert ((dp->magic == ARR_F_MAGIC) && (nelts >= 0));
 177   ARR_VRFY (elts);
 178   assert (dp->eltsize ? dp->eltsize == eltsize : (dp->eltsize = eltsize, 1));
 179
 180   /* @@@ lots of resizes for small nelts */
 181   n = MAX (1, dp->u.allocated);
 182   while (nelts > n) n <<= 1;
 183   while (3*nelts < n) n >>= 1;
 184   assert (n >= nelts);
 185
 186   if (n != dp->u.allocated) {
 187     dp = xrealloc (dp, _ARR_ELTS_OFFS+eltsize*n);
 188     dp->u.allocated = n;
 189 #if defined(DEBUG) && defined(HAVE_GNU_MALLOC)
 190   } else {
 191     tmalloc_tag = NULL;
 192 #endif
 193   }
 194   dp->nelts = nelts;
 195
 196   return dp->v.elts;
 197 }
 198
 199 #ifdef DEBUG_libfirm
 200 /**
 201  * This function returns the length of a flexible array.
 202  * Do NOT use is in code, use ARR_LEN() macro!
 203  * This function is intended to be called from a debugger.
 204  */
 205 int array_len(void *arr) {
 206   return ARR_LEN(arr);
 207 }
 208
 209 /**
 210  * This function returns the array descriptor of a flexible array.
 211  * Do NOT use is in code!.
 212  * This function is intended to be called from a debugger.
 213  */
 214 _arr_descr *array_descr(void *arr) {
 215   if (! arr)
 216     return NULL;
 217   return _ARR_DESCR(arr);
 218 }
 219 #endif /* DEBUG_libfirm */