Issue 6233044: [cxx-conversion] Convert vec.[ch] to C++ [1/3]
|
Created:
11 years, 11 months ago by Diego Novillo Modified:
11 years, 11 months ago CC:
gcc-patches_gcc.gnu.org Visibility:
Public. |
Patch Set 1 #MessagesTotal messages: 10
This series of 3 patches re-implement vec.[ch] in C++.
The main goal of this first step is to minimize changes to client
code. I tried very hard to maintain the existing API. This means
that vectors are still simple structures accessed via the existing
VEC_* functions.
The major change introduced here is the removal of all the macro-based
type creation in vec.h:
1- Given a type T and an allocation strategy A, VEC(T,A) used to
expand into the C type 'struct VEC_T_A'. The family of accessor
functions for VEC_T_A were created via macro expansion and token
pasting.
After this patch, VEC(T,A) expands to 'vec_t<T>':
template<typename T>
struct GTY(()) vec_t
{
vec_prefix prefix;
T GTY((length ("%h.prefix.num"))) vec[1];
};
The family of accessor functions for vec_t<T> are free functions
templated on <T> or <T,A> depending on whether the function needs
to perform allocation operations.
2- All the DEF_VEC_[IOP] and DEF_VEC_ALLOC_[IOP] macros expand to the
nil expansion 'struct vec_swallow_trailing_semi'. This represents
the bulk of the removal in vec.h.
3- I removed one indirection from the existing VEC structures. Before
this patch, the visible structure created by VEC_T_A had a single
element 'base', which, in turn, was the structure holding 'prefix'
and 'vec'. The new vec_t<T> has 'prefix' and 'vec' in it. This
may change in the second iteration of this patch.
Some client code changes were needed:
1- The allocation names 'heap', 'stack' and 'gc' are not embedded in
the type name anymore. They are enum values used as a template
argument for functions like VEC_alloc() and VEC_free(). Since they
are now separate identifiers, some existing code that declared
variables with the names 'heap' and 'stack' had to change.
I did not change these enum values to better names because that
would have meant changing a lot more client code. I will change
this in a future patch.
2- VEC_index and VEC_last now return a reference to the element. The
existing APIs implemented two versions of these functions. One
returning the element itself (used for vec_t<T *>). Another returning
a pointer to the element (used for vec_t<T>).
This is impossible to represent in C++ directly, as functions
cannot be overloaded by their return value. Instead, I made them
return a reference to the element. This means that vectors storing
pointers (T *) do not need to change, but vectors of objects (T) do
need to change.
We have fewer vec_t<T> than vec_t<T *>, so this was the smaller change
(which still meant changing a few hundred call sites).
3- The family of VEC_*push and VEC_*replace functions have overloads
for handling 'T' and 'const T *' objects. The former is used for
vec_t<T>, the latter for vec_t<T*>. This means, however, than when
pushing the special value 0 on a vec_t<T*>, the compiler will not
know which overload we meant, as 0 matches both. In these cases
(not very many), a static cast is all we need to help it.
I'm not terribly content with this one. I'll try to have a better
approach in the second iteration (which will liberally change all
client code).
4- I extended gengtype to understand templated types. These changes
are not as ugly as I thought they would be. Gengtype has some
hardwired knowledge of VEC_*, which I renamed to vec_t. I'm not
even sure why gengtype needs to care about vec_t in this way, but I
was looking for minimal changes, so I just did it.
The other change is more generic. It allows gengtype to deal with
templated types. There is a new function (filter_type_name) that
recognizes C++ special characters '<', '>' and ':'. It turns them
into '_'. This way, gengtype can generate a valid identifier for
the pre-processor. It only does this in contexts where it needs a
pre-processor identifier. For everything else, it emits the type
directly. So, the functions emitted in gt-*.h files have proper
template type references.
Properties of this patch:
The performance and memory numbers I collected here were done by
bootstrapping the branch before and after my patch with all
languages enabled (including Ada and Go).
I collected time and memory reports by forcing the switches
-ftime-report and -fmem-report to be on by default, and to emit
their output to a separate file (otherwise the bootstrap fails
when some configure checks get confused by the extraneous stderr
output). This produced 2.9Gb of output over 12,944 timings
files.
1- There is much less code in vec.[ch] (21% fewer lines).
Functions are no longer replicated 2 or 3 times.
2- Debugging VEC_* routines is simpler. Failures in GDB go to
the specific VEC_* function instance, instead of the DEF_VEC_*
macro.
3- The new implementation is faster. Individual compiles are
generally 2.0 to 2.5% faster (wall time). This translates into
a bootstrap speedup of 1-2% (wall time reduction of about a minute
on my desktop).
The reason for this speedup is that various VEC_ routines now
return a reference to the element, which means that for vec_t<T>
there is one less memory indirection to perform.
4- Minimal changes to binary code size. The *1 binaries are about
0.07% bigger.
5- Reduced memory consumption by 4% on average (as measured by -fmem-report).
I averaged the 'Total Allocated:' field from -fmem-report from
all the compile
There are fewer macros expanded (-23%) and fewer
trees generated (the numbers below are averages over the
12,944 compilations):
Before After (%)
decls 9,491 9,240 - 2.6%
types 2,958 2,827 - 4.4%
blocks 525 460 -12.4%
stmts 1,123 1,043 - 7.1%
refs 4,369 3,926 -10.1%
exprs 15,236 14,283 - 6.2%
constants 1,888 1,871 - 0.9%
identifiers 7,285 7,197 - 1.2%
vecs 1,786 1,786 0%
binfos 113 109 - 3.5%
ssa names 2,240 2,240 0%
constructors 245 245 0%
random kinds 13,338 12,849 - 3.7%
lang_decl kinds 2,816 2,640 - 6.2%
lang_type kinds 110 106 - 3.6%
omp clauses 0 0 0%
Next step:
Before I consider moving this patch over to trunk, I would like to
generate a second patch that will:
1- Move all the free functions VEC_* into vec_t<T>. This will
simplify the call sites quite a bit. Mainly, it will remove the
unnecessary arguments T and A that are now always specified in
every call.
2- Change VEC_index into operator[].
3- Change VEC_replace(...) to assignments using operator[].
One thing these changes will do, however, is lose the VEC_CHECK_*
expansions that add the __FILE__, __LINE__ and __FUNCTION__ arguments
to the VEC_*() functions.
To deal with this loss, we could unwind the call stack a few levels on
ICEs. In fact, I think this could be a good thing to add to ICEs in
general. Showing some functions up the stack seems more useful than
just showing a single point.
OK for cxx-conversion branch?
2012-05-22 Diego Novillo <dnovillo@google.com>
Re-implement VEC in C++.
* vec.c (vec_heap_free): Convert into a template function.
(vec_gc_o_reserve_1): Make extern.
(vec_gc_p_reserve): Remove.
(vec_gc_p_reserve_exact): Remove.
(vec_gc_o_reserve): Remove.
(vec_gc_o_reserve_exact): Remove.
(vec_heap_o_reserve_1): Make extern.
(vec_heap_p_reserve): Remove.
(vec_heap_p_reserve_exact): Remove.
(vec_heap_o_reserve): Remove.
(vec_heap_o_reserve_exact): Remove.
(vec_stack_p_reserve): Remove.
(vec_stack_p_reserve_exact): Remove.
* vec.h (VEC_CHECK_INFO, VEC_CHECK_DECL, VEC_CHECK_PASS,
VEC_ASSERT, VEC_ASSERT_FAIL, vec_assert_fail): Move earlier
in the file.
(VEC): Define to vec_t<T>.
(vec_allocation_t): Define.
(struct vec_prefix): Move earlier in the file.
(vec_t<T>): New template.
(DEF_VEC_I, DEF_VECL_ALLOC_I, DEF_VEC_P, DEF_VEC_ALLOC_P,
DEF_VEC_O, DEF_VEC_ALLOC_P, DEF_VEC_O, DEF_VEC_ALLOC_O,
DEF_VEC_ALLOC_P_STACK, DEF_VEC_ALLOC_O_STACK,
DEF_VEC_ALLOC_I_STACK): Expand to 'struct vec_swallow_trailing_semi'.
(vec_stack_p_reserve): Remove.
(vec_stack_p_reserve_exact): Remove.
(vec_stack_p_reserve_exact_1): Remove.
(vec_stack_o_reserve): Remove.
(vec_stack_o_reserve_exact): Remove.
(vec_stack_free): Re-write as a template function.
(vec_reserve): New template function.
(vec_reserve_exact): New template function.
(vec_heap_free): New template function if GATHER_STATISTICS is
defined. Otherwise, macro that expands to free().
(VEC_length_1): New template function.
(VEC_length): Call it.
(VEC_empty_1): New template function.
(VEC_empty): Call it.
(VEC_address_1): New template function.
(VEC_address): Call it.
(VEC_last_1): New template function.
(VEC_last): Call it. Change return type to T&.
Change all users that used VEC_Os.
(VEC_index_1): New template function.
(VEC_index): Call it. Return a T& instead of a T*.
Update all callers that were using VEC_O before.
(VEC_iterate_1): New template function.
(VEC_iterate): Call it.
(VEC_embedded_size_1): New template function.
(VEC_embedded_size): Call it.
(VEC_embedded_init_1): New template function.
(VEC_embedded_init): Call it.
(VEC_alloc_1): New template function.
(VEC_alloc): Call it. If A is 'stack', call XALLOCAVAR to
do the allocation.
(VEC_free_1): New template function.
(VEC_free): Call it.
(VEC_copy_1): New template function.
(VEC_copy): Call it.
(VEC_space_1): New template function
(VEC_space): Call it.
(VEC_reserve_1): New template function.
(VEC_reserve): Call it.
(VEC_reserve_exact_1): New template function.
(VEC_reserve_exact): Call it.
(VEC_splice_1): New template function.
(VEC_splice): Call it.
(VEC_safe_splice_1): New template function.
(VEC_safe_splice): Call it.
(VEC_quick_push_1): New template function. Create two overloads, one
accepting T, the other accepting T *. Update all callers
where T and T * are ambiguous.
(VEC_quick_push): Call it.
(VEC_safe_push_1): New template function. Create two overloads, one
accepting T, the other accepting T *. Update all callers
where T and T * are ambiguous.
(VEC_safe_push): Call it.
(VEC_pop_1): New template function.
(VEC_pop): Call it.
(VEC_truncate_1): New template function.
(VEC_truncate): Call it.
(VEC_safe_grow_1): New template function.
(VEC_safe_grow): Call it.
(VEC_safe_grow_cleared_1): New template function.
(VEC_safe_grow_cleared): Call it.
(VEC_replace_1): New template function.
(VEC_replace): Call it. Always accept T instead of T*.
Update all callers that used VEC_Os.
(VEC_quick_insert_1): New template function.
(VEC_quick_insert): Call it.
(VEC_safe_insert_1): New template function.
(VEC_safe_insert): Call it.
(VEC_ordered_remove_1): New template function.
(VEC_ordered_remove): Call it.
(VEC_unordered_remove_1): New template function.
(VEC_unordered_remove): Call it.
(VEC_block_remove_1): New template function.
(VEC_block_remove): Call it.
(VEC_lower_bound_1): New template function.
(VEC_lower_bound): Call it.
(VEC_OP): Remove.
(DEF_VEC_FUNC_P): Remove.
(DEF_VEC_ALLOC_FUNC_P): Remove.
(DEF_VEC_NONALLOC_FUNCS_P): Remove.
(DEF_VEC_FUNC_O): Remove.
(DEF_VEC_ALLOC_FUNC_O): Remove.
(DEF_VEC_NONALLOC_FUNCS_O): Remove.
(DEF_VEC_ALLOC_FUNC_I): Remove.
(DEF_VEC_NONALLOC_FUNCS_I): Remove.
(DEF_VEC_ALLOC_FUNC_P_STACK): Remove.
(DEF_VEC_ALLOC_FUNC_O_STACK): Remove.
(DEF_VEC_ALLOC_FUNC_I_STACK): Remove.
(vec_reserve_exact): New template function.
diff --git a/gcc/vec.c b/gcc/vec.c
index 783a3cf..ba81e35 100644
--- a/gcc/vec.c
+++ b/gcc/vec.c
@@ -1,7 +1,8 @@
/* Vector API for GNU compiler.
- Copyright (C) 2004, 2005, 2006, 2007, 2008, 2010
+ Copyright (C) 2004, 2005, 2006, 2007, 2008, 2010, 2011, 2012
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.
@@ -215,7 +216,7 @@ calculate_allocation (const struct vec_prefix *pfx, int
reserve, bool exact)
trailing array is at VEC_OFFSET offset and consists of ELT_SIZE
sized elements. */
-static void *
+void *
vec_gc_o_reserve_1 (void *vec, int reserve, size_t vec_offset, size_t
elt_size,
bool exact MEM_STAT_DECL)
{
@@ -248,61 +249,10 @@ vec_gc_o_reserve_1 (void *vec, int reserve, size_t
vec_offset, size_t elt_size,
return vec;
}
-/* Ensure there are at least RESERVE free slots in VEC, growing
- exponentially. If RESERVE < 0 grow exactly, else grow
- exponentially. As a special case, if VEC is NULL, and RESERVE is
- 0, no vector will be created. */
-
-void *
-vec_gc_p_reserve (void *vec, int reserve MEM_STAT_DECL)
-{
- return vec_gc_o_reserve_1 (vec, reserve,
- sizeof (struct vec_prefix),
- sizeof (void *), false
- PASS_MEM_STAT);
-}
-
-/* Ensure there are at least RESERVE free slots in VEC, growing
- exactly. If RESERVE < 0 grow exactly, else grow exponentially. As
- a special case, if VEC is NULL, and RESERVE is 0, no vector will be
- created. */
-
-void *
-vec_gc_p_reserve_exact (void *vec, int reserve MEM_STAT_DECL)
-{
- return vec_gc_o_reserve_1 (vec, reserve,
- sizeof (struct vec_prefix),
- sizeof (void *), true
- PASS_MEM_STAT);
-}
-
-/* As for vec_gc_p_reserve, but for object vectors. The vector's
- trailing array is at VEC_OFFSET offset and consists of ELT_SIZE
- sized elements. */
-
-void *
-vec_gc_o_reserve (void *vec, int reserve, size_t vec_offset, size_t elt_size
- MEM_STAT_DECL)
-{
- return vec_gc_o_reserve_1 (vec, reserve, vec_offset, elt_size, false
- PASS_MEM_STAT);
-}
-
-/* As for vec_gc_p_reserve_exact, but for object vectors. The
- vector's trailing array is at VEC_OFFSET offset and consists of
- ELT_SIZE sized elements. */
-
-void *
-vec_gc_o_reserve_exact (void *vec, int reserve, size_t vec_offset,
- size_t elt_size MEM_STAT_DECL)
-{
- return vec_gc_o_reserve_1 (vec, reserve, vec_offset, elt_size, true
- PASS_MEM_STAT);
-}
/* As for vec_gc_o_reserve_1, but for heap allocated vectors. */
-static void *
+void *
vec_heap_o_reserve_1 (void *vec, int reserve, size_t vec_offset,
size_t elt_size, bool exact MEM_STAT_DECL)
{
@@ -334,47 +284,6 @@ vec_heap_o_reserve_1 (void *vec, int reserve, size_t
vec_offset,
return vec;
}
-/* As for vec_gc_p_reserve, but for heap allocated vectors. */
-
-void *
-vec_heap_p_reserve (void *vec, int reserve MEM_STAT_DECL)
-{
- return vec_heap_o_reserve_1 (vec, reserve,
- sizeof (struct vec_prefix),
- sizeof (void *), false
- PASS_MEM_STAT);
-}
-
-/* As for vec_gc_p_reserve_exact, but for heap allocated vectors. */
-
-void *
-vec_heap_p_reserve_exact (void *vec, int reserve MEM_STAT_DECL)
-{
- return vec_heap_o_reserve_1 (vec, reserve,
- sizeof (struct vec_prefix),
- sizeof (void *), true
- PASS_MEM_STAT);
-}
-
-/* As for vec_gc_o_reserve, but for heap allocated vectors. */
-
-void *
-vec_heap_o_reserve (void *vec, int reserve, size_t vec_offset, size_t elt_size
- MEM_STAT_DECL)
-{
- return vec_heap_o_reserve_1 (vec, reserve, vec_offset, elt_size, false
- PASS_MEM_STAT);
-}
-
-/* As for vec_gc_o_reserve_exact, but for heap allocated vectors. */
-
-void *
-vec_heap_o_reserve_exact (void *vec, int reserve, size_t vec_offset,
- size_t elt_size MEM_STAT_DECL)
-{
- return vec_heap_o_reserve_1 (vec, reserve, vec_offset, elt_size, true
- PASS_MEM_STAT);
-}
/* Stack vectors are a little different. VEC_alloc turns into a call
to vec_stack_p_reserve_exact1 and passes in space allocated via a
@@ -456,28 +365,6 @@ vec_stack_o_reserve_1 (void *vec, int reserve, size_t
vec_offset,
/* Grow a vector allocated on the stack. */
void *
-vec_stack_p_reserve (void *vec, int reserve MEM_STAT_DECL)
-{
- return vec_stack_o_reserve_1 (vec, reserve,
- sizeof (struct vec_prefix),
- sizeof (void *), false
- PASS_MEM_STAT);
-}
-
-/* Exact version of vec_stack_p_reserve. */
-
-void *
-vec_stack_p_reserve_exact (void *vec, int reserve MEM_STAT_DECL)
-{
- return vec_stack_o_reserve_1 (vec, reserve,
- sizeof (struct vec_prefix),
- sizeof (void *), true
- PASS_MEM_STAT);
-}
-
-/* Like vec_stack_p_reserve, but for objects. */
-
-void *
vec_stack_o_reserve (void *vec, int reserve, size_t vec_offset,
size_t elt_size MEM_STAT_DECL)
{
@@ -485,7 +372,7 @@ vec_stack_o_reserve (void *vec, int reserve, size_t
vec_offset,
PASS_MEM_STAT);
}
-/* Like vec_stack_p_reserve_exact, but for objects. */
+/* Exact version of vec_stack_o_reserve. */
void *
vec_stack_o_reserve_exact (void *vec, int reserve, size_t vec_offset,
diff --git a/gcc/vec.h b/gcc/vec.h
index d477958..cc7e819 100644
--- a/gcc/vec.h
+++ b/gcc/vec.h
@@ -1,7 +1,8 @@
/* Vector API for GNU compiler.
- Copyright (C) 2004, 2005, 2007, 2008, 2009, 2010
+ Copyright (C) 2004, 2005, 2007, 2008, 2009, 2010, 2011, 2012
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.
@@ -133,6 +134,86 @@ along with GCC; see the file COPYING3. If not see
*/
+#if ENABLE_CHECKING
+#define VEC_CHECK_INFO ,__FILE__,__LINE__,__FUNCTION__
+#define VEC_CHECK_DECL ,const char *file_,unsigned line_,const char *function_
+#define VEC_CHECK_PASS ,file_,line_,function_
+
+#define VEC_ASSERT(EXPR,OP,T,A) \
+ (void)((EXPR) ? 0 : (VEC_ASSERT_FAIL(OP,VEC(T,A)), 0))
+
+extern void vec_assert_fail (const char *, const char * VEC_CHECK_DECL)
+ ATTRIBUTE_NORETURN;
+#define VEC_ASSERT_FAIL(OP,VEC) vec_assert_fail (OP,#VEC VEC_CHECK_PASS)
+#else
+#define VEC_CHECK_INFO
+#define VEC_CHECK_DECL
+#define VEC_CHECK_PASS
+#define VEC_ASSERT(EXPR,OP,T,A) (void)(EXPR)
+#endif
+
+#define VEC(T,A) vec_t<T>
+
+enum vec_allocation_t { heap, gc, stack };
+
+struct GTY(()) vec_prefix
+{
+ unsigned num;
+ unsigned alloc;
+};
+
+/* Vector type, user visible. */
+template<typename T>
+struct GTY(()) vec_t
+{
+ vec_prefix prefix;
+ T GTY((length ("%h.prefix.num"))) vec[1];
+};
+
+/* FIXME cxx-conversion. Remove these definitions and update all
+ calling sites. */
+/* Vector of integer-like object. */
+#define DEF_VEC_I(T) struct vec_swallow_trailing_semi
+#define DEF_VEC_ALLOC_I(T,A) struct vec_swallow_trailing_semi
+
+/* Vector of pointer to object. */
+#define DEF_VEC_P(T) struct vec_swallow_trailing_semi
+#define DEF_VEC_ALLOC_P(T,A) struct vec_swallow_trailing_semi
+
+/* Vector of object. */
+#define DEF_VEC_O(T) struct vec_swallow_trailing_semi
+#define DEF_VEC_ALLOC_O(T,A) struct vec_swallow_trailing_semi
+
+/* Vectors on the stack. */
+#define DEF_VEC_ALLOC_P_STACK(T) struct vec_swallow_trailing_semi
+#define DEF_VEC_ALLOC_O_STACK(T) struct vec_swallow_trailing_semi
+#define DEF_VEC_ALLOC_I_STACK(T) struct vec_swallow_trailing_semi
+
+
+/* Support functions for stack vectors. */
+extern void *vec_stack_p_reserve_exact_1 (int, void *);
+extern void *vec_stack_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL);
+extern void *vec_stack_o_reserve_exact (void *, int, size_t, size_t
+ MEM_STAT_DECL);
+extern void vec_stack_free (void *);
+
+/* Reallocate an array of elements with prefix. */
+template<typename T, enum vec_allocation_t A>
+extern vec_t<T> *vec_reserve (vec_t<T> *, int MEM_STAT_DECL);
+
+template<typename T, enum vec_allocation_t A>
+extern vec_t<T> *vec_reserve_exact (vec_t<T> *, int MEM_STAT_DECL);
+
+extern void dump_vec_loc_statistics (void);
+extern void ggc_free (void *);
+#ifdef GATHER_STATISTICS
+void vec_heap_free (void *);
+#else
+/* Avoid problems with frontends that #define free(x). */
+#define vec_heap_free(V) (free) (V)
+#endif
+
+
/* Macros to invoke API calls. A single macro works for both pointer
and object vectors, but the argument and return types might well be
different. In each macro, T is the typedef of the vector elements,
@@ -147,7 +228,14 @@ along with GCC; see the file COPYING3. If not see
Return the number of active elements in V. V can be NULL, in which
case zero is returned. */
-#define VEC_length(T,V) (VEC_OP(T,base,length)(VEC_BASE(V)))
+#define VEC_length(T,V) (VEC_length_1<T> (V))
+
+template<typename T>
+static inline unsigned
+VEC_length_1 (const vec_t<T> *vec_)
+{
+ return vec_ ? vec_->prefix.num : 0;
+}
/* Check if vector is empty
@@ -155,7 +243,30 @@ along with GCC; see the file COPYING3. If not see
Return nonzero if V is an empty vector (or V is NULL), zero otherwise. */
-#define VEC_empty(T,V) (VEC_length (T,V) == 0)
+#define VEC_empty(T,V) (VEC_empty_1<T> (V))
+
+template<typename T>
+static inline bool
+VEC_empty_1 (const vec_t<T> *vec_)
+{
+ return VEC_length (T, vec_) == 0;
+}
+
+
+/* Get the address of the array of elements
+ T *VEC_T_address (VEC(T) v)
+
+ If you need to directly manipulate the array (for instance, you
+ want to feed it to qsort), use this accessor. */
+
+#define VEC_address(T,V) (VEC_address_1<T> (V))
+
+template<typename T>
+static inline T *
+VEC_address_1 (vec_t<T> *vec_)
+{
+ return vec_ ? vec_->vec : 0;
+}
/* Get the final element of the vector.
@@ -165,16 +276,42 @@ along with GCC; see the file COPYING3. If not see
Return the final element. V must not be empty. */
-#define VEC_last(T,V) (VEC_OP(T,base,last)(VEC_BASE(V) VEC_CHECK_INFO))
+#define VEC_last(T,V) (VEC_last_1<T> (V VEC_CHECK_INFO))
+
+template<typename T>
+static inline T&
+VEC_last_1 (vec_t<T> *vec_ VEC_CHECK_DECL)
+{
+ VEC_ASSERT (vec_ && vec_->prefix.num, "last", T, base);
+ return vec_->vec[vec_->prefix.num - 1];
+}
+
/* Index into vector
T VEC_T_index(VEC(T) *v, unsigned ix); // Integer
T VEC_T_index(VEC(T) *v, unsigned ix); // Pointer
T *VEC_T_index(VEC(T) *v, unsigned ix); // Object
- Return the IX'th element. If IX must be in the domain of V. */
+ Return the IX'th element. IX must be in the domain of V. */
+
+#define VEC_index(T,V,I) (VEC_index_1<T> (V, I VEC_CHECK_INFO))
+
+template<typename T>
+static inline T&
+VEC_index_1 (vec_t<T> *vec_, unsigned ix_ VEC_CHECK_DECL)
+{
+ VEC_ASSERT (vec_ && ix_ < vec_->prefix.num, "index", T, base);
+ return vec_->vec[ix_];
+}
+
+template<typename T>
+static inline const T&
+VEC_index_1 (const vec_t<T> *vec_, unsigned ix_ VEC_CHECK_DECL)
+{
+ VEC_ASSERT (vec_ && ix_ < vec_->prefix.num, "index", T, base);
+ return vec_->vec[ix_];
+}
-#define VEC_index(T,V,I) (VEC_OP(T,base,index)(VEC_BASE(V),I VEC_CHECK_INFO))
/* Iterate over vector
int VEC_T_iterate(VEC(T) *v, unsigned ix, T &ptr); // Integer
@@ -188,7 +325,39 @@ along with GCC; see the file COPYING3. If not see
for (ix = 0; VEC_iterate(T,v,ix,ptr); ix++)
continue; */
-#define VEC_iterate(T,V,I,P) (VEC_OP(T,base,iterate)(VEC_BASE(V),I,&(P)))
+#define VEC_iterate(T,V,I,P) (VEC_iterate_1<T> (V, I, &(P)))
+
+template<typename T>
+static inline bool
+VEC_iterate_1 (const vec_t<T> *vec_, unsigned ix_, T *ptr)
+{
+ if (vec_ && ix_ < vec_->prefix.num)
+ {
+ *ptr = vec_->vec[ix_];
+ return true;
+ }
+ else
+ {
+ *ptr = 0;
+ return false;
+ }
+}
+
+template<typename T>
+static inline bool
+VEC_iterate_1 (vec_t<T> *vec_, unsigned ix_, T **ptr)
+{
+ if (vec_ && ix_ < vec_->prefix.num)
+ {
+ *ptr = &vec_->vec[ix_];
+ return true;
+ }
+ else
+ {
+ *ptr = 0;
+ return false;
+ }
+}
/* Convenience macro for forward iteration. */
@@ -207,31 +376,99 @@ along with GCC; see the file COPYING3. If not see
VEC_iterate (T, (V), (I), (P)); \
(I)--)
+
+/* Use these to determine the required size and initialization of a
+ vector embedded within another structure (as the final member).
+
+ size_t VEC_T_embedded_size(int reserve);
+ void VEC_T_embedded_init(VEC(T) *v, int reserve);
+
+ These allow the caller to perform the memory allocation. */
+
+#define VEC_embedded_size(T,N) (VEC_embedded_size_1<T> (N))
+
+template<typename T>
+static inline size_t
+VEC_embedded_size_1 (int alloc_)
+{
+ return offsetof (vec_t<T>, vec) + alloc_ * sizeof (T);
+}
+
+#define VEC_embedded_init(T,O,N) (VEC_embedded_init_1<T> (O, N))
+
+template<typename T>
+static inline void
+VEC_embedded_init_1 (vec_t<T> *vec_, int alloc_)
+{
+ vec_->prefix.num = 0;
+ vec_->prefix.alloc = alloc_;
+}
+
+
/* Allocate new vector.
VEC(T,A) *VEC_T_A_alloc(int reserve);
Allocate a new vector with space for RESERVE objects. If RESERVE
- is zero, NO vector is created. */
+ is zero, NO vector is created.
+
+ 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.
+
+ 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 VEC(TYPE,stack) vector from the function
+ which allocated it. */
+
+#define VEC_alloc(T,A,N) \
+ ((A == stack) \
+ ? VEC_alloc_1 (N, \
+ XALLOCAVAR (vec_t<T>, \
+ VEC_embedded_size_1<T> (N))) \
+ : VEC_alloc_1<T, A> (N MEM_STAT_INFO))
+
+template<typename T, enum vec_allocation_t A>
+static inline vec_t<T> *
+VEC_alloc_1 (int alloc_ MEM_STAT_DECL)
+{
+ return vec_reserve_exact<T, A> (NULL, alloc_ PASS_MEM_STAT);
+}
+
+template<typename T>
+static inline vec_t<T> *
+VEC_alloc_1 (int alloc_, vec_t<T> *space)
+{
+ return (vec_t<T> *) vec_stack_p_reserve_exact_1 (alloc_, space);
+}
-#define VEC_alloc(T,A,N) (VEC_OP(T,A,alloc)(N MEM_STAT_INFO))
/* Free a vector.
void VEC_T_A_free(VEC(T,A) *&);
Free a vector and set it to NULL. */
-#define VEC_free(T,A,V) (VEC_OP(T,A,free)(&V))
-
-/* Use these to determine the required size and initialization of a
- vector embedded within another structure (as the final member).
+#define VEC_free(T,A,V) (VEC_free_1<T, A> (&V))
- size_t VEC_T_embedded_size(int reserve);
- void VEC_T_embedded_init(VEC(T) *v, int reserve);
-
- These allow the caller to perform the memory allocation. */
+template<typename T, enum vec_allocation_t A>
+static inline void
+VEC_free_1 (vec_t<T> **vec_)
+{
+ if (*vec_)
+ {
+ if (A == heap)
+ vec_heap_free (*vec_);
+ else if (A == gc)
+ ggc_free (*vec_);
+ else if (A == stack)
+ vec_stack_free (*vec_);
+ }
+ *vec_ = NULL;
+}
-#define VEC_embedded_size(T,N) (VEC_OP(T,base,embedded_size)(N))
-#define VEC_embedded_init(T,O,N) (VEC_OP(T,base,embedded_init)(VEC_BASE(O),N))
/* Copy a vector.
VEC(T,A) *VEC_T_A_copy(VEC(T) *);
@@ -239,7 +476,24 @@ along with GCC; see the file COPYING3. If not see
Copy the live elements of a vector into a new vector. The new and
old vectors need not be allocated by the same mechanism. */
-#define VEC_copy(T,A,V) (VEC_OP(T,A,copy)(VEC_BASE(V) MEM_STAT_INFO))
+#define VEC_copy(T,A,V) (VEC_copy_1<T, A> (V MEM_STAT_INFO))
+
+template<typename T, enum vec_allocation_t A>
+static inline vec_t<T> *
+VEC_copy_1 (vec_t<T> *vec_ MEM_STAT_DECL)
+{
+ size_t len_ = vec_ ? vec_->prefix.num : 0;
+ vec_t<T> *new_vec_ = NULL;
+
+ if (len_)
+ {
+ new_vec_ = vec_reserve_exact<T, A> (NULL, len_ PASS_MEM_STAT);
+ new_vec_->prefix.num = len_;
+ memcpy (new_vec_->vec, vec_->vec, sizeof (T) * len_);
+ }
+ return new_vec_;
+}
+
/* Determine if a vector has additional capacity.
@@ -251,8 +505,18 @@ along with GCC; see the file COPYING3. If not see
nonzero in exactly the same circumstances that VEC_T_reserve
will. */
-#define VEC_space(T,V,R) \
- (VEC_OP(T,base,space)(VEC_BASE(V),R VEC_CHECK_INFO))
+#define VEC_space(T,V,R) (VEC_space_1<T> (V, R VEC_CHECK_INFO))
+
+template<typename T>
+static inline int
+VEC_space_1 (vec_t<T> *vec_, int alloc_ VEC_CHECK_DECL)
+{
+ VEC_ASSERT (alloc_ >= 0, "space", T, base);
+ return vec_
+ ? vec_->prefix.alloc - vec_->prefix.num >= (unsigned)alloc_
+ : !alloc_;
+}
+
/* Reserve space.
int VEC_T_A_reserve(VEC(T,A) *&v, int reserve);
@@ -263,7 +527,20 @@ along with GCC; see the file COPYING3. If not see
occurred. */
#define VEC_reserve(T,A,V,R) \
- (VEC_OP(T,A,reserve)(&(V),R VEC_CHECK_INFO MEM_STAT_INFO))
+ (VEC_reserve_1<T, A> (&(V), (int)(R) VEC_CHECK_INFO MEM_STAT_INFO))
+
+template<typename T, enum vec_allocation_t A>
+static inline int
+VEC_reserve_1 (vec_t<T> **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL)
+{
+ int extend = !VEC_space_1 (*vec_, alloc_ VEC_CHECK_PASS);
+
+ if (extend)
+ *vec_ = vec_reserve<T, A> (*vec_, alloc_ PASS_MEM_STAT);
+
+ return extend;
+}
+
/* Reserve space exactly.
int VEC_T_A_reserve_exact(VEC(T,A) *&v, int reserve);
@@ -274,7 +551,20 @@ along with GCC; see the file COPYING3. If not see
occurred. */
#define VEC_reserve_exact(T,A,V,R) \
- (VEC_OP(T,A,reserve_exact)(&(V),R VEC_CHECK_INFO MEM_STAT_INFO))
+ (VEC_reserve_exact_1<T, A> (&(V), R VEC_CHECK_INFO MEM_STAT_INFO))
+
+template<typename T, enum vec_allocation_t A>
+static inline int
+VEC_reserve_exact_1 (vec_t<T> **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL)
+{
+ int extend = !VEC_space_1 (*vec_, alloc_ VEC_CHECK_PASS);
+
+ if (extend)
+ *vec_ = vec_reserve_exact<T, A> (*vec_, alloc_ PASS_MEM_STAT);
+
+ return extend;
+}
+
/* Copy elements with no reallocation
void VEC_T_splice (VEC(T) *dst, VEC(T) *src); // Integer
@@ -286,8 +576,23 @@ along with GCC; see the file COPYING3. If not see
often will be. DST is assumed to have sufficient headroom
available. */
-#define VEC_splice(T,DST,SRC) \
- (VEC_OP(T,base,splice)(VEC_BASE(DST), VEC_BASE(SRC) VEC_CHECK_INFO))
+#define VEC_splice(T,DST,SRC) (VEC_splice_1<T> (DST, SRC VEC_CHECK_INFO))
+
+template<typename T>
+static inline void
+VEC_splice_1 (vec_t<T> *dst_, vec_t<T> *src_ VEC_CHECK_DECL)
+{
+ if (src_)
+ {
+ unsigned len_ = src_->prefix.num;
+ VEC_ASSERT (dst_->prefix.num + len_ <= dst_->prefix.alloc, "splice",
+ T, base);
+
+ memcpy (&dst_->vec[dst_->prefix.num], &src_->vec[0], len_ * sizeof (T));
+ dst_->prefix.num += len_;
+ }
+}
+
/* Copy elements with reallocation
void VEC_T_safe_splice (VEC(T,A) *&dst, VEC(T) *src); // Integer
@@ -300,7 +605,21 @@ along with GCC; see the file COPYING3. If not see
reallocated if needed. */
#define VEC_safe_splice(T,A,DST,SRC) \
- (VEC_OP(T,A,safe_splice)(&(DST), VEC_BASE(SRC) VEC_CHECK_INFO
MEM_STAT_INFO))
+ (VEC_safe_splice_1<T, A> (&(DST), SRC VEC_CHECK_INFO MEM_STAT_INFO))
+
+template<typename T, enum vec_allocation_t A>
+static inline void
+VEC_safe_splice_1 (vec_t<T> **dst_, vec_t<T> *src_ VEC_CHECK_DECL
MEM_STAT_DECL)
+{
+ if (src_)
+ {
+ VEC_reserve_exact_1<T, A> (dst_, src_->prefix.num
+ VEC_CHECK_PASS MEM_STAT_INFO);
+
+ VEC_splice_1 (*dst_, src_ VEC_CHECK_PASS);
+ }
+}
+
/* Push object with no reallocation
T *VEC_T_quick_push (VEC(T) *v, T obj); // Integer
@@ -312,8 +631,31 @@ along with GCC; see the file COPYING3. If not see
case NO initialization is performed. There must
be sufficient space in the vector. */
-#define VEC_quick_push(T,V,O) \
- (VEC_OP(T,base,quick_push)(VEC_BASE(V),O VEC_CHECK_INFO))
+#define VEC_quick_push(T,V,O) (VEC_quick_push_1<T> (V, O VEC_CHECK_INFO))
+
+template<typename T>
+static inline T &
+VEC_quick_push_1 (vec_t<T> *vec_, T obj_ VEC_CHECK_DECL)
+{
+ VEC_ASSERT (vec_->prefix.num < vec_->prefix.alloc, "push", T, base);
+ vec_->vec[vec_->prefix.num] = obj_;
+ T &val_ = vec_->vec[vec_->prefix.num];
+ vec_->prefix.num++;
+ return val_;
+}
+
+template<typename T>
+static inline T *
+VEC_quick_push_1 (vec_t<T> *vec_, const T *ptr_ VEC_CHECK_DECL)
+{
+ T *slot_;
+ VEC_ASSERT (vec_->prefix.num < vec_->prefix.alloc, "push", T, base);
+ slot_ = &vec_->vec[vec_->prefix.num++];
+ if (ptr_)
+ *slot_ = *ptr_;
+ return slot_;
+}
+
/* Push object with reallocation
T *VEC_T_A_safe_push (VEC(T,A) *&v, T obj); // Integer
@@ -325,7 +667,24 @@ along with GCC; see the file COPYING3. If not see
case NO initialization is performed. Reallocates V, if needed. */
#define VEC_safe_push(T,A,V,O) \
- (VEC_OP(T,A,safe_push)(&(V),O VEC_CHECK_INFO MEM_STAT_INFO))
+ (VEC_safe_push_1<T, A> (&(V), O VEC_CHECK_INFO MEM_STAT_INFO))
+
+template<typename T, enum vec_allocation_t A>
+static inline T &
+VEC_safe_push_1 (vec_t<T> **vec_, T obj_ VEC_CHECK_DECL MEM_STAT_DECL)
+{
+ VEC_reserve_1<T, A> (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT);
+ return VEC_quick_push_1 (*vec_, obj_ VEC_CHECK_PASS);
+}
+
+template<typename T, enum vec_allocation_t A>
+static inline T *
+VEC_safe_push_1 (vec_t<T> **vec_, const T *ptr_ VEC_CHECK_DECL MEM_STAT_DECL)
+{
+ VEC_reserve_1<T, A> (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT);
+ return VEC_quick_push_1 (*vec_, ptr_ VEC_CHECK_PASS);
+}
+
/* Pop element off end
T VEC_T_pop (VEC(T) *v); // Integer
@@ -335,7 +694,16 @@ along with GCC; see the file COPYING3. If not see
Pop the last element off the end. Returns the element popped, for
pointer vectors. */
-#define VEC_pop(T,V) (VEC_OP(T,base,pop)(VEC_BASE(V) VEC_CHECK_INFO))
+#define VEC_pop(T,V) (VEC_pop_1<T> (V VEC_CHECK_INFO))
+
+template<typename T>
+static inline T&
+VEC_pop_1 (vec_t<T> *vec_ VEC_CHECK_DECL)
+{
+ VEC_ASSERT (vec_->prefix.num, "pop", T, base);
+ return vec_->vec[--vec_->prefix.num];
+}
+
/* Truncate to specific length
void VEC_T_truncate (VEC(T) *v, unsigned len);
@@ -343,8 +711,18 @@ along with GCC; see the file COPYING3. If not see
Set the length as specified. The new length must be less than or
equal to the current length. This is an O(1) operation. */
-#define VEC_truncate(T,V,I) \
- (VEC_OP(T,base,truncate)(VEC_BASE(V),I VEC_CHECK_INFO))
+#define VEC_truncate(T,V,I) \
+ (VEC_truncate_1<T> (V, (unsigned)(I) VEC_CHECK_INFO))
+
+template<typename T>
+static inline void
+VEC_truncate_1 (vec_t<T> *vec_, unsigned size_ VEC_CHECK_DECL)
+{
+ VEC_ASSERT (vec_ ? vec_->prefix.num >= size_ : !size_, "truncate", T, base);
+ if (vec_)
+ vec_->prefix.num = size_;
+}
+
/* Grow to a specific length.
void VEC_T_A_safe_grow (VEC(T,A) *&v, int len);
@@ -354,7 +732,20 @@ along with GCC; see the file COPYING3. If not see
uninitialized. */
#define VEC_safe_grow(T,A,V,I) \
- (VEC_OP(T,A,safe_grow)(&(V),I VEC_CHECK_INFO MEM_STAT_INFO))
+ (VEC_safe_grow_1<T, A> (&(V), (int)(I) VEC_CHECK_INFO MEM_STAT_INFO))
+
+template<typename T, enum vec_allocation_t A>
+static inline void
+VEC_safe_grow_1 (vec_t<T> **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL)
+{
+ VEC_ASSERT (size_ >= 0 && VEC_length (T, *vec_) <= (unsigned)size_,
+ "grow", T, A);
+ VEC_reserve_exact_1<T, A> (vec_,
+ size_ - (int)(*vec_ ? (*vec_)->prefix.num : 0)
+ VEC_CHECK_PASS PASS_MEM_STAT);
+ (*vec_)->prefix.num = size_;
+}
+
/* Grow to a specific length.
void VEC_T_A_safe_grow_cleared (VEC(T,A) *&v, int len);
@@ -363,8 +754,21 @@ along with GCC; see the file COPYING3. If not see
long or longer than the current length. The new elements are
initialized to zero. */
-#define VEC_safe_grow_cleared(T,A,V,I) \
- (VEC_OP(T,A,safe_grow_cleared)(&(V),I VEC_CHECK_INFO MEM_STAT_INFO))
+#define VEC_safe_grow_cleared(T,A,V,I) \
+ (VEC_safe_grow_cleared_1<T,A> (&(V), (int)(I) \
+ VEC_CHECK_INFO MEM_STAT_INFO))
+
+template<typename T, enum vec_allocation_t A>
+static inline void
+VEC_safe_grow_cleared_1 (vec_t<T> **vec_, int size_ VEC_CHECK_DECL
+ MEM_STAT_DECL)
+{
+ int oldsize = VEC_length (T, *vec_);
+ VEC_safe_grow_1<T, A> (vec_, size_ VEC_CHECK_PASS PASS_MEM_STAT);
+ memset (&(VEC_address (T, *vec_)[oldsize]), 0,
+ sizeof (T) * (size_ - oldsize));
+}
+
/* Replace element
T VEC_T_replace (VEC(T) *v, unsigned ix, T val); // Integer
@@ -378,20 +782,57 @@ along with GCC; see the file COPYING3. If not see
performed. */
#define VEC_replace(T,V,I,O) \
- (VEC_OP(T,base,replace)(VEC_BASE(V),I,O VEC_CHECK_INFO))
+ (VEC_replace_1<T> (V, (unsigned)(I), O VEC_CHECK_INFO))
+
+template<typename T>
+static inline T&
+VEC_replace_1 (vec_t<T> *vec_, unsigned ix_, T obj_ VEC_CHECK_DECL)
+{
+ VEC_ASSERT (ix_ < vec_->prefix.num, "replace", T, base);
+ vec_->vec[ix_] = obj_;
+ return vec_->vec[ix_];
+}
+
/* Insert object with no reallocation
- T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Integer
- T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Pointer
- T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T *val); // Object
+ void VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Integer
+ void VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Pointer
+ void VEC_T_quick_insert (VEC(T) *v, unsigned ix, T *val); // Object
- Insert an element, VAL, at the IXth position of V. Return a pointer
- to the slot created. For vectors of object, the new value can be
- NULL, in which case no initialization of the inserted slot takes
- place. There must be sufficient space. */
+ Insert an element, VAL, at the IXth position of V. For vectors of
+ object, the new value can be NULL, in which case no initialization
+ of the inserted slot takes place. There must be sufficient space. */
#define VEC_quick_insert(T,V,I,O) \
- (VEC_OP(T,base,quick_insert)(VEC_BASE(V),I,O VEC_CHECK_INFO))
+ (VEC_quick_insert_1<T> (V,I,O VEC_CHECK_INFO))
+
+template<typename T>
+static inline void
+VEC_quick_insert_1 (vec_t<T> *vec_, unsigned ix_, T obj_ VEC_CHECK_DECL)
+{
+ T *slot_;
+
+ VEC_ASSERT (vec_->prefix.num < vec_->prefix.alloc, "insert", T, base);
+ VEC_ASSERT (ix_ <= vec_->prefix.num, "insert", T, base);
+ slot_ = &vec_->vec[ix_];
+ memmove (slot_ + 1, slot_, (vec_->prefix.num++ - ix_) * sizeof (T));
+ *slot_ = obj_;
+}
+
+template<typename T>
+static inline void
+VEC_quick_insert_1 (vec_t<T> *vec_, unsigned ix_, const T *ptr_
VEC_CHECK_DECL)
+{
+ T *slot_;
+
+ VEC_ASSERT (vec_->prefix.num < vec_->prefix.alloc, "insert", T, base);
+ VEC_ASSERT (ix_ <= vec_->prefix.num, "insert", T, base);
+ slot_ = &vec_->vec[ix_];
+ memmove (slot_ + 1, slot_, (vec_->prefix.num++ - ix_) * sizeof (T));
+ if (ptr_)
+ *slot_ = *ptr_;
+}
+
/* Insert object with reallocation
T *VEC_T_A_safe_insert (VEC(T,A) *&v, unsigned ix, T val); // Integer
@@ -404,31 +845,70 @@ along with GCC; see the file COPYING3. If not see
place. Reallocate V, if necessary. */
#define VEC_safe_insert(T,A,V,I,O) \
- (VEC_OP(T,A,safe_insert)(&(V),I,O VEC_CHECK_INFO MEM_STAT_INFO))
+ (VEC_safe_insert_1<T, A> (&(V),I,O VEC_CHECK_INFO MEM_STAT_INFO))
+
+template<typename T, enum vec_allocation_t A>
+static inline void
+VEC_safe_insert_1 (vec_t<T> **vec_, unsigned ix_, T obj_
+ VEC_CHECK_DECL MEM_STAT_DECL)
+{
+ VEC_reserve_1<T, A> (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT);
+ VEC_quick_insert_1 (*vec_, ix_, obj_ VEC_CHECK_PASS);
+}
+
+template<typename T, enum vec_allocation_t A>
+static inline void
+VEC_safe_insert_1 (vec_t<T> **vec_, unsigned ix_, T *ptr_
+ VEC_CHECK_DECL MEM_STAT_DECL)
+{
+ VEC_reserve_1<T, A> (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT);
+ VEC_quick_insert_1 (*vec_, ix_, ptr_ VEC_CHECK_PASS);
+}
+
+
/* Remove element retaining order
- T VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Integer
- T VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Pointer
+ void VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Integer
+ void VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Pointer
void VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Object
Remove an element from the IXth position of V. Ordering of
- remaining elements is preserved. For pointer vectors returns the
- removed object. This is an O(N) operation due to a memmove. */
+ remaining elements is preserved. This is an O(N) operation due to
+ a memmove. */
#define VEC_ordered_remove(T,V,I) \
- (VEC_OP(T,base,ordered_remove)(VEC_BASE(V),I VEC_CHECK_INFO))
+ (VEC_ordered_remove_1<T> (V,I VEC_CHECK_INFO))
+
+template<typename T>
+static inline void
+VEC_ordered_remove_1 (vec_t<T> *vec_, unsigned ix_ VEC_CHECK_DECL)
+{
+ T *slot_;
+ VEC_ASSERT (ix_ < vec_->prefix.num, "remove", T, base);
+ slot_ = &vec_->vec[ix_];
+ memmove (slot_, slot_ + 1, (--vec_->prefix.num - ix_) * sizeof (T));
+}
+
/* Remove element destroying order
- T VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Integer
- T VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Pointer
+ void VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Integer
+ void VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Pointer
void VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Object
- Remove an element from the IXth position of V. Ordering of
- remaining elements is destroyed. For pointer vectors returns the
- removed object. This is an O(1) operation. */
+ Remove an element from the IXth position of V. Ordering of
+ remaining elements is destroyed. This is an O(1) operation. */
#define VEC_unordered_remove(T,V,I) \
- (VEC_OP(T,base,unordered_remove)(VEC_BASE(V),I VEC_CHECK_INFO))
+ (VEC_unordered_remove_1<T> (V,I VEC_CHECK_INFO))
+
+template<typename T>
+static inline void
+VEC_unordered_remove_1 (vec_t<T> *vec_, unsigned ix_ VEC_CHECK_DECL)
+{
+ VEC_ASSERT (ix_ < vec_->prefix.num, "remove", T, base);
+ vec_->vec[ix_] = vec_->vec[--vec_->prefix.num];
+}
+
/* Remove a block of elements
void VEC_T_block_remove (VEC(T) *v, unsigned ix, unsigned len);
@@ -437,22 +917,27 @@ along with GCC; see the file COPYING3. If not see
This is an O(N) operation due to memmove. */
#define VEC_block_remove(T,V,I,L) \
- (VEC_OP(T,base,block_remove)(VEC_BASE(V),I,L VEC_CHECK_INFO))
+ (VEC_block_remove_1<T> (V, I, L VEC_CHECK_INFO))
-/* Get the address of the array of elements
- T *VEC_T_address (VEC(T) v)
-
- If you need to directly manipulate the array (for instance, you
- want to feed it to qsort), use this accessor. */
+template<typename T>
+static inline void
+VEC_block_remove_1 (vec_t<T> *vec_, unsigned ix_, unsigned len_
VEC_CHECK_DECL)
+{
+ T *slot_;
+ VEC_ASSERT (ix_ + len_ <= vec_->prefix.num, "block_remove", T, base);
+ slot_ = &vec_->vec[ix_];
+ vec_->prefix.num -= len_;
+ memmove (slot_, slot_ + len_, (vec_->prefix.num - ix_) * sizeof (T));
+}
-#define VEC_address(T,V) (VEC_OP(T,base,address)(VEC_BASE(V)))
/* Conveniently sort the contents of the vector with qsort.
void VEC_qsort (VEC(T) *v, int (*cmp_func)(const void *, const void *)) */
-#define VEC_qsort(T,V,CMP) qsort(VEC_address (T,V), VEC_length(T,V), \
+#define VEC_qsort(T,V,CMP) qsort(VEC_address (T, V), VEC_length (T, V), \
sizeof (T), CMP)
+
/* Find the first index in the vector not less than the object.
unsigned VEC_T_lower_bound (VEC(T) *v, const T val,
bool (*lessthan) (const T, const T)); //
Integer
@@ -465,944 +950,140 @@ along with GCC; see the file COPYING3. If not see
changing the ordering of V. LESSTHAN is a function that returns
true if the first argument is strictly less than the second. */
-#define VEC_lower_bound(T,V,O,LT) \
- (VEC_OP(T,base,lower_bound)(VEC_BASE(V),O,LT VEC_CHECK_INFO))
-
-/* Reallocate an array of elements with prefix. */
-extern void *vec_gc_p_reserve (void *, int MEM_STAT_DECL);
-extern void *vec_gc_p_reserve_exact (void *, int MEM_STAT_DECL);
-extern void *vec_gc_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL);
-extern void *vec_gc_o_reserve_exact (void *, int, size_t, size_t
- MEM_STAT_DECL);
-extern void ggc_free (void *);
-#define vec_gc_free(V) ggc_free (V)
-extern void *vec_heap_p_reserve (void *, int MEM_STAT_DECL);
-extern void *vec_heap_p_reserve_exact (void *, int MEM_STAT_DECL);
-extern void *vec_heap_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL);
-extern void *vec_heap_o_reserve_exact (void *, int, size_t, size_t
- MEM_STAT_DECL);
-extern void dump_vec_loc_statistics (void);
-#ifdef GATHER_STATISTICS
-void vec_heap_free (void *);
-#else
-/* Avoid problems with frontends that #define free(x). */
-#define vec_heap_free(V) (free) (V)
-#endif
-
-#if ENABLE_CHECKING
-#define VEC_CHECK_INFO ,__FILE__,__LINE__,__FUNCTION__
-#define VEC_CHECK_DECL ,const char *file_,unsigned line_,const char *function_
-#define VEC_CHECK_PASS ,file_,line_,function_
+#define VEC_lower_bound(T,V,O,LT) \
+ (VEC_lower_bound_1<T> (V, O, LT VEC_CHECK_INFO))
-#define VEC_ASSERT(EXPR,OP,T,A) \
- (void)((EXPR) ? 0 : (VEC_ASSERT_FAIL(OP,VEC(T,A)), 0))
-
-extern void vec_assert_fail (const char *, const char * VEC_CHECK_DECL)
- ATTRIBUTE_NORETURN;
-#define VEC_ASSERT_FAIL(OP,VEC) vec_assert_fail (OP,#VEC VEC_CHECK_PASS)
-#else
-#define VEC_CHECK_INFO
-#define VEC_CHECK_DECL
-#define VEC_CHECK_PASS
-#define VEC_ASSERT(EXPR,OP,T,A) (void)(EXPR)
-#endif
-
-/* Note: gengtype has hardwired knowledge of the expansions of the
- VEC, DEF_VEC_*, and DEF_VEC_ALLOC_* macros. If you change the
- expansions of these macros you may need to change gengtype too. */
-
-typedef struct GTY(()) vec_prefix
+template<typename T>
+static inline unsigned
+VEC_lower_bound_1 (vec_t<T> *vec_, T obj_,
+ bool (*lessthan_)(T, T) VEC_CHECK_DECL)
{
- unsigned num;
- unsigned alloc;
-} vec_prefix;
-
-#define VEC(T,A) VEC_##T##_##A
-#define VEC_OP(T,A,OP) VEC_##T##_##A##_##OP
-
-/* Base of vector type, not user visible. */
-#define VEC_T(T,B) \
-typedef struct VEC(T,B) \
-{ \
- struct vec_prefix prefix; \
- T vec[1]; \
-} VEC(T,B)
-
-#define VEC_T_GTY(T,B) \
-typedef struct GTY(()) VEC(T,B) \
-{ \
- struct vec_prefix prefix; \
- T GTY ((length ("%h.prefix.num"))) vec[1]; \
-} VEC(T,B)
-
-/* Derived vector type, user visible. */
-#define VEC_TA_GTY(T,B,A,GTY) \
-typedef struct GTY VEC(T,A) \
-{ \
- VEC(T,B) base; \
-} VEC(T,A)
-
-#define VEC_TA(T,B,A) \
-typedef struct VEC(T,A) \
-{ \
- VEC(T,B) base; \
-} VEC(T,A)
-
-/* Convert to base type. */
-#if GCC_VERSION >= 4000
-#define VEC_BASE(P) \
- ((offsetof (__typeof (*P), base) == 0 || (P)) ? &(P)->base : 0)
-#else
-#define VEC_BASE(P) ((P) ? &(P)->base : 0)
-#endif
-
-/* Vector of integer-like object. */
-#define DEF_VEC_I(T) \
-static inline void VEC_OP (T,must_be,integral_type) (void) \
-{ \
- (void)~(T)0; \
-} \
- \
-VEC_T(T,base); \
-VEC_TA(T,base,none); \
-DEF_VEC_FUNC_P(T) \
-struct vec_swallow_trailing_semi
-#define DEF_VEC_ALLOC_I(T,A) \
-VEC_TA(T,base,A); \
-DEF_VEC_ALLOC_FUNC_I(T,A) \
-DEF_VEC_NONALLOC_FUNCS_I(T,A) \
-struct vec_swallow_trailing_semi
-
-/* Vector of pointer to object. */
-#define DEF_VEC_P(T) \
-static inline void VEC_OP (T,must_be,pointer_type) (void) \
-{ \
- (void)((T)1 == (void *)1); \
-} \
- \
-VEC_T_GTY(T,base); \
-VEC_TA(T,base,none); \
-DEF_VEC_FUNC_P(T) \
-struct vec_swallow_trailing_semi
-#define DEF_VEC_ALLOC_P(T,A) \
-VEC_TA(T,base,A); \
-DEF_VEC_ALLOC_FUNC_P(T,A) \
-DEF_VEC_NONALLOC_FUNCS_P(T,A) \
-struct vec_swallow_trailing_semi
-
-#define DEF_VEC_FUNC_P(T) \
-static inline unsigned VEC_OP (T,base,length) (const VEC(T,base) *vec_) \
-{ \
- return vec_ ? vec_->prefix.num : 0; \
-} \
- \
-static inline T VEC_OP (T,base,last) \
- (const VEC(T,base) *vec_ VEC_CHECK_DECL) \
-{ \
- VEC_ASSERT (vec_ && vec_->prefix.num, "last", T, base); \
- \
- return vec_->vec[vec_->prefix.num - 1]; \
-} \
- \
-static inline T VEC_OP (T,base,index) \
- (const VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \
-{ \
- VEC_ASSERT (vec_ && ix_ < vec_->prefix.num, "index", T, base); \
- \
- return vec_->vec[ix_]; \
-} \
- \
-static inline int VEC_OP (T,base,iterate) \
- (const VEC(T,base) *vec_, unsigned ix_, T *ptr) \
-{ \
- if (vec_ && ix_ < vec_->prefix.num) \
- { \
- *ptr = vec_->vec[ix_]; \
- return 1; \
- } \
- else \
- { \
- *ptr = (T) 0; \
- return 0; \
- } \
-} \
- \
-static inline size_t VEC_OP (T,base,embedded_size) \
- (int alloc_) \
-{ \
- return offsetof (VEC(T,base),vec) + alloc_ * sizeof(T); \
-} \
- \
-static inline void VEC_OP (T,base,embedded_init) \
- (VEC(T,base) *vec_, int alloc_) \
-{ \
- vec_->prefix.num = 0; \
- vec_->prefix.alloc = alloc_; \
-} \
- \
-static inline int VEC_OP (T,base,space) \
- (VEC(T,base) *vec_, int alloc_ VEC_CHECK_DECL) \
-{ \
- VEC_ASSERT (alloc_ >= 0, "space", T, base); \
- return vec_ ? vec_->prefix.alloc - vec_->prefix.num >= (unsigned)alloc_ :
!alloc_; \
-} \
- \
-static inline void VEC_OP(T,base,splice) \
- (VEC(T,base) *dst_, VEC(T,base) *src_ VEC_CHECK_DECL) \
-{ \
- if (src_) \
- { \
- unsigned len_ = src_->prefix.num; \
- VEC_ASSERT (dst_->prefix.num + len_ <= dst_->prefix.alloc, "splice", T,
base); \
- \
- memcpy (&dst_->vec[dst_->prefix.num], &src_->vec[0], len_ * sizeof (T));
\
- dst_->prefix.num += len_; \
- } \
-} \
- \
-static inline T *VEC_OP (T,base,quick_push) \
- (VEC(T,base) *vec_, T obj_ VEC_CHECK_DECL) \
-{ \
- T *slot_; \
- \
- VEC_ASSERT (vec_->prefix.num < vec_->prefix.alloc, "push", T, base); \
- slot_ = &vec_->vec[vec_->prefix.num++]; \
- *slot_ = obj_; \
- \
- return slot_; \
-} \
- \
-static inline T VEC_OP (T,base,pop) (VEC(T,base) *vec_ VEC_CHECK_DECL) \
-{ \
- T obj_; \
- \
- VEC_ASSERT (vec_->prefix.num, "pop", T, base); \
- obj_ = vec_->vec[--vec_->prefix.num]; \
- \
- return obj_; \
-} \
- \
-static inline void VEC_OP (T,base,truncate) \
- (VEC(T,base) *vec_, unsigned size_ VEC_CHECK_DECL) \
-{ \
- VEC_ASSERT (vec_ ? vec_->prefix.num >= size_ : !size_, "truncate", T, base);
\
- if (vec_) \
- vec_->prefix.num = size_; \
-} \
- \
-static inline T VEC_OP (T,base,replace) \
- (VEC(T,base) *vec_, unsigned ix_, T obj_ VEC_CHECK_DECL) \
-{ \
- T old_obj_; \
- \
- VEC_ASSERT (ix_ < vec_->prefix.num, "replace", T, base); \
- old_obj_ = vec_->vec[ix_]; \
- vec_->vec[ix_] = obj_; \
- \
- return old_obj_; \
-} \
- \
-static inline T *VEC_OP (T,base,quick_insert) \
- (VEC(T,base) *vec_, unsigned ix_, T obj_ VEC_CHECK_DECL) \
-{ \
- T *slot_; \
- \
- VEC_ASSERT (vec_->prefix.num < vec_->prefix.alloc, "insert", T, base); \
- VEC_ASSERT (ix_ <= vec_->prefix.num, "insert", T, base); \
- slot_ = &vec_->vec[ix_]; \
- memmove (slot_ + 1, slot_, (vec_->prefix.num++ - ix_) * sizeof (T)); \
- *slot_ = obj_; \
- \
- return slot_; \
-} \
- \
-static inline T VEC_OP (T,base,ordered_remove) \
- (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \
-{ \
- T *slot_; \
- T obj_; \
- \
- VEC_ASSERT (ix_ < vec_->prefix.num, "remove", T, base); \
- slot_ = &vec_->vec[ix_]; \
- obj_ = *slot_; \
- memmove (slot_, slot_ + 1, (--vec_->prefix.num - ix_) * sizeof (T));
\
- \
- return obj_; \
-} \
- \
-static inline T VEC_OP (T,base,unordered_remove) \
- (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \
-{ \
- T *slot_; \
- T obj_; \
- \
- VEC_ASSERT (ix_ < vec_->prefix.num, "remove", T, base); \
- slot_ = &vec_->vec[ix_]; \
- obj_ = *slot_; \
- *slot_ = vec_->vec[--vec_->prefix.num]; \
- \
- return obj_; \
-} \
- \
-static inline void VEC_OP (T,base,block_remove) \
- (VEC(T,base) *vec_, unsigned ix_, unsigned len_ VEC_CHECK_DECL) \
-{ \
- T *slot_; \
- \
- VEC_ASSERT (ix_ + len_ <= vec_->prefix.num, "block_remove", T, base); \
- slot_ = &vec_->vec[ix_]; \
- vec_->prefix.num -= len_; \
- memmove (slot_, slot_ + len_, (vec_->prefix.num - ix_) * sizeof (T)); \
-} \
- \
-static inline T *VEC_OP (T,base,address) \
- (VEC(T,base) *vec_) \
-{ \
- return vec_ ? vec_->vec : 0; \
-} \
- \
-static inline unsigned VEC_OP (T,base,lower_bound) \
- (VEC(T,base) *vec_, const T obj_, \
- bool (*lessthan_)(const T, const T) VEC_CHECK_DECL) \
-{ \
- unsigned int len_ = VEC_OP (T,base, length) (vec_); \
- unsigned int half_, middle_; \
- unsigned int first_ = 0; \
- while (len_ > 0) \
- { \
- T middle_elem_; \
- half_ = len_ >> 1; \
- middle_ = first_; \
- middle_ += half_; \
- middle_elem_ = VEC_OP (T,base,index) (vec_, middle_ VEC_CHECK_PASS); \
- if (lessthan_ (middle_elem_, obj_)) \
- { \
- first_ = middle_; \
- ++first_; \
- len_ = len_ - half_ - 1; \
- } \
- else \
- len_ = half_; \
- } \
- return first_; \
-}
-
-#define DEF_VEC_ALLOC_FUNC_P(T,A) \
-static inline VEC(T,A) *VEC_OP (T,A,alloc) \
- (int alloc_ MEM_STAT_DECL) \
-{ \
- return (VEC(T,A) *) vec_##A##_p_reserve_exact (NULL, alloc_ \
- PASS_MEM_STAT); \
+ unsigned int len_ = VEC_length (T, vec_);
+ unsigned int half_, middle_;
+ unsigned int first_ = 0;
+ while (len_ > 0)
+ {
+ T middle_elem_;
+ half_ = len_ >> 1;
+ middle_ = first_;
+ middle_ += half_;
+ middle_elem_ = VEC_index_1 (vec_, middle_ VEC_CHECK_PASS);
+ if (lessthan_ (middle_elem_, obj_))
+ {
+ first_ = middle_;
+ ++first_;
+ len_ = len_ - half_ - 1;
+ }
+ else
+ len_ = half_;
+ }
+ return first_;
}
-
-#define DEF_VEC_NONALLOC_FUNCS_P(T,A) \
-static inline void VEC_OP (T,A,free) \
- (VEC(T,A) **vec_) \
-{ \
- if (*vec_) \
- vec_##A##_free (*vec_); \
- *vec_ = NULL; \
-} \
- \
-static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \
-{ \
- size_t len_ = vec_ ? vec_->prefix.num : 0; \
- VEC (T,A) *new_vec_ = NULL; \
- \
- if (len_) \
- { \
- new_vec_ = (VEC (T,A) *)(vec_##A##_p_reserve_exact \
- (NULL, len_ PASS_MEM_STAT)); \
- \
- new_vec_->base.prefix.num = len_; \
- memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_); \
- } \
- return new_vec_; \
-} \
- \
-static inline int VEC_OP (T,A,reserve) \
- (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \
-{ \
- int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \
- VEC_CHECK_PASS); \
- \
- if (extend) \
- *vec_ = (VEC(T,A) *) vec_##A##_p_reserve (*vec_, alloc_ PASS_MEM_STAT); \
- \
- return extend; \
-} \
- \
-static inline int VEC_OP (T,A,reserve_exact) \
- (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \
-{ \
- int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \
- VEC_CHECK_PASS); \
- \
- if (extend) \
- *vec_ = (VEC(T,A) *) vec_##A##_p_reserve_exact (*vec_, alloc_ \
- PASS_MEM_STAT); \
- \
- return extend; \
-} \
- \
-static inline void VEC_OP (T,A,safe_grow) \
- (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \
-{ \
- VEC_ASSERT (size_ >= 0 \
- && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \
- "grow", T, A); \
- VEC_OP (T,A,reserve_exact) (vec_, \
- size_ - (int)(*vec_ ? VEC_BASE(*vec_)->prefix.num : 0) \
- VEC_CHECK_PASS PASS_MEM_STAT); \
- VEC_BASE (*vec_)->prefix.num = size_; \
-} \
- \
-static inline void VEC_OP (T,A,safe_grow_cleared) \
- (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \
-{ \
- int oldsize = VEC_OP(T,base,length) VEC_BASE(*vec_); \
- VEC_OP (T,A,safe_grow) (vec_, size_ VEC_CHECK_PASS PASS_MEM_STAT); \
- memset (&(VEC_OP (T,base,address) VEC_BASE(*vec_))[oldsize], 0, \
- sizeof (T) * (size_ - oldsize)); \
-} \
- \
-static inline void VEC_OP(T,A,safe_splice) \
- (VEC(T,A) **dst_, VEC(T,base) *src_ VEC_CHECK_DECL MEM_STAT_DECL) \
-{ \
- if (src_) \
- { \
- VEC_OP (T,A,reserve_exact) (dst_, src_->prefix.num \
- VEC_CHECK_PASS MEM_STAT_INFO); \
- \
- VEC_OP (T,base,splice) (VEC_BASE (*dst_), src_ \
- VEC_CHECK_PASS); \
- } \
-} \
- \
-static inline T *VEC_OP (T,A,safe_push) \
- (VEC(T,A) **vec_, T obj_ VEC_CHECK_DECL MEM_STAT_DECL) \
-{ \
- VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \
- \
- return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS); \
-} \
- \
-static inline T *VEC_OP (T,A,safe_insert) \
- (VEC(T,A) **vec_, unsigned ix_, T obj_ VEC_CHECK_DECL MEM_STAT_DECL) \
-{ \
- VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \
- \
- return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_ \
- VEC_CHECK_PASS); \
-}
-
-/* Vector of object. */
-#define DEF_VEC_O(T) \
-VEC_T_GTY(T,base); \
-VEC_TA(T,base,none); \
-DEF_VEC_FUNC_O(T) \
-struct vec_swallow_trailing_semi
-#define DEF_VEC_ALLOC_O(T,A) \
-VEC_TA(T,base,A); \
-DEF_VEC_ALLOC_FUNC_O(T,A) \
-DEF_VEC_NONALLOC_FUNCS_O(T,A) \
-struct vec_swallow_trailing_semi
-
-#define DEF_VEC_FUNC_O(T) \
-static inline unsigned VEC_OP (T,base,length) (const VEC(T,base) *vec_) \
-{ \
- return vec_ ? vec_->prefix.num : 0; \
-} \
- \
-static inline T *VEC_OP (T,base,last) (VEC(T,base) *vec_ VEC_CHECK_DECL) \
-{ \
- VEC_ASSERT (vec_ && vec_->prefix.num, "last", T, base); \
- \
- return &vec_->vec[vec_->prefix.num - 1]; \
-} \
- \
-static inline T *VEC_OP (T,base,index) \
- (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \
-{ \
- VEC_ASSERT (vec_ && ix_ < vec_->prefix.num, "index", T, base); \
- \
- return &vec_->vec[ix_]; \
-} \
- \
-static inline int VEC_OP (T,base,iterate) \
- (VEC(T,base) *vec_, unsigned ix_, T **ptr) \
-{ \
- if (vec_ && ix_ < vec_->prefix.num) \
- { \
- *ptr = &vec_->vec[ix_]; \
- return 1; \
- } \
- else \
- { \
- *ptr = 0; \
- return 0; \
- } \
-} \
- \
-static inline size_t VEC_OP (T,base,embedded_size) \
- (int alloc_) \
-{ \
- return offsetof (VEC(T,base),vec) + alloc_ * sizeof(T); \
-} \
- \
-static inline void VEC_OP (T,base,embedded_init) \
- (VEC(T,base) *vec_, int alloc_) \
-{ \
- vec_->prefix.num = 0; \
- vec_->prefix.alloc = alloc_; \
-} \
- \
-static inline int VEC_OP (T,base,space) \
- (VEC(T,base) *vec_, int alloc_ VEC_CHECK_DECL) \
-{ \
- VEC_ASSERT (alloc_ >= 0, "space", T, base); \
- return vec_ ? vec_->prefix.alloc - vec_->prefix.num >= (unsigned)alloc_ :
!alloc_; \
-} \
- \
-static inline void VEC_OP(T,base,splice) \
- (VEC(T,base) *dst_, VEC(T,base) *src_ VEC_CHECK_DECL) \
-{ \
- if (src_) \
- { \
- unsigned len_ = src_->prefix.num; \
- VEC_ASSERT (dst_->prefix.num + len_ <= dst_->prefix.alloc, "splice", T,
base); \
- \
- memcpy (&dst_->vec[dst_->prefix.num], &src_->vec[0], len_ * sizeof (T));
\
- dst_->prefix.num += len_; \
- } \
-} \
- \
-static inline T *VEC_OP (T,base,quick_push) \
- (VEC(T,base) *vec_, const T *obj_ VEC_CHECK_DECL) \
-{ \
- T *slot_; \
- \
- VEC_ASSERT (vec_->prefix.num < vec_->prefix.alloc, "push", T, base); \
- slot_ = &vec_->vec[vec_->prefix.num++]; \
- if (obj_) \
- *slot_ = *obj_; \
- \
- return slot_; \
-} \
- \
-static inline void VEC_OP (T,base,pop) (VEC(T,base) *vec_ VEC_CHECK_DECL) \
-{ \
- VEC_ASSERT (vec_->prefix.num, "pop", T, base); \
- --vec_->prefix.num; \
-} \
- \
-static inline void VEC_OP (T,base,truncate) \
- (VEC(T,base) *vec_, unsigned size_ VEC_CHECK_DECL) \
-{ \
- VEC_ASSERT (vec_ ? vec_->prefix.num >= size_ : !size_, "truncate", T, base);
\
- if (vec_) \
- vec_->prefix.num = size_; \
-} \
- \
-static inline T *VEC_OP (T,base,replace) \
- (VEC(T,base) *vec_, unsigned ix_, const T *obj_ VEC_CHECK_DECL) \
-{ \
- T *slot_; \
- \
- VEC_ASSERT (ix_ < vec_->prefix.num, "replace", T, base); \
- slot_ = &vec_->vec[ix_]; \
- if (obj_) \
- *slot_ = *obj_; \
- \
- return slot_; \
-} \
- \
-static inline T *VEC_OP (T,base,quick_insert) \
- (VEC(T,base) *vec_, unsigned ix_, const T *obj_ VEC_CHECK_DECL) \
-{ \
- T *slot_; \
- \
- VEC_ASSERT (vec_->prefix.num < vec_->prefix.alloc, "insert", T, base); \
- VEC_ASSERT (ix_ <= vec_->prefix.num, "insert", T, base); \
- slot_ = &vec_->vec[ix_]; \
- memmove (slot_ + 1, slot_, (vec_->prefix.num++ - ix_) * sizeof (T)); \
- if (obj_) \
- *slot_ = *obj_; \
- \
- return slot_; \
-} \
- \
-static inline void VEC_OP (T,base,ordered_remove) \
- (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \
-{ \
- T *slot_; \
- \
- VEC_ASSERT (ix_ < vec_->prefix.num, "remove", T, base); \
- slot_ = &vec_->vec[ix_]; \
- memmove (slot_, slot_ + 1, (--vec_->prefix.num - ix_) * sizeof (T)); \
-} \
- \
-static inline void VEC_OP (T,base,unordered_remove) \
- (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \
-{ \
- VEC_ASSERT (ix_ < vec_->prefix.num, "remove", T, base); \
- vec_->vec[ix_] = vec_->vec[--vec_->prefix.num]; \
-} \
- \
-static inline void VEC_OP (T,base,block_remove) \
- (VEC(T,base) *vec_, unsigned ix_, unsigned len_ VEC_CHECK_DECL) \
-{ \
- T *slot_; \
- \
- VEC_ASSERT (ix_ + len_ <= vec_->prefix.num, "block_remove", T, base); \
- slot_ = &vec_->vec[ix_]; \
- vec_->prefix.num -= len_; \
- memmove (slot_, slot_ + len_, (vec_->prefix.num - ix_) * sizeof (T)); \
-} \
- \
-static inline T *VEC_OP (T,base,address) \
- (VEC(T,base) *vec_) \
-{ \
- return vec_ ? vec_->vec : 0; \
-} \
- \
-static inline unsigned VEC_OP (T,base,lower_bound) \
- (VEC(T,base) *vec_, const T *obj_, \
- bool (*lessthan_)(const T *, const T *) VEC_CHECK_DECL) \
-{ \
- unsigned int len_ = VEC_OP (T, base, length) (vec_); \
- unsigned int half_, middle_; \
- unsigned int first_ = 0; \
- while (len_ > 0) \
- { \
- T *middle_elem_; \
- half_ = len_ >> 1; \
- middle_ = first_; \
- middle_ += half_; \
- middle_elem_ = VEC_OP (T,base,index) (vec_, middle_ VEC_CHECK_PASS); \
- if (lessthan_ (middle_elem_, obj_)) \
- { \
- first_ = middle_; \
- ++first_; \
- len_ = len_ - half_ - 1; \
- } \
- else \
- len_ = half_; \
- } \
- return first_; \
+template<typename T>
+static inline unsigned
+VEC_lower_bound_1 (vec_t<T> *vec_, const T *ptr_,
+ bool (*lessthan_)(const T*, const T*) VEC_CHECK_DECL)
+{
+ unsigned int len_ = VEC_length (T, vec_);
+ unsigned int half_, middle_;
+ unsigned int first_ = 0;
+ while (len_ > 0)
+ {
+ T *middle_elem_;
+ half_ = len_ >> 1;
+ middle_ = first_;
+ middle_ += half_;
+ middle_elem_ = &VEC_index_1 (vec_, middle_ VEC_CHECK_PASS);
+ if (lessthan_ (middle_elem_, ptr_))
+ {
+ first_ = middle_;
+ ++first_;
+ len_ = len_ - half_ - 1;
+ }
+ else
+ len_ = half_;
+ }
+ return first_;
}
-#define DEF_VEC_ALLOC_FUNC_O(T,A) \
-static inline VEC(T,A) *VEC_OP (T,A,alloc) \
- (int alloc_ MEM_STAT_DECL) \
-{ \
- return (VEC(T,A) *) vec_##A##_o_reserve_exact (NULL, alloc_, \
- offsetof (VEC(T,A),base.vec), \
- sizeof (T) \
- PASS_MEM_STAT); \
-}
-#define DEF_VEC_NONALLOC_FUNCS_O(T,A) \
-static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \
-{ \
- size_t len_ = vec_ ? vec_->prefix.num : 0; \
- VEC (T,A) *new_vec_ = NULL; \
- \
- if (len_) \
- { \
- new_vec_ = (VEC (T,A) *)(vec_##A##_o_reserve_exact \
- (NULL, len_, \
- offsetof (VEC(T,A),base.vec), sizeof (T) \
- PASS_MEM_STAT)); \
- \
- new_vec_->base.prefix.num = len_; \
- memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_); \
- } \
- return new_vec_; \
-} \
- \
-static inline void VEC_OP (T,A,free) \
- (VEC(T,A) **vec_) \
-{ \
- if (*vec_) \
- vec_##A##_free (*vec_); \
- *vec_ = NULL; \
-} \
- \
-static inline int VEC_OP (T,A,reserve) \
- (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \
-{ \
- int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \
- VEC_CHECK_PASS); \
- \
- if (extend) \
- *vec_ = (VEC(T,A) *) vec_##A##_o_reserve (*vec_, alloc_, \
- offsetof (VEC(T,A),base.vec),\
- sizeof (T) \
- PASS_MEM_STAT); \
- \
- return extend; \
-} \
- \
-static inline int VEC_OP (T,A,reserve_exact) \
- (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \
-{ \
- int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \
- VEC_CHECK_PASS); \
- \
- if (extend) \
- *vec_ = (VEC(T,A) *) vec_##A##_o_reserve_exact \
- (*vec_, alloc_, \
- offsetof (VEC(T,A),base.vec), \
- sizeof (T) PASS_MEM_STAT); \
- \
- return extend; \
-} \
- \
-static inline void VEC_OP (T,A,safe_grow) \
- (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \
-{ \
- VEC_ASSERT (size_ >= 0 \
- && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \
- "grow", T, A); \
- VEC_OP (T,A,reserve_exact) (vec_, \
- size_ - (int)(*vec_ ? VEC_BASE(*vec_)->prefix.num : 0) \
- VEC_CHECK_PASS PASS_MEM_STAT); \
- VEC_BASE (*vec_)->prefix.num = size_; \
-} \
- \
-static inline void VEC_OP (T,A,safe_grow_cleared) \
- (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \
-{ \
- int oldsize = VEC_OP(T,base,length) VEC_BASE(*vec_); \
- VEC_OP (T,A,safe_grow) (vec_, size_ VEC_CHECK_PASS PASS_MEM_STAT); \
- memset (&(VEC_OP (T,base,address) VEC_BASE(*vec_))[oldsize], 0, \
- sizeof (T) * (size_ - oldsize)); \
-} \
- \
-static inline void VEC_OP(T,A,safe_splice) \
- (VEC(T,A) **dst_, VEC(T,base) *src_ VEC_CHECK_DECL MEM_STAT_DECL) \
-{ \
- if (src_) \
- { \
- VEC_OP (T,A,reserve_exact) (dst_, src_->prefix.num \
- VEC_CHECK_PASS MEM_STAT_INFO); \
- \
- VEC_OP (T,base,splice) (VEC_BASE (*dst_), src_ \
- VEC_CHECK_PASS); \
- } \
-} \
- \
-static inline T *VEC_OP (T,A,safe_push) \
- (VEC(T,A) **vec_, const T *obj_ VEC_CHECK_DECL MEM_STAT_DECL) \
-{ \
- VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \
- \
- return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS); \
-} \
- \
-static inline T *VEC_OP (T,A,safe_insert) \
- (VEC(T,A) **vec_, unsigned ix_, const T *obj_ \
- VEC_CHECK_DECL MEM_STAT_DECL) \
-{ \
- VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \
- \
- return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_ \
- VEC_CHECK_PASS); \
-}
+void *vec_heap_o_reserve_1 (void *, int, size_t, size_t, bool MEM_STAT_DECL);
+void *vec_gc_o_reserve_1 (void *, int, size_t, size_t, bool MEM_STAT_DECL);
-#define DEF_VEC_ALLOC_FUNC_I(T,A) \
-static inline VEC(T,A) *VEC_OP (T,A,alloc) \
- (int alloc_ MEM_STAT_DECL) \
-{ \
- return (VEC(T,A) *) vec_##A##_o_reserve_exact \
- (NULL, alloc_, offsetof (VEC(T,A),base.vec), \
- sizeof (T) PASS_MEM_STAT); \
-}
+/* Ensure there are at least RESERVE free slots in VEC_, growing
+ exponentially. If RESERVE < 0 grow exactly, else grow
+ exponentially. As a special case, if VEC_ is NULL, and RESERVE is
+ 0, no vector will be created. */
-#define DEF_VEC_NONALLOC_FUNCS_I(T,A) \
-static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \
-{ \
- size_t len_ = vec_ ? vec_->prefix.num : 0; \
- VEC (T,A) *new_vec_ = NULL; \
- \
- if (len_) \
- { \
- new_vec_ = (VEC (T,A) *)(vec_##A##_o_reserve_exact \
- (NULL, len_, \
- offsetof (VEC(T,A),base.vec), sizeof (T) \
- PASS_MEM_STAT)); \
- \
- new_vec_->base.prefix.num = len_; \
- memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_); \
- } \
- return new_vec_; \
-} \
- \
-static inline void VEC_OP (T,A,free) \
- (VEC(T,A) **vec_) \
-{ \
- if (*vec_) \
- vec_##A##_free (*vec_); \
- *vec_ = NULL; \
-} \
- \
-static inline int VEC_OP (T,A,reserve) \
- (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \
-{ \
- int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \
- VEC_CHECK_PASS); \
- \
- if (extend) \
- *vec_ = (VEC(T,A) *) vec_##A##_o_reserve (*vec_, alloc_, \
- offsetof (VEC(T,A),base.vec),\
- sizeof (T) \
- PASS_MEM_STAT); \
- \
- return extend; \
-} \
- \
-static inline int VEC_OP (T,A,reserve_exact) \
- (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \
-{ \
- int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \
- VEC_CHECK_PASS); \
- \
- if (extend) \
- *vec_ = (VEC(T,A) *) vec_##A##_o_reserve_exact \
- (*vec_, alloc_, offsetof (VEC(T,A),base.vec), \
- sizeof (T) PASS_MEM_STAT); \
- \
- return extend; \
-} \
- \
-static inline void VEC_OP (T,A,safe_grow) \
- (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \
-{ \
- VEC_ASSERT (size_ >= 0 \
- && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \
- "grow", T, A); \
- VEC_OP (T,A,reserve_exact) (vec_, \
- size_ - (int)(*vec_ ? VEC_BASE(*vec_)->prefix.num : 0) \
- VEC_CHECK_PASS PASS_MEM_STAT); \
- VEC_BASE (*vec_)->prefix.num = size_; \
-} \
- \
-static inline void VEC_OP (T,A,safe_grow_cleared) \
- (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \
-{ \
- int oldsize = VEC_OP(T,base,length) VEC_BASE(*vec_); \
- VEC_OP (T,A,safe_grow) (vec_, size_ VEC_CHECK_PASS PASS_MEM_STAT); \
- memset (&(VEC_OP (T,base,address) VEC_BASE(*vec_))[oldsize], 0, \
- sizeof (T) * (size_ - oldsize)); \
-} \
- \
-static inline void VEC_OP(T,A,safe_splice) \
- (VEC(T,A) **dst_, VEC(T,base) *src_ VEC_CHECK_DECL MEM_STAT_DECL) \
-{ \
- if (src_) \
- { \
- VEC_OP (T,A,reserve_exact) (dst_, src_->prefix.num \
- VEC_CHECK_PASS MEM_STAT_INFO); \
- \
- VEC_OP (T,base,splice) (VEC_BASE (*dst_), src_ \
- VEC_CHECK_PASS); \
- } \
-} \
- \
-static inline T *VEC_OP (T,A,safe_push) \
- (VEC(T,A) **vec_, const T obj_ VEC_CHECK_DECL MEM_STAT_DECL) \
-{ \
- VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \
- \
- return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS); \
-} \
- \
-static inline T *VEC_OP (T,A,safe_insert) \
- (VEC(T,A) **vec_, unsigned ix_, const T obj_ \
- VEC_CHECK_DECL MEM_STAT_DECL) \
-{ \
- VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \
- \
- return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_ \
- VEC_CHECK_PASS); \
+template<typename T, enum vec_allocation_t A>
+vec_t<T> *
+vec_reserve (vec_t<T> *vec_, int reserve MEM_STAT_DECL)
+{
+ if (A == gc)
+ return (vec_t<T> *) vec_gc_o_reserve_1 (vec_, reserve,
+ offsetof (vec_t<T>, vec),
+ sizeof (T), false
+ PASS_MEM_STAT);
+ else if (A == heap)
+ return (vec_t<T> *) vec_heap_o_reserve_1 (vec_, reserve,
+ offsetof (vec_t<T>, vec),
+ sizeof (T), false
+ PASS_MEM_STAT);
+ else
+ {
+ /* Only allow stack vectors when re-growing them. The initial
+ allocation of stack vectors must be done with the
+ VEC_stack_alloc macro, because it uses alloca() for the
+ allocation. */
+ if (vec_ == NULL)
+ {
+ fprintf (stderr, "Stack vectors must be initially allocated "
+ "with VEC_stack_alloc.\n");
+ gcc_unreachable ();
+ }
+ return (vec_t<T> *) vec_stack_o_reserve (vec_, reserve,
+ offsetof (vec_t<T>, vec),
+ sizeof (T) PASS_MEM_STAT);
+ }
}
-/* 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. Instead of DEF_VEC_ALLOC_P(TYPE, heap|gc), use
- DEF_VEC_ALLOC_P_STACK(TYPE). This uses alloca to get the initial
- space; because alloca can not be usefully called in an inline
- function, and because a macro can not define a macro, you must then
- write a #define for each type:
-
- #define VEC_{TYPE}_stack_alloc(alloc) \
- VEC_stack_alloc({TYPE}, alloc)
- This is really a hack and perhaps can be made better. Note that
- this macro will wind up evaluating the ALLOC parameter twice.
+/* Ensure there are at least RESERVE free slots in VEC_, growing
+ exactly. If RESERVE < 0 grow exactly, else grow exponentially. As
+ a special case, if VEC_ is NULL, and RESERVE is 0, no vector will be
+ created. */
- 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 VEC(TYPE,stack) vector from the function
- which allocated it. */
-
-extern void *vec_stack_p_reserve (void *, int MEM_STAT_DECL);
-extern void *vec_stack_p_reserve_exact (void *, int MEM_STAT_DECL);
-extern void *vec_stack_p_reserve_exact_1 (int, void *);
-extern void *vec_stack_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL);
-extern void *vec_stack_o_reserve_exact (void *, int, size_t, size_t
- MEM_STAT_DECL);
-extern void vec_stack_free (void *);
-
-#ifdef GATHER_STATISTICS
-#define VEC_stack_alloc(T,alloc,name,line,function) \
- (VEC_OP (T,stack,alloc1) \
- (alloc, XALLOCAVAR (VEC(T,stack), VEC_embedded_size (T, alloc))))
-#else
-#define VEC_stack_alloc(T,alloc) \
- (VEC_OP (T,stack,alloc1) \
- (alloc, XALLOCAVAR (VEC(T,stack), VEC_embedded_size (T, alloc))))
-#endif
-
-#define DEF_VEC_ALLOC_P_STACK(T) \
-VEC_TA(T,base,stack); \
-DEF_VEC_ALLOC_FUNC_P_STACK(T) \
-DEF_VEC_NONALLOC_FUNCS_P(T,stack) \
-struct vec_swallow_trailing_semi
-
-#define DEF_VEC_ALLOC_FUNC_P_STACK(T) \
-static inline VEC(T,stack) *VEC_OP (T,stack,alloc1) \
- (int alloc_, VEC(T,stack)* space) \
-{ \
- return (VEC(T,stack) *) vec_stack_p_reserve_exact_1 (alloc_, space); \
-}
-
-#define DEF_VEC_ALLOC_O_STACK(T) \
-VEC_TA(T,base,stack); \
-DEF_VEC_ALLOC_FUNC_O_STACK(T) \
-DEF_VEC_NONALLOC_FUNCS_O(T,stack) \
-struct vec_swallow_trailing_semi
-
-#define DEF_VEC_ALLOC_FUNC_O_STACK(T) \
-static inline VEC(T,stack) *VEC_OP (T,stack,alloc1) \
- (int alloc_, VEC(T,stack)* space) \
-{ \
- return (VEC(T,stack) *) vec_stack_p_reserve_exact_1 (alloc_, space); \
-}
-
-#define DEF_VEC_ALLOC_I_STACK(T) \
-VEC_TA(T,base,stack); \
-DEF_VEC_ALLOC_FUNC_I_STACK(T) \
-DEF_VEC_NONALLOC_FUNCS_I(T,stack) \
-struct vec_swallow_trailing_semi
-
-#define DEF_VEC_ALLOC_FUNC_I_STACK(T) \
-static inline VEC(T,stack) *VEC_OP (T,stack,alloc1) \
- (int alloc_, VEC(T,stack)* space) \
-{ \
- return (VEC(T,stack) *) vec_stack_p_reserve_exact_1 (alloc_, space); \
+template<typename T, enum vec_allocation_t A>
+vec_t<T> *
+vec_reserve_exact (vec_t<T> *vec_, int reserve MEM_STAT_DECL)
+{
+ if (A == gc)
+ return (vec_t<T> *) vec_gc_o_reserve_1 (vec_, reserve,
+ sizeof (struct vec_prefix),
+ sizeof (T), true
+ PASS_MEM_STAT);
+ else if (A == heap)
+ return (vec_t<T> *) vec_heap_o_reserve_1 (vec_, reserve,
+ sizeof (struct vec_prefix),
+ sizeof (T), true
+ PASS_MEM_STAT);
+ else if (A == stack)
+ {
+ /* Only allow stack vectors when re-growing them. The initial
+ allocation of stack vectors must be done with VEC_alloc,
+ because it uses alloca() for the allocation. */
+ if (vec_ == NULL)
+ {
+ fprintf (stderr, "Stack vectors must be initially allocated "
+ "with VEC_stack_alloc.\n");
+ gcc_unreachable ();
+ }
+ return (vec_t<T> *) vec_stack_o_reserve_exact (vec_, reserve,
+ sizeof (struct vec_prefix),
+ sizeof (T)
+ PASS_MEM_STAT);
+ }
}
#endif /* GCC_VEC_H */
--
This patch is available for review at http://codereview.appspot.com/6233044
Sign in to reply to this message.
On 5/23/12, Diego Novillo <dnovillo@google.com> wrote: > OK for cxx-conversion branch? LGTM. -- Lawrence Crowl
Sign in to reply to this message.
On Wed, May 23, 2012 at 9:48 PM, Diego Novillo <dnovillo@google.com> wrote: > > This series of 3 patches re-implement vec.[ch] in C++. > > The main goal of this first step is to minimize changes to client > code. I tried very hard to maintain the existing API. This means > that vectors are still simple structures accessed via the existing > VEC_* functions. > > The major change introduced here is the removal of all the macro-based > type creation in vec.h: > > 1- Given a type T and an allocation strategy A, VEC(T,A) used to > expand into the C type 'struct VEC_T_A'. The family of accessor > functions for VEC_T_A were created via macro expansion and token > pasting. > > After this patch, VEC(T,A) expands to 'vec_t<T>': > > template<typename T> > struct GTY(()) vec_t > { > vec_prefix prefix; > T GTY((length ("%h.prefix.num"))) vec[1]; > }; > > The family of accessor functions for vec_t<T> are free functions > templated on <T> or <T,A> depending on whether the function needs > to perform allocation operations. > > 2- All the DEF_VEC_[IOP] and DEF_VEC_ALLOC_[IOP] macros expand to the > nil expansion 'struct vec_swallow_trailing_semi'. This represents > the bulk of the removal in vec.h. > > 3- I removed one indirection from the existing VEC structures. Before > this patch, the visible structure created by VEC_T_A had a single > element 'base', which, in turn, was the structure holding 'prefix' > and 'vec'. The new vec_t<T> has 'prefix' and 'vec' in it. This > may change in the second iteration of this patch. I believe this was because of aliasing - you may dig in the svn history to find out what we miscompiled when not doing this and whether it is still necessary or not. > Some client code changes were needed: > > 1- The allocation names 'heap', 'stack' and 'gc' are not embedded in > the type name anymore. They are enum values used as a template > argument for functions like VEC_alloc() and VEC_free(). Since they > are now separate identifiers, some existing code that declared > variables with the names 'heap' and 'stack' had to change. > > I did not change these enum values to better names because that > would have meant changing a lot more client code. I will change > this in a future patch. Yeah. Can we have template <...> struct vec { enum { gc, heap, stack }; ... } and use vec<T, vec::stack> instead? Not sure if this or something similar is valid C++. > 2- VEC_index and VEC_last now return a reference to the element. The > existing APIs implemented two versions of these functions. One > returning the element itself (used for vec_t<T *>). Another returning > a pointer to the element (used for vec_t<T>). > > This is impossible to represent in C++ directly, as functions > cannot be overloaded by their return value. Instead, I made them > return a reference to the element. This means that vectors storing > pointers (T *) do not need to change, but vectors of objects (T) do > need to change. > > We have fewer vec_t<T> than vec_t<T *>, so this was the smaller change > (which still meant changing a few hundred call sites). We still can have const overloads when taking a const vec though? > 3- The family of VEC_*push and VEC_*replace functions have overloads > for handling 'T' and 'const T *' objects. The former is used for > vec_t<T>, the latter for vec_t<T*>. This means, however, than when > pushing the special value 0 on a vec_t<T*>, the compiler will not > know which overload we meant, as 0 matches both. In these cases > (not very many), a static cast is all we need to help it. > > I'm not terribly content with this one. I'll try to have a better > approach in the second iteration (which will liberally change all > client code). I wonder whether explicitely specifying the template type is better? Thus, VEC_safe_push<T *, gc>(0) instead of automatically deducing the template argument? > 4- I extended gengtype to understand templated types. These changes > are not as ugly as I thought they would be. Gengtype has some > hardwired knowledge of VEC_*, which I renamed to vec_t. I'm not > even sure why gengtype needs to care about vec_t in this way, but I > was looking for minimal changes, so I just did it. > > The other change is more generic. It allows gengtype to deal with > templated types. There is a new function (filter_type_name) that > recognizes C++ special characters '<', '>' and ':'. It turns them > into '_'. This way, gengtype can generate a valid identifier for > the pre-processor. It only does this in contexts where it needs a > pre-processor identifier. For everything else, it emits the type > directly. So, the functions emitted in gt-*.h files have proper > template type references. Well, that part is of course what needs to change. I don't think we want gengtype to work like this for templates as this does not scale. > > Properties of this patch: > > The performance and memory numbers I collected here were done by > bootstrapping the branch before and after my patch with all > languages enabled (including Ada and Go). > > I collected time and memory reports by forcing the switches > -ftime-report and -fmem-report to be on by default, and to emit > their output to a separate file (otherwise the bootstrap fails > when some configure checks get confused by the extraneous stderr > output). This produced 2.9Gb of output over 12,944 timings > files. > > 1- There is much less code in vec.[ch] (21% fewer lines). > Functions are no longer replicated 2 or 3 times. > > 2- Debugging VEC_* routines is simpler. Failures in GDB go to > the specific VEC_* function instance, instead of the DEF_VEC_* > macro. > > 3- The new implementation is faster. Individual compiles are > generally 2.0 to 2.5% faster (wall time). This translates into > a bootstrap speedup of 1-2% (wall time reduction of about a minute > on my desktop). > > The reason for this speedup is that various VEC_ routines now > return a reference to the element, which means that for vec_t<T> > there is one less memory indirection to perform. > > 4- Minimal changes to binary code size. The *1 binaries are about > 0.07% bigger. > > 5- Reduced memory consumption by 4% on average (as measured by -fmem-report). > I averaged the 'Total Allocated:' field from -fmem-report from > all the compile > > There are fewer macros expanded (-23%) and fewer > trees generated (the numbers below are averages over the > 12,944 compilations): > > Before After (%) > decls 9,491 9,240 - 2.6% > types 2,958 2,827 - 4.4% > blocks 525 460 -12.4% > stmts 1,123 1,043 - 7.1% > refs 4,369 3,926 -10.1% > exprs 15,236 14,283 - 6.2% > constants 1,888 1,871 - 0.9% > identifiers 7,285 7,197 - 1.2% > vecs 1,786 1,786 0% > binfos 113 109 - 3.5% > ssa names 2,240 2,240 0% > constructors 245 245 0% > random kinds 13,338 12,849 - 3.7% > lang_decl kinds 2,816 2,640 - 6.2% > lang_type kinds 110 106 - 3.6% > omp clauses 0 0 0% > > > > Next step: > > Before I consider moving this patch over to trunk, I would like to > generate a second patch that will: > > 1- Move all the free functions VEC_* into vec_t<T>. This will > simplify the call sites quite a bit. Mainly, it will remove the > unnecessary arguments T and A that are now always specified in > every call. > > 2- Change VEC_index into operator[]. > > 3- Change VEC_replace(...) to assignments using operator[]. I think these should not be done for now - they merely add syntactic sugar, no? > One thing these changes will do, however, is lose the VEC_CHECK_* > expansions that add the __FILE__, __LINE__ and __FUNCTION__ arguments > to the VEC_*() functions. > > To deal with this loss, we could unwind the call stack a few levels on > ICEs. In fact, I think this could be a good thing to add to ICEs in > general. Showing some functions up the stack seems more useful than > just showing a single point. > > OK for cxx-conversion branch? Where's the gengtype/GC bits? Richard. > > > 2012-05-22 Diego Novillo <dnovillo@google.com> > > Re-implement VEC in C++. > > * vec.c (vec_heap_free): Convert into a template function. > (vec_gc_o_reserve_1): Make extern. > (vec_gc_p_reserve): Remove. > (vec_gc_p_reserve_exact): Remove. > (vec_gc_o_reserve): Remove. > (vec_gc_o_reserve_exact): Remove. > (vec_heap_o_reserve_1): Make extern. > (vec_heap_p_reserve): Remove. > (vec_heap_p_reserve_exact): Remove. > (vec_heap_o_reserve): Remove. > (vec_heap_o_reserve_exact): Remove. > (vec_stack_p_reserve): Remove. > (vec_stack_p_reserve_exact): Remove. > * vec.h (VEC_CHECK_INFO, VEC_CHECK_DECL, VEC_CHECK_PASS, > VEC_ASSERT, VEC_ASSERT_FAIL, vec_assert_fail): Move earlier > in the file. > (VEC): Define to vec_t<T>. > (vec_allocation_t): Define. > (struct vec_prefix): Move earlier in the file. > (vec_t<T>): New template. > (DEF_VEC_I, DEF_VECL_ALLOC_I, DEF_VEC_P, DEF_VEC_ALLOC_P, > DEF_VEC_O, DEF_VEC_ALLOC_P, DEF_VEC_O, DEF_VEC_ALLOC_O, > DEF_VEC_ALLOC_P_STACK, DEF_VEC_ALLOC_O_STACK, > DEF_VEC_ALLOC_I_STACK): Expand to 'struct vec_swallow_trailing_semi'. > (vec_stack_p_reserve): Remove. > (vec_stack_p_reserve_exact): Remove. > (vec_stack_p_reserve_exact_1): Remove. > (vec_stack_o_reserve): Remove. > (vec_stack_o_reserve_exact): Remove. > (vec_stack_free): Re-write as a template function. > (vec_reserve): New template function. > (vec_reserve_exact): New template function. > (vec_heap_free): New template function if GATHER_STATISTICS is > defined. Otherwise, macro that expands to free(). > (VEC_length_1): New template function. > (VEC_length): Call it. > (VEC_empty_1): New template function. > (VEC_empty): Call it. > (VEC_address_1): New template function. > (VEC_address): Call it. > (VEC_last_1): New template function. > (VEC_last): Call it. Change return type to T&. > Change all users that used VEC_Os. > (VEC_index_1): New template function. > (VEC_index): Call it. Return a T& instead of a T*. > Update all callers that were using VEC_O before. > (VEC_iterate_1): New template function. > (VEC_iterate): Call it. > (VEC_embedded_size_1): New template function. > (VEC_embedded_size): Call it. > (VEC_embedded_init_1): New template function. > (VEC_embedded_init): Call it. > (VEC_alloc_1): New template function. > (VEC_alloc): Call it. If A is 'stack', call XALLOCAVAR to > do the allocation. > (VEC_free_1): New template function. > (VEC_free): Call it. > (VEC_copy_1): New template function. > (VEC_copy): Call it. > (VEC_space_1): New template function > (VEC_space): Call it. > (VEC_reserve_1): New template function. > (VEC_reserve): Call it. > (VEC_reserve_exact_1): New template function. > (VEC_reserve_exact): Call it. > (VEC_splice_1): New template function. > (VEC_splice): Call it. > (VEC_safe_splice_1): New template function. > (VEC_safe_splice): Call it. > (VEC_quick_push_1): New template function. Create two overloads, one > accepting T, the other accepting T *. Update all callers > where T and T * are ambiguous. > (VEC_quick_push): Call it. > (VEC_safe_push_1): New template function. Create two overloads, one > accepting T, the other accepting T *. Update all callers > where T and T * are ambiguous. > (VEC_safe_push): Call it. > (VEC_pop_1): New template function. > (VEC_pop): Call it. > (VEC_truncate_1): New template function. > (VEC_truncate): Call it. > (VEC_safe_grow_1): New template function. > (VEC_safe_grow): Call it. > (VEC_safe_grow_cleared_1): New template function. > (VEC_safe_grow_cleared): Call it. > (VEC_replace_1): New template function. > (VEC_replace): Call it. Always accept T instead of T*. > Update all callers that used VEC_Os. > (VEC_quick_insert_1): New template function. > (VEC_quick_insert): Call it. > (VEC_safe_insert_1): New template function. > (VEC_safe_insert): Call it. > (VEC_ordered_remove_1): New template function. > (VEC_ordered_remove): Call it. > (VEC_unordered_remove_1): New template function. > (VEC_unordered_remove): Call it. > (VEC_block_remove_1): New template function. > (VEC_block_remove): Call it. > (VEC_lower_bound_1): New template function. > (VEC_lower_bound): Call it. > (VEC_OP): Remove. > (DEF_VEC_FUNC_P): Remove. > (DEF_VEC_ALLOC_FUNC_P): Remove. > (DEF_VEC_NONALLOC_FUNCS_P): Remove. > (DEF_VEC_FUNC_O): Remove. > (DEF_VEC_ALLOC_FUNC_O): Remove. > (DEF_VEC_NONALLOC_FUNCS_O): Remove. > (DEF_VEC_ALLOC_FUNC_I): Remove. > (DEF_VEC_NONALLOC_FUNCS_I): Remove. > (DEF_VEC_ALLOC_FUNC_P_STACK): Remove. > (DEF_VEC_ALLOC_FUNC_O_STACK): Remove. > (DEF_VEC_ALLOC_FUNC_I_STACK): Remove. > (vec_reserve_exact): New template function. > > diff --git a/gcc/vec.c b/gcc/vec.c > index 783a3cf..ba81e35 100644 > --- a/gcc/vec.c > +++ b/gcc/vec.c > @@ -1,7 +1,8 @@ > /* Vector API for GNU compiler. > - Copyright (C) 2004, 2005, 2006, 2007, 2008, 2010 > + Copyright (C) 2004, 2005, 2006, 2007, 2008, 2010, 2011, 2012 > 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. > > @@ -215,7 +216,7 @@ calculate_allocation (const struct vec_prefix *pfx, int reserve, bool exact) > trailing array is at VEC_OFFSET offset and consists of ELT_SIZE > sized elements. */ > > -static void * > +void * > vec_gc_o_reserve_1 (void *vec, int reserve, size_t vec_offset, size_t elt_size, > bool exact MEM_STAT_DECL) > { > @@ -248,61 +249,10 @@ vec_gc_o_reserve_1 (void *vec, int reserve, size_t vec_offset, size_t elt_size, > return vec; > } > > -/* Ensure there are at least RESERVE free slots in VEC, growing > - exponentially. If RESERVE < 0 grow exactly, else grow > - exponentially. As a special case, if VEC is NULL, and RESERVE is > - 0, no vector will be created. */ > - > -void * > -vec_gc_p_reserve (void *vec, int reserve MEM_STAT_DECL) > -{ > - return vec_gc_o_reserve_1 (vec, reserve, > - sizeof (struct vec_prefix), > - sizeof (void *), false > - PASS_MEM_STAT); > -} > - > -/* Ensure there are at least RESERVE free slots in VEC, growing > - exactly. If RESERVE < 0 grow exactly, else grow exponentially. As > - a special case, if VEC is NULL, and RESERVE is 0, no vector will be > - created. */ > - > -void * > -vec_gc_p_reserve_exact (void *vec, int reserve MEM_STAT_DECL) > -{ > - return vec_gc_o_reserve_1 (vec, reserve, > - sizeof (struct vec_prefix), > - sizeof (void *), true > - PASS_MEM_STAT); > -} > - > -/* As for vec_gc_p_reserve, but for object vectors. The vector's > - trailing array is at VEC_OFFSET offset and consists of ELT_SIZE > - sized elements. */ > - > -void * > -vec_gc_o_reserve (void *vec, int reserve, size_t vec_offset, size_t elt_size > - MEM_STAT_DECL) > -{ > - return vec_gc_o_reserve_1 (vec, reserve, vec_offset, elt_size, false > - PASS_MEM_STAT); > -} > - > -/* As for vec_gc_p_reserve_exact, but for object vectors. The > - vector's trailing array is at VEC_OFFSET offset and consists of > - ELT_SIZE sized elements. */ > - > -void * > -vec_gc_o_reserve_exact (void *vec, int reserve, size_t vec_offset, > - size_t elt_size MEM_STAT_DECL) > -{ > - return vec_gc_o_reserve_1 (vec, reserve, vec_offset, elt_size, true > - PASS_MEM_STAT); > -} > > /* As for vec_gc_o_reserve_1, but for heap allocated vectors. */ > > -static void * > +void * > vec_heap_o_reserve_1 (void *vec, int reserve, size_t vec_offset, > size_t elt_size, bool exact MEM_STAT_DECL) > { > @@ -334,47 +284,6 @@ vec_heap_o_reserve_1 (void *vec, int reserve, size_t vec_offset, > return vec; > } > > -/* As for vec_gc_p_reserve, but for heap allocated vectors. */ > - > -void * > -vec_heap_p_reserve (void *vec, int reserve MEM_STAT_DECL) > -{ > - return vec_heap_o_reserve_1 (vec, reserve, > - sizeof (struct vec_prefix), > - sizeof (void *), false > - PASS_MEM_STAT); > -} > - > -/* As for vec_gc_p_reserve_exact, but for heap allocated vectors. */ > - > -void * > -vec_heap_p_reserve_exact (void *vec, int reserve MEM_STAT_DECL) > -{ > - return vec_heap_o_reserve_1 (vec, reserve, > - sizeof (struct vec_prefix), > - sizeof (void *), true > - PASS_MEM_STAT); > -} > - > -/* As for vec_gc_o_reserve, but for heap allocated vectors. */ > - > -void * > -vec_heap_o_reserve (void *vec, int reserve, size_t vec_offset, size_t elt_size > - MEM_STAT_DECL) > -{ > - return vec_heap_o_reserve_1 (vec, reserve, vec_offset, elt_size, false > - PASS_MEM_STAT); > -} > - > -/* As for vec_gc_o_reserve_exact, but for heap allocated vectors. */ > - > -void * > -vec_heap_o_reserve_exact (void *vec, int reserve, size_t vec_offset, > - size_t elt_size MEM_STAT_DECL) > -{ > - return vec_heap_o_reserve_1 (vec, reserve, vec_offset, elt_size, true > - PASS_MEM_STAT); > -} > > /* Stack vectors are a little different. VEC_alloc turns into a call > to vec_stack_p_reserve_exact1 and passes in space allocated via a > @@ -456,28 +365,6 @@ vec_stack_o_reserve_1 (void *vec, int reserve, size_t vec_offset, > /* Grow a vector allocated on the stack. */ > > void * > -vec_stack_p_reserve (void *vec, int reserve MEM_STAT_DECL) > -{ > - return vec_stack_o_reserve_1 (vec, reserve, > - sizeof (struct vec_prefix), > - sizeof (void *), false > - PASS_MEM_STAT); > -} > - > -/* Exact version of vec_stack_p_reserve. */ > - > -void * > -vec_stack_p_reserve_exact (void *vec, int reserve MEM_STAT_DECL) > -{ > - return vec_stack_o_reserve_1 (vec, reserve, > - sizeof (struct vec_prefix), > - sizeof (void *), true > - PASS_MEM_STAT); > -} > - > -/* Like vec_stack_p_reserve, but for objects. */ > - > -void * > vec_stack_o_reserve (void *vec, int reserve, size_t vec_offset, > size_t elt_size MEM_STAT_DECL) > { > @@ -485,7 +372,7 @@ vec_stack_o_reserve (void *vec, int reserve, size_t vec_offset, > PASS_MEM_STAT); > } > > -/* Like vec_stack_p_reserve_exact, but for objects. */ > +/* Exact version of vec_stack_o_reserve. */ > > void * > vec_stack_o_reserve_exact (void *vec, int reserve, size_t vec_offset, > diff --git a/gcc/vec.h b/gcc/vec.h > index d477958..cc7e819 100644 > --- a/gcc/vec.h > +++ b/gcc/vec.h > @@ -1,7 +1,8 @@ > /* Vector API for GNU compiler. > - Copyright (C) 2004, 2005, 2007, 2008, 2009, 2010 > + Copyright (C) 2004, 2005, 2007, 2008, 2009, 2010, 2011, 2012 > 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. > > @@ -133,6 +134,86 @@ along with GCC; see the file COPYING3. If not see > > */ > > +#if ENABLE_CHECKING > +#define VEC_CHECK_INFO ,__FILE__,__LINE__,__FUNCTION__ > +#define VEC_CHECK_DECL ,const char *file_,unsigned line_,const char *function_ > +#define VEC_CHECK_PASS ,file_,line_,function_ > + > +#define VEC_ASSERT(EXPR,OP,T,A) \ > + (void)((EXPR) ? 0 : (VEC_ASSERT_FAIL(OP,VEC(T,A)), 0)) > + > +extern void vec_assert_fail (const char *, const char * VEC_CHECK_DECL) > + ATTRIBUTE_NORETURN; > +#define VEC_ASSERT_FAIL(OP,VEC) vec_assert_fail (OP,#VEC VEC_CHECK_PASS) > +#else > +#define VEC_CHECK_INFO > +#define VEC_CHECK_DECL > +#define VEC_CHECK_PASS > +#define VEC_ASSERT(EXPR,OP,T,A) (void)(EXPR) > +#endif > + > +#define VEC(T,A) vec_t<T> > + > +enum vec_allocation_t { heap, gc, stack }; > + > +struct GTY(()) vec_prefix > +{ > + unsigned num; > + unsigned alloc; > +}; > + > +/* Vector type, user visible. */ > +template<typename T> > +struct GTY(()) vec_t > +{ > + vec_prefix prefix; > + T GTY((length ("%h.prefix.num"))) vec[1]; > +}; > + > +/* FIXME cxx-conversion. Remove these definitions and update all > + calling sites. */ > +/* Vector of integer-like object. */ > +#define DEF_VEC_I(T) struct vec_swallow_trailing_semi > +#define DEF_VEC_ALLOC_I(T,A) struct vec_swallow_trailing_semi > + > +/* Vector of pointer to object. */ > +#define DEF_VEC_P(T) struct vec_swallow_trailing_semi > +#define DEF_VEC_ALLOC_P(T,A) struct vec_swallow_trailing_semi > + > +/* Vector of object. */ > +#define DEF_VEC_O(T) struct vec_swallow_trailing_semi > +#define DEF_VEC_ALLOC_O(T,A) struct vec_swallow_trailing_semi > + > +/* Vectors on the stack. */ > +#define DEF_VEC_ALLOC_P_STACK(T) struct vec_swallow_trailing_semi > +#define DEF_VEC_ALLOC_O_STACK(T) struct vec_swallow_trailing_semi > +#define DEF_VEC_ALLOC_I_STACK(T) struct vec_swallow_trailing_semi > + > + > +/* Support functions for stack vectors. */ > +extern void *vec_stack_p_reserve_exact_1 (int, void *); > +extern void *vec_stack_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL); > +extern void *vec_stack_o_reserve_exact (void *, int, size_t, size_t > + MEM_STAT_DECL); > +extern void vec_stack_free (void *); > + > +/* Reallocate an array of elements with prefix. */ > +template<typename T, enum vec_allocation_t A> > +extern vec_t<T> *vec_reserve (vec_t<T> *, int MEM_STAT_DECL); > + > +template<typename T, enum vec_allocation_t A> > +extern vec_t<T> *vec_reserve_exact (vec_t<T> *, int MEM_STAT_DECL); > + > +extern void dump_vec_loc_statistics (void); > +extern void ggc_free (void *); > +#ifdef GATHER_STATISTICS > +void vec_heap_free (void *); > +#else > +/* Avoid problems with frontends that #define free(x). */ > +#define vec_heap_free(V) (free) (V) > +#endif > + > + > /* Macros to invoke API calls. A single macro works for both pointer > and object vectors, but the argument and return types might well be > different. In each macro, T is the typedef of the vector elements, > @@ -147,7 +228,14 @@ along with GCC; see the file COPYING3. If not see > Return the number of active elements in V. V can be NULL, in which > case zero is returned. */ > > -#define VEC_length(T,V) (VEC_OP(T,base,length)(VEC_BASE(V))) > +#define VEC_length(T,V) (VEC_length_1<T> (V)) > + > +template<typename T> > +static inline unsigned > +VEC_length_1 (const vec_t<T> *vec_) > +{ > + return vec_ ? vec_->prefix.num : 0; > +} > > > /* Check if vector is empty > @@ -155,7 +243,30 @@ along with GCC; see the file COPYING3. If not see > > Return nonzero if V is an empty vector (or V is NULL), zero otherwise. */ > > -#define VEC_empty(T,V) (VEC_length (T,V) == 0) > +#define VEC_empty(T,V) (VEC_empty_1<T> (V)) > + > +template<typename T> > +static inline bool > +VEC_empty_1 (const vec_t<T> *vec_) > +{ > + return VEC_length (T, vec_) == 0; > +} > + > + > +/* Get the address of the array of elements > + T *VEC_T_address (VEC(T) v) > + > + If you need to directly manipulate the array (for instance, you > + want to feed it to qsort), use this accessor. */ > + > +#define VEC_address(T,V) (VEC_address_1<T> (V)) > + > +template<typename T> > +static inline T * > +VEC_address_1 (vec_t<T> *vec_) > +{ > + return vec_ ? vec_->vec : 0; > +} > > > /* Get the final element of the vector. > @@ -165,16 +276,42 @@ along with GCC; see the file COPYING3. If not see > > Return the final element. V must not be empty. */ > > -#define VEC_last(T,V) (VEC_OP(T,base,last)(VEC_BASE(V) VEC_CHECK_INFO)) > +#define VEC_last(T,V) (VEC_last_1<T> (V VEC_CHECK_INFO)) > + > +template<typename T> > +static inline T& > +VEC_last_1 (vec_t<T> *vec_ VEC_CHECK_DECL) > +{ > + VEC_ASSERT (vec_ && vec_->prefix.num, "last", T, base); > + return vec_->vec[vec_->prefix.num - 1]; > +} > + > > /* Index into vector > T VEC_T_index(VEC(T) *v, unsigned ix); // Integer > T VEC_T_index(VEC(T) *v, unsigned ix); // Pointer > T *VEC_T_index(VEC(T) *v, unsigned ix); // Object > > - Return the IX'th element. If IX must be in the domain of V. */ > + Return the IX'th element. IX must be in the domain of V. */ > + > +#define VEC_index(T,V,I) (VEC_index_1<T> (V, I VEC_CHECK_INFO)) > + > +template<typename T> > +static inline T& > +VEC_index_1 (vec_t<T> *vec_, unsigned ix_ VEC_CHECK_DECL) > +{ > + VEC_ASSERT (vec_ && ix_ < vec_->prefix.num, "index", T, base); > + return vec_->vec[ix_]; > +} > + > +template<typename T> > +static inline const T& > +VEC_index_1 (const vec_t<T> *vec_, unsigned ix_ VEC_CHECK_DECL) > +{ > + VEC_ASSERT (vec_ && ix_ < vec_->prefix.num, "index", T, base); > + return vec_->vec[ix_]; > +} > > -#define VEC_index(T,V,I) (VEC_OP(T,base,index)(VEC_BASE(V),I VEC_CHECK_INFO)) > > /* Iterate over vector > int VEC_T_iterate(VEC(T) *v, unsigned ix, T &ptr); // Integer > @@ -188,7 +325,39 @@ along with GCC; see the file COPYING3. If not see > for (ix = 0; VEC_iterate(T,v,ix,ptr); ix++) > continue; */ > > -#define VEC_iterate(T,V,I,P) (VEC_OP(T,base,iterate)(VEC_BASE(V),I,&(P))) > +#define VEC_iterate(T,V,I,P) (VEC_iterate_1<T> (V, I, &(P))) > + > +template<typename T> > +static inline bool > +VEC_iterate_1 (const vec_t<T> *vec_, unsigned ix_, T *ptr) > +{ > + if (vec_ && ix_ < vec_->prefix.num) > + { > + *ptr = vec_->vec[ix_]; > + return true; > + } > + else > + { > + *ptr = 0; > + return false; > + } > +} > + > +template<typename T> > +static inline bool > +VEC_iterate_1 (vec_t<T> *vec_, unsigned ix_, T **ptr) > +{ > + if (vec_ && ix_ < vec_->prefix.num) > + { > + *ptr = &vec_->vec[ix_]; > + return true; > + } > + else > + { > + *ptr = 0; > + return false; > + } > +} > > /* Convenience macro for forward iteration. */ > > @@ -207,31 +376,99 @@ along with GCC; see the file COPYING3. If not see > VEC_iterate (T, (V), (I), (P)); \ > (I)--) > > + > +/* Use these to determine the required size and initialization of a > + vector embedded within another structure (as the final member). > + > + size_t VEC_T_embedded_size(int reserve); > + void VEC_T_embedded_init(VEC(T) *v, int reserve); > + > + These allow the caller to perform the memory allocation. */ > + > +#define VEC_embedded_size(T,N) (VEC_embedded_size_1<T> (N)) > + > +template<typename T> > +static inline size_t > +VEC_embedded_size_1 (int alloc_) > +{ > + return offsetof (vec_t<T>, vec) + alloc_ * sizeof (T); > +} > + > +#define VEC_embedded_init(T,O,N) (VEC_embedded_init_1<T> (O, N)) > + > +template<typename T> > +static inline void > +VEC_embedded_init_1 (vec_t<T> *vec_, int alloc_) > +{ > + vec_->prefix.num = 0; > + vec_->prefix.alloc = alloc_; > +} > + > + > /* Allocate new vector. > VEC(T,A) *VEC_T_A_alloc(int reserve); > > Allocate a new vector with space for RESERVE objects. If RESERVE > - is zero, NO vector is created. */ > + is zero, NO vector is created. > + > + 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. > + > + 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 VEC(TYPE,stack) vector from the function > + which allocated it. */ > + > +#define VEC_alloc(T,A,N) \ > + ((A == stack) \ > + ? VEC_alloc_1 (N, \ > + XALLOCAVAR (vec_t<T>, \ > + VEC_embedded_size_1<T> (N))) \ > + : VEC_alloc_1<T, A> (N MEM_STAT_INFO)) > + > +template<typename T, enum vec_allocation_t A> > +static inline vec_t<T> * > +VEC_alloc_1 (int alloc_ MEM_STAT_DECL) > +{ > + return vec_reserve_exact<T, A> (NULL, alloc_ PASS_MEM_STAT); > +} > + > +template<typename T> > +static inline vec_t<T> * > +VEC_alloc_1 (int alloc_, vec_t<T> *space) > +{ > + return (vec_t<T> *) vec_stack_p_reserve_exact_1 (alloc_, space); > +} > > -#define VEC_alloc(T,A,N) (VEC_OP(T,A,alloc)(N MEM_STAT_INFO)) > > /* Free a vector. > void VEC_T_A_free(VEC(T,A) *&); > > Free a vector and set it to NULL. */ > > -#define VEC_free(T,A,V) (VEC_OP(T,A,free)(&V)) > - > -/* Use these to determine the required size and initialization of a > - vector embedded within another structure (as the final member). > +#define VEC_free(T,A,V) (VEC_free_1<T, A> (&V)) > > - size_t VEC_T_embedded_size(int reserve); > - void VEC_T_embedded_init(VEC(T) *v, int reserve); > - > - These allow the caller to perform the memory allocation. */ > +template<typename T, enum vec_allocation_t A> > +static inline void > +VEC_free_1 (vec_t<T> **vec_) > +{ > + if (*vec_) > + { > + if (A == heap) > + vec_heap_free (*vec_); > + else if (A == gc) > + ggc_free (*vec_); > + else if (A == stack) > + vec_stack_free (*vec_); > + } > + *vec_ = NULL; > +} > > -#define VEC_embedded_size(T,N) (VEC_OP(T,base,embedded_size)(N)) > -#define VEC_embedded_init(T,O,N) (VEC_OP(T,base,embedded_init)(VEC_BASE(O),N)) > > /* Copy a vector. > VEC(T,A) *VEC_T_A_copy(VEC(T) *); > @@ -239,7 +476,24 @@ along with GCC; see the file COPYING3. If not see > Copy the live elements of a vector into a new vector. The new and > old vectors need not be allocated by the same mechanism. */ > > -#define VEC_copy(T,A,V) (VEC_OP(T,A,copy)(VEC_BASE(V) MEM_STAT_INFO)) > +#define VEC_copy(T,A,V) (VEC_copy_1<T, A> (V MEM_STAT_INFO)) > + > +template<typename T, enum vec_allocation_t A> > +static inline vec_t<T> * > +VEC_copy_1 (vec_t<T> *vec_ MEM_STAT_DECL) > +{ > + size_t len_ = vec_ ? vec_->prefix.num : 0; > + vec_t<T> *new_vec_ = NULL; > + > + if (len_) > + { > + new_vec_ = vec_reserve_exact<T, A> (NULL, len_ PASS_MEM_STAT); > + new_vec_->prefix.num = len_; > + memcpy (new_vec_->vec, vec_->vec, sizeof (T) * len_); > + } > + return new_vec_; > +} > + > > /* Determine if a vector has additional capacity. > > @@ -251,8 +505,18 @@ along with GCC; see the file COPYING3. If not see > nonzero in exactly the same circumstances that VEC_T_reserve > will. */ > > -#define VEC_space(T,V,R) \ > - (VEC_OP(T,base,space)(VEC_BASE(V),R VEC_CHECK_INFO)) > +#define VEC_space(T,V,R) (VEC_space_1<T> (V, R VEC_CHECK_INFO)) > + > +template<typename T> > +static inline int > +VEC_space_1 (vec_t<T> *vec_, int alloc_ VEC_CHECK_DECL) > +{ > + VEC_ASSERT (alloc_ >= 0, "space", T, base); > + return vec_ > + ? vec_->prefix.alloc - vec_->prefix.num >= (unsigned)alloc_ > + : !alloc_; > +} > + > > /* Reserve space. > int VEC_T_A_reserve(VEC(T,A) *&v, int reserve); > @@ -263,7 +527,20 @@ along with GCC; see the file COPYING3. If not see > occurred. */ > > #define VEC_reserve(T,A,V,R) \ > - (VEC_OP(T,A,reserve)(&(V),R VEC_CHECK_INFO MEM_STAT_INFO)) > + (VEC_reserve_1<T, A> (&(V), (int)(R) VEC_CHECK_INFO MEM_STAT_INFO)) > + > +template<typename T, enum vec_allocation_t A> > +static inline int > +VEC_reserve_1 (vec_t<T> **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) > +{ > + int extend = !VEC_space_1 (*vec_, alloc_ VEC_CHECK_PASS); > + > + if (extend) > + *vec_ = vec_reserve<T, A> (*vec_, alloc_ PASS_MEM_STAT); > + > + return extend; > +} > + > > /* Reserve space exactly. > int VEC_T_A_reserve_exact(VEC(T,A) *&v, int reserve); > @@ -274,7 +551,20 @@ along with GCC; see the file COPYING3. If not see > occurred. */ > > #define VEC_reserve_exact(T,A,V,R) \ > - (VEC_OP(T,A,reserve_exact)(&(V),R VEC_CHECK_INFO MEM_STAT_INFO)) > + (VEC_reserve_exact_1<T, A> (&(V), R VEC_CHECK_INFO MEM_STAT_INFO)) > + > +template<typename T, enum vec_allocation_t A> > +static inline int > +VEC_reserve_exact_1 (vec_t<T> **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) > +{ > + int extend = !VEC_space_1 (*vec_, alloc_ VEC_CHECK_PASS); > + > + if (extend) > + *vec_ = vec_reserve_exact<T, A> (*vec_, alloc_ PASS_MEM_STAT); > + > + return extend; > +} > + > > /* Copy elements with no reallocation > void VEC_T_splice (VEC(T) *dst, VEC(T) *src); // Integer > @@ -286,8 +576,23 @@ along with GCC; see the file COPYING3. If not see > often will be. DST is assumed to have sufficient headroom > available. */ > > -#define VEC_splice(T,DST,SRC) \ > - (VEC_OP(T,base,splice)(VEC_BASE(DST), VEC_BASE(SRC) VEC_CHECK_INFO)) > +#define VEC_splice(T,DST,SRC) (VEC_splice_1<T> (DST, SRC VEC_CHECK_INFO)) > + > +template<typename T> > +static inline void > +VEC_splice_1 (vec_t<T> *dst_, vec_t<T> *src_ VEC_CHECK_DECL) > +{ > + if (src_) > + { > + unsigned len_ = src_->prefix.num; > + VEC_ASSERT (dst_->prefix.num + len_ <= dst_->prefix.alloc, "splice", > + T, base); > + > + memcpy (&dst_->vec[dst_->prefix.num], &src_->vec[0], len_ * sizeof (T)); > + dst_->prefix.num += len_; > + } > +} > + > > /* Copy elements with reallocation > void VEC_T_safe_splice (VEC(T,A) *&dst, VEC(T) *src); // Integer > @@ -300,7 +605,21 @@ along with GCC; see the file COPYING3. If not see > reallocated if needed. */ > > #define VEC_safe_splice(T,A,DST,SRC) \ > - (VEC_OP(T,A,safe_splice)(&(DST), VEC_BASE(SRC) VEC_CHECK_INFO MEM_STAT_INFO)) > + (VEC_safe_splice_1<T, A> (&(DST), SRC VEC_CHECK_INFO MEM_STAT_INFO)) > + > +template<typename T, enum vec_allocation_t A> > +static inline void > +VEC_safe_splice_1 (vec_t<T> **dst_, vec_t<T> *src_ VEC_CHECK_DECL MEM_STAT_DECL) > +{ > + if (src_) > + { > + VEC_reserve_exact_1<T, A> (dst_, src_->prefix.num > + VEC_CHECK_PASS MEM_STAT_INFO); > + > + VEC_splice_1 (*dst_, src_ VEC_CHECK_PASS); > + } > +} > + > > /* Push object with no reallocation > T *VEC_T_quick_push (VEC(T) *v, T obj); // Integer > @@ -312,8 +631,31 @@ along with GCC; see the file COPYING3. If not see > case NO initialization is performed. There must > be sufficient space in the vector. */ > > -#define VEC_quick_push(T,V,O) \ > - (VEC_OP(T,base,quick_push)(VEC_BASE(V),O VEC_CHECK_INFO)) > +#define VEC_quick_push(T,V,O) (VEC_quick_push_1<T> (V, O VEC_CHECK_INFO)) > + > +template<typename T> > +static inline T & > +VEC_quick_push_1 (vec_t<T> *vec_, T obj_ VEC_CHECK_DECL) > +{ > + VEC_ASSERT (vec_->prefix.num < vec_->prefix.alloc, "push", T, base); > + vec_->vec[vec_->prefix.num] = obj_; > + T &val_ = vec_->vec[vec_->prefix.num]; > + vec_->prefix.num++; > + return val_; > +} > + > +template<typename T> > +static inline T * > +VEC_quick_push_1 (vec_t<T> *vec_, const T *ptr_ VEC_CHECK_DECL) > +{ > + T *slot_; > + VEC_ASSERT (vec_->prefix.num < vec_->prefix.alloc, "push", T, base); > + slot_ = &vec_->vec[vec_->prefix.num++]; > + if (ptr_) > + *slot_ = *ptr_; > + return slot_; > +} > + > > /* Push object with reallocation > T *VEC_T_A_safe_push (VEC(T,A) *&v, T obj); // Integer > @@ -325,7 +667,24 @@ along with GCC; see the file COPYING3. If not see > case NO initialization is performed. Reallocates V, if needed. */ > > #define VEC_safe_push(T,A,V,O) \ > - (VEC_OP(T,A,safe_push)(&(V),O VEC_CHECK_INFO MEM_STAT_INFO)) > + (VEC_safe_push_1<T, A> (&(V), O VEC_CHECK_INFO MEM_STAT_INFO)) > + > +template<typename T, enum vec_allocation_t A> > +static inline T & > +VEC_safe_push_1 (vec_t<T> **vec_, T obj_ VEC_CHECK_DECL MEM_STAT_DECL) > +{ > + VEC_reserve_1<T, A> (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); > + return VEC_quick_push_1 (*vec_, obj_ VEC_CHECK_PASS); > +} > + > +template<typename T, enum vec_allocation_t A> > +static inline T * > +VEC_safe_push_1 (vec_t<T> **vec_, const T *ptr_ VEC_CHECK_DECL MEM_STAT_DECL) > +{ > + VEC_reserve_1<T, A> (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); > + return VEC_quick_push_1 (*vec_, ptr_ VEC_CHECK_PASS); > +} > + > > /* Pop element off end > T VEC_T_pop (VEC(T) *v); // Integer > @@ -335,7 +694,16 @@ along with GCC; see the file COPYING3. If not see > Pop the last element off the end. Returns the element popped, for > pointer vectors. */ > > -#define VEC_pop(T,V) (VEC_OP(T,base,pop)(VEC_BASE(V) VEC_CHECK_INFO)) > +#define VEC_pop(T,V) (VEC_pop_1<T> (V VEC_CHECK_INFO)) > + > +template<typename T> > +static inline T& > +VEC_pop_1 (vec_t<T> *vec_ VEC_CHECK_DECL) > +{ > + VEC_ASSERT (vec_->prefix.num, "pop", T, base); > + return vec_->vec[--vec_->prefix.num]; > +} > + > > /* Truncate to specific length > void VEC_T_truncate (VEC(T) *v, unsigned len); > @@ -343,8 +711,18 @@ along with GCC; see the file COPYING3. If not see > Set the length as specified. The new length must be less than or > equal to the current length. This is an O(1) operation. */ > > -#define VEC_truncate(T,V,I) \ > - (VEC_OP(T,base,truncate)(VEC_BASE(V),I VEC_CHECK_INFO)) > +#define VEC_truncate(T,V,I) \ > + (VEC_truncate_1<T> (V, (unsigned)(I) VEC_CHECK_INFO)) > + > +template<typename T> > +static inline void > +VEC_truncate_1 (vec_t<T> *vec_, unsigned size_ VEC_CHECK_DECL) > +{ > + VEC_ASSERT (vec_ ? vec_->prefix.num >= size_ : !size_, "truncate", T, base); > + if (vec_) > + vec_->prefix.num = size_; > +} > + > > /* Grow to a specific length. > void VEC_T_A_safe_grow (VEC(T,A) *&v, int len); > @@ -354,7 +732,20 @@ along with GCC; see the file COPYING3. If not see > uninitialized. */ > > #define VEC_safe_grow(T,A,V,I) \ > - (VEC_OP(T,A,safe_grow)(&(V),I VEC_CHECK_INFO MEM_STAT_INFO)) > + (VEC_safe_grow_1<T, A> (&(V), (int)(I) VEC_CHECK_INFO MEM_STAT_INFO)) > + > +template<typename T, enum vec_allocation_t A> > +static inline void > +VEC_safe_grow_1 (vec_t<T> **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) > +{ > + VEC_ASSERT (size_ >= 0 && VEC_length (T, *vec_) <= (unsigned)size_, > + "grow", T, A); > + VEC_reserve_exact_1<T, A> (vec_, > + size_ - (int)(*vec_ ? (*vec_)->prefix.num : 0) > + VEC_CHECK_PASS PASS_MEM_STAT); > + (*vec_)->prefix.num = size_; > +} > + > > /* Grow to a specific length. > void VEC_T_A_safe_grow_cleared (VEC(T,A) *&v, int len); > @@ -363,8 +754,21 @@ along with GCC; see the file COPYING3. If not see > long or longer than the current length. The new elements are > initialized to zero. */ > > -#define VEC_safe_grow_cleared(T,A,V,I) \ > - (VEC_OP(T,A,safe_grow_cleared)(&(V),I VEC_CHECK_INFO MEM_STAT_INFO)) > +#define VEC_safe_grow_cleared(T,A,V,I) \ > + (VEC_safe_grow_cleared_1<T,A> (&(V), (int)(I) \ > + VEC_CHECK_INFO MEM_STAT_INFO)) > + > +template<typename T, enum vec_allocation_t A> > +static inline void > +VEC_safe_grow_cleared_1 (vec_t<T> **vec_, int size_ VEC_CHECK_DECL > + MEM_STAT_DECL) > +{ > + int oldsize = VEC_length (T, *vec_); > + VEC_safe_grow_1<T, A> (vec_, size_ VEC_CHECK_PASS PASS_MEM_STAT); > + memset (&(VEC_address (T, *vec_)[oldsize]), 0, > + sizeof (T) * (size_ - oldsize)); > +} > + > > /* Replace element > T VEC_T_replace (VEC(T) *v, unsigned ix, T val); // Integer > @@ -378,20 +782,57 @@ along with GCC; see the file COPYING3. If not see > performed. */ > > #define VEC_replace(T,V,I,O) \ > - (VEC_OP(T,base,replace)(VEC_BASE(V),I,O VEC_CHECK_INFO)) > + (VEC_replace_1<T> (V, (unsigned)(I), O VEC_CHECK_INFO)) > + > +template<typename T> > +static inline T& > +VEC_replace_1 (vec_t<T> *vec_, unsigned ix_, T obj_ VEC_CHECK_DECL) > +{ > + VEC_ASSERT (ix_ < vec_->prefix.num, "replace", T, base); > + vec_->vec[ix_] = obj_; > + return vec_->vec[ix_]; > +} > + > > /* Insert object with no reallocation > - T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Integer > - T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Pointer > - T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T *val); // Object > + void VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Integer > + void VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Pointer > + void VEC_T_quick_insert (VEC(T) *v, unsigned ix, T *val); // Object > > - Insert an element, VAL, at the IXth position of V. Return a pointer > - to the slot created. For vectors of object, the new value can be > - NULL, in which case no initialization of the inserted slot takes > - place. There must be sufficient space. */ > + Insert an element, VAL, at the IXth position of V. For vectors of > + object, the new value can be NULL, in which case no initialization > + of the inserted slot takes place. There must be sufficient space. */ > > #define VEC_quick_insert(T,V,I,O) \ > - (VEC_OP(T,base,quick_insert)(VEC_BASE(V),I,O VEC_CHECK_INFO)) > + (VEC_quick_insert_1<T> (V,I,O VEC_CHECK_INFO)) > + > +template<typename T> > +static inline void > +VEC_quick_insert_1 (vec_t<T> *vec_, unsigned ix_, T obj_ VEC_CHECK_DECL) > +{ > + T *slot_; > + > + VEC_ASSERT (vec_->prefix.num < vec_->prefix.alloc, "insert", T, base); > + VEC_ASSERT (ix_ <= vec_->prefix.num, "insert", T, base); > + slot_ = &vec_->vec[ix_]; > + memmove (slot_ + 1, slot_, (vec_->prefix.num++ - ix_) * sizeof (T)); > + *slot_ = obj_; > +} > + > +template<typename T> > +static inline void > +VEC_quick_insert_1 (vec_t<T> *vec_, unsigned ix_, const T *ptr_ VEC_CHECK_DECL) > +{ > + T *slot_; > + > + VEC_ASSERT (vec_->prefix.num < vec_->prefix.alloc, "insert", T, base); > + VEC_ASSERT (ix_ <= vec_->prefix.num, "insert", T, base); > + slot_ = &vec_->vec[ix_]; > + memmove (slot_ + 1, slot_, (vec_->prefix.num++ - ix_) * sizeof (T)); > + if (ptr_) > + *slot_ = *ptr_; > +} > + > > /* Insert object with reallocation > T *VEC_T_A_safe_insert (VEC(T,A) *&v, unsigned ix, T val); // Integer > @@ -404,31 +845,70 @@ along with GCC; see the file COPYING3. If not see > place. Reallocate V, if necessary. */ > > #define VEC_safe_insert(T,A,V,I,O) \ > - (VEC_OP(T,A,safe_insert)(&(V),I,O VEC_CHECK_INFO MEM_STAT_INFO)) > + (VEC_safe_insert_1<T, A> (&(V),I,O VEC_CHECK_INFO MEM_STAT_INFO)) > + > +template<typename T, enum vec_allocation_t A> > +static inline void > +VEC_safe_insert_1 (vec_t<T> **vec_, unsigned ix_, T obj_ > + VEC_CHECK_DECL MEM_STAT_DECL) > +{ > + VEC_reserve_1<T, A> (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); > + VEC_quick_insert_1 (*vec_, ix_, obj_ VEC_CHECK_PASS); > +} > + > +template<typename T, enum vec_allocation_t A> > +static inline void > +VEC_safe_insert_1 (vec_t<T> **vec_, unsigned ix_, T *ptr_ > + VEC_CHECK_DECL MEM_STAT_DECL) > +{ > + VEC_reserve_1<T, A> (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); > + VEC_quick_insert_1 (*vec_, ix_, ptr_ VEC_CHECK_PASS); > +} > + > + > > /* Remove element retaining order > - T VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Integer > - T VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Pointer > + void VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Integer > + void VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Pointer > void VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Object > > Remove an element from the IXth position of V. Ordering of > - remaining elements is preserved. For pointer vectors returns the > - removed object. This is an O(N) operation due to a memmove. */ > + remaining elements is preserved. This is an O(N) operation due to > + a memmove. */ > > #define VEC_ordered_remove(T,V,I) \ > - (VEC_OP(T,base,ordered_remove)(VEC_BASE(V),I VEC_CHECK_INFO)) > + (VEC_ordered_remove_1<T> (V,I VEC_CHECK_INFO)) > + > +template<typename T> > +static inline void > +VEC_ordered_remove_1 (vec_t<T> *vec_, unsigned ix_ VEC_CHECK_DECL) > +{ > + T *slot_; > + VEC_ASSERT (ix_ < vec_->prefix.num, "remove", T, base); > + slot_ = &vec_->vec[ix_]; > + memmove (slot_, slot_ + 1, (--vec_->prefix.num - ix_) * sizeof (T)); > +} > + > > /* Remove element destroying order > - T VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Integer > - T VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Pointer > + void VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Integer > + void VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Pointer > void VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Object > > - Remove an element from the IXth position of V. Ordering of > - remaining elements is destroyed. For pointer vectors returns the > - removed object. This is an O(1) operation. */ > + Remove an element from the IXth position of V. Ordering of > + remaining elements is destroyed. This is an O(1) operation. */ > > #define VEC_unordered_remove(T,V,I) \ > - (VEC_OP(T,base,unordered_remove)(VEC_BASE(V),I VEC_CHECK_INFO)) > + (VEC_unordered_remove_1<T> (V,I VEC_CHECK_INFO)) > + > +template<typename T> > +static inline void > +VEC_unordered_remove_1 (vec_t<T> *vec_, unsigned ix_ VEC_CHECK_DECL) > +{ > + VEC_ASSERT (ix_ < vec_->prefix.num, "remove", T, base); > + vec_->vec[ix_] = vec_->vec[--vec_->prefix.num]; > +} > + > > /* Remove a block of elements > void VEC_T_block_remove (VEC(T) *v, unsigned ix, unsigned len); > @@ -437,22 +917,27 @@ along with GCC; see the file COPYING3. If not see > This is an O(N) operation due to memmove. */ > > #define VEC_block_remove(T,V,I,L) \ > - (VEC_OP(T,base,block_remove)(VEC_BASE(V),I,L VEC_CHECK_INFO)) > + (VEC_block_remove_1<T> (V, I, L VEC_CHECK_INFO)) > > -/* Get the address of the array of elements > - T *VEC_T_address (VEC(T) v) > - > - If you need to directly manipulate the array (for instance, you > - want to feed it to qsort), use this accessor. */ > +template<typename T> > +static inline void > +VEC_block_remove_1 (vec_t<T> *vec_, unsigned ix_, unsigned len_ VEC_CHECK_DECL) > +{ > + T *slot_; > + VEC_ASSERT (ix_ + len_ <= vec_->prefix.num, "block_remove", T, base); > + slot_ = &vec_->vec[ix_]; > + vec_->prefix.num -= len_; > + memmove (slot_, slot_ + len_, (vec_->prefix.num - ix_) * sizeof (T)); > +} > > -#define VEC_address(T,V) (VEC_OP(T,base,address)(VEC_BASE(V))) > > /* Conveniently sort the contents of the vector with qsort. > void VEC_qsort (VEC(T) *v, int (*cmp_func)(const void *, const void *)) */ > > -#define VEC_qsort(T,V,CMP) qsort(VEC_address (T,V), VEC_length(T,V), \ > +#define VEC_qsort(T,V,CMP) qsort(VEC_address (T, V), VEC_length (T, V), \ > sizeof (T), CMP) > > + > /* Find the first index in the vector not less than the object. > unsigned VEC_T_lower_bound (VEC(T) *v, const T val, > bool (*lessthan) (const T, const T)); // Integer > @@ -465,944 +950,140 @@ along with GCC; see the file COPYING3. If not see > changing the ordering of V. LESSTHAN is a function that returns > true if the first argument is strictly less than the second. */ > > -#define VEC_lower_bound(T,V,O,LT) \ > - (VEC_OP(T,base,lower_bound)(VEC_BASE(V),O,LT VEC_CHECK_INFO)) > - > -/* Reallocate an array of elements with prefix. */ > -extern void *vec_gc_p_reserve (void *, int MEM_STAT_DECL); > -extern void *vec_gc_p_reserve_exact (void *, int MEM_STAT_DECL); > -extern void *vec_gc_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL); > -extern void *vec_gc_o_reserve_exact (void *, int, size_t, size_t > - MEM_STAT_DECL); > -extern void ggc_free (void *); > -#define vec_gc_free(V) ggc_free (V) > -extern void *vec_heap_p_reserve (void *, int MEM_STAT_DECL); > -extern void *vec_heap_p_reserve_exact (void *, int MEM_STAT_DECL); > -extern void *vec_heap_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL); > -extern void *vec_heap_o_reserve_exact (void *, int, size_t, size_t > - MEM_STAT_DECL); > -extern void dump_vec_loc_statistics (void); > -#ifdef GATHER_STATISTICS > -void vec_heap_free (void *); > -#else > -/* Avoid problems with frontends that #define free(x). */ > -#define vec_heap_free(V) (free) (V) > -#endif > - > -#if ENABLE_CHECKING > -#define VEC_CHECK_INFO ,__FILE__,__LINE__,__FUNCTION__ > -#define VEC_CHECK_DECL ,const char *file_,unsigned line_,const char *function_ > -#define VEC_CHECK_PASS ,file_,line_,function_ > +#define VEC_lower_bound(T,V,O,LT) \ > + (VEC_lower_bound_1<T> (V, O, LT VEC_CHECK_INFO)) > > -#define VEC_ASSERT(EXPR,OP,T,A) \ > - (void)((EXPR) ? 0 : (VEC_ASSERT_FAIL(OP,VEC(T,A)), 0)) > - > -extern void vec_assert_fail (const char *, const char * VEC_CHECK_DECL) > - ATTRIBUTE_NORETURN; > -#define VEC_ASSERT_FAIL(OP,VEC) vec_assert_fail (OP,#VEC VEC_CHECK_PASS) > -#else > -#define VEC_CHECK_INFO > -#define VEC_CHECK_DECL > -#define VEC_CHECK_PASS > -#define VEC_ASSERT(EXPR,OP,T,A) (void)(EXPR) > -#endif > - > -/* Note: gengtype has hardwired knowledge of the expansions of the > - VEC, DEF_VEC_*, and DEF_VEC_ALLOC_* macros. If you change the > - expansions of these macros you may need to change gengtype too. */ > - > -typedef struct GTY(()) vec_prefix > +template<typename T> > +static inline unsigned > +VEC_lower_bound_1 (vec_t<T> *vec_, T obj_, > + bool (*lessthan_)(T, T) VEC_CHECK_DECL) > { > - unsigned num; > - unsigned alloc; > -} vec_prefix; > - > -#define VEC(T,A) VEC_##T##_##A > -#define VEC_OP(T,A,OP) VEC_##T##_##A##_##OP > - > -/* Base of vector type, not user visible. */ > -#define VEC_T(T,B) \ > -typedef struct VEC(T,B) \ > -{ \ > - struct vec_prefix prefix; \ > - T vec[1]; \ > -} VEC(T,B) > - > -#define VEC_T_GTY(T,B) \ > -typedef struct GTY(()) VEC(T,B) \ > -{ \ > - struct vec_prefix prefix; \ > - T GTY ((length ("%h.prefix.num"))) vec[1]; \ > -} VEC(T,B) > - > -/* Derived vector type, user visible. */ > -#define VEC_TA_GTY(T,B,A,GTY) \ > -typedef struct GTY VEC(T,A) \ > -{ \ > - VEC(T,B) base; \ > -} VEC(T,A) > - > -#define VEC_TA(T,B,A) \ > -typedef struct VEC(T,A) \ > -{ \ > - VEC(T,B) base; \ > -} VEC(T,A) > - > -/* Convert to base type. */ > -#if GCC_VERSION >= 4000 > -#define VEC_BASE(P) \ > - ((offsetof (__typeof (*P), base) == 0 || (P)) ? &(P)->base : 0) > -#else > -#define VEC_BASE(P) ((P) ? &(P)->base : 0) > -#endif > - > -/* Vector of integer-like object. */ > -#define DEF_VEC_I(T) \ > -static inline void VEC_OP (T,must_be,integral_type) (void) \ > -{ \ > - (void)~(T)0; \ > -} \ > - \ > -VEC_T(T,base); \ > -VEC_TA(T,base,none); \ > -DEF_VEC_FUNC_P(T) \ > -struct vec_swallow_trailing_semi > -#define DEF_VEC_ALLOC_I(T,A) \ > -VEC_TA(T,base,A); \ > -DEF_VEC_ALLOC_FUNC_I(T,A) \ > -DEF_VEC_NONALLOC_FUNCS_I(T,A) \ > -struct vec_swallow_trailing_semi > - > -/* Vector of pointer to object. */ > -#define DEF_VEC_P(T) \ > -static inline void VEC_OP (T,must_be,pointer_type) (void) \ > -{ \ > - (void)((T)1 == (void *)1); \ > -} \ > - \ > -VEC_T_GTY(T,base); \ > -VEC_TA(T,base,none); \ > -DEF_VEC_FUNC_P(T) \ > -struct vec_swallow_trailing_semi > -#define DEF_VEC_ALLOC_P(T,A) \ > -VEC_TA(T,base,A); \ > -DEF_VEC_ALLOC_FUNC_P(T,A) \ > -DEF_VEC_NONALLOC_FUNCS_P(T,A) \ > -struct vec_swallow_trailing_semi > - > -#define DEF_VEC_FUNC_P(T) \ > -static inline unsigned VEC_OP (T,base,length) (const VEC(T,base) *vec_) \ > -{ \ > - return vec_ ? vec_->prefix.num : 0; \ > -} \ > - \ > -static inline T VEC_OP (T,base,last) \ > - (const VEC(T,base) *vec_ VEC_CHECK_DECL) \ > -{ \ > - VEC_ASSERT (vec_ && vec_->prefix.num, "last", T, base); \ > - \ > - return vec_->vec[vec_->prefix.num - 1]; \ > -} \ > - \ > -static inline T VEC_OP (T,base,index) \ > - (const VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \ > -{ \ > - VEC_ASSERT (vec_ && ix_ < vec_->prefix.num, "index", T, base); \ > - \ > - return vec_->vec[ix_]; \ > -} \ > - \ > -static inline int VEC_OP (T,base,iterate) \ > - (const VEC(T,base) *vec_, unsigned ix_, T *ptr) \ > -{ \ > - if (vec_ && ix_ < vec_->prefix.num) \ > - { \ > - *ptr = vec_->vec[ix_]; \ > - return 1; \ > - } \ > - else \ > - { \ > - *ptr = (T) 0; \ > - return 0; \ > - } \ > -} \ > - \ > -static inline size_t VEC_OP (T,base,embedded_size) \ > - (int alloc_) \ > -{ \ > - return offsetof (VEC(T,base),vec) + alloc_ * sizeof(T); \ > -} \ > - \ > -static inline void VEC_OP (T,base,embedded_init) \ > - (VEC(T,base) *vec_, int alloc_) \ > -{ \ > - vec_->prefix.num = 0; \ > - vec_->prefix.alloc = alloc_; \ > -} \ > - \ > -static inline int VEC_OP (T,base,space) \ > - (VEC(T,base) *vec_, int alloc_ VEC_CHECK_DECL) \ > -{ \ > - VEC_ASSERT (alloc_ >= 0, "space", T, base); \ > - return vec_ ? vec_->prefix.alloc - vec_->prefix.num >= (unsigned)alloc_ : !alloc_; \ > -} \ > - \ > -static inline void VEC_OP(T,base,splice) \ > - (VEC(T,base) *dst_, VEC(T,base) *src_ VEC_CHECK_DECL) \ > -{ \ > - if (src_) \ > - { \ > - unsigned len_ = src_->prefix.num; \ > - VEC_ASSERT (dst_->prefix.num + len_ <= dst_->prefix.alloc, "splice", T, base); \ > - \ > - memcpy (&dst_->vec[dst_->prefix.num], &src_->vec[0], len_ * sizeof (T)); \ > - dst_->prefix.num += len_; \ > - } \ > -} \ > - \ > -static inline T *VEC_OP (T,base,quick_push) \ > - (VEC(T,base) *vec_, T obj_ VEC_CHECK_DECL) \ > -{ \ > - T *slot_; \ > - \ > - VEC_ASSERT (vec_->prefix.num < vec_->prefix.alloc, "push", T, base); \ > - slot_ = &vec_->vec[vec_->prefix.num++]; \ > - *slot_ = obj_; \ > - \ > - return slot_; \ > -} \ > - \ > -static inline T VEC_OP (T,base,pop) (VEC(T,base) *vec_ VEC_CHECK_DECL) \ > -{ \ > - T obj_; \ > - \ > - VEC_ASSERT (vec_->prefix.num, "pop", T, base); \ > - obj_ = vec_->vec[--vec_->prefix.num]; \ > - \ > - return obj_; \ > -} \ > - \ > -static inline void VEC_OP (T,base,truncate) \ > - (VEC(T,base) *vec_, unsigned size_ VEC_CHECK_DECL) \ > -{ \ > - VEC_ASSERT (vec_ ? vec_->prefix.num >= size_ : !size_, "truncate", T, base); \ > - if (vec_) \ > - vec_->prefix.num = size_; \ > -} \ > - \ > -static inline T VEC_OP (T,base,replace) \ > - (VEC(T,base) *vec_, unsigned ix_, T obj_ VEC_CHECK_DECL) \ > -{ \ > - T old_obj_; \ > - \ > - VEC_ASSERT (ix_ < vec_->prefix.num, "replace", T, base); \ > - old_obj_ = vec_->vec[ix_]; \ > - vec_->vec[ix_] = obj_; \ > - \ > - return old_obj_; \ > -} \ > - \ > -static inline T *VEC_OP (T,base,quick_insert) \ > - (VEC(T,base) *vec_, unsigned ix_, T obj_ VEC_CHECK_DECL) \ > -{ \ > - T *slot_; \ > - \ > - VEC_ASSERT (vec_->prefix.num < vec_->prefix.alloc, "insert", T, base); \ > - VEC_ASSERT (ix_ <= vec_->prefix.num, "insert", T, base); \ > - slot_ = &vec_->vec[ix_]; \ > - memmove (slot_ + 1, slot_, (vec_->prefix.num++ - ix_) * sizeof (T)); \ > - *slot_ = obj_; \ > - \ > - return slot_; \ > -} \ > - \ > -static inline T VEC_OP (T,base,ordered_remove) \ > - (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \ > -{ \ > - T *slot_; \ > - T obj_; \ > - \ > - VEC_ASSERT (ix_ < vec_->prefix.num, "remove", T, base); \ > - slot_ = &vec_->vec[ix_]; \ > - obj_ = *slot_; \ > - memmove (slot_, slot_ + 1, (--vec_->prefix.num - ix_) * sizeof (T)); \ > - \ > - return obj_; \ > -} \ > - \ > -static inline T VEC_OP (T,base,unordered_remove) \ > - (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \ > -{ \ > - T *slot_; \ > - T obj_; \ > - \ > - VEC_ASSERT (ix_ < vec_->prefix.num, "remove", T, base); \ > - slot_ = &vec_->vec[ix_]; \ > - obj_ = *slot_; \ > - *slot_ = vec_->vec[--vec_->prefix.num]; \ > - \ > - return obj_; \ > -} \ > - \ > -static inline void VEC_OP (T,base,block_remove) \ > - (VEC(T,base) *vec_, unsigned ix_, unsigned len_ VEC_CHECK_DECL) \ > -{ \ > - T *slot_; \ > - \ > - VEC_ASSERT (ix_ + len_ <= vec_->prefix.num, "block_remove", T, base); \ > - slot_ = &vec_->vec[ix_]; \ > - vec_->prefix.num -= len_; \ > - memmove (slot_, slot_ + len_, (vec_->prefix.num - ix_) * sizeof (T)); \ > -} \ > - \ > -static inline T *VEC_OP (T,base,address) \ > - (VEC(T,base) *vec_) \ > -{ \ > - return vec_ ? vec_->vec : 0; \ > -} \ > - \ > -static inline unsigned VEC_OP (T,base,lower_bound) \ > - (VEC(T,base) *vec_, const T obj_, \ > - bool (*lessthan_)(const T, const T) VEC_CHECK_DECL) \ > -{ \ > - unsigned int len_ = VEC_OP (T,base, length) (vec_); \ > - unsigned int half_, middle_; \ > - unsigned int first_ = 0; \ > - while (len_ > 0) \ > - { \ > - T middle_elem_; \ > - half_ = len_ >> 1; \ > - middle_ = first_; \ > - middle_ += half_; \ > - middle_elem_ = VEC_OP (T,base,index) (vec_, middle_ VEC_CHECK_PASS); \ > - if (lessthan_ (middle_elem_, obj_)) \ > - { \ > - first_ = middle_; \ > - ++first_; \ > - len_ = len_ - half_ - 1; \ > - } \ > - else \ > - len_ = half_; \ > - } \ > - return first_; \ > -} > - > -#define DEF_VEC_ALLOC_FUNC_P(T,A) \ > -static inline VEC(T,A) *VEC_OP (T,A,alloc) \ > - (int alloc_ MEM_STAT_DECL) \ > -{ \ > - return (VEC(T,A) *) vec_##A##_p_reserve_exact (NULL, alloc_ \ > - PASS_MEM_STAT); \ > + unsigned int len_ = VEC_length (T, vec_); > + unsigned int half_, middle_; > + unsigned int first_ = 0; > + while (len_ > 0) > + { > + T middle_elem_; > + half_ = len_ >> 1; > + middle_ = first_; > + middle_ += half_; > + middle_elem_ = VEC_index_1 (vec_, middle_ VEC_CHECK_PASS); > + if (lessthan_ (middle_elem_, obj_)) > + { > + first_ = middle_; > + ++first_; > + len_ = len_ - half_ - 1; > + } > + else > + len_ = half_; > + } > + return first_; > } > > - > -#define DEF_VEC_NONALLOC_FUNCS_P(T,A) \ > -static inline void VEC_OP (T,A,free) \ > - (VEC(T,A) **vec_) \ > -{ \ > - if (*vec_) \ > - vec_##A##_free (*vec_); \ > - *vec_ = NULL; \ > -} \ > - \ > -static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \ > -{ \ > - size_t len_ = vec_ ? vec_->prefix.num : 0; \ > - VEC (T,A) *new_vec_ = NULL; \ > - \ > - if (len_) \ > - { \ > - new_vec_ = (VEC (T,A) *)(vec_##A##_p_reserve_exact \ > - (NULL, len_ PASS_MEM_STAT)); \ > - \ > - new_vec_->base.prefix.num = len_; \ > - memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_); \ > - } \ > - return new_vec_; \ > -} \ > - \ > -static inline int VEC_OP (T,A,reserve) \ > - (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \ > -{ \ > - int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \ > - VEC_CHECK_PASS); \ > - \ > - if (extend) \ > - *vec_ = (VEC(T,A) *) vec_##A##_p_reserve (*vec_, alloc_ PASS_MEM_STAT); \ > - \ > - return extend; \ > -} \ > - \ > -static inline int VEC_OP (T,A,reserve_exact) \ > - (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \ > -{ \ > - int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \ > - VEC_CHECK_PASS); \ > - \ > - if (extend) \ > - *vec_ = (VEC(T,A) *) vec_##A##_p_reserve_exact (*vec_, alloc_ \ > - PASS_MEM_STAT); \ > - \ > - return extend; \ > -} \ > - \ > -static inline void VEC_OP (T,A,safe_grow) \ > - (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \ > -{ \ > - VEC_ASSERT (size_ >= 0 \ > - && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \ > - "grow", T, A); \ > - VEC_OP (T,A,reserve_exact) (vec_, \ > - size_ - (int)(*vec_ ? VEC_BASE(*vec_)->prefix.num : 0) \ > - VEC_CHECK_PASS PASS_MEM_STAT); \ > - VEC_BASE (*vec_)->prefix.num = size_; \ > -} \ > - \ > -static inline void VEC_OP (T,A,safe_grow_cleared) \ > - (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \ > -{ \ > - int oldsize = VEC_OP(T,base,length) VEC_BASE(*vec_); \ > - VEC_OP (T,A,safe_grow) (vec_, size_ VEC_CHECK_PASS PASS_MEM_STAT); \ > - memset (&(VEC_OP (T,base,address) VEC_BASE(*vec_))[oldsize], 0, \ > - sizeof (T) * (size_ - oldsize)); \ > -} \ > - \ > -static inline void VEC_OP(T,A,safe_splice) \ > - (VEC(T,A) **dst_, VEC(T,base) *src_ VEC_CHECK_DECL MEM_STAT_DECL) \ > -{ \ > - if (src_) \ > - { \ > - VEC_OP (T,A,reserve_exact) (dst_, src_->prefix.num \ > - VEC_CHECK_PASS MEM_STAT_INFO); \ > - \ > - VEC_OP (T,base,splice) (VEC_BASE (*dst_), src_ \ > - VEC_CHECK_PASS); \ > - } \ > -} \ > - \ > -static inline T *VEC_OP (T,A,safe_push) \ > - (VEC(T,A) **vec_, T obj_ VEC_CHECK_DECL MEM_STAT_DECL) \ > -{ \ > - VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \ > - \ > - return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS); \ > -} \ > - \ > -static inline T *VEC_OP (T,A,safe_insert) \ > - (VEC(T,A) **vec_, unsigned ix_, T obj_ VEC_CHECK_DECL MEM_STAT_DECL) \ > -{ \ > - VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \ > - \ > - return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_ \ > - VEC_CHECK_PASS); \ > -} > - > -/* Vector of object. */ > -#define DEF_VEC_O(T) \ > -VEC_T_GTY(T,base); \ > -VEC_TA(T,base,none); \ > -DEF_VEC_FUNC_O(T) \ > -struct vec_swallow_trailing_semi > -#define DEF_VEC_ALLOC_O(T,A) \ > -VEC_TA(T,base,A); \ > -DEF_VEC_ALLOC_FUNC_O(T,A) \ > -DEF_VEC_NONALLOC_FUNCS_O(T,A) \ > -struct vec_swallow_trailing_semi > - > -#define DEF_VEC_FUNC_O(T) \ > -static inline unsigned VEC_OP (T,base,length) (const VEC(T,base) *vec_) \ > -{ \ > - return vec_ ? vec_->prefix.num : 0; \ > -} \ > - \ > -static inline T *VEC_OP (T,base,last) (VEC(T,base) *vec_ VEC_CHECK_DECL) \ > -{ \ > - VEC_ASSERT (vec_ && vec_->prefix.num, "last", T, base); \ > - \ > - return &vec_->vec[vec_->prefix.num - 1]; \ > -} \ > - \ > -static inline T *VEC_OP (T,base,index) \ > - (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \ > -{ \ > - VEC_ASSERT (vec_ && ix_ < vec_->prefix.num, "index", T, base); \ > - \ > - return &vec_->vec[ix_]; \ > -} \ > - \ > -static inline int VEC_OP (T,base,iterate) \ > - (VEC(T,base) *vec_, unsigned ix_, T **ptr) \ > -{ \ > - if (vec_ && ix_ < vec_->prefix.num) \ > - { \ > - *ptr = &vec_->vec[ix_]; \ > - return 1; \ > - } \ > - else \ > - { \ > - *ptr = 0; \ > - return 0; \ > - } \ > -} \ > - \ > -static inline size_t VEC_OP (T,base,embedded_size) \ > - (int alloc_) \ > -{ \ > - return offsetof (VEC(T,base),vec) + alloc_ * sizeof(T); \ > -} \ > - \ > -static inline void VEC_OP (T,base,embedded_init) \ > - (VEC(T,base) *vec_, int alloc_) \ > -{ \ > - vec_->prefix.num = 0; \ > - vec_->prefix.alloc = alloc_; \ > -} \ > - \ > -static inline int VEC_OP (T,base,space) \ > - (VEC(T,base) *vec_, int alloc_ VEC_CHECK_DECL) \ > -{ \ > - VEC_ASSERT (alloc_ >= 0, "space", T, base); \ > - return vec_ ? vec_->prefix.alloc - vec_->prefix.num >= (unsigned)alloc_ : !alloc_; \ > -} \ > - \ > -static inline void VEC_OP(T,base,splice) \ > - (VEC(T,base) *dst_, VEC(T,base) *src_ VEC_CHECK_DECL) \ > -{ \ > - if (src_) \ > - { \ > - unsigned len_ = src_->prefix.num; \ > - VEC_ASSERT (dst_->prefix.num + len_ <= dst_->prefix.alloc, "splice", T, base); \ > - \ > - memcpy (&dst_->vec[dst_->prefix.num], &src_->vec[0], len_ * sizeof (T)); \ > - dst_->prefix.num += len_; \ > - } \ > -} \ > - \ > -static inline T *VEC_OP (T,base,quick_push) \ > - (VEC(T,base) *vec_, const T *obj_ VEC_CHECK_DECL) \ > -{ \ > - T *slot_; \ > - \ > - VEC_ASSERT (vec_->prefix.num < vec_->prefix.alloc, "push", T, base); \ > - slot_ = &vec_->vec[vec_->prefix.num++]; \ > - if (obj_) \ > - *slot_ = *obj_; \ > - \ > - return slot_; \ > -} \ > - \ > -static inline void VEC_OP (T,base,pop) (VEC(T,base) *vec_ VEC_CHECK_DECL) \ > -{ \ > - VEC_ASSERT (vec_->prefix.num, "pop", T, base); \ > - --vec_->prefix.num; \ > -} \ > - \ > -static inline void VEC_OP (T,base,truncate) \ > - (VEC(T,base) *vec_, unsigned size_ VEC_CHECK_DECL) \ > -{ \ > - VEC_ASSERT (vec_ ? vec_->prefix.num >= size_ : !size_, "truncate", T, base); \ > - if (vec_) \ > - vec_->prefix.num = size_; \ > -} \ > - \ > -static inline T *VEC_OP (T,base,replace) \ > - (VEC(T,base) *vec_, unsigned ix_, const T *obj_ VEC_CHECK_DECL) \ > -{ \ > - T *slot_; \ > - \ > - VEC_ASSERT (ix_ < vec_->prefix.num, "replace", T, base); \ > - slot_ = &vec_->vec[ix_]; \ > - if (obj_) \ > - *slot_ = *obj_; \ > - \ > - return slot_; \ > -} \ > - \ > -static inline T *VEC_OP (T,base,quick_insert) \ > - (VEC(T,base) *vec_, unsigned ix_, const T *obj_ VEC_CHECK_DECL) \ > -{ \ > - T *slot_; \ > - \ > - VEC_ASSERT (vec_->prefix.num < vec_->prefix.alloc, "insert", T, base); \ > - VEC_ASSERT (ix_ <= vec_->prefix.num, "insert", T, base); \ > - slot_ = &vec_->vec[ix_]; \ > - memmove (slot_ + 1, slot_, (vec_->prefix.num++ - ix_) * sizeof (T)); \ > - if (obj_) \ > - *slot_ = *obj_; \ > - \ > - return slot_; \ > -} \ > - \ > -static inline void VEC_OP (T,base,ordered_remove) \ > - (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \ > -{ \ > - T *slot_; \ > - \ > - VEC_ASSERT (ix_ < vec_->prefix.num, "remove", T, base); \ > - slot_ = &vec_->vec[ix_]; \ > - memmove (slot_, slot_ + 1, (--vec_->prefix.num - ix_) * sizeof (T)); \ > -} \ > - \ > -static inline void VEC_OP (T,base,unordered_remove) \ > - (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \ > -{ \ > - VEC_ASSERT (ix_ < vec_->prefix.num, "remove", T, base); \ > - vec_->vec[ix_] = vec_->vec[--vec_->prefix.num]; \ > -} \ > - \ > -static inline void VEC_OP (T,base,block_remove) \ > - (VEC(T,base) *vec_, unsigned ix_, unsigned len_ VEC_CHECK_DECL) \ > -{ \ > - T *slot_; \ > - \ > - VEC_ASSERT (ix_ + len_ <= vec_->prefix.num, "block_remove", T, base); \ > - slot_ = &vec_->vec[ix_]; \ > - vec_->prefix.num -= len_; \ > - memmove (slot_, slot_ + len_, (vec_->prefix.num - ix_) * sizeof (T)); \ > -} \ > - \ > -static inline T *VEC_OP (T,base,address) \ > - (VEC(T,base) *vec_) \ > -{ \ > - return vec_ ? vec_->vec : 0; \ > -} \ > - \ > -static inline unsigned VEC_OP (T,base,lower_bound) \ > - (VEC(T,base) *vec_, const T *obj_, \ > - bool (*lessthan_)(const T *, const T *) VEC_CHECK_DECL) \ > -{ \ > - unsigned int len_ = VEC_OP (T, base, length) (vec_); \ > - unsigned int half_, middle_; \ > - unsigned int first_ = 0; \ > - while (len_ > 0) \ > - { \ > - T *middle_elem_; \ > - half_ = len_ >> 1; \ > - middle_ = first_; \ > - middle_ += half_; \ > - middle_elem_ = VEC_OP (T,base,index) (vec_, middle_ VEC_CHECK_PASS); \ > - if (lessthan_ (middle_elem_, obj_)) \ > - { \ > - first_ = middle_; \ > - ++first_; \ > - len_ = len_ - half_ - 1; \ > - } \ > - else \ > - len_ = half_; \ > - } \ > - return first_; \ > +template<typename T> > +static inline unsigned > +VEC_lower_bound_1 (vec_t<T> *vec_, const T *ptr_, > + bool (*lessthan_)(const T*, const T*) VEC_CHECK_DECL) > +{ > + unsigned int len_ = VEC_length (T, vec_); > + unsigned int half_, middle_; > + unsigned int first_ = 0; > + while (len_ > 0) > + { > + T *middle_elem_; > + half_ = len_ >> 1; > + middle_ = first_; > + middle_ += half_; > + middle_elem_ = &VEC_index_1 (vec_, middle_ VEC_CHECK_PASS); > + if (lessthan_ (middle_elem_, ptr_)) > + { > + first_ = middle_; > + ++first_; > + len_ = len_ - half_ - 1; > + } > + else > + len_ = half_; > + } > + return first_; > } > > -#define DEF_VEC_ALLOC_FUNC_O(T,A) \ > -static inline VEC(T,A) *VEC_OP (T,A,alloc) \ > - (int alloc_ MEM_STAT_DECL) \ > -{ \ > - return (VEC(T,A) *) vec_##A##_o_reserve_exact (NULL, alloc_, \ > - offsetof (VEC(T,A),base.vec), \ > - sizeof (T) \ > - PASS_MEM_STAT); \ > -} > > -#define DEF_VEC_NONALLOC_FUNCS_O(T,A) \ > -static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \ > -{ \ > - size_t len_ = vec_ ? vec_->prefix.num : 0; \ > - VEC (T,A) *new_vec_ = NULL; \ > - \ > - if (len_) \ > - { \ > - new_vec_ = (VEC (T,A) *)(vec_##A##_o_reserve_exact \ > - (NULL, len_, \ > - offsetof (VEC(T,A),base.vec), sizeof (T) \ > - PASS_MEM_STAT)); \ > - \ > - new_vec_->base.prefix.num = len_; \ > - memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_); \ > - } \ > - return new_vec_; \ > -} \ > - \ > -static inline void VEC_OP (T,A,free) \ > - (VEC(T,A) **vec_) \ > -{ \ > - if (*vec_) \ > - vec_##A##_free (*vec_); \ > - *vec_ = NULL; \ > -} \ > - \ > -static inline int VEC_OP (T,A,reserve) \ > - (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \ > -{ \ > - int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \ > - VEC_CHECK_PASS); \ > - \ > - if (extend) \ > - *vec_ = (VEC(T,A) *) vec_##A##_o_reserve (*vec_, alloc_, \ > - offsetof (VEC(T,A),base.vec),\ > - sizeof (T) \ > - PASS_MEM_STAT); \ > - \ > - return extend; \ > -} \ > - \ > -static inline int VEC_OP (T,A,reserve_exact) \ > - (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \ > -{ \ > - int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \ > - VEC_CHECK_PASS); \ > - \ > - if (extend) \ > - *vec_ = (VEC(T,A) *) vec_##A##_o_reserve_exact \ > - (*vec_, alloc_, \ > - offsetof (VEC(T,A),base.vec), \ > - sizeof (T) PASS_MEM_STAT); \ > - \ > - return extend; \ > -} \ > - \ > -static inline void VEC_OP (T,A,safe_grow) \ > - (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \ > -{ \ > - VEC_ASSERT (size_ >= 0 \ > - && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \ > - "grow", T, A); \ > - VEC_OP (T,A,reserve_exact) (vec_, \ > - size_ - (int)(*vec_ ? VEC_BASE(*vec_)->prefix.num : 0) \ > - VEC_CHECK_PASS PASS_MEM_STAT); \ > - VEC_BASE (*vec_)->prefix.num = size_; \ > -} \ > - \ > -static inline void VEC_OP (T,A,safe_grow_cleared) \ > - (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \ > -{ \ > - int oldsize = VEC_OP(T,base,length) VEC_BASE(*vec_); \ > - VEC_OP (T,A,safe_grow) (vec_, size_ VEC_CHECK_PASS PASS_MEM_STAT); \ > - memset (&(VEC_OP (T,base,address) VEC_BASE(*vec_))[oldsize], 0, \ > - sizeof (T) * (size_ - oldsize)); \ > -} \ > - \ > -static inline void VEC_OP(T,A,safe_splice) \ > - (VEC(T,A) **dst_, VEC(T,base) *src_ VEC_CHECK_DECL MEM_STAT_DECL) \ > -{ \ > - if (src_) \ > - { \ > - VEC_OP (T,A,reserve_exact) (dst_, src_->prefix.num \ > - VEC_CHECK_PASS MEM_STAT_INFO); \ > - \ > - VEC_OP (T,base,splice) (VEC_BASE (*dst_), src_ \ > - VEC_CHECK_PASS); \ > - } \ > -} \ > - \ > -static inline T *VEC_OP (T,A,safe_push) \ > - (VEC(T,A) **vec_, const T *obj_ VEC_CHECK_DECL MEM_STAT_DECL) \ > -{ \ > - VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \ > - \ > - return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS); \ > -} \ > - \ > -static inline T *VEC_OP (T,A,safe_insert) \ > - (VEC(T,A) **vec_, unsigned ix_, const T *obj_ \ > - VEC_CHECK_DECL MEM_STAT_DECL) \ > -{ \ > - VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \ > - \ > - return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_ \ > - VEC_CHECK_PASS); \ > -} > +void *vec_heap_o_reserve_1 (void *, int, size_t, size_t, bool MEM_STAT_DECL); > +void *vec_gc_o_reserve_1 (void *, int, size_t, size_t, bool MEM_STAT_DECL); > > -#define DEF_VEC_ALLOC_FUNC_I(T,A) \ > -static inline VEC(T,A) *VEC_OP (T,A,alloc) \ > - (int alloc_ MEM_STAT_DECL) \ > -{ \ > - return (VEC(T,A) *) vec_##A##_o_reserve_exact \ > - (NULL, alloc_, offsetof (VEC(T,A),base.vec), \ > - sizeof (T) PASS_MEM_STAT); \ > -} > +/* Ensure there are at least RESERVE free slots in VEC_, growing > + exponentially. If RESERVE < 0 grow exactly, else grow > + exponentially. As a special case, if VEC_ is NULL, and RESERVE is > + 0, no vector will be created. */ > > -#define DEF_VEC_NONALLOC_FUNCS_I(T,A) \ > -static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \ > -{ \ > - size_t len_ = vec_ ? vec_->prefix.num : 0; \ > - VEC (T,A) *new_vec_ = NULL; \ > - \ > - if (len_) \ > - { \ > - new_vec_ = (VEC (T,A) *)(vec_##A##_o_reserve_exact \ > - (NULL, len_, \ > - offsetof (VEC(T,A),base.vec), sizeof (T) \ > - PASS_MEM_STAT)); \ > - \ > - new_vec_->base.prefix.num = len_; \ > - memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_); \ > - } \ > - return new_vec_; \ > -} \ > - \ > -static inline void VEC_OP (T,A,free) \ > - (VEC(T,A) **vec_) \ > -{ \ > - if (*vec_) \ > - vec_##A##_free (*vec_); \ > - *vec_ = NULL; \ > -} \ > - \ > -static inline int VEC_OP (T,A,reserve) \ > - (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \ > -{ \ > - int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \ > - VEC_CHECK_PASS); \ > - \ > - if (extend) \ > - *vec_ = (VEC(T,A) *) vec_##A##_o_reserve (*vec_, alloc_, \ > - offsetof (VEC(T,A),base.vec),\ > - sizeof (T) \ > - PASS_MEM_STAT); \ > - \ > - return extend; \ > -} \ > - \ > -static inline int VEC_OP (T,A,reserve_exact) \ > - (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \ > -{ \ > - int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \ > - VEC_CHECK_PASS); \ > - \ > - if (extend) \ > - *vec_ = (VEC(T,A) *) vec_##A##_o_reserve_exact \ > - (*vec_, alloc_, offsetof (VEC(T,A),base.vec), \ > - sizeof (T) PASS_MEM_STAT); \ > - \ > - return extend; \ > -} \ > - \ > -static inline void VEC_OP (T,A,safe_grow) \ > - (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \ > -{ \ > - VEC_ASSERT (size_ >= 0 \ > - && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \ > - "grow", T, A); \ > - VEC_OP (T,A,reserve_exact) (vec_, \ > - size_ - (int)(*vec_ ? VEC_BASE(*vec_)->prefix.num : 0) \ > - VEC_CHECK_PASS PASS_MEM_STAT); \ > - VEC_BASE (*vec_)->prefix.num = size_; \ > -} \ > - \ > -static inline void VEC_OP (T,A,safe_grow_cleared) \ > - (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \ > -{ \ > - int oldsize = VEC_OP(T,base,length) VEC_BASE(*vec_); \ > - VEC_OP (T,A,safe_grow) (vec_, size_ VEC_CHECK_PASS PASS_MEM_STAT); \ > - memset (&(VEC_OP (T,base,address) VEC_BASE(*vec_))[oldsize], 0, \ > - sizeof (T) * (size_ - oldsize)); \ > -} \ > - \ > -static inline void VEC_OP(T,A,safe_splice) \ > - (VEC(T,A) **dst_, VEC(T,base) *src_ VEC_CHECK_DECL MEM_STAT_DECL) \ > -{ \ > - if (src_) \ > - { \ > - VEC_OP (T,A,reserve_exact) (dst_, src_->prefix.num \ > - VEC_CHECK_PASS MEM_STAT_INFO); \ > - \ > - VEC_OP (T,base,splice) (VEC_BASE (*dst_), src_ \ > - VEC_CHECK_PASS); \ > - } \ > -} \ > - \ > -static inline T *VEC_OP (T,A,safe_push) \ > - (VEC(T,A) **vec_, const T obj_ VEC_CHECK_DECL MEM_STAT_DECL) \ > -{ \ > - VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \ > - \ > - return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS); \ > -} \ > - \ > -static inline T *VEC_OP (T,A,safe_insert) \ > - (VEC(T,A) **vec_, unsigned ix_, const T obj_ \ > - VEC_CHECK_DECL MEM_STAT_DECL) \ > -{ \ > - VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \ > - \ > - return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_ \ > - VEC_CHECK_PASS); \ > +template<typename T, enum vec_allocation_t A> > +vec_t<T> * > +vec_reserve (vec_t<T> *vec_, int reserve MEM_STAT_DECL) > +{ > + if (A == gc) > + return (vec_t<T> *) vec_gc_o_reserve_1 (vec_, reserve, > + offsetof (vec_t<T>, vec), > + sizeof (T), false > + PASS_MEM_STAT); > + else if (A == heap) > + return (vec_t<T> *) vec_heap_o_reserve_1 (vec_, reserve, > + offsetof (vec_t<T>, vec), > + sizeof (T), false > + PASS_MEM_STAT); > + else > + { > + /* Only allow stack vectors when re-growing them. The initial > + allocation of stack vectors must be done with the > + VEC_stack_alloc macro, because it uses alloca() for the > + allocation. */ > + if (vec_ == NULL) > + { > + fprintf (stderr, "Stack vectors must be initially allocated " > + "with VEC_stack_alloc.\n"); > + gcc_unreachable (); > + } > + return (vec_t<T> *) vec_stack_o_reserve (vec_, reserve, > + offsetof (vec_t<T>, vec), > + sizeof (T) PASS_MEM_STAT); > + } > } > > -/* 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. Instead of DEF_VEC_ALLOC_P(TYPE, heap|gc), use > - DEF_VEC_ALLOC_P_STACK(TYPE). This uses alloca to get the initial > - space; because alloca can not be usefully called in an inline > - function, and because a macro can not define a macro, you must then > - write a #define for each type: > - > - #define VEC_{TYPE}_stack_alloc(alloc) \ > - VEC_stack_alloc({TYPE}, alloc) > > - This is really a hack and perhaps can be made better. Note that > - this macro will wind up evaluating the ALLOC parameter twice. > +/* Ensure there are at least RESERVE free slots in VEC_, growing > + exactly. If RESERVE < 0 grow exactly, else grow exponentially. As > + a special case, if VEC_ is NULL, and RESERVE is 0, no vector will be > + created. */ > > - 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 VEC(TYPE,stack) vector from the function > - which allocated it. */ > - > -extern void *vec_stack_p_reserve (void *, int MEM_STAT_DECL); > -extern void *vec_stack_p_reserve_exact (void *, int MEM_STAT_DECL); > -extern void *vec_stack_p_reserve_exact_1 (int, void *); > -extern void *vec_stack_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL); > -extern void *vec_stack_o_reserve_exact (void *, int, size_t, size_t > - MEM_STAT_DECL); > -extern void vec_stack_free (void *); > - > -#ifdef GATHER_STATISTICS > -#define VEC_stack_alloc(T,alloc,name,line,function) \ > - (VEC_OP (T,stack,alloc1) \ > - (alloc, XALLOCAVAR (VEC(T,stack), VEC_embedded_size (T, alloc)))) > -#else > -#define VEC_stack_alloc(T,alloc) \ > - (VEC_OP (T,stack,alloc1) \ > - (alloc, XALLOCAVAR (VEC(T,stack), VEC_embedded_size (T, alloc)))) > -#endif > - > -#define DEF_VEC_ALLOC_P_STACK(T) \ > -VEC_TA(T,base,stack); \ > -DEF_VEC_ALLOC_FUNC_P_STACK(T) \ > -DEF_VEC_NONALLOC_FUNCS_P(T,stack) \ > -struct vec_swallow_trailing_semi > - > -#define DEF_VEC_ALLOC_FUNC_P_STACK(T) \ > -static inline VEC(T,stack) *VEC_OP (T,stack,alloc1) \ > - (int alloc_, VEC(T,stack)* space) \ > -{ \ > - return (VEC(T,stack) *) vec_stack_p_reserve_exact_1 (alloc_, space); \ > -} > - > -#define DEF_VEC_ALLOC_O_STACK(T) \ > -VEC_TA(T,base,stack); \ > -DEF_VEC_ALLOC_FUNC_O_STACK(T) \ > -DEF_VEC_NONALLOC_FUNCS_O(T,stack) \ > -struct vec_swallow_trailing_semi > - > -#define DEF_VEC_ALLOC_FUNC_O_STACK(T) \ > -static inline VEC(T,stack) *VEC_OP (T,stack,alloc1) \ > - (int alloc_, VEC(T,stack)* space) \ > -{ \ > - return (VEC(T,stack) *) vec_stack_p_reserve_exact_1 (alloc_, space); \ > -} > - > -#define DEF_VEC_ALLOC_I_STACK(T) \ > -VEC_TA(T,base,stack); \ > -DEF_VEC_ALLOC_FUNC_I_STACK(T) \ > -DEF_VEC_NONALLOC_FUNCS_I(T,stack) \ > -struct vec_swallow_trailing_semi > - > -#define DEF_VEC_ALLOC_FUNC_I_STACK(T) \ > -static inline VEC(T,stack) *VEC_OP (T,stack,alloc1) \ > - (int alloc_, VEC(T,stack)* space) \ > -{ \ > - return (VEC(T,stack) *) vec_stack_p_reserve_exact_1 (alloc_, space); \ > +template<typename T, enum vec_allocation_t A> > +vec_t<T> * > +vec_reserve_exact (vec_t<T> *vec_, int reserve MEM_STAT_DECL) > +{ > + if (A == gc) > + return (vec_t<T> *) vec_gc_o_reserve_1 (vec_, reserve, > + sizeof (struct vec_prefix), > + sizeof (T), true > + PASS_MEM_STAT); > + else if (A == heap) > + return (vec_t<T> *) vec_heap_o_reserve_1 (vec_, reserve, > + sizeof (struct vec_prefix), > + sizeof (T), true > + PASS_MEM_STAT); > + else if (A == stack) > + { > + /* Only allow stack vectors when re-growing them. The initial > + allocation of stack vectors must be done with VEC_alloc, > + because it uses alloca() for the allocation. */ > + if (vec_ == NULL) > + { > + fprintf (stderr, "Stack vectors must be initially allocated " > + "with VEC_stack_alloc.\n"); > + gcc_unreachable (); > + } > + return (vec_t<T> *) vec_stack_o_reserve_exact (vec_, reserve, > + sizeof (struct vec_prefix), > + sizeof (T) > + PASS_MEM_STAT); > + } > } > > #endif /* GCC_VEC_H */ > > -- > This patch is available for review at http://codereview.appspot.com/6233044
Sign in to reply to this message.
On Thu, May 24, 2012 at 1:16 AM, Richard Guenther <richard.guenther@gmail.com> wrote: > On Wed, May 23, 2012 at 9:48 PM, Diego Novillo <dnovillo@google.com> wrote: >> >> This series of 3 patches re-implement vec.[ch] in C++. >> >> The main goal of this first step is to minimize changes to client >> code. I tried very hard to maintain the existing API. This means >> that vectors are still simple structures accessed via the existing >> VEC_* functions. >> >> The major change introduced here is the removal of all the macro-based >> type creation in vec.h: >> >> 1- Given a type T and an allocation strategy A, VEC(T,A) used to >> expand into the C type 'struct VEC_T_A'. The family of accessor >> functions for VEC_T_A were created via macro expansion and token >> pasting. >> >> After this patch, VEC(T,A) expands to 'vec_t<T>': >> >> template<typename T> >> struct GTY(()) vec_t >> { >> vec_prefix prefix; >> T GTY((length ("%h.prefix.num"))) vec[1]; >> }; >> >> The family of accessor functions for vec_t<T> are free functions >> templated on <T> or <T,A> depending on whether the function needs >> to perform allocation operations. >> >> 2- All the DEF_VEC_[IOP] and DEF_VEC_ALLOC_[IOP] macros expand to the >> nil expansion 'struct vec_swallow_trailing_semi'. This represents >> the bulk of the removal in vec.h. >> >> 3- I removed one indirection from the existing VEC structures. Before >> this patch, the visible structure created by VEC_T_A had a single >> element 'base', which, in turn, was the structure holding 'prefix' >> and 'vec'. The new vec_t<T> has 'prefix' and 'vec' in it. This >> may change in the second iteration of this patch. > > I believe this was because of aliasing - you may dig in the svn history > to find out what we miscompiled when not doing this and whether it is > still necessary or not. Yes it was done for aliasing reasons (I did this change). In fact it is still necessary and it was only reproduciable with LTO and -O3. Thanks, Andrew Pinski > >> Some client code changes were needed: >> >> 1- The allocation names 'heap', 'stack' and 'gc' are not embedded in >> the type name anymore. They are enum values used as a template >> argument for functions like VEC_alloc() and VEC_free(). Since they >> are now separate identifiers, some existing code that declared >> variables with the names 'heap' and 'stack' had to change. >> >> I did not change these enum values to better names because that >> would have meant changing a lot more client code. I will change >> this in a future patch. > > Yeah. Can we have > > template <...> > struct vec { > enum { gc, heap, stack }; > ... > } > > and use vec<T, vec::stack> instead? Not sure if this or something similar > is valid C++. > >> 2- VEC_index and VEC_last now return a reference to the element. The >> existing APIs implemented two versions of these functions. One >> returning the element itself (used for vec_t<T *>). Another returning >> a pointer to the element (used for vec_t<T>). >> >> This is impossible to represent in C++ directly, as functions >> cannot be overloaded by their return value. Instead, I made them >> return a reference to the element. This means that vectors storing >> pointers (T *) do not need to change, but vectors of objects (T) do >> need to change. >> >> We have fewer vec_t<T> than vec_t<T *>, so this was the smaller change >> (which still meant changing a few hundred call sites). > > We still can have const overloads when taking a const vec though? > >> 3- The family of VEC_*push and VEC_*replace functions have overloads >> for handling 'T' and 'const T *' objects. The former is used for >> vec_t<T>, the latter for vec_t<T*>. This means, however, than when >> pushing the special value 0 on a vec_t<T*>, the compiler will not >> know which overload we meant, as 0 matches both. In these cases >> (not very many), a static cast is all we need to help it. >> >> I'm not terribly content with this one. I'll try to have a better >> approach in the second iteration (which will liberally change all >> client code). > > I wonder whether explicitely specifying the template type is better? Thus, > VEC_safe_push<T *, gc>(0) instead of automatically deducing the template > argument? > >> 4- I extended gengtype to understand templated types. These changes >> are not as ugly as I thought they would be. Gengtype has some >> hardwired knowledge of VEC_*, which I renamed to vec_t. I'm not >> even sure why gengtype needs to care about vec_t in this way, but I >> was looking for minimal changes, so I just did it. >> >> The other change is more generic. It allows gengtype to deal with >> templated types. There is a new function (filter_type_name) that >> recognizes C++ special characters '<', '>' and ':'. It turns them >> into '_'. This way, gengtype can generate a valid identifier for >> the pre-processor. It only does this in contexts where it needs a >> pre-processor identifier. For everything else, it emits the type >> directly. So, the functions emitted in gt-*.h files have proper >> template type references. > > Well, that part is of course what needs to change. I don't think we want > gengtype to work like this for templates as this does not scale. > >> >> Properties of this patch: >> >> The performance and memory numbers I collected here were done by >> bootstrapping the branch before and after my patch with all >> languages enabled (including Ada and Go). >> >> I collected time and memory reports by forcing the switches >> -ftime-report and -fmem-report to be on by default, and to emit >> their output to a separate file (otherwise the bootstrap fails >> when some configure checks get confused by the extraneous stderr >> output). This produced 2.9Gb of output over 12,944 timings >> files. >> >> 1- There is much less code in vec.[ch] (21% fewer lines). >> Functions are no longer replicated 2 or 3 times. >> >> 2- Debugging VEC_* routines is simpler. Failures in GDB go to >> the specific VEC_* function instance, instead of the DEF_VEC_* >> macro. >> >> 3- The new implementation is faster. Individual compiles are >> generally 2.0 to 2.5% faster (wall time). This translates into >> a bootstrap speedup of 1-2% (wall time reduction of about a minute >> on my desktop). >> >> The reason for this speedup is that various VEC_ routines now >> return a reference to the element, which means that for vec_t<T> >> there is one less memory indirection to perform. >> >> 4- Minimal changes to binary code size. The *1 binaries are about >> 0.07% bigger. >> >> 5- Reduced memory consumption by 4% on average (as measured by -fmem-report). >> I averaged the 'Total Allocated:' field from -fmem-report from >> all the compile >> >> There are fewer macros expanded (-23%) and fewer >> trees generated (the numbers below are averages over the >> 12,944 compilations): >> >> Before After (%) >> decls 9,491 9,240 - 2.6% >> types 2,958 2,827 - 4.4% >> blocks 525 460 -12.4% >> stmts 1,123 1,043 - 7.1% >> refs 4,369 3,926 -10.1% >> exprs 15,236 14,283 - 6.2% >> constants 1,888 1,871 - 0.9% >> identifiers 7,285 7,197 - 1.2% >> vecs 1,786 1,786 0% >> binfos 113 109 - 3.5% >> ssa names 2,240 2,240 0% >> constructors 245 245 0% >> random kinds 13,338 12,849 - 3.7% >> lang_decl kinds 2,816 2,640 - 6.2% >> lang_type kinds 110 106 - 3.6% >> omp clauses 0 0 0% >> >> >> >> Next step: >> >> Before I consider moving this patch over to trunk, I would like to >> generate a second patch that will: >> >> 1- Move all the free functions VEC_* into vec_t<T>. This will >> simplify the call sites quite a bit. Mainly, it will remove the >> unnecessary arguments T and A that are now always specified in >> every call. >> >> 2- Change VEC_index into operator[]. >> >> 3- Change VEC_replace(...) to assignments using operator[]. > > I think these should not be done for now - they merely add syntactic > sugar, no? > >> One thing these changes will do, however, is lose the VEC_CHECK_* >> expansions that add the __FILE__, __LINE__ and __FUNCTION__ arguments >> to the VEC_*() functions. >> >> To deal with this loss, we could unwind the call stack a few levels on >> ICEs. In fact, I think this could be a good thing to add to ICEs in >> general. Showing some functions up the stack seems more useful than >> just showing a single point. >> >> OK for cxx-conversion branch? > > Where's the gengtype/GC bits? > > Richard. > >> >> >> 2012-05-22 Diego Novillo <dnovillo@google.com> >> >> Re-implement VEC in C++. >> >> * vec.c (vec_heap_free): Convert into a template function. >> (vec_gc_o_reserve_1): Make extern. >> (vec_gc_p_reserve): Remove. >> (vec_gc_p_reserve_exact): Remove. >> (vec_gc_o_reserve): Remove. >> (vec_gc_o_reserve_exact): Remove. >> (vec_heap_o_reserve_1): Make extern. >> (vec_heap_p_reserve): Remove. >> (vec_heap_p_reserve_exact): Remove. >> (vec_heap_o_reserve): Remove. >> (vec_heap_o_reserve_exact): Remove. >> (vec_stack_p_reserve): Remove. >> (vec_stack_p_reserve_exact): Remove. >> * vec.h (VEC_CHECK_INFO, VEC_CHECK_DECL, VEC_CHECK_PASS, >> VEC_ASSERT, VEC_ASSERT_FAIL, vec_assert_fail): Move earlier >> in the file. >> (VEC): Define to vec_t<T>. >> (vec_allocation_t): Define. >> (struct vec_prefix): Move earlier in the file. >> (vec_t<T>): New template. >> (DEF_VEC_I, DEF_VECL_ALLOC_I, DEF_VEC_P, DEF_VEC_ALLOC_P, >> DEF_VEC_O, DEF_VEC_ALLOC_P, DEF_VEC_O, DEF_VEC_ALLOC_O, >> DEF_VEC_ALLOC_P_STACK, DEF_VEC_ALLOC_O_STACK, >> DEF_VEC_ALLOC_I_STACK): Expand to 'struct vec_swallow_trailing_semi'. >> (vec_stack_p_reserve): Remove. >> (vec_stack_p_reserve_exact): Remove. >> (vec_stack_p_reserve_exact_1): Remove. >> (vec_stack_o_reserve): Remove. >> (vec_stack_o_reserve_exact): Remove. >> (vec_stack_free): Re-write as a template function. >> (vec_reserve): New template function. >> (vec_reserve_exact): New template function. >> (vec_heap_free): New template function if GATHER_STATISTICS is >> defined. Otherwise, macro that expands to free(). >> (VEC_length_1): New template function. >> (VEC_length): Call it. >> (VEC_empty_1): New template function. >> (VEC_empty): Call it. >> (VEC_address_1): New template function. >> (VEC_address): Call it. >> (VEC_last_1): New template function. >> (VEC_last): Call it. Change return type to T&. >> Change all users that used VEC_Os. >> (VEC_index_1): New template function. >> (VEC_index): Call it. Return a T& instead of a T*. >> Update all callers that were using VEC_O before. >> (VEC_iterate_1): New template function. >> (VEC_iterate): Call it. >> (VEC_embedded_size_1): New template function. >> (VEC_embedded_size): Call it. >> (VEC_embedded_init_1): New template function. >> (VEC_embedded_init): Call it. >> (VEC_alloc_1): New template function. >> (VEC_alloc): Call it. If A is 'stack', call XALLOCAVAR to >> do the allocation. >> (VEC_free_1): New template function. >> (VEC_free): Call it. >> (VEC_copy_1): New template function. >> (VEC_copy): Call it. >> (VEC_space_1): New template function >> (VEC_space): Call it. >> (VEC_reserve_1): New template function. >> (VEC_reserve): Call it. >> (VEC_reserve_exact_1): New template function. >> (VEC_reserve_exact): Call it. >> (VEC_splice_1): New template function. >> (VEC_splice): Call it. >> (VEC_safe_splice_1): New template function. >> (VEC_safe_splice): Call it. >> (VEC_quick_push_1): New template function. Create two overloads, one >> accepting T, the other accepting T *. Update all callers >> where T and T * are ambiguous. >> (VEC_quick_push): Call it. >> (VEC_safe_push_1): New template function. Create two overloads, one >> accepting T, the other accepting T *. Update all callers >> where T and T * are ambiguous. >> (VEC_safe_push): Call it. >> (VEC_pop_1): New template function. >> (VEC_pop): Call it. >> (VEC_truncate_1): New template function. >> (VEC_truncate): Call it. >> (VEC_safe_grow_1): New template function. >> (VEC_safe_grow): Call it. >> (VEC_safe_grow_cleared_1): New template function. >> (VEC_safe_grow_cleared): Call it. >> (VEC_replace_1): New template function. >> (VEC_replace): Call it. Always accept T instead of T*. >> Update all callers that used VEC_Os. >> (VEC_quick_insert_1): New template function. >> (VEC_quick_insert): Call it. >> (VEC_safe_insert_1): New template function. >> (VEC_safe_insert): Call it. >> (VEC_ordered_remove_1): New template function. >> (VEC_ordered_remove): Call it. >> (VEC_unordered_remove_1): New template function. >> (VEC_unordered_remove): Call it. >> (VEC_block_remove_1): New template function. >> (VEC_block_remove): Call it. >> (VEC_lower_bound_1): New template function. >> (VEC_lower_bound): Call it. >> (VEC_OP): Remove. >> (DEF_VEC_FUNC_P): Remove. >> (DEF_VEC_ALLOC_FUNC_P): Remove. >> (DEF_VEC_NONALLOC_FUNCS_P): Remove. >> (DEF_VEC_FUNC_O): Remove. >> (DEF_VEC_ALLOC_FUNC_O): Remove. >> (DEF_VEC_NONALLOC_FUNCS_O): Remove. >> (DEF_VEC_ALLOC_FUNC_I): Remove. >> (DEF_VEC_NONALLOC_FUNCS_I): Remove. >> (DEF_VEC_ALLOC_FUNC_P_STACK): Remove. >> (DEF_VEC_ALLOC_FUNC_O_STACK): Remove. >> (DEF_VEC_ALLOC_FUNC_I_STACK): Remove. >> (vec_reserve_exact): New template function. >> >> diff --git a/gcc/vec.c b/gcc/vec.c >> index 783a3cf..ba81e35 100644 >> --- a/gcc/vec.c >> +++ b/gcc/vec.c >> @@ -1,7 +1,8 @@ >> /* Vector API for GNU compiler. >> - Copyright (C) 2004, 2005, 2006, 2007, 2008, 2010 >> + Copyright (C) 2004, 2005, 2006, 2007, 2008, 2010, 2011, 2012 >> 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. >> >> @@ -215,7 +216,7 @@ calculate_allocation (const struct vec_prefix *pfx, int reserve, bool exact) >> trailing array is at VEC_OFFSET offset and consists of ELT_SIZE >> sized elements. */ >> >> -static void * >> +void * >> vec_gc_o_reserve_1 (void *vec, int reserve, size_t vec_offset, size_t elt_size, >> bool exact MEM_STAT_DECL) >> { >> @@ -248,61 +249,10 @@ vec_gc_o_reserve_1 (void *vec, int reserve, size_t vec_offset, size_t elt_size, >> return vec; >> } >> >> -/* Ensure there are at least RESERVE free slots in VEC, growing >> - exponentially. If RESERVE < 0 grow exactly, else grow >> - exponentially. As a special case, if VEC is NULL, and RESERVE is >> - 0, no vector will be created. */ >> - >> -void * >> -vec_gc_p_reserve (void *vec, int reserve MEM_STAT_DECL) >> -{ >> - return vec_gc_o_reserve_1 (vec, reserve, >> - sizeof (struct vec_prefix), >> - sizeof (void *), false >> - PASS_MEM_STAT); >> -} >> - >> -/* Ensure there are at least RESERVE free slots in VEC, growing >> - exactly. If RESERVE < 0 grow exactly, else grow exponentially. As >> - a special case, if VEC is NULL, and RESERVE is 0, no vector will be >> - created. */ >> - >> -void * >> -vec_gc_p_reserve_exact (void *vec, int reserve MEM_STAT_DECL) >> -{ >> - return vec_gc_o_reserve_1 (vec, reserve, >> - sizeof (struct vec_prefix), >> - sizeof (void *), true >> - PASS_MEM_STAT); >> -} >> - >> -/* As for vec_gc_p_reserve, but for object vectors. The vector's >> - trailing array is at VEC_OFFSET offset and consists of ELT_SIZE >> - sized elements. */ >> - >> -void * >> -vec_gc_o_reserve (void *vec, int reserve, size_t vec_offset, size_t elt_size >> - MEM_STAT_DECL) >> -{ >> - return vec_gc_o_reserve_1 (vec, reserve, vec_offset, elt_size, false >> - PASS_MEM_STAT); >> -} >> - >> -/* As for vec_gc_p_reserve_exact, but for object vectors. The >> - vector's trailing array is at VEC_OFFSET offset and consists of >> - ELT_SIZE sized elements. */ >> - >> -void * >> -vec_gc_o_reserve_exact (void *vec, int reserve, size_t vec_offset, >> - size_t elt_size MEM_STAT_DECL) >> -{ >> - return vec_gc_o_reserve_1 (vec, reserve, vec_offset, elt_size, true >> - PASS_MEM_STAT); >> -} >> >> /* As for vec_gc_o_reserve_1, but for heap allocated vectors. */ >> >> -static void * >> +void * >> vec_heap_o_reserve_1 (void *vec, int reserve, size_t vec_offset, >> size_t elt_size, bool exact MEM_STAT_DECL) >> { >> @@ -334,47 +284,6 @@ vec_heap_o_reserve_1 (void *vec, int reserve, size_t vec_offset, >> return vec; >> } >> >> -/* As for vec_gc_p_reserve, but for heap allocated vectors. */ >> - >> -void * >> -vec_heap_p_reserve (void *vec, int reserve MEM_STAT_DECL) >> -{ >> - return vec_heap_o_reserve_1 (vec, reserve, >> - sizeof (struct vec_prefix), >> - sizeof (void *), false >> - PASS_MEM_STAT); >> -} >> - >> -/* As for vec_gc_p_reserve_exact, but for heap allocated vectors. */ >> - >> -void * >> -vec_heap_p_reserve_exact (void *vec, int reserve MEM_STAT_DECL) >> -{ >> - return vec_heap_o_reserve_1 (vec, reserve, >> - sizeof (struct vec_prefix), >> - sizeof (void *), true >> - PASS_MEM_STAT); >> -} >> - >> -/* As for vec_gc_o_reserve, but for heap allocated vectors. */ >> - >> -void * >> -vec_heap_o_reserve (void *vec, int reserve, size_t vec_offset, size_t elt_size >> - MEM_STAT_DECL) >> -{ >> - return vec_heap_o_reserve_1 (vec, reserve, vec_offset, elt_size, false >> - PASS_MEM_STAT); >> -} >> - >> -/* As for vec_gc_o_reserve_exact, but for heap allocated vectors. */ >> - >> -void * >> -vec_heap_o_reserve_exact (void *vec, int reserve, size_t vec_offset, >> - size_t elt_size MEM_STAT_DECL) >> -{ >> - return vec_heap_o_reserve_1 (vec, reserve, vec_offset, elt_size, true >> - PASS_MEM_STAT); >> -} >> >> /* Stack vectors are a little different. VEC_alloc turns into a call >> to vec_stack_p_reserve_exact1 and passes in space allocated via a >> @@ -456,28 +365,6 @@ vec_stack_o_reserve_1 (void *vec, int reserve, size_t vec_offset, >> /* Grow a vector allocated on the stack. */ >> >> void * >> -vec_stack_p_reserve (void *vec, int reserve MEM_STAT_DECL) >> -{ >> - return vec_stack_o_reserve_1 (vec, reserve, >> - sizeof (struct vec_prefix), >> - sizeof (void *), false >> - PASS_MEM_STAT); >> -} >> - >> -/* Exact version of vec_stack_p_reserve. */ >> - >> -void * >> -vec_stack_p_reserve_exact (void *vec, int reserve MEM_STAT_DECL) >> -{ >> - return vec_stack_o_reserve_1 (vec, reserve, >> - sizeof (struct vec_prefix), >> - sizeof (void *), true >> - PASS_MEM_STAT); >> -} >> - >> -/* Like vec_stack_p_reserve, but for objects. */ >> - >> -void * >> vec_stack_o_reserve (void *vec, int reserve, size_t vec_offset, >> size_t elt_size MEM_STAT_DECL) >> { >> @@ -485,7 +372,7 @@ vec_stack_o_reserve (void *vec, int reserve, size_t vec_offset, >> PASS_MEM_STAT); >> } >> >> -/* Like vec_stack_p_reserve_exact, but for objects. */ >> +/* Exact version of vec_stack_o_reserve. */ >> >> void * >> vec_stack_o_reserve_exact (void *vec, int reserve, size_t vec_offset, >> diff --git a/gcc/vec.h b/gcc/vec.h >> index d477958..cc7e819 100644 >> --- a/gcc/vec.h >> +++ b/gcc/vec.h >> @@ -1,7 +1,8 @@ >> /* Vector API for GNU compiler. >> - Copyright (C) 2004, 2005, 2007, 2008, 2009, 2010 >> + Copyright (C) 2004, 2005, 2007, 2008, 2009, 2010, 2011, 2012 >> 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. >> >> @@ -133,6 +134,86 @@ along with GCC; see the file COPYING3. If not see >> >> */ >> >> +#if ENABLE_CHECKING >> +#define VEC_CHECK_INFO ,__FILE__,__LINE__,__FUNCTION__ >> +#define VEC_CHECK_DECL ,const char *file_,unsigned line_,const char *function_ >> +#define VEC_CHECK_PASS ,file_,line_,function_ >> + >> +#define VEC_ASSERT(EXPR,OP,T,A) \ >> + (void)((EXPR) ? 0 : (VEC_ASSERT_FAIL(OP,VEC(T,A)), 0)) >> + >> +extern void vec_assert_fail (const char *, const char * VEC_CHECK_DECL) >> + ATTRIBUTE_NORETURN; >> +#define VEC_ASSERT_FAIL(OP,VEC) vec_assert_fail (OP,#VEC VEC_CHECK_PASS) >> +#else >> +#define VEC_CHECK_INFO >> +#define VEC_CHECK_DECL >> +#define VEC_CHECK_PASS >> +#define VEC_ASSERT(EXPR,OP,T,A) (void)(EXPR) >> +#endif >> + >> +#define VEC(T,A) vec_t<T> >> + >> +enum vec_allocation_t { heap, gc, stack }; >> + >> +struct GTY(()) vec_prefix >> +{ >> + unsigned num; >> + unsigned alloc; >> +}; >> + >> +/* Vector type, user visible. */ >> +template<typename T> >> +struct GTY(()) vec_t >> +{ >> + vec_prefix prefix; >> + T GTY((length ("%h.prefix.num"))) vec[1]; >> +}; >> + >> +/* FIXME cxx-conversion. Remove these definitions and update all >> + calling sites. */ >> +/* Vector of integer-like object. */ >> +#define DEF_VEC_I(T) struct vec_swallow_trailing_semi >> +#define DEF_VEC_ALLOC_I(T,A) struct vec_swallow_trailing_semi >> + >> +/* Vector of pointer to object. */ >> +#define DEF_VEC_P(T) struct vec_swallow_trailing_semi >> +#define DEF_VEC_ALLOC_P(T,A) struct vec_swallow_trailing_semi >> + >> +/* Vector of object. */ >> +#define DEF_VEC_O(T) struct vec_swallow_trailing_semi >> +#define DEF_VEC_ALLOC_O(T,A) struct vec_swallow_trailing_semi >> + >> +/* Vectors on the stack. */ >> +#define DEF_VEC_ALLOC_P_STACK(T) struct vec_swallow_trailing_semi >> +#define DEF_VEC_ALLOC_O_STACK(T) struct vec_swallow_trailing_semi >> +#define DEF_VEC_ALLOC_I_STACK(T) struct vec_swallow_trailing_semi >> + >> + >> +/* Support functions for stack vectors. */ >> +extern void *vec_stack_p_reserve_exact_1 (int, void *); >> +extern void *vec_stack_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL); >> +extern void *vec_stack_o_reserve_exact (void *, int, size_t, size_t >> + MEM_STAT_DECL); >> +extern void vec_stack_free (void *); >> + >> +/* Reallocate an array of elements with prefix. */ >> +template<typename T, enum vec_allocation_t A> >> +extern vec_t<T> *vec_reserve (vec_t<T> *, int MEM_STAT_DECL); >> + >> +template<typename T, enum vec_allocation_t A> >> +extern vec_t<T> *vec_reserve_exact (vec_t<T> *, int MEM_STAT_DECL); >> + >> +extern void dump_vec_loc_statistics (void); >> +extern void ggc_free (void *); >> +#ifdef GATHER_STATISTICS >> +void vec_heap_free (void *); >> +#else >> +/* Avoid problems with frontends that #define free(x). */ >> +#define vec_heap_free(V) (free) (V) >> +#endif >> + >> + >> /* Macros to invoke API calls. A single macro works for both pointer >> and object vectors, but the argument and return types might well be >> different. In each macro, T is the typedef of the vector elements, >> @@ -147,7 +228,14 @@ along with GCC; see the file COPYING3. If not see >> Return the number of active elements in V. V can be NULL, in which >> case zero is returned. */ >> >> -#define VEC_length(T,V) (VEC_OP(T,base,length)(VEC_BASE(V))) >> +#define VEC_length(T,V) (VEC_length_1<T> (V)) >> + >> +template<typename T> >> +static inline unsigned >> +VEC_length_1 (const vec_t<T> *vec_) >> +{ >> + return vec_ ? vec_->prefix.num : 0; >> +} >> >> >> /* Check if vector is empty >> @@ -155,7 +243,30 @@ along with GCC; see the file COPYING3. If not see >> >> Return nonzero if V is an empty vector (or V is NULL), zero otherwise. */ >> >> -#define VEC_empty(T,V) (VEC_length (T,V) == 0) >> +#define VEC_empty(T,V) (VEC_empty_1<T> (V)) >> + >> +template<typename T> >> +static inline bool >> +VEC_empty_1 (const vec_t<T> *vec_) >> +{ >> + return VEC_length (T, vec_) == 0; >> +} >> + >> + >> +/* Get the address of the array of elements >> + T *VEC_T_address (VEC(T) v) >> + >> + If you need to directly manipulate the array (for instance, you >> + want to feed it to qsort), use this accessor. */ >> + >> +#define VEC_address(T,V) (VEC_address_1<T> (V)) >> + >> +template<typename T> >> +static inline T * >> +VEC_address_1 (vec_t<T> *vec_) >> +{ >> + return vec_ ? vec_->vec : 0; >> +} >> >> >> /* Get the final element of the vector. >> @@ -165,16 +276,42 @@ along with GCC; see the file COPYING3. If not see >> >> Return the final element. V must not be empty. */ >> >> -#define VEC_last(T,V) (VEC_OP(T,base,last)(VEC_BASE(V) VEC_CHECK_INFO)) >> +#define VEC_last(T,V) (VEC_last_1<T> (V VEC_CHECK_INFO)) >> + >> +template<typename T> >> +static inline T& >> +VEC_last_1 (vec_t<T> *vec_ VEC_CHECK_DECL) >> +{ >> + VEC_ASSERT (vec_ && vec_->prefix.num, "last", T, base); >> + return vec_->vec[vec_->prefix.num - 1]; >> +} >> + >> >> /* Index into vector >> T VEC_T_index(VEC(T) *v, unsigned ix); // Integer >> T VEC_T_index(VEC(T) *v, unsigned ix); // Pointer >> T *VEC_T_index(VEC(T) *v, unsigned ix); // Object >> >> - Return the IX'th element. If IX must be in the domain of V. */ >> + Return the IX'th element. IX must be in the domain of V. */ >> + >> +#define VEC_index(T,V,I) (VEC_index_1<T> (V, I VEC_CHECK_INFO)) >> + >> +template<typename T> >> +static inline T& >> +VEC_index_1 (vec_t<T> *vec_, unsigned ix_ VEC_CHECK_DECL) >> +{ >> + VEC_ASSERT (vec_ && ix_ < vec_->prefix.num, "index", T, base); >> + return vec_->vec[ix_]; >> +} >> + >> +template<typename T> >> +static inline const T& >> +VEC_index_1 (const vec_t<T> *vec_, unsigned ix_ VEC_CHECK_DECL) >> +{ >> + VEC_ASSERT (vec_ && ix_ < vec_->prefix.num, "index", T, base); >> + return vec_->vec[ix_]; >> +} >> >> -#define VEC_index(T,V,I) (VEC_OP(T,base,index)(VEC_BASE(V),I VEC_CHECK_INFO)) >> >> /* Iterate over vector >> int VEC_T_iterate(VEC(T) *v, unsigned ix, T &ptr); // Integer >> @@ -188,7 +325,39 @@ along with GCC; see the file COPYING3. If not see >> for (ix = 0; VEC_iterate(T,v,ix,ptr); ix++) >> continue; */ >> >> -#define VEC_iterate(T,V,I,P) (VEC_OP(T,base,iterate)(VEC_BASE(V),I,&(P))) >> +#define VEC_iterate(T,V,I,P) (VEC_iterate_1<T> (V, I, &(P))) >> + >> +template<typename T> >> +static inline bool >> +VEC_iterate_1 (const vec_t<T> *vec_, unsigned ix_, T *ptr) >> +{ >> + if (vec_ && ix_ < vec_->prefix.num) >> + { >> + *ptr = vec_->vec[ix_]; >> + return true; >> + } >> + else >> + { >> + *ptr = 0; >> + return false; >> + } >> +} >> + >> +template<typename T> >> +static inline bool >> +VEC_iterate_1 (vec_t<T> *vec_, unsigned ix_, T **ptr) >> +{ >> + if (vec_ && ix_ < vec_->prefix.num) >> + { >> + *ptr = &vec_->vec[ix_]; >> + return true; >> + } >> + else >> + { >> + *ptr = 0; >> + return false; >> + } >> +} >> >> /* Convenience macro for forward iteration. */ >> >> @@ -207,31 +376,99 @@ along with GCC; see the file COPYING3. If not see >> VEC_iterate (T, (V), (I), (P)); \ >> (I)--) >> >> + >> +/* Use these to determine the required size and initialization of a >> + vector embedded within another structure (as the final member). >> + >> + size_t VEC_T_embedded_size(int reserve); >> + void VEC_T_embedded_init(VEC(T) *v, int reserve); >> + >> + These allow the caller to perform the memory allocation. */ >> + >> +#define VEC_embedded_size(T,N) (VEC_embedded_size_1<T> (N)) >> + >> +template<typename T> >> +static inline size_t >> +VEC_embedded_size_1 (int alloc_) >> +{ >> + return offsetof (vec_t<T>, vec) + alloc_ * sizeof (T); >> +} >> + >> +#define VEC_embedded_init(T,O,N) (VEC_embedded_init_1<T> (O, N)) >> + >> +template<typename T> >> +static inline void >> +VEC_embedded_init_1 (vec_t<T> *vec_, int alloc_) >> +{ >> + vec_->prefix.num = 0; >> + vec_->prefix.alloc = alloc_; >> +} >> + >> + >> /* Allocate new vector. >> VEC(T,A) *VEC_T_A_alloc(int reserve); >> >> Allocate a new vector with space for RESERVE objects. If RESERVE >> - is zero, NO vector is created. */ >> + is zero, NO vector is created. >> + >> + 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. >> + >> + 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 VEC(TYPE,stack) vector from the function >> + which allocated it. */ >> + >> +#define VEC_alloc(T,A,N) \ >> + ((A == stack) \ >> + ? VEC_alloc_1 (N, \ >> + XALLOCAVAR (vec_t<T>, \ >> + VEC_embedded_size_1<T> (N))) \ >> + : VEC_alloc_1<T, A> (N MEM_STAT_INFO)) >> + >> +template<typename T, enum vec_allocation_t A> >> +static inline vec_t<T> * >> +VEC_alloc_1 (int alloc_ MEM_STAT_DECL) >> +{ >> + return vec_reserve_exact<T, A> (NULL, alloc_ PASS_MEM_STAT); >> +} >> + >> +template<typename T> >> +static inline vec_t<T> * >> +VEC_alloc_1 (int alloc_, vec_t<T> *space) >> +{ >> + return (vec_t<T> *) vec_stack_p_reserve_exact_1 (alloc_, space); >> +} >> >> -#define VEC_alloc(T,A,N) (VEC_OP(T,A,alloc)(N MEM_STAT_INFO)) >> >> /* Free a vector. >> void VEC_T_A_free(VEC(T,A) *&); >> >> Free a vector and set it to NULL. */ >> >> -#define VEC_free(T,A,V) (VEC_OP(T,A,free)(&V)) >> - >> -/* Use these to determine the required size and initialization of a >> - vector embedded within another structure (as the final member). >> +#define VEC_free(T,A,V) (VEC_free_1<T, A> (&V)) >> >> - size_t VEC_T_embedded_size(int reserve); >> - void VEC_T_embedded_init(VEC(T) *v, int reserve); >> - >> - These allow the caller to perform the memory allocation. */ >> +template<typename T, enum vec_allocation_t A> >> +static inline void >> +VEC_free_1 (vec_t<T> **vec_) >> +{ >> + if (*vec_) >> + { >> + if (A == heap) >> + vec_heap_free (*vec_); >> + else if (A == gc) >> + ggc_free (*vec_); >> + else if (A == stack) >> + vec_stack_free (*vec_); >> + } >> + *vec_ = NULL; >> +} >> >> -#define VEC_embedded_size(T,N) (VEC_OP(T,base,embedded_size)(N)) >> -#define VEC_embedded_init(T,O,N) (VEC_OP(T,base,embedded_init)(VEC_BASE(O),N)) >> >> /* Copy a vector. >> VEC(T,A) *VEC_T_A_copy(VEC(T) *); >> @@ -239,7 +476,24 @@ along with GCC; see the file COPYING3. If not see >> Copy the live elements of a vector into a new vector. The new and >> old vectors need not be allocated by the same mechanism. */ >> >> -#define VEC_copy(T,A,V) (VEC_OP(T,A,copy)(VEC_BASE(V) MEM_STAT_INFO)) >> +#define VEC_copy(T,A,V) (VEC_copy_1<T, A> (V MEM_STAT_INFO)) >> + >> +template<typename T, enum vec_allocation_t A> >> +static inline vec_t<T> * >> +VEC_copy_1 (vec_t<T> *vec_ MEM_STAT_DECL) >> +{ >> + size_t len_ = vec_ ? vec_->prefix.num : 0; >> + vec_t<T> *new_vec_ = NULL; >> + >> + if (len_) >> + { >> + new_vec_ = vec_reserve_exact<T, A> (NULL, len_ PASS_MEM_STAT); >> + new_vec_->prefix.num = len_; >> + memcpy (new_vec_->vec, vec_->vec, sizeof (T) * len_); >> + } >> + return new_vec_; >> +} >> + >> >> /* Determine if a vector has additional capacity. >> >> @@ -251,8 +505,18 @@ along with GCC; see the file COPYING3. If not see >> nonzero in exactly the same circumstances that VEC_T_reserve >> will. */ >> >> -#define VEC_space(T,V,R) \ >> - (VEC_OP(T,base,space)(VEC_BASE(V),R VEC_CHECK_INFO)) >> +#define VEC_space(T,V,R) (VEC_space_1<T> (V, R VEC_CHECK_INFO)) >> + >> +template<typename T> >> +static inline int >> +VEC_space_1 (vec_t<T> *vec_, int alloc_ VEC_CHECK_DECL) >> +{ >> + VEC_ASSERT (alloc_ >= 0, "space", T, base); >> + return vec_ >> + ? vec_->prefix.alloc - vec_->prefix.num >= (unsigned)alloc_ >> + : !alloc_; >> +} >> + >> >> /* Reserve space. >> int VEC_T_A_reserve(VEC(T,A) *&v, int reserve); >> @@ -263,7 +527,20 @@ along with GCC; see the file COPYING3. If not see >> occurred. */ >> >> #define VEC_reserve(T,A,V,R) \ >> - (VEC_OP(T,A,reserve)(&(V),R VEC_CHECK_INFO MEM_STAT_INFO)) >> + (VEC_reserve_1<T, A> (&(V), (int)(R) VEC_CHECK_INFO MEM_STAT_INFO)) >> + >> +template<typename T, enum vec_allocation_t A> >> +static inline int >> +VEC_reserve_1 (vec_t<T> **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) >> +{ >> + int extend = !VEC_space_1 (*vec_, alloc_ VEC_CHECK_PASS); >> + >> + if (extend) >> + *vec_ = vec_reserve<T, A> (*vec_, alloc_ PASS_MEM_STAT); >> + >> + return extend; >> +} >> + >> >> /* Reserve space exactly. >> int VEC_T_A_reserve_exact(VEC(T,A) *&v, int reserve); >> @@ -274,7 +551,20 @@ along with GCC; see the file COPYING3. If not see >> occurred. */ >> >> #define VEC_reserve_exact(T,A,V,R) \ >> - (VEC_OP(T,A,reserve_exact)(&(V),R VEC_CHECK_INFO MEM_STAT_INFO)) >> + (VEC_reserve_exact_1<T, A> (&(V), R VEC_CHECK_INFO MEM_STAT_INFO)) >> + >> +template<typename T, enum vec_allocation_t A> >> +static inline int >> +VEC_reserve_exact_1 (vec_t<T> **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) >> +{ >> + int extend = !VEC_space_1 (*vec_, alloc_ VEC_CHECK_PASS); >> + >> + if (extend) >> + *vec_ = vec_reserve_exact<T, A> (*vec_, alloc_ PASS_MEM_STAT); >> + >> + return extend; >> +} >> + >> >> /* Copy elements with no reallocation >> void VEC_T_splice (VEC(T) *dst, VEC(T) *src); // Integer >> @@ -286,8 +576,23 @@ along with GCC; see the file COPYING3. If not see >> often will be. DST is assumed to have sufficient headroom >> available. */ >> >> -#define VEC_splice(T,DST,SRC) \ >> - (VEC_OP(T,base,splice)(VEC_BASE(DST), VEC_BASE(SRC) VEC_CHECK_INFO)) >> +#define VEC_splice(T,DST,SRC) (VEC_splice_1<T> (DST, SRC VEC_CHECK_INFO)) >> + >> +template<typename T> >> +static inline void >> +VEC_splice_1 (vec_t<T> *dst_, vec_t<T> *src_ VEC_CHECK_DECL) >> +{ >> + if (src_) >> + { >> + unsigned len_ = src_->prefix.num; >> + VEC_ASSERT (dst_->prefix.num + len_ <= dst_->prefix.alloc, "splice", >> + T, base); >> + >> + memcpy (&dst_->vec[dst_->prefix.num], &src_->vec[0], len_ * sizeof (T)); >> + dst_->prefix.num += len_; >> + } >> +} >> + >> >> /* Copy elements with reallocation >> void VEC_T_safe_splice (VEC(T,A) *&dst, VEC(T) *src); // Integer >> @@ -300,7 +605,21 @@ along with GCC; see the file COPYING3. If not see >> reallocated if needed. */ >> >> #define VEC_safe_splice(T,A,DST,SRC) \ >> - (VEC_OP(T,A,safe_splice)(&(DST), VEC_BASE(SRC) VEC_CHECK_INFO MEM_STAT_INFO)) >> + (VEC_safe_splice_1<T, A> (&(DST), SRC VEC_CHECK_INFO MEM_STAT_INFO)) >> + >> +template<typename T, enum vec_allocation_t A> >> +static inline void >> +VEC_safe_splice_1 (vec_t<T> **dst_, vec_t<T> *src_ VEC_CHECK_DECL MEM_STAT_DECL) >> +{ >> + if (src_) >> + { >> + VEC_reserve_exact_1<T, A> (dst_, src_->prefix.num >> + VEC_CHECK_PASS MEM_STAT_INFO); >> + >> + VEC_splice_1 (*dst_, src_ VEC_CHECK_PASS); >> + } >> +} >> + >> >> /* Push object with no reallocation >> T *VEC_T_quick_push (VEC(T) *v, T obj); // Integer >> @@ -312,8 +631,31 @@ along with GCC; see the file COPYING3. If not see >> case NO initialization is performed. There must >> be sufficient space in the vector. */ >> >> -#define VEC_quick_push(T,V,O) \ >> - (VEC_OP(T,base,quick_push)(VEC_BASE(V),O VEC_CHECK_INFO)) >> +#define VEC_quick_push(T,V,O) (VEC_quick_push_1<T> (V, O VEC_CHECK_INFO)) >> + >> +template<typename T> >> +static inline T & >> +VEC_quick_push_1 (vec_t<T> *vec_, T obj_ VEC_CHECK_DECL) >> +{ >> + VEC_ASSERT (vec_->prefix.num < vec_->prefix.alloc, "push", T, base); >> + vec_->vec[vec_->prefix.num] = obj_; >> + T &val_ = vec_->vec[vec_->prefix.num]; >> + vec_->prefix.num++; >> + return val_; >> +} >> + >> +template<typename T> >> +static inline T * >> +VEC_quick_push_1 (vec_t<T> *vec_, const T *ptr_ VEC_CHECK_DECL) >> +{ >> + T *slot_; >> + VEC_ASSERT (vec_->prefix.num < vec_->prefix.alloc, "push", T, base); >> + slot_ = &vec_->vec[vec_->prefix.num++]; >> + if (ptr_) >> + *slot_ = *ptr_; >> + return slot_; >> +} >> + >> >> /* Push object with reallocation >> T *VEC_T_A_safe_push (VEC(T,A) *&v, T obj); // Integer >> @@ -325,7 +667,24 @@ along with GCC; see the file COPYING3. If not see >> case NO initialization is performed. Reallocates V, if needed. */ >> >> #define VEC_safe_push(T,A,V,O) \ >> - (VEC_OP(T,A,safe_push)(&(V),O VEC_CHECK_INFO MEM_STAT_INFO)) >> + (VEC_safe_push_1<T, A> (&(V), O VEC_CHECK_INFO MEM_STAT_INFO)) >> + >> +template<typename T, enum vec_allocation_t A> >> +static inline T & >> +VEC_safe_push_1 (vec_t<T> **vec_, T obj_ VEC_CHECK_DECL MEM_STAT_DECL) >> +{ >> + VEC_reserve_1<T, A> (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); >> + return VEC_quick_push_1 (*vec_, obj_ VEC_CHECK_PASS); >> +} >> + >> +template<typename T, enum vec_allocation_t A> >> +static inline T * >> +VEC_safe_push_1 (vec_t<T> **vec_, const T *ptr_ VEC_CHECK_DECL MEM_STAT_DECL) >> +{ >> + VEC_reserve_1<T, A> (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); >> + return VEC_quick_push_1 (*vec_, ptr_ VEC_CHECK_PASS); >> +} >> + >> >> /* Pop element off end >> T VEC_T_pop (VEC(T) *v); // Integer >> @@ -335,7 +694,16 @@ along with GCC; see the file COPYING3. If not see >> Pop the last element off the end. Returns the element popped, for >> pointer vectors. */ >> >> -#define VEC_pop(T,V) (VEC_OP(T,base,pop)(VEC_BASE(V) VEC_CHECK_INFO)) >> +#define VEC_pop(T,V) (VEC_pop_1<T> (V VEC_CHECK_INFO)) >> + >> +template<typename T> >> +static inline T& >> +VEC_pop_1 (vec_t<T> *vec_ VEC_CHECK_DECL) >> +{ >> + VEC_ASSERT (vec_->prefix.num, "pop", T, base); >> + return vec_->vec[--vec_->prefix.num]; >> +} >> + >> >> /* Truncate to specific length >> void VEC_T_truncate (VEC(T) *v, unsigned len); >> @@ -343,8 +711,18 @@ along with GCC; see the file COPYING3. If not see >> Set the length as specified. The new length must be less than or >> equal to the current length. This is an O(1) operation. */ >> >> -#define VEC_truncate(T,V,I) \ >> - (VEC_OP(T,base,truncate)(VEC_BASE(V),I VEC_CHECK_INFO)) >> +#define VEC_truncate(T,V,I) \ >> + (VEC_truncate_1<T> (V, (unsigned)(I) VEC_CHECK_INFO)) >> + >> +template<typename T> >> +static inline void >> +VEC_truncate_1 (vec_t<T> *vec_, unsigned size_ VEC_CHECK_DECL) >> +{ >> + VEC_ASSERT (vec_ ? vec_->prefix.num >= size_ : !size_, "truncate", T, base); >> + if (vec_) >> + vec_->prefix.num = size_; >> +} >> + >> >> /* Grow to a specific length. >> void VEC_T_A_safe_grow (VEC(T,A) *&v, int len); >> @@ -354,7 +732,20 @@ along with GCC; see the file COPYING3. If not see >> uninitialized. */ >> >> #define VEC_safe_grow(T,A,V,I) \ >> - (VEC_OP(T,A,safe_grow)(&(V),I VEC_CHECK_INFO MEM_STAT_INFO)) >> + (VEC_safe_grow_1<T, A> (&(V), (int)(I) VEC_CHECK_INFO MEM_STAT_INFO)) >> + >> +template<typename T, enum vec_allocation_t A> >> +static inline void >> +VEC_safe_grow_1 (vec_t<T> **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) >> +{ >> + VEC_ASSERT (size_ >= 0 && VEC_length (T, *vec_) <= (unsigned)size_, >> + "grow", T, A); >> + VEC_reserve_exact_1<T, A> (vec_, >> + size_ - (int)(*vec_ ? (*vec_)->prefix.num : 0) >> + VEC_CHECK_PASS PASS_MEM_STAT); >> + (*vec_)->prefix.num = size_; >> +} >> + >> >> /* Grow to a specific length. >> void VEC_T_A_safe_grow_cleared (VEC(T,A) *&v, int len); >> @@ -363,8 +754,21 @@ along with GCC; see the file COPYING3. If not see >> long or longer than the current length. The new elements are >> initialized to zero. */ >> >> -#define VEC_safe_grow_cleared(T,A,V,I) \ >> - (VEC_OP(T,A,safe_grow_cleared)(&(V),I VEC_CHECK_INFO MEM_STAT_INFO)) >> +#define VEC_safe_grow_cleared(T,A,V,I) \ >> + (VEC_safe_grow_cleared_1<T,A> (&(V), (int)(I) \ >> + VEC_CHECK_INFO MEM_STAT_INFO)) >> + >> +template<typename T, enum vec_allocation_t A> >> +static inline void >> +VEC_safe_grow_cleared_1 (vec_t<T> **vec_, int size_ VEC_CHECK_DECL >> + MEM_STAT_DECL) >> +{ >> + int oldsize = VEC_length (T, *vec_); >> + VEC_safe_grow_1<T, A> (vec_, size_ VEC_CHECK_PASS PASS_MEM_STAT); >> + memset (&(VEC_address (T, *vec_)[oldsize]), 0, >> + sizeof (T) * (size_ - oldsize)); >> +} >> + >> >> /* Replace element >> T VEC_T_replace (VEC(T) *v, unsigned ix, T val); // Integer >> @@ -378,20 +782,57 @@ along with GCC; see the file COPYING3. If not see >> performed. */ >> >> #define VEC_replace(T,V,I,O) \ >> - (VEC_OP(T,base,replace)(VEC_BASE(V),I,O VEC_CHECK_INFO)) >> + (VEC_replace_1<T> (V, (unsigned)(I), O VEC_CHECK_INFO)) >> + >> +template<typename T> >> +static inline T& >> +VEC_replace_1 (vec_t<T> *vec_, unsigned ix_, T obj_ VEC_CHECK_DECL) >> +{ >> + VEC_ASSERT (ix_ < vec_->prefix.num, "replace", T, base); >> + vec_->vec[ix_] = obj_; >> + return vec_->vec[ix_]; >> +} >> + >> >> /* Insert object with no reallocation >> - T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Integer >> - T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Pointer >> - T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T *val); // Object >> + void VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Integer >> + void VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Pointer >> + void VEC_T_quick_insert (VEC(T) *v, unsigned ix, T *val); // Object >> >> - Insert an element, VAL, at the IXth position of V. Return a pointer >> - to the slot created. For vectors of object, the new value can be >> - NULL, in which case no initialization of the inserted slot takes >> - place. There must be sufficient space. */ >> + Insert an element, VAL, at the IXth position of V. For vectors of >> + object, the new value can be NULL, in which case no initialization >> + of the inserted slot takes place. There must be sufficient space. */ >> >> #define VEC_quick_insert(T,V,I,O) \ >> - (VEC_OP(T,base,quick_insert)(VEC_BASE(V),I,O VEC_CHECK_INFO)) >> + (VEC_quick_insert_1<T> (V,I,O VEC_CHECK_INFO)) >> + >> +template<typename T> >> +static inline void >> +VEC_quick_insert_1 (vec_t<T> *vec_, unsigned ix_, T obj_ VEC_CHECK_DECL) >> +{ >> + T *slot_; >> + >> + VEC_ASSERT (vec_->prefix.num < vec_->prefix.alloc, "insert", T, base); >> + VEC_ASSERT (ix_ <= vec_->prefix.num, "insert", T, base); >> + slot_ = &vec_->vec[ix_]; >> + memmove (slot_ + 1, slot_, (vec_->prefix.num++ - ix_) * sizeof (T)); >> + *slot_ = obj_; >> +} >> + >> +template<typename T> >> +static inline void >> +VEC_quick_insert_1 (vec_t<T> *vec_, unsigned ix_, const T *ptr_ VEC_CHECK_DECL) >> +{ >> + T *slot_; >> + >> + VEC_ASSERT (vec_->prefix.num < vec_->prefix.alloc, "insert", T, base); >> + VEC_ASSERT (ix_ <= vec_->prefix.num, "insert", T, base); >> + slot_ = &vec_->vec[ix_]; >> + memmove (slot_ + 1, slot_, (vec_->prefix.num++ - ix_) * sizeof (T)); >> + if (ptr_) >> + *slot_ = *ptr_; >> +} >> + >> >> /* Insert object with reallocation >> T *VEC_T_A_safe_insert (VEC(T,A) *&v, unsigned ix, T val); // Integer >> @@ -404,31 +845,70 @@ along with GCC; see the file COPYING3. If not see >> place. Reallocate V, if necessary. */ >> >> #define VEC_safe_insert(T,A,V,I,O) \ >> - (VEC_OP(T,A,safe_insert)(&(V),I,O VEC_CHECK_INFO MEM_STAT_INFO)) >> + (VEC_safe_insert_1<T, A> (&(V),I,O VEC_CHECK_INFO MEM_STAT_INFO)) >> + >> +template<typename T, enum vec_allocation_t A> >> +static inline void >> +VEC_safe_insert_1 (vec_t<T> **vec_, unsigned ix_, T obj_ >> + VEC_CHECK_DECL MEM_STAT_DECL) >> +{ >> + VEC_reserve_1<T, A> (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); >> + VEC_quick_insert_1 (*vec_, ix_, obj_ VEC_CHECK_PASS); >> +} >> + >> +template<typename T, enum vec_allocation_t A> >> +static inline void >> +VEC_safe_insert_1 (vec_t<T> **vec_, unsigned ix_, T *ptr_ >> + VEC_CHECK_DECL MEM_STAT_DECL) >> +{ >> + VEC_reserve_1<T, A> (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); >> + VEC_quick_insert_1 (*vec_, ix_, ptr_ VEC_CHECK_PASS); >> +} >> + >> + >> >> /* Remove element retaining order >> - T VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Integer >> - T VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Pointer >> + void VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Integer >> + void VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Pointer >> void VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Object >> >> Remove an element from the IXth position of V. Ordering of >> - remaining elements is preserved. For pointer vectors returns the >> - removed object. This is an O(N) operation due to a memmove. */ >> + remaining elements is preserved. This is an O(N) operation due to >> + a memmove. */ >> >> #define VEC_ordered_remove(T,V,I) \ >> - (VEC_OP(T,base,ordered_remove)(VEC_BASE(V),I VEC_CHECK_INFO)) >> + (VEC_ordered_remove_1<T> (V,I VEC_CHECK_INFO)) >> + >> +template<typename T> >> +static inline void >> +VEC_ordered_remove_1 (vec_t<T> *vec_, unsigned ix_ VEC_CHECK_DECL) >> +{ >> + T *slot_; >> + VEC_ASSERT (ix_ < vec_->prefix.num, "remove", T, base); >> + slot_ = &vec_->vec[ix_]; >> + memmove (slot_, slot_ + 1, (--vec_->prefix.num - ix_) * sizeof (T)); >> +} >> + >> >> /* Remove element destroying order >> - T VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Integer >> - T VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Pointer >> + void VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Integer >> + void VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Pointer >> void VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Object >> >> - Remove an element from the IXth position of V. Ordering of >> - remaining elements is destroyed. For pointer vectors returns the >> - removed object. This is an O(1) operation. */ >> + Remove an element from the IXth position of V. Ordering of >> + remaining elements is destroyed. This is an O(1) operation. */ >> >> #define VEC_unordered_remove(T,V,I) \ >> - (VEC_OP(T,base,unordered_remove)(VEC_BASE(V),I VEC_CHECK_INFO)) >> + (VEC_unordered_remove_1<T> (V,I VEC_CHECK_INFO)) >> + >> +template<typename T> >> +static inline void >> +VEC_unordered_remove_1 (vec_t<T> *vec_, unsigned ix_ VEC_CHECK_DECL) >> +{ >> + VEC_ASSERT (ix_ < vec_->prefix.num, "remove", T, base); >> + vec_->vec[ix_] = vec_->vec[--vec_->prefix.num]; >> +} >> + >> >> /* Remove a block of elements >> void VEC_T_block_remove (VEC(T) *v, unsigned ix, unsigned len); >> @@ -437,22 +917,27 @@ along with GCC; see the file COPYING3. If not see >> This is an O(N) operation due to memmove. */ >> >> #define VEC_block_remove(T,V,I,L) \ >> - (VEC_OP(T,base,block_remove)(VEC_BASE(V),I,L VEC_CHECK_INFO)) >> + (VEC_block_remove_1<T> (V, I, L VEC_CHECK_INFO)) >> >> -/* Get the address of the array of elements >> - T *VEC_T_address (VEC(T) v) >> - >> - If you need to directly manipulate the array (for instance, you >> - want to feed it to qsort), use this accessor. */ >> +template<typename T> >> +static inline void >> +VEC_block_remove_1 (vec_t<T> *vec_, unsigned ix_, unsigned len_ VEC_CHECK_DECL) >> +{ >> + T *slot_; >> + VEC_ASSERT (ix_ + len_ <= vec_->prefix.num, "block_remove", T, base); >> + slot_ = &vec_->vec[ix_]; >> + vec_->prefix.num -= len_; >> + memmove (slot_, slot_ + len_, (vec_->prefix.num - ix_) * sizeof (T)); >> +} >> >> -#define VEC_address(T,V) (VEC_OP(T,base,address)(VEC_BASE(V))) >> >> /* Conveniently sort the contents of the vector with qsort. >> void VEC_qsort (VEC(T) *v, int (*cmp_func)(const void *, const void *)) */ >> >> -#define VEC_qsort(T,V,CMP) qsort(VEC_address (T,V), VEC_length(T,V), \ >> +#define VEC_qsort(T,V,CMP) qsort(VEC_address (T, V), VEC_length (T, V), \ >> sizeof (T), CMP) >> >> + >> /* Find the first index in the vector not less than the object. >> unsigned VEC_T_lower_bound (VEC(T) *v, const T val, >> bool (*lessthan) (const T, const T)); // Integer >> @@ -465,944 +950,140 @@ along with GCC; see the file COPYING3. If not see >> changing the ordering of V. LESSTHAN is a function that returns >> true if the first argument is strictly less than the second. */ >> >> -#define VEC_lower_bound(T,V,O,LT) \ >> - (VEC_OP(T,base,lower_bound)(VEC_BASE(V),O,LT VEC_CHECK_INFO)) >> - >> -/* Reallocate an array of elements with prefix. */ >> -extern void *vec_gc_p_reserve (void *, int MEM_STAT_DECL); >> -extern void *vec_gc_p_reserve_exact (void *, int MEM_STAT_DECL); >> -extern void *vec_gc_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL); >> -extern void *vec_gc_o_reserve_exact (void *, int, size_t, size_t >> - MEM_STAT_DECL); >> -extern void ggc_free (void *); >> -#define vec_gc_free(V) ggc_free (V) >> -extern void *vec_heap_p_reserve (void *, int MEM_STAT_DECL); >> -extern void *vec_heap_p_reserve_exact (void *, int MEM_STAT_DECL); >> -extern void *vec_heap_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL); >> -extern void *vec_heap_o_reserve_exact (void *, int, size_t, size_t >> - MEM_STAT_DECL); >> -extern void dump_vec_loc_statistics (void); >> -#ifdef GATHER_STATISTICS >> -void vec_heap_free (void *); >> -#else >> -/* Avoid problems with frontends that #define free(x). */ >> -#define vec_heap_free(V) (free) (V) >> -#endif >> - >> -#if ENABLE_CHECKING >> -#define VEC_CHECK_INFO ,__FILE__,__LINE__,__FUNCTION__ >> -#define VEC_CHECK_DECL ,const char *file_,unsigned line_,const char *function_ >> -#define VEC_CHECK_PASS ,file_,line_,function_ >> +#define VEC_lower_bound(T,V,O,LT) \ >> + (VEC_lower_bound_1<T> (V, O, LT VEC_CHECK_INFO)) >> >> -#define VEC_ASSERT(EXPR,OP,T,A) \ >> - (void)((EXPR) ? 0 : (VEC_ASSERT_FAIL(OP,VEC(T,A)), 0)) >> - >> -extern void vec_assert_fail (const char *, const char * VEC_CHECK_DECL) >> - ATTRIBUTE_NORETURN; >> -#define VEC_ASSERT_FAIL(OP,VEC) vec_assert_fail (OP,#VEC VEC_CHECK_PASS) >> -#else >> -#define VEC_CHECK_INFO >> -#define VEC_CHECK_DECL >> -#define VEC_CHECK_PASS >> -#define VEC_ASSERT(EXPR,OP,T,A) (void)(EXPR) >> -#endif >> - >> -/* Note: gengtype has hardwired knowledge of the expansions of the >> - VEC, DEF_VEC_*, and DEF_VEC_ALLOC_* macros. If you change the >> - expansions of these macros you may need to change gengtype too. */ >> - >> -typedef struct GTY(()) vec_prefix >> +template<typename T> >> +static inline unsigned >> +VEC_lower_bound_1 (vec_t<T> *vec_, T obj_, >> + bool (*lessthan_)(T, T) VEC_CHECK_DECL) >> { >> - unsigned num; >> - unsigned alloc; >> -} vec_prefix; >> - >> -#define VEC(T,A) VEC_##T##_##A >> -#define VEC_OP(T,A,OP) VEC_##T##_##A##_##OP >> - >> -/* Base of vector type, not user visible. */ >> -#define VEC_T(T,B) \ >> -typedef struct VEC(T,B) \ >> -{ \ >> - struct vec_prefix prefix; \ >> - T vec[1]; \ >> -} VEC(T,B) >> - >> -#define VEC_T_GTY(T,B) \ >> -typedef struct GTY(()) VEC(T,B) \ >> -{ \ >> - struct vec_prefix prefix; \ >> - T GTY ((length ("%h.prefix.num"))) vec[1]; \ >> -} VEC(T,B) >> - >> -/* Derived vector type, user visible. */ >> -#define VEC_TA_GTY(T,B,A,GTY) \ >> -typedef struct GTY VEC(T,A) \ >> -{ \ >> - VEC(T,B) base; \ >> -} VEC(T,A) >> - >> -#define VEC_TA(T,B,A) \ >> -typedef struct VEC(T,A) \ >> -{ \ >> - VEC(T,B) base; \ >> -} VEC(T,A) >> - >> -/* Convert to base type. */ >> -#if GCC_VERSION >= 4000 >> -#define VEC_BASE(P) \ >> - ((offsetof (__typeof (*P), base) == 0 || (P)) ? &(P)->base : 0) >> -#else >> -#define VEC_BASE(P) ((P) ? &(P)->base : 0) >> -#endif >> - >> -/* Vector of integer-like object. */ >> -#define DEF_VEC_I(T) \ >> -static inline void VEC_OP (T,must_be,integral_type) (void) \ >> -{ \ >> - (void)~(T)0; \ >> -} \ >> - \ >> -VEC_T(T,base); \ >> -VEC_TA(T,base,none); \ >> -DEF_VEC_FUNC_P(T) \ >> -struct vec_swallow_trailing_semi >> -#define DEF_VEC_ALLOC_I(T,A) \ >> -VEC_TA(T,base,A); \ >> -DEF_VEC_ALLOC_FUNC_I(T,A) \ >> -DEF_VEC_NONALLOC_FUNCS_I(T,A) \ >> -struct vec_swallow_trailing_semi >> - >> -/* Vector of pointer to object. */ >> -#define DEF_VEC_P(T) \ >> -static inline void VEC_OP (T,must_be,pointer_type) (void) \ >> -{ \ >> - (void)((T)1 == (void *)1); \ >> -} \ >> - \ >> -VEC_T_GTY(T,base); \ >> -VEC_TA(T,base,none); \ >> -DEF_VEC_FUNC_P(T) \ >> -struct vec_swallow_trailing_semi >> -#define DEF_VEC_ALLOC_P(T,A) \ >> -VEC_TA(T,base,A); \ >> -DEF_VEC_ALLOC_FUNC_P(T,A) \ >> -DEF_VEC_NONALLOC_FUNCS_P(T,A) \ >> -struct vec_swallow_trailing_semi >> - >> -#define DEF_VEC_FUNC_P(T) \ >> -static inline unsigned VEC_OP (T,base,length) (const VEC(T,base) *vec_) \ >> -{ \ >> - return vec_ ? vec_->prefix.num : 0; \ >> -} \ >> - \ >> -static inline T VEC_OP (T,base,last) \ >> - (const VEC(T,base) *vec_ VEC_CHECK_DECL) \ >> -{ \ >> - VEC_ASSERT (vec_ && vec_->prefix.num, "last", T, base); \ >> - \ >> - return vec_->vec[vec_->prefix.num - 1]; \ >> -} \ >> - \ >> -static inline T VEC_OP (T,base,index) \ >> - (const VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \ >> -{ \ >> - VEC_ASSERT (vec_ && ix_ < vec_->prefix.num, "index", T, base); \ >> - \ >> - return vec_->vec[ix_]; \ >> -} \ >> - \ >> -static inline int VEC_OP (T,base,iterate) \ >> - (const VEC(T,base) *vec_, unsigned ix_, T *ptr) \ >> -{ \ >> - if (vec_ && ix_ < vec_->prefix.num) \ >> - { \ >> - *ptr = vec_->vec[ix_]; \ >> - return 1; \ >> - } \ >> - else \ >> - { \ >> - *ptr = (T) 0; \ >> - return 0; \ >> - } \ >> -} \ >> - \ >> -static inline size_t VEC_OP (T,base,embedded_size) \ >> - (int alloc_) \ >> -{ \ >> - return offsetof (VEC(T,base),vec) + alloc_ * sizeof(T); \ >> -} \ >> - \ >> -static inline void VEC_OP (T,base,embedded_init) \ >> - (VEC(T,base) *vec_, int alloc_) \ >> -{ \ >> - vec_->prefix.num = 0; \ >> - vec_->prefix.alloc = alloc_; \ >> -} \ >> - \ >> -static inline int VEC_OP (T,base,space) \ >> - (VEC(T,base) *vec_, int alloc_ VEC_CHECK_DECL) \ >> -{ \ >> - VEC_ASSERT (alloc_ >= 0, "space", T, base); \ >> - return vec_ ? vec_->prefix.alloc - vec_->prefix.num >= (unsigned)alloc_ : !alloc_; \ >> -} \ >> - \ >> -static inline void VEC_OP(T,base,splice) \ >> - (VEC(T,base) *dst_, VEC(T,base) *src_ VEC_CHECK_DECL) \ >> -{ \ >> - if (src_) \ >> - { \ >> - unsigned len_ = src_->prefix.num; \ >> - VEC_ASSERT (dst_->prefix.num + len_ <= dst_->prefix.alloc, "splice", T, base); \ >> - \ >> - memcpy (&dst_->vec[dst_->prefix.num], &src_->vec[0], len_ * sizeof (T)); \ >> - dst_->prefix.num += len_; \ >> - } \ >> -} \ >> - \ >> -static inline T *VEC_OP (T,base,quick_push) \ >> - (VEC(T,base) *vec_, T obj_ VEC_CHECK_DECL) \ >> -{ \ >> - T *slot_; \ >> - \ >> - VEC_ASSERT (vec_->prefix.num < vec_->prefix.alloc, "push", T, base); \ >> - slot_ = &vec_->vec[vec_->prefix.num++]; \ >> - *slot_ = obj_; \ >> - \ >> - return slot_; \ >> -} \ >> - \ >> -static inline T VEC_OP (T,base,pop) (VEC(T,base) *vec_ VEC_CHECK_DECL) \ >> -{ \ >> - T obj_; \ >> - \ >> - VEC_ASSERT (vec_->prefix.num, "pop", T, base); \ >> - obj_ = vec_->vec[--vec_->prefix.num]; \ >> - \ >> - return obj_; \ >> -} \ >> - \ >> -static inline void VEC_OP (T,base,truncate) \ >> - (VEC(T,base) *vec_, unsigned size_ VEC_CHECK_DECL) \ >> -{ \ >> - VEC_ASSERT (vec_ ? vec_->prefix.num >= size_ : !size_, "truncate", T, base); \ >> - if (vec_) \ >> - vec_->prefix.num = size_; \ >> -} \ >> - \ >> -static inline T VEC_OP (T,base,replace) \ >> - (VEC(T,base) *vec_, unsigned ix_, T obj_ VEC_CHECK_DECL) \ >> -{ \ >> - T old_obj_; \ >> - \ >> - VEC_ASSERT (ix_ < vec_->prefix.num, "replace", T, base); \ >> - old_obj_ = vec_->vec[ix_]; \ >> - vec_->vec[ix_] = obj_; \ >> - \ >> - return old_obj_; \ >> -} \ >> - \ >> -static inline T *VEC_OP (T,base,quick_insert) \ >> - (VEC(T,base) *vec_, unsigned ix_, T obj_ VEC_CHECK_DECL) \ >> -{ \ >> - T *slot_; \ >> - \ >> - VEC_ASSERT (vec_->prefix.num < vec_->prefix.alloc, "insert", T, base); \ >> - VEC_ASSERT (ix_ <= vec_->prefix.num, "insert", T, base); \ >> - slot_ = &vec_->vec[ix_]; \ >> - memmove (slot_ + 1, slot_, (vec_->prefix.num++ - ix_) * sizeof (T)); \ >> - *slot_ = obj_; \ >> - \ >> - return slot_; \ >> -} \ >> - \ >> -static inline T VEC_OP (T,base,ordered_remove) \ >> - (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \ >> -{ \ >> - T *slot_; \ >> - T obj_; \ >> - \ >> - VEC_ASSERT (ix_ < vec_->prefix.num, "remove", T, base); \ >> - slot_ = &vec_->vec[ix_]; \ >> - obj_ = *slot_; \ >> - memmove (slot_, slot_ + 1, (--vec_->prefix.num - ix_) * sizeof (T)); \ >> - \ >> - return obj_; \ >> -} \ >> - \ >> -static inline T VEC_OP (T,base,unordered_remove) \ >> - (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \ >> -{ \ >> - T *slot_; \ >> - T obj_; \ >> - \ >> - VEC_ASSERT (ix_ < vec_->prefix.num, "remove", T, base); \ >> - slot_ = &vec_->vec[ix_]; \ >> - obj_ = *slot_; \ >> - *slot_ = vec_->vec[--vec_->prefix.num]; \ >> - \ >> - return obj_; \ >> -} \ >> - \ >> -static inline void VEC_OP (T,base,block_remove) \ >> - (VEC(T,base) *vec_, unsigned ix_, unsigned len_ VEC_CHECK_DECL) \ >> -{ \ >> - T *slot_; \ >> - \ >> - VEC_ASSERT (ix_ + len_ <= vec_->prefix.num, "block_remove", T, base); \ >> - slot_ = &vec_->vec[ix_]; \ >> - vec_->prefix.num -= len_; \ >> - memmove (slot_, slot_ + len_, (vec_->prefix.num - ix_) * sizeof (T)); \ >> -} \ >> - \ >> -static inline T *VEC_OP (T,base,address) \ >> - (VEC(T,base) *vec_) \ >> -{ \ >> - return vec_ ? vec_->vec : 0; \ >> -} \ >> - \ >> -static inline unsigned VEC_OP (T,base,lower_bound) \ >> - (VEC(T,base) *vec_, const T obj_, \ >> - bool (*lessthan_)(const T, const T) VEC_CHECK_DECL) \ >> -{ \ >> - unsigned int len_ = VEC_OP (T,base, length) (vec_); \ >> - unsigned int half_, middle_; \ >> - unsigned int first_ = 0; \ >> - while (len_ > 0) \ >> - { \ >> - T middle_elem_; \ >> - half_ = len_ >> 1; \ >> - middle_ = first_; \ >> - middle_ += half_; \ >> - middle_elem_ = VEC_OP (T,base,index) (vec_, middle_ VEC_CHECK_PASS); \ >> - if (lessthan_ (middle_elem_, obj_)) \ >> - { \ >> - first_ = middle_; \ >> - ++first_; \ >> - len_ = len_ - half_ - 1; \ >> - } \ >> - else \ >> - len_ = half_; \ >> - } \ >> - return first_; \ >> -} >> - >> -#define DEF_VEC_ALLOC_FUNC_P(T,A) \ >> -static inline VEC(T,A) *VEC_OP (T,A,alloc) \ >> - (int alloc_ MEM_STAT_DECL) \ >> -{ \ >> - return (VEC(T,A) *) vec_##A##_p_reserve_exact (NULL, alloc_ \ >> - PASS_MEM_STAT); \ >> + unsigned int len_ = VEC_length (T, vec_); >> + unsigned int half_, middle_; >> + unsigned int first_ = 0; >> + while (len_ > 0) >> + { >> + T middle_elem_; >> + half_ = len_ >> 1; >> + middle_ = first_; >> + middle_ += half_; >> + middle_elem_ = VEC_index_1 (vec_, middle_ VEC_CHECK_PASS); >> + if (lessthan_ (middle_elem_, obj_)) >> + { >> + first_ = middle_; >> + ++first_; >> + len_ = len_ - half_ - 1; >> + } >> + else >> + len_ = half_; >> + } >> + return first_; >> } >> >> - >> -#define DEF_VEC_NONALLOC_FUNCS_P(T,A) \ >> -static inline void VEC_OP (T,A,free) \ >> - (VEC(T,A) **vec_) \ >> -{ \ >> - if (*vec_) \ >> - vec_##A##_free (*vec_); \ >> - *vec_ = NULL; \ >> -} \ >> - \ >> -static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \ >> -{ \ >> - size_t len_ = vec_ ? vec_->prefix.num : 0; \ >> - VEC (T,A) *new_vec_ = NULL; \ >> - \ >> - if (len_) \ >> - { \ >> - new_vec_ = (VEC (T,A) *)(vec_##A##_p_reserve_exact \ >> - (NULL, len_ PASS_MEM_STAT)); \ >> - \ >> - new_vec_->base.prefix.num = len_; \ >> - memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_); \ >> - } \ >> - return new_vec_; \ >> -} \ >> - \ >> -static inline int VEC_OP (T,A,reserve) \ >> - (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \ >> -{ \ >> - int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \ >> - VEC_CHECK_PASS); \ >> - \ >> - if (extend) \ >> - *vec_ = (VEC(T,A) *) vec_##A##_p_reserve (*vec_, alloc_ PASS_MEM_STAT); \ >> - \ >> - return extend; \ >> -} \ >> - \ >> -static inline int VEC_OP (T,A,reserve_exact) \ >> - (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \ >> -{ \ >> - int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \ >> - VEC_CHECK_PASS); \ >> - \ >> - if (extend) \ >> - *vec_ = (VEC(T,A) *) vec_##A##_p_reserve_exact (*vec_, alloc_ \ >> - PASS_MEM_STAT); \ >> - \ >> - return extend; \ >> -} \ >> - \ >> -static inline void VEC_OP (T,A,safe_grow) \ >> - (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \ >> -{ \ >> - VEC_ASSERT (size_ >= 0 \ >> - && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \ >> - "grow", T, A); \ >> - VEC_OP (T,A,reserve_exact) (vec_, \ >> - size_ - (int)(*vec_ ? VEC_BASE(*vec_)->prefix.num : 0) \ >> - VEC_CHECK_PASS PASS_MEM_STAT); \ >> - VEC_BASE (*vec_)->prefix.num = size_; \ >> -} \ >> - \ >> -static inline void VEC_OP (T,A,safe_grow_cleared) \ >> - (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \ >> -{ \ >> - int oldsize = VEC_OP(T,base,length) VEC_BASE(*vec_); \ >> - VEC_OP (T,A,safe_grow) (vec_, size_ VEC_CHECK_PASS PASS_MEM_STAT); \ >> - memset (&(VEC_OP (T,base,address) VEC_BASE(*vec_))[oldsize], 0, \ >> - sizeof (T) * (size_ - oldsize)); \ >> -} \ >> - \ >> -static inline void VEC_OP(T,A,safe_splice) \ >> - (VEC(T,A) **dst_, VEC(T,base) *src_ VEC_CHECK_DECL MEM_STAT_DECL) \ >> -{ \ >> - if (src_) \ >> - { \ >> - VEC_OP (T,A,reserve_exact) (dst_, src_->prefix.num \ >> - VEC_CHECK_PASS MEM_STAT_INFO); \ >> - \ >> - VEC_OP (T,base,splice) (VEC_BASE (*dst_), src_ \ >> - VEC_CHECK_PASS); \ >> - } \ >> -} \ >> - \ >> -static inline T *VEC_OP (T,A,safe_push) \ >> - (VEC(T,A) **vec_, T obj_ VEC_CHECK_DECL MEM_STAT_DECL) \ >> -{ \ >> - VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \ >> - \ >> - return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS); \ >> -} \ >> - \ >> -static inline T *VEC_OP (T,A,safe_insert) \ >> - (VEC(T,A) **vec_, unsigned ix_, T obj_ VEC_CHECK_DECL MEM_STAT_DECL) \ >> -{ \ >> - VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \ >> - \ >> - return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_ \ >> - VEC_CHECK_PASS); \ >> -} >> - >> -/* Vector of object. */ >> -#define DEF_VEC_O(T) \ >> -VEC_T_GTY(T,base); \ >> -VEC_TA(T,base,none); \ >> -DEF_VEC_FUNC_O(T) \ >> -struct vec_swallow_trailing_semi >> -#define DEF_VEC_ALLOC_O(T,A) \ >> -VEC_TA(T,base,A); \ >> -DEF_VEC_ALLOC_FUNC_O(T,A) \ >> -DEF_VEC_NONALLOC_FUNCS_O(T,A) \ >> -struct vec_swallow_trailing_semi >> - >> -#define DEF_VEC_FUNC_O(T) \ >> -static inline unsigned VEC_OP (T,base,length) (const VEC(T,base) *vec_) \ >> -{ \ >> - return vec_ ? vec_->prefix.num : 0; \ >> -} \ >> - \ >> -static inline T *VEC_OP (T,base,last) (VEC(T,base) *vec_ VEC_CHECK_DECL) \ >> -{ \ >> - VEC_ASSERT (vec_ && vec_->prefix.num, "last", T, base); \ >> - \ >> - return &vec_->vec[vec_->prefix.num - 1]; \ >> -} \ >> - \ >> -static inline T *VEC_OP (T,base,index) \ >> - (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \ >> -{ \ >> - VEC_ASSERT (vec_ && ix_ < vec_->prefix.num, "index", T, base); \ >> - \ >> - return &vec_->vec[ix_]; \ >> -} \ >> - \ >> -static inline int VEC_OP (T,base,iterate) \ >> - (VEC(T,base) *vec_, unsigned ix_, T **ptr) \ >> -{ \ >> - if (vec_ && ix_ < vec_->prefix.num) \ >> - { \ >> - *ptr = &vec_->vec[ix_]; \ >> - return 1; \ >> - } \ >> - else \ >> - { \ >> - *ptr = 0; \ >> - return 0; \ >> - } \ >> -} \ >> - \ >> -static inline size_t VEC_OP (T,base,embedded_size) \ >> - (int alloc_) \ >> -{ \ >> - return offsetof (VEC(T,base),vec) + alloc_ * sizeof(T); \ >> -} \ >> - \ >> -static inline void VEC_OP (T,base,embedded_init) \ >> - (VEC(T,base) *vec_, int alloc_) \ >> -{ \ >> - vec_->prefix.num = 0; \ >> - vec_->prefix.alloc = alloc_; \ >> -} \ >> - \ >> -static inline int VEC_OP (T,base,space) \ >> - (VEC(T,base) *vec_, int alloc_ VEC_CHECK_DECL) \ >> -{ \ >> - VEC_ASSERT (alloc_ >= 0, "space", T, base); \ >> - return vec_ ? vec_->prefix.alloc - vec_->prefix.num >= (unsigned)alloc_ : !alloc_; \ >> -} \ >> - \ >> -static inline void VEC_OP(T,base,splice) \ >> - (VEC(T,base) *dst_, VEC(T,base) *src_ VEC_CHECK_DECL) \ >> -{ \ >> - if (src_) \ >> - { \ >> - unsigned len_ = src_->prefix.num; \ >> - VEC_ASSERT (dst_->prefix.num + len_ <= dst_->prefix.alloc, "splice", T, base); \ >> - \ >> - memcpy (&dst_->vec[dst_->prefix.num], &src_->vec[0], len_ * sizeof (T)); \ >> - dst_->prefix.num += len_; \ >> - } \ >> -} \ >> - \ >> -static inline T *VEC_OP (T,base,quick_push) \ >> - (VEC(T,base) *vec_, const T *obj_ VEC_CHECK_DECL) \ >> -{ \ >> - T *slot_; \ >> - \ >> - VEC_ASSERT (vec_->prefix.num < vec_->prefix.alloc, "push", T, base); \ >> - slot_ = &vec_->vec[vec_->prefix.num++]; \ >> - if (obj_) \ >> - *slot_ = *obj_; \ >> - \ >> - return slot_; \ >> -} \ >> - \ >> -static inline void VEC_OP (T,base,pop) (VEC(T,base) *vec_ VEC_CHECK_DECL) \ >> -{ \ >> - VEC_ASSERT (vec_->prefix.num, "pop", T, base); \ >> - --vec_->prefix.num; \ >> -} \ >> - \ >> -static inline void VEC_OP (T,base,truncate) \ >> - (VEC(T,base) *vec_, unsigned size_ VEC_CHECK_DECL) \ >> -{ \ >> - VEC_ASSERT (vec_ ? vec_->prefix.num >= size_ : !size_, "truncate", T, base); \ >> - if (vec_) \ >> - vec_->prefix.num = size_; \ >> -} \ >> - \ >> -static inline T *VEC_OP (T,base,replace) \ >> - (VEC(T,base) *vec_, unsigned ix_, const T *obj_ VEC_CHECK_DECL) \ >> -{ \ >> - T *slot_; \ >> - \ >> - VEC_ASSERT (ix_ < vec_->prefix.num, "replace", T, base); \ >> - slot_ = &vec_->vec[ix_]; \ >> - if (obj_) \ >> - *slot_ = *obj_; \ >> - \ >> - return slot_; \ >> -} \ >> - \ >> -static inline T *VEC_OP (T,base,quick_insert) \ >> - (VEC(T,base) *vec_, unsigned ix_, const T *obj_ VEC_CHECK_DECL) \ >> -{ \ >> - T *slot_; \ >> - \ >> - VEC_ASSERT (vec_->prefix.num < vec_->prefix.alloc, "insert", T, base); \ >> - VEC_ASSERT (ix_ <= vec_->prefix.num, "insert", T, base); \ >> - slot_ = &vec_->vec[ix_]; \ >> - memmove (slot_ + 1, slot_, (vec_->prefix.num++ - ix_) * sizeof (T)); \ >> - if (obj_) \ >> - *slot_ = *obj_; \ >> - \ >> - return slot_; \ >> -} \ >> - \ >> -static inline void VEC_OP (T,base,ordered_remove) \ >> - (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \ >> -{ \ >> - T *slot_; \ >> - \ >> - VEC_ASSERT (ix_ < vec_->prefix.num, "remove", T, base); \ >> - slot_ = &vec_->vec[ix_]; \ >> - memmove (slot_, slot_ + 1, (--vec_->prefix.num - ix_) * sizeof (T)); \ >> -} \ >> - \ >> -static inline void VEC_OP (T,base,unordered_remove) \ >> - (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \ >> -{ \ >> - VEC_ASSERT (ix_ < vec_->prefix.num, "remove", T, base); \ >> - vec_->vec[ix_] = vec_->vec[--vec_->prefix.num]; \ >> -} \ >> - \ >> -static inline void VEC_OP (T,base,block_remove) \ >> - (VEC(T,base) *vec_, unsigned ix_, unsigned len_ VEC_CHECK_DECL) \ >> -{ \ >> - T *slot_; \ >> - \ >> - VEC_ASSERT (ix_ + len_ <= vec_->prefix.num, "block_remove", T, base); \ >> - slot_ = &vec_->vec[ix_]; \ >> - vec_->prefix.num -= len_; \ >> - memmove (slot_, slot_ + len_, (vec_->prefix.num - ix_) * sizeof (T)); \ >> -} \ >> - \ >> -static inline T *VEC_OP (T,base,address) \ >> - (VEC(T,base) *vec_) \ >> -{ \ >> - return vec_ ? vec_->vec : 0; \ >> -} \ >> - \ >> -static inline unsigned VEC_OP (T,base,lower_bound) \ >> - (VEC(T,base) *vec_, const T *obj_, \ >> - bool (*lessthan_)(const T *, const T *) VEC_CHECK_DECL) \ >> -{ \ >> - unsigned int len_ = VEC_OP (T, base, length) (vec_); \ >> - unsigned int half_, middle_; \ >> - unsigned int first_ = 0; \ >> - while (len_ > 0) \ >> - { \ >> - T *middle_elem_; \ >> - half_ = len_ >> 1; \ >> - middle_ = first_; \ >> - middle_ += half_; \ >> - middle_elem_ = VEC_OP (T,base,index) (vec_, middle_ VEC_CHECK_PASS); \ >> - if (lessthan_ (middle_elem_, obj_)) \ >> - { \ >> - first_ = middle_; \ >> - ++first_; \ >> - len_ = len_ - half_ - 1; \ >> - } \ >> - else \ >> - len_ = half_; \ >> - } \ >> - return first_; \ >> +template<typename T> >> +static inline unsigned >> +VEC_lower_bound_1 (vec_t<T> *vec_, const T *ptr_, >> + bool (*lessthan_)(const T*, const T*) VEC_CHECK_DECL) >> +{ >> + unsigned int len_ = VEC_length (T, vec_); >> + unsigned int half_, middle_; >> + unsigned int first_ = 0; >> + while (len_ > 0) >> + { >> + T *middle_elem_; >> + half_ = len_ >> 1; >> + middle_ = first_; >> + middle_ += half_; >> + middle_elem_ = &VEC_index_1 (vec_, middle_ VEC_CHECK_PASS); >> + if (lessthan_ (middle_elem_, ptr_)) >> + { >> + first_ = middle_; >> + ++first_; >> + len_ = len_ - half_ - 1; >> + } >> + else >> + len_ = half_; >> + } >> + return first_; >> } >> >> -#define DEF_VEC_ALLOC_FUNC_O(T,A) \ >> -static inline VEC(T,A) *VEC_OP (T,A,alloc) \ >> - (int alloc_ MEM_STAT_DECL) \ >> -{ \ >> - return (VEC(T,A) *) vec_##A##_o_reserve_exact (NULL, alloc_, \ >> - offsetof (VEC(T,A),base.vec), \ >> - sizeof (T) \ >> - PASS_MEM_STAT); \ >> -} >> >> -#define DEF_VEC_NONALLOC_FUNCS_O(T,A) \ >> -static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \ >> -{ \ >> - size_t len_ = vec_ ? vec_->prefix.num : 0; \ >> - VEC (T,A) *new_vec_ = NULL; \ >> - \ >> - if (len_) \ >> - { \ >> - new_vec_ = (VEC (T,A) *)(vec_##A##_o_reserve_exact \ >> - (NULL, len_, \ >> - offsetof (VEC(T,A),base.vec), sizeof (T) \ >> - PASS_MEM_STAT)); \ >> - \ >> - new_vec_->base.prefix.num = len_; \ >> - memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_); \ >> - } \ >> - return new_vec_; \ >> -} \ >> - \ >> -static inline void VEC_OP (T,A,free) \ >> - (VEC(T,A) **vec_) \ >> -{ \ >> - if (*vec_) \ >> - vec_##A##_free (*vec_); \ >> - *vec_ = NULL; \ >> -} \ >> - \ >> -static inline int VEC_OP (T,A,reserve) \ >> - (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \ >> -{ \ >> - int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \ >> - VEC_CHECK_PASS); \ >> - \ >> - if (extend) \ >> - *vec_ = (VEC(T,A) *) vec_##A##_o_reserve (*vec_, alloc_, \ >> - offsetof (VEC(T,A),base.vec),\ >> - sizeof (T) \ >> - PASS_MEM_STAT); \ >> - \ >> - return extend; \ >> -} \ >> - \ >> -static inline int VEC_OP (T,A,reserve_exact) \ >> - (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \ >> -{ \ >> - int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \ >> - VEC_CHECK_PASS); \ >> - \ >> - if (extend) \ >> - *vec_ = (VEC(T,A) *) vec_##A##_o_reserve_exact \ >> - (*vec_, alloc_, \ >> - offsetof (VEC(T,A),base.vec), \ >> - sizeof (T) PASS_MEM_STAT); \ >> - \ >> - return extend; \ >> -} \ >> - \ >> -static inline void VEC_OP (T,A,safe_grow) \ >> - (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \ >> -{ \ >> - VEC_ASSERT (size_ >= 0 \ >> - && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \ >> - "grow", T, A); \ >> - VEC_OP (T,A,reserve_exact) (vec_, \ >> - size_ - (int)(*vec_ ? VEC_BASE(*vec_)->prefix.num : 0) \ >> - VEC_CHECK_PASS PASS_MEM_STAT); \ >> - VEC_BASE (*vec_)->prefix.num = size_; \ >> -} \ >> - \ >> -static inline void VEC_OP (T,A,safe_grow_cleared) \ >> - (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \ >> -{ \ >> - int oldsize = VEC_OP(T,base,length) VEC_BASE(*vec_); \ >> - VEC_OP (T,A,safe_grow) (vec_, size_ VEC_CHECK_PASS PASS_MEM_STAT); \ >> - memset (&(VEC_OP (T,base,address) VEC_BASE(*vec_))[oldsize], 0, \ >> - sizeof (T) * (size_ - oldsize)); \ >> -} \ >> - \ >> -static inline void VEC_OP(T,A,safe_splice) \ >> - (VEC(T,A) **dst_, VEC(T,base) *src_ VEC_CHECK_DECL MEM_STAT_DECL) \ >> -{ \ >> - if (src_) \ >> - { \ >> - VEC_OP (T,A,reserve_exact) (dst_, src_->prefix.num \ >> - VEC_CHECK_PASS MEM_STAT_INFO); \ >> - \ >> - VEC_OP (T,base,splice) (VEC_BASE (*dst_), src_ \ >> - VEC_CHECK_PASS); \ >> - } \ >> -} \ >> - \ >> -static inline T *VEC_OP (T,A,safe_push) \ >> - (VEC(T,A) **vec_, const T *obj_ VEC_CHECK_DECL MEM_STAT_DECL) \ >> -{ \ >> - VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \ >> - \ >> - return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS); \ >> -} \ >> - \ >> -static inline T *VEC_OP (T,A,safe_insert) \ >> - (VEC(T,A) **vec_, unsigned ix_, const T *obj_ \ >> - VEC_CHECK_DECL MEM_STAT_DECL) \ >> -{ \ >> - VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \ >> - \ >> - return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_ \ >> - VEC_CHECK_PASS); \ >> -} >> +void *vec_heap_o_reserve_1 (void *, int, size_t, size_t, bool MEM_STAT_DECL); >> +void *vec_gc_o_reserve_1 (void *, int, size_t, size_t, bool MEM_STAT_DECL); >> >> -#define DEF_VEC_ALLOC_FUNC_I(T,A) \ >> -static inline VEC(T,A) *VEC_OP (T,A,alloc) \ >> - (int alloc_ MEM_STAT_DECL) \ >> -{ \ >> - return (VEC(T,A) *) vec_##A##_o_reserve_exact \ >> - (NULL, alloc_, offsetof (VEC(T,A),base.vec), \ >> - sizeof (T) PASS_MEM_STAT); \ >> -} >> +/* Ensure there are at least RESERVE free slots in VEC_, growing >> + exponentially. If RESERVE < 0 grow exactly, else grow >> + exponentially. As a special case, if VEC_ is NULL, and RESERVE is >> + 0, no vector will be created. */ >> >> -#define DEF_VEC_NONALLOC_FUNCS_I(T,A) \ >> -static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \ >> -{ \ >> - size_t len_ = vec_ ? vec_->prefix.num : 0; \ >> - VEC (T,A) *new_vec_ = NULL; \ >> - \ >> - if (len_) \ >> - { \ >> - new_vec_ = (VEC (T,A) *)(vec_##A##_o_reserve_exact \ >> - (NULL, len_, \ >> - offsetof (VEC(T,A),base.vec), sizeof (T) \ >> - PASS_MEM_STAT)); \ >> - \ >> - new_vec_->base.prefix.num = len_; \ >> - memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_); \ >> - } \ >> - return new_vec_; \ >> -} \ >> - \ >> -static inline void VEC_OP (T,A,free) \ >> - (VEC(T,A) **vec_) \ >> -{ \ >> - if (*vec_) \ >> - vec_##A##_free (*vec_); \ >> - *vec_ = NULL; \ >> -} \ >> - \ >> -static inline int VEC_OP (T,A,reserve) \ >> - (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \ >> -{ \ >> - int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \ >> - VEC_CHECK_PASS); \ >> - \ >> - if (extend) \ >> - *vec_ = (VEC(T,A) *) vec_##A##_o_reserve (*vec_, alloc_, \ >> - offsetof (VEC(T,A),base.vec),\ >> - sizeof (T) \ >> - PASS_MEM_STAT); \ >> - \ >> - return extend; \ >> -} \ >> - \ >> -static inline int VEC_OP (T,A,reserve_exact) \ >> - (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \ >> -{ \ >> - int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \ >> - VEC_CHECK_PASS); \ >> - \ >> - if (extend) \ >> - *vec_ = (VEC(T,A) *) vec_##A##_o_reserve_exact \ >> - (*vec_, alloc_, offsetof (VEC(T,A),base.vec), \ >> - sizeof (T) PASS_MEM_STAT); \ >> - \ >> - return extend; \ >> -} \ >> - \ >> -static inline void VEC_OP (T,A,safe_grow) \ >> - (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \ >> -{ \ >> - VEC_ASSERT (size_ >= 0 \ >> - && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \ >> - "grow", T, A); \ >> - VEC_OP (T,A,reserve_exact) (vec_, \ >> - size_ - (int)(*vec_ ? VEC_BASE(*vec_)->prefix.num : 0) \ >> - VEC_CHECK_PASS PASS_MEM_STAT); \ >> - VEC_BASE (*vec_)->prefix.num = size_; \ >> -} \ >> - \ >> -static inline void VEC_OP (T,A,safe_grow_cleared) \ >> - (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \ >> -{ \ >> - int oldsize = VEC_OP(T,base,length) VEC_BASE(*vec_); \ >> - VEC_OP (T,A,safe_grow) (vec_, size_ VEC_CHECK_PASS PASS_MEM_STAT); \ >> - memset (&(VEC_OP (T,base,address) VEC_BASE(*vec_))[oldsize], 0, \ >> - sizeof (T) * (size_ - oldsize)); \ >> -} \ >> - \ >> -static inline void VEC_OP(T,A,safe_splice) \ >> - (VEC(T,A) **dst_, VEC(T,base) *src_ VEC_CHECK_DECL MEM_STAT_DECL) \ >> -{ \ >> - if (src_) \ >> - { \ >> - VEC_OP (T,A,reserve_exact) (dst_, src_->prefix.num \ >> - VEC_CHECK_PASS MEM_STAT_INFO); \ >> - \ >> - VEC_OP (T,base,splice) (VEC_BASE (*dst_), src_ \ >> - VEC_CHECK_PASS); \ >> - } \ >> -} \ >> - \ >> -static inline T *VEC_OP (T,A,safe_push) \ >> - (VEC(T,A) **vec_, const T obj_ VEC_CHECK_DECL MEM_STAT_DECL) \ >> -{ \ >> - VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \ >> - \ >> - return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS); \ >> -} \ >> - \ >> -static inline T *VEC_OP (T,A,safe_insert) \ >> - (VEC(T,A) **vec_, unsigned ix_, const T obj_ \ >> - VEC_CHECK_DECL MEM_STAT_DECL) \ >> -{ \ >> - VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \ >> - \ >> - return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_ \ >> - VEC_CHECK_PASS); \ >> +template<typename T, enum vec_allocation_t A> >> +vec_t<T> * >> +vec_reserve (vec_t<T> *vec_, int reserve MEM_STAT_DECL) >> +{ >> + if (A == gc) >> + return (vec_t<T> *) vec_gc_o_reserve_1 (vec_, reserve, >> + offsetof (vec_t<T>, vec), >> + sizeof (T), false >> + PASS_MEM_STAT); >> + else if (A == heap) >> + return (vec_t<T> *) vec_heap_o_reserve_1 (vec_, reserve, >> + offsetof (vec_t<T>, vec), >> + sizeof (T), false >> + PASS_MEM_STAT); >> + else >> + { >> + /* Only allow stack vectors when re-growing them. The initial >> + allocation of stack vectors must be done with the >> + VEC_stack_alloc macro, because it uses alloca() for the >> + allocation. */ >> + if (vec_ == NULL) >> + { >> + fprintf (stderr, "Stack vectors must be initially allocated " >> + "with VEC_stack_alloc.\n"); >> + gcc_unreachable (); >> + } >> + return (vec_t<T> *) vec_stack_o_reserve (vec_, reserve, >> + offsetof (vec_t<T>, vec), >> + sizeof (T) PASS_MEM_STAT); >> + } >> } >> >> -/* 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. Instead of DEF_VEC_ALLOC_P(TYPE, heap|gc), use >> - DEF_VEC_ALLOC_P_STACK(TYPE). This uses alloca to get the initial >> - space; because alloca can not be usefully called in an inline >> - function, and because a macro can not define a macro, you must then >> - write a #define for each type: >> - >> - #define VEC_{TYPE}_stack_alloc(alloc) \ >> - VEC_stack_alloc({TYPE}, alloc) >> >> - This is really a hack and perhaps can be made better. Note that >> - this macro will wind up evaluating the ALLOC parameter twice. >> +/* Ensure there are at least RESERVE free slots in VEC_, growing >> + exactly. If RESERVE < 0 grow exactly, else grow exponentially. As >> + a special case, if VEC_ is NULL, and RESERVE is 0, no vector will be >> + created. */ >> >> - 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 VEC(TYPE,stack) vector from the function >> - which allocated it. */ >> - >> -extern void *vec_stack_p_reserve (void *, int MEM_STAT_DECL); >> -extern void *vec_stack_p_reserve_exact (void *, int MEM_STAT_DECL); >> -extern void *vec_stack_p_reserve_exact_1 (int, void *); >> -extern void *vec_stack_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL); >> -extern void *vec_stack_o_reserve_exact (void *, int, size_t, size_t >> - MEM_STAT_DECL); >> -extern void vec_stack_free (void *); >> - >> -#ifdef GATHER_STATISTICS >> -#define VEC_stack_alloc(T,alloc,name,line,function) \ >> - (VEC_OP (T,stack,alloc1) \ >> - (alloc, XALLOCAVAR (VEC(T,stack), VEC_embedded_size (T, alloc)))) >> -#else >> -#define VEC_stack_alloc(T,alloc) \ >> - (VEC_OP (T,stack,alloc1) \ >> - (alloc, XALLOCAVAR (VEC(T,stack), VEC_embedded_size (T, alloc)))) >> -#endif >> - >> -#define DEF_VEC_ALLOC_P_STACK(T) \ >> -VEC_TA(T,base,stack); \ >> -DEF_VEC_ALLOC_FUNC_P_STACK(T) \ >> -DEF_VEC_NONALLOC_FUNCS_P(T,stack) \ >> -struct vec_swallow_trailing_semi >> - >> -#define DEF_VEC_ALLOC_FUNC_P_STACK(T) \ >> -static inline VEC(T,stack) *VEC_OP (T,stack,alloc1) \ >> - (int alloc_, VEC(T,stack)* space) \ >> -{ \ >> - return (VEC(T,stack) *) vec_stack_p_reserve_exact_1 (alloc_, space); \ >> -} >> - >> -#define DEF_VEC_ALLOC_O_STACK(T) \ >> -VEC_TA(T,base,stack); \ >> -DEF_VEC_ALLOC_FUNC_O_STACK(T) \ >> -DEF_VEC_NONALLOC_FUNCS_O(T,stack) \ >> -struct vec_swallow_trailing_semi >> - >> -#define DEF_VEC_ALLOC_FUNC_O_STACK(T) \ >> -static inline VEC(T,stack) *VEC_OP (T,stack,alloc1) \ >> - (int alloc_, VEC(T,stack)* space) \ >> -{ \ >> - return (VEC(T,stack) *) vec_stack_p_reserve_exact_1 (alloc_, space); \ >> -} >> - >> -#define DEF_VEC_ALLOC_I_STACK(T) \ >> -VEC_TA(T,base,stack); \ >> -DEF_VEC_ALLOC_FUNC_I_STACK(T) \ >> -DEF_VEC_NONALLOC_FUNCS_I(T,stack) \ >> -struct vec_swallow_trailing_semi >> - >> -#define DEF_VEC_ALLOC_FUNC_I_STACK(T) \ >> -static inline VEC(T,stack) *VEC_OP (T,stack,alloc1) \ >> - (int alloc_, VEC(T,stack)* space) \ >> -{ \ >> - return (VEC(T,stack) *) vec_stack_p_reserve_exact_1 (alloc_, space); \ >> +template<typename T, enum vec_allocation_t A> >> +vec_t<T> * >> +vec_reserve_exact (vec_t<T> *vec_, int reserve MEM_STAT_DECL) >> +{ >> + if (A == gc) >> + return (vec_t<T> *) vec_gc_o_reserve_1 (vec_, reserve, >> + sizeof (struct vec_prefix), >> + sizeof (T), true >> + PASS_MEM_STAT); >> + else if (A == heap) >> + return (vec_t<T> *) vec_heap_o_reserve_1 (vec_, reserve, >> + sizeof (struct vec_prefix), >> + sizeof (T), true >> + PASS_MEM_STAT); >> + else if (A == stack) >> + { >> + /* Only allow stack vectors when re-growing them. The initial >> + allocation of stack vectors must be done with VEC_alloc, >> + because it uses alloca() for the allocation. */ >> + if (vec_ == NULL) >> + { >> + fprintf (stderr, "Stack vectors must be initially allocated " >> + "with VEC_stack_alloc.\n"); >> + gcc_unreachable (); >> + } >> + return (vec_t<T> *) vec_stack_o_reserve_exact (vec_, reserve, >> + sizeof (struct vec_prefix), >> + sizeof (T) >> + PASS_MEM_STAT); >> + } >> } >> >> #endif /* GCC_VEC_H */ >> >> -- >> This patch is available for review at http://codereview.appspot.com/6233044
Sign in to reply to this message.
On 12-05-24 04:20 , Andrew Pinski wrote: > On Thu, May 24, 2012 at 1:16 AM, Richard Guenther > <richard.guenther@gmail.com> wrote: >> >> I believe this was because of aliasing - you may dig in the svn history >> to find out what we miscompiled when not doing this and whether it is >> still necessary or not. > > Yes it was done for aliasing reasons (I did this change). In fact it > is still necessary and it was only reproduciable with LTO and -O3. No tests fail with all languages enabled (including Ada and Go), profiled+LTO bootstrap works. If you added a test for this, it is now working. If not, could you please add one? In any case, it is very likely that I will refactor this data structure again so I can make vectors one word structures, so that I can implement operator[]. Diego.
Sign in to reply to this message.
On 12-05-24 04:16 , Richard Guenther wrote: > On Wed, May 23, 2012 at 9:48 PM, Diego Novillo<dnovillo@google.com> wrote: >> >> This series of 3 patches re-implement vec.[ch] in C++. >> >> The main goal of this first step is to minimize changes to client >> code. I tried very hard to maintain the existing API. This means >> that vectors are still simple structures accessed via the existing >> VEC_* functions. >> >> The major change introduced here is the removal of all the macro-based >> type creation in vec.h: >> >> 1- Given a type T and an allocation strategy A, VEC(T,A) used to >> expand into the C type 'struct VEC_T_A'. The family of accessor >> functions for VEC_T_A were created via macro expansion and token >> pasting. >> >> After this patch, VEC(T,A) expands to 'vec_t<T>': >> >> template<typename T> >> struct GTY(()) vec_t >> { >> vec_prefix prefix; >> T GTY((length ("%h.prefix.num"))) vec[1]; >> }; >> >> The family of accessor functions for vec_t<T> are free functions >> templated on<T> or<T,A> depending on whether the function needs >> to perform allocation operations. >> >> 2- All the DEF_VEC_[IOP] and DEF_VEC_ALLOC_[IOP] macros expand to the >> nil expansion 'struct vec_swallow_trailing_semi'. This represents >> the bulk of the removal in vec.h. >> >> 3- I removed one indirection from the existing VEC structures. Before >> this patch, the visible structure created by VEC_T_A had a single >> element 'base', which, in turn, was the structure holding 'prefix' >> and 'vec'. The new vec_t<T> has 'prefix' and 'vec' in it. This >> may change in the second iteration of this patch. > > I believe this was because of aliasing - you may dig in the svn history > to find out what we miscompiled when not doing this and whether it is > still necessary or not. > >> Some client code changes were needed: >> >> 1- The allocation names 'heap', 'stack' and 'gc' are not embedded in >> the type name anymore. They are enum values used as a template >> argument for functions like VEC_alloc() and VEC_free(). Since they >> are now separate identifiers, some existing code that declared >> variables with the names 'heap' and 'stack' had to change. >> >> I did not change these enum values to better names because that >> would have meant changing a lot more client code. I will change >> this in a future patch. > > Yeah. Can we have > > template<...> > struct vec { > enum { gc, heap, stack }; > ... > } > > and use vec<T, vec::stack> instead? Not sure if this or something similar > is valid C++. Sure. Something involving a new namespace, like Gaby suggested down-thread. > >> 2- VEC_index and VEC_last now return a reference to the element. The >> existing APIs implemented two versions of these functions. One >> returning the element itself (used for vec_t<T *>). Another returning >> a pointer to the element (used for vec_t<T>). >> >> This is impossible to represent in C++ directly, as functions >> cannot be overloaded by their return value. Instead, I made them >> return a reference to the element. This means that vectors storing >> pointers (T *) do not need to change, but vectors of objects (T) do >> need to change. >> >> We have fewer vec_t<T> than vec_t<T *>, so this was the smaller change >> (which still meant changing a few hundred call sites). > > We still can have const overloads when taking a const vec though? I'm going to say 'sure' because I don't really think I understand this question :) >> 3- The family of VEC_*push and VEC_*replace functions have overloads >> for handling 'T' and 'const T *' objects. The former is used for >> vec_t<T>, the latter for vec_t<T*>. This means, however, than when >> pushing the special value 0 on a vec_t<T*>, the compiler will not >> know which overload we meant, as 0 matches both. In these cases >> (not very many), a static cast is all we need to help it. >> >> I'm not terribly content with this one. I'll try to have a better >> approach in the second iteration (which will liberally change all >> client code). > > I wonder whether explicitely specifying the template type is better? Thus, > VEC_safe_push<T *, gc>(0) instead of automatically deducing the template > argument? Not sure. I didn't like the casts, Lawrence had another suggestion involving something like C++11's nullptr. Lawrence, what was that nullptr thing you were telling me earlier? > >> 4- I extended gengtype to understand templated types. These changes >> are not as ugly as I thought they would be. Gengtype has some >> hardwired knowledge of VEC_*, which I renamed to vec_t. I'm not >> even sure why gengtype needs to care about vec_t in this way, but I >> was looking for minimal changes, so I just did it. >> >> The other change is more generic. It allows gengtype to deal with >> templated types. There is a new function (filter_type_name) that >> recognizes C++ special characters '<','>' and ':'. It turns them >> into '_'. This way, gengtype can generate a valid identifier for >> the pre-processor. It only does this in contexts where it needs a >> pre-processor identifier. For everything else, it emits the type >> directly. So, the functions emitted in gt-*.h files have proper >> template type references. > > Well, that part is of course what needs to change. I don't think we want > gengtype to work like this for templates as this does not scale. Well, certainly, but that was outside the scope of this one patch. I'm trying to make small incremental steps. >> 2- Change VEC_index into operator[]. >> >> 3- Change VEC_replace(...) to assignments using operator[]. > > I think these should not be done for now - they merely add syntactic > sugar, no? It makes the code more compact, readable and easier to write. I can certainly wait until the branch has been merged to make all these changes. It's going to affect a boatload of call sites. Diego.
Sign in to reply to this message.
I have committed these three patches as a single revision r187836 on cxx-conversion. I will address further comments to the patch in subsequent changes. Andrew, if you have some time, could you see if you can recreate that LTO aliasing failure you were describing earlier? I may change the data structure again, but it would still be interesting to have a test for it. Thanks. Diego.
Sign in to reply to this message.
On 5/24/12, Diego Novillo <dnovillo@google.com> wrote: > On 12-05-24 04:16 , Richard Guenther wrote: >> On May 23, 2012 Diego Novillo<dnovillo@google.com> wrote: >>> Some client code changes were needed: >>> >>> 1- The allocation names 'heap', 'stack' and 'gc' are not embedded in >>> the type name anymore. They are enum values used as a template >>> argument for functions like VEC_alloc() and VEC_free(). Since they >>> are now separate identifiers, some existing code that declared >>> variables with the names 'heap' and 'stack' had to change. >>> >>> I did not change these enum values to better names because that >>> would have meant changing a lot more client code. I will change >>> this in a future patch. >> >> Yeah. Can we have >> >> template<...> >> struct vec { >> enum { gc, heap, stack }; >> ... >> } >> >> and use vec<T, vec::stack> instead? Not sure if this or something >> similar >> is valid C++. > > Sure. Something involving a new namespace, like Gaby suggested > down-thread. I like namespaces, but "using namespace" does not work the way most people think it does. So, I was planning to defer that issue for a while. >>> 2- VEC_index and VEC_last now return a reference to the element. The >>> existing APIs implemented two versions of these functions. One >>> returning the element itself (used for vec_t<T *>). Another >>> returning a pointer to the element (used for vec_t<T>). >>> >>> This is impossible to represent in C++ directly, as functions >>> cannot be overloaded by their return value. Instead, I made them >>> return a reference to the element. This means that vectors storing >>> pointers (T *) do not need to change, but vectors of objects (T) do >>> need to change. >>> >>> We have fewer vec_t<T> than vec_t<T *>, so this was the smaller >>> change (which still meant changing a few hundred call sites). >> >> We still can have const overloads when taking a const vec though? > > I'm going to say 'sure' because I don't really think I understand this > question :) Yes, we can. >>> 3- The family of VEC_*push and VEC_*replace functions have overloads >>> for handling 'T' and 'const T *' objects. The former is used for >>> vec_t<T>, the latter for vec_t<T*>. This means, however, than when >>> pushing the special value 0 on a vec_t<T*>, the compiler will not >>> know which overload we meant, as 0 matches both. In these cases >>> (not very many), a static cast is all we need to help it. >>> >>> I'm not terribly content with this one. I'll try to have a better >>> approach in the second iteration (which will liberally change all >>> client code). >> >> I wonder whether explicitely specifying the template type is better? >> Thus, VEC_safe_push<T *, gc>(0) instead of automatically deducing the >> template argument? > > Not sure. I didn't like the casts, Lawrence had another suggestion > involving something like C++11's nullptr. Lawrence, what was that > nullptr thing you were telling me earlier? One would write VEC_save_push(v, nullptr), which unambiguously means the null pointer. C++11 has nullptr built in to the language, but we can approximate it with: struct nullptr_t { template <typname T> operator T*() { return 0; } } nullptr; The downside is that using plain 0 would still be ambiguous. Programmers that mean the integer would need to cast the 0. >>> 4- I extended gengtype to understand templated types. These changes >>> are not as ugly as I thought they would be. Gengtype has some >>> hardwired knowledge of VEC_*, which I renamed to vec_t. I'm not >>> even sure why gengtype needs to care about vec_t in this way, but I >>> was looking for minimal changes, so I just did it. >>> >>> The other change is more generic. It allows gengtype to deal with >>> templated types. There is a new function (filter_type_name) that >>> recognizes C++ special characters '<','>' and ':'. It turns them >>> into '_'. This way, gengtype can generate a valid identifier for >>> the pre-processor. It only does this in contexts where it needs a >>> pre-processor identifier. For everything else, it emits the type >>> directly. So, the functions emitted in gt-*.h files have proper >>> template type references. >> >> Well, that part is of course what needs to change. I don't think we want >> gengtype to work like this for templates as this does not scale. > > Well, certainly, but that was outside the scope of this one patch. I'm > trying to make small incremental steps. > >>> 2- Change VEC_index into operator[]. >>> >>> 3- Change VEC_replace(...) to assignments using operator[]. >> >> I think these should not be done for now - they merely add syntactic >> sugar, no? > > It makes the code more compact, readable and easier to write. > I can certainly wait until the branch has been merged to make > all these changes. It's going to affect a boatload of call sites. How about picking a one or two files to show the effect, but leave the bulk of the call site changes to later changes directly on trunk? -- Lawrence Crowl
Sign in to reply to this message.
>>>>> "Diego" == Diego Novillo <dnovillo@google.com> writes: Diego> +struct GTY(()) vec_prefix Diego> +{ Diego> + unsigned num; Diego> + unsigned alloc; Diego> +}; Diego> + Diego> +/* Vector type, user visible. */ Diego> +template<typename T> Diego> +struct GTY(()) vec_t Diego> +{ Diego> + vec_prefix prefix; Diego> + T GTY((length ("%h.prefix.num"))) vec[1]; Diego> +}; I'm curious why you didn't use inheritance here. template<typename T> struct GTY(()) vec_t : public vec_prefix { ... }; Tom
Sign in to reply to this message.
On 12-05-25 14:27 , Tom Tromey wrote: >>>>>> "Diego" == Diego Novillo<dnovillo@google.com> writes: > > Diego> +struct GTY(()) vec_prefix > Diego> +{ > Diego> + unsigned num; > Diego> + unsigned alloc; > Diego> +}; > Diego> + > Diego> +/* Vector type, user visible. */ > Diego> +template<typename T> > Diego> +struct GTY(()) vec_t > Diego> +{ > Diego> + vec_prefix prefix; > Diego> + T GTY((length ("%h.prefix.num"))) vec[1]; > Diego> +}; > > I'm curious why you didn't use inheritance here. > > template<typename T> > struct GTY(()) vec_t : public vec_prefix > { > ... > }; Minimalism. I was almost obsessed by it with the first patch. It would've required more changes if I didn't make it a POD type. I will make it into a more standard C++ type in subsequent patches. Diego.
Sign in to reply to this message.
|
