1/* Vector API for GDB.
2   Copyright (C) 2004, 2005, 2006, 2007 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
23struct 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
34static inline unsigned
35calculate_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
79void *
80vec_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
90void *
91vec_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.  */
109DEF_VEC_I (int);
110typedef struct X
111{
112  int i;
113} obj_t;
114typedef obj_t *ptr_t;
115
116DEF_VEC_P (ptr_t);
117DEF_VEC_O (obj_t);
118#endif
119