/* Vector API for GNU compiler. | |

Copyright (C) 2004-2018 Free Software Foundation, Inc. | |

Contributed by Nathan Sidwell <nathan@codesourcery.com> | |

Re-implemented in C++ by Diego Novillo <dnovillo@google.com> | |

This file is part of GCC. | |

GCC is free software; you can redistribute it and/or modify it under | |

the terms of the GNU General Public License as published by the Free | |

Software Foundation; either version 3, or (at your option) any later | |

version. | |

GCC is distributed in the hope that it will be useful, but WITHOUT ANY | |

WARRANTY; without even the implied warranty of MERCHANTABILITY or | |

FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |

for more details. | |

You should have received a copy of the GNU General Public License | |

along with GCC; see the file COPYING3. If not see | |

<http://www.gnu.org/licenses/>. */ | |

#ifndef GCC_VEC_H | |

#define GCC_VEC_H | |

/* 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. | |

The interface functions are typesafe and use inline functions, | |

sometimes backed by out-of-line generic functions. The vectors are | |

designed to interoperate with the GTY machinery. | |

There are both 'index' and 'iterate' accessors. The index accessor | |

is implemented by operator[]. The iterator returns a boolean | |

iteration condition and updates the iteration variable passed by | |

reference. Because the iterator will be inlined, the address-of | |

can be optimized away. | |

Each operation that increases the number of active elements is | |

available in 'quick' and 'safe' variants. The former presumes that | |

there is sufficient allocated space for the operation to succeed | |

(it dies if there is not). The latter will reallocate the | |

vector, if needed. Reallocation causes an exponential increase in | |

vector size. If you know you will be adding N elements, it would | |

be more efficient to use the reserve operation before adding the | |

elements with the 'quick' operation. This will ensure there are at | |

least as many elements as you ask for, it will exponentially | |

increase if there are too few spare slots. If you want reserve a | |

specific number of slots, but do not want the exponential increase | |

(for instance, you know this is the last allocation), use the | |

reserve_exact operation. You can also create a vector of a | |

specific size from the get go. | |

You should prefer the push and pop operations, as they append and | |

remove from the end of the vector. If you need to remove several | |

items in one go, use the truncate operation. The insert and remove | |

operations allow you to change elements in the middle of the | |

vector. There are two remove operations, one which preserves the | |

element ordering 'ordered_remove', and one which does not | |

'unordered_remove'. The latter function copies the end element | |

into the removed slot, rather than invoke a memmove operation. The | |

'lower_bound' function will determine where to place an item in the | |

array using insert that will maintain sorted order. | |

Vectors are template types with three arguments: the type of the | |

elements in the vector, the allocation strategy, and the physical | |

layout to use | |

Four allocation strategies are supported: | |

- Heap: allocation is done using malloc/free. This is the | |

default allocation strategy. | |

- GC: allocation is done using ggc_alloc/ggc_free. | |

- GC atomic: same as GC with the exception that the elements | |

themselves are assumed to be of an atomic type that does | |

not need to be garbage collected. This means that marking | |

routines do not need to traverse the array marking the | |

individual elements. This increases the performance of | |

GC activities. | |

Two physical layouts are supported: | |

- Embedded: The vector is structured using the trailing array | |

idiom. The last member of the structure is an array of size | |

1. When the vector is initially allocated, a single memory | |

block is created to hold the vector's control data and the | |

array of elements. These vectors cannot grow without | |

reallocation (see discussion on embeddable vectors below). | |

- Space efficient: The vector is structured as a pointer to an | |

embedded vector. This is the default layout. It means that | |

vectors occupy a single word of storage before initial | |

allocation. Vectors are allowed to grow (the internal | |

pointer is reallocated but the main vector instance does not | |

need to relocate). | |

The type, allocation and layout are specified when the vector is | |

declared. | |

If you need to directly manipulate a vector, then the 'address' | |

accessor will return the address of the start of the vector. Also | |

the 'space' predicate will tell you whether there is spare capacity | |

in the vector. You will not normally need to use these two functions. | |

Notes on the different layout strategies | |

* Embeddable vectors (vec<T, A, vl_embed>) | |

These vectors are suitable to be embedded in other data | |

structures so that they can be pre-allocated in a contiguous | |

memory block. | |

Embeddable vectors are implemented using the trailing array | |

idiom, thus they are not resizeable without changing the address | |

of the vector object itself. This means you cannot have | |

variables or fields of embeddable vector type -- always use a | |

pointer to a vector. The one exception is the final field of a | |

structure, which could be a vector type. | |

You will have to use the embedded_size & embedded_init calls to | |

create such objects, and they will not be resizeable (so the | |

'safe' allocation variants are not available). | |

Properties of embeddable vectors: | |

- The whole vector and control data are allocated in a single | |

contiguous block. It uses the trailing-vector idiom, so | |

allocation must reserve enough space for all the elements | |

in the vector plus its control data. | |

- The vector cannot be re-allocated. | |

- The vector cannot grow nor shrink. | |

- No indirections needed for access/manipulation. | |

- It requires 2 words of storage (prior to vector allocation). | |

* Space efficient vector (vec<T, A, vl_ptr>) | |

These vectors can grow dynamically and are allocated together | |

with their control data. They are suited to be included in data | |

structures. Prior to initial allocation, they only take a single | |

word of storage. | |

These vectors are implemented as a pointer to embeddable vectors. | |

The semantics allow for this pointer to be NULL to represent | |

empty vectors. This way, empty vectors occupy minimal space in | |

the structure containing them. | |

Properties: | |

- The whole vector and control data are allocated in a single | |

contiguous block. | |

- The whole vector may be re-allocated. | |

- Vector data may grow and shrink. | |

- Access and manipulation requires a pointer test and | |

indirection. | |

- It requires 1 word of storage (prior to vector allocation). | |

An example of their use would be, | |

struct my_struct { | |

// A space-efficient vector of tree pointers in GC memory. | |

vec<tree, va_gc, vl_ptr> v; | |

}; | |

struct my_struct *s; | |

if (s->v.length ()) { we have some contents } | |

s->v.safe_push (decl); // append some decl onto the end | |

for (ix = 0; s->v.iterate (ix, &elt); ix++) | |

{ do something with elt } | |

*/ | |

/* 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. */ | |

struct vec_prefix | |

{ | |

/* FIXME - These fields should be private, but we need to cater to | |

compilers that have stricter notions of PODness for types. */ | |

/* Memory allocation support routines in vec.c. */ | |

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., | |

tree_binfo::base_binfos), and offsetof only supports base types. | |

