Mercurial > hg > CbC > CbC_gcc
annotate gcc/vec.h @ 131:84e7813d76e9
gcc-8.2
| author | mir3636 |
|---|---|
| date | Thu, 25 Oct 2018 07:37:49 +0900 |
| parents | 04ced10e8804 |
| children | 1830386684a0 |
| rev | line source |
|---|---|
| 0 | 1 /* Vector API for GNU compiler. |
| 131 | 2 Copyright (C) 2004-2018 Free Software Foundation, Inc. |
| 0 | 3 Contributed by Nathan Sidwell <nathan@codesourcery.com> |
| 111 | 4 Re-implemented in C++ by Diego Novillo <dnovillo@google.com> |
| 0 | 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 | |
| 111 | 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.*/ | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
29 |
| 111 | 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); | |
| 0 | 33 |
| 111 | 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. | |
| 0 | 39 |
| 111 | 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. | |
| 0 | 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 | |
| 111 | 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. | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
108 |
| 0 | 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. | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
113 |
| 111 | 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). | |
| 0 | 166 |
| 167 An example of their use would be, | |
| 168 | |
| 169 struct my_struct { | |
| 111 | 170 // A space-efficient vector of tree pointers in GC memory. |
| 171 vec<tree, va_gc, vl_ptr> v; | |
| 0 | 172 }; |
| 173 | |
| 174 struct my_struct *s; | |
| 175 | |
| 111 | 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++) | |
| 0 | 179 { do something with elt } |
| 180 */ | |
| 181 | |
| 111 | 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); | |
| 0 | 285 |
| 111 | 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. */ | |
| 0 | 333 |
| 111 | 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. */ | |
| 0 | 348 |
| 111 | 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 }; | |
| 0 | 390 |
| 391 | |
| 111 | 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 | |
| 131 | 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 | |
| 111 | 487 /* Default-construct N elements in DST. */ |
| 488 | |
| 489 template <typename T> | |
| 490 inline void | |
| 491 vec_default_construct (T *dst, unsigned n) | |
| 492 { | |
| 131 | 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 | |
| 111 | 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). */ | |
| 0 | 561 |
| 111 | 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 | |
| 0 | 627 |
| 111 | 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 } | |
| 0 | 706 |
| 707 | |
| 111 | 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 | |
| 0 | 719 |
| 111 | 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 } | |
| 0 | 744 |
| 111 | 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 | |
| 0 | 758 |
| 111 | 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 | |
| 0 | 791 |
| 111 | 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 } | |
| 0 | 799 |
| 111 | 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. */ | |
| 0 | 828 |
| 111 | 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. */ | |
| 0 | 847 |
| 111 | 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 | |
| 0 | 856 |
| 111 | 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++) | |
| 0 | 876 continue; */ |
| 877 | |
| 111 | 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. */ | |
| 0 | 903 |
| 111 | 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. */ | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
922 |
| 111 | 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. */ | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
941 |
| 111 | 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 | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
978 |
| 111 | 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. */ | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
992 |
| 111 | 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 | |
| 0 | 1016 |
| 111 | 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 | |
| 131 | 1031 /* Remove elements in [START, END) from VEC for which COND holds. Ordering of |
| 1032 remaining elements is preserved. This is an O(N) operation. */ | |
| 1033 | |
| 1034 #define VEC_ORDERED_REMOVE_IF_FROM_TO(vec, read_index, write_index, \ | |
| 1035 elem_ptr, start, end, cond) \ | |
| 1036 { \ | |
| 1037 gcc_assert ((end) <= (vec).length ()); \ | |
| 1038 for (read_index = write_index = (start); read_index < (end); \ | |
| 1039 ++read_index) \ | |
| 1040 { \ | |
| 1041 elem_ptr = &(vec)[read_index]; \ | |
| 1042 bool remove_p = (cond); \ | |
| 1043 if (remove_p) \ | |
| 1044 continue; \ | |
| 1045 \ | |
| 1046 if (read_index != write_index) \ | |
| 1047 (vec)[write_index] = (vec)[read_index]; \ | |
| 1048 \ | |
| 1049 write_index++; \ | |
| 1050 } \ | |
| 1051 \ | |
| 1052 if (read_index - write_index > 0) \ | |
| 1053 (vec).block_remove (write_index, read_index - write_index); \ | |
| 1054 } | |
| 1055 | |
| 1056 | |
| 1057 /* Remove elements from VEC for which COND holds. Ordering of remaining | |
| 1058 elements is preserved. This is an O(N) operation. */ | |
| 1059 | |
| 1060 #define VEC_ORDERED_REMOVE_IF(vec, read_index, write_index, elem_ptr, \ | |
| 1061 cond) \ | |
| 1062 VEC_ORDERED_REMOVE_IF_FROM_TO ((vec), read_index, write_index, \ | |
| 1063 elem_ptr, 0, (vec).length (), (cond)) | |
| 1064 | |
| 111 | 1065 /* Remove an element from the IXth position of this vector. Ordering of |
| 1066 remaining elements is destroyed. This is an O(1) operation. */ | |
| 1067 | |
| 1068 template<typename T, typename A> | |
| 1069 inline void | |
| 1070 vec<T, A, vl_embed>::unordered_remove (unsigned ix) | |
| 1071 { | |
| 1072 gcc_checking_assert (ix < length ()); | |
| 1073 m_vecdata[ix] = m_vecdata[--m_vecpfx.m_num]; | |
| 1074 } | |
| 1075 | |
| 1076 | |
| 1077 /* Remove LEN elements starting at the IXth. Ordering is retained. | |
| 1078 This is an O(N) operation due to memmove. */ | |
| 0 | 1079 |
| 111 | 1080 template<typename T, typename A> |
| 1081 inline void | |
| 1082 vec<T, A, vl_embed>::block_remove (unsigned ix, unsigned len) | |
| 1083 { | |
| 1084 gcc_checking_assert (ix + len <= length ()); | |
| 1085 T *slot = &m_vecdata[ix]; | |
| 1086 m_vecpfx.m_num -= len; | |
| 1087 memmove (slot, slot + len, (m_vecpfx.m_num - ix) * sizeof (T)); | |
| 1088 } | |
| 1089 | |
| 1090 | |
| 1091 /* Sort the contents of this vector with qsort. CMP is the comparison | |
| 1092 function to pass to qsort. */ | |
| 0 | 1093 |
| 111 | 1094 template<typename T, typename A> |
| 1095 inline void | |
| 1096 vec<T, A, vl_embed>::qsort (int (*cmp) (const void *, const void *)) | |
| 1097 { | |
| 1098 if (length () > 1) | |
| 1099 ::qsort (address (), length (), sizeof (T), cmp); | |
| 1100 } | |
| 1101 | |
| 1102 | |
| 1103 /* Search the contents of the sorted vector with a binary search. | |
| 1104 CMP is the comparison function to pass to bsearch. */ | |
| 1105 | |
| 1106 template<typename T, typename A> | |
| 1107 inline T * | |
| 1108 vec<T, A, vl_embed>::bsearch (const void *key, | |
| 1109 int (*compar) (const void *, const void *)) | |
| 1110 { | |
| 1111 const void *base = this->address (); | |
| 1112 size_t nmemb = this->length (); | |
| 1113 size_t size = sizeof (T); | |
| 1114 /* The following is a copy of glibc stdlib-bsearch.h. */ | |
| 1115 size_t l, u, idx; | |
| 1116 const void *p; | |
| 1117 int comparison; | |
| 0 | 1118 |
| 111 | 1119 l = 0; |
| 1120 u = nmemb; | |
| 1121 while (l < u) | |
| 1122 { | |
| 1123 idx = (l + u) / 2; | |
| 1124 p = (const void *) (((const char *) base) + (idx * size)); | |
| 1125 comparison = (*compar) (key, p); | |
| 1126 if (comparison < 0) | |
| 1127 u = idx; | |
| 1128 else if (comparison > 0) | |
| 1129 l = idx + 1; | |
| 1130 else | |
| 1131 return (T *)const_cast<void *>(p); | |
| 1132 } | |
| 0 | 1133 |
| 111 | 1134 return NULL; |
| 1135 } | |
| 1136 | |
| 1137 /* Return true if SEARCH is an element of V. Note that this is O(N) in the | |
| 1138 size of the vector and so should be used with care. */ | |
| 1139 | |
| 1140 template<typename T, typename A> | |
| 1141 inline bool | |
| 1142 vec<T, A, vl_embed>::contains (const T &search) const | |
| 1143 { | |
| 1144 unsigned int len = length (); | |
| 1145 for (unsigned int i = 0; i < len; i++) | |
| 1146 if ((*this)[i] == search) | |
| 1147 return true; | |
| 1148 | |
| 1149 return false; | |
| 1150 } | |
| 0 | 1151 |
| 111 | 1152 /* Find and return the first position in which OBJ could be inserted |
| 1153 without changing the ordering of this vector. LESSTHAN is a | |
| 1154 function that returns true if the first argument is strictly less | |
| 1155 than the second. */ | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1156 |
| 111 | 1157 template<typename T, typename A> |
| 1158 unsigned | |
| 1159 vec<T, A, vl_embed>::lower_bound (T obj, bool (*lessthan)(const T &, const T &)) | |
| 1160 const | |
| 1161 { | |
| 1162 unsigned int len = length (); | |
| 1163 unsigned int half, middle; | |
| 1164 unsigned int first = 0; | |
| 1165 while (len > 0) | |
| 1166 { | |
| 1167 half = len / 2; | |
| 1168 middle = first; | |
| 1169 middle += half; | |
| 1170 T middle_elem = (*this)[middle]; | |
| 1171 if (lessthan (middle_elem, obj)) | |
| 1172 { | |
| 1173 first = middle; | |
| 1174 ++first; | |
| 1175 len = len - half - 1; | |
| 1176 } | |
| 1177 else | |
| 1178 len = half; | |
| 1179 } | |
| 1180 return first; | |
| 1181 } | |
| 1182 | |
| 1183 | |
| 1184 /* Return the number of bytes needed to embed an instance of an | |
| 1185 embeddable vec inside another data structure. | |
| 1186 | |
| 1187 Use these methods to determine the required size and initialization | |
| 1188 of a vector V of type T embedded within another structure (as the | |
| 1189 final member): | |
| 1190 | |
| 1191 size_t vec<T, A, vl_embed>::embedded_size (unsigned alloc); | |
| 1192 void v->embedded_init (unsigned alloc, unsigned num); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1193 |
| 0 | 1194 These allow the caller to perform the memory allocation. */ |
| 1195 | |
| 111 | 1196 template<typename T, typename A> |
| 1197 inline size_t | |
| 1198 vec<T, A, vl_embed>::embedded_size (unsigned alloc) | |
| 1199 { | |
| 1200 typedef vec<T, A, vl_embed> vec_embedded; | |
| 1201 return offsetof (vec_embedded, m_vecdata) + alloc * sizeof (T); | |
| 1202 } | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1203 |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1204 |
| 111 | 1205 /* Initialize the vector to contain room for ALLOC elements and |
| 1206 NUM active elements. */ | |
| 0 | 1207 |
| 111 | 1208 template<typename T, typename A> |
| 1209 inline void | |
| 1210 vec<T, A, vl_embed>::embedded_init (unsigned alloc, unsigned num, unsigned aut) | |
| 1211 { | |
| 1212 m_vecpfx.m_alloc = alloc; | |
| 1213 m_vecpfx.m_using_auto_storage = aut; | |
| 1214 m_vecpfx.m_num = num; | |
| 1215 } | |
| 0 | 1216 |
| 1217 | |
| 111 | 1218 /* Grow the vector to a specific length. LEN must be as long or longer than |
| 1219 the current length. The new elements are uninitialized. */ | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1220 |
| 111 | 1221 template<typename T, typename A> |
| 1222 inline void | |
| 1223 vec<T, A, vl_embed>::quick_grow (unsigned len) | |
| 1224 { | |
| 1225 gcc_checking_assert (length () <= len && len <= m_vecpfx.m_alloc); | |
| 1226 m_vecpfx.m_num = len; | |
| 1227 } | |
| 0 | 1228 |
| 1229 | |
| 111 | 1230 /* Grow the vector to a specific length. LEN must be as long or longer than |
| 1231 the current length. The new elements are initialized to zero. */ | |
| 0 | 1232 |
| 111 | 1233 template<typename T, typename A> |
| 1234 inline void | |
| 1235 vec<T, A, vl_embed>::quick_grow_cleared (unsigned len) | |
| 1236 { | |
| 1237 unsigned oldlen = length (); | |
| 1238 size_t growby = len - oldlen; | |
| 1239 quick_grow (len); | |
| 1240 if (growby != 0) | |
| 1241 vec_default_construct (address () + oldlen, growby); | |
| 1242 } | |
| 0 | 1243 |
| 111 | 1244 /* Garbage collection support for vec<T, A, vl_embed>. */ |
| 0 | 1245 |
| 111 | 1246 template<typename T> |
| 1247 void | |
| 1248 gt_ggc_mx (vec<T, va_gc> *v) | |
| 1249 { | |
| 1250 extern void gt_ggc_mx (T &); | |
| 1251 for (unsigned i = 0; i < v->length (); i++) | |
| 1252 gt_ggc_mx ((*v)[i]); | |
| 1253 } | |
| 0 | 1254 |
| 111 | 1255 template<typename T> |
| 1256 void | |
| 1257 gt_ggc_mx (vec<T, va_gc_atomic, vl_embed> *v ATTRIBUTE_UNUSED) | |
| 1258 { | |
| 1259 /* Nothing to do. Vectors of atomic types wrt GC do not need to | |
| 1260 be traversed. */ | |
| 1261 } | |
| 1262 | |
| 1263 | |
| 1264 /* PCH support for vec<T, A, vl_embed>. */ | |
| 1265 | |
| 1266 template<typename T, typename A> | |
| 1267 void | |
| 1268 gt_pch_nx (vec<T, A, vl_embed> *v) | |
| 1269 { | |
| 1270 extern void gt_pch_nx (T &); | |
| 1271 for (unsigned i = 0; i < v->length (); i++) | |
| 1272 gt_pch_nx ((*v)[i]); | |
| 1273 } | |
| 1274 | |
| 1275 template<typename T, typename A> | |
| 1276 void | |
| 1277 gt_pch_nx (vec<T *, A, vl_embed> *v, gt_pointer_operator op, void *cookie) | |
| 1278 { | |
| 1279 for (unsigned i = 0; i < v->length (); i++) | |
| 1280 op (&((*v)[i]), cookie); | |
| 1281 } | |
| 1282 | |
| 1283 template<typename T, typename A> | |
| 1284 void | |
| 1285 gt_pch_nx (vec<T, A, vl_embed> *v, gt_pointer_operator op, void *cookie) | |
| 1286 { | |
| 1287 extern void gt_pch_nx (T *, gt_pointer_operator, void *); | |
| 1288 for (unsigned i = 0; i < v->length (); i++) | |
| 1289 gt_pch_nx (&((*v)[i]), op, cookie); | |
| 0 | 1290 } |
| 1291 | |
| 111 | 1292 |
| 1293 /* Space efficient vector. These vectors can grow dynamically and are | |
| 1294 allocated together with their control data. They are suited to be | |
| 1295 included in data structures. Prior to initial allocation, they | |
| 1296 only take a single word of storage. | |
| 1297 | |
| 1298 These vectors are implemented as a pointer to an embeddable vector. | |
| 1299 The semantics allow for this pointer to be NULL to represent empty | |
| 1300 vectors. This way, empty vectors occupy minimal space in the | |
| 1301 structure containing them. | |
| 1302 | |
| 1303 Properties: | |
| 1304 | |
| 1305 - The whole vector and control data are allocated in a single | |
| 1306 contiguous block. | |
| 1307 - The whole vector may be re-allocated. | |
| 1308 - Vector data may grow and shrink. | |
| 1309 - Access and manipulation requires a pointer test and | |
| 1310 indirection. | |
| 1311 - It requires 1 word of storage (prior to vector allocation). | |
| 1312 | |
| 1313 | |
| 1314 Limitations: | |
| 1315 | |
| 1316 These vectors must be PODs because they are stored in unions. | |
| 1317 (http://en.wikipedia.org/wiki/Plain_old_data_structures). | |
| 1318 As long as we use C++03, we cannot have constructors nor | |
| 1319 destructors in classes that are stored in unions. */ | |
| 1320 | |
| 1321 template<typename T> | |
| 1322 struct vec<T, va_heap, vl_ptr> | |
| 1323 { | |
| 1324 public: | |
| 1325 /* Memory allocation and deallocation for the embedded vector. | |
| 1326 Needed because we cannot have proper ctors/dtors defined. */ | |
| 1327 void create (unsigned nelems CXX_MEM_STAT_INFO); | |
| 1328 void release (void); | |
| 1329 | |
| 1330 /* Vector operations. */ | |
| 1331 bool exists (void) const | |
| 1332 { return m_vec != NULL; } | |
| 1333 | |
| 1334 bool is_empty (void) const | |
| 1335 { return m_vec ? m_vec->is_empty () : true; } | |
| 1336 | |
| 1337 unsigned length (void) const | |
| 1338 { return m_vec ? m_vec->length () : 0; } | |
| 1339 | |
| 1340 T *address (void) | |
| 1341 { return m_vec ? m_vec->m_vecdata : NULL; } | |
| 1342 | |
| 1343 const T *address (void) const | |
| 1344 { return m_vec ? m_vec->m_vecdata : NULL; } | |
| 1345 | |
| 1346 T *begin () { return address (); } | |
| 1347 const T *begin () const { return address (); } | |
| 1348 T *end () { return begin () + length (); } | |
| 1349 const T *end () const { return begin () + length (); } | |
| 1350 const T &operator[] (unsigned ix) const | |
| 1351 { return (*m_vec)[ix]; } | |
| 1352 | |
| 1353 bool operator!=(const vec &other) const | |
| 1354 { return !(*this == other); } | |
| 1355 | |
| 1356 bool operator==(const vec &other) const | |
| 1357 { return address () == other.address (); } | |
| 1358 | |
| 1359 T &operator[] (unsigned ix) | |
| 1360 { return (*m_vec)[ix]; } | |
| 1361 | |
| 1362 T &last (void) | |
| 1363 { return m_vec->last (); } | |
| 1364 | |
| 1365 bool space (int nelems) const | |
| 1366 { return m_vec ? m_vec->space (nelems) : nelems == 0; } | |
| 1367 | |
| 1368 bool iterate (unsigned ix, T *p) const; | |
| 1369 bool iterate (unsigned ix, T **p) const; | |
| 1370 vec copy (ALONE_CXX_MEM_STAT_INFO) const; | |
| 1371 bool reserve (unsigned, bool = false CXX_MEM_STAT_INFO); | |
| 1372 bool reserve_exact (unsigned CXX_MEM_STAT_INFO); | |
| 1373 void splice (const vec &); | |
| 1374 void safe_splice (const vec & CXX_MEM_STAT_INFO); | |
| 1375 T *quick_push (const T &); | |
| 1376 T *safe_push (const T &CXX_MEM_STAT_INFO); | |
| 1377 T &pop (void); | |
| 1378 void truncate (unsigned); | |
| 1379 void safe_grow (unsigned CXX_MEM_STAT_INFO); | |
| 1380 void safe_grow_cleared (unsigned CXX_MEM_STAT_INFO); | |
| 1381 void quick_grow (unsigned); | |
| 1382 void quick_grow_cleared (unsigned); | |
| 1383 void quick_insert (unsigned, const T &); | |
| 1384 void safe_insert (unsigned, const T & CXX_MEM_STAT_INFO); | |
| 1385 void ordered_remove (unsigned); | |
| 1386 void unordered_remove (unsigned); | |
| 1387 void block_remove (unsigned, unsigned); | |
| 1388 void qsort (int (*) (const void *, const void *)); | |
| 1389 T *bsearch (const void *key, int (*compar)(const void *, const void *)); | |
| 1390 unsigned lower_bound (T, bool (*)(const T &, const T &)) const; | |
| 1391 bool contains (const T &search) const; | |
| 131 | 1392 void reverse (void); |
| 111 | 1393 |
| 1394 bool using_auto_storage () const; | |
| 1395 | |
| 1396 /* FIXME - This field should be private, but we need to cater to | |
| 1397 compilers that have stricter notions of PODness for types. */ | |
| 1398 vec<T, va_heap, vl_embed> *m_vec; | |
| 1399 }; | |
| 1400 | |
| 1401 | |
| 1402 /* auto_vec is a subclass of vec that automatically manages creating and | |
| 1403 releasing the internal vector. If N is non zero then it has N elements of | |
| 1404 internal storage. The default is no internal storage, and you probably only | |
| 1405 want to ask for internal storage for vectors on the stack because if the | |
| 1406 size of the vector is larger than the internal storage that space is wasted. | |
| 1407 */ | |
| 1408 template<typename T, size_t N = 0> | |
| 1409 class auto_vec : public vec<T, va_heap> | |
| 1410 { | |
| 1411 public: | |
| 1412 auto_vec () | |
| 1413 { | |
| 1414 m_auto.embedded_init (MAX (N, 2), 0, 1); | |
| 1415 this->m_vec = &m_auto; | |
| 1416 } | |
| 1417 | |
| 1418 auto_vec (size_t s) | |
| 1419 { | |
| 1420 if (s > N) | |
| 1421 { | |
| 1422 this->create (s); | |
| 1423 return; | |
| 1424 } | |
| 1425 | |
| 1426 m_auto.embedded_init (MAX (N, 2), 0, 1); | |
| 1427 this->m_vec = &m_auto; | |
| 1428 } | |
| 1429 | |
| 1430 ~auto_vec () | |
| 1431 { | |
| 1432 this->release (); | |
| 1433 } | |
| 1434 | |
| 1435 private: | |
| 1436 vec<T, va_heap, vl_embed> m_auto; | |
| 1437 T m_data[MAX (N - 1, 1)]; | |
| 1438 }; | |
| 1439 | |
| 1440 /* auto_vec is a sub class of vec whose storage is released when it is | |
| 1441 destroyed. */ | |
| 1442 template<typename T> | |
| 1443 class auto_vec<T, 0> : public vec<T, va_heap> | |
| 1444 { | |
| 1445 public: | |
| 1446 auto_vec () { this->m_vec = NULL; } | |
| 1447 auto_vec (size_t n) { this->create (n); } | |
| 1448 ~auto_vec () { this->release (); } | |
| 1449 }; | |
| 1450 | |
| 1451 | |
| 1452 /* Allocate heap memory for pointer V and create the internal vector | |
| 1453 with space for NELEMS elements. If NELEMS is 0, the internal | |
| 1454 vector is initialized to empty. */ | |
| 1455 | |
| 1456 template<typename T> | |
| 1457 inline void | |
| 1458 vec_alloc (vec<T> *&v, unsigned nelems CXX_MEM_STAT_INFO) | |
| 1459 { | |
| 1460 v = new vec<T>; | |
| 1461 v->create (nelems PASS_MEM_STAT); | |
| 1462 } | |
| 1463 | |
| 1464 | |
| 131 | 1465 /* A subclass of auto_vec <char *> that frees all of its elements on |
| 1466 deletion. */ | |
| 1467 | |
| 1468 class auto_string_vec : public auto_vec <char *> | |
| 1469 { | |
| 1470 public: | |
| 1471 ~auto_string_vec (); | |
| 1472 }; | |
| 1473 | |
| 111 | 1474 /* Conditionally allocate heap memory for VEC and its internal vector. */ |
| 1475 | |
| 1476 template<typename T> | |
| 1477 inline void | |
| 1478 vec_check_alloc (vec<T, va_heap> *&vec, unsigned nelems CXX_MEM_STAT_INFO) | |
| 1479 { | |
| 1480 if (!vec) | |
| 1481 vec_alloc (vec, nelems PASS_MEM_STAT); | |
| 1482 } | |
| 1483 | |
| 1484 | |
| 1485 /* Free the heap memory allocated by vector V and set it to NULL. */ | |
| 1486 | |
| 1487 template<typename T> | |
| 1488 inline void | |
| 1489 vec_free (vec<T> *&v) | |
| 1490 { | |
| 1491 if (v == NULL) | |
| 1492 return; | |
| 1493 | |
| 1494 v->release (); | |
| 1495 delete v; | |
| 1496 v = NULL; | |
| 1497 } | |
| 1498 | |
| 1499 | |
| 1500 /* Return iteration condition and update PTR to point to the IX'th | |
| 1501 element of this vector. Use this to iterate over the elements of a | |
| 1502 vector as follows, | |
| 1503 | |
| 1504 for (ix = 0; v.iterate (ix, &ptr); ix++) | |
| 1505 continue; */ | |
| 1506 | |
| 1507 template<typename T> | |
| 1508 inline bool | |
| 1509 vec<T, va_heap, vl_ptr>::iterate (unsigned ix, T *ptr) const | |
| 1510 { | |
| 1511 if (m_vec) | |
| 1512 return m_vec->iterate (ix, ptr); | |
| 1513 else | |
| 1514 { | |
| 1515 *ptr = 0; | |
| 1516 return false; | |
| 1517 } | |
| 1518 } | |
| 1519 | |
| 1520 | |
| 1521 /* Return iteration condition and update *PTR to point to the | |
| 1522 IX'th element of this vector. Use this to iterate over the | |
| 1523 elements of a vector as follows, | |
| 1524 | |
| 1525 for (ix = 0; v->iterate (ix, &ptr); ix++) | |
| 1526 continue; | |
| 1527 | |
| 1528 This variant is for vectors of objects. */ | |
| 1529 | |
| 1530 template<typename T> | |
| 1531 inline bool | |
| 1532 vec<T, va_heap, vl_ptr>::iterate (unsigned ix, T **ptr) const | |
| 1533 { | |
| 1534 if (m_vec) | |
| 1535 return m_vec->iterate (ix, ptr); | |
| 1536 else | |
| 1537 { | |
| 1538 *ptr = 0; | |
| 1539 return false; | |
| 1540 } | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1541 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1542 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1543 |
| 111 | 1544 /* Convenience macro for forward iteration. */ |
| 1545 #define FOR_EACH_VEC_ELT(V, I, P) \ | |
| 1546 for (I = 0; (V).iterate ((I), &(P)); ++(I)) | |
| 1547 | |
| 1548 #define FOR_EACH_VEC_SAFE_ELT(V, I, P) \ | |
| 1549 for (I = 0; vec_safe_iterate ((V), (I), &(P)); ++(I)) | |
| 1550 | |
| 1551 /* Likewise, but start from FROM rather than 0. */ | |
| 1552 #define FOR_EACH_VEC_ELT_FROM(V, I, P, FROM) \ | |
| 1553 for (I = (FROM); (V).iterate ((I), &(P)); ++(I)) | |
| 1554 | |
| 1555 /* Convenience macro for reverse iteration. */ | |
| 1556 #define FOR_EACH_VEC_ELT_REVERSE(V, I, P) \ | |
| 1557 for (I = (V).length () - 1; \ | |
| 1558 (V).iterate ((I), &(P)); \ | |
| 1559 (I)--) | |
| 1560 | |
| 1561 #define FOR_EACH_VEC_SAFE_ELT_REVERSE(V, I, P) \ | |
| 1562 for (I = vec_safe_length (V) - 1; \ | |
| 1563 vec_safe_iterate ((V), (I), &(P)); \ | |
| 1564 (I)--) | |
| 1565 | |
| 131 | 1566 /* auto_string_vec's dtor, freeing all contained strings, automatically |
| 1567 chaining up to ~auto_vec <char *>, which frees the internal buffer. */ | |
| 1568 | |
| 1569 inline | |
| 1570 auto_string_vec::~auto_string_vec () | |
| 1571 { | |
| 1572 int i; | |
| 1573 char *str; | |
| 1574 FOR_EACH_VEC_ELT (*this, i, str) | |
| 1575 free (str); | |
| 1576 } | |
| 1577 | |
| 111 | 1578 |
| 1579 /* Return a copy of this vector. */ | |
| 1580 | |
| 1581 template<typename T> | |
| 1582 inline vec<T, va_heap, vl_ptr> | |
| 1583 vec<T, va_heap, vl_ptr>::copy (ALONE_MEM_STAT_DECL) const | |
| 1584 { | |
| 1585 vec<T, va_heap, vl_ptr> new_vec = vNULL; | |
| 1586 if (length ()) | |
| 1587 new_vec.m_vec = m_vec->copy (); | |
| 1588 return new_vec; | |
| 1589 } | |
| 1590 | |
| 1591 | |
| 1592 /* Ensure that the vector has at least RESERVE slots available (if | |
| 1593 EXACT is false), or exactly RESERVE slots available (if EXACT is | |
| 1594 true). | |
| 1595 | |
| 1596 This may create additional headroom if EXACT is false. | |
| 1597 | |
| 1598 Note that this can cause the embedded vector to be reallocated. | |
| 1599 Returns true iff reallocation actually occurred. */ | |
| 1600 | |
| 1601 template<typename T> | |
| 1602 inline bool | |
| 1603 vec<T, va_heap, vl_ptr>::reserve (unsigned nelems, bool exact MEM_STAT_DECL) | |
| 1604 { | |
| 1605 if (space (nelems)) | |
| 1606 return false; | |
| 1607 | |
| 1608 /* For now play a game with va_heap::reserve to hide our auto storage if any, | |
| 1609 this is necessary because it doesn't have enough information to know the | |
| 1610 embedded vector is in auto storage, and so should not be freed. */ | |
| 1611 vec<T, va_heap, vl_embed> *oldvec = m_vec; | |
| 1612 unsigned int oldsize = 0; | |
| 1613 bool handle_auto_vec = m_vec && using_auto_storage (); | |
| 1614 if (handle_auto_vec) | |
| 1615 { | |
| 1616 m_vec = NULL; | |
| 1617 oldsize = oldvec->length (); | |
| 1618 nelems += oldsize; | |
| 1619 } | |
| 1620 | |
| 1621 va_heap::reserve (m_vec, nelems, exact PASS_MEM_STAT); | |
| 1622 if (handle_auto_vec) | |
| 1623 { | |
| 1624 vec_copy_construct (m_vec->address (), oldvec->address (), oldsize); | |
| 1625 m_vec->m_vecpfx.m_num = oldsize; | |
| 1626 } | |
| 1627 | |
| 1628 return true; | |
| 1629 } | |
| 1630 | |
| 1631 | |
| 1632 /* Ensure that this vector has exactly NELEMS slots available. This | |
| 1633 will not create additional headroom. Note this can cause the | |
| 1634 embedded vector to be reallocated. Returns true iff reallocation | |
| 1635 actually occurred. */ | |
| 1636 | |
| 1637 template<typename T> | |
| 1638 inline bool | |
| 1639 vec<T, va_heap, vl_ptr>::reserve_exact (unsigned nelems MEM_STAT_DECL) | |
| 1640 { | |
| 1641 return reserve (nelems, true PASS_MEM_STAT); | |
| 0 | 1642 } |
| 1643 | |
| 111 | 1644 |
| 1645 /* Create the internal vector and reserve NELEMS for it. This is | |
| 1646 exactly like vec::reserve, but the internal vector is | |
| 1647 unconditionally allocated from scratch. The old one, if it | |
| 1648 existed, is lost. */ | |
| 1649 | |
| 1650 template<typename T> | |
| 1651 inline void | |
| 1652 vec<T, va_heap, vl_ptr>::create (unsigned nelems MEM_STAT_DECL) | |
| 1653 { | |
| 1654 m_vec = NULL; | |
| 1655 if (nelems > 0) | |
| 1656 reserve_exact (nelems PASS_MEM_STAT); | |
| 1657 } | |
| 1658 | |
| 1659 | |
| 1660 /* Free the memory occupied by the embedded vector. */ | |
| 1661 | |
| 1662 template<typename T> | |
| 1663 inline void | |
| 1664 vec<T, va_heap, vl_ptr>::release (void) | |
| 1665 { | |
| 1666 if (!m_vec) | |
| 1667 return; | |
| 1668 | |
| 1669 if (using_auto_storage ()) | |
| 1670 { | |
| 1671 m_vec->m_vecpfx.m_num = 0; | |
| 1672 return; | |
| 1673 } | |
| 1674 | |
| 1675 va_heap::release (m_vec); | |
| 1676 } | |
| 1677 | |
| 1678 /* Copy the elements from SRC to the end of this vector as if by memcpy. | |
| 1679 SRC and this vector must be allocated with the same memory | |
| 1680 allocation mechanism. This vector is assumed to have sufficient | |
| 1681 headroom available. */ | |
| 1682 | |
| 1683 template<typename T> | |
| 1684 inline void | |
| 1685 vec<T, va_heap, vl_ptr>::splice (const vec<T, va_heap, vl_ptr> &src) | |
| 1686 { | |
| 1687 if (src.m_vec) | |
| 1688 m_vec->splice (*(src.m_vec)); | |
| 1689 } | |
| 1690 | |
| 0 | 1691 |
| 111 | 1692 /* Copy the elements in SRC to the end of this vector as if by memcpy. |
| 1693 SRC and this vector must be allocated with the same mechanism. | |
| 1694 If there is not enough headroom in this vector, it will be reallocated | |
| 1695 as needed. */ | |
| 1696 | |
| 1697 template<typename T> | |
| 1698 inline void | |
| 1699 vec<T, va_heap, vl_ptr>::safe_splice (const vec<T, va_heap, vl_ptr> &src | |
| 1700 MEM_STAT_DECL) | |
| 1701 { | |
| 1702 if (src.length ()) | |
| 1703 { | |
| 1704 reserve_exact (src.length ()); | |
| 1705 splice (src); | |
| 1706 } | |
| 1707 } | |
| 1708 | |
| 1709 | |
| 1710 /* Push OBJ (a new element) onto the end of the vector. There must be | |
| 1711 sufficient space in the vector. Return a pointer to the slot | |
| 1712 where OBJ was inserted. */ | |
| 1713 | |
| 1714 template<typename T> | |
| 1715 inline T * | |
| 1716 vec<T, va_heap, vl_ptr>::quick_push (const T &obj) | |
| 1717 { | |
| 1718 return m_vec->quick_push (obj); | |
| 1719 } | |
| 1720 | |
| 1721 | |
| 1722 /* Push a new element OBJ onto the end of this vector. Reallocates | |
| 1723 the embedded vector, if needed. Return a pointer to the slot where | |
| 1724 OBJ was inserted. */ | |
| 1725 | |
| 1726 template<typename T> | |
| 1727 inline T * | |
| 1728 vec<T, va_heap, vl_ptr>::safe_push (const T &obj MEM_STAT_DECL) | |
| 1729 { | |
| 1730 reserve (1, false PASS_MEM_STAT); | |
| 1731 return quick_push (obj); | |
| 1732 } | |
| 1733 | |
| 1734 | |
| 1735 /* Pop and return the last element off the end of the vector. */ | |
| 1736 | |
| 1737 template<typename T> | |
| 1738 inline T & | |
| 1739 vec<T, va_heap, vl_ptr>::pop (void) | |
| 1740 { | |
| 1741 return m_vec->pop (); | |
| 0 | 1742 } |
| 1743 | |
| 111 | 1744 |
| 1745 /* Set the length of the vector to LEN. The new length must be less | |
| 1746 than or equal to the current length. This is an O(1) operation. */ | |
| 1747 | |
| 1748 template<typename T> | |
| 1749 inline void | |
| 1750 vec<T, va_heap, vl_ptr>::truncate (unsigned size) | |
| 1751 { | |
| 1752 if (m_vec) | |
| 1753 m_vec->truncate (size); | |
| 1754 else | |
| 1755 gcc_checking_assert (size == 0); | |
| 1756 } | |
| 1757 | |
| 1758 | |
| 1759 /* Grow the vector to a specific length. LEN must be as long or | |
| 1760 longer than the current length. The new elements are | |
| 1761 uninitialized. Reallocate the internal vector, if needed. */ | |
| 1762 | |
| 1763 template<typename T> | |
| 1764 inline void | |
| 1765 vec<T, va_heap, vl_ptr>::safe_grow (unsigned len MEM_STAT_DECL) | |
| 1766 { | |
| 1767 unsigned oldlen = length (); | |
| 1768 gcc_checking_assert (oldlen <= len); | |
| 1769 reserve_exact (len - oldlen PASS_MEM_STAT); | |
| 1770 if (m_vec) | |
| 1771 m_vec->quick_grow (len); | |
| 1772 else | |
| 1773 gcc_checking_assert (len == 0); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1774 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1775 |
| 111 | 1776 |
| 1777 /* Grow the embedded vector to a specific length. LEN must be as | |
| 1778 long or longer than the current length. The new elements are | |
| 1779 initialized to zero. Reallocate the internal vector, if needed. */ | |
| 1780 | |
| 1781 template<typename T> | |
| 1782 inline void | |
| 1783 vec<T, va_heap, vl_ptr>::safe_grow_cleared (unsigned len MEM_STAT_DECL) | |
| 1784 { | |
| 1785 unsigned oldlen = length (); | |
| 1786 size_t growby = len - oldlen; | |
| 1787 safe_grow (len PASS_MEM_STAT); | |
| 1788 if (growby != 0) | |
| 1789 vec_default_construct (address () + oldlen, growby); | |
| 1790 } | |
| 1791 | |
| 1792 | |
| 1793 /* Same as vec::safe_grow but without reallocation of the internal vector. | |
| 1794 If the vector cannot be extended, a runtime assertion will be triggered. */ | |
| 1795 | |
| 1796 template<typename T> | |
| 1797 inline void | |
| 1798 vec<T, va_heap, vl_ptr>::quick_grow (unsigned len) | |
| 1799 { | |
| 1800 gcc_checking_assert (m_vec); | |
| 1801 m_vec->quick_grow (len); | |
| 0 | 1802 } |
| 1803 | |
| 111 | 1804 |
| 1805 /* Same as vec::quick_grow_cleared but without reallocation of the | |
| 1806 internal vector. If the vector cannot be extended, a runtime | |
| 1807 assertion will be triggered. */ | |
| 1808 | |
| 1809 template<typename T> | |
| 1810 inline void | |
| 1811 vec<T, va_heap, vl_ptr>::quick_grow_cleared (unsigned len) | |
| 1812 { | |
| 1813 gcc_checking_assert (m_vec); | |
| 1814 m_vec->quick_grow_cleared (len); | |
| 1815 } | |
| 1816 | |
| 1817 | |
| 1818 /* Insert an element, OBJ, at the IXth position of this vector. There | |
| 1819 must be sufficient space. */ | |
| 1820 | |
| 1821 template<typename T> | |
| 1822 inline void | |
| 1823 vec<T, va_heap, vl_ptr>::quick_insert (unsigned ix, const T &obj) | |
| 1824 { | |
| 1825 m_vec->quick_insert (ix, obj); | |
| 1826 } | |
| 1827 | |
| 1828 | |
| 1829 /* Insert an element, OBJ, at the IXth position of the vector. | |
| 1830 Reallocate the embedded vector, if necessary. */ | |
| 1831 | |
| 1832 template<typename T> | |
| 1833 inline void | |
| 1834 vec<T, va_heap, vl_ptr>::safe_insert (unsigned ix, const T &obj MEM_STAT_DECL) | |
| 1835 { | |
| 1836 reserve (1, false PASS_MEM_STAT); | |
| 1837 quick_insert (ix, obj); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1838 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1839 |
| 111 | 1840 |
| 1841 /* Remove an element from the IXth position of this vector. Ordering of | |
| 1842 remaining elements is preserved. This is an O(N) operation due to | |
| 1843 a memmove. */ | |
| 1844 | |
| 1845 template<typename T> | |
| 1846 inline void | |
| 1847 vec<T, va_heap, vl_ptr>::ordered_remove (unsigned ix) | |
| 1848 { | |
| 1849 m_vec->ordered_remove (ix); | |
| 1850 } | |
| 1851 | |
| 1852 | |
| 1853 /* Remove an element from the IXth position of this vector. Ordering | |
| 1854 of remaining elements is destroyed. This is an O(1) operation. */ | |
| 1855 | |
| 1856 template<typename T> | |
| 1857 inline void | |
| 1858 vec<T, va_heap, vl_ptr>::unordered_remove (unsigned ix) | |
| 1859 { | |
| 1860 m_vec->unordered_remove (ix); | |
| 1861 } | |
| 1862 | |
| 1863 | |
| 1864 /* Remove LEN elements starting at the IXth. Ordering is retained. | |
| 1865 This is an O(N) operation due to memmove. */ | |
| 1866 | |
| 1867 template<typename T> | |
| 1868 inline void | |
| 1869 vec<T, va_heap, vl_ptr>::block_remove (unsigned ix, unsigned len) | |
| 1870 { | |
| 1871 m_vec->block_remove (ix, len); | |
| 1872 } | |
| 1873 | |
| 1874 | |
| 1875 /* Sort the contents of this vector with qsort. CMP is the comparison | |
| 1876 function to pass to qsort. */ | |
| 1877 | |
| 1878 template<typename T> | |
| 1879 inline void | |
| 1880 vec<T, va_heap, vl_ptr>::qsort (int (*cmp) (const void *, const void *)) | |
| 1881 { | |
| 1882 if (m_vec) | |
| 1883 m_vec->qsort (cmp); | |
| 0 | 1884 } |
| 1885 | |
| 111 | 1886 |
| 1887 /* Search the contents of the sorted vector with a binary search. | |
| 1888 CMP is the comparison function to pass to bsearch. */ | |
| 1889 | |
| 1890 template<typename T> | |
| 1891 inline T * | |
| 1892 vec<T, va_heap, vl_ptr>::bsearch (const void *key, | |
| 1893 int (*cmp) (const void *, const void *)) | |
| 1894 { | |
| 1895 if (m_vec) | |
| 1896 return m_vec->bsearch (key, cmp); | |
| 1897 return NULL; | |
| 1898 } | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1899 |
| 111 | 1900 |
| 1901 /* Find and return the first position in which OBJ could be inserted | |
| 1902 without changing the ordering of this vector. LESSTHAN is a | |
| 1903 function that returns true if the first argument is strictly less | |
| 1904 than the second. */ | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1905 |
| 111 | 1906 template<typename T> |
| 1907 inline unsigned | |
| 1908 vec<T, va_heap, vl_ptr>::lower_bound (T obj, | |
| 1909 bool (*lessthan)(const T &, const T &)) | |
| 1910 const | |
| 1911 { | |
| 1912 return m_vec ? m_vec->lower_bound (obj, lessthan) : 0; | |
| 1913 } | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1914 |
| 111 | 1915 /* Return true if SEARCH is an element of V. Note that this is O(N) in the |
| 1916 size of the vector and so should be used with care. */ | |
| 1917 | |
| 1918 template<typename T> | |
| 1919 inline bool | |
| 1920 vec<T, va_heap, vl_ptr>::contains (const T &search) const | |
| 1921 { | |
| 1922 return m_vec ? m_vec->contains (search) : false; | |
| 1923 } | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1924 |
| 131 | 1925 /* Reverse content of the vector. */ |
| 1926 | |
| 1927 template<typename T> | |
| 1928 inline void | |
| 1929 vec<T, va_heap, vl_ptr>::reverse (void) | |
| 1930 { | |
| 1931 unsigned l = length (); | |
| 1932 T *ptr = address (); | |
| 1933 | |
| 1934 for (unsigned i = 0; i < l / 2; i++) | |
| 1935 std::swap (ptr[i], ptr[l - i - 1]); | |
| 1936 } | |
| 1937 | |
| 111 | 1938 template<typename T> |
| 1939 inline bool | |
| 1940 vec<T, va_heap, vl_ptr>::using_auto_storage () const | |
| 1941 { | |
| 1942 return m_vec->m_vecpfx.m_using_auto_storage; | |
| 1943 } | |
| 1944 | |
| 1945 /* Release VEC and call release of all element vectors. */ | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1946 |
| 111 | 1947 template<typename T> |
| 1948 inline void | |
| 1949 release_vec_vec (vec<vec<T> > &vec) | |
| 1950 { | |
| 1951 for (unsigned i = 0; i < vec.length (); i++) | |
| 1952 vec[i].release (); | |
| 1953 | |
| 1954 vec.release (); | |
| 1955 } | |
| 1956 | |
| 1957 #if (GCC_VERSION >= 3000) | |
| 1958 # pragma GCC poison m_vec m_vecpfx m_vecdata | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1959 #endif |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1960 |
| 111 | 1961 #endif // GCC_VEC_H |