gdb/common/vec.c

   1 /* Vector API for GDB.
   2    Copyright (C) 2004-2014 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 #ifdef GDBSERVER
  21 #include "server.h"
  22 #else
  23 #include "defs.h"
  24 #endif
  25
  26 #include "vec.h"
  27
  28 struct vec_prefix
  29 {
  30   unsigned num;
  31   unsigned alloc;
  32   void *vec[1];
  33 };
  34
  35 /* Calculate the new ALLOC value, making sure that abs(RESERVE) slots
  36    are free.  If RESERVE < 0 grow exactly, otherwise grow
  37    exponentially.  */
  38
  39 static inline unsigned
  40 calculate_allocation (const struct vec_prefix *pfx, int reserve)
  41 {
  42   unsigned alloc = 0;
  43   unsigned num = 0;
  44
  45   if (pfx)
  46     {
  47       alloc = pfx->alloc;
  48       num = pfx->num;
  49     }
  50   else if (!reserve)
  51     /* If there's no prefix, and we've not requested anything, then we
  52        will create a NULL vector.  */
  53     return 0;
  54
  55   /* We must have run out of room.  */
  56   gdb_assert (alloc - num < (unsigned)(reserve < 0 ? -reserve : reserve));
  57
  58   if (reserve < 0)
  59     /* Exact size.  */
  60     alloc = num + -reserve;
  61   else
  62     {
  63       /* Exponential growth.  */
  64       if (!alloc)
  65         alloc = 4;
  66       else if (alloc < 16)
  67         /* Double when small.  */
  68         alloc = alloc * 2;
  69       else
  70         /* Grow slower when large.  */
  71         alloc = (alloc * 3 / 2);
  72
  73       /* If this is still too small, set it to the right size.  */
  74       if (alloc < num + reserve)
  75         alloc = num + reserve;
  76     }
  77   return alloc;
  78 }
  79
  80 /* Ensure there are at least abs(RESERVE) free slots in VEC.  If
  81    RESERVE < 0 grow exactly, else grow exponentially.  As a special
  82    case, if VEC is NULL, and RESERVE is 0, no vector will be created.  */
  83
  84 void *
  85 vec_p_reserve (void *vec, int reserve)
  86 {
  87   return vec_o_reserve (vec, reserve,
  88                         offsetof (struct vec_prefix, vec), sizeof (void *));
  89 }
  90
  91 /* As vec_p_reserve, but for object vectors.  The vector's trailing
  92    array is at VEC_OFFSET offset and consists of ELT_SIZE sized
  93    elements.  */
  94
  95 void *
  96 vec_o_reserve (void *vec, int reserve, size_t vec_offset, size_t elt_size)
  97 {
  98   struct vec_prefix *pfx = vec;
  99   unsigned alloc = calculate_allocation (pfx, reserve);
 100
 101   if (!alloc)
 102     return NULL;
 103
 104   vec = xrealloc (vec, vec_offset + alloc * elt_size);
 105   ((struct vec_prefix *)vec)->alloc = alloc;
 106   if (!pfx)
 107     ((struct vec_prefix *)vec)->num = 0;
 108
 109   return vec;
 110 }
 111
 112 #if 0
 113 /* Example uses.  */
 114 DEF_VEC_I (int);
 115 typedef struct X
 116 {
 117   int i;
 118 } obj_t;
 119 typedef obj_t *ptr_t;
 120
 121 DEF_VEC_P (ptr_t);
 122 DEF_VEC_O (obj_t);
 123 #endif