To compensate, we make vec_prefix a field inside vec and make | |

vec a friend class of vec_prefix so it can access its fields. */ | |

template <typename, typename, typename> friend struct vec; | |

/* The allocator types also need access to our internals. */ | |

friend struct va_gc; | |

friend struct va_gc_atomic; | |

friend struct va_heap; | |

unsigned m_alloc : 31; | |

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 | |

vl_embed - Embeddable vector that uses the trailing array idiom. | |

vl_ptr - Space efficient vector that uses a pointer to an | |

embeddable vector. */ | |

struct vl_embed { }; | |

struct vl_ptr { }; | |

/* Types of supported allocations | |

va_heap - Allocation uses malloc/free. | |

va_gc - Allocation uses ggc_alloc. | |

va_gc_atomic - Same as GC, but individual elements of the array | |

do not need to be marked during collection. */ | |

/* Allocator type for heap vectors. */ | |

struct va_heap | |

{ | |

/* Heap vectors are frequently regular instances, so use the vl_ptr | |

layout for them. */ | |

typedef vl_ptr default_layout; | |

template<typename T> | |

static void reserve (vec<T, va_heap, vl_embed> *&, unsigned, bool | |

CXX_MEM_STAT_INFO); | |

template<typename T> | |

static void release (vec<T, va_heap, vl_embed> *&); | |

}; | |

/* 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 RESERVE is 0, no vector will be created. */ | |

template<typename T> | |

inline void | |

va_heap::reserve (vec<T, va_heap, vl_embed> *&v, unsigned reserve, bool exact | |

MEM_STAT_DECL) | |

{ | |

unsigned alloc | |

= vec_prefix::calculate_allocation (v ? &v->m_vecpfx : 0, reserve, exact); | |

gcc_checking_assert (alloc); | |

if (GATHER_STATISTICS && v) | |

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 = static_cast <vec<T, va_heap, vl_embed> *> (xrealloc (v, size)); | |

v->embedded_init (alloc, nelem); | |

if (GATHER_STATISTICS) | |

v->m_vecpfx.register_overhead (v, alloc, nelem PASS_MEM_STAT); | |

} | |

/* Free the heap space allocated for vector V. */ | |

template<typename T> | |

void | |

va_heap::release (vec<T, va_heap, vl_embed> *&v) | |

{ | |

if (v == NULL) | |

return; | |

if (GATHER_STATISTICS) | |

v->m_vecpfx.release_overhead (v, v->allocated (), true); | |

::free (v); | |

v = NULL; | |

} | |

/* Allocator type for GC vectors. Notice that we need the structure | |

declaration even if GC is not enabled. */ | |

struct va_gc | |

{ | |

/* Use vl_embed as the default layout for GC vectors. Due to GTY | |

limitations, GC vectors must always be pointers, so it is more | |

efficient to use a pointer to the vl_embed layout, rather than | |

using a pointer to a pointer as would be the case with vl_ptr. */ | |

typedef vl_embed default_layout; | |

template<typename T, typename A> | |

static void reserve (vec<T, A, vl_embed> *&, unsigned, bool | |

CXX_MEM_STAT_INFO); | |

template<typename T, typename A> | |

static void release (vec<T, A, vl_embed> *&v); | |

}; | |

/* Free GC memory used by V and reset V to NULL. */ | |

template<typename T, typename A> | |

inline void | |

va_gc::release (vec<T, A, vl_embed> *&v) | |

