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

   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       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 descriptor.
  53  */
  54 _arr_descr arr_mt_descr
  55 #ifndef NDEBUG
  56         = { ARR_D_MAGIC, 0, {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 *_new_arr_d(struct obstack *obstack, int nelts, size_t elts_size) {
  73         _arr_descr *dp;
  74
  75         assert(obstack && (nelts >= 0));
  76
  77         dp = obstack_alloc(obstack, _ARR_ELTS_OFFS + elts_size);
  78         _ARR_SET_DBGINF(dp, ARR_D_MAGIC, elts_size/nelts);
  79         dp->u.obstack = obstack;
  80         dp->nelts = nelts;
  81         return dp->v.elts;
  82 }
  83
  84 /**
  85  * Creates a flexible array.
  86  *
  87  * @param nelts      The number of elements
  88  * @param elts_size  The size of the array elements.
  89  *
  90  * @return A pointer to the flexible array (can be used as a pointer to the
  91  *         first element of this array).
  92  *
  93  * @remark Helper function, use NEW_ARR_F() instead.
  94  */
  95 void *_new_arr_f(int nelts, size_t elts_size) {
  96         _arr_descr *new;
  97
  98         assert (nelts >= 0);
  99         new = xmalloc (_ARR_ELTS_OFFS+elts_size);
 100         _ARR_SET_DBGINF (new, ARR_F_MAGIC, nelts ? elts_size/nelts : 0);
 101         new->u.allocated = new->nelts = nelts;
 102         return new->v.elts;
 103 }
 104
 105 /**
 106  * Delete a flexible array.
 107  *
 108  * @param elts    The flexible array (pointer to the first element).
 109  *
 110  * @remark Helper function, use DEL_ARR_F() instead.
 111  */
 112 void _del_arr_f(void *elts) {
 113         _arr_descr *dp = _ARR_DESCR (elts);
 114
 115         ARR_VRFY (elts);
 116         assert (dp->magic == ARR_F_MAGIC);
 117
 118 #ifndef NDEBUG
 119         {
 120                 _arr_descr *wdp = (_arr_descr *)dp;
 121                 wdp->magic = 0xdeadbeef;
 122         }
 123 #endif
 124         free(dp);
 125 }
 126
 127 /**
 128  * Resize a flexible array, always reallocate data.
 129  *
 130  * @param elts       The flexible array (pointer to the first element).
 131  * @param nelts      The new number of elements.
 132  * @param elts_size  The size of the array elements.
 133  *
 134  * @return A resized flexible array, possibly other address than
 135  *         elts.
 136  *
 137  * @remark Helper function, use ARR_SETLEN() instead.
 138  */
 139 void *_arr_setlen (void *elts, int nelts, size_t elts_size) {
 140         _arr_descr *dp = _ARR_DESCR (elts);
 141
 142         assert ((dp->magic == ARR_F_MAGIC) && (nelts >= 0));
 143         ARR_VRFY (elts);
 144         assert (!dp->eltsize || !nelts || (dp->eltsize == elts_size/nelts));
 145
 146         dp = xrealloc (dp, _ARR_ELTS_OFFS+elts_size);
 147         dp->u.allocated = dp->nelts = nelts;
 148
 149         return dp->v.elts;
 150 }
 151
 152 /**
 153  * Resize a flexible array, allocate more data if needed but do NOT
 154  * reduce.
 155  *
 156  * @param elts     The flexible array (pointer to the first element).
 157  * @param nelts    The new number of elements.
 158  * @param eltsize  The size of the array elements.
 159  *
 160  * @return A resized flexible array, possibly other address than
 161  *         elts.
 162  *
 163  * @remark Helper function, use ARR_RESIZE() instead.
 164  */
 165 void *_arr_resize(void *elts, int nelts, size_t eltsize) {
 166         _arr_descr *dp = _ARR_DESCR(elts);
 167         int n;
 168
 169         assert((dp->magic == ARR_F_MAGIC) && (nelts >= 0));
 170         ARR_VRFY(elts);
 171         assert(dp->eltsize ? dp->eltsize == eltsize : (dp->eltsize = eltsize, 1));
 172
 173         /* @@@ lots of resizes for small nelts */
 174         n = MAX(1, dp->u.allocated);
 175         while (nelts > n) n <<= 1;
 176         while (3*nelts < n) n >>= 1;
 177         assert(n >= nelts);
 178
 179         if (n != dp->u.allocated) {
 180                 dp = xrealloc(dp, _ARR_ELTS_OFFS+eltsize*n);
 181                 dp->u.allocated = n;
 182 #if defined(DEBUG) && defined(HAVE_GNU_MALLOC)
 183         } else {
 184                 tmalloc_tag = NULL;
 185 #endif
 186         }
 187         dp->nelts = nelts;
 188
 189         return dp->v.elts;
 190 }
 191
 192 #ifdef DEBUG_libfirm
 193 /**
 194  * This function returns the length of a flexible array.
 195  * Do NOT use is in code, use ARR_LEN() macro!
 196  * This function is intended to be called from a debugger.
 197  */
 198 int array_len(const void *arr) {
 199         return ARR_LEN(arr);
 200 }
 201
 202 /**
 203  * This function returns the array descriptor of a flexible array.
 204  * Do NOT use is in code!.
 205  * This function is intended to be called from a debugger.
 206  */
 207 _arr_descr *array_descr(const void *arr) {
 208         if (! arr)
 209                 return NULL;
 210         return _ARR_DESCR(arr);
 211 }
 212 #endif /* DEBUG_libfirm */