Mercurial > hg > CbC > CbC_gcc
annotate gcc/vec.h @ 120:f93fa5091070
fix conv1.c
| author | mir3636 |
|---|---|
| date | Thu, 08 Mar 2018 14:53:42 +0900 |
| parents | 04ced10e8804 |
| children | 84e7813d76e9 |
| rev | line source |
|---|---|
| 0 | 1 /* Vector API for GNU compiler. |
| 111 | 2 Copyright (C) 2004-2017 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 | |
| 410 /* Default-construct N elements in DST. */ | |
| 411 | |
| 412 template <typename T> | |
| 413 inline void | |
| 414 vec_default_construct (T *dst, unsigned n) | |
| 415 { | |
| 416 for ( ; n; ++dst, --n) | |
| 417 ::new (static_cast<void*>(dst)) T (); | |
| 418 } | |
| 419 | |
| 420 /* Copy-construct N elements in DST from *SRC. */ | |
| 421 | |
| 422 template <typename T> | |
| 423 inline void | |
| 424 vec_copy_construct (T *dst, const T *src, unsigned n) | |
| 425 { | |
| 426 for ( ; n; ++dst, ++src, --n) | |
| 427 ::new (static_cast<void*>(dst)) T (*src); | |
| 428 } | |
| 429 | |
| 430 /* Type to provide NULL values for vec<T, A, L>. This is used to | |
| 431 provide nil initializers for vec instances. Since vec must be | |
| 432 a POD, we cannot have proper ctor/dtor for it. To initialize | |
| 433 a vec instance, you can assign it the value vNULL. This isn't | |
| 434 needed for file-scope and function-local static vectors, which | |
| 435 are zero-initialized by default. */ | |
| 436 struct vnull | |
| 437 { | |
| 438 template <typename T, typename A, typename L> | |
| 439 CONSTEXPR operator vec<T, A, L> () { return vec<T, A, L>(); } | |
| 440 }; | |
| 441 extern 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). */ | |
| 0 | 469 |
| 111 | 470 template<typename T, typename A> |
| 471 struct GTY((user)) vec<T, A, vl_embed> | |
| 472 { | |
| 473 public: | |
| 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 T *begin () { return address (); } | |
| 480 const T *begin () const { return address (); } | |
| 481 T *end () { return address () + length (); } | |
| 482 const T *end () const { return address () + length (); } | |
| 483 const T &operator[] (unsigned) const; | |
| 484 T &operator[] (unsigned); | |
| 485 T &last (void); | |
| 486 bool space (unsigned) const; | |
| 487 bool iterate (unsigned, T *) const; | |
| 488 bool iterate (unsigned, T **) const; | |
| 489 vec *copy (ALONE_CXX_MEM_STAT_INFO) const; | |
| 490 void splice (const vec &); | |
| 491 void splice (const vec *src); | |
| 492 T *quick_push (const T &); | |
| 493 T &pop (void); | |
| 494 void truncate (unsigned); | |
| 495 void quick_insert (unsigned, const T &); | |
| 496 void ordered_remove (unsigned); | |
| 497 void unordered_remove (unsigned); | |
| 498 void block_remove (unsigned, unsigned); | |
| 499 void qsort (int (*) (const void *, const void *)); | |
| 500 T *bsearch (const void *key, int (*compar)(const void *, const void *)); | |
| 501 unsigned lower_bound (T, bool (*)(const T &, const T &)) const; | |
| 502 bool contains (const T &search) const; | |
| 503 static size_t embedded_size (unsigned); | |
| 504 void embedded_init (unsigned, unsigned = 0, unsigned = 0); | |
| 505 void quick_grow (unsigned len); | |
| 506 void quick_grow_cleared (unsigned len); | |
| 507 | |
| 508 /* vec class can access our internal data and functions. */ | |
| 509 template <typename, typename, typename> friend struct vec; | |
| 510 | |
| 511 /* The allocator types also need access to our internals. */ | |
| 512 friend struct va_gc; | |
| 513 friend struct va_gc_atomic; | |
| 514 friend struct va_heap; | |
| 515 | |
| 516 /* FIXME - These fields should be private, but we need to cater to | |
| 517 compilers that have stricter notions of PODness for types. */ | |
| 518 vec_prefix m_vecpfx; | |
| 519 T m_vecdata[1]; | |
| 520 }; | |
| 521 | |
| 522 | |
| 523 /* Convenience wrapper functions to use when dealing with pointers to | |
| 524 embedded vectors. Some functionality for these vectors must be | |
| 525 provided via free functions for these reasons: | |
| 526 | |
| 527 1- The pointer may be NULL (e.g., before initial allocation). | |
| 528 | |
| 529 2- When the vector needs to grow, it must be reallocated, so | |
| 530 the pointer will change its value. | |
| 531 | |
| 532 Because of limitations with the current GC machinery, all vectors | |
| 533 in GC memory *must* be pointers. */ | |
| 534 | |
| 0 | 535 |
| 111 | 536 /* If V contains no room for NELEMS elements, return false. Otherwise, |
| 537 return true. */ | |
| 538 template<typename T, typename A> | |
| 539 inline bool | |
| 540 vec_safe_space (const vec<T, A, vl_embed> *v, unsigned nelems) | |
| 541 { | |
| 542 return v ? v->space (nelems) : nelems == 0; | |
| 543 } | |
| 544 | |
| 545 | |
| 546 /* If V is NULL, return 0. Otherwise, return V->length(). */ | |
| 547 template<typename T, typename A> | |
| 548 inline unsigned | |
| 549 vec_safe_length (const vec<T, A, vl_embed> *v) | |
| 550 { | |
| 551 return v ? v->length () : 0; | |
| 552 } | |
| 553 | |
| 554 | |
| 555 /* If V is NULL, return NULL. Otherwise, return V->address(). */ | |
| 556 template<typename T, typename A> | |
| 557 inline T * | |
| 558 vec_safe_address (vec<T, A, vl_embed> *v) | |
| 559 { | |
| 560 return v ? v->address () : NULL; | |
| 561 } | |
| 562 | |
| 563 | |
| 564 /* If V is NULL, return true. Otherwise, return V->is_empty(). */ | |
| 565 template<typename T, typename A> | |
| 566 inline bool | |
| 567 vec_safe_is_empty (vec<T, A, vl_embed> *v) | |
| 568 { | |
| 569 return v ? v->is_empty () : true; | |
| 570 } | |
| 571 | |
| 572 /* If V does not have space for NELEMS elements, call | |
| 573 V->reserve(NELEMS, EXACT). */ | |
| 574 template<typename T, typename A> | |
| 575 inline bool | |
| 576 vec_safe_reserve (vec<T, A, vl_embed> *&v, unsigned nelems, bool exact = false | |
| 577 CXX_MEM_STAT_INFO) | |
| 578 { | |
| 579 bool extend = nelems ? !vec_safe_space (v, nelems) : false; | |
| 580 if (extend) | |
| 581 A::reserve (v, nelems, exact PASS_MEM_STAT); | |
| 582 return extend; | |
| 583 } | |
| 584 | |
| 585 template<typename T, typename A> | |
| 586 inline bool | |
| 587 vec_safe_reserve_exact (vec<T, A, vl_embed> *&v, unsigned nelems | |
| 588 CXX_MEM_STAT_INFO) | |
| 589 { | |
| 590 return vec_safe_reserve (v, nelems, true PASS_MEM_STAT); | |
| 591 } | |
| 592 | |
| 593 | |
| 594 /* Allocate GC memory for V with space for NELEMS slots. If NELEMS | |
| 595 is 0, V is initialized to NULL. */ | |
| 596 | |
| 597 template<typename T, typename A> | |
| 598 inline void | |
| 599 vec_alloc (vec<T, A, vl_embed> *&v, unsigned nelems CXX_MEM_STAT_INFO) | |
| 600 { | |
| 601 v = NULL; | |
| 602 vec_safe_reserve (v, nelems, false PASS_MEM_STAT); | |
| 603 } | |
| 604 | |
| 605 | |
| 606 /* Free the GC memory allocated by vector V and set it to NULL. */ | |
| 607 | |
| 608 template<typename T, typename A> | |
| 609 inline void | |
| 610 vec_free (vec<T, A, vl_embed> *&v) | |
| 611 { | |
| 612 A::release (v); | |
| 613 } | |
| 0 | 614 |
| 615 | |
| 111 | 616 /* Grow V to length LEN. Allocate it, if necessary. */ |
| 617 template<typename T, typename A> | |
| 618 inline void | |
| 619 vec_safe_grow (vec<T, A, vl_embed> *&v, unsigned len CXX_MEM_STAT_INFO) | |
| 620 { | |
| 621 unsigned oldlen = vec_safe_length (v); | |
| 622 gcc_checking_assert (len >= oldlen); | |
| 623 vec_safe_reserve_exact (v, len - oldlen PASS_MEM_STAT); | |
| 624 v->quick_grow (len); | |
| 625 } | |
| 626 | |
| 0 | 627 |
| 111 | 628 /* If V is NULL, allocate it. Call V->safe_grow_cleared(LEN). */ |
| 629 template<typename T, typename A> | |
| 630 inline void | |
| 631 vec_safe_grow_cleared (vec<T, A, vl_embed> *&v, unsigned len CXX_MEM_STAT_INFO) | |
| 632 { | |
| 633 unsigned oldlen = vec_safe_length (v); | |
| 634 vec_safe_grow (v, len PASS_MEM_STAT); | |
| 635 vec_default_construct (v->address () + oldlen, len - oldlen); | |
| 636 } | |
| 637 | |
| 638 | |
| 639 /* If V is NULL return false, otherwise return V->iterate(IX, PTR). */ | |
| 640 template<typename T, typename A> | |
| 641 inline bool | |
| 642 vec_safe_iterate (const vec<T, A, vl_embed> *v, unsigned ix, T **ptr) | |
| 643 { | |
| 644 if (v) | |
| 645 return v->iterate (ix, ptr); | |
| 646 else | |
| 647 { | |
| 648 *ptr = 0; | |
| 649 return false; | |
| 650 } | |
| 651 } | |
| 0 | 652 |
| 111 | 653 template<typename T, typename A> |
| 654 inline bool | |
| 655 vec_safe_iterate (const vec<T, A, vl_embed> *v, unsigned ix, T *ptr) | |
| 656 { | |
| 657 if (v) | |
| 658 return v->iterate (ix, ptr); | |
| 659 else | |
| 660 { | |
| 661 *ptr = 0; | |
| 662 return false; | |
| 663 } | |
| 664 } | |
| 665 | |
| 0 | 666 |
| 111 | 667 /* If V has no room for one more element, reallocate it. Then call |
| 668 V->quick_push(OBJ). */ | |
| 669 template<typename T, typename A> | |
| 670 inline T * | |
| 671 vec_safe_push (vec<T, A, vl_embed> *&v, const T &obj CXX_MEM_STAT_INFO) | |
| 672 { | |
| 673 vec_safe_reserve (v, 1, false PASS_MEM_STAT); | |
| 674 return v->quick_push (obj); | |
| 675 } | |
| 676 | |
| 677 | |
| 678 /* if V has no room for one more element, reallocate it. Then call | |
| 679 V->quick_insert(IX, OBJ). */ | |
| 680 template<typename T, typename A> | |
| 681 inline void | |
| 682 vec_safe_insert (vec<T, A, vl_embed> *&v, unsigned ix, const T &obj | |
| 683 CXX_MEM_STAT_INFO) | |
| 684 { | |
| 685 vec_safe_reserve (v, 1, false PASS_MEM_STAT); | |
| 686 v->quick_insert (ix, obj); | |
| 687 } | |
| 688 | |
| 689 | |
| 690 /* If V is NULL, do nothing. Otherwise, call V->truncate(SIZE). */ | |
| 691 template<typename T, typename A> | |
| 692 inline void | |
| 693 vec_safe_truncate (vec<T, A, vl_embed> *v, unsigned size) | |
| 694 { | |
| 695 if (v) | |
| 696 v->truncate (size); | |
| 697 } | |
| 698 | |
| 0 | 699 |
| 111 | 700 /* If SRC is not NULL, return a pointer to a copy of it. */ |
| 701 template<typename T, typename A> | |
| 702 inline vec<T, A, vl_embed> * | |
| 703 vec_safe_copy (vec<T, A, vl_embed> *src CXX_MEM_STAT_INFO) | |
| 704 { | |
| 705 return src ? src->copy (ALONE_PASS_MEM_STAT) : NULL; | |
| 706 } | |
| 0 | 707 |
| 111 | 708 /* Copy the elements from SRC to the end of DST as if by memcpy. |
| 709 Reallocate DST, if necessary. */ | |
| 710 template<typename T, typename A> | |
| 711 inline void | |
| 712 vec_safe_splice (vec<T, A, vl_embed> *&dst, const vec<T, A, vl_embed> *src | |
| 713 CXX_MEM_STAT_INFO) | |
| 714 { | |
| 715 unsigned src_len = vec_safe_length (src); | |
| 716 if (src_len) | |
| 717 { | |
| 718 vec_safe_reserve_exact (dst, vec_safe_length (dst) + src_len | |
| 719 PASS_MEM_STAT); | |
| 720 dst->splice (*src); | |
| 721 } | |
| 722 } | |
| 723 | |
| 724 /* Return true if SEARCH is an element of V. Note that this is O(N) in the | |
| 725 size of the vector and so should be used with care. */ | |
| 726 | |
| 727 template<typename T, typename A> | |
| 728 inline bool | |
| 729 vec_safe_contains (vec<T, A, vl_embed> *v, const T &search) | |
| 730 { | |
| 731 return v ? v->contains (search) : false; | |
| 732 } | |
| 733 | |
| 734 /* Index into vector. Return the IX'th element. IX must be in the | |
| 735 domain of the vector. */ | |
| 0 | 736 |
| 111 | 737 template<typename T, typename A> |
| 738 inline const T & | |
| 739 vec<T, A, vl_embed>::operator[] (unsigned ix) const | |
| 740 { | |
| 741 gcc_checking_assert (ix < m_vecpfx.m_num); | |
| 742 return m_vecdata[ix]; | |
| 743 } | |
| 744 | |
| 745 template<typename T, typename A> | |
| 746 inline T & | |
| 747 vec<T, A, vl_embed>::operator[] (unsigned ix) | |
| 748 { | |
| 749 gcc_checking_assert (ix < m_vecpfx.m_num); | |
| 750 return m_vecdata[ix]; | |
| 751 } | |
| 752 | |
| 753 | |
| 754 /* Get the final element of the vector, which must not be empty. */ | |
| 0 | 755 |
| 111 | 756 template<typename T, typename A> |
| 757 inline T & | |
| 758 vec<T, A, vl_embed>::last (void) | |
| 759 { | |
| 760 gcc_checking_assert (m_vecpfx.m_num > 0); | |
| 761 return (*this)[m_vecpfx.m_num - 1]; | |
| 762 } | |
| 763 | |
| 0 | 764 |
| 111 | 765 /* If this vector has space for NELEMS additional entries, return |
| 766 true. You usually only need to use this if you are doing your | |
| 767 own vector reallocation, for instance on an embedded vector. This | |
| 768 returns true in exactly the same circumstances that vec::reserve | |
| 769 will. */ | |
| 770 | |
| 771 template<typename T, typename A> | |
| 772 inline bool | |
| 773 vec<T, A, vl_embed>::space (unsigned nelems) const | |
| 774 { | |
| 775 return m_vecpfx.m_alloc - m_vecpfx.m_num >= nelems; | |
| 776 } | |
| 777 | |
| 778 | |
| 779 /* Return iteration condition and update PTR to point to the IX'th | |
| 780 element of this vector. Use this to iterate over the elements of a | |
| 781 vector as follows, | |
| 782 | |
| 783 for (ix = 0; vec<T, A>::iterate (v, ix, &ptr); ix++) | |
| 0 | 784 continue; */ |
| 785 | |
| 111 | 786 template<typename T, typename A> |
| 787 inline bool | |
| 788 vec<T, A, vl_embed>::iterate (unsigned ix, T *ptr) const | |
| 789 { | |
| 790 if (ix < m_vecpfx.m_num) | |
| 791 { | |
| 792 *ptr = m_vecdata[ix]; | |
| 793 return true; | |
| 794 } | |
| 795 else | |
| 796 { | |
| 797 *ptr = 0; | |
| 798 return false; | |
| 799 } | |
| 800 } | |
| 801 | |
| 802 | |
| 803 /* Return iteration condition and update *PTR to point to the | |
| 804 IX'th element of this vector. Use this to iterate over the | |
| 805 elements of a vector as follows, | |
| 806 | |
| 807 for (ix = 0; v->iterate (ix, &ptr); ix++) | |
| 808 continue; | |
| 809 | |
| 810 This variant is for vectors of objects. */ | |
| 0 | 811 |
| 111 | 812 template<typename T, typename A> |
| 813 inline bool | |
| 814 vec<T, A, vl_embed>::iterate (unsigned ix, T **ptr) const | |
| 815 { | |
| 816 if (ix < m_vecpfx.m_num) | |
| 817 { | |
| 818 *ptr = CONST_CAST (T *, &m_vecdata[ix]); | |
| 819 return true; | |
| 820 } | |
| 821 else | |
| 822 { | |
| 823 *ptr = 0; | |
| 824 return false; | |
| 825 } | |
| 826 } | |
| 827 | |
| 828 | |
| 829 /* 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
|
830 |
| 111 | 831 template<typename T, typename A> |
| 832 inline vec<T, A, vl_embed> * | |
| 833 vec<T, A, vl_embed>::copy (ALONE_MEM_STAT_DECL) const | |
| 834 { | |
| 835 vec<T, A, vl_embed> *new_vec = NULL; | |
| 836 unsigned len = length (); | |
| 837 if (len) | |
| 838 { | |
| 839 vec_alloc (new_vec, len PASS_MEM_STAT); | |
| 840 new_vec->embedded_init (len, len); | |
| 841 vec_copy_construct (new_vec->address (), m_vecdata, len); | |
| 842 } | |
| 843 return new_vec; | |
| 844 } | |
| 845 | |
| 846 | |
| 847 /* Copy the elements from SRC to the end of this vector as if by memcpy. | |
| 848 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
|
849 |
| 111 | 850 template<typename T, typename A> |
| 851 inline void | |
| 852 vec<T, A, vl_embed>::splice (const vec<T, A, vl_embed> &src) | |
| 853 { | |
| 854 unsigned len = src.length (); | |
| 855 if (len) | |
| 856 { | |
| 857 gcc_checking_assert (space (len)); | |
| 858 vec_copy_construct (end (), src.address (), len); | |
| 859 m_vecpfx.m_num += len; | |
| 860 } | |
| 861 } | |
| 862 | |
| 863 template<typename T, typename A> | |
| 864 inline void | |
| 865 vec<T, A, vl_embed>::splice (const vec<T, A, vl_embed> *src) | |
| 866 { | |
| 867 if (src) | |
| 868 splice (*src); | |
| 869 } | |
| 870 | |
| 871 | |
| 872 /* Push OBJ (a new element) onto the end of the vector. There must be | |
| 873 sufficient space in the vector. Return a pointer to the slot | |
| 874 where OBJ was inserted. */ | |
| 875 | |
| 876 template<typename T, typename A> | |
| 877 inline T * | |
| 878 vec<T, A, vl_embed>::quick_push (const T &obj) | |
| 879 { | |
| 880 gcc_checking_assert (space (1)); | |
| 881 T *slot = &m_vecdata[m_vecpfx.m_num++]; | |
| 882 *slot = obj; | |
| 883 return slot; | |
| 884 } | |
| 885 | |
|
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
|
886 |
| 111 | 887 /* Pop and return the last element off the end of the vector. */ |
| 888 | |
| 889 template<typename T, typename A> | |
| 890 inline T & | |
| 891 vec<T, A, vl_embed>::pop (void) | |
| 892 { | |
| 893 gcc_checking_assert (length () > 0); | |
| 894 return m_vecdata[--m_vecpfx.m_num]; | |
| 895 } | |
| 896 | |
| 897 | |
| 898 /* Set the length of the vector to SIZE. The new length must be less | |
| 899 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
|
900 |
| 111 | 901 template<typename T, typename A> |
| 902 inline void | |
| 903 vec<T, A, vl_embed>::truncate (unsigned size) | |
| 904 { | |
| 905 gcc_checking_assert (length () >= size); | |
| 906 m_vecpfx.m_num = size; | |
| 907 } | |
| 908 | |
| 909 | |
| 910 /* Insert an element, OBJ, at the IXth position of this vector. There | |
| 911 must be sufficient space. */ | |
| 912 | |
| 913 template<typename T, typename A> | |
| 914 inline void | |
| 915 vec<T, A, vl_embed>::quick_insert (unsigned ix, const T &obj) | |
| 916 { | |
| 917 gcc_checking_assert (length () < allocated ()); | |
| 918 gcc_checking_assert (ix <= length ()); | |
| 919 T *slot = &m_vecdata[ix]; | |
| 920 memmove (slot + 1, slot, (m_vecpfx.m_num++ - ix) * sizeof (T)); | |
| 921 *slot = obj; | |
| 922 } | |
| 923 | |
| 0 | 924 |
| 111 | 925 /* Remove an element from the IXth position of this vector. Ordering of |
| 926 remaining elements is preserved. This is an O(N) operation due to | |
| 927 memmove. */ | |
| 928 | |
| 929 template<typename T, typename A> | |
| 930 inline void | |
| 931 vec<T, A, vl_embed>::ordered_remove (unsigned ix) | |
| 932 { | |
| 933 gcc_checking_assert (ix < length ()); | |
| 934 T *slot = &m_vecdata[ix]; | |
| 935 memmove (slot, slot + 1, (--m_vecpfx.m_num - ix) * sizeof (T)); | |
| 936 } | |
| 937 | |
| 938 | |
| 939 /* Remove an element from the IXth position of this vector. Ordering of | |
| 940 remaining elements is destroyed. This is an O(1) operation. */ | |
| 941 | |
| 942 template<typename T, typename A> | |
| 943 inline void | |
| 944 vec<T, A, vl_embed>::unordered_remove (unsigned ix) | |
| 945 { | |
| 946 gcc_checking_assert (ix < length ()); | |
| 947 m_vecdata[ix] = m_vecdata[--m_vecpfx.m_num]; | |
| 948 } | |
| 949 | |
| 950 | |
| 951 /* Remove LEN elements starting at the IXth. Ordering is retained. | |
| 952 This is an O(N) operation due to memmove. */ | |
| 0 | 953 |
| 111 | 954 template<typename T, typename A> |
| 955 inline void | |
| 956 vec<T, A, vl_embed>::block_remove (unsigned ix, unsigned len) | |
| 957 { | |
| 958 gcc_checking_assert (ix + len <= length ()); | |
| 959 T *slot = &m_vecdata[ix]; | |
| 960 m_vecpfx.m_num -= len; | |
| 961 memmove (slot, slot + len, (m_vecpfx.m_num - ix) * sizeof (T)); | |
| 962 } | |
| 963 | |
| 964 | |
| 965 /* Sort the contents of this vector with qsort. CMP is the comparison | |
| 966 function to pass to qsort. */ | |
| 0 | 967 |
| 111 | 968 template<typename T, typename A> |
| 969 inline void | |
| 970 vec<T, A, vl_embed>::qsort (int (*cmp) (const void *, const void *)) | |
| 971 { | |
| 972 if (length () > 1) | |
| 973 ::qsort (address (), length (), sizeof (T), cmp); | |
| 974 } | |
| 975 | |
| 976 | |
| 977 /* Search the contents of the sorted vector with a binary search. | |
| 978 CMP is the comparison function to pass to bsearch. */ | |
| 979 | |
| 980 template<typename T, typename A> | |
| 981 inline T * | |
| 982 vec<T, A, vl_embed>::bsearch (const void *key, | |
| 983 int (*compar) (const void *, const void *)) | |
| 984 { | |
| 985 const void *base = this->address (); | |
| 986 size_t nmemb = this->length (); | |
| 987 size_t size = sizeof (T); | |
| 988 /* The following is a copy of glibc stdlib-bsearch.h. */ | |
| 989 size_t l, u, idx; | |
| 990 const void *p; | |
| 991 int comparison; | |
| 0 | 992 |
| 111 | 993 l = 0; |
| 994 u = nmemb; | |
| 995 while (l < u) | |
| 996 { | |
| 997 idx = (l + u) / 2; | |
| 998 p = (const void *) (((const char *) base) + (idx * size)); | |
| 999 comparison = (*compar) (key, p); | |
| 1000 if (comparison < 0) | |
| 1001 u = idx; | |
| 1002 else if (comparison > 0) | |
| 1003 l = idx + 1; | |
| 1004 else | |
| 1005 return (T *)const_cast<void *>(p); | |
| 1006 } | |
| 0 | 1007 |
| 111 | 1008 return NULL; |
| 1009 } | |
| 1010 | |
| 1011 /* Return true if SEARCH is an element of V. Note that this is O(N) in the | |
| 1012 size of the vector and so should be used with care. */ | |
| 1013 | |
| 1014 template<typename T, typename A> | |
| 1015 inline bool | |
| 1016 vec<T, A, vl_embed>::contains (const T &search) const | |
| 1017 { | |
| 1018 unsigned int len = length (); | |
| 1019 for (unsigned int i = 0; i < len; i++) | |
| 1020 if ((*this)[i] == search) | |
| 1021 return true; | |
| 1022 | |
| 1023 return false; | |
| 1024 } | |
| 0 | 1025 |
| 111 | 1026 /* Find and return the first position in which OBJ could be inserted |
| 1027 without changing the ordering of this vector. LESSTHAN is a | |
| 1028 function that returns true if the first argument is strictly less | |
| 1029 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
|
1030 |
| 111 | 1031 template<typename T, typename A> |
| 1032 unsigned | |
| 1033 vec<T, A, vl_embed>::lower_bound (T obj, bool (*lessthan)(const T &, const T &)) | |
| 1034 const | |
| 1035 { | |
| 1036 unsigned int len = length (); | |
| 1037 unsigned int half, middle; | |
| 1038 unsigned int first = 0; | |
| 1039 while (len > 0) | |
| 1040 { | |
| 1041 half = len / 2; | |
| 1042 middle = first; | |
| 1043 middle += half; | |
| 1044 T middle_elem = (*this)[middle]; | |
| 1045 if (lessthan (middle_elem, obj)) | |
| 1046 { | |
| 1047 first = middle; | |
| 1048 ++first; | |
| 1049 len = len - half - 1; | |
| 1050 } | |
| 1051 else | |
| 1052 len = half; | |
| 1053 } | |
| 1054 return first; | |
| 1055 } | |
| 1056 | |
| 1057 | |
| 1058 /* Return the number of bytes needed to embed an instance of an | |
| 1059 embeddable vec inside another data structure. | |
| 1060 | |
| 1061 Use these methods to determine the required size and initialization | |
| 1062 of a vector V of type T embedded within another structure (as the | |
| 1063 final member): | |
| 1064 | |
| 1065 size_t vec<T, A, vl_embed>::embedded_size (unsigned alloc); | |
| 1066 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
|
1067 |
| 0 | 1068 These allow the caller to perform the memory allocation. */ |
| 1069 | |
| 111 | 1070 template<typename T, typename A> |
| 1071 inline size_t | |
| 1072 vec<T, A, vl_embed>::embedded_size (unsigned alloc) | |
| 1073 { | |
| 1074 typedef vec<T, A, vl_embed> vec_embedded; | |
| 1075 return offsetof (vec_embedded, m_vecdata) + alloc * sizeof (T); | |
| 1076 } | |
|
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
|
1077 |
|
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
|
1078 |
| 111 | 1079 /* Initialize the vector to contain room for ALLOC elements and |
| 1080 NUM active elements. */ | |
| 0 | 1081 |
| 111 | 1082 template<typename T, typename A> |
| 1083 inline void | |
| 1084 vec<T, A, vl_embed>::embedded_init (unsigned alloc, unsigned num, unsigned aut) | |
| 1085 { | |
| 1086 m_vecpfx.m_alloc = alloc; | |
| 1087 m_vecpfx.m_using_auto_storage = aut; | |
| 1088 m_vecpfx.m_num = num; | |
| 1089 } | |
| 0 | 1090 |
| 1091 | |
| 111 | 1092 /* Grow the vector to a specific length. LEN must be as long or longer than |
| 1093 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
|
1094 |
| 111 | 1095 template<typename T, typename A> |
| 1096 inline void | |
| 1097 vec<T, A, vl_embed>::quick_grow (unsigned len) | |
| 1098 { | |
| 1099 gcc_checking_assert (length () <= len && len <= m_vecpfx.m_alloc); | |
| 1100 m_vecpfx.m_num = len; | |
| 1101 } | |
| 0 | 1102 |
| 1103 | |
| 111 | 1104 /* Grow the vector to a specific length. LEN must be as long or longer than |
| 1105 the current length. The new elements are initialized to zero. */ | |
| 0 | 1106 |
| 111 | 1107 template<typename T, typename A> |
| 1108 inline void | |
| 1109 vec<T, A, vl_embed>::quick_grow_cleared (unsigned len) | |
| 1110 { | |
| 1111 unsigned oldlen = length (); | |
| 1112 size_t growby = len - oldlen; | |
| 1113 quick_grow (len); | |
| 1114 if (growby != 0) | |
| 1115 vec_default_construct (address () + oldlen, growby); | |
| 1116 } | |
| 0 | 1117 |
| 111 | 1118 /* Garbage collection support for vec<T, A, vl_embed>. */ |
| 0 | 1119 |
| 111 | 1120 template<typename T> |
| 1121 void | |
| 1122 gt_ggc_mx (vec<T, va_gc> *v) | |
| 1123 { | |
| 1124 extern void gt_ggc_mx (T &); | |
| 1125 for (unsigned i = 0; i < v->length (); i++) | |
| 1126 gt_ggc_mx ((*v)[i]); | |
| 1127 } | |
| 0 | 1128 |
| 111 | 1129 template<typename T> |
| 1130 void | |
| 1131 gt_ggc_mx (vec<T, va_gc_atomic, vl_embed> *v ATTRIBUTE_UNUSED) | |
| 1132 { | |
| 1133 /* Nothing to do. Vectors of atomic types wrt GC do not need to | |
| 1134 be traversed. */ | |
| 1135 } | |
| 1136 | |
| 1137 | |
| 1138 /* PCH support for vec<T, A, vl_embed>. */ | |
| 1139 | |
| 1140 template<typename T, typename A> | |
| 1141 void | |
| 1142 gt_pch_nx (vec<T, A, vl_embed> *v) | |
| 1143 { | |
| 1144 extern void gt_pch_nx (T &); | |
| 1145 for (unsigned i = 0; i < v->length (); i++) | |
| 1146 gt_pch_nx ((*v)[i]); | |
| 1147 } | |
| 1148 | |
| 1149 template<typename T, typename A> | |
| 1150 void | |
| 1151 gt_pch_nx (vec<T *, A, vl_embed> *v, gt_pointer_operator op, void *cookie) | |
| 1152 { | |
| 1153 for (unsigned i = 0; i < v->length (); i++) | |
| 1154 op (&((*v)[i]), cookie); | |
| 1155 } | |
| 1156 | |
| 1157 template<typename T, typename A> | |
| 1158 void | |
| 1159 gt_pch_nx (vec<T, A, vl_embed> *v, gt_pointer_operator op, void *cookie) | |
| 1160 { | |
| 1161 extern void gt_pch_nx (T *, gt_pointer_operator, void *); | |
| 1162 for (unsigned i = 0; i < v->length (); i++) | |
| 1163 gt_pch_nx (&((*v)[i]), op, cookie); | |
| 0 | 1164 } |
| 1165 | |
| 111 | 1166 |
| 1167 /* Space efficient vector. These vectors can grow dynamically and are | |
| 1168 allocated together with their control data. They are suited to be | |
| 1169 included in data structures. Prior to initial allocation, they | |
| 1170 only take a single word of storage. | |
| 1171 | |
| 1172 These vectors are implemented as a pointer to an embeddable vector. | |
| 1173 The semantics allow for this pointer to be NULL to represent empty | |
| 1174 vectors. This way, empty vectors occupy minimal space in the | |
| 1175 structure containing them. | |
| 1176 | |
| 1177 Properties: | |
| 1178 | |
| 1179 - The whole vector and control data are allocated in a single | |
| 1180 contiguous block. | |
| 1181 - The whole vector may be re-allocated. | |
| 1182 - Vector data may grow and shrink. | |
| 1183 - Access and manipulation requires a pointer test and | |
| 1184 indirection. | |
| 1185 - It requires 1 word of storage (prior to vector allocation). | |
| 1186 | |
| 1187 | |
| 1188 Limitations: | |
| 1189 | |
| 1190 These vectors must be PODs because they are stored in unions. | |
| 1191 (http://en.wikipedia.org/wiki/Plain_old_data_structures). | |
| 1192 As long as we use C++03, we cannot have constructors nor | |
| 1193 destructors in classes that are stored in unions. */ | |
| 1194 | |
| 1195 template<typename T> | |
| 1196 struct vec<T, va_heap, vl_ptr> | |
| 1197 { | |
| 1198 public: | |
| 1199 /* Memory allocation and deallocation for the embedded vector. | |
| 1200 Needed because we cannot have proper ctors/dtors defined. */ | |
| 1201 void create (unsigned nelems CXX_MEM_STAT_INFO); | |
| 1202 void release (void); | |
| 1203 | |
| 1204 /* Vector operations. */ | |
| 1205 bool exists (void) const | |
| 1206 { return m_vec != NULL; } | |
| 1207 | |
| 1208 bool is_empty (void) const | |
| 1209 { return m_vec ? m_vec->is_empty () : true; } | |
| 1210 | |
| 1211 unsigned length (void) const | |
| 1212 { return m_vec ? m_vec->length () : 0; } | |
| 1213 | |
| 1214 T *address (void) | |
| 1215 { return m_vec ? m_vec->m_vecdata : NULL; } | |
| 1216 | |
| 1217 const T *address (void) const | |
| 1218 { return m_vec ? m_vec->m_vecdata : NULL; } | |
| 1219 | |
| 1220 T *begin () { return address (); } | |
| 1221 const T *begin () const { return address (); } | |
| 1222 T *end () { return begin () + length (); } | |
| 1223 const T *end () const { return begin () + length (); } | |
| 1224 const T &operator[] (unsigned ix) const | |
| 1225 { return (*m_vec)[ix]; } | |
| 1226 | |
| 1227 bool operator!=(const vec &other) const | |
| 1228 { return !(*this == other); } | |
| 1229 | |
| 1230 bool operator==(const vec &other) const | |
| 1231 { return address () == other.address (); } | |
| 1232 | |
| 1233 T &operator[] (unsigned ix) | |
| 1234 { return (*m_vec)[ix]; } | |
| 1235 | |
| 1236 T &last (void) | |
| 1237 { return m_vec->last (); } | |
| 1238 | |
| 1239 bool space (int nelems) const | |
| 1240 { return m_vec ? m_vec->space (nelems) : nelems == 0; } | |
| 1241 | |
| 1242 bool iterate (unsigned ix, T *p) const; | |
| 1243 bool iterate (unsigned ix, T **p) const; | |
| 1244 vec copy (ALONE_CXX_MEM_STAT_INFO) const; | |
| 1245 bool reserve (unsigned, bool = false CXX_MEM_STAT_INFO); | |
| 1246 bool reserve_exact (unsigned CXX_MEM_STAT_INFO); | |
| 1247 void splice (const vec &); | |
| 1248 void safe_splice (const vec & CXX_MEM_STAT_INFO); | |
| 1249 T *quick_push (const T &); | |
| 1250 T *safe_push (const T &CXX_MEM_STAT_INFO); | |
| 1251 T &pop (void); | |
| 1252 void truncate (unsigned); | |
| 1253 void safe_grow (unsigned CXX_MEM_STAT_INFO); | |
| 1254 void safe_grow_cleared (unsigned CXX_MEM_STAT_INFO); | |
| 1255 void quick_grow (unsigned); | |
| 1256 void quick_grow_cleared (unsigned); | |
| 1257 void quick_insert (unsigned, const T &); | |
| 1258 void safe_insert (unsigned, const T & CXX_MEM_STAT_INFO); | |
| 1259 void ordered_remove (unsigned); | |
| 1260 void unordered_remove (unsigned); | |
| 1261 void block_remove (unsigned, unsigned); | |
| 1262 void qsort (int (*) (const void *, const void *)); | |
| 1263 T *bsearch (const void *key, int (*compar)(const void *, const void *)); | |
| 1264 unsigned lower_bound (T, bool (*)(const T &, const T &)) const; | |
| 1265 bool contains (const T &search) const; | |
| 1266 | |
| 1267 bool using_auto_storage () const; | |
| 1268 | |
| 1269 /* FIXME - This field should be private, but we need to cater to | |
| 1270 compilers that have stricter notions of PODness for types. */ | |
| 1271 vec<T, va_heap, vl_embed> *m_vec; | |
| 1272 }; | |
| 1273 | |
| 1274 | |
| 1275 /* auto_vec is a subclass of vec that automatically manages creating and | |
| 1276 releasing the internal vector. If N is non zero then it has N elements of | |
| 1277 internal storage. The default is no internal storage, and you probably only | |
| 1278 want to ask for internal storage for vectors on the stack because if the | |
| 1279 size of the vector is larger than the internal storage that space is wasted. | |
| 1280 */ | |
| 1281 template<typename T, size_t N = 0> | |
| 1282 class auto_vec : public vec<T, va_heap> | |
| 1283 { | |
| 1284 public: | |
| 1285 auto_vec () | |
| 1286 { | |
| 1287 m_auto.embedded_init (MAX (N, 2), 0, 1); | |
| 1288 this->m_vec = &m_auto; | |
| 1289 } | |
| 1290 | |
| 1291 auto_vec (size_t s) | |
| 1292 { | |
| 1293 if (s > N) | |
| 1294 { | |
| 1295 this->create (s); | |
| 1296 return; | |
| 1297 } | |
| 1298 | |
| 1299 m_auto.embedded_init (MAX (N, 2), 0, 1); | |
| 1300 this->m_vec = &m_auto; | |
| 1301 } | |
| 1302 | |
| 1303 ~auto_vec () | |
| 1304 { | |
| 1305 this->release (); | |
| 1306 } | |
| 1307 | |
| 1308 private: | |
| 1309 vec<T, va_heap, vl_embed> m_auto; | |
| 1310 T m_data[MAX (N - 1, 1)]; | |
| 1311 }; | |
| 1312 | |
| 1313 /* auto_vec is a sub class of vec whose storage is released when it is | |
| 1314 destroyed. */ | |
| 1315 template<typename T> | |
| 1316 class auto_vec<T, 0> : public vec<T, va_heap> | |
| 1317 { | |
| 1318 public: | |
| 1319 auto_vec () { this->m_vec = NULL; } | |
| 1320 auto_vec (size_t n) { this->create (n); } | |
| 1321 ~auto_vec () { this->release (); } | |
| 1322 }; | |
| 1323 | |
| 1324 | |
| 1325 /* Allocate heap memory for pointer V and create the internal vector | |
| 1326 with space for NELEMS elements. If NELEMS is 0, the internal | |
| 1327 vector is initialized to empty. */ | |
| 1328 | |
| 1329 template<typename T> | |
| 1330 inline void | |
| 1331 vec_alloc (vec<T> *&v, unsigned nelems CXX_MEM_STAT_INFO) | |
| 1332 { | |
| 1333 v = new vec<T>; | |
| 1334 v->create (nelems PASS_MEM_STAT); | |
| 1335 } | |
| 1336 | |
| 1337 | |
| 1338 /* Conditionally allocate heap memory for VEC and its internal vector. */ | |
| 1339 | |
| 1340 template<typename T> | |
| 1341 inline void | |
| 1342 vec_check_alloc (vec<T, va_heap> *&vec, unsigned nelems CXX_MEM_STAT_INFO) | |
| 1343 { | |
| 1344 if (!vec) | |
| 1345 vec_alloc (vec, nelems PASS_MEM_STAT); | |
| 1346 } | |
| 1347 | |
| 1348 | |
| 1349 /* Free the heap memory allocated by vector V and set it to NULL. */ | |
| 1350 | |
| 1351 template<typename T> | |
| 1352 inline void | |
| 1353 vec_free (vec<T> *&v) | |
| 1354 { | |
| 1355 if (v == NULL) | |
| 1356 return; | |
| 1357 | |
| 1358 v->release (); | |
| 1359 delete v; | |
| 1360 v = NULL; | |
| 1361 } | |
| 1362 | |
| 1363 | |
| 1364 /* Return iteration condition and update PTR to point to the IX'th | |
| 1365 element of this vector. Use this to iterate over the elements of a | |
| 1366 vector as follows, | |
| 1367 | |
| 1368 for (ix = 0; v.iterate (ix, &ptr); ix++) | |
| 1369 continue; */ | |
| 1370 | |
| 1371 template<typename T> | |
| 1372 inline bool | |
| 1373 vec<T, va_heap, vl_ptr>::iterate (unsigned ix, T *ptr) const | |
| 1374 { | |
| 1375 if (m_vec) | |
| 1376 return m_vec->iterate (ix, ptr); | |
| 1377 else | |
| 1378 { | |
| 1379 *ptr = 0; | |
| 1380 return false; | |
| 1381 } | |
| 1382 } | |
| 1383 | |
| 1384 | |
| 1385 /* Return iteration condition and update *PTR to point to the | |
| 1386 IX'th element of this vector. Use this to iterate over the | |
| 1387 elements of a vector as follows, | |
| 1388 | |
| 1389 for (ix = 0; v->iterate (ix, &ptr); ix++) | |
| 1390 continue; | |
| 1391 | |
| 1392 This variant is for vectors of objects. */ | |
| 1393 | |
| 1394 template<typename T> | |
| 1395 inline bool | |
| 1396 vec<T, va_heap, vl_ptr>::iterate (unsigned ix, T **ptr) const | |
| 1397 { | |
| 1398 if (m_vec) | |
| 1399 return m_vec->iterate (ix, ptr); | |
| 1400 else | |
| 1401 { | |
| 1402 *ptr = 0; | |
| 1403 return false; | |
| 1404 } | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1405 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1406 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1407 |
| 111 | 1408 /* Convenience macro for forward iteration. */ |
| 1409 #define FOR_EACH_VEC_ELT(V, I, P) \ | |
| 1410 for (I = 0; (V).iterate ((I), &(P)); ++(I)) | |
| 1411 | |
| 1412 #define FOR_EACH_VEC_SAFE_ELT(V, I, P) \ | |
| 1413 for (I = 0; vec_safe_iterate ((V), (I), &(P)); ++(I)) | |
| 1414 | |
| 1415 /* Likewise, but start from FROM rather than 0. */ | |
| 1416 #define FOR_EACH_VEC_ELT_FROM(V, I, P, FROM) \ | |
| 1417 for (I = (FROM); (V).iterate ((I), &(P)); ++(I)) | |
| 1418 | |
| 1419 /* Convenience macro for reverse iteration. */ | |
| 1420 #define FOR_EACH_VEC_ELT_REVERSE(V, I, P) \ | |
| 1421 for (I = (V).length () - 1; \ | |
| 1422 (V).iterate ((I), &(P)); \ | |
| 1423 (I)--) | |
| 1424 | |
| 1425 #define FOR_EACH_VEC_SAFE_ELT_REVERSE(V, I, P) \ | |
| 1426 for (I = vec_safe_length (V) - 1; \ | |
| 1427 vec_safe_iterate ((V), (I), &(P)); \ | |
| 1428 (I)--) | |
| 1429 | |
| 1430 | |
| 1431 /* Return a copy of this vector. */ | |
| 1432 | |
| 1433 template<typename T> | |
| 1434 inline vec<T, va_heap, vl_ptr> | |
| 1435 vec<T, va_heap, vl_ptr>::copy (ALONE_MEM_STAT_DECL) const | |
| 1436 { | |
| 1437 vec<T, va_heap, vl_ptr> new_vec = vNULL; | |
| 1438 if (length ()) | |
| 1439 new_vec.m_vec = m_vec->copy (); | |
| 1440 return new_vec; | |
| 1441 } | |
| 1442 | |
| 1443 | |
| 1444 /* Ensure that the vector has at least RESERVE slots available (if | |
| 1445 EXACT is false), or exactly RESERVE slots available (if EXACT is | |
| 1446 true). | |
| 1447 | |
| 1448 This may create additional headroom if EXACT is false. | |
| 1449 | |
| 1450 Note that this can cause the embedded vector to be reallocated. | |
| 1451 Returns true iff reallocation actually occurred. */ | |
| 1452 | |
| 1453 template<typename T> | |
| 1454 inline bool | |
| 1455 vec<T, va_heap, vl_ptr>::reserve (unsigned nelems, bool exact MEM_STAT_DECL) | |
| 1456 { | |
| 1457 if (space (nelems)) | |
| 1458 return false; | |
| 1459 | |
| 1460 /* For now play a game with va_heap::reserve to hide our auto storage if any, | |
| 1461 this is necessary because it doesn't have enough information to know the | |
| 1462 embedded vector is in auto storage, and so should not be freed. */ | |
| 1463 vec<T, va_heap, vl_embed> *oldvec = m_vec; | |
| 1464 unsigned int oldsize = 0; | |
| 1465 bool handle_auto_vec = m_vec && using_auto_storage (); | |
| 1466 if (handle_auto_vec) | |
| 1467 { | |
| 1468 m_vec = NULL; | |
| 1469 oldsize = oldvec->length (); | |
| 1470 nelems += oldsize; | |
| 1471 } | |
| 1472 | |
| 1473 va_heap::reserve (m_vec, nelems, exact PASS_MEM_STAT); | |
| 1474 if (handle_auto_vec) | |
| 1475 { | |
| 1476 vec_copy_construct (m_vec->address (), oldvec->address (), oldsize); | |
| 1477 m_vec->m_vecpfx.m_num = oldsize; | |
| 1478 } | |
| 1479 | |
| 1480 return true; | |
| 1481 } | |
| 1482 | |
| 1483 | |
| 1484 /* Ensure that this vector has exactly NELEMS slots available. This | |
| 1485 will not create additional headroom. Note this can cause the | |
| 1486 embedded vector to be reallocated. Returns true iff reallocation | |
| 1487 actually occurred. */ | |
| 1488 | |
| 1489 template<typename T> | |
| 1490 inline bool | |
| 1491 vec<T, va_heap, vl_ptr>::reserve_exact (unsigned nelems MEM_STAT_DECL) | |
| 1492 { | |
| 1493 return reserve (nelems, true PASS_MEM_STAT); | |
| 0 | 1494 } |
| 1495 | |
| 111 | 1496 |
| 1497 /* Create the internal vector and reserve NELEMS for it. This is | |
| 1498 exactly like vec::reserve, but the internal vector is | |
| 1499 unconditionally allocated from scratch. The old one, if it | |
| 1500 existed, is lost. */ | |
| 1501 | |
| 1502 template<typename T> | |
| 1503 inline void | |
| 1504 vec<T, va_heap, vl_ptr>::create (unsigned nelems MEM_STAT_DECL) | |
| 1505 { | |
| 1506 m_vec = NULL; | |
| 1507 if (nelems > 0) | |
| 1508 reserve_exact (nelems PASS_MEM_STAT); | |
| 1509 } | |
| 1510 | |
| 1511 | |
| 1512 /* Free the memory occupied by the embedded vector. */ | |
| 1513 | |
| 1514 template<typename T> | |
| 1515 inline void | |
| 1516 vec<T, va_heap, vl_ptr>::release (void) | |
| 1517 { | |
| 1518 if (!m_vec) | |
| 1519 return; | |
| 1520 | |
| 1521 if (using_auto_storage ()) | |
| 1522 { | |
| 1523 m_vec->m_vecpfx.m_num = 0; | |
| 1524 return; | |
| 1525 } | |
| 1526 | |
| 1527 va_heap::release (m_vec); | |
| 1528 } | |
| 1529 | |
| 1530 /* Copy the elements from SRC to the end of this vector as if by memcpy. | |
| 1531 SRC and this vector must be allocated with the same memory | |
| 1532 allocation mechanism. This vector is assumed to have sufficient | |
| 1533 headroom available. */ | |
| 1534 | |
| 1535 template<typename T> | |
| 1536 inline void | |
| 1537 vec<T, va_heap, vl_ptr>::splice (const vec<T, va_heap, vl_ptr> &src) | |
| 1538 { | |
| 1539 if (src.m_vec) | |
| 1540 m_vec->splice (*(src.m_vec)); | |
| 1541 } | |
| 1542 | |
| 0 | 1543 |
| 111 | 1544 /* Copy the elements in SRC to the end of this vector as if by memcpy. |
| 1545 SRC and this vector must be allocated with the same mechanism. | |
| 1546 If there is not enough headroom in this vector, it will be reallocated | |
| 1547 as needed. */ | |
| 1548 | |
| 1549 template<typename T> | |
| 1550 inline void | |
| 1551 vec<T, va_heap, vl_ptr>::safe_splice (const vec<T, va_heap, vl_ptr> &src | |
| 1552 MEM_STAT_DECL) | |
| 1553 { | |
| 1554 if (src.length ()) | |
| 1555 { | |
| 1556 reserve_exact (src.length ()); | |
| 1557 splice (src); | |
| 1558 } | |
| 1559 } | |
| 1560 | |
| 1561 | |
| 1562 /* Push OBJ (a new element) onto the end of the vector. There must be | |
| 1563 sufficient space in the vector. Return a pointer to the slot | |
| 1564 where OBJ was inserted. */ | |
| 1565 | |
| 1566 template<typename T> | |
| 1567 inline T * | |
| 1568 vec<T, va_heap, vl_ptr>::quick_push (const T &obj) | |
| 1569 { | |
| 1570 return m_vec->quick_push (obj); | |
| 1571 } | |
| 1572 | |
| 1573 | |
| 1574 /* Push a new element OBJ onto the end of this vector. Reallocates | |
| 1575 the embedded vector, if needed. Return a pointer to the slot where | |
| 1576 OBJ was inserted. */ | |
| 1577 | |
| 1578 template<typename T> | |
| 1579 inline T * | |
| 1580 vec<T, va_heap, vl_ptr>::safe_push (const T &obj MEM_STAT_DECL) | |
| 1581 { | |
| 1582 reserve (1, false PASS_MEM_STAT); | |
| 1583 return quick_push (obj); | |
| 1584 } | |
| 1585 | |
| 1586 | |
| 1587 /* Pop and return the last element off the end of the vector. */ | |
| 1588 | |
| 1589 template<typename T> | |
| 1590 inline T & | |
| 1591 vec<T, va_heap, vl_ptr>::pop (void) | |
| 1592 { | |
| 1593 return m_vec->pop (); | |
| 0 | 1594 } |
| 1595 | |
| 111 | 1596 |
| 1597 /* Set the length of the vector to LEN. The new length must be less | |
| 1598 than or equal to the current length. This is an O(1) operation. */ | |
| 1599 | |
| 1600 template<typename T> | |
| 1601 inline void | |
| 1602 vec<T, va_heap, vl_ptr>::truncate (unsigned size) | |
| 1603 { | |
| 1604 if (m_vec) | |
| 1605 m_vec->truncate (size); | |
| 1606 else | |
| 1607 gcc_checking_assert (size == 0); | |
| 1608 } | |
| 1609 | |
| 1610 | |
| 1611 /* Grow the vector to a specific length. LEN must be as long or | |
| 1612 longer than the current length. The new elements are | |
| 1613 uninitialized. Reallocate the internal vector, if needed. */ | |
| 1614 | |
| 1615 template<typename T> | |
| 1616 inline void | |
| 1617 vec<T, va_heap, vl_ptr>::safe_grow (unsigned len MEM_STAT_DECL) | |
| 1618 { | |
| 1619 unsigned oldlen = length (); | |
| 1620 gcc_checking_assert (oldlen <= len); | |
| 1621 reserve_exact (len - oldlen PASS_MEM_STAT); | |
| 1622 if (m_vec) | |
| 1623 m_vec->quick_grow (len); | |
| 1624 else | |
| 1625 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
|
1626 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1627 |
| 111 | 1628 |
| 1629 /* Grow the embedded vector to a specific length. LEN must be as | |
| 1630 long or longer than the current length. The new elements are | |
| 1631 initialized to zero. Reallocate the internal vector, if needed. */ | |
| 1632 | |
| 1633 template<typename T> | |
| 1634 inline void | |
| 1635 vec<T, va_heap, vl_ptr>::safe_grow_cleared (unsigned len MEM_STAT_DECL) | |
| 1636 { | |
| 1637 unsigned oldlen = length (); | |
| 1638 size_t growby = len - oldlen; | |
| 1639 safe_grow (len PASS_MEM_STAT); | |
| 1640 if (growby != 0) | |
| 1641 vec_default_construct (address () + oldlen, growby); | |
| 1642 } | |
| 1643 | |
| 1644 | |
| 1645 /* Same as vec::safe_grow but without reallocation of the internal vector. | |
| 1646 If the vector cannot be extended, a runtime assertion will be triggered. */ | |
| 1647 | |
| 1648 template<typename T> | |
| 1649 inline void | |
| 1650 vec<T, va_heap, vl_ptr>::quick_grow (unsigned len) | |
| 1651 { | |
| 1652 gcc_checking_assert (m_vec); | |
| 1653 m_vec->quick_grow (len); | |
| 0 | 1654 } |
| 1655 | |
| 111 | 1656 |
| 1657 /* Same as vec::quick_grow_cleared but without reallocation of the | |
| 1658 internal vector. If the vector cannot be extended, a runtime | |
| 1659 assertion will be triggered. */ | |
| 1660 | |
| 1661 template<typename T> | |
| 1662 inline void | |
| 1663 vec<T, va_heap, vl_ptr>::quick_grow_cleared (unsigned len) | |
| 1664 { | |
| 1665 gcc_checking_assert (m_vec); | |
| 1666 m_vec->quick_grow_cleared (len); | |
| 1667 } | |
| 1668 | |
| 1669 | |
| 1670 /* Insert an element, OBJ, at the IXth position of this vector. There | |
| 1671 must be sufficient space. */ | |
| 1672 | |
| 1673 template<typename T> | |
| 1674 inline void | |
| 1675 vec<T, va_heap, vl_ptr>::quick_insert (unsigned ix, const T &obj) | |
| 1676 { | |
| 1677 m_vec->quick_insert (ix, obj); | |
| 1678 } | |
| 1679 | |
| 1680 | |
| 1681 /* Insert an element, OBJ, at the IXth position of the vector. | |
| 1682 Reallocate the embedded vector, if necessary. */ | |
| 1683 | |
| 1684 template<typename T> | |
| 1685 inline void | |
| 1686 vec<T, va_heap, vl_ptr>::safe_insert (unsigned ix, const T &obj MEM_STAT_DECL) | |
| 1687 { | |
| 1688 reserve (1, false PASS_MEM_STAT); | |
| 1689 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
|
1690 } |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1691 |
| 111 | 1692 |
| 1693 /* Remove an element from the IXth position of this vector. Ordering of | |
| 1694 remaining elements is preserved. This is an O(N) operation due to | |
| 1695 a memmove. */ | |
| 1696 | |
| 1697 template<typename T> | |
| 1698 inline void | |
| 1699 vec<T, va_heap, vl_ptr>::ordered_remove (unsigned ix) | |
| 1700 { | |
| 1701 m_vec->ordered_remove (ix); | |
| 1702 } | |
| 1703 | |
| 1704 | |
| 1705 /* Remove an element from the IXth position of this vector. Ordering | |
| 1706 of remaining elements is destroyed. This is an O(1) operation. */ | |
| 1707 | |
| 1708 template<typename T> | |
| 1709 inline void | |
| 1710 vec<T, va_heap, vl_ptr>::unordered_remove (unsigned ix) | |
| 1711 { | |
| 1712 m_vec->unordered_remove (ix); | |
| 1713 } | |
| 1714 | |
| 1715 | |
| 1716 /* Remove LEN elements starting at the IXth. Ordering is retained. | |
| 1717 This is an O(N) operation due to memmove. */ | |
| 1718 | |
| 1719 template<typename T> | |
| 1720 inline void | |
| 1721 vec<T, va_heap, vl_ptr>::block_remove (unsigned ix, unsigned len) | |
| 1722 { | |
| 1723 m_vec->block_remove (ix, len); | |
| 1724 } | |
| 1725 | |
| 1726 | |
| 1727 /* Sort the contents of this vector with qsort. CMP is the comparison | |
| 1728 function to pass to qsort. */ | |
| 1729 | |
| 1730 template<typename T> | |
| 1731 inline void | |
| 1732 vec<T, va_heap, vl_ptr>::qsort (int (*cmp) (const void *, const void *)) | |
| 1733 { | |
| 1734 if (m_vec) | |
| 1735 m_vec->qsort (cmp); | |
| 0 | 1736 } |
| 1737 | |
| 111 | 1738 |
| 1739 /* Search the contents of the sorted vector with a binary search. | |
| 1740 CMP is the comparison function to pass to bsearch. */ | |
| 1741 | |
| 1742 template<typename T> | |
| 1743 inline T * | |
| 1744 vec<T, va_heap, vl_ptr>::bsearch (const void *key, | |
| 1745 int (*cmp) (const void *, const void *)) | |
| 1746 { | |
| 1747 if (m_vec) | |
| 1748 return m_vec->bsearch (key, cmp); | |
| 1749 return NULL; | |
| 1750 } | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1751 |
| 111 | 1752 |
| 1753 /* Find and return the first position in which OBJ could be inserted | |
| 1754 without changing the ordering of this vector. LESSTHAN is a | |
| 1755 function that returns true if the first argument is strictly less | |
| 1756 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
|
1757 |
| 111 | 1758 template<typename T> |
| 1759 inline unsigned | |
| 1760 vec<T, va_heap, vl_ptr>::lower_bound (T obj, | |
| 1761 bool (*lessthan)(const T &, const T &)) | |
| 1762 const | |
| 1763 { | |
| 1764 return m_vec ? m_vec->lower_bound (obj, lessthan) : 0; | |
| 1765 } | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1766 |
| 111 | 1767 /* Return true if SEARCH is an element of V. Note that this is O(N) in the |
| 1768 size of the vector and so should be used with care. */ | |
| 1769 | |
| 1770 template<typename T> | |
| 1771 inline bool | |
| 1772 vec<T, va_heap, vl_ptr>::contains (const T &search) const | |
| 1773 { | |
| 1774 return m_vec ? m_vec->contains (search) : false; | |
| 1775 } | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1776 |
| 111 | 1777 template<typename T> |
| 1778 inline bool | |
| 1779 vec<T, va_heap, vl_ptr>::using_auto_storage () const | |
| 1780 { | |
| 1781 return m_vec->m_vecpfx.m_using_auto_storage; | |
| 1782 } | |
| 1783 | |
| 1784 /* 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
|
1785 |
| 111 | 1786 template<typename T> |
| 1787 inline void | |
| 1788 release_vec_vec (vec<vec<T> > &vec) | |
| 1789 { | |
| 1790 for (unsigned i = 0; i < vec.length (); i++) | |
| 1791 vec[i].release (); | |
| 1792 | |
| 1793 vec.release (); | |
| 1794 } | |
| 1795 | |
| 1796 #if (GCC_VERSION >= 3000) | |
| 1797 # 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
|
1798 #endif |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1799 |
| 111 | 1800 #endif // GCC_VEC_H |