1/* Vector API for GNU compiler. 2 Copyright (C) 2004, 2005, 2007, 2008, 2009, 2010 3 Free Software Foundation, Inc. 4 Contributed by Nathan Sidwell <nathan@codesourcery.com> 5 6This file is part of GCC. 7 8GCC is free software; you can redistribute it and/or modify it under 9the terms of the GNU General Public License as published by the Free 10Software Foundation; either version 3, or (at your option) any later 11version. 12 13GCC is distributed in the hope that it will be useful, but WITHOUT ANY 14WARRANTY; without even the implied warranty of MERCHANTABILITY or 15FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 16for more details. 17 18You should have received a copy of the GNU General Public License 19along with GCC; see the file COPYING3. If not see 20<http://www.gnu.org/licenses/>. */ 21 22#ifndef GCC_VEC_H 23#define GCC_VEC_H 24 25/* The macros here implement a set of templated vector types and 26 associated interfaces. These templates are implemented with 27 macros, as we're not in C++ land. The interface functions are 28 typesafe and use static inline functions, sometimes backed by 29 out-of-line generic functions. The vectors are designed to 30 interoperate with the GTY machinery. 31 32 Because of the different behavior of structure objects, scalar 33 objects and of pointers, there are three flavors, one for each of 34 these variants. Both the structure object and pointer variants 35 pass pointers to objects around -- in the former case the pointers 36 are stored into the vector and in the latter case the pointers are 37 dereferenced and the objects copied into the vector. The scalar 38 object variant is suitable for int-like objects, and the vector 39 elements are returned by value. 40 41 There are both 'index' and 'iterate' accessors. The iterator 42 returns a boolean iteration condition and updates the iteration 43 variable passed by reference. Because the iterator will be 44 inlined, the address-of can be optimized away. 45 46 The vectors are implemented using the trailing array idiom, thus 47 they are not resizeable without changing the address of the vector 48 object itself. This means you cannot have variables or fields of 49 vector type -- always use a pointer to a vector. The one exception 50 is the final field of a structure, which could be a vector type. 51 You will have to use the embedded_size & embedded_init calls to 52 create such objects, and they will probably not be resizeable (so 53 don't use the 'safe' allocation variants). The trailing array 54 idiom is used (rather than a pointer to an array of data), because, 55 if we allow NULL to also represent an empty vector, empty vectors 56 occupy minimal space in the structure containing them. 57 58 Each operation that increases the number of active elements is 59 available in 'quick' and 'safe' variants. The former presumes that 60 there is sufficient allocated space for the operation to succeed 61 (it dies if there is not). The latter will reallocate the 62 vector, if needed. Reallocation causes an exponential increase in 63 vector size. If you know you will be adding N elements, it would 64 be more efficient to use the reserve operation before adding the 65 elements with the 'quick' operation. This will ensure there are at 66 least as many elements as you ask for, it will exponentially 67 increase if there are too few spare slots. If you want reserve a 68 specific number of slots, but do not want the exponential increase 69 (for instance, you know this is the last allocation), use the 70 reserve_exact operation. You can also create a vector of a 71 specific size from the get go. 72 73 You should prefer the push and pop operations, as they append and 74 remove from the end of the vector. If you need to remove several 75 items in one go, use the truncate operation. The insert and remove 76 operations allow you to change elements in the middle of the 77 vector. There are two remove operations, one which preserves the 78 element ordering 'ordered_remove', and one which does not 79 'unordered_remove'. The latter function copies the end element 80 into the removed slot, rather than invoke a memmove operation. The 81 'lower_bound' function will determine where to place an item in the 82 array using insert that will maintain sorted order. 83 84 When a vector type is defined, first a non-memory managed version 85 is created. You can then define either or both garbage collected 86 and heap allocated versions. The allocation mechanism is specified 87 when the type is defined, and is therefore part of the type. If 88 you need both gc'd and heap allocated versions, you still must have 89 *exactly* one definition of the common non-memory managed base vector. 90 91 If you need to directly manipulate a vector, then the 'address' 92 accessor will return the address of the start of the vector. Also 93 the 'space' predicate will tell you whether there is spare capacity 94 in the vector. You will not normally need to use these two functions. 95 96 Vector types are defined using a DEF_VEC_{O,P,I}(TYPEDEF) macro, to 97 get the non-memory allocation version, and then a 98 DEF_VEC_ALLOC_{O,P,I}(TYPEDEF,ALLOC) macro to get memory managed 99 vectors. Variables of vector type are declared using a 100 VEC(TYPEDEF,ALLOC) macro. The ALLOC argument specifies the 101 allocation strategy, and can be either 'gc' or 'heap' for garbage 102 collected and heap allocated respectively. It can be 'none' to get 103 a vector that must be explicitly allocated (for instance as a 104 trailing array of another structure). The characters O, P and I 105 indicate whether TYPEDEF is a pointer (P), object (O) or integral 106 (I) type. Be careful to pick the correct one, as you'll get an 107 awkward and inefficient API if you use the wrong one. There is a 108 check, which results in a compile-time warning, for the P and I 109 versions, but there is no check for the O versions, as that is not 110 possible in plain C. Due to the way GTY works, you must annotate 111 any structures you wish to insert or reference from a vector with a 112 GTY(()) tag. You need to do this even if you never declare the GC 113 allocated variants. 114 115 An example of their use would be, 116 117 DEF_VEC_P(tree); // non-managed tree vector. 118 DEF_VEC_ALLOC_P(tree,gc); // gc'd vector of tree pointers. This must 119 // appear at file scope. 120 121 struct my_struct { 122 VEC(tree,gc) *v; // A (pointer to) a vector of tree pointers. 123 }; 124 125 struct my_struct *s; 126 127 if (VEC_length(tree,s->v)) { we have some contents } 128 VEC_safe_push(tree,gc,s->v,decl); // append some decl onto the end 129 for (ix = 0; VEC_iterate(tree,s->v,ix,elt); ix++) 130 { do something with elt } 131 132*/ 133 134/* Macros to invoke API calls. A single macro works for both pointer 135 and object vectors, but the argument and return types might well be 136 different. In each macro, T is the typedef of the vector elements, 137 and A is the allocation strategy. The allocation strategy is only 138 present when it is required. Some of these macros pass the vector, 139 V, by reference (by taking its address), this is noted in the 140 descriptions. */ 141 142/* Length of vector 143 unsigned VEC_T_length(const VEC(T) *v); 144 145 Return the number of active elements in V. V can be NULL, in which 146 case zero is returned. */ 147 148#define VEC_length(T,V) (VEC_OP(T,base,length)(VEC_BASE(V))) 149 150 151/* Check if vector is empty 152 int VEC_T_empty(const VEC(T) *v); 153 154 Return nonzero if V is an empty vector (or V is NULL), zero otherwise. */ 155 156#define VEC_empty(T,V) (VEC_length (T,V) == 0) 157 158 159/* Get the final element of the vector. 160 T VEC_T_last(VEC(T) *v); // Integer 161 T VEC_T_last(VEC(T) *v); // Pointer 162 T *VEC_T_last(VEC(T) *v); // Object 163 164 Return the final element. V must not be empty. */ 165 166#define VEC_last(T,V) (VEC_OP(T,base,last)(VEC_BASE(V) VEC_CHECK_INFO)) 167 168/* Index into vector 169 T VEC_T_index(VEC(T) *v, unsigned ix); // Integer 170 T VEC_T_index(VEC(T) *v, unsigned ix); // Pointer 171 T *VEC_T_index(VEC(T) *v, unsigned ix); // Object 172 173 Return the IX'th element. If IX must be in the domain of V. */ 174 175#define VEC_index(T,V,I) (VEC_OP(T,base,index)(VEC_BASE(V),I VEC_CHECK_INFO)) 176 177/* Iterate over vector 178 int VEC_T_iterate(VEC(T) *v, unsigned ix, T &ptr); // Integer 179 int VEC_T_iterate(VEC(T) *v, unsigned ix, T &ptr); // Pointer 180 int VEC_T_iterate(VEC(T) *v, unsigned ix, T *&ptr); // Object 181 182 Return iteration condition and update PTR to point to the IX'th 183 element. At the end of iteration, sets PTR to NULL. Use this to 184 iterate over the elements of a vector as follows, 185 186 for (ix = 0; VEC_iterate(T,v,ix,ptr); ix++) 187 continue; */ 188 189#define VEC_iterate(T,V,I,P) (VEC_OP(T,base,iterate)(VEC_BASE(V),I,&(P))) 190 191/* Allocate new vector. 192 VEC(T,A) *VEC_T_A_alloc(int reserve); 193 194 Allocate a new vector with space for RESERVE objects. If RESERVE 195 is zero, NO vector is created. */ 196 197#define VEC_alloc(T,A,N) (VEC_OP(T,A,alloc)(N MEM_STAT_INFO)) 198 199/* Free a vector. 200 void VEC_T_A_free(VEC(T,A) *&); 201 202 Free a vector and set it to NULL. */ 203 204#define VEC_free(T,A,V) (VEC_OP(T,A,free)(&V)) 205 206/* Use these to determine the required size and initialization of a 207 vector embedded within another structure (as the final member). 208 209 size_t VEC_T_embedded_size(int reserve); 210 void VEC_T_embedded_init(VEC(T) *v, int reserve); 211 212 These allow the caller to perform the memory allocation. */ 213 214#define VEC_embedded_size(T,N) (VEC_OP(T,base,embedded_size)(N)) 215#define VEC_embedded_init(T,O,N) (VEC_OP(T,base,embedded_init)(VEC_BASE(O),N)) 216 217/* Copy a vector. 218 VEC(T,A) *VEC_T_A_copy(VEC(T) *); 219 220 Copy the live elements of a vector into a new vector. The new and 221 old vectors need not be allocated by the same mechanism. */ 222 223#define VEC_copy(T,A,V) (VEC_OP(T,A,copy)(VEC_BASE(V) MEM_STAT_INFO)) 224 225/* Determine if a vector has additional capacity. 226 227 int VEC_T_space (VEC(T) *v,int reserve) 228 229 If V has space for RESERVE additional entries, return nonzero. You 230 usually only need to use this if you are doing your own vector 231 reallocation, for instance on an embedded vector. This returns 232 nonzero in exactly the same circumstances that VEC_T_reserve 233 will. */ 234 235#define VEC_space(T,V,R) \ 236 (VEC_OP(T,base,space)(VEC_BASE(V),R VEC_CHECK_INFO)) 237 238/* Reserve space. 239 int VEC_T_A_reserve(VEC(T,A) *&v, int reserve); 240 241 Ensure that V has at least RESERVE slots available. This will 242 create additional headroom. Note this can cause V to be 243 reallocated. Returns nonzero iff reallocation actually 244 occurred. */ 245 246#define VEC_reserve(T,A,V,R) \ 247 (VEC_OP(T,A,reserve)(&(V),R VEC_CHECK_INFO MEM_STAT_INFO)) 248 249/* Reserve space exactly. 250 int VEC_T_A_reserve_exact(VEC(T,A) *&v, int reserve); 251 252 Ensure that V has at least RESERVE slots available. This will not 253 create additional headroom. Note this can cause V to be 254 reallocated. Returns nonzero iff reallocation actually 255 occurred. */ 256 257#define VEC_reserve_exact(T,A,V,R) \ 258 (VEC_OP(T,A,reserve_exact)(&(V),R VEC_CHECK_INFO MEM_STAT_INFO)) 259 260/* Push object with no reallocation 261 T *VEC_T_quick_push (VEC(T) *v, T obj); // Integer 262 T *VEC_T_quick_push (VEC(T) *v, T obj); // Pointer 263 T *VEC_T_quick_push (VEC(T) *v, T *obj); // Object 264 265 Push a new element onto the end, returns a pointer to the slot 266 filled in. For object vectors, the new value can be NULL, in which 267 case NO initialization is performed. There must 268 be sufficient space in the vector. */ 269 270#define VEC_quick_push(T,V,O) \ 271 (VEC_OP(T,base,quick_push)(VEC_BASE(V),O VEC_CHECK_INFO)) 272 273/* Push object with reallocation 274 T *VEC_T_A_safe_push (VEC(T,A) *&v, T obj); // Integer 275 T *VEC_T_A_safe_push (VEC(T,A) *&v, T obj); // Pointer 276 T *VEC_T_A_safe_push (VEC(T,A) *&v, T *obj); // Object 277 278 Push a new element onto the end, returns a pointer to the slot 279 filled in. For object vectors, the new value can be NULL, in which 280 case NO initialization is performed. Reallocates V, if needed. */ 281 282#define VEC_safe_push(T,A,V,O) \ 283 (VEC_OP(T,A,safe_push)(&(V),O VEC_CHECK_INFO MEM_STAT_INFO)) 284 285/* Pop element off end 286 T VEC_T_pop (VEC(T) *v); // Integer 287 T VEC_T_pop (VEC(T) *v); // Pointer 288 void VEC_T_pop (VEC(T) *v); // Object 289 290 Pop the last element off the end. Returns the element popped, for 291 pointer vectors. */ 292 293#define VEC_pop(T,V) (VEC_OP(T,base,pop)(VEC_BASE(V) VEC_CHECK_INFO)) 294 295/* Truncate to specific length 296 void VEC_T_truncate (VEC(T) *v, unsigned len); 297 298 Set the length as specified. The new length must be less than or 299 equal to the current length. This is an O(1) operation. */ 300 301#define VEC_truncate(T,V,I) \ 302 (VEC_OP(T,base,truncate)(VEC_BASE(V),I VEC_CHECK_INFO)) 303 304/* Grow to a specific length. 305 void VEC_T_A_safe_grow (VEC(T,A) *&v, int len); 306 307 Grow the vector to a specific length. The LEN must be as 308 long or longer than the current length. The new elements are 309 uninitialized. */ 310 311#define VEC_safe_grow(T,A,V,I) \ 312 (VEC_OP(T,A,safe_grow)(&(V),I VEC_CHECK_INFO MEM_STAT_INFO)) 313 314/* Grow to a specific length. 315 void VEC_T_A_safe_grow_cleared (VEC(T,A) *&v, int len); 316 317 Grow the vector to a specific length. The LEN must be as 318 long or longer than the current length. The new elements are 319 initialized to zero. */ 320 321#define VEC_safe_grow_cleared(T,A,V,I) \ 322 (VEC_OP(T,A,safe_grow_cleared)(&(V),I VEC_CHECK_INFO MEM_STAT_INFO)) 323 324/* Replace element 325 T VEC_T_replace (VEC(T) *v, unsigned ix, T val); // Integer 326 T VEC_T_replace (VEC(T) *v, unsigned ix, T val); // Pointer 327 T *VEC_T_replace (VEC(T) *v, unsigned ix, T *val); // Object 328 329 Replace the IXth element of V with a new value, VAL. For pointer 330 vectors returns the original value. For object vectors returns a 331 pointer to the new value. For object vectors the new value can be 332 NULL, in which case no overwriting of the slot is actually 333 performed. */ 334 335#define VEC_replace(T,V,I,O) \ 336 (VEC_OP(T,base,replace)(VEC_BASE(V),I,O VEC_CHECK_INFO)) 337 338/* Insert object with no reallocation 339 T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Integer 340 T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Pointer 341 T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T *val); // Object 342 343 Insert an element, VAL, at the IXth position of V. Return a pointer 344 to the slot created. For vectors of object, the new value can be 345 NULL, in which case no initialization of the inserted slot takes 346 place. There must be sufficient space. */ 347 348#define VEC_quick_insert(T,V,I,O) \ 349 (VEC_OP(T,base,quick_insert)(VEC_BASE(V),I,O VEC_CHECK_INFO)) 350 351/* Insert object with reallocation 352 T *VEC_T_A_safe_insert (VEC(T,A) *&v, unsigned ix, T val); // Integer 353 T *VEC_T_A_safe_insert (VEC(T,A) *&v, unsigned ix, T val); // Pointer 354 T *VEC_T_A_safe_insert (VEC(T,A) *&v, unsigned ix, T *val); // Object 355 356 Insert an element, VAL, at the IXth position of V. Return a pointer 357 to the slot created. For vectors of object, the new value can be 358 NULL, in which case no initialization of the inserted slot takes 359 place. Reallocate V, if necessary. */ 360 361#define VEC_safe_insert(T,A,V,I,O) \ 362 (VEC_OP(T,A,safe_insert)(&(V),I,O VEC_CHECK_INFO MEM_STAT_INFO)) 363 364/* Remove element retaining order 365 T VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Integer 366 T VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Pointer 367 void VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Object 368 369 Remove an element from the IXth position of V. Ordering of 370 remaining elements is preserved. For pointer vectors returns the 371 removed object. This is an O(N) operation due to a memmove. */ 372 373#define VEC_ordered_remove(T,V,I) \ 374 (VEC_OP(T,base,ordered_remove)(VEC_BASE(V),I VEC_CHECK_INFO)) 375 376/* Remove element destroying order 377 T VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Integer 378 T VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Pointer 379 void VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Object 380 381 Remove an element from the IXth position of V. Ordering of 382 remaining elements is destroyed. For pointer vectors returns the 383 removed object. This is an O(1) operation. */ 384 385#define VEC_unordered_remove(T,V,I) \ 386 (VEC_OP(T,base,unordered_remove)(VEC_BASE(V),I VEC_CHECK_INFO)) 387 388/* Remove a block of elements 389 void VEC_T_block_remove (VEC(T) *v, unsigned ix, unsigned len); 390 391 Remove LEN elements starting at the IXth. Ordering is retained. 392 This is an O(1) operation. */ 393 394#define VEC_block_remove(T,V,I,L) \ 395 (VEC_OP(T,base,block_remove)(VEC_BASE(V),I,L VEC_CHECK_INFO)) 396 397/* Get the address of the array of elements 398 T *VEC_T_address (VEC(T) v) 399 400 If you need to directly manipulate the array (for instance, you 401 want to feed it to qsort), use this accessor. */ 402 403#define VEC_address(T,V) (VEC_OP(T,base,address)(VEC_BASE(V))) 404 405/* Find the first index in the vector not less than the object. 406 unsigned VEC_T_lower_bound (VEC(T) *v, const T val, 407 bool (*lessthan) (const T, const T)); // Integer 408 unsigned VEC_T_lower_bound (VEC(T) *v, const T val, 409 bool (*lessthan) (const T, const T)); // Pointer 410 unsigned VEC_T_lower_bound (VEC(T) *v, const T *val, 411 bool (*lessthan) (const T*, const T*)); // Object 412 413 Find the first position in which VAL could be inserted without 414 changing the ordering of V. LESSTHAN is a function that returns 415 true if the first argument is strictly less than the second. */ 416 417#define VEC_lower_bound(T,V,O,LT) \ 418 (VEC_OP(T,base,lower_bound)(VEC_BASE(V),O,LT VEC_CHECK_INFO)) 419 420/* Reallocate an array of elements with prefix. */ 421extern void *vec_gc_p_reserve (void *, int MEM_STAT_DECL); 422extern void *vec_gc_p_reserve_exact (void *, int MEM_STAT_DECL); 423extern void *vec_gc_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL); 424extern void *vec_gc_o_reserve_exact (void *, int, size_t, size_t 425 MEM_STAT_DECL); 426extern void ggc_free (void *); 427#define vec_gc_free(V) ggc_free (V) 428extern void *vec_heap_p_reserve (void *, int MEM_STAT_DECL); 429extern void *vec_heap_p_reserve_exact (void *, int MEM_STAT_DECL); 430extern void *vec_heap_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL); 431extern void *vec_heap_o_reserve_exact (void *, int, size_t, size_t 432 MEM_STAT_DECL); 433extern void dump_vec_loc_statistics (void); 434#ifdef GATHER_STATISTICS 435void vec_heap_free (void *); 436#else 437#define vec_heap_free(V) free (V) 438#endif 439 440#if ENABLE_CHECKING 441#define VEC_CHECK_INFO ,__FILE__,__LINE__,__FUNCTION__ 442#define VEC_CHECK_DECL ,const char *file_,unsigned line_,const char *function_ 443#define VEC_CHECK_PASS ,file_,line_,function_ 444 445#define VEC_ASSERT(EXPR,OP,T,A) \ 446 (void)((EXPR) ? 0 : (VEC_ASSERT_FAIL(OP,VEC(T,A)), 0)) 447 448extern void vec_assert_fail (const char *, const char * VEC_CHECK_DECL) 449 ATTRIBUTE_NORETURN; 450#define VEC_ASSERT_FAIL(OP,VEC) vec_assert_fail (OP,#VEC VEC_CHECK_PASS) 451#else 452#define VEC_CHECK_INFO 453#define VEC_CHECK_DECL 454#define VEC_CHECK_PASS 455#define VEC_ASSERT(EXPR,OP,T,A) (void)(EXPR) 456#endif 457 458/* Note: gengtype has hardwired knowledge of the expansions of the 459 VEC, DEF_VEC_*, and DEF_VEC_ALLOC_* macros. If you change the 460 expansions of these macros you may need to change gengtype too. */ 461 462#define VEC(T,A) VEC_##T##_##A 463#define VEC_OP(T,A,OP) VEC_##T##_##A##_##OP 464 465/* Base of vector type, not user visible. */ 466#define VEC_T(T,B) \ 467typedef struct VEC(T,B) \ 468{ \ 469 unsigned num; \ 470 unsigned alloc; \ 471 T vec[1]; \ 472} VEC(T,B) 473 474#define VEC_T_GTY(T,B) \ 475typedef struct GTY(()) VEC(T,B) \ 476{ \ 477 unsigned num; \ 478 unsigned alloc; \ 479 T GTY ((length ("%h.num"))) vec[1]; \ 480} VEC(T,B) 481 482/* Derived vector type, user visible. */ 483#define VEC_TA_GTY(T,B,A,GTY) \ 484typedef struct GTY VEC(T,A) \ 485{ \ 486 VEC(T,B) base; \ 487} VEC(T,A) 488 489#define VEC_TA(T,B,A) \ 490typedef struct VEC(T,A) \ 491{ \ 492 VEC(T,B) base; \ 493} VEC(T,A) 494 495/* Convert to base type. */ 496#define VEC_BASE(P) ((P) ? &(P)->base : 0) 497 498/* Vector of integer-like object. */ 499#define DEF_VEC_I(T) \ 500static inline void VEC_OP (T,must_be,integral_type) (void) \ 501{ \ 502 (void)~(T)0; \ 503} \ 504 \ 505VEC_T(T,base); \ 506VEC_TA(T,base,none); \ 507DEF_VEC_FUNC_P(T) \ 508struct vec_swallow_trailing_semi 509#define DEF_VEC_ALLOC_I(T,A) \ 510VEC_TA(T,base,A); \ 511DEF_VEC_ALLOC_FUNC_I(T,A) \ 512DEF_VEC_NONALLOC_FUNCS_I(T,A) \ 513struct vec_swallow_trailing_semi 514 515/* Vector of pointer to object. */ 516#define DEF_VEC_P(T) \ 517static inline void VEC_OP (T,must_be,pointer_type) (void) \ 518{ \ 519 (void)((T)1 == (void *)1); \ 520} \ 521 \ 522VEC_T_GTY(T,base); \ 523VEC_TA(T,base,none); \ 524DEF_VEC_FUNC_P(T) \ 525struct vec_swallow_trailing_semi 526#define DEF_VEC_ALLOC_P(T,A) \ 527VEC_TA(T,base,A); \ 528DEF_VEC_ALLOC_FUNC_P(T,A) \ 529DEF_VEC_NONALLOC_FUNCS_P(T,A) \ 530struct vec_swallow_trailing_semi 531 532#define DEF_VEC_FUNC_P(T) \ 533static inline unsigned VEC_OP (T,base,length) (const VEC(T,base) *vec_) \ 534{ \ 535 return vec_ ? vec_->num : 0; \ 536} \ 537 \ 538static inline T VEC_OP (T,base,last) \ 539 (const VEC(T,base) *vec_ VEC_CHECK_DECL) \ 540{ \ 541 VEC_ASSERT (vec_ && vec_->num, "last", T, base); \ 542 \ 543 return vec_->vec[vec_->num - 1]; \ 544} \ 545 \ 546static inline T VEC_OP (T,base,index) \ 547 (const VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \ 548{ \ 549 VEC_ASSERT (vec_ && ix_ < vec_->num, "index", T, base); \ 550 \ 551 return vec_->vec[ix_]; \ 552} \ 553 \ 554static inline int VEC_OP (T,base,iterate) \ 555 (const VEC(T,base) *vec_, unsigned ix_, T *ptr) \ 556{ \ 557 if (vec_ && ix_ < vec_->num) \ 558 { \ 559 *ptr = vec_->vec[ix_]; \ 560 return 1; \ 561 } \ 562 else \ 563 { \ 564 *ptr = (T) 0; \ 565 return 0; \ 566 } \ 567} \ 568 \ 569static inline size_t VEC_OP (T,base,embedded_size) \ 570 (int alloc_) \ 571{ \ 572 return offsetof (VEC(T,base),vec) + alloc_ * sizeof(T); \ 573} \ 574 \ 575static inline void VEC_OP (T,base,embedded_init) \ 576 (VEC(T,base) *vec_, int alloc_) \ 577{ \ 578 vec_->num = 0; \ 579 vec_->alloc = alloc_; \ 580} \ 581 \ 582static inline int VEC_OP (T,base,space) \ 583 (VEC(T,base) *vec_, int alloc_ VEC_CHECK_DECL) \ 584{ \ 585 VEC_ASSERT (alloc_ >= 0, "space", T, base); \ 586 return vec_ ? vec_->alloc - vec_->num >= (unsigned)alloc_ : !alloc_; \ 587} \ 588 \ 589static inline T *VEC_OP (T,base,quick_push) \ 590 (VEC(T,base) *vec_, T obj_ VEC_CHECK_DECL) \ 591{ \ 592 T *slot_; \ 593 \ 594 VEC_ASSERT (vec_->num < vec_->alloc, "push", T, base); \ 595 slot_ = &vec_->vec[vec_->num++]; \ 596 *slot_ = obj_; \ 597 \ 598 return slot_; \ 599} \ 600 \ 601static inline T VEC_OP (T,base,pop) (VEC(T,base) *vec_ VEC_CHECK_DECL) \ 602{ \ 603 T obj_; \ 604 \ 605 VEC_ASSERT (vec_->num, "pop", T, base); \ 606 obj_ = vec_->vec[--vec_->num]; \ 607 \ 608 return obj_; \ 609} \ 610 \ 611static inline void VEC_OP (T,base,truncate) \ 612 (VEC(T,base) *vec_, unsigned size_ VEC_CHECK_DECL) \ 613{ \ 614 VEC_ASSERT (vec_ ? vec_->num >= size_ : !size_, "truncate", T, base); \ 615 if (vec_) \ 616 vec_->num = size_; \ 617} \ 618 \ 619static inline T VEC_OP (T,base,replace) \ 620 (VEC(T,base) *vec_, unsigned ix_, T obj_ VEC_CHECK_DECL) \ 621{ \ 622 T old_obj_; \ 623 \ 624 VEC_ASSERT (ix_ < vec_->num, "replace", T, base); \ 625 old_obj_ = vec_->vec[ix_]; \ 626 vec_->vec[ix_] = obj_; \ 627 \ 628 return old_obj_; \ 629} \ 630 \ 631static inline T *VEC_OP (T,base,quick_insert) \ 632 (VEC(T,base) *vec_, unsigned ix_, T obj_ VEC_CHECK_DECL) \ 633{ \ 634 T *slot_; \ 635 \ 636 VEC_ASSERT (vec_->num < vec_->alloc, "insert", T, base); \ 637 VEC_ASSERT (ix_ <= vec_->num, "insert", T, base); \ 638 slot_ = &vec_->vec[ix_]; \ 639 memmove (slot_ + 1, slot_, (vec_->num++ - ix_) * sizeof (T)); \ 640 *slot_ = obj_; \ 641 \ 642 return slot_; \ 643} \ 644 \ 645static inline T VEC_OP (T,base,ordered_remove) \ 646 (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \ 647{ \ 648 T *slot_; \ 649 T obj_; \ 650 \ 651 VEC_ASSERT (ix_ < vec_->num, "remove", T, base); \ 652 slot_ = &vec_->vec[ix_]; \ 653 obj_ = *slot_; \ 654 memmove (slot_, slot_ + 1, (--vec_->num - ix_) * sizeof (T)); \ 655 \ 656 return obj_; \ 657} \ 658 \ 659static inline T VEC_OP (T,base,unordered_remove) \ 660 (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \ 661{ \ 662 T *slot_; \ 663 T obj_; \ 664 \ 665 VEC_ASSERT (ix_ < vec_->num, "remove", T, base); \ 666 slot_ = &vec_->vec[ix_]; \ 667 obj_ = *slot_; \ 668 *slot_ = vec_->vec[--vec_->num]; \ 669 \ 670 return obj_; \ 671} \ 672 \ 673static inline void VEC_OP (T,base,block_remove) \ 674 (VEC(T,base) *vec_, unsigned ix_, unsigned len_ VEC_CHECK_DECL) \ 675{ \ 676 T *slot_; \ 677 \ 678 VEC_ASSERT (ix_ + len_ <= vec_->num, "block_remove", T, base); \ 679 slot_ = &vec_->vec[ix_]; \ 680 vec_->num -= len_; \ 681 memmove (slot_, slot_ + len_, (vec_->num - ix_) * sizeof (T)); \ 682} \ 683 \ 684static inline T *VEC_OP (T,base,address) \ 685 (VEC(T,base) *vec_) \ 686{ \ 687 return vec_ ? vec_->vec : 0; \ 688} \ 689 \ 690static inline unsigned VEC_OP (T,base,lower_bound) \ 691 (VEC(T,base) *vec_, const T obj_, \ 692 bool (*lessthan_)(const T, const T) VEC_CHECK_DECL) \ 693{ \ 694 unsigned int len_ = VEC_OP (T,base, length) (vec_); \ 695 unsigned int half_, middle_; \ 696 unsigned int first_ = 0; \ 697 while (len_ > 0) \ 698 { \ 699 T middle_elem_; \ 700 half_ = len_ >> 1; \ 701 middle_ = first_; \ 702 middle_ += half_; \ 703 middle_elem_ = VEC_OP (T,base,index) (vec_, middle_ VEC_CHECK_PASS); \ 704 if (lessthan_ (middle_elem_, obj_)) \ 705 { \ 706 first_ = middle_; \ 707 ++first_; \ 708 len_ = len_ - half_ - 1; \ 709 } \ 710 else \ 711 len_ = half_; \ 712 } \ 713 return first_; \ 714} 715 716#define DEF_VEC_ALLOC_FUNC_P(T,A) \ 717static inline VEC(T,A) *VEC_OP (T,A,alloc) \ 718 (int alloc_ MEM_STAT_DECL) \ 719{ \ 720 return (VEC(T,A) *) vec_##A##_p_reserve_exact (NULL, alloc_ \ 721 PASS_MEM_STAT); \ 722} 723 724 725#define DEF_VEC_NONALLOC_FUNCS_P(T,A) \ 726static inline void VEC_OP (T,A,free) \ 727 (VEC(T,A) **vec_) \ 728{ \ 729 if (*vec_) \ 730 vec_##A##_free (*vec_); \ 731 *vec_ = NULL; \ 732} \ 733 \ 734static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \ 735{ \ 736 size_t len_ = vec_ ? vec_->num : 0; \ 737 VEC (T,A) *new_vec_ = NULL; \ 738 \ 739 if (len_) \ 740 { \ 741 new_vec_ = (VEC (T,A) *)(vec_##A##_p_reserve_exact \ 742 (NULL, len_ PASS_MEM_STAT)); \ 743 \ 744 new_vec_->base.num = len_; \ 745 memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_); \ 746 } \ 747 return new_vec_; \ 748} \ 749 \ 750static inline int VEC_OP (T,A,reserve) \ 751 (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \ 752{ \ 753 int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \ 754 VEC_CHECK_PASS); \ 755 \ 756 if (extend) \ 757 *vec_ = (VEC(T,A) *) vec_##A##_p_reserve (*vec_, alloc_ PASS_MEM_STAT); \ 758 \ 759 return extend; \ 760} \ 761 \ 762static inline int VEC_OP (T,A,reserve_exact) \ 763 (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \ 764{ \ 765 int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \ 766 VEC_CHECK_PASS); \ 767 \ 768 if (extend) \ 769 *vec_ = (VEC(T,A) *) vec_##A##_p_reserve_exact (*vec_, alloc_ \ 770 PASS_MEM_STAT); \ 771 \ 772 return extend; \ 773} \ 774 \ 775static inline void VEC_OP (T,A,safe_grow) \ 776 (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \ 777{ \ 778 VEC_ASSERT (size_ >= 0 \ 779 && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \ 780 "grow", T, A); \ 781 VEC_OP (T,A,reserve_exact) (vec_, \ 782 size_ - (int)(*vec_ ? VEC_BASE(*vec_)->num : 0) \ 783 VEC_CHECK_PASS PASS_MEM_STAT); \ 784 VEC_BASE (*vec_)->num = size_; \ 785} \ 786 \ 787static inline void VEC_OP (T,A,safe_grow_cleared) \ 788 (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \ 789{ \ 790 int oldsize = VEC_OP(T,base,length) VEC_BASE(*vec_); \ 791 VEC_OP (T,A,safe_grow) (vec_, size_ VEC_CHECK_PASS PASS_MEM_STAT); \ 792 memset (&(VEC_OP (T,base,address) VEC_BASE(*vec_))[oldsize], 0, \ 793 sizeof (T) * (size_ - oldsize)); \ 794} \ 795 \ 796static inline T *VEC_OP (T,A,safe_push) \ 797 (VEC(T,A) **vec_, T obj_ VEC_CHECK_DECL MEM_STAT_DECL) \ 798{ \ 799 VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \ 800 \ 801 return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS); \ 802} \ 803 \ 804static inline T *VEC_OP (T,A,safe_insert) \ 805 (VEC(T,A) **vec_, unsigned ix_, T obj_ VEC_CHECK_DECL MEM_STAT_DECL) \ 806{ \ 807 VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \ 808 \ 809 return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_ \ 810 VEC_CHECK_PASS); \ 811} 812 813/* Vector of object. */ 814#define DEF_VEC_O(T) \ 815VEC_T_GTY(T,base); \ 816VEC_TA(T,base,none); \ 817DEF_VEC_FUNC_O(T) \ 818struct vec_swallow_trailing_semi 819#define DEF_VEC_ALLOC_O(T,A) \ 820VEC_TA(T,base,A); \ 821DEF_VEC_ALLOC_FUNC_O(T,A) \ 822DEF_VEC_NONALLOC_FUNCS_O(T,A) \ 823struct vec_swallow_trailing_semi 824 825#define DEF_VEC_FUNC_O(T) \ 826static inline unsigned VEC_OP (T,base,length) (const VEC(T,base) *vec_) \ 827{ \ 828 return vec_ ? vec_->num : 0; \ 829} \ 830 \ 831static inline T *VEC_OP (T,base,last) (VEC(T,base) *vec_ VEC_CHECK_DECL) \ 832{ \ 833 VEC_ASSERT (vec_ && vec_->num, "last", T, base); \ 834 \ 835 return &vec_->vec[vec_->num - 1]; \ 836} \ 837 \ 838static inline T *VEC_OP (T,base,index) \ 839 (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \ 840{ \ 841 VEC_ASSERT (vec_ && ix_ < vec_->num, "index", T, base); \ 842 \ 843 return &vec_->vec[ix_]; \ 844} \ 845 \ 846static inline int VEC_OP (T,base,iterate) \ 847 (VEC(T,base) *vec_, unsigned ix_, T **ptr) \ 848{ \ 849 if (vec_ && ix_ < vec_->num) \ 850 { \ 851 *ptr = &vec_->vec[ix_]; \ 852 return 1; \ 853 } \ 854 else \ 855 { \ 856 *ptr = 0; \ 857 return 0; \ 858 } \ 859} \ 860 \ 861static inline size_t VEC_OP (T,base,embedded_size) \ 862 (int alloc_) \ 863{ \ 864 return offsetof (VEC(T,base),vec) + alloc_ * sizeof(T); \ 865} \ 866 \ 867static inline void VEC_OP (T,base,embedded_init) \ 868 (VEC(T,base) *vec_, int alloc_) \ 869{ \ 870 vec_->num = 0; \ 871 vec_->alloc = alloc_; \ 872} \ 873 \ 874static inline int VEC_OP (T,base,space) \ 875 (VEC(T,base) *vec_, int alloc_ VEC_CHECK_DECL) \ 876{ \ 877 VEC_ASSERT (alloc_ >= 0, "space", T, base); \ 878 return vec_ ? vec_->alloc - vec_->num >= (unsigned)alloc_ : !alloc_; \ 879} \ 880 \ 881static inline T *VEC_OP (T,base,quick_push) \ 882 (VEC(T,base) *vec_, const T *obj_ VEC_CHECK_DECL) \ 883{ \ 884 T *slot_; \ 885 \ 886 VEC_ASSERT (vec_->num < vec_->alloc, "push", T, base); \ 887 slot_ = &vec_->vec[vec_->num++]; \ 888 if (obj_) \ 889 *slot_ = *obj_; \ 890 \ 891 return slot_; \ 892} \ 893 \ 894static inline void VEC_OP (T,base,pop) (VEC(T,base) *vec_ VEC_CHECK_DECL) \ 895{ \ 896 VEC_ASSERT (vec_->num, "pop", T, base); \ 897 --vec_->num; \ 898} \ 899 \ 900static inline void VEC_OP (T,base,truncate) \ 901 (VEC(T,base) *vec_, unsigned size_ VEC_CHECK_DECL) \ 902{ \ 903 VEC_ASSERT (vec_ ? vec_->num >= size_ : !size_, "truncate", T, base); \ 904 if (vec_) \ 905 vec_->num = size_; \ 906} \ 907 \ 908static inline T *VEC_OP (T,base,replace) \ 909 (VEC(T,base) *vec_, unsigned ix_, const T *obj_ VEC_CHECK_DECL) \ 910{ \ 911 T *slot_; \ 912 \ 913 VEC_ASSERT (ix_ < vec_->num, "replace", T, base); \ 914 slot_ = &vec_->vec[ix_]; \ 915 if (obj_) \ 916 *slot_ = *obj_; \ 917 \ 918 return slot_; \ 919} \ 920 \ 921static inline T *VEC_OP (T,base,quick_insert) \ 922 (VEC(T,base) *vec_, unsigned ix_, const T *obj_ VEC_CHECK_DECL) \ 923{ \ 924 T *slot_; \ 925 \ 926 VEC_ASSERT (vec_->num < vec_->alloc, "insert", T, base); \ 927 VEC_ASSERT (ix_ <= vec_->num, "insert", T, base); \ 928 slot_ = &vec_->vec[ix_]; \ 929 memmove (slot_ + 1, slot_, (vec_->num++ - ix_) * sizeof (T)); \ 930 if (obj_) \ 931 *slot_ = *obj_; \ 932 \ 933 return slot_; \ 934} \ 935 \ 936static inline void VEC_OP (T,base,ordered_remove) \ 937 (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \ 938{ \ 939 T *slot_; \ 940 \ 941 VEC_ASSERT (ix_ < vec_->num, "remove", T, base); \ 942 slot_ = &vec_->vec[ix_]; \ 943 memmove (slot_, slot_ + 1, (--vec_->num - ix_) * sizeof (T)); \ 944} \ 945 \ 946static inline void VEC_OP (T,base,unordered_remove) \ 947 (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \ 948{ \ 949 VEC_ASSERT (ix_ < vec_->num, "remove", T, base); \ 950 vec_->vec[ix_] = vec_->vec[--vec_->num]; \ 951} \ 952 \ 953static inline void VEC_OP (T,base,block_remove) \ 954 (VEC(T,base) *vec_, unsigned ix_, unsigned len_ VEC_CHECK_DECL) \ 955{ \ 956 T *slot_; \ 957 \ 958 VEC_ASSERT (ix_ + len_ <= vec_->num, "block_remove", T, base); \ 959 slot_ = &vec_->vec[ix_]; \ 960 vec_->num -= len_; \ 961 memmove (slot_, slot_ + len_, (vec_->num - ix_) * sizeof (T)); \ 962} \ 963 \ 964static inline T *VEC_OP (T,base,address) \ 965 (VEC(T,base) *vec_) \ 966{ \ 967 return vec_ ? vec_->vec : 0; \ 968} \ 969 \ 970static inline unsigned VEC_OP (T,base,lower_bound) \ 971 (VEC(T,base) *vec_, const T *obj_, \ 972 bool (*lessthan_)(const T *, const T *) VEC_CHECK_DECL) \ 973{ \ 974 unsigned int len_ = VEC_OP (T, base, length) (vec_); \ 975 unsigned int half_, middle_; \ 976 unsigned int first_ = 0; \ 977 while (len_ > 0) \ 978 { \ 979 T *middle_elem_; \ 980 half_ = len_ >> 1; \ 981 middle_ = first_; \ 982 middle_ += half_; \ 983 middle_elem_ = VEC_OP (T,base,index) (vec_, middle_ VEC_CHECK_PASS); \ 984 if (lessthan_ (middle_elem_, obj_)) \ 985 { \ 986 first_ = middle_; \ 987 ++first_; \ 988 len_ = len_ - half_ - 1; \ 989 } \ 990 else \ 991 len_ = half_; \ 992 } \ 993 return first_; \ 994} 995 996#define DEF_VEC_ALLOC_FUNC_O(T,A) \ 997static inline VEC(T,A) *VEC_OP (T,A,alloc) \ 998 (int alloc_ MEM_STAT_DECL) \ 999{ \ 1000 return (VEC(T,A) *) vec_##A##_o_reserve_exact (NULL, alloc_, \ 1001 offsetof (VEC(T,A),base.vec), \ 1002 sizeof (T) \ 1003 PASS_MEM_STAT); \ 1004} 1005 1006#define DEF_VEC_NONALLOC_FUNCS_O(T,A) \ 1007static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \ 1008{ \ 1009 size_t len_ = vec_ ? vec_->num : 0; \ 1010 VEC (T,A) *new_vec_ = NULL; \ 1011 \ 1012 if (len_) \ 1013 { \ 1014 new_vec_ = (VEC (T,A) *)(vec_##A##_o_reserve_exact \ 1015 (NULL, len_, \ 1016 offsetof (VEC(T,A),base.vec), sizeof (T) \ 1017 PASS_MEM_STAT)); \ 1018 \ 1019 new_vec_->base.num = len_; \ 1020 memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_); \ 1021 } \ 1022 return new_vec_; \ 1023} \ 1024 \ 1025static inline void VEC_OP (T,A,free) \ 1026 (VEC(T,A) **vec_) \ 1027{ \ 1028 if (*vec_) \ 1029 vec_##A##_free (*vec_); \ 1030 *vec_ = NULL; \ 1031} \ 1032 \ 1033static inline int VEC_OP (T,A,reserve) \ 1034 (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \ 1035{ \ 1036 int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \ 1037 VEC_CHECK_PASS); \ 1038 \ 1039 if (extend) \ 1040 *vec_ = (VEC(T,A) *) vec_##A##_o_reserve (*vec_, alloc_, \ 1041 offsetof (VEC(T,A),base.vec),\ 1042 sizeof (T) \ 1043 PASS_MEM_STAT); \ 1044 \ 1045 return extend; \ 1046} \ 1047 \ 1048static inline int VEC_OP (T,A,reserve_exact) \ 1049 (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \ 1050{ \ 1051 int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \ 1052 VEC_CHECK_PASS); \ 1053 \ 1054 if (extend) \ 1055 *vec_ = (VEC(T,A) *) vec_##A##_o_reserve_exact \ 1056 (*vec_, alloc_, \ 1057 offsetof (VEC(T,A),base.vec), \ 1058 sizeof (T) PASS_MEM_STAT); \ 1059 \ 1060 return extend; \ 1061} \ 1062 \ 1063static inline void VEC_OP (T,A,safe_grow) \ 1064 (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \ 1065{ \ 1066 VEC_ASSERT (size_ >= 0 \ 1067 && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \ 1068 "grow", T, A); \ 1069 VEC_OP (T,A,reserve_exact) (vec_, \ 1070 size_ - (int)(*vec_ ? VEC_BASE(*vec_)->num : 0) \ 1071 VEC_CHECK_PASS PASS_MEM_STAT); \ 1072 VEC_BASE (*vec_)->num = size_; \ 1073} \ 1074 \ 1075static inline void VEC_OP (T,A,safe_grow_cleared) \ 1076 (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \ 1077{ \ 1078 int oldsize = VEC_OP(T,base,length) VEC_BASE(*vec_); \ 1079 VEC_OP (T,A,safe_grow) (vec_, size_ VEC_CHECK_PASS PASS_MEM_STAT); \ 1080 memset (&(VEC_OP (T,base,address) VEC_BASE(*vec_))[oldsize], 0, \ 1081 sizeof (T) * (size_ - oldsize)); \ 1082} \ 1083 \ 1084static inline T *VEC_OP (T,A,safe_push) \ 1085 (VEC(T,A) **vec_, const T *obj_ VEC_CHECK_DECL MEM_STAT_DECL) \ 1086{ \ 1087 VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \ 1088 \ 1089 return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS); \ 1090} \ 1091 \ 1092static inline T *VEC_OP (T,A,safe_insert) \ 1093 (VEC(T,A) **vec_, unsigned ix_, const T *obj_ \ 1094 VEC_CHECK_DECL MEM_STAT_DECL) \ 1095{ \ 1096 VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \ 1097 \ 1098 return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_ \ 1099 VEC_CHECK_PASS); \ 1100} 1101 1102#define DEF_VEC_ALLOC_FUNC_I(T,A) \ 1103static inline VEC(T,A) *VEC_OP (T,A,alloc) \ 1104 (int alloc_ MEM_STAT_DECL) \ 1105{ \ 1106 return (VEC(T,A) *) vec_##A##_o_reserve_exact \ 1107 (NULL, alloc_, offsetof (VEC(T,A),base.vec), \ 1108 sizeof (T) PASS_MEM_STAT); \ 1109} 1110 1111#define DEF_VEC_NONALLOC_FUNCS_I(T,A) \ 1112static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \ 1113{ \ 1114 size_t len_ = vec_ ? vec_->num : 0; \ 1115 VEC (T,A) *new_vec_ = NULL; \ 1116 \ 1117 if (len_) \ 1118 { \ 1119 new_vec_ = (VEC (T,A) *)(vec_##A##_o_reserve_exact \ 1120 (NULL, len_, \ 1121 offsetof (VEC(T,A),base.vec), sizeof (T) \ 1122 PASS_MEM_STAT)); \ 1123 \ 1124 new_vec_->base.num = len_; \ 1125 memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_); \ 1126 } \ 1127 return new_vec_; \ 1128} \ 1129 \ 1130static inline void VEC_OP (T,A,free) \ 1131 (VEC(T,A) **vec_) \ 1132{ \ 1133 if (*vec_) \ 1134 vec_##A##_free (*vec_); \ 1135 *vec_ = NULL; \ 1136} \ 1137 \ 1138static inline int VEC_OP (T,A,reserve) \ 1139 (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \ 1140{ \ 1141 int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \ 1142 VEC_CHECK_PASS); \ 1143 \ 1144 if (extend) \ 1145 *vec_ = (VEC(T,A) *) vec_##A##_o_reserve (*vec_, alloc_, \ 1146 offsetof (VEC(T,A),base.vec),\ 1147 sizeof (T) \ 1148 PASS_MEM_STAT); \ 1149 \ 1150 return extend; \ 1151} \ 1152 \ 1153static inline int VEC_OP (T,A,reserve_exact) \ 1154 (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \ 1155{ \ 1156 int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), alloc_ \ 1157 VEC_CHECK_PASS); \ 1158 \ 1159 if (extend) \ 1160 *vec_ = (VEC(T,A) *) vec_##A##_o_reserve_exact \ 1161 (*vec_, alloc_, offsetof (VEC(T,A),base.vec), \ 1162 sizeof (T) PASS_MEM_STAT); \ 1163 \ 1164 return extend; \ 1165} \ 1166 \ 1167static inline void VEC_OP (T,A,safe_grow) \ 1168 (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \ 1169{ \ 1170 VEC_ASSERT (size_ >= 0 \ 1171 && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \ 1172 "grow", T, A); \ 1173 VEC_OP (T,A,reserve_exact) (vec_, \ 1174 size_ - (int)(*vec_ ? VEC_BASE(*vec_)->num : 0) \ 1175 VEC_CHECK_PASS PASS_MEM_STAT); \ 1176 VEC_BASE (*vec_)->num = size_; \ 1177} \ 1178 \ 1179static inline void VEC_OP (T,A,safe_grow_cleared) \ 1180 (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \ 1181{ \ 1182 int oldsize = VEC_OP(T,base,length) VEC_BASE(*vec_); \ 1183 VEC_OP (T,A,safe_grow) (vec_, size_ VEC_CHECK_PASS PASS_MEM_STAT); \ 1184 memset (&(VEC_OP (T,base,address) VEC_BASE(*vec_))[oldsize], 0, \ 1185 sizeof (T) * (size_ - oldsize)); \ 1186} \ 1187 \ 1188static inline T *VEC_OP (T,A,safe_push) \ 1189 (VEC(T,A) **vec_, const T obj_ VEC_CHECK_DECL MEM_STAT_DECL) \ 1190{ \ 1191 VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \ 1192 \ 1193 return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS); \ 1194} \ 1195 \ 1196static inline T *VEC_OP (T,A,safe_insert) \ 1197 (VEC(T,A) **vec_, unsigned ix_, const T obj_ \ 1198 VEC_CHECK_DECL MEM_STAT_DECL) \ 1199{ \ 1200 VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \ 1201 \ 1202 return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_ \ 1203 VEC_CHECK_PASS); \ 1204} 1205 1206/* We support a vector which starts out with space on the stack and 1207 switches to heap space when forced to reallocate. This works a 1208 little differently. Instead of DEF_VEC_ALLOC_P(TYPE, heap|gc), use 1209 DEF_VEC_ALLOC_P_STACK(TYPE). This uses alloca to get the initial 1210 space; because alloca can not be usefully called in an inline 1211 function, and because a macro can not define a macro, you must then 1212 write a #define for each type: 1213 1214 #define VEC_{TYPE}_stack_alloc(alloc) \ 1215 VEC_stack_alloc({TYPE}, alloc) 1216 1217 This is really a hack and perhaps can be made better. Note that 1218 this macro will wind up evaluating the ALLOC parameter twice. 1219 1220 Only the initial allocation will be made using alloca, so pass a 1221 reasonable estimate that doesn't use too much stack space; don't 1222 pass zero. Don't return a VEC(TYPE,stack) vector from the function 1223 which allocated it. */ 1224 1225extern void *vec_stack_p_reserve (void *, int MEM_STAT_DECL); 1226extern void *vec_stack_p_reserve_exact (void *, int MEM_STAT_DECL); 1227extern void *vec_stack_p_reserve_exact_1 (int, void *); 1228extern void *vec_stack_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL); 1229extern void *vec_stack_o_reserve_exact (void *, int, size_t, size_t 1230 MEM_STAT_DECL); 1231extern void vec_stack_free (void *); 1232 1233#ifdef GATHER_STATISTICS 1234#define VEC_stack_alloc(T,alloc,name,line,function) \ 1235 (VEC_OP (T,stack,alloc1) \ 1236 (alloc, XALLOCAVAR (VEC(T,stack), VEC_embedded_size (T, alloc)))) 1237#else 1238#define VEC_stack_alloc(T,alloc) \ 1239 (VEC_OP (T,stack,alloc1) \ 1240 (alloc, XALLOCAVAR (VEC(T,stack), VEC_embedded_size (T, alloc)))) 1241#endif 1242 1243#define DEF_VEC_ALLOC_P_STACK(T) \ 1244VEC_TA(T,base,stack); \ 1245DEF_VEC_ALLOC_FUNC_P_STACK(T) \ 1246DEF_VEC_NONALLOC_FUNCS_P(T,stack) \ 1247struct vec_swallow_trailing_semi 1248 1249#define DEF_VEC_ALLOC_FUNC_P_STACK(T) \ 1250static inline VEC(T,stack) *VEC_OP (T,stack,alloc1) \ 1251 (int alloc_, VEC(T,stack)* space) \ 1252{ \ 1253 return (VEC(T,stack) *) vec_stack_p_reserve_exact_1 (alloc_, space); \ 1254} 1255 1256#define DEF_VEC_ALLOC_O_STACK(T) \ 1257VEC_TA(T,base,stack); \ 1258DEF_VEC_ALLOC_FUNC_O_STACK(T) \ 1259DEF_VEC_NONALLOC_FUNCS_O(T,stack) \ 1260struct vec_swallow_trailing_semi 1261 1262#define DEF_VEC_ALLOC_FUNC_O_STACK(T) \ 1263static inline VEC(T,stack) *VEC_OP (T,stack,alloc1) \ 1264 (int alloc_, VEC(T,stack)* space) \ 1265{ \ 1266 return (VEC(T,stack) *) vec_stack_p_reserve_exact_1 (alloc_, space); \ 1267} 1268 1269#define DEF_VEC_ALLOC_I_STACK(T) \ 1270VEC_TA(T,base,stack); \ 1271DEF_VEC_ALLOC_FUNC_I_STACK(T) \ 1272DEF_VEC_NONALLOC_FUNCS_I(T,stack) \ 1273struct vec_swallow_trailing_semi 1274 1275#define DEF_VEC_ALLOC_FUNC_I_STACK(T) \ 1276static inline VEC(T,stack) *VEC_OP (T,stack,alloc1) \ 1277 (int alloc_, VEC(T,stack)* space) \ 1278{ \ 1279 return (VEC(T,stack) *) vec_stack_p_reserve_exact_1 (alloc_, space); \ 1280} 1281 1282#endif /* GCC_VEC_H */ 1283