gdb/vec.c

   1 /* Vector API for GDB.
   2    Copyright (C) 2004, 2005, 2006, 2007, 2008 Free Software Foundation, Inc.
   3    Contributed by Nathan Sidwell <nathan@codesourcery.com>
   4
   5    This file is part of GDB.
   6
   7    This program is free software; you can redistribute it and/or modify
   8    it under the terms of the GNU General Public License as published by
   9    the Free Software Foundation; either version 3 of the License, or
  10    (at your option) any later version.
  11
  12    This program is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
  19
  20 #include "defs.h"
  21 #include "vec.h"
  22
  23 struct vec_prefix
  24 {
  25   unsigned num;
  26   unsigned alloc;
  27   void *vec[1];
  28 };
  29
  30 /* Calculate the new ALLOC value, making sure that abs(RESERVE) slots
  31    are free.  If RESERVE < 0 grow exactly, otherwise grow
  32    exponentially.  */
  33
  34 static inline unsigned
  35 calculate_allocation (const struct vec_prefix *pfx, int reserve)
  36 {
  37   unsigned alloc = 0;
  38   unsigned num = 0;
  39
  40   if (pfx)
  41     {
  42       alloc = pfx->alloc;
  43       num = pfx->num;
  44     }
  45   else if (!reserve)
  46     /* If there's no prefix, and we've not requested anything, then we
  47        will create a NULL vector.  */
  48     return 0;
  49
  50   /* We must have run out of room.  */
  51   gdb_assert (alloc - num < (unsigned)(reserve < 0 ? -reserve : reserve));
  52
  53   if (reserve < 0)
  54     /* Exact size.  */
  55     alloc = num + -reserve;
  56   else
  57     {
  58       /* Exponential growth. */
  59       if (!alloc)
  60         alloc = 4;
  61       else if (alloc < 16)
  62         /* Double when small.  */
  63         alloc = alloc * 2;
  64       else
  65         /* Grow slower when large.  */
  66         alloc = (alloc * 3 / 2);
  67
  68       /* If this is still too small, set it to the right size. */
  69       if (alloc < num + reserve)
  70         alloc = num + reserve;
  71     }
  72   return alloc;
  73 }
  74
  75 /* Ensure there are at least abs(RESERVE) free slots in VEC.  If
  76    RESERVE < 0 grow exactly, else grow exponentially.  As a special
  77    case, if VEC is NULL, and RESERVE is 0, no vector will be created. */
  78
  79 void *
  80 vec_p_reserve (void *vec, int reserve)
  81 {
  82   return vec_o_reserve (vec, reserve,
  83                         offsetof (struct vec_prefix, vec), sizeof (void *));
  84 }
  85
  86 /* As vec_p_reserve, but for object vectors.  The vector's trailing
  87    array is at VEC_OFFSET offset and consists of ELT_SIZE sized
  88    elements.  */
  89
  90 void *
  91 vec_o_reserve (void *vec, int reserve, size_t vec_offset, size_t elt_size)
  92 {
  93   struct vec_prefix *pfx = vec;
  94   unsigned alloc = calculate_allocation (pfx, reserve);
  95
  96   if (!alloc)
  97     return NULL;
  98
  99   vec = xrealloc (vec, vec_offset + alloc * elt_size);
 100   ((struct vec_prefix *)vec)->alloc = alloc;
 101   if (!pfx)
 102     ((struct vec_prefix *)vec)->num = 0;
 103
 104   return vec;
 105 }
 106
 107 #if 0
 108 /* Example uses.  */
 109 DEF_VEC_I (int);
 110 typedef struct X
 111 {
 112   int i;
 113 } obj_t;
 114 typedef obj_t *ptr_t;
 115
 116 DEF_VEC_P (ptr_t);
 117 DEF_VEC_O (obj_t);
 118 #endif