/* Vector API for GNU compiler. | |

Copyright (C) 2004-2013 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 | |

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

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

- Stack: allocation is done using alloca. | |

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

/* 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 (size_t, const char *, int, const char *); | |

void release_overhead (void); | |

static unsigned calculate_allocation (vec_prefix *, unsigned, bool); | |

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

friend struct va_stack; | |

unsigned alloc_; | |

unsigned num_; | |

}; | |

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

va_stack - Allocation uses alloca. */ | |

/* 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 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->vecpfx_ : 0, reserve, exact); | |

if (!alloc) | |

{ | |

release (v); | |

return; | |

} | |

if (GATHER_STATISTICS && v) | |

v->vecpfx_.release_overhead (); | |

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->vecpfx_.register_overhead (size FINAL_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->vecpfx_.release_overhead (); | |

::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) { 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. */ | |

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

{ | |

}; | |

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

struct va_stack | |

{ | |

/* Use vl_ptr as the default layout for stack vectors. */ | |

typedef vl_ptr default_layout; | |

template<typename T> | |

static void alloc (vec<T, va_stack, vl_ptr>&, unsigned, | |

vec<T, va_stack, vl_embed> *); | |

template <typename T> | |

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

CXX_MEM_STAT_INFO); | |

template <typename T> | |

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

}; | |

/* Helper functions to keep track of vectors allocated on the stack. */ | |

void register_stack_vec (void *); | |

int stack_vec_register_index (void *); | |

void unregister_stack_vec (unsigned); | |

/* Allocate a vector V which uses alloca for the initial allocation. | |

SPACE is space allocated using alloca. NELEMS is the number of | |

entries allocated. */ | |

template<typename T> | |

void | |

va_stack::alloc (vec<T, va_stack, vl_ptr> &v, unsigned nelems, | |

vec<T, va_stack, vl_embed> *space) | |

{ | |

v.vec_ = space; | |

register_stack_vec (static_cast<void *> (v.vec_)); | |

v.vec_->embedded_init (nelems, 0); | |

} | |

/* Reserve NELEMS slots for a vector initially allocated on the stack. | |

When this happens, we switch back to heap allocation. We remove | |

the vector from stack_vecs, if it is there, since we no longer need | |

to avoid freeing it. If EXACT is true, grow exactly, otherwise | |

grow exponentially. */ | |

template<typename T> | |

void | |

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

MEM_STAT_DECL) | |

{ | |

int ix = stack_vec_register_index (static_cast<void *> (v)); | |

if (ix >= 0) | |

unregister_stack_vec (ix); | |

else | |

{ | |

/* V is already on the heap. */ | |

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

nelems, exact PASS_MEM_STAT); | |

return; | |

} | |

/* Move VEC_ to the heap. */ | |

nelems += v->vecpfx_.num_; | |

vec<T, va_stack, vl_embed> *oldvec = v; | |

v = NULL; | |

va_heap::reserve (reinterpret_cast<vec<T, va_heap, vl_embed> *&>(v), nelems, | |

exact PASS_MEM_STAT); | |

if (v && oldvec) | |

{ | |

v->vecpfx_.num_ = oldvec->length (); | |

memcpy (v->vecdata_, | |

oldvec->vecdata_, | |

oldvec->length () * sizeof (T)); | |

} | |

} | |

/* Free a vector allocated on the stack. Don't actually free it if we | |

find it in the hash table. */ | |

template<typename T> | |

void | |

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

{ | |

if (v == NULL) | |

return; | |

int ix = stack_vec_register_index (static_cast<void *> (v)); | |

if (ix >= 0) | |

{ | |

unregister_stack_vec (ix); | |

v = NULL; | |

} | |

else | |

{ | |

/* The vector was not on the list of vectors allocated on the stack, so it | |

must be allocated on the heap. */ | |

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

} | |

} | |

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

{ | |

}; | |

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

struct vnull | |

{ | |

template <typename T, typename A, typename L> | |

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 vecpfx_.alloc_; } | |

unsigned length (void) const { return vecpfx_.num_; } | |

