Dump per-site memory statistics.
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.
Not all vector operations support non-POD types and such restrictions
are enforced through static assertions. Some operations which often use
memmove to move elements around like quick_insert, safe_insert,
ordered_remove, unordered_remove, block_remove etc. require trivially
copyable types. Sorting operations, qsort, sort and stablesort, require
those too but as an extension allow also std::pair of 2 trivially copyable
types which happens to work even when std::pair itself isn't trivially
copyable. The quick_grow and safe_grow operations require trivially
default constructible types. One can use quick_grow_cleared or
safe_grow_cleared for non-trivially default constructible types if needed
(but of course such operation is more expensive then). The pop operation
returns reference to the last element only for trivially destructible
types, for non-trivially destructible types one should use last operation
followed by pop which in that case returns void.
And finally, the GC and GC atomic vectors should always be used with
trivially destructible types, as nothing will invoke destructors when they
are freed during GC.
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.
References vec_mem_desc, and VEC_ORIGIN.
Referenced by dump_memory_report().