{ | |

if (v) | |

::ggc_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 RESERVE is 0, no vector will be created. */ | |

template<typename T, typename A> | |

void | |

va_gc::reserve (vec<T, A, vl_embed> *&v, unsigned reserve, bool exact | |

MEM_STAT_DECL) | |

{ | |

unsigned alloc | |

= vec_prefix::calculate_allocation (v ? &v->m_vecpfx : 0, reserve, exact); | |

if (!alloc) | |

{ | |

::ggc_free (v); | |

v = NULL; | |

return; | |

} | |

/* Calculate the amount of space we want. */ | |

size_t size = vec<T, A, vl_embed>::embedded_size (alloc); | |

/* Ask the allocator how much space it will really give us. */ | |

size = ::ggc_round_alloc_size (size); | |

/* Adjust the number of slots accordingly. */ | |

size_t vec_offset = sizeof (vec_prefix); | |

size_t elt_size = sizeof (T); | |

alloc = (size - vec_offset) / elt_size; | |

/* And finally, recalculate the amount of space we ask for. */ | |

size = vec_offset + alloc * elt_size; | |

unsigned nelem = v ? v->length () : 0; | |

v = static_cast <vec<T, A, vl_embed> *> (::ggc_realloc (v, size | |

PASS_MEM_STAT)); | |

v->embedded_init (alloc, nelem); | |

} | |

/* Allocator type for GC vectors. This is for vectors of types | |

atomics w.r.t. collection, so allocation and deallocation is | |

completely inherited from va_gc. */ | |

struct va_gc_atomic : va_gc | |

{ | |

}; | |

/* Generic vector template. Default values for A and L indicate the | |

most commonly used strategies. | |

FIXME - Ideally, they would all be vl_ptr to encourage using regular | |

instances for vectors, but the existing GTY machinery is limited | |

in that it can only deal with GC objects that are pointers | |

themselves. | |

This means that vector operations that need to deal with | |

potentially NULL pointers, must be provided as free | |

functions (see the vec_safe_* functions above). */ | |

template<typename T, | |

typename A = va_heap, | |

typename L = typename A::default_layout> | |

struct GTY((user)) vec | |

{ | |

}; | |

/* Generic vec<> debug helpers. | |

These need to be instantiated for each vec<TYPE> used throughout | |

the compiler like this: | |

DEFINE_DEBUG_VEC (TYPE) | |

The reason we have a debug_helper() is because GDB can't | |

disambiguate a plain call to debug(some_vec), and it must be called | |

like debug<TYPE>(some_vec). */ | |

template<typename T> | |

void | |

debug_helper (vec<T> &ref) | |

{ | |

unsigned i; | |

for (i = 0; i < ref.length (); ++i) | |

{ | |

fprintf (stderr, "[%d] = ", i); | |

debug_slim (ref[i]); | |

fputc ('\n', stderr); | |

} | |

} | |

/* We need a separate va_gc variant here because default template | |

argument for functions cannot be used in c++-98. Once this | |

restriction is removed, those variant should be folded with the | |

above debug_helper. */ | |

template<typename T> | |

void | |

debug_helper (vec<T, va_gc> &ref) | |

{ | |

unsigned i; | |

for (i = 0; i < ref.length (); ++i) | |

{ | |

fprintf (stderr, "[%d] = ", i); | |

debug_slim (ref[i]); | |

fputc ('\n', stderr); | |

} | |

} | |

/* Macro to define debug(vec<T>) and debug(vec<T, va_gc>) helper | |

functions for a type T. */ | |

#define DEFINE_DEBUG_VEC(T) \ | |

template void debug_helper (vec<T> &); \ | |

template void debug_helper (vec<T, va_gc> &); \ | |

/* Define the vec<T> debug functions. */ \ | |

DEBUG_FUNCTION void \ | |

debug (vec<T> &ref) \ | |

{ \ | |

debug_helper <T> (ref); \ | |

} \ | |

DEBUG_FUNCTION void \ | |

debug (vec<T> *ptr) \ | |

{ \ | |

if (ptr) \ | |

debug (*ptr); \ | |

else \ | |

fprintf (stderr, "<nil>\n"); \ | |

} \ | |

/* Define the vec<T, va_gc> debug functions. */ \ | |

DEBUG_FUNCTION void \ | |

debug (vec<T, va_gc> &ref) \ | |

{ \ | |

debug_helper <T> (ref); \ | |

} \ | |

DEBUG_FUNCTION void \ | |

debug (vec<T, va_gc> *ptr) \ | |

{ \ | |

if (ptr) \ | |

debug (*ptr); \ | |

else \ | |

fprintf (stderr, "<nil>\n"); \ | |

} | |

/* Default-construct N elements in DST. */ | |

template <typename T> | |

inline void | |

vec_default_construct (T *dst, unsigned n) | |

{ | |

#ifdef BROKEN_VALUE_INITIALIZATION | |

/* Versions of GCC before 4.4 sometimes leave certain objects | |

uninitialized when value initialized, though if the type has | |

user defined default ctor, that ctor is invoked. As a workaround | |

perform clearing first and then the value initialization, which | |

fixes the case when value initialization doesn't initialize due to | |

the bugs and should initialize to all zeros, but still allows | |

vectors for types with user defined default ctor that initializes | |

some or all elements to non-zero. If T has no user defined | |

default ctor and some non-static data members have user defined | |

default ctors that initialize to non-zero the workaround will | |

still not work properly; in that case we just need to provide | |

user defined default ctor. */ | |

memset (dst, '\0', sizeof (T) * n); | |

#endif | |

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. 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> | |

CONSTEXPR operator vec<T, A, L> () { return vec<T, A, L>(); } | |

}; | |

extern vnull vNULL; | |

/* Embeddable vector. These vectors are suitable to be embedded | |

in other data structures so that they can be pre-allocated in a | |

contiguous memory block. | |

Embeddable vectors are implemented using the trailing array idiom, | |

thus they are not resizeable without changing the address of the | |

vector object itself. This means you cannot have variables or | |

fields of embeddable vector type -- always use a pointer to a | |

vector. The one exception is the final field of a structure, which | |

could be a vector type. | |

You will have to use the embedded_size & embedded_init calls to | |

create such objects, and they will not be resizeable (so the 'safe' | |

allocation variants are not available). | |

Properties: | |

- The whole vector and control data are allocated in a single | |

contiguous block. It uses the trailing-vector idiom, so | |

allocation must reserve enough space for all the elements | |

in the vector plus its control data. | |

- The vector cannot be re-allocated. | |

- The vector cannot grow nor shrink. | |

- No indirections needed for access/manipulation. | |

- It requires 2 words of storage (prior to vector allocation). */ | |

template<typename T, typename A> | |

struct GTY((user)) vec<T, A, vl_embed> | |

{ | |

public: | |

unsigned allocated (void) const { return m_vecpfx.m_alloc; } | |

unsigned length (void) const { return m_vecpfx.m_num; } | |

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 space (unsigned) const; | |

bool iterate (unsigned, T *) const; | |

bool iterate (unsigned, T **) const; | |

vec *copy (ALONE_CXX_MEM_STAT_INFO) const; | |

void splice (const vec &); | |

void splice (const vec *src); | |

T *quick_push (const T &); | |

T &pop (void); | |

void truncate (unsigned); | |

void quick_insert (unsigned, const T &); | |

void ordered_remove (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, unsigned = 0); | |

void quick_grow (unsigned len); | |

void quick_grow_cleared (unsigned len); | |

/* vec class can access our internal data and functions. */ | |

template <typename, typename, typename> friend struct vec; | |

/* The allocator types also need access to our internals. */ | |

friend struct va_gc; | |

friend struct va_gc_atomic; | |

friend struct va_heap; | |

/* FIXME - These fields should be private, but we need to cater to | |

compilers that have stricter notions of PODness for types. */ | |

vec_prefix m_vecpfx; | |

T m_vecdata[1]; | |

}; | |

/* Convenience wrapper functions to use when dealing with pointers to | |

embedded vectors. Some functionality for these vectors must be | |

provided via free functions for these reasons: | |

1- The pointer may be NULL (e.g., before initial allocation). | |

2- When the vector needs to grow, it must be reallocated, so | |

the pointer will change its value. | |

Because of limitations with the current GC machinery, all vectors | |

in GC memory *must* be pointers. */ | |

/* If V contains no room for NELEMS elements, return false. Otherwise, | |

return true. */ | |

template<typename T, typename A> | |

inline bool | |

vec_safe_space (const vec<T, A, vl_embed> *v, unsigned nelems) | |

{ | |

return v ? v->space (nelems) : nelems == 0; | |

} | |

/* If V is NULL, return 0. Otherwise, return V->length(). */ | |

template<typename T, typename A> | |

inline unsigned | |

vec_safe_length (const vec<T, A, vl_embed> *v) | |

{ | |

return v ? v->length () : 0; | |

} | |

/* If V is NULL, return NULL. Otherwise, return V->address(). */ | |

template<typename T, typename A> | |

inline T * | |

vec_safe_address (vec<T, A, vl_embed> *v) | |

{ | |

return v ? v->address () : NULL; | |

} | |

/* If V is NULL, return true. Otherwise, return V->is_empty(). */ | |

template<typename T, typename A> | |

inline bool | |

vec_safe_is_empty (vec<T, A, vl_embed> *v) | |

{ | |

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> | |

inline bool | |

vec_safe_reserve (vec<T, A, vl_embed> *&v, unsigned nelems, bool exact = false | |

CXX_MEM_STAT_INFO) | |

{ | |

bool extend = nelems ? !vec_safe_space (v, nelems) : false; | |

if (extend) | |

A::reserve (v, nelems, exact PASS_MEM_STAT); | |

return extend; | |

} | |

template<typename T, typename A> | |

inline bool | |

vec_safe_reserve_exact (vec<T, A, vl_embed> *&v, unsigned nelems | |

CXX_MEM_STAT_INFO) | |

{ | |

return vec_safe_reserve (v, nelems, true PASS_MEM_STAT); | |

} | |

/* Allocate GC memory for V with space for NELEMS slots. If NELEMS | |

is 0, V is initialized to NULL. */ | |

template<typename T, typename A> | |

inline void | |

vec_alloc (vec<T, A, vl_embed> *&v, unsigned nelems CXX_MEM_STAT_INFO) | |

{ | |

v = NULL; | |

vec_safe_reserve (v, nelems, false PASS_MEM_STAT); | |

} | |

/* Free the GC memory allocated by vector V and set it to NULL. */ | |

template<typename T, typename A> | |

inline void | |

vec_free (vec<T, A, vl_embed> *&v) | |

{ | |

A::release (v); | |

} | |

/* Grow V to length LEN. Allocate it, if necessary. */ | |

template<typename T, typename A> | |

inline void | |

vec_safe_grow (vec<T, A, vl_embed> *&v, unsigned len CXX_MEM_STAT_INFO) | |

{ | |

unsigned oldlen = vec_safe_length (v); | |

gcc_checking_assert (len >= oldlen); | |

vec_safe_reserve_exact (v, len - oldlen PASS_MEM_STAT); | |

v->quick_grow (len); | |

} | |

/* If V is NULL, allocate it. Call V->safe_grow_cleared(LEN). */ | |

template<typename T, typename A> | |

inline void | |

vec_safe_grow_cleared (vec<T, A, vl_embed> *&v, unsigned len CXX_MEM_STAT_INFO) | |

{ | |

unsigned oldlen = vec_safe_length (v); | |

vec_safe_grow (v, len PASS_MEM_STAT); | |

vec_default_construct (v->address () + oldlen, len - oldlen); | |

} | |

/* If V is NULL return false, otherwise return V->iterate(IX, PTR). */ | |

template<typename T, typename A> | |

inline bool | |

vec_safe_iterate (const vec<T, A, vl_embed> *v, unsigned ix, T **ptr) | |

{ | |

if (v) | |

return v->iterate (ix, ptr); | |

else | |

{ | |

*ptr = 0; | |

return false; | |

} | |

} | |

template<typename T, typename A> | |

inline bool | |

vec_safe_iterate (const vec<T, A, vl_embed> *v, unsigned ix, T *ptr) | |

{ | |

if (v) | |

return v->iterate (ix, ptr); | |

else | |

{ | |

*ptr = 0; | |

return false; | |

} | |

} | |

/* If V has no room for one more element, reallocate it. Then call | |

V->quick_push(OBJ). */ | |

template<typename T, typename A> | |

inline T * | |

vec_safe_push (vec<T, A, vl_embed> *&v, const T &obj CXX_MEM_STAT_INFO) | |

{ | |

vec_safe_reserve (v, 1, false PASS_MEM_STAT); | |

return v->quick_push (obj); | |

} | |

/* if V has no room for one more element, reallocate it. Then call | |

V->quick_insert(IX, OBJ). */ | |

template<typename T, typename A> | |

inline void | |

vec_safe_insert (vec<T, A, vl_embed> *&v, unsigned ix, const T &obj | |

CXX_MEM_STAT_INFO) | |

{ | |

vec_safe_reserve (v, 1, false PASS_MEM_STAT); | |

v->quick_insert (ix, obj); | |

} | |

/* If V is NULL, do nothing. Otherwise, call V->truncate(SIZE). */ | |

template<typename T, typename A> | |

inline void | |

vec_safe_truncate (vec<T, A, vl_embed> *v, unsigned size) | |

{ | |

if (v) | |

v->truncate (size); | |

} | |

/* 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 CXX_MEM_STAT_INFO) | |

{ | |

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, const vec<T, A, vl_embed> *src | |

CXX_MEM_STAT_INFO) | |

{ | |

unsigned src_len = vec_safe_length (src); | |

if (src_len) | |

{ | |

vec_safe_reserve_exact (dst, vec_safe_length (dst) + src_len | |

PASS_MEM_STAT); | |

dst->splice (*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. */ | |

template<typename T, typename A> | |

inline const T & | |

vec<T, A, vl_embed>::operator[] (unsigned ix) const | |

{ | |

gcc_checking_assert (ix < m_vecpfx.m_num); | |

return m_vecdata[ix]; | |

} | |

template<typename T, typename A> | |

inline T & | |

vec<T, A, vl_embed>::operator[] (unsigned ix) | |

{ | |

gcc_checking_assert (ix < m_vecpfx.m_num); | |

return m_vecdata[ix]; | |

} | |

/* Get the final element of the vector, which must not be empty. */ | |

template<typename T, typename A> | |

inline T & | |

vec<T, A, vl_embed>::last (void) | |

{ | |

gcc_checking_assert (m_vecpfx.m_num > 0); | |

return (*this)[m_vecpfx.m_num - 1]; | |

} | |

/* If this vector has space for NELEMS additional entries, return | |

true. You usually only need to use this if you are doing your | |

own vector reallocation, for instance on an embedded vector. This | |

returns true in exactly the same circumstances that vec::reserve | |

will. */ | |

template<typename T, typename A> | |

inline bool | |

vec<T, A, vl_embed>::space (unsigned nelems) const | |

{ | |

return m_vecpfx.m_alloc - m_vecpfx.m_num >= nelems; | |

} | |

/* Return iteration condition and update PTR to point to the IX'th | |

element of this vector. Use this to iterate over the elements of a | |

vector as follows, | |

for (ix = 0; vec<T, A>::iterate (v, ix, &ptr); ix++) | |

continue; */ | |

template<typename T, typename A> | |

inline bool | |

vec<T, A, vl_embed>::iterate (unsigned ix, T *ptr) const | |

{ | |

if (ix < m_vecpfx.m_num) | |

{ | |

*ptr = m_vecdata[ix]; | |

return true; | |

} | |

else | |

{ | |

*ptr = 0; | |

return false; | |

} | |

} | |

/* Return iteration condition and update *PTR to point to the | |

IX'th element of this vector. Use this to iterate over the | |

elements of a vector as follows, | |

for (ix = 0; v->iterate (ix, &ptr); ix++) | |

continue; | |

This variant is for vectors of objects. */ | |

template<typename T, typename A> | |

inline bool | |

vec<T, A, vl_embed>::iterate (unsigned ix, T **ptr) const | |

{ | |

if (ix < m_vecpfx.m_num) | |

{ | |

*ptr = CONST_CAST (T *, &m_vecdata[ix]); | |

return true; | |

} | |

else | |

{ | |

*ptr = 0; | |

return false; | |

} | |

} | |

/* Return a pointer to a copy of this vector. */ | |

template<typename T, typename A> | |

inline vec<T, A, vl_embed> * | |

vec<T, A, vl_embed>::copy (ALONE_MEM_STAT_DECL) const | |

{ | |

vec<T, A, vl_embed> *new_vec = NULL; | |

unsigned len = length (); | |

if (len) | |

{ | |

vec_alloc (new_vec, len PASS_MEM_STAT); | |

new_vec->embedded_init (len, len); | |

vec_copy_construct (new_vec->address (), m_vecdata, len); | |

} | |

return new_vec; | |

} | |

/* Copy the elements from SRC to the end of this vector as if by memcpy. | |

The vector must have sufficient headroom available. */ | |

template<typename T, typename A> | |

inline void | |

vec<T, A, vl_embed>::splice (const vec<T, A, vl_embed> &src) | |

{ | |

unsigned len = src.length (); | |

if (len) | |

{ | |

gcc_checking_assert (space (len)); | |

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 (const vec<T, A, vl_embed> *src) | |

{ | |

if (src) | |

splice (*src); | |

} | |

/* Push OBJ (a new element) onto the end of the vector. There must be | |

sufficient space in the vector. Return a pointer to the slot | |

where OBJ was inserted. */ | |

template<typename T, typename A> | |

inline T * | |

vec<T, A, vl_embed>::quick_push (const T &obj) | |

{ | |

gcc_checking_assert (space (1)); | |

T *slot = &m_vecdata[m_vecpfx.m_num++]; | |

*slot = obj; | |

return slot; | |

} | |

/* Pop and return the last element off the end of the vector. */ | |

template<typename T, typename A> | |

inline T & | |

vec<T, A, vl_embed>::pop (void) | |

{ | |

gcc_checking_assert (length () > 0); | |

return m_vecdata[--m_vecpfx.m_num]; | |

} | |

/* Set the length of the vector to SIZE. The new length must be less | |

than or equal to the current length. This is an O(1) operation. */ | |

template<typename T, typename A> | |

inline void | |

vec<T, A, vl_embed>::truncate (unsigned size) | |

{ | |

gcc_checking_assert (length () >= size); | |

m_vecpfx.m_num = size; | |

} | |

/* Insert an element, OBJ, at the IXth position of this vector. There | |

must be sufficient space. */ | |

template<typename T, typename A> | |

inline void | |

vec<T, A, vl_embed>::quick_insert (unsigned ix, const T &obj) | |

{ | |

gcc_checking_assert (length () < allocated ()); | |

gcc_checking_assert (ix <= length ()); | |

T *slot = &m_vecdata[ix]; | |

memmove (slot + 1, slot, (m_vecpfx.m_num++ - ix) * sizeof (T)); | |

*slot = obj; | |

} | |

/* Remove an element from the IXth position of this vector. Ordering of | |

remaining elements is preserved. This is an O(N) operation due to | |

memmove. */ | |

template<typename T, typename A> | |

inline void | |

vec<T, A, vl_embed>::ordered_remove (unsigned ix) | |

{ | |

gcc_checking_assert (ix < length ()); | |

T *slot = &m_vecdata[ix]; | |

memmove (slot, slot + 1, (--m_vecpfx.m_num - ix) * sizeof (T)); | |

} | |

/* Remove an element from the IXth position of this vector. Ordering of | |

remaining elements is destroyed. This is an O(1) operation. */ | |

template<typename T, typename A> | |

inline void | |

vec<T, A, vl_embed>::unordered_remove (unsigned ix) | |

{ | |

gcc_checking_assert (ix < length ()); | |

m_vecdata[ix] = m_vecdata[--m_vecpfx.m_num]; | |

} | |

/* Remove LEN elements starting at the IXth. Ordering is retained. | |

This is an O(N) operation due to memmove. */ | |

template<typename T, typename A> | |

inline void | |

vec<T, A, vl_embed>::block_remove (unsigned ix, unsigned len) | |

{ | |

gcc_checking_assert (ix + len <= length ()); | |

T *slot = &m_vecdata[ix]; | |

m_vecpfx.m_num -= len; | |

memmove (slot, slot + len, (m_vecpfx.m_num - ix) * sizeof (T)); | |

} | |

/* Sort the contents of this vector with qsort. CMP is the comparison | |

function to pass to qsort. */ | |

template<typename T, typename A> | |

inline void | |

vec<T, A, vl_embed>::qsort (int (*cmp) (const void *, const void *)) | |

{ | |

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 | |

than the second. */ | |

template<typename T, typename A> | |

unsigned | |

vec<T, A, vl_embed>::lower_bound (T obj, bool (*lessthan)(const T &, const T &)) | |

const | |

{ | |

unsigned int len = length (); | |

unsigned int half, middle; | |

unsigned int first = 0; | |

while (len > 0) | |

{ | |

half = len / 2; | |

middle = first; | |

middle += half; | |

T middle_elem = (*this)[middle]; | |

if (lessthan (middle_elem, obj)) | |

{ | |

first = middle; | |

++first; | |

len = len - half - 1; | |

} | |

else | |

len = half; | |

} | |

return first; | |

} | |

/* Return the number of bytes needed to embed an instance of an | |

embeddable vec inside another data structure. | |

Use these methods to determine the required size and initialization | |

of a vector V of type T embedded within another structure (as the | |

final member): | |

size_t vec<T, A, vl_embed>::embedded_size (unsigned alloc); | |

void v->embedded_init (unsigned alloc, unsigned num); | |

These allow the caller to perform the memory allocation. */ | |

template<typename T, typename A> | |

inline size_t | |

vec<T, A, vl_embed>::embedded_size (unsigned alloc) | |

{ | |

typedef vec<T, A, vl_embed> vec_embedded; | |

return offsetof (vec_embedded, m_vecdata) + alloc * sizeof (T); | |

} | |

/* Initialize the vector to contain room for ALLOC elements and | |

NUM active elements. */ | |

template<typename T, typename A> | |

inline void | |

vec<T, A, vl_embed>::embedded_init (unsigned alloc, unsigned num, unsigned aut) | |

{ | |

m_vecpfx.m_alloc = alloc; | |

m_vecpfx.m_using_auto_storage = aut; | |

m_vecpfx.m_num = num; | |

} | |

/* Grow the vector to a specific length. LEN must be as long or longer than | |

the current length. The new elements are uninitialized. */ | |

template<typename T, typename A> | |

inline void | |

vec<T, A, vl_embed>::quick_grow (unsigned len) | |

{ | |

gcc_checking_assert (length () <= len && len <= m_vecpfx.m_alloc); | |

m_vecpfx.m_num = len; | |

} | |

/* Grow the vector to a specific length. LEN must be as long or longer than | |

the current length. The new elements are initialized to zero. */ | |

template<typename T, typename A> | |

inline void | |

vec<T, A, vl_embed>::quick_grow_cleared (unsigned len) | |

{ | |

unsigned oldlen = length (); | |

size_t growby = len - oldlen; | |

quick_grow (len); | |

if (growby != 0) | |

vec_default_construct (address () + oldlen, growby); | |

} | |

/* Garbage collection support for vec<T, A, vl_embed>. */ | |

template<typename T> | |

void | |

gt_ggc_mx (vec<T, va_gc> *v) | |

{ | |

extern void gt_ggc_mx (T &); | |

for (unsigned i = 0; i < v->length (); i++) | |

gt_ggc_mx ((*v)[i]); | |

} | |

template<typename T> | |

void | |

gt_ggc_mx (vec<T, va_gc_atomic, vl_embed> *v ATTRIBUTE_UNUSED) | |

{ | |

/* Nothing to do. Vectors of atomic types wrt GC do not need to | |

be traversed. */ | |

} | |

/* PCH support for vec<T, A, vl_embed>. */ | |

template<typename T, typename A> | |

void | |

gt_pch_nx (vec<T, A, vl_embed> *v) | |

{ | |

extern void gt_pch_nx (T &); | |

for (unsigned i = 0; i < v->length (); i++) | |

gt_pch_nx ((*v)[i]); | |

} | |

template<typename T, typename A> | |

void | |

gt_pch_nx (vec<T *, A, vl_embed> *v, gt_pointer_operator op, void *cookie) | |

{ | |

for (unsigned i = 0; i < v->length (); i++) | |

op (&((*v)[i]), cookie); | |

} | |

template<typename T, typename A> | |

void | |

gt_pch_nx (vec<T, A, vl_embed> *v, gt_pointer_operator op, void *cookie) | |

{ | |

extern void gt_pch_nx (T *, gt_pointer_operator, void *); | |

for (unsigned i = 0; i < v->length (); i++) | |

gt_pch_nx (&((*v)[i]), op, cookie); | |

} | |

/* Space efficient vector. These vectors can grow dynamically and are | |

allocated together with their control data. They are suited to be | |

included in data structures. Prior to initial allocation, they | |

only take a single word of storage. | |

These vectors are implemented as a pointer to an embeddable vector. | |

The semantics allow for this pointer to be NULL to represent empty | |

vectors. This way, empty vectors occupy minimal space in the | |

structure containing them. | |

Properties: | |

- The whole vector and control data are allocated in a single | |

contiguous block. | |

- The whole vector may be re-allocated. | |

- Vector data may grow and shrink. | |

- Access and manipulation requires a pointer test and | |

indirection. | |

- It requires 1 word of storage (prior to vector allocation). | |

Limitations: | |

These vectors must be PODs because they are stored in unions. | |

(http://en.wikipedia.org/wiki/Plain_old_data_structures). | |

As long as we use C++03, we cannot have constructors nor | |

destructors in classes that are stored in unions. */ | |

template<typename T> | |

struct vec<T, va_heap, vl_ptr> | |

{ | |

public: | |

/* Memory allocation and deallocation for the embedded vector. | |

Needed because we cannot have proper ctors/dtors defined. */ | |

void create (unsigned nelems CXX_MEM_STAT_INFO); | |

void release (void); | |

/* Vector operations. */ | |

bool exists (void) const | |

{ return m_vec != NULL; } | |

bool is_empty (void) const | |

{ return m_vec ? m_vec->is_empty () : true; } | |

unsigned length (void) const | |

{ return m_vec ? m_vec->length () : 0; } | |

T *address (void) | |

{ return m_vec ? m_vec->m_vecdata : NULL; } | |

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]; } | |

bool operator!=(const vec &other) const | |

{ return !(*this == other); } | |

bool operator==(const vec &other) const | |

{ return address () == other.address (); } | |

T &operator[] (unsigned ix) | |

{ return (*m_vec)[ix]; } | |

T &last (void) | |

{ return m_vec->last (); } | |

bool space (int nelems) const | |

{ return m_vec ? m_vec->space (nelems) : nelems == 0; } | |

bool iterate (unsigned ix, T *p) const; | |

bool iterate (unsigned ix, T **p) const; | |

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 (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 truncate (unsigned); | |

void safe_grow (unsigned CXX_MEM_STAT_INFO); | |

void safe_grow_cleared (unsigned CXX_MEM_STAT_INFO); | |

void quick_grow (unsigned); | |

void quick_grow_cleared (unsigned); | |

void quick_insert (unsigned, const T &); | |

void safe_insert (unsigned, const T & CXX_MEM_STAT_INFO); | |

void ordered_remove (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; | |

bool using_auto_storage () const; | |

/* FIXME - This field should be private, but we need to cater to | |

compilers that have stricter notions of PODness for types. */ | |

vec<T, va_heap, vl_embed> *m_vec; | |

}; | |

/* auto_vec is a subclass of vec that automatically manages creating and | |

releasing the internal vector. If N is non zero then it has N elements of | |

internal storage. The default is no internal storage, and you probably only | |

want to ask for internal storage for vectors on the stack because if the | |

size of the vector is larger than the internal storage that space is wasted. | |

*/ | |

template<typename T, size_t N = 0> | |

class auto_vec : public vec<T, va_heap> | |

{ | |

public: | |

auto_vec () | |

{ | |

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 () | |

{ | |

this->release (); | |

} | |

private: | |

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 | |

destroyed. */ | |

template<typename T> | |

class auto_vec<T, 0> : public vec<T, va_heap> | |

{ | |

public: | |

auto_vec () { this->m_vec = NULL; } | |

auto_vec (size_t n) { this->create (n); } | |

~auto_vec () { this->release (); } | |

}; | |

/* Allocate heap memory for pointer V and create the internal vector | |

with space for NELEMS elements. If NELEMS is 0, the internal | |

vector is initialized to empty. */ | |

template<typename T> | |

inline void | |

vec_alloc (vec<T> *&v, unsigned nelems CXX_MEM_STAT_INFO) | |

{ | |

v = new vec<T>; | |

v->create (nelems PASS_MEM_STAT); | |

} | |

/* Conditionally allocate heap memory for VEC and its internal vector. */ | |

template<typename T> | |

inline void | |

vec_check_alloc (vec<T, va_heap> *&vec, unsigned nelems CXX_MEM_STAT_INFO) | |

{ | |

if (!vec) | |

vec_alloc (vec, nelems PASS_MEM_STAT); | |

} | |

/* Free the heap memory allocated by vector V and set it to NULL. */ | |

template<typename T> | |

inline void | |

vec_free (vec<T> *&v) | |

{ | |

if (v == NULL) | |

return; | |

v->release (); | |

delete v; | |

v = NULL; | |

} | |

/* Return iteration condition and update PTR to point to the IX'th | |

element of this vector. Use this to iterate over the elements of a | |

vector as follows, | |

for (ix = 0; v.iterate (ix, &ptr); ix++) | |

continue; */ | |

template<typename T> | |

inline bool | |

vec<T, va_heap, vl_ptr>::iterate (unsigned ix, T *ptr) const | |

{ | |

if (m_vec) | |

return m_vec->iterate (ix, ptr); | |

else | |

{ | |

*ptr = 0; | |

return false; | |

} | |

} | |

/* Return iteration condition and update *PTR to point to the | |

IX'th element of this vector. Use this to iterate over the | |

elements of a vector as follows, | |

for (ix = 0; v->iterate (ix, &ptr); ix++) | |

continue; | |

This variant is for vectors of objects. */ | |

template<typename T> | |

inline bool | |

vec<T, va_heap, vl_ptr>::iterate (unsigned ix, T **ptr) const | |

{ | |

if (m_vec) | |

return m_vec->iterate (ix, ptr); | |

else | |

{ | |

*ptr = 0; | |

return false; | |

} | |

} | |

/* Convenience macro for forward iteration. */ | |

#define FOR_EACH_VEC_ELT(V, I, P) \ | |

for (I = 0; (V).iterate ((I), &(P)); ++(I)) | |

#define FOR_EACH_VEC_SAFE_ELT(V, I, P) \ | |

for (I = 0; vec_safe_iterate ((V), (I), &(P)); ++(I)) | |

/* Likewise, but start from FROM rather than 0. */ | |

#define FOR_EACH_VEC_ELT_FROM(V, I, P, FROM) \ | |

for (I = (FROM); (V).iterate ((I), &(P)); ++(I)) | |

/* Convenience macro for reverse iteration. */ | |

#define FOR_EACH_VEC_ELT_REVERSE(V, I, P) \ | |

for (I = (V).length () - 1; \ | |

(V).iterate ((I), &(P)); \ | |

(I)--) | |

#define FOR_EACH_VEC_SAFE_ELT_REVERSE(V, I, P) \ | |

for (I = vec_safe_length (V) - 1; \ | |

vec_safe_iterate ((V), (I), &(P)); \ | |

(I)--) | |

/* Return a copy of this vector. */ | |

template<typename T> | |

inline vec<T, va_heap, vl_ptr> | |

vec<T, va_heap, vl_ptr>::copy (ALONE_MEM_STAT_DECL) const | |

{ | |

vec<T, va_heap, vl_ptr> new_vec = vNULL; | |

if (length ()) | |

new_vec.m_vec = m_vec->copy (); | |

return new_vec; | |

} | |

/* Ensure that the vector has at least RESERVE slots available (if | |

EXACT is false), or exactly RESERVE slots available (if EXACT is | |

true). | |

This may create additional headroom if EXACT is false. | |

Note that this can cause the embedded vector to be reallocated. | |

Returns true iff reallocation actually occurred. */ | |

template<typename T> | |

inline bool | |

vec<T, va_heap, vl_ptr>::reserve (unsigned nelems, bool exact MEM_STAT_DECL) | |

{ | |

if (space (nelems)) | |

return false; | |

/* For now play a game with va_heap::reserve to hide our auto storage if any, | |

this is necessary because it doesn't have enough information to know the | |

embedded vector is in auto storage, and so should not be freed. */ | |

vec<T, va_heap, vl_embed> *oldvec = m_vec; | |

unsigned int oldsize = 0; | |

bool handle_auto_vec = m_vec && using_auto_storage (); | |

if (handle_auto_vec) | |

{ | |

m_vec = NULL; | |

oldsize = oldvec->length (); | |

nelems += oldsize; | |

} | |

va_heap::reserve (m_vec, nelems, exact PASS_MEM_STAT); | |

if (handle_auto_vec) | |

{ | |

vec_copy_construct (m_vec->address (), oldvec->address (), oldsize); | |

m_vec->m_vecpfx.m_num = oldsize; | |

} | |

return true; | |

} | |

/* Ensure that this vector has exactly NELEMS slots available. This | |

will not create additional headroom. Note this can cause the | |

embedded vector to be reallocated. Returns true iff reallocation | |

actually occurred. */ | |

template<typename T> | |

inline bool | |

vec<T, va_heap, vl_ptr>::reserve_exact (unsigned nelems MEM_STAT_DECL) | |

{ | |

return reserve (nelems, true PASS_MEM_STAT); | |

} | |

/* Create the internal vector and reserve NELEMS for it. This is | |

exactly like vec::reserve, but the internal vector is | |

unconditionally allocated from scratch. The old one, if it | |

existed, is lost. */ | |

template<typename T> | |

inline void | |

vec<T, va_heap, vl_ptr>::create (unsigned nelems MEM_STAT_DECL) | |

{ | |

m_vec = NULL; | |

if (nelems > 0) | |

reserve_exact (nelems PASS_MEM_STAT); | |

} | |

/* Free the memory occupied by the embedded vector. */ | |

template<typename T> | |

inline void | |

vec<T, va_heap, vl_ptr>::release (void) | |

{ | |

if (!m_vec) | |

return; | |

if (using_auto_storage ()) | |

{ | |

m_vec->m_vecpfx.m_num = 0; | |

return; | |

} | |

va_heap::release (m_vec); | |

} | |

/* Copy the elements from SRC to the end of this vector as if by memcpy. | |

SRC and this vector must be allocated with the same memory | |

allocation mechanism. This vector is assumed to have sufficient | |

headroom available. */ | |

template<typename T> | |

inline void | |

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)); | |

} | |

/* Copy the elements in SRC to the end of this vector as if by memcpy. | |

SRC and this vector must be allocated with the same mechanism. | |

If there is not enough headroom in this vector, it will be reallocated | |

as needed. */ | |

template<typename T> | |

inline void | |

vec<T, va_heap, vl_ptr>::safe_splice (const vec<T, va_heap, vl_ptr> &src | |

MEM_STAT_DECL) | |

{ | |

if (src.length ()) | |

{ | |

reserve_exact (src.length ()); | |

splice (src); | |

} | |

} | |

/* Push OBJ (a new element) onto the end of the vector. There must be | |

sufficient space in the vector. Return a pointer to the slot | |

where OBJ was inserted. */ | |

template<typename T> | |

inline T * | |

vec<T, va_heap, vl_ptr>::quick_push (const T &obj) | |

{ | |

return m_vec->quick_push (obj); | |

} | |

/* Push a new element OBJ onto the end of this vector. Reallocates | |

the embedded vector, if needed. Return a pointer to the slot where | |

OBJ was inserted. */ | |

template<typename T> | |

inline T * | |

vec<T, va_heap, vl_ptr>::safe_push (const T &obj MEM_STAT_DECL) | |

{ | |

reserve (1, false PASS_MEM_STAT); | |

return quick_push (obj); | |

} | |

/* Pop and return the last element off the end of the vector. */ | |

template<typename T> | |

inline T & | |

vec<T, va_heap, vl_ptr>::pop (void) | |

{ | |

return m_vec->pop (); | |

} | |

/* Set the length of the vector to LEN. The new length must be less | |

than or equal to the current length. This is an O(1) operation. */ | |

template<typename T> | |

inline void | |

vec<T, va_heap, vl_ptr>::truncate (unsigned size) | |

{ | |

if (m_vec) | |

m_vec->truncate (size); | |

else | |

gcc_checking_assert (size == 0); | |

} | |

/* Grow the vector to a specific length. LEN must be as long or | |

longer than the current length. The new elements are | |

uninitialized. Reallocate the internal vector, if needed. */ | |

template<typename T> | |

inline void | |

vec<T, va_heap, vl_ptr>::safe_grow (unsigned len MEM_STAT_DECL) | |

{ | |

unsigned oldlen = length (); | |

gcc_checking_assert (oldlen <= len); | |

reserve_exact (len - oldlen PASS_MEM_STAT); | |

if (m_vec) | |

m_vec->quick_grow (len); | |

else | |

gcc_checking_assert (len == 0); | |

} | |

/* Grow the embedded vector to a specific length. LEN must be as | |

long or longer than the current length. The new elements are | |

initialized to zero. Reallocate the internal vector, if needed. */ | |

template<typename T> | |

inline void | |

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); | |

if (growby != 0) | |

vec_default_construct (address () + oldlen, growby); | |

} | |

/* Same as vec::safe_grow but without reallocation of the internal vector. | |

If the vector cannot be extended, a runtime assertion will be triggered. */ | |

template<typename T> | |

inline void | |

vec<T, va_heap, vl_ptr>::quick_grow (unsigned len) | |

{ | |

gcc_checking_assert (m_vec); | |

m_vec->quick_grow (len); | |

} | |

/* Same as vec::quick_grow_cleared but without reallocation of the | |

internal vector. If the vector cannot be extended, a runtime | |

assertion will be triggered. */ | |

template<typename T> | |

inline void | |

vec<T, va_heap, vl_ptr>::quick_grow_cleared (unsigned len) | |

{ | |

gcc_checking_assert (m_vec); | |

m_vec->quick_grow_cleared (len); | |

} | |

/* Insert an element, OBJ, at the IXth position of this vector. There | |

must be sufficient space. */ | |

template<typename T> | |

inline void | |

vec<T, va_heap, vl_ptr>::quick_insert (unsigned ix, const T &obj) | |

{ | |

m_vec->quick_insert (ix, obj); | |

} | |

/* Insert an element, OBJ, at the IXth position of the vector. | |

Reallocate the embedded vector, if necessary. */ | |

template<typename T> | |

inline void | |

vec<T, va_heap, vl_ptr>::safe_insert (unsigned ix, const T &obj MEM_STAT_DECL) | |

{ | |

reserve (1, false PASS_MEM_STAT); | |

quick_insert (ix, obj); | |

} | |

/* Remove an element from the IXth position of this vector. Ordering of | |

remaining elements is preserved. This is an O(N) operation due to | |

a memmove. */ | |

template<typename T> | |

inline void | |

vec<T, va_heap, vl_ptr>::ordered_remove (unsigned ix) | |

{ | |

m_vec->ordered_remove (ix); | |

} | |

/* Remove an element from the IXth position of this vector. Ordering | |

of remaining elements is destroyed. This is an O(1) operation. */ | |

template<typename T> | |

inline void | |

vec<T, va_heap, vl_ptr>::unordered_remove (unsigned ix) | |

{ | |

m_vec->unordered_remove (ix); | |

} | |

/* Remove LEN elements starting at the IXth. Ordering is retained. | |

This is an O(N) operation due to memmove. */ | |

template<typename T> | |

inline void | |

vec<T, va_heap, vl_ptr>::block_remove (unsigned ix, unsigned len) | |

{ | |

m_vec->block_remove (ix, len); | |

} | |

/* Sort the contents of this vector with qsort. CMP is the comparison | |

function to pass to qsort. */ | |

template<typename T> | |

inline void | |

vec<T, va_heap, vl_ptr>::qsort (int (*cmp) (const void *, const void *)) | |

{ | |

if (m_vec) | |

m_vec->qsort (cmp); | |

} | |

/* 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 | |

than the second. */ | |

template<typename T> | |

inline unsigned | |

vec<T, va_heap, vl_ptr>::lower_bound (T obj, | |

bool (*lessthan)(const T &, const T &)) | |

const | |

{ | |

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 | |

{ | |

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 (); | |

vec.release (); | |

} | |

#if (GCC_VERSION >= 3000) | |

# pragma GCC poison m_vec m_vecpfx m_vecdata | |

#endif | |

#endif // GCC_VEC_H |