bool is_empty (void) const { return vecpfx_.num_ == 0; } | |

T *address (void) { return vecdata_; } | |

const T *address (void) const { return vecdata_; } | |

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

void splice (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 *)); | |

unsigned lower_bound (T, bool (*)(const T &, const T &)) const; | |

static size_t embedded_size (unsigned); | |

void embedded_init (unsigned, 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; | |

friend struct va_stack; | |

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

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

vec_prefix vecpfx_; | |

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

memset (&(v->address()[oldlen]), 0, sizeof (T) * (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) | |

{ | |

return src ? src->copy () : 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 | |

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

} | |

} | |

/* 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 < vecpfx_.num_); | |

return vecdata_[ix]; | |

} | |

template<typename T, typename A> | |

inline T & | |

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

{ | |

gcc_checking_assert (ix < vecpfx_.num_); | |

return 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 (vecpfx_.num_ > 0); | |

return (*this)[vecpfx_.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 vecpfx_.alloc_ - vecpfx_.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 < vecpfx_.num_) | |

{ | |

*ptr = 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 < vecpfx_.num_) | |

{ | |

*ptr = CONST_CAST (T *, &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); | |

memcpy (new_vec->address(), vecdata_, sizeof (T) * 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 (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)); | |

vecpfx_.num_ += len; | |

} | |

} | |

template<typename T, typename A> | |

inline void | |

vec<T, A, vl_embed>::splice (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 = &vecdata_[vecpfx_.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 vecdata_[--vecpfx_.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); | |

vecpfx_.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 = &vecdata_[ix]; | |

memmove (slot + 1, slot, (vecpfx_.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 = &vecdata_[ix]; | |

memmove (slot, slot + 1, (--vecpfx_.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()); | |

vecdata_[ix] = vecdata_[--vecpfx_.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 = &vecdata_[ix]; | |

vecpfx_.num_ -= len; | |

memmove (slot, slot + len, (vecpfx_.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 *)) | |

{ | |

::qsort (address(), length(), sizeof (T), cmp); | |

} | |

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

{ | |

vecpfx_.alloc_ = alloc; | |

vecpfx_.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 <= vecpfx_.alloc_); | |

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

quick_grow (len); | |

memset (&(address()[oldlen]), 0, sizeof (T) * (len - oldlen)); | |

} | |

/* 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, typename A> | |

struct vec<T, A, 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 vec_ != NULL; } | |

bool is_empty (void) const | |

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

unsigned length (void) const | |

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

T *address (void) | |

{ return vec_ ? vec_->vecdata_ : NULL; } | |

const T *address (void) const | |

{ return vec_ ? vec_->vecdata_ : NULL; } | |

const T &operator[] (unsigned ix) const | |

{ return (*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 (*vec_)[ix]; } | |

T &last (void) | |

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

bool space (int nelems) const | |

{ return vec_ ? 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 (vec &); | |

void safe_splice (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 *)); | |

unsigned lower_bound (T, bool (*)(const T &, const T &)) const; | |

template<typename T1> | |

friend void va_stack::alloc(vec<T1, va_stack, vl_ptr>&, unsigned, | |

vec<T1, va_stack, vl_embed> *); | |

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

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

vec<T, A, vl_embed> *vec_; | |

}; | |

/* Empty specialization for GC allocation. This will prevent GC | |

vectors from using the vl_ptr layout. FIXME: This is needed to | |

circumvent limitations in the GTY machinery. */ | |

template<typename T> | |

struct vec<T, va_gc, vl_ptr> | |

{ | |

}; | |

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

} | |

