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

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