From patchwork Wed May 23 19:48:42 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Diego Novillo X-Patchwork-Id: 161028 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id A04CEB6FBC for ; Thu, 24 May 2012 05:49:31 +1000 (EST) Comment: DKIM? See http://www.dkim.org DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d=gcc.gnu.org; s=default; x=1338407372; h=Comment: DomainKey-Signature:Received:Received:Received:Received:Received: Received:Received:Received:Received:To:Subject:Message-Id:Date: From:Mailing-List:Precedence:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:Sender:Delivered-To; bh=7Jy4LO9 ghal9PXZrCkb4lZfYXE4=; b=FkUsmSFFtmO1aazJasM4tF5Yfc8wXzUk2iz0IsE VUOXkJ9RCVfThkyo+rH0JdCqmHBl0tKJr97n4vdpnEYN5xQuZERJDQ//2tg7NDu3 /hdpBtUkmmXtfekVbGTpUzhLeI60N47OEDbI4+p1DmUMSPFrewLtqcL29QdimjCr rpQI= Comment: DomainKeys? See http://antispam.yahoo.com/domainkeys DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=default; d=gcc.gnu.org; h=Received:Received:X-SWARE-Spam-Status:X-Spam-Check-By:Received:Received:X-Google-DKIM-Signature:Received:Received:Received:Received:Received:To:Subject:Message-Id:Date:From:X-Gm-Message-State:X-IsSubscribed:Mailing-List:Precedence:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help:Sender:Delivered-To; b=HN0jJPEeesJ0+2Z0iFhOjToOEVfaPt6SPr4O/QRd5WrdP9t7ZgAC4Yfey87GYj qCKfmYPr3+OcXJ6SpqdXuezzh4BHDRDBG3ezInef6KCZExDc3Z9edTUwVO7WmlI2 ya0QPfSHFUfTyhCJMLG8GXxMcFF1/yS+IPzNmk0cOybq4=; Received: (qmail 5223 invoked by alias); 23 May 2012 19:49:24 -0000 Received: (qmail 5169 invoked by uid 22791); 23 May 2012 19:49:11 -0000 X-SWARE-Spam-Status: No, hits=-3.2 required=5.0 tests=AWL, BAYES_40, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, KHOP_RCVD_TRUST, RCVD_IN_DNSWL_LOW, RCVD_IN_HOSTKARMA_YE, TW_CP, TW_CX, TW_TM, T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from mail-we0-f201.google.com (HELO mail-we0-f201.google.com) (74.125.82.201) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Wed, 23 May 2012 19:48:45 +0000 Received: by wefh52 with SMTP id h52so460250wef.2 for ; Wed, 23 May 2012 12:48:43 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20120113; h=to:subject:message-id:date:from:x-gm-message-state; bh=deU3DVLxSTnknmNwaZDKOMRRHMbxDVL/1+Q4FMh3N6s=; b=lH//lxczRObXT2VA4IV8SYbXgNCtQOUXUtdQU/J3VM3vK2xsGFrxR7I669OHPJFcR3 8DEmQjT7bK4NZsP4tZ++yirK/OzxztuwL4/z3GoBQ+IUFoWCpWLzhSrH46S7Ce1te7XD CkUN4qFWFishcWiOucD3PHON/MPP9c/wK8I2lHxQQ7C9BSp9xRhvn2mEjE02vrfXTOnE fKGqTOQWPvDiEtnmVSFYMZGI+sKZ/EYUfnPqHZM2LPU1gFSEnsW8q2nGL5+aJ0/NErC+ leXGLSdSWoLD/yiPr9jJ/VnRCYq/k7vXwLkj00iSQPHaUXQUevLBxbcs5SctyPCpukwx P1rA== Received: by 10.213.21.24 with SMTP id h24mr1255626ebb.1.1337802523904; Wed, 23 May 2012 12:48:43 -0700 (PDT) Received: by 10.213.21.24 with SMTP id h24mr1255622ebb.1.1337802523824; Wed, 23 May 2012 12:48:43 -0700 (PDT) Received: from hpza9.eem.corp.google.com ([74.125.121.33]) by gmr-mx.google.com with ESMTPS id b15si24921456een.0.2012.05.23.12.48.43 (version=TLSv1/SSLv3 cipher=AES128-SHA); Wed, 23 May 2012 12:48:43 -0700 (PDT) Received: from torture.tor.corp.google.com (torture.tor.corp.google.com [172.29.41.4]) by hpza9.eem.corp.google.com (Postfix) with ESMTP id 4626A5C014A; Wed, 23 May 2012 12:48:43 -0700 (PDT) Received: by torture.tor.corp.google.com (Postfix, from userid 54752) id 6D6291020B8; Wed, 23 May 2012 15:48:42 -0400 (EDT) To: reply@codereview.appspotmail.com, crowl@google.com, iant@google.com, gcc-patches@gcc.gnu.org Subject: [cxx-conversion] Convert vec.[ch] to C++ [1/3] (issue6233044) Message-Id: <20120523194842.6D6291020B8@torture.tor.corp.google.com> Date: Wed, 23 May 2012 15:48:42 -0400 (EDT) From: dnovillo@google.com (Diego Novillo) X-Gm-Message-State: ALoCoQlTVmFXj0eUl4j4lwImDsgi8eini6jvYDRcCsrUxCgGTdclkhabxcqi/j3TN9ri5fItU5EUhMFDy+a7cLKrssMIU633SmEqTXpD5VjbjqdAb5d9+I2qxI+8nZfBPz/wh0D72GQVhXXihDbOBe777txoli+leQ== X-IsSubscribed: yes Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org 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': template struct GTY(()) vec_t { vec_prefix prefix; T GTY((length ("%h.prefix.num"))) vec[1]; }; The family of accessor functions for vec_t are free functions templated on or 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 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). Another returning a pointer to the element (used for vec_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 than vec_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, the latter for vec_t. This means, however, than when pushing the special value 0 on a vec_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 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. 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 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. (vec_allocation_t): Define. (struct vec_prefix): Move earlier in the file. (vec_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. --- This patch is available for review at http://codereview.appspot.com/6233044 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 + Re-implemented in C++ by Diego Novillo 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 + Re-implemented in C++ by Diego Novillo 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 + +enum vec_allocation_t { heap, gc, stack }; + +struct GTY(()) vec_prefix +{ + unsigned num; + unsigned alloc; +}; + +/* Vector type, user visible. */ +template +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 +extern vec_t *vec_reserve (vec_t *, int MEM_STAT_DECL); + +template +extern vec_t *vec_reserve_exact (vec_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 (V)) + +template +static inline unsigned +VEC_length_1 (const vec_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 (V)) + +template +static inline bool +VEC_empty_1 (const vec_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 (V)) + +template +static inline T * +VEC_address_1 (vec_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 (V VEC_CHECK_INFO)) + +template +static inline T& +VEC_last_1 (vec_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 (V, I VEC_CHECK_INFO)) + +template +static inline T& +VEC_index_1 (vec_t *vec_, unsigned ix_ VEC_CHECK_DECL) +{ + VEC_ASSERT (vec_ && ix_ < vec_->prefix.num, "index", T, base); + return vec_->vec[ix_]; +} + +template +static inline const T& +VEC_index_1 (const vec_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 (V, I, &(P))) + +template +static inline bool +VEC_iterate_1 (const vec_t *vec_, unsigned ix_, T *ptr) +{ + if (vec_ && ix_ < vec_->prefix.num) + { + *ptr = vec_->vec[ix_]; + return true; + } + else + { + *ptr = 0; + return false; + } +} + +template +static inline bool +VEC_iterate_1 (vec_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 (N)) + +template +static inline size_t +VEC_embedded_size_1 (int alloc_) +{ + return offsetof (vec_t, vec) + alloc_ * sizeof (T); +} + +#define VEC_embedded_init(T,O,N) (VEC_embedded_init_1 (O, N)) + +template +static inline void +VEC_embedded_init_1 (vec_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, \ + VEC_embedded_size_1 (N))) \ + : VEC_alloc_1 (N MEM_STAT_INFO)) + +template +static inline vec_t * +VEC_alloc_1 (int alloc_ MEM_STAT_DECL) +{ + return vec_reserve_exact (NULL, alloc_ PASS_MEM_STAT); +} + +template +static inline vec_t * +VEC_alloc_1 (int alloc_, vec_t *space) +{ + return (vec_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 (&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 +static inline void +VEC_free_1 (vec_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 (V MEM_STAT_INFO)) + +template +static inline vec_t * +VEC_copy_1 (vec_t *vec_ MEM_STAT_DECL) +{ + size_t len_ = vec_ ? vec_->prefix.num : 0; + vec_t *new_vec_ = NULL; + + if (len_) + { + new_vec_ = vec_reserve_exact (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 (V, R VEC_CHECK_INFO)) + +template +static inline int +VEC_space_1 (vec_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 (&(V), (int)(R) VEC_CHECK_INFO MEM_STAT_INFO)) + +template +static inline int +VEC_reserve_1 (vec_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 (*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 (&(V), R VEC_CHECK_INFO MEM_STAT_INFO)) + +template +static inline int +VEC_reserve_exact_1 (vec_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 (*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 (DST, SRC VEC_CHECK_INFO)) + +template +static inline void +VEC_splice_1 (vec_t *dst_, vec_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 (&(DST), SRC VEC_CHECK_INFO MEM_STAT_INFO)) + +template +static inline void +VEC_safe_splice_1 (vec_t **dst_, vec_t *src_ VEC_CHECK_DECL MEM_STAT_DECL) +{ + if (src_) + { + VEC_reserve_exact_1 (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 (V, O VEC_CHECK_INFO)) + +template +static inline T & +VEC_quick_push_1 (vec_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 +static inline T * +VEC_quick_push_1 (vec_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 (&(V), O VEC_CHECK_INFO MEM_STAT_INFO)) + +template +static inline T & +VEC_safe_push_1 (vec_t **vec_, T obj_ VEC_CHECK_DECL MEM_STAT_DECL) +{ + VEC_reserve_1 (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); + return VEC_quick_push_1 (*vec_, obj_ VEC_CHECK_PASS); +} + +template +static inline T * +VEC_safe_push_1 (vec_t **vec_, const T *ptr_ VEC_CHECK_DECL MEM_STAT_DECL) +{ + VEC_reserve_1 (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 (V VEC_CHECK_INFO)) + +template +static inline T& +VEC_pop_1 (vec_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 (V, (unsigned)(I) VEC_CHECK_INFO)) + +template +static inline void +VEC_truncate_1 (vec_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 (&(V), (int)(I) VEC_CHECK_INFO MEM_STAT_INFO)) + +template +static inline void +VEC_safe_grow_1 (vec_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 (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 (&(V), (int)(I) \ + VEC_CHECK_INFO MEM_STAT_INFO)) + +template +static inline void +VEC_safe_grow_cleared_1 (vec_t **vec_, int size_ VEC_CHECK_DECL + MEM_STAT_DECL) +{ + int oldsize = VEC_length (T, *vec_); + VEC_safe_grow_1 (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 (V, (unsigned)(I), O VEC_CHECK_INFO)) + +template +static inline T& +VEC_replace_1 (vec_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 (V,I,O VEC_CHECK_INFO)) + +template +static inline void +VEC_quick_insert_1 (vec_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 +static inline void +VEC_quick_insert_1 (vec_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 (&(V),I,O VEC_CHECK_INFO MEM_STAT_INFO)) + +template +static inline void +VEC_safe_insert_1 (vec_t **vec_, unsigned ix_, T obj_ + VEC_CHECK_DECL MEM_STAT_DECL) +{ + VEC_reserve_1 (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); + VEC_quick_insert_1 (*vec_, ix_, obj_ VEC_CHECK_PASS); +} + +template +static inline void +VEC_safe_insert_1 (vec_t **vec_, unsigned ix_, T *ptr_ + VEC_CHECK_DECL MEM_STAT_DECL) +{ + VEC_reserve_1 (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 (V,I VEC_CHECK_INFO)) + +template +static inline void +VEC_ordered_remove_1 (vec_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 (V,I VEC_CHECK_INFO)) + +template +static inline void +VEC_unordered_remove_1 (vec_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 (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 +static inline void +VEC_block_remove_1 (vec_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 (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 +static inline unsigned +VEC_lower_bound_1 (vec_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 +static inline unsigned +VEC_lower_bound_1 (vec_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 +vec_t * +vec_reserve (vec_t *vec_, int reserve MEM_STAT_DECL) +{ + if (A == gc) + return (vec_t *) vec_gc_o_reserve_1 (vec_, reserve, + offsetof (vec_t, vec), + sizeof (T), false + PASS_MEM_STAT); + else if (A == heap) + return (vec_t *) vec_heap_o_reserve_1 (vec_, reserve, + offsetof (vec_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 *) vec_stack_o_reserve (vec_, reserve, + offsetof (vec_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 +vec_t * +vec_reserve_exact (vec_t *vec_, int reserve MEM_STAT_DECL) +{ + if (A == gc) + return (vec_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 *) 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 *) vec_stack_o_reserve_exact (vec_, reserve, + sizeof (struct vec_prefix), + sizeof (T) + PASS_MEM_STAT); + } } #endif /* GCC_VEC_H */