1 /* Vector API for GNU compiler. 2 Copyright (C) 2004-2018 Free Software Foundation, Inc. 3 Contributed by Nathan Sidwell <nathan@codesourcery.com> 4 Re-implemented in C++ by Diego Novillo <dnovillo@google.com> 5 6 This file is part of GCC. 7 8 GCC is free software; you can redistribute it and/or modify it under 9 the terms of the GNU General Public License as published by the Free 10 Software Foundation; either version 3, or (at your option) any later 11 version. 12 13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 14 WARRANTY; without even the implied warranty of MERCHANTABILITY or 15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 16 for more details. 17 18 You should have received a copy of the GNU General Public License 19 along 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 /* Some gen* file have no ggc support as the header file gtype-desc.h is 26 missing. Provide these definitions in case ggc.h has not been included. 27 This is not a problem because any code that runs before gengtype is built 28 will never need to use GC vectors.*/ 29 30 extern void ggc_free (void *); 31 extern size_t ggc_round_alloc_size (size_t requested_size); 32 extern void *ggc_realloc (void *, size_t MEM_STAT_DECL); 33 34 /* Templated vector type and associated interfaces. 35 36 The interface functions are typesafe and use inline functions, 37 sometimes backed by out-of-line generic functions. The vectors are 38 designed to interoperate with the GTY machinery. 39 40 There are both 'index' and 'iterate' accessors. The index accessor 41 is implemented by operator[]. The iterator returns a boolean 42 iteration condition and updates the iteration variable passed by 43 reference. Because the iterator will be inlined, the address-of 44 can be optimized away. 45 46 Each operation that increases the number of active elements is 47 available in 'quick' and 'safe' variants. The former presumes that 48 there is sufficient allocated space for the operation to succeed 49 (it dies if there is not). The latter will reallocate the 50 vector, if needed. Reallocation causes an exponential increase in 51 vector size. If you know you will be adding N elements, it would 52 be more efficient to use the reserve operation before adding the 53 elements with the 'quick' operation. This will ensure there are at 54 least as many elements as you ask for, it will exponentially 55 increase if there are too few spare slots. If you want reserve a 56 specific number of slots, but do not want the exponential increase 57 (for instance, you know this is the last allocation), use the 58 reserve_exact operation. You can also create a vector of a 59 specific size from the get go. 60 61 You should prefer the push and pop operations, as they append and 62 remove from the end of the vector. If you need to remove several 63 items in one go, use the truncate operation. The insert and remove 64 operations allow you to change elements in the middle of the 65 vector. There are two remove operations, one which preserves the 66 element ordering 'ordered_remove', and one which does not 67 'unordered_remove'. The latter function copies the end element 68 into the removed slot, rather than invoke a memmove operation. The 69 'lower_bound' function will determine where to place an item in the 70 array using insert that will maintain sorted order. 71 72 Vectors are template types with three arguments: the type of the 73 elements in the vector, the allocation strategy, and the physical 74 layout to use 75 76 Four allocation strategies are supported: 77 78 - Heap: allocation is done using malloc/free. This is the 79 default allocation strategy. 80 81 - GC: allocation is done using ggc_alloc/ggc_free. 82 83 - GC atomic: same as GC with the exception that the elements 84 themselves are assumed to be of an atomic type that does 85 not need to be garbage collected. This means that marking 86 routines do not need to traverse the array marking the 87 individual elements. This increases the performance of 88 GC activities. 89 90 Two physical layouts are supported: 91 92 - Embedded: The vector is structured using the trailing array 93 idiom. The last member of the structure is an array of size 94 1. When the vector is initially allocated, a single memory 95 block is created to hold the vector's control data and the 96 array of elements. These vectors cannot grow without 97 reallocation (see discussion on embeddable vectors below). 98 99 - Space efficient: The vector is structured as a pointer to an 100 embedded vector. This is the default layout. It means that 101 vectors occupy a single word of storage before initial 102 allocation. Vectors are allowed to grow (the internal 103 pointer is reallocated but the main vector instance does not 104 need to relocate). 105 106 The type, allocation and layout are specified when the vector is 107 declared. 108 109 If you need to directly manipulate a vector, then the 'address' 110 accessor will return the address of the start of the vector. Also 111 the 'space' predicate will tell you whether there is spare capacity 112 in the vector. You will not normally need to use these two functions. 113 114 Notes on the different layout strategies 115 116 * Embeddable vectors (vec<T, A, vl_embed>) 117 118 These vectors are suitable to be embedded in other data 119 structures so that they can be pre-allocated in a contiguous 120 memory block. 121 122 Embeddable vectors are implemented using the trailing array 123 idiom, thus they are not resizeable without changing the address 124 of the vector object itself. This means you cannot have 125 variables or fields of embeddable vector type -- always use a 126 pointer to a vector. The one exception is the final field of a 127 structure, which could be a vector type. 128 129 You will have to use the embedded_size & embedded_init calls to 130 create such objects, and they will not be resizeable (so the 131 'safe' allocation variants are not available). 132 133 Properties of embeddable vectors: 134 135 - The whole vector and control data are allocated in a single 136 contiguous block. It uses the trailing-vector idiom, so 137 allocation must reserve enough space for all the elements 138 in the vector plus its control data. 139 - The vector cannot be re-allocated. 140 - The vector cannot grow nor shrink. 141 - No indirections needed for access/manipulation. 142 - It requires 2 words of storage (prior to vector allocation). 143 144 145 * Space efficient vector (vec<T, A, vl_ptr>) 146 147 These vectors can grow dynamically and are allocated together 148 with their control data. They are suited to be included in data 149 structures. Prior to initial allocation, they only take a single 150 word of storage. 151 152 These vectors are implemented as a pointer to embeddable vectors. 153 The semantics allow for this pointer to be NULL to represent 154 empty vectors. This way, empty vectors occupy minimal space in 155 the structure containing them. 156 157 Properties: 158 159 - The whole vector and control data are allocated in a single 160 contiguous block. 161 - The whole vector may be re-allocated. 162 - Vector data may grow and shrink. 163 - Access and manipulation requires a pointer test and 164 indirection. 165 - It requires 1 word of storage (prior to vector allocation). 166 167 An example of their use would be, 168 169 struct my_struct { 170 // A space-efficient vector of tree pointers in GC memory. 171 vec<tree, va_gc, vl_ptr> v; 172 }; 173 174 struct my_struct *s; 175 176 if (s->v.length ()) { we have some contents } 177 s->v.safe_push (decl); // append some decl onto the end 178 for (ix = 0; s->v.iterate (ix, &elt); ix++) 179 { do something with elt } 180 */ 181 182 /* Support function for statistics. */ 183 extern void dump_vec_loc_statistics (void); 184 185 /* Hashtable mapping vec addresses to descriptors. */ 186 extern htab_t vec_mem_usage_hash; 187 188 /* Control data for vectors. This contains the number of allocated 189 and used slots inside a vector. */ 190 191 struct vec_prefix 192 { 193 /* FIXME - These fields should be private, but we need to cater to 194 compilers that have stricter notions of PODness for types. */ 195 196 /* Memory allocation support routines in vec.c. */ 197 void register_overhead (void *, size_t, size_t CXX_MEM_STAT_INFO); 198 void release_overhead (void *, size_t, bool CXX_MEM_STAT_INFO); 199 static unsigned calculate_allocation (vec_prefix *, unsigned, bool); 200 static unsigned calculate_allocation_1 (unsigned, unsigned); 201 202 /* Note that vec_prefix should be a base class for vec, but we use 203 offsetof() on vector fields of tree structures (e.g., 204 tree_binfo::base_binfos), and offsetof only supports base types. 205 206 To compensate, we make vec_prefix a field inside vec and make 207 vec a friend class of vec_prefix so it can access its fields. */ 208 template <typename, typename, typename> friend struct vec; 209 210 /* The allocator types also need access to our internals. */ 211 friend struct va_gc; 212 friend struct va_gc_atomic; 213 friend struct va_heap; 214 215 unsigned m_alloc : 31; 216 unsigned m_using_auto_storage : 1; 217 unsigned m_num; 218 }; 219 220 /* Calculate the number of slots to reserve a vector, making sure that 221 RESERVE slots are free. If EXACT grow exactly, otherwise grow 222 exponentially. PFX is the control data for the vector. */ 223 224 inline unsigned 225 vec_prefix::calculate_allocation (vec_prefix *pfx, unsigned reserve, 226 bool exact) 227 { 228 if (exact) 229 return (pfx ? pfx->m_num : 0) + reserve; 230 else if (!pfx) 231 return MAX (4, reserve); 232 return calculate_allocation_1 (pfx->m_alloc, pfx->m_num + reserve); 233 } 234 235 template<typename, typename, typename> struct vec; 236 237 /* Valid vector layouts 238 239 vl_embed - Embeddable vector that uses the trailing array idiom. 240 vl_ptr - Space efficient vector that uses a pointer to an 241 embeddable vector. */ 242 struct vl_embed { }; 243 struct vl_ptr { }; 244 245 246 /* Types of supported allocations 247 248 va_heap - Allocation uses malloc/free. 249 va_gc - Allocation uses ggc_alloc. 250 va_gc_atomic - Same as GC, but individual elements of the array 251 do not need to be marked during collection. */ 252 253 /* Allocator type for heap vectors. */ 254 struct va_heap 255 { 256 /* Heap vectors are frequently regular instances, so use the vl_ptr 257 layout for them. */ 258 typedef vl_ptr default_layout; 259 260 template<typename T> 261 static void reserve (vec<T, va_heap, vl_embed> *&, unsigned, bool 262 CXX_MEM_STAT_INFO); 263 264 template<typename T> 265 static void release (vec<T, va_heap, vl_embed> *&); 266 }; 267 268 269 /* Allocator for heap memory. Ensure there are at least RESERVE free 270 slots in V. If EXACT is true, grow exactly, else grow 271 exponentially. As a special case, if the vector had not been 272 allocated and RESERVE is 0, no vector will be created. */ 273 274 template<typename T> 275 inline void 276 va_heap::reserve (vec<T, va_heap, vl_embed> *&v, unsigned reserve, bool exact 277 MEM_STAT_DECL) 278 { 279 unsigned alloc 280 = vec_prefix::calculate_allocation (v ? &v->m_vecpfx : 0, reserve, exact); 281 gcc_checking_assert (alloc); 282 283 if (GATHER_STATISTICS && v) 284 v->m_vecpfx.release_overhead (v, v->allocated (), false); 285 286 size_t size = vec<T, va_heap, vl_embed>::embedded_size (alloc); 287 unsigned nelem = v ? v->length () : 0; 288 v = static_cast <vec<T, va_heap, vl_embed> *> (xrealloc (v, size)); 289 v->embedded_init (alloc, nelem); 290 291 if (GATHER_STATISTICS) 292 v->m_vecpfx.register_overhead (v, alloc, nelem PASS_MEM_STAT); 293 } 294 295 296 /* Free the heap space allocated for vector V. */ 297 298 template<typename T> 299 void 300 va_heap::release (vec<T, va_heap, vl_embed> *&v) 301 { 302 if (v == NULL) 303 return; 304 305 if (GATHER_STATISTICS) 306 v->m_vecpfx.release_overhead (v, v->allocated (), true); 307 ::free (v); 308 v = NULL; 309 } 310 311 312 /* Allocator type for GC vectors. Notice that we need the structure 313 declaration even if GC is not enabled. */ 314 315 struct va_gc 316 { 317 /* Use vl_embed as the default layout for GC vectors. Due to GTY 318 limitations, GC vectors must always be pointers, so it is more 319 efficient to use a pointer to the vl_embed layout, rather than 320 using a pointer to a pointer as would be the case with vl_ptr. */ 321 typedef vl_embed default_layout; 322 323 template<typename T, typename A> 324 static void reserve (vec<T, A, vl_embed> *&, unsigned, bool 325 CXX_MEM_STAT_INFO); 326 327 template<typename T, typename A> 328 static void release (vec<T, A, vl_embed> *&v); 329 }; 330 331 332 /* Free GC memory used by V and reset V to NULL. */ 333 334 template<typename T, typename A> 335 inline void 336 va_gc::release (vec<T, A, vl_embed> *&v) 337 { 338 if (v) 339 ::ggc_free (v); 340 v = NULL; 341 } 342 343 344 /* Allocator for GC memory. Ensure there are at least RESERVE free 345 slots in V. If EXACT is true, grow exactly, else grow 346 exponentially. As a special case, if the vector had not been 347 allocated and RESERVE is 0, no vector will be created. */ 348 349 template<typename T, typename A> 350 void 351 va_gc::reserve (vec<T, A, vl_embed> *&v, unsigned reserve, bool exact 352 MEM_STAT_DECL) 353 { 354 unsigned alloc 355 = vec_prefix::calculate_allocation (v ? &v->m_vecpfx : 0, reserve, exact); 356 if (!alloc) 357 { 358 ::ggc_free (v); 359 v = NULL; 360 return; 361 } 362 363 /* Calculate the amount of space we want. */ 364 size_t size = vec<T, A, vl_embed>::embedded_size (alloc); 365 366 /* Ask the allocator how much space it will really give us. */ 367 size = ::ggc_round_alloc_size (size); 368 369 /* Adjust the number of slots accordingly. */ 370 size_t vec_offset = sizeof (vec_prefix); 371 size_t elt_size = sizeof (T); 372 alloc = (size - vec_offset) / elt_size; 373 374 /* And finally, recalculate the amount of space we ask for. */ 375 size = vec_offset + alloc * elt_size; 376 377 unsigned nelem = v ? v->length () : 0; 378 v = static_cast <vec<T, A, vl_embed> *> (::ggc_realloc (v, size 379 PASS_MEM_STAT)); 380 v->embedded_init (alloc, nelem); 381 } 382 383 384 /* Allocator type for GC vectors. This is for vectors of types 385 atomics w.r.t. collection, so allocation and deallocation is 386 completely inherited from va_gc. */ 387 struct va_gc_atomic : va_gc 388 { 389 }; 390 391 392 /* Generic vector template. Default values for A and L indicate the 393 most commonly used strategies. 394 395 FIXME - Ideally, they would all be vl_ptr to encourage using regular 396 instances for vectors, but the existing GTY machinery is limited 397 in that it can only deal with GC objects that are pointers 398 themselves. 399 400 This means that vector operations that need to deal with 401 potentially NULL pointers, must be provided as free 402 functions (see the vec_safe_* functions above). */ 403 template<typename T, 404 typename A = va_heap, 405 typename L = typename A::default_layout> 406 struct GTY((user)) vec 407 { 408 }; 409 410 /* Generic vec<> debug helpers. 411 412 These need to be instantiated for each vec<TYPE> used throughout 413 the compiler like this: 414 415 DEFINE_DEBUG_VEC (TYPE) 416 417 The reason we have a debug_helper() is because GDB can't 418 disambiguate a plain call to debug(some_vec), and it must be called 419 like debug<TYPE>(some_vec). */ 420 421 template<typename T> 422 void 423 debug_helper (vec<T> &ref) 424 { 425 unsigned i; 426 for (i = 0; i < ref.length (); ++i) 427 { 428 fprintf (stderr, "[%d] = ", i); 429 debug_slim (ref[i]); 430 fputc ('\n', stderr); 431 } 432 } 433 434 /* We need a separate va_gc variant here because default template 435 argument for functions cannot be used in c++-98. Once this 436 restriction is removed, those variant should be folded with the 437 above debug_helper. */ 438 439 template<typename T> 440 void 441 debug_helper (vec<T, va_gc> &ref) 442 { 443 unsigned i; 444 for (i = 0; i < ref.length (); ++i) 445 { 446 fprintf (stderr, "[%d] = ", i); 447 debug_slim (ref[i]); 448 fputc ('\n', stderr); 449 } 450 } 451 452 /* Macro to define debug(vec<T>) and debug(vec<T, va_gc>) helper 453 functions for a type T. */ 454 455 #define DEFINE_DEBUG_VEC(T) \ 456 template void debug_helper (vec<T> &); \ 457 template void debug_helper (vec<T, va_gc> &); \ 458 /* Define the vec<T> debug functions. */ \ 459 DEBUG_FUNCTION void \ 460 debug (vec<T> &ref) \ 461 { \ 462 debug_helper <T> (ref); \ 463 } \ 464 DEBUG_FUNCTION void \ 465 debug (vec<T> *ptr) \ 466 { \ 467 if (ptr) \ 468 debug (*ptr); \ 469 else \ 470 fprintf (stderr, "<nil>\n"); \ 471 } \ 472 /* Define the vec<T, va_gc> debug functions. */ \ 473 DEBUG_FUNCTION void \ 474 debug (vec<T, va_gc> &ref) \ 475 { \ 476 debug_helper <T> (ref); \ 477 } \ 478 DEBUG_FUNCTION void \ 479 debug (vec<T, va_gc> *ptr) \ 480 { \ 481 if (ptr) \ 482 debug (*ptr); \ 483 else \ 484 fprintf (stderr, "<nil>\n"); \ 485 } 486 487 /* Default-construct N elements in DST. */ 488 489 template <typename T> 490 inline void 491 vec_default_construct (T *dst, unsigned n) 492 { 493 #ifdef BROKEN_VALUE_INITIALIZATION 494 /* Versions of GCC before 4.4 sometimes leave certain objects 495 uninitialized when value initialized, though if the type has 496 user defined default ctor, that ctor is invoked. As a workaround 497 perform clearing first and then the value initialization, which 498 fixes the case when value initialization doesn't initialize due to 499 the bugs and should initialize to all zeros, but still allows 500 vectors for types with user defined default ctor that initializes 501 some or all elements to non-zero. If T has no user defined 502 default ctor and some non-static data members have user defined 503 default ctors that initialize to non-zero the workaround will 504 still not work properly; in that case we just need to provide 505 user defined default ctor. */ 506 memset (dst, '\0', sizeof (T) * n); 507 #endif 508 for ( ; n; ++dst, --n) 509 ::new (static_cast<void*>(dst)) T (); 510 } 511 512 /* Copy-construct N elements in DST from *SRC. */ 513 514 template <typename T> 515 inline void 516 vec_copy_construct (T *dst, const T *src, unsigned n) 517 { 518 for ( ; n; ++dst, ++src, --n) 519 ::new (static_cast<void*>(dst)) T (*src); 520 } 521 522 /* Type to provide NULL values for vec<T, A, L>. This is used to 523 provide nil initializers for vec instances. Since vec must be 524 a POD, we cannot have proper ctor/dtor for it. To initialize 525 a vec instance, you can assign it the value vNULL. This isn't 526 needed for file-scope and function-local static vectors, which 527 are zero-initialized by default. */ 528 struct vnull 529 { 530 template <typename T, typename A, typename L> 531 CONSTEXPR operator vec<T, A, L> () { return vec<T, A, L>(); } 532 }; 533 extern vnull vNULL; 534 535 536 /* Embeddable vector. These vectors are suitable to be embedded 537 in other data structures so that they can be pre-allocated in a 538 contiguous memory block. 539 540 Embeddable vectors are implemented using the trailing array idiom, 541 thus they are not resizeable without changing the address of the 542 vector object itself. This means you cannot have variables or 543 fields of embeddable vector type -- always use a pointer to a 544 vector. The one exception is the final field of a structure, which 545 could be a vector type. 546 547 You will have to use the embedded_size & embedded_init calls to 548 create such objects, and they will not be resizeable (so the 'safe' 549 allocation variants are not available). 550 551 Properties: 552 553 - The whole vector and control data are allocated in a single 554 contiguous block. It uses the trailing-vector idiom, so 555 allocation must reserve enough space for all the elements 556 in the vector plus its control data. 557 - The vector cannot be re-allocated. 558 - The vector cannot grow nor shrink. 559 - No indirections needed for access/manipulation. 560 - It requires 2 words of storage (prior to vector allocation). */ 561 562 template<typename T, typename A> 563 struct GTY((user)) vec<T, A, vl_embed> 564 { 565 public: 566 unsigned allocated (void) const { return m_vecpfx.m_alloc; } 567 unsigned length (void) const { return m_vecpfx.m_num; } 568 bool is_empty (void) const { return m_vecpfx.m_num == 0; } 569 T *address (void) { return m_vecdata; } 570 const T *address (void) const { return m_vecdata; } 571 T *begin () { return address (); } 572 const T *begin () const { return address (); } 573 T *end () { return address () + length (); } 574 const T *end () const { return address () + length (); } 575 const T &operator[] (unsigned) const; 576 T &operator[] (unsigned); 577 T &last (void); 578 bool space (unsigned) const; 579 bool iterate (unsigned, T *) const; 580 bool iterate (unsigned, T **) const; 581 vec *copy (ALONE_CXX_MEM_STAT_INFO) const; 582 void splice (const vec &); 583 void splice (const vec *src); 584 T *quick_push (const T &); 585 T &pop (void); 586 void truncate (unsigned); 587 void quick_insert (unsigned, const T &); 588 void ordered_remove (unsigned); 589 void unordered_remove (unsigned); 590 void block_remove (unsigned, unsigned); 591 void qsort (int (*) (const void *, const void *)); 592 T *bsearch (const void *key, int (*compar)(const void *, const void *)); 593 unsigned lower_bound (T, bool (*)(const T &, const T &)) const; 594 bool contains (const T &search) const; 595 static size_t embedded_size (unsigned); 596 void embedded_init (unsigned, unsigned = 0, unsigned = 0); 597 void quick_grow (unsigned len); 598 void quick_grow_cleared (unsigned len); 599 600 /* vec class can access our internal data and functions. */ 601 template <typename, typename, typename> friend struct vec; 602 603 /* The allocator types also need access to our internals. */ 604 friend struct va_gc; 605 friend struct va_gc_atomic; 606 friend struct va_heap; 607 608 /* FIXME - These fields should be private, but we need to cater to 609 compilers that have stricter notions of PODness for types. */ 610 vec_prefix m_vecpfx; 611 T m_vecdata[1]; 612 }; 613 614 615 /* Convenience wrapper functions to use when dealing with pointers to 616 embedded vectors. Some functionality for these vectors must be 617 provided via free functions for these reasons: 618 619 1- The pointer may be NULL (e.g., before initial allocation). 620 621 2- When the vector needs to grow, it must be reallocated, so 622 the pointer will change its value. 623 624 Because of limitations with the current GC machinery, all vectors 625 in GC memory *must* be pointers. */ 626 627 628 /* If V contains no room for NELEMS elements, return false. Otherwise, 629 return true. */ 630 template<typename T, typename A> 631 inline bool 632 vec_safe_space (const vec<T, A, vl_embed> *v, unsigned nelems) 633 { 634 return v ? v->space (nelems) : nelems == 0; 635 } 636 637 638 /* If V is NULL, return 0. Otherwise, return V->length(). */ 639 template<typename T, typename A> 640 inline unsigned 641 vec_safe_length (const vec<T, A, vl_embed> *v) 642 { 643 return v ? v->length () : 0; 644 } 645 646 647 /* If V is NULL, return NULL. Otherwise, return V->address(). */ 648 template<typename T, typename A> 649 inline T * 650 vec_safe_address (vec<T, A, vl_embed> *v) 651 { 652 return v ? v->address () : NULL; 653 } 654 655 656 /* If V is NULL, return true. Otherwise, return V->is_empty(). */ 657 template<typename T, typename A> 658 inline bool 659 vec_safe_is_empty (vec<T, A, vl_embed> *v) 660 { 661 return v ? v->is_empty () : true; 662 } 663 664 /* If V does not have space for NELEMS elements, call 665 V->reserve(NELEMS, EXACT). */ 666 template<typename T, typename A> 667 inline bool 668 vec_safe_reserve (vec<T, A, vl_embed> *&v, unsigned nelems, bool exact = false 669 CXX_MEM_STAT_INFO) 670 { 671 bool extend = nelems ? !vec_safe_space (v, nelems) : false; 672 if (extend) 673 A::reserve (v, nelems, exact PASS_MEM_STAT); 674 return extend; 675 } 676 677 template<typename T, typename A> 678 inline bool 679 vec_safe_reserve_exact (vec<T, A, vl_embed> *&v, unsigned nelems 680 CXX_MEM_STAT_INFO) 681 { 682 return vec_safe_reserve (v, nelems, true PASS_MEM_STAT); 683 } 684 685 686 /* Allocate GC memory for V with space for NELEMS slots. If NELEMS 687 is 0, V is initialized to NULL. */ 688 689 template<typename T, typename A> 690 inline void 691 vec_alloc (vec<T, A, vl_embed> *&v, unsigned nelems CXX_MEM_STAT_INFO) 692 { 693 v = NULL; 694 vec_safe_reserve (v, nelems, false PASS_MEM_STAT); 695 } 696 697 698 /* Free the GC memory allocated by vector V and set it to NULL. */ 699 700 template<typename T, typename A> 701 inline void 702 vec_free (vec<T, A, vl_embed> *&v) 703 { 704 A::release (v); 705 } 706 707 708 /* Grow V to length LEN. Allocate it, if necessary. */ 709 template<typename T, typename A> 710 inline void 711 vec_safe_grow (vec<T, A, vl_embed> *&v, unsigned len CXX_MEM_STAT_INFO) 712 { 713 unsigned oldlen = vec_safe_length (v); 714 gcc_checking_assert (len >= oldlen); 715 vec_safe_reserve_exact (v, len - oldlen PASS_MEM_STAT); 716 v->quick_grow (len); 717 } 718 719 720 /* If V is NULL, allocate it. Call V->safe_grow_cleared(LEN). */ 721 template<typename T, typename A> 722 inline void 723 vec_safe_grow_cleared (vec<T, A, vl_embed> *&v, unsigned len CXX_MEM_STAT_INFO) 724 { 725 unsigned oldlen = vec_safe_length (v); 726 vec_safe_grow (v, len PASS_MEM_STAT); 727 vec_default_construct (v->address () + oldlen, len - oldlen); 728 } 729 730 731 /* If V is NULL return false, otherwise return V->iterate(IX, PTR). */ 732 template<typename T, typename A> 733 inline bool 734 vec_safe_iterate (const vec<T, A, vl_embed> *v, unsigned ix, T **ptr) 735 { 736 if (v) 737 return v->iterate (ix, ptr); 738 else 739 { 740 *ptr = 0; 741 return false; 742 } 743 } 744 745 template<typename T, typename A> 746 inline bool 747 vec_safe_iterate (const vec<T, A, vl_embed> *v, unsigned ix, T *ptr) 748 { 749 if (v) 750 return v->iterate (ix, ptr); 751 else 752 { 753 *ptr = 0; 754 return false; 755 } 756 } 757 758 759 /* If V has no room for one more element, reallocate it. Then call 760 V->quick_push(OBJ). */ 761 template<typename T, typename A> 762 inline T * 763 vec_safe_push (vec<T, A, vl_embed> *&v, const T &obj CXX_MEM_STAT_INFO) 764 { 765 vec_safe_reserve (v, 1, false PASS_MEM_STAT); 766 return v->quick_push (obj); 767 } 768 769 770 /* if V has no room for one more element, reallocate it. Then call 771 V->quick_insert(IX, OBJ). */ 772 template<typename T, typename A> 773 inline void 774 vec_safe_insert (vec<T, A, vl_embed> *&v, unsigned ix, const T &obj 775 CXX_MEM_STAT_INFO) 776 { 777 vec_safe_reserve (v, 1, false PASS_MEM_STAT); 778 v->quick_insert (ix, obj); 779 } 780 781 782 /* If V is NULL, do nothing. Otherwise, call V->truncate(SIZE). */ 783 template<typename T, typename A> 784 inline void 785 vec_safe_truncate (vec<T, A, vl_embed> *v, unsigned size) 786 { 787 if (v) 788 v->truncate (size); 789 } 790 791 792 /* If SRC is not NULL, return a pointer to a copy of it. */ 793 template<typename T, typename A> 794 inline vec<T, A, vl_embed> * 795 vec_safe_copy (vec<T, A, vl_embed> *src CXX_MEM_STAT_INFO) 796 { 797 return src ? src->copy (ALONE_PASS_MEM_STAT) : NULL; 798 } 799 800 /* Copy the elements from SRC to the end of DST as if by memcpy. 801 Reallocate DST, if necessary. */ 802 template<typename T, typename A> 803 inline void 804 vec_safe_splice (vec<T, A, vl_embed> *&dst, const vec<T, A, vl_embed> *src 805 CXX_MEM_STAT_INFO) 806 { 807 unsigned src_len = vec_safe_length (src); 808 if (src_len) 809 { 810 vec_safe_reserve_exact (dst, vec_safe_length (dst) + src_len 811 PASS_MEM_STAT); 812 dst->splice (*src); 813 } 814 } 815 816 /* Return true if SEARCH is an element of V. Note that this is O(N) in the 817 size of the vector and so should be used with care. */ 818 819 template<typename T, typename A> 820 inline bool 821 vec_safe_contains (vec<T, A, vl_embed> *v, const T &search) 822 { 823 return v ? v->contains (search) : false; 824 } 825 826 /* Index into vector. Return the IX'th element. IX must be in the 827 domain of the vector. */ 828 829 template<typename T, typename A> 830 inline const T & 831 vec<T, A, vl_embed>::operator[] (unsigned ix) const 832 { 833 gcc_checking_assert (ix < m_vecpfx.m_num); 834 return m_vecdata[ix]; 835 } 836 837 template<typename T, typename A> 838 inline T & 839 vec<T, A, vl_embed>::operator[] (unsigned ix) 840 { 841 gcc_checking_assert (ix < m_vecpfx.m_num); 842 return m_vecdata[ix]; 843 } 844 845 846 /* Get the final element of the vector, which must not be empty. */ 847 848 template<typename T, typename A> 849 inline T & 850 vec<T, A, vl_embed>::last (void) 851 { 852 gcc_checking_assert (m_vecpfx.m_num > 0); 853 return (*this)[m_vecpfx.m_num - 1]; 854 } 855 856 857 /* If this vector has space for NELEMS additional entries, return 858 true. You usually only need to use this if you are doing your 859 own vector reallocation, for instance on an embedded vector. This 860 returns true in exactly the same circumstances that vec::reserve 861 will. */ 862 863 template<typename T, typename A> 864 inline bool 865 vec<T, A, vl_embed>::space (unsigned nelems) const 866 { 867 return m_vecpfx.m_alloc - m_vecpfx.m_num >= nelems; 868 } 869 870 871 /* Return iteration condition and update PTR to point to the IX'th 872 element of this vector. Use this to iterate over the elements of a 873 vector as follows, 874 875 for (ix = 0; vec<T, A>::iterate (v, ix, &ptr); ix++) 876 continue; */ 877 878 template<typename T, typename A> 879 inline bool 880 vec<T, A, vl_embed>::iterate (unsigned ix, T *ptr) const 881 { 882 if (ix < m_vecpfx.m_num) 883 { 884 *ptr = m_vecdata[ix]; 885 return true; 886 } 887 else 888 { 889 *ptr = 0; 890 return false; 891 } 892 } 893 894 895 /* Return iteration condition and update *PTR to point to the 896 IX'th element of this vector. Use this to iterate over the 897 elements of a vector as follows, 898 899 for (ix = 0; v->iterate (ix, &ptr); ix++) 900 continue; 901 902 This variant is for vectors of objects. */ 903 904 template<typename T, typename A> 905 inline bool 906 vec<T, A, vl_embed>::iterate (unsigned ix, T **ptr) const 907 { 908 if (ix < m_vecpfx.m_num) 909 { 910 *ptr = CONST_CAST (T *, &m_vecdata[ix]); 911 return true; 912 } 913 else 914 { 915 *ptr = 0; 916 return false; 917 } 918 } 919 920 921 /* Return a pointer to a copy of this vector. */ 922 923 template<typename T, typename A> 924 inline vec<T, A, vl_embed> * 925 vec<T, A, vl_embed>::copy (ALONE_MEM_STAT_DECL) const 926 { 927 vec<T, A, vl_embed> *new_vec = NULL; 928 unsigned len = length (); 929 if (len) 930 { 931 vec_alloc (new_vec, len PASS_MEM_STAT); 932 new_vec->embedded_init (len, len); 933 vec_copy_construct (new_vec->address (), m_vecdata, len); 934 } 935 return new_vec; 936 } 937 938 939 /* Copy the elements from SRC to the end of this vector as if by memcpy. 940 The vector must have sufficient headroom available. */ 941 942 template<typename T, typename A> 943 inline void 944 vec<T, A, vl_embed>::splice (const vec<T, A, vl_embed> &src) 945 { 946 unsigned len = src.length (); 947 if (len) 948 { 949 gcc_checking_assert (space (len)); 950 vec_copy_construct (end (), src.address (), len); 951 m_vecpfx.m_num += len; 952 } 953 } 954 955 template<typename T, typename A> 956 inline void 957 vec<T, A, vl_embed>::splice (const vec<T, A, vl_embed> *src) 958 { 959 if (src) 960 splice (*src); 961 } 962 963 964 /* Push OBJ (a new element) onto the end of the vector. There must be 965 sufficient space in the vector. Return a pointer to the slot 966 where OBJ was inserted. */ 967 968 template<typename T, typename A> 969 inline T * 970 vec<T, A, vl_embed>::quick_push (const T &obj) 971 { 972 gcc_checking_assert (space (1)); 973 T *slot = &m_vecdata[m_vecpfx.m_num++]; 974 *slot = obj; 975 return slot; 976 } 977 978 979 /* Pop and return the last element off the end of the vector. */ 980 981 template<typename T, typename A> 982 inline T & 983 vec<T, A, vl_embed>::pop (void) 984 { 985 gcc_checking_assert (length () > 0); 986 return m_vecdata[--m_vecpfx.m_num]; 987 } 988 989 990 /* Set the length of the vector to SIZE. The new length must be less 991 than or equal to the current length. This is an O(1) operation. */ 992 993 template<typename T, typename A> 994 inline void 995 vec<T, A, vl_embed>::truncate (unsigned size) 996 { 997 gcc_checking_assert (length () >= size); 998 m_vecpfx.m_num = size; 999 } 1000 1001 1002 /* Insert an element, OBJ, at the IXth position of this vector. There 1003 must be sufficient space. */ 1004 1005 template<typename T, typename A> 1006 inline void 1007 vec<T, A, vl_embed>::quick_insert (unsigned ix, const T &obj) 1008 { 1009 gcc_checking_assert (length () < allocated ()); 1010 gcc_checking_assert (ix <= length ()); 1011 T *slot = &m_vecdata[ix]; 1012 memmove (slot + 1, slot, (m_vecpfx.m_num++ - ix) * sizeof (T)); 1013 *slot = obj; 1014 } 1015 1016 1017 /* Remove an element from the IXth position of this vector. Ordering of 1018 remaining elements is preserved. This is an O(N) operation due to 1019 memmove. */ 1020 1021 template<typename T, typename A> 1022 inline void 1023 vec<T, A, vl_embed>::ordered_remove (unsigned ix) 1024 { 1025 gcc_checking_assert (ix < length ()); 1026 T *slot = &m_vecdata[ix]; 1027 memmove (slot, slot + 1, (--m_vecpfx.m_num - ix) * sizeof (T)); 1028 } 1029 1030 1031 /* Remove an element from the IXth position of this vector. Ordering of 1032 remaining elements is destroyed. This is an O(1) operation. */ 1033 1034 template<typename T, typename A> 1035 inline void 1036 vec<T, A, vl_embed>::unordered_remove (unsigned ix) 1037 { 1038 gcc_checking_assert (ix < length ()); 1039 m_vecdata[ix] = m_vecdata[--m_vecpfx.m_num]; 1040 } 1041 1042 1043 /* Remove LEN elements starting at the IXth. Ordering is retained. 1044 This is an O(N) operation due to memmove. */ 1045 1046 template<typename T, typename A> 1047 inline void 1048 vec<T, A, vl_embed>::block_remove (unsigned ix, unsigned len) 1049 { 1050 gcc_checking_assert (ix + len <= length ()); 1051 T *slot = &m_vecdata[ix]; 1052 m_vecpfx.m_num -= len; 1053 memmove (slot, slot + len, (m_vecpfx.m_num - ix) * sizeof (T)); 1054 } 1055 1056 1057 /* Sort the contents of this vector with qsort. CMP is the comparison 1058 function to pass to qsort. */ 1059 1060 template<typename T, typename A> 1061 inline void 1062 vec<T, A, vl_embed>::qsort (int (*cmp) (const void *, const void *)) 1063 { 1064 if (length () > 1) 1065 ::qsort (address (), length (), sizeof (T), cmp); 1066 } 1067 1068 1069 /* Search the contents of the sorted vector with a binary search. 1070 CMP is the comparison function to pass to bsearch. */ 1071 1072 template<typename T, typename A> 1073 inline T * 1074 vec<T, A, vl_embed>::bsearch (const void *key, 1075 int (*compar) (const void *, const void *)) 1076 { 1077 const void *base = this->address (); 1078 size_t nmemb = this->length (); 1079 size_t size = sizeof (T); 1080 /* The following is a copy of glibc stdlib-bsearch.h. */ 1081 size_t l, u, idx; 1082 const void *p; 1083 int comparison; 1084 1085 l = 0; 1086 u = nmemb; 1087 while (l < u) 1088 { 1089 idx = (l + u) / 2; 1090 p = (const void *) (((const char *) base) + (idx * size)); 1091 comparison = (*compar) (key, p); 1092 if (comparison < 0) 1093 u = idx; 1094 else if (comparison > 0) 1095 l = idx + 1; 1096 else 1097 return (T *)const_cast<void *>(p); 1098 } 1099 1100 return NULL; 1101 } 1102 1103 /* Return true if SEARCH is an element of V. Note that this is O(N) in the 1104 size of the vector and so should be used with care. */ 1105 1106 template<typename T, typename A> 1107 inline bool 1108 vec<T, A, vl_embed>::contains (const T &search) const 1109 { 1110 unsigned int len = length (); 1111 for (unsigned int i = 0; i < len; i++) 1112 if ((*this)[i] == search) 1113 return true; 1114 1115 return false; 1116 } 1117 1118 /* Find and return the first position in which OBJ could be inserted 1119 without changing the ordering of this vector. LESSTHAN is a 1120 function that returns true if the first argument is strictly less 1121 than the second. */ 1122 1123 template<typename T, typename A> 1124 unsigned 1125 vec<T, A, vl_embed>::lower_bound (T obj, bool (*lessthan)(const T &, const T &)) 1126 const 1127 { 1128 unsigned int len = length (); 1129 unsigned int half, middle; 1130 unsigned int first = 0; 1131 while (len > 0) 1132 { 1133 half = len / 2; 1134 middle = first; 1135 middle += half; 1136 T middle_elem = (*this)[middle]; 1137 if (lessthan (middle_elem, obj)) 1138 { 1139 first = middle; 1140 ++first; 1141 len = len - half - 1; 1142 } 1143 else 1144 len = half; 1145 } 1146 return first; 1147 } 1148 1149 1150 /* Return the number of bytes needed to embed an instance of an 1151 embeddable vec inside another data structure. 1152 1153 Use these methods to determine the required size and initialization 1154 of a vector V of type T embedded within another structure (as the 1155 final member): 1156 1157 size_t vec<T, A, vl_embed>::embedded_size (unsigned alloc); 1158 void v->embedded_init (unsigned alloc, unsigned num); 1159 1160 These allow the caller to perform the memory allocation. */ 1161 1162 template<typename T, typename A> 1163 inline size_t 1164 vec<T, A, vl_embed>::embedded_size (unsigned alloc) 1165 { 1166 typedef vec<T, A, vl_embed> vec_embedded; 1167 return offsetof (vec_embedded, m_vecdata) + alloc * sizeof (T); 1168 } 1169 1170 1171 /* Initialize the vector to contain room for ALLOC elements and 1172 NUM active elements. */ 1173 1174 template<typename T, typename A> 1175 inline void 1176 vec<T, A, vl_embed>::embedded_init (unsigned alloc, unsigned num, unsigned aut) 1177 { 1178 m_vecpfx.m_alloc = alloc; 1179 m_vecpfx.m_using_auto_storage = aut; 1180 m_vecpfx.m_num = num; 1181 } 1182 1183 1184 /* Grow the vector to a specific length. LEN must be as long or longer than 1185 the current length. The new elements are uninitialized. */ 1186 1187 template<typename T, typename A> 1188 inline void 1189 vec<T, A, vl_embed>::quick_grow (unsigned len) 1190 { 1191 gcc_checking_assert (length () <= len && len <= m_vecpfx.m_alloc); 1192 m_vecpfx.m_num = len; 1193 } 1194 1195 1196 /* Grow the vector to a specific length. LEN must be as long or longer than 1197 the current length. The new elements are initialized to zero. */ 1198 1199 template<typename T, typename A> 1200 inline void 1201 vec<T, A, vl_embed>::quick_grow_cleared (unsigned len) 1202 { 1203 unsigned oldlen = length (); 1204 size_t growby = len - oldlen; 1205 quick_grow (len); 1206 if (growby != 0) 1207 vec_default_construct (address () + oldlen, growby); 1208 } 1209 1210 /* Garbage collection support for vec<T, A, vl_embed>. */ 1211 1212 template<typename T> 1213 void 1214 gt_ggc_mx (vec<T, va_gc> *v) 1215 { 1216 extern void gt_ggc_mx (T &); 1217 for (unsigned i = 0; i < v->length (); i++) 1218 gt_ggc_mx ((*v)[i]); 1219 } 1220 1221 template<typename T> 1222 void 1223 gt_ggc_mx (vec<T, va_gc_atomic, vl_embed> *v ATTRIBUTE_UNUSED) 1224 { 1225 /* Nothing to do. Vectors of atomic types wrt GC do not need to 1226 be traversed. */ 1227 } 1228 1229 1230 /* PCH support for vec<T, A, vl_embed>. */ 1231 1232 template<typename T, typename A> 1233 void 1234 gt_pch_nx (vec<T, A, vl_embed> *v) 1235 { 1236 extern void gt_pch_nx (T &); 1237 for (unsigned i = 0; i < v->length (); i++) 1238 gt_pch_nx ((*v)[i]); 1239 } 1240 1241 template<typename T, typename A> 1242 void 1243 gt_pch_nx (vec<T *, A, vl_embed> *v, gt_pointer_operator op, void *cookie) 1244 { 1245 for (unsigned i = 0; i < v->length (); i++) 1246 op (&((*v)[i]), cookie); 1247 } 1248 1249 template<typename T, typename A> 1250 void 1251 gt_pch_nx (vec<T, A, vl_embed> *v, gt_pointer_operator op, void *cookie) 1252 { 1253 extern void gt_pch_nx (T *, gt_pointer_operator, void *); 1254 for (unsigned i = 0; i < v->length (); i++) 1255 gt_pch_nx (&((*v)[i]), op, cookie); 1256 } 1257 1258 1259 /* Space efficient vector. These vectors can grow dynamically and are 1260 allocated together with their control data. They are suited to be 1261 included in data structures. Prior to initial allocation, they 1262 only take a single word of storage. 1263 1264 These vectors are implemented as a pointer to an embeddable vector. 1265 The semantics allow for this pointer to be NULL to represent empty 1266 vectors. This way, empty vectors occupy minimal space in the 1267 structure containing them. 1268 1269 Properties: 1270 1271 - The whole vector and control data are allocated in a single 1272 contiguous block. 1273 - The whole vector may be re-allocated. 1274 - Vector data may grow and shrink. 1275 - Access and manipulation requires a pointer test and 1276 indirection. 1277 - It requires 1 word of storage (prior to vector allocation). 1278 1279 1280 Limitations: 1281 1282 These vectors must be PODs because they are stored in unions. 1283 (http://en.wikipedia.org/wiki/Plain_old_data_structures). 1284 As long as we use C++03, we cannot have constructors nor 1285 destructors in classes that are stored in unions. */ 1286 1287 template<typename T> 1288 struct vec<T, va_heap, vl_ptr> 1289 { 1290 public: 1291 /* Memory allocation and deallocation for the embedded vector. 1292 Needed because we cannot have proper ctors/dtors defined. */ 1293 void create (unsigned nelems CXX_MEM_STAT_INFO); 1294 void release (void); 1295 1296 /* Vector operations. */ 1297 bool exists (void) const 1298 { return m_vec != NULL; } 1299 1300 bool is_empty (void) const 1301 { return m_vec ? m_vec->is_empty () : true; } 1302 1303 unsigned length (void) const 1304 { return m_vec ? m_vec->length () : 0; } 1305 1306 T *address (void) 1307 { return m_vec ? m_vec->m_vecdata : NULL; } 1308 1309 const T *address (void) const 1310 { return m_vec ? m_vec->m_vecdata : NULL; } 1311 1312 T *begin () { return address (); } 1313 const T *begin () const { return address (); } 1314 T *end () { return begin () + length (); } 1315 const T *end () const { return begin () + length (); } 1316 const T &operator[] (unsigned ix) const 1317 { return (*m_vec)[ix]; } 1318 1319 bool operator!=(const vec &other) const 1320 { return !(*this == other); } 1321 1322 bool operator==(const vec &other) const 1323 { return address () == other.address (); } 1324 1325 T &operator[] (unsigned ix) 1326 { return (*m_vec)[ix]; } 1327 1328 T &last (void) 1329 { return m_vec->last (); } 1330 1331 bool space (int nelems) const 1332 { return m_vec ? m_vec->space (nelems) : nelems == 0; } 1333 1334 bool iterate (unsigned ix, T *p) const; 1335 bool iterate (unsigned ix, T **p) const; 1336 vec copy (ALONE_CXX_MEM_STAT_INFO) const; 1337 bool reserve (unsigned, bool = false CXX_MEM_STAT_INFO); 1338 bool reserve_exact (unsigned CXX_MEM_STAT_INFO); 1339 void splice (const vec &); 1340 void safe_splice (const vec & CXX_MEM_STAT_INFO); 1341 T *quick_push (const T &); 1342 T *safe_push (const T &CXX_MEM_STAT_INFO); 1343 T &pop (void); 1344 void truncate (unsigned); 1345 void safe_grow (unsigned CXX_MEM_STAT_INFO); 1346 void safe_grow_cleared (unsigned CXX_MEM_STAT_INFO); 1347 void quick_grow (unsigned); 1348 void quick_grow_cleared (unsigned); 1349 void quick_insert (unsigned, const T &); 1350 void safe_insert (unsigned, const T & CXX_MEM_STAT_INFO); 1351 void ordered_remove (unsigned); 1352 void unordered_remove (unsigned); 1353 void block_remove (unsigned, unsigned); 1354 void qsort (int (*) (const void *, const void *)); 1355 T *bsearch (const void *key, int (*compar)(const void *, const void *)); 1356 unsigned lower_bound (T, bool (*)(const T &, const T &)) const; 1357 bool contains (const T &search) const; 1358 1359 bool using_auto_storage () const; 1360 1361 /* FIXME - This field should be private, but we need to cater to 1362 compilers that have stricter notions of PODness for types. */ 1363 vec<T, va_heap, vl_embed> *m_vec; 1364 }; 1365 1366 1367 /* auto_vec is a subclass of vec that automatically manages creating and 1368 releasing the internal vector. If N is non zero then it has N elements of 1369 internal storage. The default is no internal storage, and you probably only 1370 want to ask for internal storage for vectors on the stack because if the 1371 size of the vector is larger than the internal storage that space is wasted. 1372 */ 1373 template<typename T, size_t N = 0> 1374 class auto_vec : public vec<T, va_heap> 1375 { 1376 public: 1377 auto_vec () 1378 { 1379 m_auto.embedded_init (MAX (N, 2), 0, 1); 1380 this->m_vec = &m_auto; 1381 } 1382 1383 auto_vec (size_t s) 1384 { 1385 if (s > N) 1386 { 1387 this->create (s); 1388 return; 1389 } 1390 1391 m_auto.embedded_init (MAX (N, 2), 0, 1); 1392 this->m_vec = &m_auto; 1393 } 1394 1395 ~auto_vec () 1396 { 1397 this->release (); 1398 } 1399 1400 private: 1401 vec<T, va_heap, vl_embed> m_auto; 1402 T m_data[MAX (N - 1, 1)]; 1403 }; 1404 1405 /* auto_vec is a sub class of vec whose storage is released when it is 1406 destroyed. */ 1407 template<typename T> 1408 class auto_vec<T, 0> : public vec<T, va_heap> 1409 { 1410 public: 1411 auto_vec () { this->m_vec = NULL; } 1412 auto_vec (size_t n) { this->create (n); } 1413 ~auto_vec () { this->release (); } 1414 }; 1415 1416 1417 /* Allocate heap memory for pointer V and create the internal vector 1418 with space for NELEMS elements. If NELEMS is 0, the internal 1419 vector is initialized to empty. */ 1420 1421 template<typename T> 1422 inline void 1423 vec_alloc (vec<T> *&v, unsigned nelems CXX_MEM_STAT_INFO) 1424 { 1425 v = new vec<T>; 1426 v->create (nelems PASS_MEM_STAT); 1427 } 1428 1429 1430 /* Conditionally allocate heap memory for VEC and its internal vector. */ 1431 1432 template<typename T> 1433 inline void 1434 vec_check_alloc (vec<T, va_heap> *&vec, unsigned nelems CXX_MEM_STAT_INFO) 1435 { 1436 if (!vec) 1437 vec_alloc (vec, nelems PASS_MEM_STAT); 1438 } 1439 1440 1441 /* Free the heap memory allocated by vector V and set it to NULL. */ 1442 1443 template<typename T> 1444 inline void 1445 vec_free (vec<T> *&v) 1446 { 1447 if (v == NULL) 1448 return; 1449 1450 v->release (); 1451 delete v; 1452 v = NULL; 1453 } 1454 1455 1456 /* Return iteration condition and update PTR to point to the IX'th 1457 element of this vector. Use this to iterate over the elements of a 1458 vector as follows, 1459 1460 for (ix = 0; v.iterate (ix, &ptr); ix++) 1461 continue; */ 1462 1463 template<typename T> 1464 inline bool 1465 vec<T, va_heap, vl_ptr>::iterate (unsigned ix, T *ptr) const 1466 { 1467 if (m_vec) 1468 return m_vec->iterate (ix, ptr); 1469 else 1470 { 1471 *ptr = 0; 1472 return false; 1473 } 1474 } 1475 1476 1477 /* Return iteration condition and update *PTR to point to the 1478 IX'th element of this vector. Use this to iterate over the 1479 elements of a vector as follows, 1480 1481 for (ix = 0; v->iterate (ix, &ptr); ix++) 1482 continue; 1483 1484 This variant is for vectors of objects. */ 1485 1486 template<typename T> 1487 inline bool 1488 vec<T, va_heap, vl_ptr>::iterate (unsigned ix, T **ptr) const 1489 { 1490 if (m_vec) 1491 return m_vec->iterate (ix, ptr); 1492 else 1493 { 1494 *ptr = 0; 1495 return false; 1496 } 1497 } 1498 1499 1500 /* Convenience macro for forward iteration. */ 1501 #define FOR_EACH_VEC_ELT(V, I, P) \ 1502 for (I = 0; (V).iterate ((I), &(P)); ++(I)) 1503 1504 #define FOR_EACH_VEC_SAFE_ELT(V, I, P) \ 1505 for (I = 0; vec_safe_iterate ((V), (I), &(P)); ++(I)) 1506 1507 /* Likewise, but start from FROM rather than 0. */ 1508 #define FOR_EACH_VEC_ELT_FROM(V, I, P, FROM) \ 1509 for (I = (FROM); (V).iterate ((I), &(P)); ++(I)) 1510 1511 /* Convenience macro for reverse iteration. */ 1512 #define FOR_EACH_VEC_ELT_REVERSE(V, I, P) \ 1513 for (I = (V).length () - 1; \ 1514 (V).iterate ((I), &(P)); \ 1515 (I)--) 1516 1517 #define FOR_EACH_VEC_SAFE_ELT_REVERSE(V, I, P) \ 1518 for (I = vec_safe_length (V) - 1; \ 1519 vec_safe_iterate ((V), (I), &(P)); \ 1520 (I)--) 1521 1522 1523 /* Return a copy of this vector. */ 1524 1525 template<typename T> 1526 inline vec<T, va_heap, vl_ptr> 1527 vec<T, va_heap, vl_ptr>::copy (ALONE_MEM_STAT_DECL) const 1528 { 1529 vec<T, va_heap, vl_ptr> new_vec = vNULL; 1530 if (length ()) 1531 new_vec.m_vec = m_vec->copy (); 1532 return new_vec; 1533 } 1534 1535 1536 /* Ensure that the vector has at least RESERVE slots available (if 1537 EXACT is false), or exactly RESERVE slots available (if EXACT is 1538 true). 1539 1540 This may create additional headroom if EXACT is false. 1541 1542 Note that this can cause the embedded vector to be reallocated. 1543 Returns true iff reallocation actually occurred. */ 1544 1545 template<typename T> 1546 inline bool 1547 vec<T, va_heap, vl_ptr>::reserve (unsigned nelems, bool exact MEM_STAT_DECL) 1548 { 1549 if (space (nelems)) 1550 return false; 1551 1552 /* For now play a game with va_heap::reserve to hide our auto storage if any, 1553 this is necessary because it doesn't have enough information to know the 1554 embedded vector is in auto storage, and so should not be freed. */ 1555 vec<T, va_heap, vl_embed> *oldvec = m_vec; 1556 unsigned int oldsize = 0; 1557 bool handle_auto_vec = m_vec && using_auto_storage (); 1558 if (handle_auto_vec) 1559 { 1560 m_vec = NULL; 1561 oldsize = oldvec->length (); 1562 nelems += oldsize; 1563 } 1564 1565 va_heap::reserve (m_vec, nelems, exact PASS_MEM_STAT); 1566 if (handle_auto_vec) 1567 { 1568 vec_copy_construct (m_vec->address (), oldvec->address (), oldsize); 1569 m_vec->m_vecpfx.m_num = oldsize; 1570 } 1571 1572 return true; 1573 } 1574 1575 1576 /* Ensure that this vector has exactly NELEMS slots available. This 1577 will not create additional headroom. Note this can cause the 1578 embedded vector to be reallocated. Returns true iff reallocation 1579 actually occurred. */ 1580 1581 template<typename T> 1582 inline bool 1583 vec<T, va_heap, vl_ptr>::reserve_exact (unsigned nelems MEM_STAT_DECL) 1584 { 1585 return reserve (nelems, true PASS_MEM_STAT); 1586 } 1587 1588 1589 /* Create the internal vector and reserve NELEMS for it. This is 1590 exactly like vec::reserve, but the internal vector is 1591 unconditionally allocated from scratch. The old one, if it 1592 existed, is lost. */ 1593 1594 template<typename T> 1595 inline void 1596 vec<T, va_heap, vl_ptr>::create (unsigned nelems MEM_STAT_DECL) 1597 { 1598 m_vec = NULL; 1599 if (nelems > 0) 1600 reserve_exact (nelems PASS_MEM_STAT); 1601 } 1602 1603 1604 /* Free the memory occupied by the embedded vector. */ 1605 1606 template<typename T> 1607 inline void 1608 vec<T, va_heap, vl_ptr>::release (void) 1609 { 1610 if (!m_vec) 1611 return; 1612 1613 if (using_auto_storage ()) 1614 { 1615 m_vec->m_vecpfx.m_num = 0; 1616 return; 1617 } 1618 1619 va_heap::release (m_vec); 1620 } 1621 1622 /* Copy the elements from SRC to the end of this vector as if by memcpy. 1623 SRC and this vector must be allocated with the same memory 1624 allocation mechanism. This vector is assumed to have sufficient 1625 headroom available. */ 1626 1627 template<typename T> 1628 inline void 1629 vec<T, va_heap, vl_ptr>::splice (const vec<T, va_heap, vl_ptr> &src) 1630 { 1631 if (src.m_vec) 1632 m_vec->splice (*(src.m_vec)); 1633 } 1634 1635 1636 /* Copy the elements in SRC to the end of this vector as if by memcpy. 1637 SRC and this vector must be allocated with the same mechanism. 1638 If there is not enough headroom in this vector, it will be reallocated 1639 as needed. */ 1640 1641 template<typename T> 1642 inline void 1643 vec<T, va_heap, vl_ptr>::safe_splice (const vec<T, va_heap, vl_ptr> &src 1644 MEM_STAT_DECL) 1645 { 1646 if (src.length ()) 1647 { 1648 reserve_exact (src.length ()); 1649 splice (src); 1650 } 1651 } 1652 1653 1654 /* Push OBJ (a new element) onto the end of the vector. There must be 1655 sufficient space in the vector. Return a pointer to the slot 1656 where OBJ was inserted. */ 1657 1658 template<typename T> 1659 inline T * 1660 vec<T, va_heap, vl_ptr>::quick_push (const T &obj) 1661 { 1662 return m_vec->quick_push (obj); 1663 } 1664 1665 1666 /* Push a new element OBJ onto the end of this vector. Reallocates 1667 the embedded vector, if needed. Return a pointer to the slot where 1668 OBJ was inserted. */ 1669 1670 template<typename T> 1671 inline T * 1672 vec<T, va_heap, vl_ptr>::safe_push (const T &obj MEM_STAT_DECL) 1673 { 1674 reserve (1, false PASS_MEM_STAT); 1675 return quick_push (obj); 1676 } 1677 1678 1679 /* Pop and return the last element off the end of the vector. */ 1680 1681 template<typename T> 1682 inline T & 1683 vec<T, va_heap, vl_ptr>::pop (void) 1684 { 1685 return m_vec->pop (); 1686 } 1687 1688 1689 /* Set the length of the vector to LEN. The new length must be less 1690 than or equal to the current length. This is an O(1) operation. */ 1691 1692 template<typename T> 1693 inline void 1694 vec<T, va_heap, vl_ptr>::truncate (unsigned size) 1695 { 1696 if (m_vec) 1697 m_vec->truncate (size); 1698 else 1699 gcc_checking_assert (size == 0); 1700 } 1701 1702 1703 /* Grow the vector to a specific length. LEN must be as long or 1704 longer than the current length. The new elements are 1705 uninitialized. Reallocate the internal vector, if needed. */ 1706 1707 template<typename T> 1708 inline void 1709 vec<T, va_heap, vl_ptr>::safe_grow (unsigned len MEM_STAT_DECL) 1710 { 1711 unsigned oldlen = length (); 1712 gcc_checking_assert (oldlen <= len); 1713 reserve_exact (len - oldlen PASS_MEM_STAT); 1714 if (m_vec) 1715 m_vec->quick_grow (len); 1716 else 1717 gcc_checking_assert (len == 0); 1718 } 1719 1720 1721 /* Grow the embedded vector to a specific length. LEN must be as 1722 long or longer than the current length. The new elements are 1723 initialized to zero. Reallocate the internal vector, if needed. */ 1724 1725 template<typename T> 1726 inline void 1727 vec<T, va_heap, vl_ptr>::safe_grow_cleared (unsigned len MEM_STAT_DECL) 1728 { 1729 unsigned oldlen = length (); 1730 size_t growby = len - oldlen; 1731 safe_grow (len PASS_MEM_STAT); 1732 if (growby != 0) 1733 vec_default_construct (address () + oldlen, growby); 1734 } 1735 1736 1737 /* Same as vec::safe_grow but without reallocation of the internal vector. 1738 If the vector cannot be extended, a runtime assertion will be triggered. */ 1739 1740 template<typename T> 1741 inline void 1742 vec<T, va_heap, vl_ptr>::quick_grow (unsigned len) 1743 { 1744 gcc_checking_assert (m_vec); 1745 m_vec->quick_grow (len); 1746 } 1747 1748 1749 /* Same as vec::quick_grow_cleared but without reallocation of the 1750 internal vector. If the vector cannot be extended, a runtime 1751 assertion will be triggered. */ 1752 1753 template<typename T> 1754 inline void 1755 vec<T, va_heap, vl_ptr>::quick_grow_cleared (unsigned len) 1756 { 1757 gcc_checking_assert (m_vec); 1758 m_vec->quick_grow_cleared (len); 1759 } 1760 1761 1762 /* Insert an element, OBJ, at the IXth position of this vector. There 1763 must be sufficient space. */ 1764 1765 template<typename T> 1766 inline void 1767 vec<T, va_heap, vl_ptr>::quick_insert (unsigned ix, const T &obj) 1768 { 1769 m_vec->quick_insert (ix, obj); 1770 } 1771 1772 1773 /* Insert an element, OBJ, at the IXth position of the vector. 1774 Reallocate the embedded vector, if necessary. */ 1775 1776 template<typename T> 1777 inline void 1778 vec<T, va_heap, vl_ptr>::safe_insert (unsigned ix, const T &obj MEM_STAT_DECL) 1779 { 1780 reserve (1, false PASS_MEM_STAT); 1781 quick_insert (ix, obj); 1782 } 1783 1784 1785 /* Remove an element from the IXth position of this vector. Ordering of 1786 remaining elements is preserved. This is an O(N) operation due to 1787 a memmove. */ 1788 1789 template<typename T> 1790 inline void 1791 vec<T, va_heap, vl_ptr>::ordered_remove (unsigned ix) 1792 { 1793 m_vec->ordered_remove (ix); 1794 } 1795 1796 1797 /* Remove an element from the IXth position of this vector. Ordering 1798 of remaining elements is destroyed. This is an O(1) operation. */ 1799 1800 template<typename T> 1801 inline void 1802 vec<T, va_heap, vl_ptr>::unordered_remove (unsigned ix) 1803 { 1804 m_vec->unordered_remove (ix); 1805 } 1806 1807 1808 /* Remove LEN elements starting at the IXth. Ordering is retained. 1809 This is an O(N) operation due to memmove. */ 1810 1811 template<typename T> 1812 inline void 1813 vec<T, va_heap, vl_ptr>::block_remove (unsigned ix, unsigned len) 1814 { 1815 m_vec->block_remove (ix, len); 1816 } 1817 1818 1819 /* Sort the contents of this vector with qsort. CMP is the comparison 1820 function to pass to qsort. */ 1821 1822 template<typename T> 1823 inline void 1824 vec<T, va_heap, vl_ptr>::qsort (int (*cmp) (const void *, const void *)) 1825 { 1826 if (m_vec) 1827 m_vec->qsort (cmp); 1828 } 1829 1830 1831 /* Search the contents of the sorted vector with a binary search. 1832 CMP is the comparison function to pass to bsearch. */ 1833 1834 template<typename T> 1835 inline T * 1836 vec<T, va_heap, vl_ptr>::bsearch (const void *key, 1837 int (*cmp) (const void *, const void *)) 1838 { 1839 if (m_vec) 1840 return m_vec->bsearch (key, cmp); 1841 return NULL; 1842 } 1843 1844 1845 /* Find and return the first position in which OBJ could be inserted 1846 without changing the ordering of this vector. LESSTHAN is a 1847 function that returns true if the first argument is strictly less 1848 than the second. */ 1849 1850 template<typename T> 1851 inline unsigned 1852 vec<T, va_heap, vl_ptr>::lower_bound (T obj, 1853 bool (*lessthan)(const T &, const T &)) 1854 const 1855 { 1856 return m_vec ? m_vec->lower_bound (obj, lessthan) : 0; 1857 } 1858 1859 /* Return true if SEARCH is an element of V. Note that this is O(N) in the 1860 size of the vector and so should be used with care. */ 1861 1862 template<typename T> 1863 inline bool 1864 vec<T, va_heap, vl_ptr>::contains (const T &search) const 1865 { 1866 return m_vec ? m_vec->contains (search) : false; 1867 } 1868 1869 template<typename T> 1870 inline bool 1871 vec<T, va_heap, vl_ptr>::using_auto_storage () const 1872 { 1873 return m_vec->m_vecpfx.m_using_auto_storage; 1874 } 1875 1876 /* Release VEC and call release of all element vectors. */ 1877 1878 template<typename T> 1879 inline void 1880 release_vec_vec (vec<vec<T> > &vec) 1881 { 1882 for (unsigned i = 0; i < vec.length (); i++) 1883 vec[i].release (); 1884 1885 vec.release (); 1886 } 1887 1888 #if (GCC_VERSION >= 3000) 1889 # pragma GCC poison m_vec m_vecpfx m_vecdata 1890 #endif 1891 1892 #endif // GCC_VEC_H 1893