gdb/vec.c

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