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