/* Vector API for GNU compiler.
- Copyright (C) 2004-2013 Free Software Foundation, Inc.
+ Copyright (C) 2004-2017 Free Software Foundation, Inc.
Contributed by Nathan Sidwell <nathan@codesourcery.com>
Re-implemented in C++ by Diego Novillo <dnovillo@google.com>
#ifndef GCC_VEC_H
#define GCC_VEC_H
-/* FIXME - When compiling some of the gen* binaries, we cannot enable GC
- support because the headers generated by gengtype are still not
- present. In particular, the header file gtype-desc.h is missing,
- so compilation may fail if we try to include ggc.h.
-
- Since we use some of those declarations, we need to provide them
- (even if the GC-based templates are not used). This is not a
- problem because the code that runs before gengtype is built will
- never need to use GC vectors. But it does force us to declare
- these functions more than once. */
-#ifdef GENERATOR_FILE
-#define VEC_GC_ENABLED 0
-#else
-#define VEC_GC_ENABLED 1
-#endif // GENERATOR_FILE
-
-#include "statistics.h" // For CXX_MEM_STAT_INFO.
-
-#if VEC_GC_ENABLED
-#include "ggc.h"
-#else
-# ifndef GCC_GGC_H
- /* Even if we think that GC is not enabled, the test that sets it is
- weak. There are files compiled with -DGENERATOR_FILE that already
- include ggc.h. We only need to provide these definitions if ggc.h
- has not been included. Sigh. */
- extern void ggc_free (void *);
- extern size_t ggc_round_alloc_size (size_t requested_size);
- extern void *ggc_realloc_stat (void *, size_t MEM_STAT_DECL);
-# endif // GCC_GGC_H
-#endif // VEC_GC_ENABLED
+/* Some gen* file have no ggc support as the header file gtype-desc.h is
+ missing. Provide these definitions in case ggc.h has not been included.
+ This is not a problem because any code that runs before gengtype is built
+ will never need to use GC vectors.*/
+
+extern void ggc_free (void *);
+extern size_t ggc_round_alloc_size (size_t requested_size);
+extern void *ggc_realloc (void *, size_t MEM_STAT_DECL);
/* Templated vector type and associated interfaces.
/* Support function for statistics. */
extern void dump_vec_loc_statistics (void);
+/* Hashtable mapping vec addresses to descriptors. */
+extern htab_t vec_mem_usage_hash;
/* Control data for vectors. This contains the number of allocated
and used slots inside a vector. */
compilers that have stricter notions of PODness for types. */
/* Memory allocation support routines in vec.c. */
- void register_overhead (size_t, const char *, int, const char *);
- void release_overhead (void);
+ void register_overhead (void *, size_t, size_t CXX_MEM_STAT_INFO);
+ void release_overhead (void *, size_t, bool CXX_MEM_STAT_INFO);
static unsigned calculate_allocation (vec_prefix *, unsigned, bool);
+ static unsigned calculate_allocation_1 (unsigned, unsigned);
/* Note that vec_prefix should be a base class for vec, but we use
offsetof() on vector fields of tree structures (e.g.,
friend struct va_heap;
unsigned m_alloc : 31;
- unsigned m_has_auto_buf : 1;
+ unsigned m_using_auto_storage : 1;
unsigned m_num;
};
+/* Calculate the number of slots to reserve a vector, making sure that
+ RESERVE slots are free. If EXACT grow exactly, otherwise grow
+ exponentially. PFX is the control data for the vector. */
+
+inline unsigned
+vec_prefix::calculate_allocation (vec_prefix *pfx, unsigned reserve,
+ bool exact)
+{
+ if (exact)
+ return (pfx ? pfx->m_num : 0) + reserve;
+ else if (!pfx)
+ return MAX (4, reserve);
+ return calculate_allocation_1 (pfx->m_alloc, pfx->m_num + reserve);
+}
+
template<typename, typename, typename> struct vec;
/* Valid vector layouts
/* Allocator for heap memory. Ensure there are at least RESERVE free
slots in V. If EXACT is true, grow exactly, else grow
exponentially. As a special case, if the vector had not been
- allocated and and RESERVE is 0, no vector will be created. */
+ allocated and RESERVE is 0, no vector will be created. */
template<typename T>
inline void
{
unsigned alloc
= vec_prefix::calculate_allocation (v ? &v->m_vecpfx : 0, reserve, exact);
- gcc_assert (alloc);
+ gcc_checking_assert (alloc);
if (GATHER_STATISTICS && v)
- v->m_vecpfx.release_overhead ();
+ v->m_vecpfx.release_overhead (v, v->allocated (), false);
size_t size = vec<T, va_heap, vl_embed>::embedded_size (alloc);
unsigned nelem = v ? v->length () : 0;
v->embedded_init (alloc, nelem);
if (GATHER_STATISTICS)
- v->m_vecpfx.register_overhead (size FINAL_PASS_MEM_STAT);
+ v->m_vecpfx.register_overhead (v, alloc, nelem PASS_MEM_STAT);
}
return;
if (GATHER_STATISTICS)
- v->m_vecpfx.release_overhead ();
+ v->m_vecpfx.release_overhead (v, v->allocated (), true);
::free (v);
v = NULL;
}
/* Allocator for GC memory. Ensure there are at least RESERVE free
slots in V. If EXACT is true, grow exactly, else grow
exponentially. As a special case, if the vector had not been
- allocated and and RESERVE is 0, no vector will be created. */
+ allocated and RESERVE is 0, no vector will be created. */
template<typename T, typename A>
void
size = vec_offset + alloc * elt_size;
unsigned nelem = v ? v->length () : 0;
- v = static_cast <vec<T, A, vl_embed> *> (::ggc_realloc_stat (v, size
+ v = static_cast <vec<T, A, vl_embed> *> (::ggc_realloc (v, size
PASS_MEM_STAT));
v->embedded_init (alloc, nelem);
}
{
};
+/* Default-construct N elements in DST. */
+
+template <typename T>
+inline void
+vec_default_construct (T *dst, unsigned n)
+{
+ for ( ; n; ++dst, --n)
+ ::new (static_cast<void*>(dst)) T ();
+}
+
+/* Copy-construct N elements in DST from *SRC. */
+
+template <typename T>
+inline void
+vec_copy_construct (T *dst, const T *src, unsigned n)
+{
+ for ( ; n; ++dst, ++src, --n)
+ ::new (static_cast<void*>(dst)) T (*src);
+}
+
/* Type to provide NULL values for vec<T, A, L>. This is used to
provide nil initializers for vec instances. Since vec must be
a POD, we cannot have proper ctor/dtor for it. To initialize
- a vec instance, you can assign it the value vNULL. */
+ a vec instance, you can assign it the value vNULL. This isn't
+ needed for file-scope and function-local static vectors, which
+ are zero-initialized by default. */
struct vnull
{
template <typename T, typename A, typename L>
- operator vec<T, A, L> () { return vec<T, A, L>(); }
+ CONSTEXPR operator vec<T, A, L> () { return vec<T, A, L>(); }
};
extern vnull vNULL;
bool is_empty (void) const { return m_vecpfx.m_num == 0; }
T *address (void) { return m_vecdata; }
const T *address (void) const { return m_vecdata; }
+ T *begin () { return address (); }
+ const T *begin () const { return address (); }
+ T *end () { return address () + length (); }
+ const T *end () const { return address () + length (); }
const T &operator[] (unsigned) const;
T &operator[] (unsigned);
T &last (void);
bool iterate (unsigned, T *) const;
bool iterate (unsigned, T **) const;
vec *copy (ALONE_CXX_MEM_STAT_INFO) const;
- void splice (vec &);
- void splice (vec *src);
+ void splice (const vec &);
+ void splice (const vec *src);
T *quick_push (const T &);
T &pop (void);
void truncate (unsigned);
void unordered_remove (unsigned);
void block_remove (unsigned, unsigned);
void qsort (int (*) (const void *, const void *));
+ T *bsearch (const void *key, int (*compar)(const void *, const void *));
unsigned lower_bound (T, bool (*)(const T &, const T &)) const;
+ bool contains (const T &search) const;
static size_t embedded_size (unsigned);
- void embedded_init (unsigned, unsigned = 0);
+ void embedded_init (unsigned, unsigned = 0, unsigned = 0);
void quick_grow (unsigned len);
void quick_grow_cleared (unsigned len);
return v ? v->is_empty () : true;
}
-
/* If V does not have space for NELEMS elements, call
V->reserve(NELEMS, EXACT). */
template<typename T, typename A>
{
unsigned oldlen = vec_safe_length (v);
vec_safe_grow (v, len PASS_MEM_STAT);
- memset (&(v->address ()[oldlen]), 0, sizeof (T) * (len - oldlen));
+ vec_default_construct (v->address () + oldlen, len - oldlen);
}
/* If SRC is not NULL, return a pointer to a copy of it. */
template<typename T, typename A>
inline vec<T, A, vl_embed> *
-vec_safe_copy (vec<T, A, vl_embed> *src)
+vec_safe_copy (vec<T, A, vl_embed> *src CXX_MEM_STAT_INFO)
{
- return src ? src->copy () : NULL;
+ return src ? src->copy (ALONE_PASS_MEM_STAT) : NULL;
}
/* Copy the elements from SRC to the end of DST as if by memcpy.
Reallocate DST, if necessary. */
template<typename T, typename A>
inline void
-vec_safe_splice (vec<T, A, vl_embed> *&dst, vec<T, A, vl_embed> *src
+vec_safe_splice (vec<T, A, vl_embed> *&dst, const vec<T, A, vl_embed> *src
CXX_MEM_STAT_INFO)
{
unsigned src_len = vec_safe_length (src);
}
}
+/* Return true if SEARCH is an element of V. Note that this is O(N) in the
+ size of the vector and so should be used with care. */
+
+template<typename T, typename A>
+inline bool
+vec_safe_contains (vec<T, A, vl_embed> *v, const T &search)
+{
+ return v ? v->contains (search) : false;
+}
/* Index into vector. Return the IX'th element. IX must be in the
domain of the vector. */
{
vec_alloc (new_vec, len PASS_MEM_STAT);
new_vec->embedded_init (len, len);
- memcpy (new_vec->address (), m_vecdata, sizeof (T) * len);
+ vec_copy_construct (new_vec->address (), m_vecdata, len);
}
return new_vec;
}
template<typename T, typename A>
inline void
-vec<T, A, vl_embed>::splice (vec<T, A, vl_embed> &src)
+vec<T, A, vl_embed>::splice (const vec<T, A, vl_embed> &src)
{
unsigned len = src.length ();
if (len)
{
gcc_checking_assert (space (len));
- memcpy (address () + length (), src.address (), len * sizeof (T));
+ vec_copy_construct (end (), src.address (), len);
m_vecpfx.m_num += len;
}
}
template<typename T, typename A>
inline void
-vec<T, A, vl_embed>::splice (vec<T, A, vl_embed> *src)
+vec<T, A, vl_embed>::splice (const vec<T, A, vl_embed> *src)
{
if (src)
splice (*src);
inline void
vec<T, A, vl_embed>::qsort (int (*cmp) (const void *, const void *))
{
- ::qsort (address (), length (), sizeof (T), cmp);
+ if (length () > 1)
+ ::qsort (address (), length (), sizeof (T), cmp);
}
+/* Search the contents of the sorted vector with a binary search.
+ CMP is the comparison function to pass to bsearch. */
+
+template<typename T, typename A>
+inline T *
+vec<T, A, vl_embed>::bsearch (const void *key,
+ int (*compar) (const void *, const void *))
+{
+ const void *base = this->address ();
+ size_t nmemb = this->length ();
+ size_t size = sizeof (T);
+ /* The following is a copy of glibc stdlib-bsearch.h. */
+ size_t l, u, idx;
+ const void *p;
+ int comparison;
+
+ l = 0;
+ u = nmemb;
+ while (l < u)
+ {
+ idx = (l + u) / 2;
+ p = (const void *) (((const char *) base) + (idx * size));
+ comparison = (*compar) (key, p);
+ if (comparison < 0)
+ u = idx;
+ else if (comparison > 0)
+ l = idx + 1;
+ else
+ return (T *)const_cast<void *>(p);
+ }
+
+ return NULL;
+}
+
+/* Return true if SEARCH is an element of V. Note that this is O(N) in the
+ size of the vector and so should be used with care. */
+
+template<typename T, typename A>
+inline bool
+vec<T, A, vl_embed>::contains (const T &search) const
+{
+ unsigned int len = length ();
+ for (unsigned int i = 0; i < len; i++)
+ if ((*this)[i] == search)
+ return true;
+
+ return false;
+}
+
/* Find and return the first position in which OBJ could be inserted
without changing the ordering of this vector. LESSTHAN is a
function that returns true if the first argument is strictly less
template<typename T, typename A>
inline void
-vec<T, A, vl_embed>::embedded_init (unsigned alloc, unsigned num)
+vec<T, A, vl_embed>::embedded_init (unsigned alloc, unsigned num, unsigned aut)
{
m_vecpfx.m_alloc = alloc;
- m_vecpfx.m_has_auto_buf = 0;
+ m_vecpfx.m_using_auto_storage = aut;
m_vecpfx.m_num = num;
}
vec<T, A, vl_embed>::quick_grow_cleared (unsigned len)
{
unsigned oldlen = length ();
+ size_t growby = len - oldlen;
quick_grow (len);
- memset (&(address ()[oldlen]), 0, sizeof (T) * (len - oldlen));
+ if (growby != 0)
+ vec_default_construct (address () + oldlen, growby);
}
-
/* Garbage collection support for vec<T, A, vl_embed>. */
template<typename T>
const T *address (void) const
{ return m_vec ? m_vec->m_vecdata : NULL; }
+ T *begin () { return address (); }
+ const T *begin () const { return address (); }
+ T *end () { return begin () + length (); }
+ const T *end () const { return begin () + length (); }
const T &operator[] (unsigned ix) const
{ return (*m_vec)[ix]; }
vec copy (ALONE_CXX_MEM_STAT_INFO) const;
bool reserve (unsigned, bool = false CXX_MEM_STAT_INFO);
bool reserve_exact (unsigned CXX_MEM_STAT_INFO);
- void splice (vec &);
- void safe_splice (vec & CXX_MEM_STAT_INFO);
+ void splice (const vec &);
+ void safe_splice (const vec & CXX_MEM_STAT_INFO);
T *quick_push (const T &);
T *safe_push (const T &CXX_MEM_STAT_INFO);
T &pop (void);
void unordered_remove (unsigned);
void block_remove (unsigned, unsigned);
void qsort (int (*) (const void *, const void *));
+ T *bsearch (const void *key, int (*compar)(const void *, const void *));
unsigned lower_bound (T, bool (*)(const T &, const T &)) const;
+ bool contains (const T &search) const;
bool using_auto_storage () const;
public:
auto_vec ()
{
- m_header.m_alloc = N;
- m_header.m_has_auto_buf = 1;
- m_header.m_num = 0;
- this->m_vec = reinterpret_cast<vec<T, va_heap, vl_embed> *> (&m_header);
+ m_auto.embedded_init (MAX (N, 2), 0, 1);
+ this->m_vec = &m_auto;
+ }
+
+ auto_vec (size_t s)
+ {
+ if (s > N)
+ {
+ this->create (s);
+ return;
+ }
+
+ m_auto.embedded_init (MAX (N, 2), 0, 1);
+ this->m_vec = &m_auto;
}
~auto_vec ()
}
private:
- friend class vec<T, va_heap, vl_ptr>;
-
- vec_prefix m_header;
- T m_data[N];
+ vec<T, va_heap, vl_embed> m_auto;
+ T m_data[MAX (N - 1, 1)];
};
/* auto_vec is a sub class of vec whose storage is released when it is
inline bool
vec<T, va_heap, vl_ptr>::reserve (unsigned nelems, bool exact MEM_STAT_DECL)
{
- if (!nelems || space (nelems))
+ if (space (nelems))
return false;
/* For now play a game with va_heap::reserve to hide our auto storage if any,
va_heap::reserve (m_vec, nelems, exact PASS_MEM_STAT);
if (handle_auto_vec)
{
- memcpy (m_vec->address (), oldvec->address (), sizeof (T) * oldsize);
+ vec_copy_construct (m_vec->address (), oldvec->address (), oldsize);
m_vec->m_vecpfx.m_num = oldsize;
}
if (using_auto_storage ())
{
- static_cast<auto_vec<T, 1> *> (this)->m_header.m_num = 0;
+ m_vec->m_vecpfx.m_num = 0;
return;
}
template<typename T>
inline void
-vec<T, va_heap, vl_ptr>::splice (vec<T, va_heap, vl_ptr> &src)
+vec<T, va_heap, vl_ptr>::splice (const vec<T, va_heap, vl_ptr> &src)
{
if (src.m_vec)
m_vec->splice (*(src.m_vec));
template<typename T>
inline void
-vec<T, va_heap, vl_ptr>::safe_splice (vec<T, va_heap, vl_ptr> &src
+vec<T, va_heap, vl_ptr>::safe_splice (const vec<T, va_heap, vl_ptr> &src
MEM_STAT_DECL)
{
if (src.length ())
unsigned oldlen = length ();
gcc_checking_assert (oldlen <= len);
reserve_exact (len - oldlen PASS_MEM_STAT);
- m_vec->quick_grow (len);
+ if (m_vec)
+ m_vec->quick_grow (len);
+ else
+ gcc_checking_assert (len == 0);
}
vec<T, va_heap, vl_ptr>::safe_grow_cleared (unsigned len MEM_STAT_DECL)
{
unsigned oldlen = length ();
+ size_t growby = len - oldlen;
safe_grow (len PASS_MEM_STAT);
- memset (&(address ()[oldlen]), 0, sizeof (T) * (len - oldlen));
+ if (growby != 0)
+ vec_default_construct (address () + oldlen, growby);
}
}
+/* Search the contents of the sorted vector with a binary search.
+ CMP is the comparison function to pass to bsearch. */
+
+template<typename T>
+inline T *
+vec<T, va_heap, vl_ptr>::bsearch (const void *key,
+ int (*cmp) (const void *, const void *))
+{
+ if (m_vec)
+ return m_vec->bsearch (key, cmp);
+ return NULL;
+}
+
+
/* Find and return the first position in which OBJ could be inserted
without changing the ordering of this vector. LESSTHAN is a
function that returns true if the first argument is strictly less
return m_vec ? m_vec->lower_bound (obj, lessthan) : 0;
}
+/* Return true if SEARCH is an element of V. Note that this is O(N) in the
+ size of the vector and so should be used with care. */
+
+template<typename T>
+inline bool
+vec<T, va_heap, vl_ptr>::contains (const T &search) const
+{
+ return m_vec ? m_vec->contains (search) : false;
+}
+
template<typename T>
inline bool
vec<T, va_heap, vl_ptr>::using_auto_storage () const
{
- if (!m_vec->m_vecpfx.m_has_auto_buf)
- return false;
+ return m_vec->m_vecpfx.m_using_auto_storage;
+}
+
+/* Release VEC and call release of all element vectors. */
+
+template<typename T>
+inline void
+release_vec_vec (vec<vec<T> > &vec)
+{
+ for (unsigned i = 0; i < vec.length (); i++)
+ vec[i].release ();
- const vec_prefix *auto_header
- = &static_cast<const auto_vec<T, 1> *> (this)->m_header;
- return reinterpret_cast<vec_prefix *> (m_vec) == auto_header;
+ vec.release ();
}
#if (GCC_VERSION >= 3000)
projects / gcc.git / blobdiff