1169689Skan/* Vector API for GNU compiler. 2169689Skan Copyright (C) 2004, 2005 Free Software Foundation, Inc. 3169689Skan Contributed by Nathan Sidwell <nathan@codesourcery.com> 4169689Skan 5169689SkanThis file is part of GCC. 6169689Skan 7169689SkanGCC is free software; you can redistribute it and/or modify it under 8169689Skanthe terms of the GNU General Public License as published by the Free 9169689SkanSoftware Foundation; either version 2, or (at your option) any later 10169689Skanversion. 11169689Skan 12169689SkanGCC is distributed in the hope that it will be useful, but WITHOUT ANY 13169689SkanWARRANTY; without even the implied warranty of MERCHANTABILITY or 14169689SkanFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15169689Skanfor more details. 16169689Skan 17169689SkanYou should have received a copy of the GNU General Public License 18169689Skanalong with GCC; see the file COPYING. If not, write to the Free 19169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 20169689Skan02110-1301, USA. */ 21169689Skan 22169689Skan#ifndef GCC_VEC_H 23169689Skan#define GCC_VEC_H 24169689Skan 25169689Skan/* The macros here implement a set of templated vector types and 26169689Skan associated interfaces. These templates are implemented with 27169689Skan macros, as we're not in C++ land. The interface functions are 28169689Skan typesafe and use static inline functions, sometimes backed by 29169689Skan out-of-line generic functions. The vectors are designed to 30169689Skan interoperate with the GTY machinery. 31169689Skan 32169689Skan Because of the different behavior of structure objects, scalar 33169689Skan objects and of pointers, there are three flavors, one for each of 34169689Skan these variants. Both the structure object and pointer variants 35169689Skan pass pointers to objects around -- in the former case the pointers 36169689Skan are stored into the vector and in the latter case the pointers are 37169689Skan dereferenced and the objects copied into the vector. The scalar 38169689Skan object variant is suitable for int-like objects, and the vector 39169689Skan elements are returned by value. 40169689Skan 41169689Skan There are both 'index' and 'iterate' accessors. The iterator 42169689Skan returns a boolean iteration condition and updates the iteration 43169689Skan variable passed by reference. Because the iterator will be 44169689Skan inlined, the address-of can be optimized away. 45169689Skan 46169689Skan The vectors are implemented using the trailing array idiom, thus 47169689Skan they are not resizeable without changing the address of the vector 48169689Skan object itself. This means you cannot have variables or fields of 49169689Skan vector type -- always use a pointer to a vector. The one exception 50169689Skan is the final field of a structure, which could be a vector type. 51169689Skan You will have to use the embedded_size & embedded_init calls to 52169689Skan create such objects, and they will probably not be resizeable (so 53169689Skan don't use the 'safe' allocation variants). The trailing array 54169689Skan idiom is used (rather than a pointer to an array of data), because, 55169689Skan if we allow NULL to also represent an empty vector, empty vectors 56169689Skan occupy minimal space in the structure containing them. 57169689Skan 58169689Skan Each operation that increases the number of active elements is 59169689Skan available in 'quick' and 'safe' variants. The former presumes that 60169689Skan there is sufficient allocated space for the operation to succeed 61169689Skan (it dies if there is not). The latter will reallocate the 62169689Skan vector, if needed. Reallocation causes an exponential increase in 63169689Skan vector size. If you know you will be adding N elements, it would 64169689Skan be more efficient to use the reserve operation before adding the 65169689Skan elements with the 'quick' operation. This will ensure there are at 66169689Skan least as many elements as you ask for, it will exponentially 67169689Skan increase if there are too few spare slots. If you want reserve a 68169689Skan specific number of slots, but do not want the exponential increase 69169689Skan (for instance, you know this is the last allocation), use the 70169689Skan reserve_exact operation. You can also create a vector of a 71169689Skan specific size from the get go. 72169689Skan 73169689Skan You should prefer the push and pop operations, as they append and 74169689Skan remove from the end of the vector. If you need to remove several 75169689Skan items in one go, use the truncate operation. The insert and remove 76169689Skan operations allow you to change elements in the middle of the 77169689Skan vector. There are two remove operations, one which preserves the 78169689Skan element ordering 'ordered_remove', and one which does not 79169689Skan 'unordered_remove'. The latter function copies the end element 80169689Skan into the removed slot, rather than invoke a memmove operation. The 81169689Skan 'lower_bound' function will determine where to place an item in the 82169689Skan array using insert that will maintain sorted order. 83169689Skan 84169689Skan When a vector type is defined, first a non-memory managed version 85169689Skan is created. You can then define either or both garbage collected 86169689Skan and heap allocated versions. The allocation mechanism is specified 87169689Skan when the type is defined, and is therefore part of the type. If 88169689Skan you need both gc'd and heap allocated versions, you still must have 89169689Skan *exactly* one definition of the common non-memory managed base vector. 90169689Skan 91169689Skan If you need to directly manipulate a vector, then the 'address' 92169689Skan accessor will return the address of the start of the vector. Also 93169689Skan the 'space' predicate will tell you whether there is spare capacity 94169689Skan in the vector. You will not normally need to use these two functions. 95169689Skan 96169689Skan Vector types are defined using a DEF_VEC_{O,P,I}(TYPEDEF) macro, to 97169689Skan get the non-memory allocation version, and then a 98169689Skan DEF_VEC_ALLOC_{O,P,I}(TYPEDEF,ALLOC) macro to get memory managed 99169689Skan vectors. Variables of vector type are declared using a 100169689Skan VEC(TYPEDEF,ALLOC) macro. The ALLOC argument specifies the 101169689Skan allocation strategy, and can be either 'gc' or 'heap' for garbage 102169689Skan collected and heap allocated respectively. It can be 'none' to get 103169689Skan a vector that must be explicitly allocated (for instance as a 104169689Skan trailing array of another structure). The characters O, P and I 105169689Skan indicate whether TYPEDEF is a pointer (P), object (O) or integral 106169689Skan (I) type. Be careful to pick the correct one, as you'll get an 107169689Skan awkward and inefficient API if you use the wrong one. There is a 108169689Skan check, which results in a compile-time warning, for the P and I 109169689Skan versions, but there is no check for the O versions, as that is not 110169689Skan possible in plain C. Due to the way GTY works, you must annotate 111169689Skan any structures you wish to insert or reference from a vector with a 112169689Skan GTY(()) tag. You need to do this even if you never declare the GC 113169689Skan allocated variants. 114169689Skan 115169689Skan An example of their use would be, 116169689Skan 117169689Skan DEF_VEC_P(tree); // non-managed tree vector. 118169689Skan DEF_VEC_ALLOC_P(tree,gc); // gc'd vector of tree pointers. This must 119169689Skan // appear at file scope. 120169689Skan 121169689Skan struct my_struct { 122169689Skan VEC(tree,gc) *v; // A (pointer to) a vector of tree pointers. 123169689Skan }; 124169689Skan 125169689Skan struct my_struct *s; 126169689Skan 127169689Skan if (VEC_length(tree,s->v)) { we have some contents } 128169689Skan VEC_safe_push(tree,gc,s->v,decl); // append some decl onto the end 129169689Skan for (ix = 0; VEC_iterate(tree,s->v,ix,elt); ix++) 130169689Skan { do something with elt } 131169689Skan 132169689Skan*/ 133169689Skan 134169689Skan/* Macros to invoke API calls. A single macro works for both pointer 135169689Skan and object vectors, but the argument and return types might well be 136169689Skan different. In each macro, T is the typedef of the vector elements, 137169689Skan and A is the allocation strategy. The allocation strategy is only 138169689Skan present when it is required. Some of these macros pass the vector, 139169689Skan V, by reference (by taking its address), this is noted in the 140169689Skan descriptions. */ 141169689Skan 142169689Skan/* Length of vector 143169689Skan unsigned VEC_T_length(const VEC(T) *v); 144169689Skan 145169689Skan Return the number of active elements in V. V can be NULL, in which 146169689Skan case zero is returned. */ 147169689Skan 148169689Skan#define VEC_length(T,V) (VEC_OP(T,base,length)(VEC_BASE(V))) 149169689Skan 150169689Skan 151169689Skan/* Check if vector is empty 152169689Skan int VEC_T_empty(const VEC(T) *v); 153169689Skan 154169689Skan Return nonzero if V is an empty vector (or V is NULL), zero otherwise. */ 155169689Skan 156169689Skan#define VEC_empty(T,V) (VEC_length (T,V) == 0) 157169689Skan 158169689Skan 159169689Skan/* Get the final element of the vector. 160169689Skan T VEC_T_last(VEC(T) *v); // Integer 161169689Skan T VEC_T_last(VEC(T) *v); // Pointer 162169689Skan T *VEC_T_last(VEC(T) *v); // Object 163169689Skan 164169689Skan Return the final element. V must not be empty. */ 165169689Skan 166169689Skan#define VEC_last(T,V) (VEC_OP(T,base,last)(VEC_BASE(V) VEC_CHECK_INFO)) 167169689Skan 168169689Skan/* Index into vector 169169689Skan T VEC_T_index(VEC(T) *v, unsigned ix); // Integer 170169689Skan T VEC_T_index(VEC(T) *v, unsigned ix); // Pointer 171169689Skan T *VEC_T_index(VEC(T) *v, unsigned ix); // Object 172169689Skan 173169689Skan Return the IX'th element. If IX must be in the domain of V. */ 174169689Skan 175169689Skan#define VEC_index(T,V,I) (VEC_OP(T,base,index)(VEC_BASE(V),I VEC_CHECK_INFO)) 176169689Skan 177169689Skan/* Iterate over vector 178169689Skan int VEC_T_iterate(VEC(T) *v, unsigned ix, T &ptr); // Integer 179169689Skan int VEC_T_iterate(VEC(T) *v, unsigned ix, T &ptr); // Pointer 180169689Skan int VEC_T_iterate(VEC(T) *v, unsigned ix, T *&ptr); // Object 181169689Skan 182169689Skan Return iteration condition and update PTR to point to the IX'th 183169689Skan element. At the end of iteration, sets PTR to NULL. Use this to 184169689Skan iterate over the elements of a vector as follows, 185169689Skan 186169689Skan for (ix = 0; VEC_iterate(T,v,ix,ptr); ix++) 187169689Skan continue; */ 188169689Skan 189169689Skan#define VEC_iterate(T,V,I,P) (VEC_OP(T,base,iterate)(VEC_BASE(V),I,&(P))) 190169689Skan 191169689Skan/* Allocate new vector. 192169689Skan VEC(T,A) *VEC_T_A_alloc(int reserve); 193169689Skan 194169689Skan Allocate a new vector with space for RESERVE objects. If RESERVE 195169689Skan is zero, NO vector is created. */ 196169689Skan 197169689Skan#define VEC_alloc(T,A,N) (VEC_OP(T,A,alloc)(N MEM_STAT_INFO)) 198169689Skan 199169689Skan/* Free a vector. 200169689Skan void VEC_T_A_free(VEC(T,A) *&); 201169689Skan 202169689Skan Free a vector and set it to NULL. */ 203169689Skan 204169689Skan#define VEC_free(T,A,V) (VEC_OP(T,A,free)(&V)) 205169689Skan 206169689Skan/* Use these to determine the required size and initialization of a 207169689Skan vector embedded within another structure (as the final member). 208169689Skan 209169689Skan size_t VEC_T_embedded_size(int reserve); 210169689Skan void VEC_T_embedded_init(VEC(T) *v, int reserve); 211169689Skan 212169689Skan These allow the caller to perform the memory allocation. */ 213169689Skan 214169689Skan#define VEC_embedded_size(T,N) (VEC_OP(T,base,embedded_size)(N)) 215169689Skan#define VEC_embedded_init(T,O,N) (VEC_OP(T,base,embedded_init)(VEC_BASE(O),N)) 216169689Skan 217169689Skan/* Copy a vector. 218169689Skan VEC(T,A) *VEC_T_A_copy(VEC(T) *); 219169689Skan 220169689Skan Copy the live elements of a vector into a new vector. The new and 221169689Skan old vectors need not be allocated by the same mechanism. */ 222169689Skan 223169689Skan#define VEC_copy(T,A,V) (VEC_OP(T,A,copy)(VEC_BASE(V) MEM_STAT_INFO)) 224169689Skan 225169689Skan/* Determine if a vector has additional capacity. 226169689Skan 227169689Skan int VEC_T_space (VEC(T) *v,int reserve) 228169689Skan 229169689Skan If V has space for RESERVE additional entries, return nonzero. You 230169689Skan usually only need to use this if you are doing your own vector 231169689Skan reallocation, for instance on an embedded vector. This returns 232169689Skan nonzero in exactly the same circumstances that VEC_T_reserve 233169689Skan will. */ 234169689Skan 235169689Skan#define VEC_space(T,V,R) \ 236169689Skan (VEC_OP(T,base,space)(VEC_BASE(V),R VEC_CHECK_INFO)) 237169689Skan 238169689Skan/* Reserve space. 239169689Skan int VEC_T_A_reserve(VEC(T,A) *&v, int reserve); 240169689Skan 241169689Skan Ensure that V has at least RESERVE slots available. This will 242169689Skan create additional headroom. Note this can cause V to be 243169689Skan reallocated. Returns nonzero iff reallocation actually 244169689Skan occurred. */ 245169689Skan 246169689Skan#define VEC_reserve(T,A,V,R) \ 247169689Skan (VEC_OP(T,A,reserve)(&(V),R VEC_CHECK_INFO MEM_STAT_INFO)) 248169689Skan 249169689Skan/* Reserve space exactly. 250169689Skan int VEC_T_A_reserve_exact(VEC(T,A) *&v, int reserve); 251169689Skan 252169689Skan Ensure that V has at least RESERVE slots available. This will not 253169689Skan create additional headroom. Note this can cause V to be 254169689Skan reallocated. Returns nonzero iff reallocation actually 255169689Skan occurred. */ 256169689Skan 257169689Skan#define VEC_reserve_exact(T,A,V,R) \ 258169689Skan (VEC_OP(T,A,reserve_exact)(&(V),R VEC_CHECK_INFO MEM_STAT_INFO)) 259169689Skan 260169689Skan/* Push object with no reallocation 261169689Skan T *VEC_T_quick_push (VEC(T) *v, T obj); // Integer 262169689Skan T *VEC_T_quick_push (VEC(T) *v, T obj); // Pointer 263169689Skan T *VEC_T_quick_push (VEC(T) *v, T *obj); // Object 264169689Skan 265169689Skan Push a new element onto the end, returns a pointer to the slot 266169689Skan filled in. For object vectors, the new value can be NULL, in which 267169689Skan case NO initialization is performed. There must 268169689Skan be sufficient space in the vector. */ 269169689Skan 270169689Skan#define VEC_quick_push(T,V,O) \ 271169689Skan (VEC_OP(T,base,quick_push)(VEC_BASE(V),O VEC_CHECK_INFO)) 272169689Skan 273169689Skan/* Push object with reallocation 274169689Skan T *VEC_T_A_safe_push (VEC(T,A) *&v, T obj); // Integer 275169689Skan T *VEC_T_A_safe_push (VEC(T,A) *&v, T obj); // Pointer 276169689Skan T *VEC_T_A_safe_push (VEC(T,A) *&v, T *obj); // Object 277169689Skan 278169689Skan Push a new element onto the end, returns a pointer to the slot 279169689Skan filled in. For object vectors, the new value can be NULL, in which 280169689Skan case NO initialization is performed. Reallocates V, if needed. */ 281169689Skan 282169689Skan#define VEC_safe_push(T,A,V,O) \ 283169689Skan (VEC_OP(T,A,safe_push)(&(V),O VEC_CHECK_INFO MEM_STAT_INFO)) 284169689Skan 285169689Skan/* Pop element off end 286169689Skan T VEC_T_pop (VEC(T) *v); // Integer 287169689Skan T VEC_T_pop (VEC(T) *v); // Pointer 288169689Skan void VEC_T_pop (VEC(T) *v); // Object 289169689Skan 290169689Skan Pop the last element off the end. Returns the element popped, for 291169689Skan pointer vectors. */ 292169689Skan 293169689Skan#define VEC_pop(T,V) (VEC_OP(T,base,pop)(VEC_BASE(V) VEC_CHECK_INFO)) 294169689Skan 295169689Skan/* Truncate to specific length 296169689Skan void VEC_T_truncate (VEC(T) *v, unsigned len); 297169689Skan 298169689Skan Set the length as specified. The new length must be less than or 299169689Skan equal to the current length. This is an O(1) operation. */ 300169689Skan 301169689Skan#define VEC_truncate(T,V,I) \ 302169689Skan (VEC_OP(T,base,truncate)(VEC_BASE(V),I VEC_CHECK_INFO)) 303169689Skan 304169689Skan/* Grow to a specific length. 305169689Skan void VEC_T_A_safe_grow (VEC(T,A) *&v, int len); 306169689Skan 307169689Skan Grow the vector to a specific length. The LEN must be as 308169689Skan long or longer than the current length. The new elements are 309169689Skan uninitialized. */ 310169689Skan 311169689Skan#define VEC_safe_grow(T,A,V,I) \ 312169689Skan (VEC_OP(T,A,safe_grow)(&(V),I VEC_CHECK_INFO MEM_STAT_INFO)) 313169689Skan 314169689Skan/* Replace element 315169689Skan T VEC_T_replace (VEC(T) *v, unsigned ix, T val); // Integer 316169689Skan T VEC_T_replace (VEC(T) *v, unsigned ix, T val); // Pointer 317169689Skan T *VEC_T_replace (VEC(T) *v, unsigned ix, T *val); // Object 318169689Skan 319169689Skan Replace the IXth element of V with a new value, VAL. For pointer 320169689Skan vectors returns the original value. For object vectors returns a 321169689Skan pointer to the new value. For object vectors the new value can be 322169689Skan NULL, in which case no overwriting of the slot is actually 323169689Skan performed. */ 324169689Skan 325169689Skan#define VEC_replace(T,V,I,O) \ 326169689Skan (VEC_OP(T,base,replace)(VEC_BASE(V),I,O VEC_CHECK_INFO)) 327169689Skan 328169689Skan/* Insert object with no reallocation 329169689Skan T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Integer 330169689Skan T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Pointer 331169689Skan T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T *val); // Object 332169689Skan 333169689Skan Insert an element, VAL, at the IXth position of V. Return a pointer 334169689Skan to the slot created. For vectors of object, the new value can be 335169689Skan NULL, in which case no initialization of the inserted slot takes 336169689Skan place. There must be sufficient space. */ 337169689Skan 338169689Skan#define VEC_quick_insert(T,V,I,O) \ 339169689Skan (VEC_OP(T,base,quick_insert)(VEC_BASE(V),I,O VEC_CHECK_INFO)) 340169689Skan 341169689Skan/* Insert object with reallocation 342169689Skan T *VEC_T_A_safe_insert (VEC(T,A) *&v, unsigned ix, T val); // Integer 343169689Skan T *VEC_T_A_safe_insert (VEC(T,A) *&v, unsigned ix, T val); // Pointer 344169689Skan T *VEC_T_A_safe_insert (VEC(T,A) *&v, unsigned ix, T *val); // Object 345169689Skan 346169689Skan Insert an element, VAL, at the IXth position of V. Return a pointer 347169689Skan to the slot created. For vectors of object, the new value can be 348169689Skan NULL, in which case no initialization of the inserted slot takes 349169689Skan place. Reallocate V, if necessary. */ 350169689Skan 351169689Skan#define VEC_safe_insert(T,A,V,I,O) \ 352169689Skan (VEC_OP(T,A,safe_insert)(&(V),I,O VEC_CHECK_INFO MEM_STAT_INFO)) 353169689Skan 354169689Skan/* Remove element retaining order 355169689Skan T VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Integer 356169689Skan T VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Pointer 357169689Skan void VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Object 358169689Skan 359169689Skan Remove an element from the IXth position of V. Ordering of 360169689Skan remaining elements is preserved. For pointer vectors returns the 361169689Skan removed object. This is an O(N) operation due to a memmove. */ 362169689Skan 363169689Skan#define VEC_ordered_remove(T,V,I) \ 364169689Skan (VEC_OP(T,base,ordered_remove)(VEC_BASE(V),I VEC_CHECK_INFO)) 365169689Skan 366169689Skan/* Remove element destroying order 367169689Skan T VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Integer 368169689Skan T VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Pointer 369169689Skan void VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Object 370169689Skan 371169689Skan Remove an element from the IXth position of V. Ordering of 372169689Skan remaining elements is destroyed. For pointer vectors returns the 373169689Skan removed object. This is an O(1) operation. */ 374169689Skan 375169689Skan#define VEC_unordered_remove(T,V,I) \ 376169689Skan (VEC_OP(T,base,unordered_remove)(VEC_BASE(V),I VEC_CHECK_INFO)) 377169689Skan 378169689Skan/* Remove a block of elements 379169689Skan void VEC_T_block_remove (VEC(T) *v, unsigned ix, unsigned len); 380169689Skan 381169689Skan Remove LEN elements starting at the IXth. Ordering is retained. 382169689Skan This is an O(1) operation. */ 383169689Skan 384169689Skan#define VEC_block_remove(T,V,I,L) \ 385169689Skan (VEC_OP(T,base,block_remove)(VEC_BASE(V),I,L VEC_CHECK_INFO)) 386169689Skan 387169689Skan/* Get the address of the array of elements 388169689Skan T *VEC_T_address (VEC(T) v) 389169689Skan 390169689Skan If you need to directly manipulate the array (for instance, you 391169689Skan want to feed it to qsort), use this accessor. */ 392169689Skan 393169689Skan#define VEC_address(T,V) (VEC_OP(T,base,address)(VEC_BASE(V))) 394169689Skan 395169689Skan/* Find the first index in the vector not less than the object. 396169689Skan unsigned VEC_T_lower_bound (VEC(T) *v, const T val, 397169689Skan bool (*lessthan) (const T, const T)); // Integer 398169689Skan unsigned VEC_T_lower_bound (VEC(T) *v, const T val, 399169689Skan bool (*lessthan) (const T, const T)); // Pointer 400169689Skan unsigned VEC_T_lower_bound (VEC(T) *v, const T *val, 401169689Skan bool (*lessthan) (const T*, const T*)); // Object 402169689Skan 403169689Skan Find the first position in which VAL could be inserted without 404169689Skan changing the ordering of V. LESSTHAN is a function that returns 405169689Skan true if the first argument is strictly less than the second. */ 406169689Skan 407169689Skan#define VEC_lower_bound(T,V,O,LT) \ 408169689Skan (VEC_OP(T,base,lower_bound)(VEC_BASE(V),O,LT VEC_CHECK_INFO)) 409169689Skan 410169689Skan#if !IN_GENGTYPE 411169689Skan/* Reallocate an array of elements with prefix. */ 412169689Skanextern void *vec_gc_p_reserve (void *, int MEM_STAT_DECL); 413169689Skanextern void *vec_gc_p_reserve_exact (void *, int MEM_STAT_DECL); 414169689Skanextern void *vec_gc_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL); 415169689Skanextern void *vec_gc_o_reserve_exact (void *, int, size_t, size_t 416169689Skan MEM_STAT_DECL); 417169689Skanextern void ggc_free (void *); 418169689Skan#define vec_gc_free(V) ggc_free (V) 419169689Skanextern void *vec_heap_p_reserve (void *, int MEM_STAT_DECL); 420169689Skanextern void *vec_heap_p_reserve_exact (void *, int MEM_STAT_DECL); 421169689Skanextern void *vec_heap_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL); 422169689Skanextern void *vec_heap_o_reserve_exact (void *, int, size_t, size_t 423169689Skan MEM_STAT_DECL); 424169689Skan#define vec_heap_free(V) free (V) 425169689Skan 426169689Skan#if ENABLE_CHECKING 427169689Skan#define VEC_CHECK_INFO ,__FILE__,__LINE__,__FUNCTION__ 428169689Skan#define VEC_CHECK_DECL ,const char *file_,unsigned line_,const char *function_ 429169689Skan#define VEC_CHECK_PASS ,file_,line_,function_ 430169689Skan 431169689Skan#define VEC_ASSERT(EXPR,OP,T,A) \ 432169689Skan (void)((EXPR) ? 0 : (VEC_ASSERT_FAIL(OP,VEC(T,A)), 0)) 433169689Skan 434169689Skanextern void vec_assert_fail (const char *, const char * VEC_CHECK_DECL) 435169689Skan ATTRIBUTE_NORETURN; 436169689Skan#define VEC_ASSERT_FAIL(OP,VEC) vec_assert_fail (OP,#VEC VEC_CHECK_PASS) 437169689Skan#else 438169689Skan#define VEC_CHECK_INFO 439169689Skan#define VEC_CHECK_DECL 440169689Skan#define VEC_CHECK_PASS 441169689Skan#define VEC_ASSERT(EXPR,OP,T,A) (void)(EXPR) 442169689Skan#endif 443169689Skan 444169689Skan#define VEC(T,A) VEC_##T##_##A 445169689Skan#define VEC_OP(T,A,OP) VEC_##T##_##A##_##OP 446169689Skan#else /* IN_GENGTYPE */ 447169689Skan#define VEC(T,A) VEC_ T _ A 448169689Skan#define VEC_STRINGIFY(X) VEC_STRINGIFY_(X) 449169689Skan#define VEC_STRINGIFY_(X) #X 450169689Skan#undef GTY 451169689Skan#endif /* IN_GENGTYPE */ 452169689Skan 453169689Skan/* Base of vector type, not user visible. */ 454169689Skan#define VEC_T(T,B) \ 455169689Skantypedef struct VEC(T,B) \ 456169689Skan{ \ 457169689Skan unsigned num; \ 458169689Skan unsigned alloc; \ 459169689Skan T vec[1]; \ 460169689Skan} VEC(T,B) 461169689Skan 462169689Skan#define VEC_T_GTY(T,B) \ 463169689Skantypedef struct VEC(T,B) GTY(()) \ 464169689Skan{ \ 465169689Skan unsigned num; \ 466169689Skan unsigned alloc; \ 467169689Skan T GTY ((length ("%h.num"))) vec[1]; \ 468169689Skan} VEC(T,B) 469169689Skan 470169689Skan/* Derived vector type, user visible. */ 471169689Skan#define VEC_TA_GTY(T,B,A,GTY) \ 472169689Skantypedef struct VEC(T,A) GTY \ 473169689Skan{ \ 474169689Skan VEC(T,B) base; \ 475169689Skan} VEC(T,A) 476169689Skan 477169689Skan/* Convert to base type. */ 478169689Skan#define VEC_BASE(P) ((P) ? &(P)->base : 0) 479169689Skan 480169689Skan/* Vector of integer-like object. */ 481169689Skan#if IN_GENGTYPE 482169689Skan{"DEF_VEC_I", VEC_STRINGIFY (VEC_T(#0,#1)) ";", "none"}, 483169689Skan{"DEF_VEC_ALLOC_I", VEC_STRINGIFY (VEC_TA (#0,#1,#2,#3)) ";", NULL}, 484169689Skan#else 485169689Skan#define DEF_VEC_I(T) \ 486169689Skanstatic inline void VEC_OP (T,must_be,integral_type) (void) \ 487169689Skan{ \ 488169689Skan (void)~(T)0; \ 489169689Skan} \ 490169689Skan \ 491169689SkanVEC_T(T,base); \ 492169689SkanVEC_TA_GTY(T,base,none,); \ 493169689SkanDEF_VEC_FUNC_P(T) \ 494169689Skanstruct vec_swallow_trailing_semi 495169689Skan#define DEF_VEC_ALLOC_I(T,A) \ 496169689SkanVEC_TA_GTY(T,base,A,); \ 497169689SkanDEF_VEC_ALLOC_FUNC_I(T,A) \ 498169689Skanstruct vec_swallow_trailing_semi 499169689Skan#endif 500169689Skan 501169689Skan/* Vector of pointer to object. */ 502169689Skan#if IN_GENGTYPE 503169689Skan{"DEF_VEC_P", VEC_STRINGIFY (VEC_T_GTY(#0,#1)) ";", "none"}, 504169689Skan{"DEF_VEC_ALLOC_P", VEC_STRINGIFY (VEC_TA_GTY (#0,#1,#2,#3)) ";", NULL}, 505169689Skan#else 506169689Skan#define DEF_VEC_P(T) \ 507169689Skanstatic inline void VEC_OP (T,must_be,pointer_type) (void) \ 508169689Skan{ \ 509169689Skan (void)((T)1 == (void *)1); \ 510169689Skan} \ 511169689Skan \ 512169689SkanVEC_T_GTY(T,base); \ 513169689SkanVEC_TA_GTY(T,base,none,); \ 514169689SkanDEF_VEC_FUNC_P(T) \ 515169689Skanstruct vec_swallow_trailing_semi 516169689Skan#define DEF_VEC_ALLOC_P(T,A) \ 517169689SkanVEC_TA_GTY(T,base,A,); \ 518169689SkanDEF_VEC_ALLOC_FUNC_P(T,A) \ 519169689Skanstruct vec_swallow_trailing_semi 520169689Skan#endif 521169689Skan 522169689Skan#define DEF_VEC_FUNC_P(T) \ 523169689Skanstatic inline unsigned VEC_OP (T,base,length) (const VEC(T,base) *vec_) \ 524169689Skan{ \ 525169689Skan return vec_ ? vec_->num : 0; \ 526169689Skan} \ 527169689Skan \ 528169689Skanstatic inline T VEC_OP (T,base,last) \ 529169689Skan (const VEC(T,base) *vec_ VEC_CHECK_DECL) \ 530169689Skan{ \ 531169689Skan VEC_ASSERT (vec_ && vec_->num, "last", T, base); \ 532169689Skan \ 533169689Skan return vec_->vec[vec_->num - 1]; \ 534169689Skan} \ 535169689Skan \ 536169689Skanstatic inline T VEC_OP (T,base,index) \ 537169689Skan (const VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \ 538169689Skan{ \ 539169689Skan VEC_ASSERT (vec_ && ix_ < vec_->num, "index", T, base); \ 540169689Skan \ 541169689Skan return vec_->vec[ix_]; \ 542169689Skan} \ 543169689Skan \ 544169689Skanstatic inline int VEC_OP (T,base,iterate) \ 545169689Skan (const VEC(T,base) *vec_, unsigned ix_, T *ptr) \ 546169689Skan{ \ 547169689Skan if (vec_ && ix_ < vec_->num) \ 548169689Skan { \ 549169689Skan *ptr = vec_->vec[ix_]; \ 550169689Skan return 1; \ 551169689Skan } \ 552169689Skan else \ 553169689Skan { \ 554169689Skan *ptr = 0; \ 555169689Skan return 0; \ 556169689Skan } \ 557169689Skan} \ 558169689Skan \ 559169689Skanstatic inline size_t VEC_OP (T,base,embedded_size) \ 560169689Skan (int alloc_) \ 561169689Skan{ \ 562169689Skan return offsetof (VEC(T,base),vec) + alloc_ * sizeof(T); \ 563169689Skan} \ 564169689Skan \ 565169689Skanstatic inline void VEC_OP (T,base,embedded_init) \ 566169689Skan (VEC(T,base) *vec_, int alloc_) \ 567169689Skan{ \ 568169689Skan vec_->num = 0; \ 569169689Skan vec_->alloc = alloc_; \ 570169689Skan} \ 571169689Skan \ 572169689Skanstatic inline int VEC_OP (T,base,space) \ 573169689Skan (VEC(T,base) *vec_, int alloc_ VEC_CHECK_DECL) \ 574169689Skan{ \ 575169689Skan VEC_ASSERT (alloc_ >= 0, "space", T, base); \ 576169689Skan return vec_ ? vec_->alloc - vec_->num >= (unsigned)alloc_ : !alloc_; \ 577169689Skan} \ 578169689Skan \ 579169689Skanstatic inline T *VEC_OP (T,base,quick_push) \ 580169689Skan (VEC(T,base) *vec_, T obj_ VEC_CHECK_DECL) \ 581169689Skan{ \ 582169689Skan T *slot_; \ 583169689Skan \ 584169689Skan VEC_ASSERT (vec_->num < vec_->alloc, "push", T, base); \ 585169689Skan slot_ = &vec_->vec[vec_->num++]; \ 586169689Skan *slot_ = obj_; \ 587169689Skan \ 588169689Skan return slot_; \ 589169689Skan} \ 590169689Skan \ 591169689Skanstatic inline T VEC_OP (T,base,pop) (VEC(T,base) *vec_ VEC_CHECK_DECL) \ 592169689Skan{ \ 593169689Skan T obj_; \ 594169689Skan \ 595169689Skan VEC_ASSERT (vec_->num, "pop", T, base); \ 596169689Skan obj_ = vec_->vec[--vec_->num]; \ 597169689Skan \ 598169689Skan return obj_; \ 599169689Skan} \ 600169689Skan \ 601169689Skanstatic inline void VEC_OP (T,base,truncate) \ 602169689Skan (VEC(T,base) *vec_, unsigned size_ VEC_CHECK_DECL) \ 603169689Skan{ \ 604169689Skan VEC_ASSERT (vec_ ? vec_->num >= size_ : !size_, "truncate", T, base); \ 605169689Skan if (vec_) \ 606169689Skan vec_->num = size_; \ 607169689Skan} \ 608169689Skan \ 609169689Skanstatic inline T VEC_OP (T,base,replace) \ 610169689Skan (VEC(T,base) *vec_, unsigned ix_, T obj_ VEC_CHECK_DECL) \ 611169689Skan{ \ 612169689Skan T old_obj_; \ 613169689Skan \ 614169689Skan VEC_ASSERT (ix_ < vec_->num, "replace", T, base); \ 615169689Skan old_obj_ = vec_->vec[ix_]; \ 616169689Skan vec_->vec[ix_] = obj_; \ 617169689Skan \ 618169689Skan return old_obj_; \ 619169689Skan} \ 620169689Skan \ 621169689Skanstatic inline T *VEC_OP (T,base,quick_insert) \ 622169689Skan (VEC(T,base) *vec_, unsigned ix_, T obj_ VEC_CHECK_DECL) \ 623169689Skan{ \ 624169689Skan T *slot_; \ 625169689Skan \ 626169689Skan VEC_ASSERT (vec_->num < vec_->alloc, "insert", T, base); \ 627169689Skan VEC_ASSERT (ix_ <= vec_->num, "insert", T, base); \ 628169689Skan slot_ = &vec_->vec[ix_]; \ 629169689Skan memmove (slot_ + 1, slot_, (vec_->num++ - ix_) * sizeof (T)); \ 630169689Skan *slot_ = obj_; \ 631169689Skan \ 632169689Skan return slot_; \ 633169689Skan} \ 634169689Skan \ 635169689Skanstatic inline T VEC_OP (T,base,ordered_remove) \ 636169689Skan (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \ 637169689Skan{ \ 638169689Skan T *slot_; \ 639169689Skan T obj_; \ 640169689Skan \ 641169689Skan VEC_ASSERT (ix_ < vec_->num, "remove", T, base); \ 642169689Skan slot_ = &vec_->vec[ix_]; \ 643169689Skan obj_ = *slot_; \ 644169689Skan memmove (slot_, slot_ + 1, (--vec_->num - ix_) * sizeof (T)); \ 645169689Skan \ 646169689Skan return obj_; \ 647169689Skan} \ 648169689Skan \ 649169689Skanstatic inline T VEC_OP (T,base,unordered_remove) \ 650169689Skan (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \ 651169689Skan{ \ 652169689Skan T *slot_; \ 653169689Skan T obj_; \ 654169689Skan \ 655169689Skan VEC_ASSERT (ix_ < vec_->num, "remove", T, base); \ 656169689Skan slot_ = &vec_->vec[ix_]; \ 657169689Skan obj_ = *slot_; \ 658169689Skan *slot_ = vec_->vec[--vec_->num]; \ 659169689Skan \ 660169689Skan return obj_; \ 661169689Skan} \ 662169689Skan \ 663169689Skanstatic inline void VEC_OP (T,base,block_remove) \ 664169689Skan (VEC(T,base) *vec_, unsigned ix_, unsigned len_ VEC_CHECK_DECL) \ 665169689Skan{ \ 666169689Skan T *slot_; \ 667169689Skan \ 668169689Skan VEC_ASSERT (ix_ + len_ <= vec_->num, "block_remove", T, base); \ 669169689Skan slot_ = &vec_->vec[ix_]; \ 670169689Skan vec_->num -= len_; \ 671169689Skan memmove (slot_, slot_ + len_, (vec_->num - ix_) * sizeof (T)); \ 672169689Skan} \ 673169689Skan \ 674169689Skanstatic inline T *VEC_OP (T,base,address) \ 675169689Skan (VEC(T,base) *vec_) \ 676169689Skan{ \ 677169689Skan return vec_ ? vec_->vec : 0; \ 678169689Skan} \ 679169689Skan \ 680169689Skanstatic inline unsigned VEC_OP (T,base,lower_bound) \ 681169689Skan (VEC(T,base) *vec_, const T obj_, \ 682169689Skan bool (*lessthan_)(const T, const T) VEC_CHECK_DECL) \ 683169689Skan{ \ 684169689Skan unsigned int len_ = VEC_OP (T,base, length) (vec_); \ 685169689Skan unsigned int half_, middle_; \ 686169689Skan unsigned int first_ = 0; \ 687169689Skan while (len_ > 0) \ 688169689Skan { \ 689169689Skan T middle_elem_; \ 690169689Skan half_ = len_ >> 1; \ 691169689Skan middle_ = first_; \ 692169689Skan middle_ += half_; \ 693169689Skan middle_elem_ = VEC_OP (T,base,index) (vec_, middle_ VEC_CHECK_PASS); \ 694169689Skan if (lessthan_ (middle_elem_, obj_)) \ 695169689Skan { \ 696169689Skan first_ = middle_; \ 697169689Skan ++first_; \ 698169689Skan len_ = len_ - half_ - 1; \ 699169689Skan } \ 700169689Skan else \ 701169689Skan len_ = half_; \ 702169689Skan } \ 703169689Skan return first_; \ 704169689Skan} 705169689Skan 706169689Skan#define DEF_VEC_ALLOC_FUNC_P(T,A) \ 707169689Skanstatic inline VEC(T,A) *VEC_OP (T,A,alloc) \ 708169689Skan (int alloc_ MEM_STAT_DECL) \ 709169689Skan{ \ 710169689Skan return (VEC(T,A) *) vec_##A##_p_reserve_exact (NULL, alloc_ \ 711169689Skan PASS_MEM_STAT); \ 712169689Skan} \ 713169689Skan \ 714169689Skanstatic inline void VEC_OP (T,A,free) \ 715169689Skan (VEC(T,A) **vec_) \ 716169689Skan{ \ 717169689Skan if (*vec_) \ 718169689Skan vec_##A##_free (*vec_); \ 719169689Skan *vec_ = NULL; \ 720169689Skan} \ 721169689Skan \ 722169689Skanstatic inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \ 723169689Skan{ \ 724169689Skan size_t len_ = vec_ ? vec_->num : 0; \ 725169689Skan VEC (T,A) *new_vec_ = NULL; \ 726169689Skan \ 727169689Skan if (len_) \ 728169689Skan { \ 729169689Skan new_vec_ = (VEC (T,A) *)(vec_##A##_p_reserve_exact \ 730169689Skan (NULL, len_ PASS_MEM_STAT)); \ 731169689Skan \ 732169689Skan new_vec_->base.num = len_; \ 733169689Skan memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_); \ 734169689Skan } \ 735169689Skan return new_vec_; \ 736169689Skan} \ 737169689Skan \ 738169689Skanstatic inline int VEC_OP (T,A,reserve) \ 739169689Skan (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \ 740169689Skan{ \ 741169689Skan int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \ 742169689Skan VEC_CHECK_PASS); \ 743169689Skan \ 744169689Skan if (extend) \ 745169689Skan *vec_ = (VEC(T,A) *) vec_##A##_p_reserve (*vec_, alloc_ PASS_MEM_STAT); \ 746169689Skan \ 747169689Skan return extend; \ 748169689Skan} \ 749169689Skan \ 750169689Skanstatic inline int VEC_OP (T,A,reserve_exact) \ 751169689Skan (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \ 752169689Skan{ \ 753169689Skan int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \ 754169689Skan VEC_CHECK_PASS); \ 755169689Skan \ 756169689Skan if (extend) \ 757169689Skan *vec_ = (VEC(T,A) *) vec_##A##_p_reserve_exact (*vec_, alloc_ \ 758169689Skan PASS_MEM_STAT); \ 759169689Skan \ 760169689Skan return extend; \ 761169689Skan} \ 762169689Skan \ 763169689Skanstatic inline void VEC_OP (T,A,safe_grow) \ 764169689Skan (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \ 765169689Skan{ \ 766169689Skan VEC_ASSERT (size_ >= 0 \ 767169689Skan && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \ 768169689Skan "grow", T, A); \ 769169689Skan VEC_OP (T,A,reserve_exact) (vec_, \ 770169689Skan size_ - (int)(*vec_ ? VEC_BASE(*vec_)->num : 0) \ 771169689Skan VEC_CHECK_PASS PASS_MEM_STAT); \ 772169689Skan VEC_BASE (*vec_)->num = size_; \ 773169689Skan} \ 774169689Skan \ 775169689Skanstatic inline T *VEC_OP (T,A,safe_push) \ 776169689Skan (VEC(T,A) **vec_, T obj_ VEC_CHECK_DECL MEM_STAT_DECL) \ 777169689Skan{ \ 778169689Skan VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \ 779169689Skan \ 780169689Skan return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS); \ 781169689Skan} \ 782169689Skan \ 783169689Skanstatic inline T *VEC_OP (T,A,safe_insert) \ 784169689Skan (VEC(T,A) **vec_, unsigned ix_, T obj_ VEC_CHECK_DECL MEM_STAT_DECL) \ 785169689Skan{ \ 786169689Skan VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \ 787169689Skan \ 788169689Skan return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_ \ 789169689Skan VEC_CHECK_PASS); \ 790169689Skan} 791169689Skan 792169689Skan/* Vector of object. */ 793169689Skan#if IN_GENGTYPE 794169689Skan{"DEF_VEC_O", VEC_STRINGIFY (VEC_T_GTY(#0,#1)) ";", "none"}, 795169689Skan{"DEF_VEC_ALLOC_O", VEC_STRINGIFY (VEC_TA_GTY(#0,#1,#2,#3)) ";", NULL}, 796169689Skan#else 797169689Skan#define DEF_VEC_O(T) \ 798169689SkanVEC_T_GTY(T,base); \ 799169689SkanVEC_TA_GTY(T,base,none,); \ 800169689SkanDEF_VEC_FUNC_O(T) \ 801169689Skanstruct vec_swallow_trailing_semi 802169689Skan#define DEF_VEC_ALLOC_O(T,A) \ 803169689SkanVEC_TA_GTY(T,base,A,); \ 804169689SkanDEF_VEC_ALLOC_FUNC_O(T,A) \ 805169689Skanstruct vec_swallow_trailing_semi 806169689Skan#endif 807169689Skan 808169689Skan#define DEF_VEC_FUNC_O(T) \ 809169689Skanstatic inline unsigned VEC_OP (T,base,length) (const VEC(T,base) *vec_) \ 810169689Skan{ \ 811169689Skan return vec_ ? vec_->num : 0; \ 812169689Skan} \ 813169689Skan \ 814169689Skanstatic inline T *VEC_OP (T,base,last) (VEC(T,base) *vec_ VEC_CHECK_DECL) \ 815169689Skan{ \ 816169689Skan VEC_ASSERT (vec_ && vec_->num, "last", T, base); \ 817169689Skan \ 818169689Skan return &vec_->vec[vec_->num - 1]; \ 819169689Skan} \ 820169689Skan \ 821169689Skanstatic inline T *VEC_OP (T,base,index) \ 822169689Skan (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \ 823169689Skan{ \ 824169689Skan VEC_ASSERT (vec_ && ix_ < vec_->num, "index", T, base); \ 825169689Skan \ 826169689Skan return &vec_->vec[ix_]; \ 827169689Skan} \ 828169689Skan \ 829169689Skanstatic inline int VEC_OP (T,base,iterate) \ 830169689Skan (VEC(T,base) *vec_, unsigned ix_, T **ptr) \ 831169689Skan{ \ 832169689Skan if (vec_ && ix_ < vec_->num) \ 833169689Skan { \ 834169689Skan *ptr = &vec_->vec[ix_]; \ 835169689Skan return 1; \ 836169689Skan } \ 837169689Skan else \ 838169689Skan { \ 839169689Skan *ptr = 0; \ 840169689Skan return 0; \ 841169689Skan } \ 842169689Skan} \ 843169689Skan \ 844169689Skanstatic inline size_t VEC_OP (T,base,embedded_size) \ 845169689Skan (int alloc_) \ 846169689Skan{ \ 847169689Skan return offsetof (VEC(T,base),vec) + alloc_ * sizeof(T); \ 848169689Skan} \ 849169689Skan \ 850169689Skanstatic inline void VEC_OP (T,base,embedded_init) \ 851169689Skan (VEC(T,base) *vec_, int alloc_) \ 852169689Skan{ \ 853169689Skan vec_->num = 0; \ 854169689Skan vec_->alloc = alloc_; \ 855169689Skan} \ 856169689Skan \ 857169689Skanstatic inline int VEC_OP (T,base,space) \ 858169689Skan (VEC(T,base) *vec_, int alloc_ VEC_CHECK_DECL) \ 859169689Skan{ \ 860169689Skan VEC_ASSERT (alloc_ >= 0, "space", T, base); \ 861169689Skan return vec_ ? vec_->alloc - vec_->num >= (unsigned)alloc_ : !alloc_; \ 862169689Skan} \ 863169689Skan \ 864169689Skanstatic inline T *VEC_OP (T,base,quick_push) \ 865169689Skan (VEC(T,base) *vec_, const T *obj_ VEC_CHECK_DECL) \ 866169689Skan{ \ 867169689Skan T *slot_; \ 868169689Skan \ 869169689Skan VEC_ASSERT (vec_->num < vec_->alloc, "push", T, base); \ 870169689Skan slot_ = &vec_->vec[vec_->num++]; \ 871169689Skan if (obj_) \ 872169689Skan *slot_ = *obj_; \ 873169689Skan \ 874169689Skan return slot_; \ 875169689Skan} \ 876169689Skan \ 877169689Skanstatic inline void VEC_OP (T,base,pop) (VEC(T,base) *vec_ VEC_CHECK_DECL) \ 878169689Skan{ \ 879169689Skan VEC_ASSERT (vec_->num, "pop", T, base); \ 880169689Skan --vec_->num; \ 881169689Skan} \ 882169689Skan \ 883169689Skanstatic inline void VEC_OP (T,base,truncate) \ 884169689Skan (VEC(T,base) *vec_, unsigned size_ VEC_CHECK_DECL) \ 885169689Skan{ \ 886169689Skan VEC_ASSERT (vec_ ? vec_->num >= size_ : !size_, "truncate", T, base); \ 887169689Skan if (vec_) \ 888169689Skan vec_->num = size_; \ 889169689Skan} \ 890169689Skan \ 891169689Skanstatic inline T *VEC_OP (T,base,replace) \ 892169689Skan (VEC(T,base) *vec_, unsigned ix_, const T *obj_ VEC_CHECK_DECL) \ 893169689Skan{ \ 894169689Skan T *slot_; \ 895169689Skan \ 896169689Skan VEC_ASSERT (ix_ < vec_->num, "replace", T, base); \ 897169689Skan slot_ = &vec_->vec[ix_]; \ 898169689Skan if (obj_) \ 899169689Skan *slot_ = *obj_; \ 900169689Skan \ 901169689Skan return slot_; \ 902169689Skan} \ 903169689Skan \ 904169689Skanstatic inline T *VEC_OP (T,base,quick_insert) \ 905169689Skan (VEC(T,base) *vec_, unsigned ix_, const T *obj_ VEC_CHECK_DECL) \ 906169689Skan{ \ 907169689Skan T *slot_; \ 908169689Skan \ 909169689Skan VEC_ASSERT (vec_->num < vec_->alloc, "insert", T, base); \ 910169689Skan VEC_ASSERT (ix_ <= vec_->num, "insert", T, base); \ 911169689Skan slot_ = &vec_->vec[ix_]; \ 912169689Skan memmove (slot_ + 1, slot_, (vec_->num++ - ix_) * sizeof (T)); \ 913169689Skan if (obj_) \ 914169689Skan *slot_ = *obj_; \ 915169689Skan \ 916169689Skan return slot_; \ 917169689Skan} \ 918169689Skan \ 919169689Skanstatic inline void VEC_OP (T,base,ordered_remove) \ 920169689Skan (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \ 921169689Skan{ \ 922169689Skan T *slot_; \ 923169689Skan \ 924169689Skan VEC_ASSERT (ix_ < vec_->num, "remove", T, base); \ 925169689Skan slot_ = &vec_->vec[ix_]; \ 926169689Skan memmove (slot_, slot_ + 1, (--vec_->num - ix_) * sizeof (T)); \ 927169689Skan} \ 928169689Skan \ 929169689Skanstatic inline void VEC_OP (T,base,unordered_remove) \ 930169689Skan (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \ 931169689Skan{ \ 932169689Skan VEC_ASSERT (ix_ < vec_->num, "remove", T, base); \ 933169689Skan vec_->vec[ix_] = vec_->vec[--vec_->num]; \ 934169689Skan} \ 935169689Skan \ 936169689Skanstatic inline void VEC_OP (T,base,block_remove) \ 937169689Skan (VEC(T,base) *vec_, unsigned ix_, unsigned len_ VEC_CHECK_DECL) \ 938169689Skan{ \ 939169689Skan T *slot_; \ 940169689Skan \ 941169689Skan VEC_ASSERT (ix_ + len_ <= vec_->num, "block_remove", T, base); \ 942169689Skan slot_ = &vec_->vec[ix_]; \ 943169689Skan vec_->num -= len_; \ 944169689Skan memmove (slot_, slot_ + len_, (vec_->num - ix_) * sizeof (T)); \ 945169689Skan} \ 946169689Skan \ 947169689Skanstatic inline T *VEC_OP (T,base,address) \ 948169689Skan (VEC(T,base) *vec_) \ 949169689Skan{ \ 950169689Skan return vec_ ? vec_->vec : 0; \ 951169689Skan} \ 952169689Skan \ 953169689Skanstatic inline unsigned VEC_OP (T,base,lower_bound) \ 954169689Skan (VEC(T,base) *vec_, const T *obj_, \ 955169689Skan bool (*lessthan_)(const T *, const T *) VEC_CHECK_DECL) \ 956169689Skan{ \ 957169689Skan unsigned int len_ = VEC_OP (T, base, length) (vec_); \ 958169689Skan unsigned int half_, middle_; \ 959169689Skan unsigned int first_ = 0; \ 960169689Skan while (len_ > 0) \ 961169689Skan { \ 962169689Skan T *middle_elem_; \ 963169689Skan half_ = len_ >> 1; \ 964169689Skan middle_ = first_; \ 965169689Skan middle_ += half_; \ 966169689Skan middle_elem_ = VEC_OP (T,base,index) (vec_, middle_ VEC_CHECK_PASS); \ 967169689Skan if (lessthan_ (middle_elem_, obj_)) \ 968169689Skan { \ 969169689Skan first_ = middle_; \ 970169689Skan ++first_; \ 971169689Skan len_ = len_ - half_ - 1; \ 972169689Skan } \ 973169689Skan else \ 974169689Skan len_ = half_; \ 975169689Skan } \ 976169689Skan return first_; \ 977169689Skan} 978169689Skan 979169689Skan#define DEF_VEC_ALLOC_FUNC_O(T,A) \ 980169689Skanstatic inline VEC(T,A) *VEC_OP (T,A,alloc) \ 981169689Skan (int alloc_ MEM_STAT_DECL) \ 982169689Skan{ \ 983169689Skan return (VEC(T,A) *) vec_##A##_o_reserve_exact (NULL, alloc_, \ 984169689Skan offsetof (VEC(T,A),base.vec), \ 985169689Skan sizeof (T) \ 986169689Skan PASS_MEM_STAT); \ 987169689Skan} \ 988169689Skan \ 989169689Skanstatic inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \ 990169689Skan{ \ 991169689Skan size_t len_ = vec_ ? vec_->num : 0; \ 992169689Skan VEC (T,A) *new_vec_ = NULL; \ 993169689Skan \ 994169689Skan if (len_) \ 995169689Skan { \ 996169689Skan new_vec_ = (VEC (T,A) *)(vec_##A##_o_reserve_exact \ 997169689Skan (NULL, len_, \ 998169689Skan offsetof (VEC(T,A),base.vec), sizeof (T) \ 999169689Skan PASS_MEM_STAT)); \ 1000169689Skan \ 1001169689Skan new_vec_->base.num = len_; \ 1002169689Skan memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_); \ 1003169689Skan } \ 1004169689Skan return new_vec_; \ 1005169689Skan} \ 1006169689Skan \ 1007169689Skanstatic inline void VEC_OP (T,A,free) \ 1008169689Skan (VEC(T,A) **vec_) \ 1009169689Skan{ \ 1010169689Skan if (*vec_) \ 1011169689Skan vec_##A##_free (*vec_); \ 1012169689Skan *vec_ = NULL; \ 1013169689Skan} \ 1014169689Skan \ 1015169689Skanstatic inline int VEC_OP (T,A,reserve) \ 1016169689Skan (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \ 1017169689Skan{ \ 1018169689Skan int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \ 1019169689Skan VEC_CHECK_PASS); \ 1020169689Skan \ 1021169689Skan if (extend) \ 1022169689Skan *vec_ = (VEC(T,A) *) vec_##A##_o_reserve (*vec_, alloc_, \ 1023169689Skan offsetof (VEC(T,A),base.vec),\ 1024169689Skan sizeof (T) \ 1025169689Skan PASS_MEM_STAT); \ 1026169689Skan \ 1027169689Skan return extend; \ 1028169689Skan} \ 1029169689Skan \ 1030169689Skanstatic inline int VEC_OP (T,A,reserve_exact) \ 1031169689Skan (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \ 1032169689Skan{ \ 1033169689Skan int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \ 1034169689Skan VEC_CHECK_PASS); \ 1035169689Skan \ 1036169689Skan if (extend) \ 1037169689Skan *vec_ = (VEC(T,A) *) vec_##A##_o_reserve_exact \ 1038169689Skan (*vec_, alloc_, \ 1039169689Skan offsetof (VEC(T,A),base.vec), \ 1040169689Skan sizeof (T) PASS_MEM_STAT); \ 1041169689Skan \ 1042169689Skan return extend; \ 1043169689Skan} \ 1044169689Skan \ 1045169689Skanstatic inline void VEC_OP (T,A,safe_grow) \ 1046169689Skan (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \ 1047169689Skan{ \ 1048169689Skan VEC_ASSERT (size_ >= 0 \ 1049169689Skan && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \ 1050169689Skan "grow", T, A); \ 1051169689Skan VEC_OP (T,A,reserve_exact) (vec_, \ 1052169689Skan size_ - (int)(*vec_ ? VEC_BASE(*vec_)->num : 0) \ 1053169689Skan VEC_CHECK_PASS PASS_MEM_STAT); \ 1054169689Skan VEC_BASE (*vec_)->num = size_; \ 1055169689Skan} \ 1056169689Skan \ 1057169689Skanstatic inline T *VEC_OP (T,A,safe_push) \ 1058169689Skan (VEC(T,A) **vec_, const T *obj_ VEC_CHECK_DECL MEM_STAT_DECL) \ 1059169689Skan{ \ 1060169689Skan VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \ 1061169689Skan \ 1062169689Skan return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS); \ 1063169689Skan} \ 1064169689Skan \ 1065169689Skanstatic inline T *VEC_OP (T,A,safe_insert) \ 1066169689Skan (VEC(T,A) **vec_, unsigned ix_, const T *obj_ \ 1067169689Skan VEC_CHECK_DECL MEM_STAT_DECL) \ 1068169689Skan{ \ 1069169689Skan VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \ 1070169689Skan \ 1071169689Skan return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_ \ 1072169689Skan VEC_CHECK_PASS); \ 1073169689Skan} 1074169689Skan 1075169689Skan#define DEF_VEC_ALLOC_FUNC_I(T,A) \ 1076169689Skanstatic inline VEC(T,A) *VEC_OP (T,A,alloc) \ 1077169689Skan (int alloc_ MEM_STAT_DECL) \ 1078169689Skan{ \ 1079169689Skan return (VEC(T,A) *) vec_##A##_o_reserve_exact \ 1080169689Skan (NULL, alloc_, offsetof (VEC(T,A),base.vec), \ 1081169689Skan sizeof (T) PASS_MEM_STAT); \ 1082169689Skan} \ 1083169689Skan \ 1084169689Skanstatic inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \ 1085169689Skan{ \ 1086169689Skan size_t len_ = vec_ ? vec_->num : 0; \ 1087169689Skan VEC (T,A) *new_vec_ = NULL; \ 1088169689Skan \ 1089169689Skan if (len_) \ 1090169689Skan { \ 1091169689Skan new_vec_ = (VEC (T,A) *)(vec_##A##_o_reserve_exact \ 1092169689Skan (NULL, len_, \ 1093169689Skan offsetof (VEC(T,A),base.vec), sizeof (T) \ 1094169689Skan PASS_MEM_STAT)); \ 1095169689Skan \ 1096169689Skan new_vec_->base.num = len_; \ 1097169689Skan memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_); \ 1098169689Skan } \ 1099169689Skan return new_vec_; \ 1100169689Skan} \ 1101169689Skan \ 1102169689Skanstatic inline void VEC_OP (T,A,free) \ 1103169689Skan (VEC(T,A) **vec_) \ 1104169689Skan{ \ 1105169689Skan if (*vec_) \ 1106169689Skan vec_##A##_free (*vec_); \ 1107169689Skan *vec_ = NULL; \ 1108169689Skan} \ 1109169689Skan \ 1110169689Skanstatic inline int VEC_OP (T,A,reserve) \ 1111169689Skan (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \ 1112169689Skan{ \ 1113169689Skan int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \ 1114169689Skan VEC_CHECK_PASS); \ 1115169689Skan \ 1116169689Skan if (extend) \ 1117169689Skan *vec_ = (VEC(T,A) *) vec_##A##_o_reserve (*vec_, alloc_, \ 1118169689Skan offsetof (VEC(T,A),base.vec),\ 1119169689Skan sizeof (T) \ 1120169689Skan PASS_MEM_STAT); \ 1121169689Skan \ 1122169689Skan return extend; \ 1123169689Skan} \ 1124169689Skan \ 1125169689Skanstatic inline int VEC_OP (T,A,reserve_exact) \ 1126169689Skan (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \ 1127169689Skan{ \ 1128169689Skan int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \ 1129169689Skan VEC_CHECK_PASS); \ 1130169689Skan \ 1131169689Skan if (extend) \ 1132169689Skan *vec_ = (VEC(T,A) *) vec_##A##_o_reserve_exact \ 1133169689Skan (*vec_, alloc_, offsetof (VEC(T,A),base.vec), \ 1134169689Skan sizeof (T) PASS_MEM_STAT); \ 1135169689Skan \ 1136169689Skan return extend; \ 1137169689Skan} \ 1138169689Skan \ 1139169689Skanstatic inline void VEC_OP (T,A,safe_grow) \ 1140169689Skan (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \ 1141169689Skan{ \ 1142169689Skan VEC_ASSERT (size_ >= 0 \ 1143169689Skan && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \ 1144169689Skan "grow", T, A); \ 1145169689Skan VEC_OP (T,A,reserve_exact) (vec_, \ 1146169689Skan size_ - (int)(*vec_ ? VEC_BASE(*vec_)->num : 0) \ 1147169689Skan VEC_CHECK_PASS PASS_MEM_STAT); \ 1148169689Skan VEC_BASE (*vec_)->num = size_; \ 1149169689Skan} \ 1150169689Skan \ 1151169689Skanstatic inline T *VEC_OP (T,A,safe_push) \ 1152169689Skan (VEC(T,A) **vec_, const T obj_ VEC_CHECK_DECL MEM_STAT_DECL) \ 1153169689Skan{ \ 1154169689Skan VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \ 1155169689Skan \ 1156169689Skan return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS); \ 1157169689Skan} \ 1158169689Skan \ 1159169689Skanstatic inline T *VEC_OP (T,A,safe_insert) \ 1160169689Skan (VEC(T,A) **vec_, unsigned ix_, const T obj_ \ 1161169689Skan VEC_CHECK_DECL MEM_STAT_DECL) \ 1162169689Skan{ \ 1163169689Skan VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \ 1164169689Skan \ 1165169689Skan return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_ \ 1166169689Skan VEC_CHECK_PASS); \ 1167169689Skan} 1168169689Skan 1169169689Skan#endif /* GCC_VEC_H */ 1170