1/* Vector API for GNU compiler. 2 Copyright (C) 2004, 2005 Free Software Foundation, Inc. 3 Contributed by Nathan Sidwell <nathan@codesourcery.com> 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify it under 8the terms of the GNU General Public License as published by the Free 9Software Foundation; either version 2, or (at your option) any later 10version. 11 12GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13WARRANTY; without even the implied warranty of MERCHANTABILITY or 14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 15for more details. 16 17You should have received a copy of the GNU General Public License 18along with GCC; see the file COPYING. If not, write to the Free 19Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 2002110-1301, USA. */ 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 a 70 negative number for reservation. 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 abs(RESERVE) slots available. The 242 signedness of RESERVE determines the reallocation behavior. A 243 negative value will not create additional headroom beyond that 244 requested. A positive value will create additional headroom. Note 245 this can cause V to be reallocated. Returns nonzero iff 246 reallocation actually occurred. */ 247 248#define VEC_reserve(T,A,V,R) \ 249 (VEC_OP(T,A,reserve)(&(V),R VEC_CHECK_INFO MEM_STAT_INFO)) 250 251/* Push object with no reallocation 252 T *VEC_T_quick_push (VEC(T) *v, T obj); // Integer 253 T *VEC_T_quick_push (VEC(T) *v, T obj); // Pointer 254 T *VEC_T_quick_push (VEC(T) *v, T *obj); // Object 255 256 Push a new element onto the end, returns a pointer to the slot 257 filled in. For object vectors, the new value can be NULL, in which 258 case NO initialization is performed. There must 259 be sufficient space in the vector. */ 260 261#define VEC_quick_push(T,V,O) \ 262 (VEC_OP(T,base,quick_push)(VEC_BASE(V),O VEC_CHECK_INFO)) 263 264/* Push object with reallocation 265 T *VEC_T_A_safe_push (VEC(T,A) *&v, T obj); // Integer 266 T *VEC_T_A_safe_push (VEC(T,A) *&v, T obj); // Pointer 267 T *VEC_T_A_safe_push (VEC(T,A) *&v, T *obj); // Object 268 269 Push a new element onto the end, returns a pointer to the slot 270 filled in. For object vectors, the new value can be NULL, in which 271 case NO initialization is performed. Reallocates V, if needed. */ 272 273#define VEC_safe_push(T,A,V,O) \ 274 (VEC_OP(T,A,safe_push)(&(V),O VEC_CHECK_INFO MEM_STAT_INFO)) 275 276/* Pop element off end 277 T VEC_T_pop (VEC(T) *v); // Integer 278 T VEC_T_pop (VEC(T) *v); // Pointer 279 void VEC_T_pop (VEC(T) *v); // Object 280 281 Pop the last element off the end. Returns the element popped, for 282 pointer vectors. */ 283 284#define VEC_pop(T,V) (VEC_OP(T,base,pop)(VEC_BASE(V) VEC_CHECK_INFO)) 285 286/* Truncate to specific length 287 void VEC_T_truncate (VEC(T) *v, unsigned len); 288 289 Set the length as specified. The new length must be less than or 290 equal to the current length. This is an O(1) operation. */ 291 292#define VEC_truncate(T,V,I) \ 293 (VEC_OP(T,base,truncate)(VEC_BASE(V),I VEC_CHECK_INFO)) 294 295/* Grow to a specific length. 296 void VEC_T_A_safe_grow (VEC(T,A) *&v, int len); 297 298 Grow the vector to a specific length. The LEN must be as 299 long or longer than the current length. The new elements are 300 uninitialized. */ 301 302#define VEC_safe_grow(T,A,V,I) \ 303 (VEC_OP(T,A,safe_grow)(&(V),I VEC_CHECK_INFO MEM_STAT_INFO)) 304 305/* Replace element 306 T VEC_T_replace (VEC(T) *v, unsigned ix, T val); // Integer 307 T VEC_T_replace (VEC(T) *v, unsigned ix, T val); // Pointer 308 T *VEC_T_replace (VEC(T) *v, unsigned ix, T *val); // Object 309 310 Replace the IXth element of V with a new value, VAL. For pointer 311 vectors returns the original value. For object vectors returns a 312 pointer to the new value. For object vectors the new value can be 313 NULL, in which case no overwriting of the slot is actually 314 performed. */ 315 316#define VEC_replace(T,V,I,O) \ 317 (VEC_OP(T,base,replace)(VEC_BASE(V),I,O VEC_CHECK_INFO)) 318 319/* Insert object with no reallocation 320 T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Integer 321 T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T val); // Pointer 322 T *VEC_T_quick_insert (VEC(T) *v, unsigned ix, T *val); // Object 323 324 Insert an element, VAL, at the IXth position of V. Return a pointer 325 to the slot created. For vectors of object, the new value can be 326 NULL, in which case no initialization of the inserted slot takes 327 place. There must be sufficient space. */ 328 329#define VEC_quick_insert(T,V,I,O) \ 330 (VEC_OP(T,base,quick_insert)(VEC_BASE(V),I,O VEC_CHECK_INFO)) 331 332/* Insert object with reallocation 333 T *VEC_T_A_safe_insert (VEC(T,A) *&v, unsigned ix, T val); // Integer 334 T *VEC_T_A_safe_insert (VEC(T,A) *&v, unsigned ix, T val); // Pointer 335 T *VEC_T_A_safe_insert (VEC(T,A) *&v, unsigned ix, T *val); // Object 336 337 Insert an element, VAL, at the IXth position of V. Return a pointer 338 to the slot created. For vectors of object, the new value can be 339 NULL, in which case no initialization of the inserted slot takes 340 place. Reallocate V, if necessary. */ 341 342#define VEC_safe_insert(T,A,V,I,O) \ 343 (VEC_OP(T,A,safe_insert)(&(V),I,O VEC_CHECK_INFO MEM_STAT_INFO)) 344 345/* Remove element retaining order 346 T VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Integer 347 T VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Pointer 348 void VEC_T_ordered_remove (VEC(T) *v, unsigned ix); // Object 349 350 Remove an element from the IXth position of V. Ordering of 351 remaining elements is preserved. For pointer vectors returns the 352 removed object. This is an O(N) operation due to a memmove. */ 353 354#define VEC_ordered_remove(T,V,I) \ 355 (VEC_OP(T,base,ordered_remove)(VEC_BASE(V),I VEC_CHECK_INFO)) 356 357/* Remove element destroying order 358 T VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Integer 359 T VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Pointer 360 void VEC_T_unordered_remove (VEC(T) *v, unsigned ix); // Object 361 362 Remove an element from the IXth position of V. Ordering of 363 remaining elements is destroyed. For pointer vectors returns the 364 removed object. This is an O(1) operation. */ 365 366#define VEC_unordered_remove(T,V,I) \ 367 (VEC_OP(T,base,unordered_remove)(VEC_BASE(V),I VEC_CHECK_INFO)) 368 369/* Get the address of the array of elements 370 T *VEC_T_address (VEC(T) v) 371 372 If you need to directly manipulate the array (for instance, you 373 want to feed it to qsort), use this accessor. */ 374 375#define VEC_address(T,V) (VEC_OP(T,base,address)(VEC_BASE(V))) 376 377/* Find the first index in the vector not less than the object. 378 unsigned VEC_T_lower_bound (VEC(T) *v, const T val, 379 bool (*lessthan) (const T, const T)); // Integer 380 unsigned VEC_T_lower_bound (VEC(T) *v, const T val, 381 bool (*lessthan) (const T, const T)); // Pointer 382 unsigned VEC_T_lower_bound (VEC(T) *v, const T *val, 383 bool (*lessthan) (const T*, const T*)); // Object 384 385 Find the first position in which VAL could be inserted without 386 changing the ordering of V. LESSTHAN is a function that returns 387 true if the first argument is strictly less than the second. */ 388 389#define VEC_lower_bound(T,V,O,LT) \ 390 (VEC_OP(T,base,lower_bound)(VEC_BASE(V),O,LT VEC_CHECK_INFO)) 391 392#if !IN_GENGTYPE 393/* Reallocate an array of elements with prefix. */ 394extern void *vec_gc_p_reserve (void *, int MEM_STAT_DECL); 395extern void *vec_gc_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL); 396extern void ggc_free (void *); 397#define vec_gc_free(V) ggc_free (V) 398extern void *vec_heap_p_reserve (void *, int MEM_STAT_DECL); 399extern void *vec_heap_o_reserve (void *, int, size_t, size_t MEM_STAT_DECL); 400#define vec_heap_free(V) free (V) 401 402#if ENABLE_CHECKING 403#define VEC_CHECK_INFO ,__FILE__,__LINE__,__FUNCTION__ 404#define VEC_CHECK_DECL ,const char *file_,unsigned line_,const char *function_ 405#define VEC_CHECK_PASS ,file_,line_,function_ 406 407#define VEC_ASSERT(EXPR,OP,T,A) \ 408 (void)((EXPR) ? 0 : (VEC_ASSERT_FAIL(OP,VEC(T,A)), 0)) 409 410extern void vec_assert_fail (const char *, const char * VEC_CHECK_DECL) 411 ATTRIBUTE_NORETURN; 412#define VEC_ASSERT_FAIL(OP,VEC) vec_assert_fail (OP,#VEC VEC_CHECK_PASS) 413#else 414#define VEC_CHECK_INFO 415#define VEC_CHECK_DECL 416#define VEC_CHECK_PASS 417#define VEC_ASSERT(EXPR,OP,T,A) (void)(EXPR) 418#endif 419 420#define VEC(T,A) VEC_##T##_##A 421#define VEC_OP(T,A,OP) VEC_##T##_##A##_##OP 422#else /* IN_GENGTYPE */ 423#define VEC(T,A) VEC_ T _ A 424#define VEC_STRINGIFY(X) VEC_STRINGIFY_(X) 425#define VEC_STRINGIFY_(X) #X 426#undef GTY 427#endif /* IN_GENGTYPE */ 428 429/* Base of vector type, not user visible. */ 430#define VEC_T(T,B) \ 431typedef struct VEC(T,B) \ 432{ \ 433 unsigned num; \ 434 unsigned alloc; \ 435 T vec[1]; \ 436} VEC(T,B) 437 438#define VEC_T_GTY(T,B) \ 439typedef struct VEC(T,B) GTY(()) \ 440{ \ 441 unsigned num; \ 442 unsigned alloc; \ 443 T GTY ((length ("%h.num"))) vec[1]; \ 444} VEC(T,B) 445 446/* Derived vector type, user visible. */ 447#define VEC_TA_GTY(T,B,A,GTY) \ 448typedef struct VEC(T,A) GTY \ 449{ \ 450 VEC(T,B) base; \ 451} VEC(T,A) 452 453/* Convert to base type. */ 454#define VEC_BASE(P) ((P) ? &(P)->base : 0) 455 456/* Vector of integer-like object. */ 457#if IN_GENGTYPE 458{"DEF_VEC_I", VEC_STRINGIFY (VEC_T(#0,#1)) ";", "none"}, 459{"DEF_VEC_ALLOC_I", VEC_STRINGIFY (VEC_TA (#0,#1,#2,#3)) ";", NULL}, 460#else 461#define DEF_VEC_I(T) \ 462static inline void VEC_OP (T,must_be,integral_type) (void) \ 463{ \ 464 (void)~(T)0; \ 465} \ 466 \ 467VEC_T(T,base); \ 468VEC_TA_GTY(T,base,none,); \ 469DEF_VEC_FUNC_P(T) \ 470struct vec_swallow_trailing_semi 471#define DEF_VEC_ALLOC_I(T,A) \ 472VEC_TA_GTY(T,base,A,); \ 473DEF_VEC_ALLOC_FUNC_P(T,A) \ 474struct vec_swallow_trailing_semi 475#endif 476 477/* Vector of pointer to object. */ 478#if IN_GENGTYPE 479{"DEF_VEC_P", VEC_STRINGIFY (VEC_T_GTY(#0,#1)) ";", "none"}, 480{"DEF_VEC_ALLOC_P", VEC_STRINGIFY (VEC_TA_GTY (#0,#1,#2,#3)) ";", NULL}, 481#else 482#define DEF_VEC_P(T) \ 483static inline void VEC_OP (T,must_be,pointer_type) (void) \ 484{ \ 485 (void)((T)1 == (void *)1); \ 486} \ 487 \ 488VEC_T_GTY(T,base); \ 489VEC_TA_GTY(T,base,none,); \ 490DEF_VEC_FUNC_P(T) \ 491struct vec_swallow_trailing_semi 492#define DEF_VEC_ALLOC_P(T,A) \ 493VEC_TA_GTY(T,base,A,); \ 494DEF_VEC_ALLOC_FUNC_P(T,A) \ 495struct vec_swallow_trailing_semi 496#endif 497 498#define DEF_VEC_FUNC_P(T) \ 499static inline unsigned VEC_OP (T,base,length) (const VEC(T,base) *vec_) \ 500{ \ 501 return vec_ ? vec_->num : 0; \ 502} \ 503 \ 504static inline T VEC_OP (T,base,last) \ 505 (const VEC(T,base) *vec_ VEC_CHECK_DECL) \ 506{ \ 507 VEC_ASSERT (vec_ && vec_->num, "last", T, base); \ 508 \ 509 return vec_->vec[vec_->num - 1]; \ 510} \ 511 \ 512static inline T VEC_OP (T,base,index) \ 513 (const VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \ 514{ \ 515 VEC_ASSERT (vec_ && ix_ < vec_->num, "index", T, base); \ 516 \ 517 return vec_->vec[ix_]; \ 518} \ 519 \ 520static inline int VEC_OP (T,base,iterate) \ 521 (const VEC(T,base) *vec_, unsigned ix_, T *ptr) \ 522{ \ 523 if (vec_ && ix_ < vec_->num) \ 524 { \ 525 *ptr = vec_->vec[ix_]; \ 526 return 1; \ 527 } \ 528 else \ 529 { \ 530 *ptr = 0; \ 531 return 0; \ 532 } \ 533} \ 534 \ 535static inline size_t VEC_OP (T,base,embedded_size) \ 536 (int alloc_) \ 537{ \ 538 return offsetof (VEC(T,base),vec) + alloc_ * sizeof(T); \ 539} \ 540 \ 541static inline void VEC_OP (T,base,embedded_init) \ 542 (VEC(T,base) *vec_, int alloc_) \ 543{ \ 544 vec_->num = 0; \ 545 vec_->alloc = alloc_; \ 546} \ 547 \ 548static inline int VEC_OP (T,base,space) \ 549 (VEC(T,base) *vec_, int alloc_ VEC_CHECK_DECL) \ 550{ \ 551 VEC_ASSERT (alloc_ >= 0, "space", T, base); \ 552 return vec_ ? vec_->alloc - vec_->num >= (unsigned)alloc_ : !alloc_; \ 553} \ 554 \ 555static inline T *VEC_OP (T,base,quick_push) \ 556 (VEC(T,base) *vec_, T obj_ VEC_CHECK_DECL) \ 557{ \ 558 T *slot_; \ 559 \ 560 VEC_ASSERT (vec_->num < vec_->alloc, "push", T, base); \ 561 slot_ = &vec_->vec[vec_->num++]; \ 562 *slot_ = obj_; \ 563 \ 564 return slot_; \ 565} \ 566 \ 567static inline T VEC_OP (T,base,pop) (VEC(T,base) *vec_ VEC_CHECK_DECL) \ 568{ \ 569 T obj_; \ 570 \ 571 VEC_ASSERT (vec_->num, "pop", T, base); \ 572 obj_ = vec_->vec[--vec_->num]; \ 573 \ 574 return obj_; \ 575} \ 576 \ 577static inline void VEC_OP (T,base,truncate) \ 578 (VEC(T,base) *vec_, unsigned size_ VEC_CHECK_DECL) \ 579{ \ 580 VEC_ASSERT (vec_ ? vec_->num >= size_ : !size_, "truncate", T, base); \ 581 if (vec_) \ 582 vec_->num = size_; \ 583} \ 584 \ 585static inline T VEC_OP (T,base,replace) \ 586 (VEC(T,base) *vec_, unsigned ix_, T obj_ VEC_CHECK_DECL) \ 587{ \ 588 T old_obj_; \ 589 \ 590 VEC_ASSERT (ix_ < vec_->num, "replace", T, base); \ 591 old_obj_ = vec_->vec[ix_]; \ 592 vec_->vec[ix_] = obj_; \ 593 \ 594 return old_obj_; \ 595} \ 596 \ 597static inline T *VEC_OP (T,base,quick_insert) \ 598 (VEC(T,base) *vec_, unsigned ix_, T obj_ VEC_CHECK_DECL) \ 599{ \ 600 T *slot_; \ 601 \ 602 VEC_ASSERT (vec_->num < vec_->alloc, "insert", T, base); \ 603 VEC_ASSERT (ix_ <= vec_->num, "insert", T, base); \ 604 slot_ = &vec_->vec[ix_]; \ 605 memmove (slot_ + 1, slot_, (vec_->num++ - ix_) * sizeof (T)); \ 606 *slot_ = obj_; \ 607 \ 608 return slot_; \ 609} \ 610 \ 611static inline T VEC_OP (T,base,ordered_remove) \ 612 (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \ 613{ \ 614 T *slot_; \ 615 T obj_; \ 616 \ 617 VEC_ASSERT (ix_ < vec_->num, "remove", T, base); \ 618 slot_ = &vec_->vec[ix_]; \ 619 obj_ = *slot_; \ 620 memmove (slot_, slot_ + 1, (--vec_->num - ix_) * sizeof (T)); \ 621 \ 622 return obj_; \ 623} \ 624 \ 625static inline T VEC_OP (T,base,unordered_remove) \ 626 (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \ 627{ \ 628 T *slot_; \ 629 T obj_; \ 630 \ 631 VEC_ASSERT (ix_ < vec_->num, "remove", T, base); \ 632 slot_ = &vec_->vec[ix_]; \ 633 obj_ = *slot_; \ 634 *slot_ = vec_->vec[--vec_->num]; \ 635 \ 636 return obj_; \ 637} \ 638 \ 639static inline T *VEC_OP (T,base,address) \ 640 (VEC(T,base) *vec_) \ 641{ \ 642 return vec_ ? vec_->vec : 0; \ 643} \ 644 \ 645static inline unsigned VEC_OP (T,base,lower_bound) \ 646 (VEC(T,base) *vec_, const T obj_, \ 647 bool (*lessthan_)(const T, const T) VEC_CHECK_DECL) \ 648{ \ 649 unsigned int len_ = VEC_OP (T,base, length) (vec_); \ 650 unsigned int half_, middle_; \ 651 unsigned int first_ = 0; \ 652 while (len_ > 0) \ 653 { \ 654 T middle_elem_; \ 655 half_ = len_ >> 1; \ 656 middle_ = first_; \ 657 middle_ += half_; \ 658 middle_elem_ = VEC_OP (T,base,index) (vec_, middle_ VEC_CHECK_PASS); \ 659 if (lessthan_ (middle_elem_, obj_)) \ 660 { \ 661 first_ = middle_; \ 662 ++first_; \ 663 len_ = len_ - half_ - 1; \ 664 } \ 665 else \ 666 len_ = half_; \ 667 } \ 668 return first_; \ 669} 670 671#define DEF_VEC_ALLOC_FUNC_P(T,A) \ 672static inline VEC(T,A) *VEC_OP (T,A,alloc) \ 673 (int alloc_ MEM_STAT_DECL) \ 674{ \ 675 /* We must request exact size allocation, hence the negation. */ \ 676 return (VEC(T,A) *) vec_##A##_p_reserve (NULL, -alloc_ PASS_MEM_STAT); \ 677} \ 678 \ 679static inline void VEC_OP (T,A,free) \ 680 (VEC(T,A) **vec_) \ 681{ \ 682 if (*vec_) \ 683 vec_##A##_free (*vec_); \ 684 *vec_ = NULL; \ 685} \ 686 \ 687static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \ 688{ \ 689 size_t len_ = vec_ ? vec_->num : 0; \ 690 VEC (T,A) *new_vec_ = NULL; \ 691 \ 692 if (len_) \ 693 { \ 694 /* We must request exact size allocation, hence the negation. */ \ 695 new_vec_ = (VEC (T,A) *)(vec_##A##_p_reserve \ 696 (NULL, -len_ PASS_MEM_STAT)); \ 697 \ 698 new_vec_->base.num = len_; \ 699 memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_); \ 700 } \ 701 return new_vec_; \ 702} \ 703 \ 704static inline int VEC_OP (T,A,reserve) \ 705 (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \ 706{ \ 707 int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), \ 708 alloc_ < 0 ? -alloc_ : alloc_ \ 709 VEC_CHECK_PASS); \ 710 \ 711 if (extend) \ 712 *vec_ = (VEC(T,A) *) vec_##A##_p_reserve (*vec_, alloc_ PASS_MEM_STAT); \ 713 \ 714 return extend; \ 715} \ 716 \ 717static inline void VEC_OP (T,A,safe_grow) \ 718 (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \ 719{ \ 720 VEC_ASSERT (size_ >= 0 \ 721 && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \ 722 "grow", T, A); \ 723 VEC_OP (T,A,reserve) (vec_, (int)(*vec_ ? VEC_BASE(*vec_)->num : 0) - size_ \ 724 VEC_CHECK_PASS PASS_MEM_STAT); \ 725 VEC_BASE (*vec_)->num = size_; \ 726} \ 727 \ 728static inline T *VEC_OP (T,A,safe_push) \ 729 (VEC(T,A) **vec_, T obj_ VEC_CHECK_DECL MEM_STAT_DECL) \ 730{ \ 731 VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \ 732 \ 733 return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS); \ 734} \ 735 \ 736static inline T *VEC_OP (T,A,safe_insert) \ 737 (VEC(T,A) **vec_, unsigned ix_, T obj_ VEC_CHECK_DECL MEM_STAT_DECL) \ 738{ \ 739 VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \ 740 \ 741 return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_ \ 742 VEC_CHECK_PASS); \ 743} 744 745/* Vector of object. */ 746#if IN_GENGTYPE 747{"DEF_VEC_O", VEC_STRINGIFY (VEC_T_GTY(#0,#1)) ";", "none"}, 748{"DEF_VEC_ALLOC_O", VEC_STRINGIFY (VEC_TA_GTY(#0,#1,#2,#3)) ";", NULL}, 749#else 750#define DEF_VEC_O(T) \ 751VEC_T_GTY(T,base); \ 752VEC_TA_GTY(T,base,none,); \ 753DEF_VEC_FUNC_O(T) \ 754struct vec_swallow_trailing_semi 755#define DEF_VEC_ALLOC_O(T,A) \ 756VEC_TA_GTY(T,base,A,); \ 757DEF_VEC_ALLOC_FUNC_O(T,A) \ 758struct vec_swallow_trailing_semi 759#endif 760 761#define DEF_VEC_FUNC_O(T) \ 762static inline unsigned VEC_OP (T,base,length) (const VEC(T,base) *vec_) \ 763{ \ 764 return vec_ ? vec_->num : 0; \ 765} \ 766 \ 767static inline T *VEC_OP (T,base,last) (VEC(T,base) *vec_ VEC_CHECK_DECL) \ 768{ \ 769 VEC_ASSERT (vec_ && vec_->num, "last", T, base); \ 770 \ 771 return &vec_->vec[vec_->num - 1]; \ 772} \ 773 \ 774static inline T *VEC_OP (T,base,index) \ 775 (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \ 776{ \ 777 VEC_ASSERT (vec_ && ix_ < vec_->num, "index", T, base); \ 778 \ 779 return &vec_->vec[ix_]; \ 780} \ 781 \ 782static inline int VEC_OP (T,base,iterate) \ 783 (VEC(T,base) *vec_, unsigned ix_, T **ptr) \ 784{ \ 785 if (vec_ && ix_ < vec_->num) \ 786 { \ 787 *ptr = &vec_->vec[ix_]; \ 788 return 1; \ 789 } \ 790 else \ 791 { \ 792 *ptr = 0; \ 793 return 0; \ 794 } \ 795} \ 796 \ 797static inline size_t VEC_OP (T,base,embedded_size) \ 798 (int alloc_) \ 799{ \ 800 return offsetof (VEC(T,base),vec) + alloc_ * sizeof(T); \ 801} \ 802 \ 803static inline void VEC_OP (T,base,embedded_init) \ 804 (VEC(T,base) *vec_, int alloc_) \ 805{ \ 806 vec_->num = 0; \ 807 vec_->alloc = alloc_; \ 808} \ 809 \ 810static inline int VEC_OP (T,base,space) \ 811 (VEC(T,base) *vec_, int alloc_ VEC_CHECK_DECL) \ 812{ \ 813 VEC_ASSERT (alloc_ >= 0, "space", T, base); \ 814 return vec_ ? vec_->alloc - vec_->num >= (unsigned)alloc_ : !alloc_; \ 815} \ 816 \ 817static inline T *VEC_OP (T,base,quick_push) \ 818 (VEC(T,base) *vec_, const T *obj_ VEC_CHECK_DECL) \ 819{ \ 820 T *slot_; \ 821 \ 822 VEC_ASSERT (vec_->num < vec_->alloc, "push", T, base); \ 823 slot_ = &vec_->vec[vec_->num++]; \ 824 if (obj_) \ 825 *slot_ = *obj_; \ 826 \ 827 return slot_; \ 828} \ 829 \ 830static inline void VEC_OP (T,base,pop) (VEC(T,base) *vec_ VEC_CHECK_DECL) \ 831{ \ 832 VEC_ASSERT (vec_->num, "pop", T, base); \ 833 --vec_->num; \ 834} \ 835 \ 836static inline void VEC_OP (T,base,truncate) \ 837 (VEC(T,base) *vec_, unsigned size_ VEC_CHECK_DECL) \ 838{ \ 839 VEC_ASSERT (vec_ ? vec_->num >= size_ : !size_, "truncate", T, base); \ 840 if (vec_) \ 841 vec_->num = size_; \ 842} \ 843 \ 844static inline T *VEC_OP (T,base,replace) \ 845 (VEC(T,base) *vec_, unsigned ix_, const T *obj_ VEC_CHECK_DECL) \ 846{ \ 847 T *slot_; \ 848 \ 849 VEC_ASSERT (ix_ < vec_->num, "replace", T, base); \ 850 slot_ = &vec_->vec[ix_]; \ 851 if (obj_) \ 852 *slot_ = *obj_; \ 853 \ 854 return slot_; \ 855} \ 856 \ 857static inline T *VEC_OP (T,base,quick_insert) \ 858 (VEC(T,base) *vec_, unsigned ix_, const T *obj_ VEC_CHECK_DECL) \ 859{ \ 860 T *slot_; \ 861 \ 862 VEC_ASSERT (vec_->num < vec_->alloc, "insert", T, base); \ 863 VEC_ASSERT (ix_ <= vec_->num, "insert", T, base); \ 864 slot_ = &vec_->vec[ix_]; \ 865 memmove (slot_ + 1, slot_, (vec_->num++ - ix_) * sizeof (T)); \ 866 if (obj_) \ 867 *slot_ = *obj_; \ 868 \ 869 return slot_; \ 870} \ 871 \ 872static inline void VEC_OP (T,base,ordered_remove) \ 873 (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \ 874{ \ 875 T *slot_; \ 876 \ 877 VEC_ASSERT (ix_ < vec_->num, "remove", T, base); \ 878 slot_ = &vec_->vec[ix_]; \ 879 memmove (slot_, slot_ + 1, (--vec_->num - ix_) * sizeof (T)); \ 880} \ 881 \ 882static inline void VEC_OP (T,base,unordered_remove) \ 883 (VEC(T,base) *vec_, unsigned ix_ VEC_CHECK_DECL) \ 884{ \ 885 VEC_ASSERT (ix_ < vec_->num, "remove", T, base); \ 886 vec_->vec[ix_] = vec_->vec[--vec_->num]; \ 887} \ 888 \ 889static inline T *VEC_OP (T,base,address) \ 890 (VEC(T,base) *vec_) \ 891{ \ 892 return vec_ ? vec_->vec : 0; \ 893} \ 894 \ 895static inline unsigned VEC_OP (T,base,lower_bound) \ 896 (VEC(T,base) *vec_, const T *obj_, \ 897 bool (*lessthan_)(const T *, const T *) VEC_CHECK_DECL) \ 898{ \ 899 unsigned int len_ = VEC_OP (T, base, length) (vec_); \ 900 unsigned int half_, middle_; \ 901 unsigned int first_ = 0; \ 902 while (len_ > 0) \ 903 { \ 904 T *middle_elem_; \ 905 half_ = len_ >> 1; \ 906 middle_ = first_; \ 907 middle_ += half_; \ 908 middle_elem_ = VEC_OP (T,base,index) (vec_, middle_ VEC_CHECK_PASS); \ 909 if (lessthan_ (middle_elem_, obj_)) \ 910 { \ 911 first_ = middle_; \ 912 ++first_; \ 913 len_ = len_ - half_ - 1; \ 914 } \ 915 else \ 916 len_ = half_; \ 917 } \ 918 return first_; \ 919} 920 921#define DEF_VEC_ALLOC_FUNC_O(T,A) \ 922static inline VEC(T,A) *VEC_OP (T,A,alloc) \ 923 (int alloc_ MEM_STAT_DECL) \ 924{ \ 925 /* We must request exact size allocation, hence the negation. */ \ 926 return (VEC(T,A) *) vec_##A##_o_reserve (NULL, -alloc_, \ 927 offsetof (VEC(T,A),base.vec), \ 928 sizeof (T) \ 929 PASS_MEM_STAT); \ 930} \ 931 \ 932static inline VEC(T,A) *VEC_OP (T,A,copy) (VEC(T,base) *vec_ MEM_STAT_DECL) \ 933{ \ 934 size_t len_ = vec_ ? vec_->num : 0; \ 935 VEC (T,A) *new_vec_ = NULL; \ 936 \ 937 if (len_) \ 938 { \ 939 /* We must request exact size allocation, hence the negation. */ \ 940 new_vec_ = (VEC (T,A) *)(vec_##A##_o_reserve \ 941 (NULL, -len_, \ 942 offsetof (VEC(T,A),base.vec), sizeof (T) \ 943 PASS_MEM_STAT)); \ 944 \ 945 new_vec_->base.num = len_; \ 946 memcpy (new_vec_->base.vec, vec_->vec, sizeof (T) * len_); \ 947 } \ 948 return new_vec_; \ 949} \ 950 \ 951static inline void VEC_OP (T,A,free) \ 952 (VEC(T,A) **vec_) \ 953{ \ 954 if (*vec_) \ 955 vec_##A##_free (*vec_); \ 956 *vec_ = NULL; \ 957} \ 958 \ 959static inline int VEC_OP (T,A,reserve) \ 960 (VEC(T,A) **vec_, int alloc_ VEC_CHECK_DECL MEM_STAT_DECL) \ 961{ \ 962 int extend = !VEC_OP (T,base,space) (VEC_BASE(*vec_), \ 963 alloc_ < 0 ? -alloc_ : alloc_ \ 964 VEC_CHECK_PASS); \ 965 \ 966 if (extend) \ 967 *vec_ = (VEC(T,A) *) vec_##A##_o_reserve (*vec_, alloc_, \ 968 offsetof (VEC(T,A),base.vec),\ 969 sizeof (T) \ 970 PASS_MEM_STAT); \ 971 \ 972 return extend; \ 973} \ 974 \ 975static inline void VEC_OP (T,A,safe_grow) \ 976 (VEC(T,A) **vec_, int size_ VEC_CHECK_DECL MEM_STAT_DECL) \ 977{ \ 978 VEC_ASSERT (size_ >= 0 \ 979 && VEC_OP(T,base,length) VEC_BASE(*vec_) <= (unsigned)size_, \ 980 "grow", T, A); \ 981 VEC_OP (T,A,reserve) (vec_, (int)(*vec_ ? VEC_BASE(*vec_)->num : 0) - size_ \ 982 VEC_CHECK_PASS PASS_MEM_STAT); \ 983 VEC_BASE (*vec_)->num = size_; \ 984 VEC_BASE (*vec_)->num = size_; \ 985} \ 986 \ 987static inline T *VEC_OP (T,A,safe_push) \ 988 (VEC(T,A) **vec_, const T *obj_ VEC_CHECK_DECL MEM_STAT_DECL) \ 989{ \ 990 VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \ 991 \ 992 return VEC_OP (T,base,quick_push) (VEC_BASE(*vec_), obj_ VEC_CHECK_PASS); \ 993} \ 994 \ 995static inline T *VEC_OP (T,A,safe_insert) \ 996 (VEC(T,A) **vec_, unsigned ix_, const T *obj_ \ 997 VEC_CHECK_DECL MEM_STAT_DECL) \ 998{ \ 999 VEC_OP (T,A,reserve) (vec_, 1 VEC_CHECK_PASS PASS_MEM_STAT); \ 1000 \ 1001 return VEC_OP (T,base,quick_insert) (VEC_BASE(*vec_), ix_, obj_ \ 1002 VEC_CHECK_PASS); \ 1003} 1004#endif /* GCC_VEC_H */ 1005