/* Allocate a new stack vector with space for exactly NELEMS objects. | |

If NELEMS is zero, NO vector is created. | |

For the stack allocator, no memory is really allocated. The vector | |

is initialized to be at address SPACE and contain NELEMS slots. | |

Memory allocation actually occurs in the expansion of VEC_alloc. | |

Usage notes: | |

* This does not allocate an instance of vec<T, A>. It allocates the | |

actual vector of elements (i.e., vec<T, A, vl_embed>) inside a | |

vec<T, A> instance. | |

* This allocator must always be a macro: | |

We support a vector which starts out with space on the stack and | |

switches to heap space when forced to reallocate. This works a | |

little differently. In the case of stack vectors, vec_alloc will | |

expand to a call to vec_alloc_1 that calls XALLOCAVAR to request | |

the initial allocation. This uses alloca to get the initial | |

space. Since alloca can not be usefully called in an inline | |

function, vec_alloc must always be a macro. | |

Important limitations of stack vectors: | |

- Only the initial allocation will be made using alloca, so pass | |

a reasonable estimate that doesn't use too much stack space; | |

don't pass zero. | |

- Don't return a stack-allocated vector from the function which | |

allocated it. */ | |

#define vec_stack_alloc(T,V,N) \ | |

do { \ | |

typedef vec<T, va_stack, vl_embed> stackv; \ | |

va_stack::alloc (V, N, XALLOCAVAR (stackv, stackv::embedded_size (N)));\ | |

} while (0) | |

/* 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, typename A> | |

inline bool | |

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

{ | |

if (vec_) | |

return 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, typename A> | |

inline bool | |

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

{ | |

if (vec_) | |

return 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, typename A> | |

inline vec<T, A, vl_ptr> | |

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

{ | |

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

if (length ()) | |

new_vec.vec_ = 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, typename A> | |

inline bool | |

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

{ | |

bool extend = nelems ? !space (nelems) : false; | |

if (extend) | |

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

return extend; | |

} | |

/* 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, typename A> | |

inline bool | |

vec<T, A, 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, typename A> | |

inline void | |

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

{ | |

vec_ = NULL; | |

if (nelems > 0) | |

reserve_exact (nelems PASS_MEM_STAT); | |

} | |

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

template<typename T, typename A> | |

inline void | |

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

{ | |

if (vec_) | |

A::release (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, typename A> | |

inline void | |

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

{ | |

if (src.vec_) | |

vec_->splice (*(src.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, typename A> | |

inline void | |

vec<T, A, vl_ptr>::safe_splice (vec<T, A, 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, typename A> | |

inline T * | |

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

{ | |

return 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, typename A> | |

inline T * | |

vec<T, A, 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, typename A> | |

inline T & | |

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

{ | |

return 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, typename A> | |

inline void | |

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

{ | |

if (vec_) | |

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, typename A> | |

inline void | |

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

{ | |

unsigned oldlen = length (); | |

gcc_checking_assert (oldlen <= len); | |

reserve_exact (len - oldlen PASS_MEM_STAT); | |

vec_->quick_grow (len); | |

} | |

/* 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, typename A> | |

inline void | |

vec<T, A, vl_ptr>::safe_grow_cleared (unsigned len MEM_STAT_DECL) | |

{ | |

unsigned oldlen = length (); | |

safe_grow (len PASS_MEM_STAT); | |

memset (&(address()[oldlen]), 0, sizeof (T) * (len - oldlen)); | |

} | |

/* 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, typename A> | |

inline void | |

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

{ | |

gcc_checking_assert (vec_); | |

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, typename A> | |

inline void | |

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

{ | |

gcc_checking_assert (vec_); | |

vec_->quick_grow_cleared (len); | |

} | |

/* 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_ptr>::quick_insert (unsigned ix, const T &obj) | |

{ | |

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, typename A> | |

inline void | |

vec<T, A, 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, typename A> | |

inline void | |

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

{ | |

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, typename A> | |

inline void | |

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

{ | |

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, typename A> | |

inline void | |

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

{ | |

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, typename A> | |

inline void | |

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

{ | |

if (vec_) | |

vec_->qsort (cmp); | |

} | |

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

inline unsigned | |

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

const | |

{ | |

return vec_ ? vec_->lower_bound (obj, lessthan) : 0; | |

} | |

#if (GCC_VERSION >= 3000) | |

# pragma GCC poison vec_ vecpfx_ vecdata_ | |

#endif | |

#endif // GCC_VEC_H |