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