1 | /* Vector API for GNU compiler. |
---|---|

2 | Copyright (C) 2004-2022 Free Software Foundation, Inc. |

3 | Contributed by Nathan Sidwell <nathan@codesourcery.com> |

4 | Re-implemented in C++ by Diego Novillo <dnovillo@google.com> |

5 | |

6 | This file is part of GCC. |

7 | |

8 | GCC is free software; you can redistribute it and/or modify it under |

9 | the terms of the GNU General Public License as published by the Free |

10 | Software Foundation; either version 3, or (at your option) any later |

11 | version. |

12 | |

13 | GCC is distributed in the hope that it will be useful, but WITHOUT ANY |

14 | WARRANTY; without even the implied warranty of MERCHANTABILITY or |

15 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |

16 | for more details. |

17 | |

18 | You should have received a copy of the GNU General Public License |

19 | along with GCC; see the file COPYING3. If not see |

20 | <http://www.gnu.org/licenses/>. */ |

21 | |

22 | #ifndef GCC_VEC_H |

23 | #define GCC_VEC_H |

24 | |

25 | /* Some gen* file have no ggc support as the header file gtype-desc.h is |

26 | missing. Provide these definitions in case ggc.h has not been included. |

27 | This is not a problem because any code that runs before gengtype is built |

28 | will never need to use GC vectors.*/ |

29 | |

30 | extern void ggc_free (void *); |

31 | extern size_t ggc_round_alloc_size (size_t requested_size); |

32 | extern void *ggc_realloc (void *, size_t MEM_STAT_DECL); |

33 | |

34 | /* Templated vector type and associated interfaces. |

35 | |

36 | The interface functions are typesafe and use inline functions, |

37 | sometimes backed by out-of-line generic functions. The vectors are |

38 | designed to interoperate with the GTY machinery. |

39 | |

40 | There are both 'index' and 'iterate' accessors. The index accessor |

41 | is implemented by operator[]. The iterator returns a boolean |

42 | iteration condition and updates the iteration variable passed by |

43 | reference. Because the iterator will be inlined, the address-of |

44 | can be optimized away. |

45 | |

46 | Each operation that increases the number of active elements is |

47 | available in 'quick' and 'safe' variants. The former presumes that |

48 | there is sufficient allocated space for the operation to succeed |

49 | (it dies if there is not). The latter will reallocate the |

50 | vector, if needed. Reallocation causes an exponential increase in |

51 | vector size. If you know you will be adding N elements, it would |

52 | be more efficient to use the reserve operation before adding the |

53 | elements with the 'quick' operation. This will ensure there are at |

54 | least as many elements as you ask for, it will exponentially |

55 | increase if there are too few spare slots. If you want reserve a |

56 | specific number of slots, but do not want the exponential increase |

57 | (for instance, you know this is the last allocation), use the |

58 | reserve_exact operation. You can also create a vector of a |

59 | specific size from the get go. |

60 | |

61 | You should prefer the push and pop operations, as they append and |

62 | remove from the end of the vector. If you need to remove several |

63 | items in one go, use the truncate operation. The insert and remove |

64 | operations allow you to change elements in the middle of the |

65 | vector. There are two remove operations, one which preserves the |

66 | element ordering 'ordered_remove', and one which does not |

67 | 'unordered_remove'. The latter function copies the end element |

68 | into the removed slot, rather than invoke a memmove operation. The |

69 | 'lower_bound' function will determine where to place an item in the |

70 | array using insert that will maintain sorted order. |

71 | |

72 | Vectors are template types with three arguments: the type of the |

73 | elements in the vector, the allocation strategy, and the physical |

74 | layout to use |

75 | |

76 | Four allocation strategies are supported: |

77 | |

78 | - Heap: allocation is done using malloc/free. This is the |

79 | default allocation strategy. |

80 | |

81 | - GC: allocation is done using ggc_alloc/ggc_free. |

82 | |

83 | - GC atomic: same as GC with the exception that the elements |

84 | themselves are assumed to be of an atomic type that does |

85 | not need to be garbage collected. This means that marking |

86 | routines do not need to traverse the array marking the |

87 | individual elements. This increases the performance of |

88 | GC activities. |

89 | |

90 | Two physical layouts are supported: |

91 | |

92 | - Embedded: The vector is structured using the trailing array |

93 | idiom. The last member of the structure is an array of size |

94 | 1. When the vector is initially allocated, a single memory |

95 | block is created to hold the vector's control data and the |

96 | array of elements. These vectors cannot grow without |

97 | reallocation (see discussion on embeddable vectors below). |

98 | |

99 | - Space efficient: The vector is structured as a pointer to an |

100 | embedded vector. This is the default layout. It means that |

101 | vectors occupy a single word of storage before initial |

102 | allocation. Vectors are allowed to grow (the internal |

103 | pointer is reallocated but the main vector instance does not |

104 | need to relocate). |

105 | |

106 | The type, allocation and layout are specified when the vector is |

107 | declared. |

108 | |

109 | If you need to directly manipulate a vector, then the 'address' |

110 | accessor will return the address of the start of the vector. Also |

111 | the 'space' predicate will tell you whether there is spare capacity |

112 | in the vector. You will not normally need to use these two functions. |

113 | |

114 | Notes on the different layout strategies |

115 | |

116 | * Embeddable vectors (vec<T, A, vl_embed>) |

117 | |

118 | These vectors are suitable to be embedded in other data |

119 | structures so that they can be pre-allocated in a contiguous |

120 | memory block. |

121 | |

122 | Embeddable vectors are implemented using the trailing array |

123 | idiom, thus they are not resizeable without changing the address |

124 | of the vector object itself. This means you cannot have |

125 | variables or fields of embeddable vector type -- always use a |

126 | pointer to a vector. The one exception is the final field of a |

127 | structure, which could be a vector type. |

128 | |

129 | You will have to use the embedded_size & embedded_init calls to |

130 | create such objects, and they will not be resizeable (so the |

131 | 'safe' allocation variants are not available). |

132 | |

133 | Properties of embeddable vectors: |

134 | |

135 | - The whole vector and control data are allocated in a single |

136 | contiguous block. It uses the trailing-vector idiom, so |

137 | allocation must reserve enough space for all the elements |

138 | in the vector plus its control data. |

139 | - The vector cannot be re-allocated. |

140 | - The vector cannot grow nor shrink. |

141 | - No indirections needed for access/manipulation. |

142 | - It requires 2 words of storage (prior to vector allocation). |

143 | |

144 | |

145 | * Space efficient vector (vec<T, A, vl_ptr>) |

146 | |

147 | These vectors can grow dynamically and are allocated together |

148 | with their control data. They are suited to be included in data |

149 | structures. Prior to initial allocation, they only take a single |

150 | word of storage. |

151 | |

152 | These vectors are implemented as a pointer to embeddable vectors. |

153 | The semantics allow for this pointer to be NULL to represent |

154 | empty vectors. This way, empty vectors occupy minimal space in |

155 | the structure containing them. |

156 | |

157 | Properties: |

158 | |

159 | - The whole vector and control data are allocated in a single |

160 | contiguous block. |

161 | - The whole vector may be re-allocated. |

162 | - Vector data may grow and shrink. |

163 | - Access and manipulation requires a pointer test and |

164 | indirection. |

165 | - It requires 1 word of storage (prior to vector allocation). |

166 | |

167 | An example of their use would be, |

168 | |

169 | struct my_struct { |

170 | // A space-efficient vector of tree pointers in GC memory. |

171 | vec<tree, va_gc, vl_ptr> v; |

172 | }; |

173 | |

174 | struct my_struct *s; |

175 | |

176 | if (s->v.length ()) { we have some contents } |

177 | s->v.safe_push (decl); // append some decl onto the end |

178 | for (ix = 0; s->v.iterate (ix, &elt); ix++) |

179 | { do something with elt } |

180 | */ |

181 | |

182 | /* Support function for statistics. */ |

183 | extern void dump_vec_loc_statistics (void); |

184 | |

185 | /* Hashtable mapping vec addresses to descriptors. */ |

186 | extern htab_t vec_mem_usage_hash; |

187 | |

188 | /* Control data for vectors. This contains the number of allocated |

189 | and used slots inside a vector. */ |

190 | |

191 | struct vec_prefix |

192 | { |

193 | /* FIXME - These fields should be private, but we need to cater to |

194 | compilers that have stricter notions of PODness for types. */ |

195 | |

196 | /* Memory allocation support routines in vec.cc. */ |

197 | void register_overhead (void *, size_t, size_t CXX_MEM_STAT_INFO); |

198 | void release_overhead (void *, size_t, 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 | size_t elt_size = sizeof (T); |

280 | unsigned alloc |

281 | = vec_prefix::calculate_allocation (v ? &v->m_vecpfx : 0, reserve, exact); |

282 | gcc_checking_assert (alloc); |

283 | |

284 | if (GATHER_STATISTICS && v) |

285 | v->m_vecpfx.release_overhead (v, elt_size * v->allocated (), |

286 | v->allocated (), false); |

287 | |

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); |

292 | |

293 | if (GATHER_STATISTICS) |

294 | v->m_vecpfx.register_overhead (v, alloc, elt_size PASS_MEM_STAT); |

295 | } |

296 | |

297 | |

298 | #if GCC_VERSION >= 4007 |

299 | #pragma GCC diagnostic push |

300 | #pragma GCC diagnostic ignored "-Wfree-nonheap-object" |

301 | #endif |

302 | |

303 | /* Free the heap space allocated for vector V. */ |

304 | |

305 | template<typename T> |

306 | void |

307 | va_heap::release (vec<T, va_heap, vl_embed> *&v) |

308 | { |

309 | size_t elt_size = sizeof (T); |

310 | if (v == NULL) |

311 | return; |

312 | |

313 | if (GATHER_STATISTICS) |

314 | v->m_vecpfx.release_overhead (v, elt_size * v->allocated (), |

315 | v->allocated (), true); |

316 | ::free (v); |

317 | v = NULL; |

318 | } |

319 | |

320 | #if GCC_VERSION >= 4007 |

321 | #pragma GCC diagnostic pop |

322 | #endif |

323 | |

324 | /* Allocator type for GC vectors. Notice that we need the structure |

325 | declaration even if GC is not enabled. */ |

326 | |

327 | struct va_gc |

328 | { |

329 | /* Use vl_embed as the default layout for GC vectors. Due to GTY |

330 | limitations, GC vectors must always be pointers, so it is more |

331 | efficient to use a pointer to the vl_embed layout, rather than |

332 | using a pointer to a pointer as would be the case with vl_ptr. */ |

333 | typedef vl_embed default_layout; |

334 | |

335 | template<typename T, typename A> |

336 | static void reserve (vec<T, A, vl_embed> *&, unsigned, bool |

337 | CXX_MEM_STAT_INFO); |

338 | |

339 | template<typename T, typename A> |

340 | static void release (vec<T, A, vl_embed> *&v); |

341 | }; |

342 | |

343 | |

344 | /* Free GC memory used by V and reset V to NULL. */ |

345 | |

346 | template<typename T, typename A> |

347 | inline void |

348 | va_gc::release (vec<T, A, vl_embed> *&v) |

349 | { |

350 | if (v) |

351 | ::ggc_free (v); |

352 | v = NULL; |

353 | } |

354 | |

355 | |

356 | /* Allocator for GC memory. Ensure there are at least RESERVE free |

357 | slots in V. If EXACT is true, grow exactly, else grow |

358 | exponentially. As a special case, if the vector had not been |

359 | allocated and RESERVE is 0, no vector will be created. */ |

360 | |

361 | template<typename T, typename A> |

362 | void |

363 | va_gc::reserve (vec<T, A, vl_embed> *&v, unsigned reserve, bool exact |

364 | MEM_STAT_DECL) |

365 | { |

366 | unsigned alloc |

367 | = vec_prefix::calculate_allocation (v ? &v->m_vecpfx : 0, reserve, exact); |

368 | if (!alloc) |

369 | { |

370 | ::ggc_free (v); |

371 | v = NULL; |

372 | return; |

373 | } |

374 | |

375 | /* Calculate the amount of space we want. */ |

376 | size_t size = vec<T, A, vl_embed>::embedded_size (alloc); |

377 | |

378 | /* Ask the allocator how much space it will really give us. */ |

379 | size = ::ggc_round_alloc_size (size); |

380 | |

381 | /* Adjust the number of slots accordingly. */ |

382 | size_t vec_offset = sizeof (vec_prefix); |

383 | size_t elt_size = sizeof (T); |

384 | alloc = (size - vec_offset) / elt_size; |

385 | |

386 | /* And finally, recalculate the amount of space we ask for. */ |

387 | size = vec_offset + alloc * elt_size; |

388 | |

389 | unsigned nelem = v ? v->length () : 0; |

390 | v = static_cast <vec<T, A, vl_embed> *> (::ggc_realloc (v, size |

391 | PASS_MEM_STAT)); |

392 | v->embedded_init (alloc, nelem); |

393 | } |

394 | |

395 | |

396 | /* Allocator type for GC vectors. This is for vectors of types |

397 | atomics w.r.t. collection, so allocation and deallocation is |

398 | completely inherited from va_gc. */ |

399 | struct va_gc_atomic : va_gc |

400 | { |

401 | }; |

402 | |

403 | |

404 | /* Generic vector template. Default values for A and L indicate the |

405 | most commonly used strategies. |

406 | |

407 | FIXME - Ideally, they would all be vl_ptr to encourage using regular |

408 | instances for vectors, but the existing GTY machinery is limited |

409 | in that it can only deal with GC objects that are pointers |

410 | themselves. |

411 | |

412 | This means that vector operations that need to deal with |

413 | potentially NULL pointers, must be provided as free |

414 | functions (see the vec_safe_* functions above). */ |

415 | template<typename T, |

416 | typename A = va_heap, |

417 | typename L = typename A::default_layout> |

418 | struct GTY((user)) vec |

419 | { |

420 | }; |

421 | |

422 | /* Allow C++11 range-based 'for' to work directly on vec<T>*. */ |

423 | template<typename T, typename A, typename L> |

424 | T* begin (vec<T,A,L> *v) { return v ? v->begin () : nullptr; } |

425 | template<typename T, typename A, typename L> |

426 | T* end (vec<T,A,L> *v) { return v ? v->end () : nullptr; } |

427 | template<typename T, typename A, typename L> |

428 | const T* begin (const vec<T,A,L> *v) { return v ? v->begin () : nullptr; } |

429 | template<typename T, typename A, typename L> |

430 | const T* end (const vec<T,A,L> *v) { return v ? v->end () : nullptr; } |

431 | |

432 | /* Generic vec<> debug helpers. |

433 | |

434 | These need to be instantiated for each vec<TYPE> used throughout |

435 | the compiler like this: |

436 | |

437 | DEFINE_DEBUG_VEC (TYPE) |

438 | |

439 | The reason we have a debug_helper() is because GDB can't |

440 | disambiguate a plain call to debug(some_vec), and it must be called |

441 | like debug<TYPE>(some_vec). */ |

442 | |

443 | template<typename T> |

444 | void |

445 | debug_helper (vec<T> &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 | /* We need a separate va_gc variant here because default template |

457 | argument for functions cannot be used in c++-98. Once this |

458 | restriction is removed, those variant should be folded with the |

459 | above debug_helper. */ |

460 | |

461 | template<typename T> |

462 | void |

463 | debug_helper (vec<T, va_gc> &ref) |

464 | { |

465 | unsigned i; |

466 | for (i = 0; i < ref.length (); ++i) |

467 | { |

468 | fprintf (stderr, "[%d] = ", i); |

469 | debug_slim (ref[i]); |

470 | fputc ('\n', stderr); |

471 | } |

472 | } |

473 | |

474 | /* Macro to define debug(vec<T>) and debug(vec<T, va_gc>) helper |

475 | functions for a type T. */ |

476 | |

477 | #define DEFINE_DEBUG_VEC(T) \ |

478 | template void debug_helper (vec<T> &); \ |

479 | template void debug_helper (vec<T, va_gc> &); \ |

480 | /* Define the vec<T> debug functions. */ \ |

481 | DEBUG_FUNCTION void \ |

482 | debug (vec<T> &ref) \ |

483 | { \ |

484 | debug_helper <T> (ref); \ |

485 | } \ |

486 | DEBUG_FUNCTION void \ |

487 | debug (vec<T> *ptr) \ |

488 | { \ |

489 | if (ptr) \ |

490 | debug (*ptr); \ |

491 | else \ |

492 | fprintf (stderr, "<nil>\n"); \ |

493 | } \ |

494 | /* Define the vec<T, va_gc> debug functions. */ \ |

495 | DEBUG_FUNCTION void \ |

496 | debug (vec<T, va_gc> &ref) \ |

497 | { \ |

498 | debug_helper <T> (ref); \ |

499 | } \ |

500 | DEBUG_FUNCTION void \ |

501 | debug (vec<T, va_gc> *ptr) \ |

502 | { \ |

503 | if (ptr) \ |

504 | debug (*ptr); \ |

505 | else \ |

506 | fprintf (stderr, "<nil>\n"); \ |

507 | } |

508 | |

509 | /* Default-construct N elements in DST. */ |

510 | |

511 | template <typename T> |

512 | inline void |

513 | vec_default_construct (T *dst, unsigned n) |

514 | { |

515 | #ifdef BROKEN_VALUE_INITIALIZATION |

516 | /* Versions of GCC before 4.4 sometimes leave certain objects |

517 | uninitialized when value initialized, though if the type has |

518 | user defined default ctor, that ctor is invoked. As a workaround |

519 | perform clearing first and then the value initialization, which |

520 | fixes the case when value initialization doesn't initialize due to |

521 | the bugs and should initialize to all zeros, but still allows |

522 | vectors for types with user defined default ctor that initializes |

523 | some or all elements to non-zero. If T has no user defined |

524 | default ctor and some non-static data members have user defined |

525 | default ctors that initialize to non-zero the workaround will |

526 | still not work properly; in that case we just need to provide |

527 | user defined default ctor. */ |

528 | memset (dst, '\0', sizeof (T) * n); |

529 | #endif |

530 | for ( ; n; ++dst, --n) |

531 | ::new (static_cast<void*>(dst)) T (); |

532 | } |

533 | |

534 | /* Copy-construct N elements in DST from *SRC. */ |

535 | |

536 | template <typename T> |

537 | inline void |

538 | vec_copy_construct (T *dst, const T *src, unsigned n) |

539 | { |

540 | for ( ; n; ++dst, ++src, --n) |

541 | ::new (static_cast<void*>(dst)) T (*src); |

542 | } |

543 | |

544 | /* Type to provide zero-initialized values for vec<T, A, L>. This is |

545 | used to provide nil initializers for vec instances. Since vec must |

546 | be a trivially copyable type that can be copied by memcpy and zeroed |

547 | out by memset, it must have defaulted default and copy ctor and copy |

548 | assignment. To initialize a vec either use value initialization |

549 | (e.g., vec() or vec v{ };) or assign it the value vNULL. This isn't |

550 | needed for file-scope and function-local static vectors, which are |

551 | zero-initialized by default. */ |

552 | struct vnull { }; |

553 | constexpr vnull vNULL{ }; |

554 | |

555 | |

556 | /* Embeddable vector. These vectors are suitable to be embedded |

557 | in other data structures so that they can be pre-allocated in a |

558 | contiguous memory block. |

559 | |

560 | Embeddable vectors are implemented using the trailing array idiom, |

561 | thus they are not resizeable without changing the address of the |

562 | vector object itself. This means you cannot have variables or |

563 | fields of embeddable vector type -- always use a pointer to a |

564 | vector. The one exception is the final field of a structure, which |

565 | could be a vector type. |

566 | |

567 | You will have to use the embedded_size & embedded_init calls to |

568 | create such objects, and they will not be resizeable (so the 'safe' |

569 | allocation variants are not available). |

570 | |

571 | Properties: |

572 | |

573 | - The whole vector and control data are allocated in a single |

574 | contiguous block. It uses the trailing-vector idiom, so |

575 | allocation must reserve enough space for all the elements |

576 | in the vector plus its control data. |

577 | - The vector cannot be re-allocated. |

578 | - The vector cannot grow nor shrink. |

579 | - No indirections needed for access/manipulation. |

580 | - It requires 2 words of storage (prior to vector allocation). */ |

581 | |

582 | template<typename T, typename A> |

583 | struct GTY((user)) vec<T, A, vl_embed> |

584 | { |

585 | public: |

586 | unsigned allocated (void) const { return m_vecpfx.m_alloc; } |

587 | unsigned length (void) const { return m_vecpfx.m_num; } |

588 | bool is_empty (void) const { return m_vecpfx.m_num == 0; } |

589 | T *address (void) { return m_vecdata; } |

590 | const T *address (void) const { return m_vecdata; } |

591 | T *begin () { return address (); } |

592 | const T *begin () const { return address (); } |

593 | T *end () { return address () + length (); } |

594 | const T *end () const { return address () + length (); } |

595 | const T &operator[] (unsigned) const; |

596 | T &operator[] (unsigned); |

597 | T &last (void); |

598 | bool space (unsigned) const; |

599 | bool iterate (unsigned, T *) const; |

600 | bool iterate (unsigned, T **) const; |

601 | vec *copy (ALONE_CXX_MEM_STAT_INFO) const; |

602 | void splice (const vec &); |

603 | void splice (const vec *src); |

604 | T *quick_push (const T &); |

605 | T &pop (void); |

606 | void truncate (unsigned); |

607 | void quick_insert (unsigned, const T &); |

608 | void ordered_remove (unsigned); |

609 | void unordered_remove (unsigned); |

610 | void block_remove (unsigned, unsigned); |

611 | void qsort (int (*) (const void *, const void *)); |

612 | void sort (int (*) (const void *, const void *, void *), void *); |

613 | void stablesort (int (*) (const void *, const void *, void *), void *); |

614 | T *bsearch (const void *key, int (*compar)(const void *, const void *)); |

615 | T *bsearch (const void *key, |

616 | int (*compar)(const void *, const void *, void *), void *); |

617 | unsigned lower_bound (T, bool (*)(const T &, const T &)) const; |

618 | bool contains (const T &search) const; |

619 | static size_t embedded_size (unsigned); |

620 | void embedded_init (unsigned, unsigned = 0, unsigned = 0); |

621 | void quick_grow (unsigned len); |

622 | void quick_grow_cleared (unsigned len); |

623 | |

624 | /* vec class can access our internal data and functions. */ |

625 | template <typename, typename, typename> friend struct vec; |

626 | |

627 | /* The allocator types also need access to our internals. */ |

628 | friend struct va_gc; |

629 | friend struct va_gc_atomic; |

630 | friend struct va_heap; |

631 | |

632 | /* FIXME - These fields should be private, but we need to cater to |

633 | compilers that have stricter notions of PODness for types. */ |

634 | vec_prefix m_vecpfx; |

635 | T m_vecdata[1]; |

636 | }; |

637 | |

638 | |

639 | /* Convenience wrapper functions to use when dealing with pointers to |

640 | embedded vectors. Some functionality for these vectors must be |

641 | provided via free functions for these reasons: |

642 | |

643 | 1- The pointer may be NULL (e.g., before initial allocation). |

644 | |

645 | 2- When the vector needs to grow, it must be reallocated, so |

646 | the pointer will change its value. |

647 | |

648 | Because of limitations with the current GC machinery, all vectors |

649 | in GC memory *must* be pointers. */ |

650 | |

651 | |

652 | /* If V contains no room for NELEMS elements, return false. Otherwise, |

653 | return true. */ |

654 | template<typename T, typename A> |

655 | inline bool |

656 | vec_safe_space (const vec<T, A, vl_embed> *v, unsigned nelems) |

657 | { |

658 | return v ? v->space (nelems) : nelems == 0; |

659 | } |

660 | |

661 | |

662 | /* If V is NULL, return 0. Otherwise, return V->length(). */ |

663 | template<typename T, typename A> |

664 | inline unsigned |

665 | vec_safe_length (const vec<T, A, vl_embed> *v) |

666 | { |

667 | return v ? v->length () : 0; |

668 | } |

669 | |

670 | |

671 | /* If V is NULL, return NULL. Otherwise, return V->address(). */ |

672 | template<typename T, typename A> |

673 | inline T * |

674 | vec_safe_address (vec<T, A, vl_embed> *v) |

675 | { |

676 | return v ? v->address () : NULL; |

677 | } |

678 | |

679 | |

680 | /* If V is NULL, return true. Otherwise, return V->is_empty(). */ |

681 | template<typename T, typename A> |

682 | inline bool |

683 | vec_safe_is_empty (vec<T, A, vl_embed> *v) |

684 | { |

685 | return v ? v->is_empty () : true; |

686 | } |

687 | |

688 | /* If V does not have space for NELEMS elements, call |

689 | V->reserve(NELEMS, EXACT). */ |

690 | template<typename T, typename A> |

691 | inline bool |

692 | vec_safe_reserve (vec<T, A, vl_embed> *&v, unsigned nelems, bool exact = false |

693 | CXX_MEM_STAT_INFO) |

694 | { |

695 | bool extend = nelems ? !vec_safe_space (v, nelems) : false; |

696 | if (extend) |

697 | A::reserve (v, nelems, exact PASS_MEM_STAT); |

698 | return extend; |

699 | } |

700 | |

701 | template<typename T, typename A> |

702 | inline bool |

703 | vec_safe_reserve_exact (vec<T, A, vl_embed> *&v, unsigned nelems |

704 | CXX_MEM_STAT_INFO) |

705 | { |

706 | return vec_safe_reserve (v, nelems, true PASS_MEM_STAT); |

707 | } |

708 | |

709 | |

710 | /* Allocate GC memory for V with space for NELEMS slots. If NELEMS |

711 | is 0, V is initialized to NULL. */ |

712 | |

713 | template<typename T, typename A> |

714 | inline void |

715 | vec_alloc (vec<T, A, vl_embed> *&v, unsigned nelems CXX_MEM_STAT_INFO) |

716 | { |

717 | v = NULL; |

718 | vec_safe_reserve (v, nelems, false PASS_MEM_STAT); |

719 | } |

720 | |

721 | |

722 | /* Free the GC memory allocated by vector V and set it to NULL. */ |

723 | |

724 | template<typename T, typename A> |

725 | inline void |

726 | vec_free (vec<T, A, vl_embed> *&v) |

727 | { |

728 | A::release (v); |

729 | } |

730 | |

731 | |

732 | /* Grow V to length LEN. Allocate it, if necessary. */ |

733 | template<typename T, typename A> |

734 | inline void |

735 | vec_safe_grow (vec<T, A, vl_embed> *&v, unsigned len, |

736 | bool exact = false CXX_MEM_STAT_INFO) |

737 | { |

738 | unsigned oldlen = vec_safe_length (v); |

739 | gcc_checking_assert (len >= oldlen); |

740 | vec_safe_reserve (v, len - oldlen, exact PASS_MEM_STAT); |

741 | v->quick_grow (len); |

742 | } |

743 | |

744 | |

745 | /* If V is NULL, allocate it. Call V->safe_grow_cleared(LEN). */ |

746 | template<typename T, typename A> |

747 | inline void |

748 | vec_safe_grow_cleared (vec<T, A, vl_embed> *&v, unsigned len, |

749 | bool exact = false CXX_MEM_STAT_INFO) |

750 | { |

751 | unsigned oldlen = vec_safe_length (v); |

752 | vec_safe_grow (v, len, exact PASS_MEM_STAT); |

753 | vec_default_construct (v->address () + oldlen, len - oldlen); |

754 | } |

755 | |

756 | |

757 | /* Assume V is not NULL. */ |

758 | |

759 | template<typename T> |

760 | inline void |

761 | vec_safe_grow_cleared (vec<T, va_heap, vl_ptr> *&v, |

762 | unsigned len, bool exact = false CXX_MEM_STAT_INFO) |

763 | { |

764 | v->safe_grow_cleared (len, exact PASS_MEM_STAT); |

765 | } |

766 | |

767 | /* If V does not have space for NELEMS elements, call |

768 | V->reserve(NELEMS, EXACT). */ |

769 | |

770 | template<typename T> |

771 | inline bool |

772 | vec_safe_reserve (vec<T, va_heap, vl_ptr> *&v, unsigned nelems, bool exact = false |

773 | CXX_MEM_STAT_INFO) |

774 | { |

775 | return v->reserve (nelems, exact); |

776 | } |

777 | |

778 | |

779 | /* If V is NULL return false, otherwise return V->iterate(IX, PTR). */ |

780 | template<typename T, typename A> |

781 | inline bool |

782 | vec_safe_iterate (const vec<T, A, vl_embed> *v, unsigned ix, T **ptr) |

783 | { |

784 | if (v) |

785 | return v->iterate (ix, ptr); |

786 | else |

787 | { |

788 | *ptr = 0; |

789 | return false; |

790 | } |

791 | } |

792 | |

793 | template<typename T, typename A> |

794 | inline bool |

795 | vec_safe_iterate (const vec<T, A, vl_embed> *v, unsigned ix, T *ptr) |

796 | { |

797 | if (v) |

798 | return v->iterate (ix, ptr); |

799 | else |

800 | { |

801 | *ptr = 0; |

802 | return false; |

803 | } |

804 | } |

805 | |

806 | |

807 | /* If V has no room for one more element, reallocate it. Then call |

808 | V->quick_push(OBJ). */ |

809 | template<typename T, typename A> |

810 | inline T * |

811 | vec_safe_push (vec<T, A, vl_embed> *&v, const T &obj CXX_MEM_STAT_INFO) |

812 | { |

813 | vec_safe_reserve (v, 1, false PASS_MEM_STAT); |

814 | return v->quick_push (obj); |

815 | } |

816 | |

817 | |

818 | /* if V has no room for one more element, reallocate it. Then call |

819 | V->quick_insert(IX, OBJ). */ |

820 | template<typename T, typename A> |

821 | inline void |

822 | vec_safe_insert (vec<T, A, vl_embed> *&v, unsigned ix, const T &obj |

823 | CXX_MEM_STAT_INFO) |

824 | { |

825 | vec_safe_reserve (v, 1, false PASS_MEM_STAT); |

826 | v->quick_insert (ix, obj); |

827 | } |

828 | |

829 | |

830 | /* If V is NULL, do nothing. Otherwise, call V->truncate(SIZE). */ |

831 | template<typename T, typename A> |

832 | inline void |

833 | vec_safe_truncate (vec<T, A, vl_embed> *v, unsigned size) |

834 | { |

835 | if (v) |

836 | v->truncate (size); |

837 | } |

838 | |

839 | |

840 | /* If SRC is not NULL, return a pointer to a copy of it. */ |

841 | template<typename T, typename A> |

842 | inline vec<T, A, vl_embed> * |

843 | vec_safe_copy (vec<T, A, vl_embed> *src CXX_MEM_STAT_INFO) |

844 | { |

845 | return src ? src->copy (ALONE_PASS_MEM_STAT) : NULL; |

846 | } |

847 | |

848 | /* Copy the elements from SRC to the end of DST as if by memcpy. |

849 | Reallocate DST, if necessary. */ |

850 | template<typename T, typename A> |

851 | inline void |

852 | vec_safe_splice (vec<T, A, vl_embed> *&dst, const vec<T, A, vl_embed> *src |

853 | CXX_MEM_STAT_INFO) |

854 | { |

855 | unsigned src_len = vec_safe_length (src); |

856 | if (src_len) |

857 | { |

858 | vec_safe_reserve_exact (dst, vec_safe_length (dst) + src_len |

859 | PASS_MEM_STAT); |

860 | dst->splice (*src); |

861 | } |

862 | } |

863 | |

864 | /* Return true if SEARCH is an element of V. Note that this is O(N) in the |

865 | size of the vector and so should be used with care. */ |

866 | |

867 | template<typename T, typename A> |

868 | inline bool |

869 | vec_safe_contains (vec<T, A, vl_embed> *v, const T &search) |

870 | { |

871 | return v ? v->contains (search) : false; |

872 | } |

873 | |

874 | /* Index into vector. Return the IX'th element. IX must be in the |

875 | domain of the vector. */ |

876 | |

877 | template<typename T, typename A> |

878 | inline const T & |

879 | vec<T, A, vl_embed>::operator[] (unsigned ix) const |

880 | { |

881 | gcc_checking_assert (ix < m_vecpfx.m_num); |

882 | return m_vecdata[ix]; |

883 | } |

884 | |

885 | template<typename T, typename A> |

886 | inline T & |

887 | vec<T, A, vl_embed>::operator[] (unsigned ix) |

888 | { |

889 | gcc_checking_assert (ix < m_vecpfx.m_num); |

890 | return m_vecdata[ix]; |

891 | } |

892 | |

893 | |

894 | /* Get the final element of the vector, which must not be empty. */ |

895 | |

896 | template<typename T, typename A> |

897 | inline T & |

898 | vec<T, A, vl_embed>::last (void) |

899 | { |

900 | gcc_checking_assert (m_vecpfx.m_num > 0); |

901 | return (*this)[m_vecpfx.m_num - 1]; |

902 | } |

903 | |

904 | |

905 | /* If this vector has space for NELEMS additional entries, return |

906 | true. You usually only need to use this if you are doing your |

907 | own vector reallocation, for instance on an embedded vector. This |

908 | returns true in exactly the same circumstances that vec::reserve |

909 | will. */ |

910 | |

911 | template<typename T, typename A> |

912 | inline bool |

913 | vec<T, A, vl_embed>::space (unsigned nelems) const |

914 | { |

915 | return m_vecpfx.m_alloc - m_vecpfx.m_num >= nelems; |

916 | } |

917 | |

918 | |

919 | /* Return iteration condition and update *PTR to (a copy of) the IX'th |

920 | element of this vector. Use this to iterate over the elements of a |

921 | vector as follows, |

922 | |

923 | for (ix = 0; v->iterate (ix, &val); ix++) |

924 | continue; */ |

925 | |

926 | template<typename T, typename A> |

927 | inline bool |

928 | vec<T, A, vl_embed>::iterate (unsigned ix, T *ptr) const |

929 | { |

930 | if (ix < m_vecpfx.m_num) |

931 | { |

932 | *ptr = m_vecdata[ix]; |

933 | return true; |

934 | } |

935 | else |

936 | { |

937 | *ptr = 0; |

938 | return false; |

939 | } |

940 | } |

941 | |

942 | |

943 | /* Return iteration condition and update *PTR to point to the |

944 | IX'th element of this vector. Use this to iterate over the |

945 | elements of a vector as follows, |

946 | |

947 | for (ix = 0; v->iterate (ix, &ptr); ix++) |

948 | continue; |

949 | |

950 | This variant is for vectors of objects. */ |

951 | |

952 | template<typename T, typename A> |

953 | inline bool |

954 | vec<T, A, vl_embed>::iterate (unsigned ix, T **ptr) const |

955 | { |

956 | if (ix < m_vecpfx.m_num) |

957 | { |

958 | *ptr = CONST_CAST (T *, &m_vecdata[ix]); |

959 | return true; |

960 | } |

961 | else |

962 | { |

963 | *ptr = 0; |

964 | return false; |

965 | } |

966 | } |

967 | |

968 | |

969 | /* Return a pointer to a copy of this vector. */ |

970 | |

971 | template<typename T, typename A> |

972 | inline vec<T, A, vl_embed> * |

973 | vec<T, A, vl_embed>::copy (ALONE_MEM_STAT_DECL) const |

974 | { |

975 | vec<T, A, vl_embed> *new_vec = NULL; |

976 | unsigned len = length (); |

977 | if (len) |

978 | { |

979 | vec_alloc (new_vec, len PASS_MEM_STAT); |

980 | new_vec->embedded_init (len, len); |

981 | vec_copy_construct (new_vec->address (), m_vecdata, len); |

982 | } |

983 | return new_vec; |

984 | } |

985 | |

986 | |

987 | /* Copy the elements from SRC to the end of this vector as if by memcpy. |

988 | The vector must have sufficient headroom available. */ |

989 | |

990 | template<typename T, typename A> |

991 | inline void |

992 | vec<T, A, vl_embed>::splice (const vec<T, A, vl_embed> &src) |

993 | { |

994 | unsigned len = src.length (); |

995 | if (len) |

996 | { |

997 | gcc_checking_assert (space (len)); |

998 | vec_copy_construct (end (), src.address (), len); |

999 | m_vecpfx.m_num += len; |

1000 | } |

1001 | } |

1002 | |

1003 | template<typename T, typename A> |

1004 | inline void |

1005 | vec<T, A, vl_embed>::splice (const vec<T, A, vl_embed> *src) |

1006 | { |

1007 | if (src) |

1008 | splice (*src); |

1009 | } |

1010 | |

1011 | |

1012 | /* Push OBJ (a new element) onto the end of the vector. There must be |

1013 | sufficient space in the vector. Return a pointer to the slot |

1014 | where OBJ was inserted. */ |

1015 | |

1016 | template<typename T, typename A> |

1017 | inline T * |

1018 | vec<T, A, vl_embed>::quick_push (const T &obj) |

1019 | { |

1020 | gcc_checking_assert (space (1)); |

1021 | T *slot = &m_vecdata[m_vecpfx.m_num++]; |

1022 | *slot = obj; |

1023 | return slot; |

1024 | } |

1025 | |

1026 | |

1027 | /* Pop and return the last element off the end of the vector. */ |

1028 | |

1029 | template<typename T, typename A> |

1030 | inline T & |

1031 | vec<T, A, vl_embed>::pop (void) |

1032 | { |

1033 | gcc_checking_assert (length () > 0); |

1034 | return m_vecdata[--m_vecpfx.m_num]; |

1035 | } |

1036 | |

1037 | |

1038 | /* Set the length of the vector to SIZE. The new length must be less |

1039 | than or equal to the current length. This is an O(1) operation. */ |

1040 | |

1041 | template<typename T, typename A> |

1042 | inline void |

1043 | vec<T, A, vl_embed>::truncate (unsigned size) |

1044 | { |

1045 | gcc_checking_assert (length () >= size); |

1046 | m_vecpfx.m_num = size; |

1047 | } |

1048 | |

1049 | |

1050 | /* Insert an element, OBJ, at the IXth position of this vector. There |

1051 | must be sufficient space. */ |

1052 | |

1053 | template<typename T, typename A> |

1054 | inline void |

1055 | vec<T, A, vl_embed>::quick_insert (unsigned ix, const T &obj) |

1056 | { |

1057 | gcc_checking_assert (length () < allocated ()); |

1058 | gcc_checking_assert (ix <= length ()); |

1059 | T *slot = &m_vecdata[ix]; |

1060 | memmove (slot + 1, slot, (m_vecpfx.m_num++ - ix) * sizeof (T)); |

1061 | *slot = obj; |

1062 | } |

1063 | |

1064 | |

1065 | /* Remove an element from the IXth position of this vector. Ordering of |

1066 | remaining elements is preserved. This is an O(N) operation due to |

1067 | memmove. */ |

1068 | |

1069 | template<typename T, typename A> |

1070 | inline void |

1071 | vec<T, A, vl_embed>::ordered_remove (unsigned ix) |

1072 | { |

1073 | gcc_checking_assert (ix < length ()); |

1074 | T *slot = &m_vecdata[ix]; |

1075 | memmove (slot, slot + 1, (--m_vecpfx.m_num - ix) * sizeof (T)); |

1076 | } |

1077 | |

1078 | |

1079 | /* Remove elements in [START, END) from VEC for which COND holds. Ordering of |

1080 | remaining elements is preserved. This is an O(N) operation. */ |

1081 | |

1082 | #define VEC_ORDERED_REMOVE_IF_FROM_TO(vec, read_index, write_index, \ |

1083 | elem_ptr, start, end, cond) \ |

1084 | { \ |

1085 | gcc_assert ((end) <= (vec).length ()); \ |

1086 | for (read_index = write_index = (start); read_index < (end); \ |

1087 | ++read_index) \ |

1088 | { \ |

1089 | elem_ptr = &(vec)[read_index]; \ |

1090 | bool remove_p = (cond); \ |

1091 | if (remove_p) \ |

1092 | continue; \ |

1093 | \ |

1094 | if (read_index != write_index) \ |

1095 | (vec)[write_index] = (vec)[read_index]; \ |

1096 | \ |

1097 | write_index++; \ |

1098 | } \ |

1099 | \ |

1100 | if (read_index - write_index > 0) \ |

1101 | (vec).block_remove (write_index, read_index - write_index); \ |

1102 | } |

1103 | |

1104 | |

1105 | /* Remove elements from VEC for which COND holds. Ordering of remaining |

1106 | elements is preserved. This is an O(N) operation. */ |

1107 | |

1108 | #define VEC_ORDERED_REMOVE_IF(vec, read_index, write_index, elem_ptr, \ |

1109 | cond) \ |

1110 | VEC_ORDERED_REMOVE_IF_FROM_TO ((vec), read_index, write_index, \ |

1111 | elem_ptr, 0, (vec).length (), (cond)) |

1112 | |

1113 | /* Remove an element from the IXth position of this vector. Ordering of |

1114 | remaining elements is destroyed. This is an O(1) operation. */ |

1115 | |

1116 | template<typename T, typename A> |

1117 | inline void |

1118 | vec<T, A, vl_embed>::unordered_remove (unsigned ix) |

1119 | { |

1120 | gcc_checking_assert (ix < length ()); |

1121 | m_vecdata[ix] = m_vecdata[--m_vecpfx.m_num]; |

1122 | } |

1123 | |

1124 | |

1125 | /* Remove LEN elements starting at the IXth. Ordering is retained. |

1126 | This is an O(N) operation due to memmove. */ |

1127 | |

1128 | template<typename T, typename A> |

1129 | inline void |

1130 | vec<T, A, vl_embed>::block_remove (unsigned ix, unsigned len) |

1131 | { |

1132 | gcc_checking_assert (ix + len <= length ()); |

1133 | T *slot = &m_vecdata[ix]; |

1134 | m_vecpfx.m_num -= len; |

1135 | memmove (slot, slot + len, (m_vecpfx.m_num - ix) * sizeof (T)); |

1136 | } |

1137 | |

1138 | |

1139 | /* Sort the contents of this vector with qsort. CMP is the comparison |

1140 | function to pass to qsort. */ |

1141 | |

1142 | template<typename T, typename A> |

1143 | inline void |

1144 | vec<T, A, vl_embed>::qsort (int (*cmp) (const void *, const void *)) |

1145 | { |

1146 | if (length () > 1) |

1147 | gcc_qsort (address (), length (), sizeof (T), cmp); |

1148 | } |

1149 | |

1150 | /* Sort the contents of this vector with qsort. CMP is the comparison |

1151 | function to pass to qsort. */ |

1152 | |

1153 | template<typename T, typename A> |

1154 | inline void |

1155 | vec<T, A, vl_embed>::sort (int (*cmp) (const void *, const void *, void *), |

1156 | void *data) |

1157 | { |

1158 | if (length () > 1) |

1159 | gcc_sort_r (address (), length (), sizeof (T), cmp, data); |

1160 | } |

1161 | |

1162 | /* Sort the contents of this vector with gcc_stablesort_r. CMP is the |

1163 | comparison function to pass to qsort. */ |

1164 | |

1165 | template<typename T, typename A> |

1166 | inline void |

1167 | vec<T, A, vl_embed>::stablesort (int (*cmp) (const void *, const void *, |

1168 | void *), void *data) |

1169 | { |

1170 | if (length () > 1) |

1171 | gcc_stablesort_r (address (), length (), sizeof (T), cmp, data); |

1172 | } |

1173 | |

1174 | /* Search the contents of the sorted vector with a binary search. |

1175 | CMP is the comparison function to pass to bsearch. */ |

1176 | |

1177 | template<typename T, typename A> |

1178 | inline T * |

1179 | vec<T, A, vl_embed>::bsearch (const void *key, |

1180 | int (*compar) (const void *, const void *)) |

1181 | { |

1182 | const void *base = this->address (); |

1183 | size_t nmemb = this->length (); |

1184 | size_t size = sizeof (T); |

1185 | /* The following is a copy of glibc stdlib-bsearch.h. */ |

1186 | size_t l, u, idx; |

1187 | const void *p; |

1188 | int comparison; |

1189 | |

1190 | l = 0; |

1191 | u = nmemb; |

1192 | while (l < u) |

1193 | { |

1194 | idx = (l + u) / 2; |

1195 | p = (const void *) (((const char *) base) + (idx * size)); |

1196 | comparison = (*compar) (key, p); |

1197 | if (comparison < 0) |

1198 | u = idx; |

1199 | else if (comparison > 0) |

1200 | l = idx + 1; |

1201 | else |

1202 | return (T *)const_cast<void *>(p); |

1203 | } |

1204 | |

1205 | return NULL; |

1206 | } |

1207 | |

1208 | /* Search the contents of the sorted vector with a binary search. |

1209 | CMP is the comparison function to pass to bsearch. */ |

1210 | |

1211 | template<typename T, typename A> |

1212 | inline T * |

1213 | vec<T, A, vl_embed>::bsearch (const void *key, |

1214 | int (*compar) (const void *, const void *, |

1215 | void *), void *data) |

1216 | { |

1217 | const void *base = this->address (); |

1218 | size_t nmemb = this->length (); |

1219 | size_t size = sizeof (T); |

1220 | /* The following is a copy of glibc stdlib-bsearch.h. */ |

1221 | size_t l, u, idx; |

1222 | const void *p; |

1223 | int comparison; |

1224 | |

1225 | l = 0; |

1226 | u = nmemb; |

1227 | while (l < u) |

1228 | { |

1229 | idx = (l + u) / 2; |

1230 | p = (const void *) (((const char *) base) + (idx * size)); |

1231 | comparison = (*compar) (key, p, data); |

1232 | if (comparison < 0) |

1233 | u = idx; |

1234 | else if (comparison > 0) |

1235 | l = idx + 1; |

1236 | else |

1237 | return (T *)const_cast<void *>(p); |

1238 | } |

1239 | |

1240 | return NULL; |

1241 | } |

1242 | |

1243 | /* Return true if SEARCH is an element of V. Note that this is O(N) in the |

1244 | size of the vector and so should be used with care. */ |

1245 | |

1246 | template<typename T, typename A> |

1247 | inline bool |

1248 | vec<T, A, vl_embed>::contains (const T &search) const |

1249 | { |

1250 | unsigned int len = length (); |

1251 | for (unsigned int i = 0; i < len; i++) |

1252 | if ((*this)[i] == search) |

1253 | return true; |

1254 | |

1255 | return false; |

1256 | } |

1257 | |

1258 | /* Find and return the first position in which OBJ could be inserted |

1259 | without changing the ordering of this vector. LESSTHAN is a |

1260 | function that returns true if the first argument is strictly less |

1261 | than the second. */ |

1262 | |

1263 | template<typename T, typename A> |

1264 | unsigned |

1265 | vec<T, A, vl_embed>::lower_bound (T obj, bool (*lessthan)(const T &, const T &)) |

1266 | const |

1267 | { |

1268 | unsigned int len = length (); |

1269 | unsigned int half, middle; |

1270 | unsigned int first = 0; |

1271 | while (len > 0) |

1272 | { |

1273 | half = len / 2; |

1274 | middle = first; |

1275 | middle += half; |

1276 | T middle_elem = (*this)[middle]; |

1277 | if (lessthan (middle_elem, obj)) |

1278 | { |

1279 | first = middle; |

1280 | ++first; |

1281 | len = len - half - 1; |

1282 | } |

1283 | else |

1284 | len = half; |

1285 | } |

1286 | return first; |

1287 | } |

1288 | |

1289 | |

1290 | /* Return the number of bytes needed to embed an instance of an |

1291 | embeddable vec inside another data structure. |

1292 | |

1293 | Use these methods to determine the required size and initialization |

1294 | of a vector V of type T embedded within another structure (as the |

1295 | final member): |

1296 | |

1297 | size_t vec<T, A, vl_embed>::embedded_size (unsigned alloc); |

1298 | void v->embedded_init (unsigned alloc, unsigned num); |

1299 | |

1300 | These allow the caller to perform the memory allocation. */ |

1301 | |

1302 | template<typename T, typename A> |

1303 | inline size_t |

1304 | vec<T, A, vl_embed>::embedded_size (unsigned alloc) |

1305 | { |

1306 | struct alignas (T) U { char data[sizeof (T)]; }; |

1307 | typedef vec<U, A, vl_embed> vec_embedded; |

1308 | typedef typename std::conditional<std::is_standard_layout<T>::value, |

1309 | vec, vec_embedded>::type vec_stdlayout; |

1310 | static_assert (sizeof (vec_stdlayout) == sizeof (vec), ""); |

1311 | static_assert (alignof (vec_stdlayout) == alignof (vec), ""); |

1312 | return offsetof (vec_stdlayout, m_vecdata) + alloc * sizeof (T); |

1313 | } |

1314 | |

1315 | |

1316 | /* Initialize the vector to contain room for ALLOC elements and |

1317 | NUM active elements. */ |

1318 | |

1319 | template<typename T, typename A> |

1320 | inline void |

1321 | vec<T, A, vl_embed>::embedded_init (unsigned alloc, unsigned num, unsigned aut) |

1322 | { |

1323 | m_vecpfx.m_alloc = alloc; |

1324 | m_vecpfx.m_using_auto_storage = aut; |

1325 | m_vecpfx.m_num = num; |

1326 | } |

1327 | |

1328 | |

1329 | /* Grow the vector to a specific length. LEN must be as long or longer than |

1330 | the current length. The new elements are uninitialized. */ |

1331 | |

1332 | template<typename T, typename A> |

1333 | inline void |

1334 | vec<T, A, vl_embed>::quick_grow (unsigned len) |

1335 | { |

1336 | gcc_checking_assert (length () <= len && len <= m_vecpfx.m_alloc); |

1337 | m_vecpfx.m_num = len; |

1338 | } |

1339 | |

1340 | |

1341 | /* Grow the vector to a specific length. LEN must be as long or longer than |

1342 | the current length. The new elements are initialized to zero. */ |

1343 | |

1344 | template<typename T, typename A> |

1345 | inline void |

1346 | vec<T, A, vl_embed>::quick_grow_cleared (unsigned len) |

1347 | { |

1348 | unsigned oldlen = length (); |

1349 | size_t growby = len - oldlen; |

1350 | quick_grow (len); |

1351 | if (growby != 0) |

1352 | vec_default_construct (address () + oldlen, growby); |

1353 | } |

1354 | |

1355 | /* Garbage collection support for vec<T, A, vl_embed>. */ |

1356 | |

1357 | template<typename T> |

1358 | void |

1359 | gt_ggc_mx (vec<T, va_gc> *v) |

1360 | { |

1361 | extern void gt_ggc_mx (T &); |

1362 | for (unsigned i = 0; i < v->length (); i++) |

1363 | gt_ggc_mx ((*v)[i]); |

1364 | } |

1365 | |

1366 | template<typename T> |

1367 | void |

1368 | gt_ggc_mx (vec<T, va_gc_atomic, vl_embed> *v ATTRIBUTE_UNUSED) |

1369 | { |

1370 | /* Nothing to do. Vectors of atomic types wrt GC do not need to |

1371 | be traversed. */ |

1372 | } |

1373 | |

1374 | |

1375 | /* PCH support for vec<T, A, vl_embed>. */ |

1376 | |

1377 | template<typename T, typename A> |

1378 | void |

1379 | gt_pch_nx (vec<T, A, vl_embed> *v) |

1380 | { |

1381 | extern void gt_pch_nx (T &); |

1382 | for (unsigned i = 0; i < v->length (); i++) |

1383 | gt_pch_nx ((*v)[i]); |

1384 | } |

1385 | |

1386 | template<typename T, typename A> |

1387 | void |

1388 | gt_pch_nx (vec<T *, A, vl_embed> *v, gt_pointer_operator op, void *cookie) |

1389 | { |

1390 | for (unsigned i = 0; i < v->length (); i++) |

1391 | op (&((*v)[i]), NULL, cookie); |

1392 | } |

1393 | |

1394 | template<typename T, typename A> |

1395 | void |

1396 | gt_pch_nx (vec<T, A, vl_embed> *v, gt_pointer_operator op, void *cookie) |

1397 | { |

1398 | extern void gt_pch_nx (T *, gt_pointer_operator, void *); |

1399 | for (unsigned i = 0; i < v->length (); i++) |

1400 | gt_pch_nx (&((*v)[i]), op, cookie); |

1401 | } |

1402 | |

1403 | |

1404 | /* Space efficient vector. These vectors can grow dynamically and are |

1405 | allocated together with their control data. They are suited to be |

1406 | included in data structures. Prior to initial allocation, they |

1407 | only take a single word of storage. |

1408 | |

1409 | These vectors are implemented as a pointer to an embeddable vector. |

1410 | The semantics allow for this pointer to be NULL to represent empty |

1411 | vectors. This way, empty vectors occupy minimal space in the |

1412 | structure containing them. |

1413 | |

1414 | Properties: |

1415 | |

1416 | - The whole vector and control data are allocated in a single |

1417 | contiguous block. |

1418 | - The whole vector may be re-allocated. |

1419 | - Vector data may grow and shrink. |

1420 | - Access and manipulation requires a pointer test and |

1421 | indirection. |

1422 | - It requires 1 word of storage (prior to vector allocation). |

1423 | |

1424 | |

1425 | Limitations: |

1426 | |

1427 | These vectors must be PODs because they are stored in unions. |

1428 | (http://en.wikipedia.org/wiki/Plain_old_data_structures). |

1429 | As long as we use C++03, we cannot have constructors nor |

1430 | destructors in classes that are stored in unions. */ |

1431 | |

1432 | template<typename T, size_t N = 0> |

1433 | class auto_vec; |

1434 | |

1435 | template<typename T> |

1436 | struct vec<T, va_heap, vl_ptr> |

1437 | { |

1438 | public: |

1439 | /* Default ctors to ensure triviality. Use value-initialization |

1440 | (e.g., vec() or vec v{ };) or vNULL to create a zero-initialized |

1441 | instance. */ |

1442 | vec () = default; |

1443 | vec (const vec &) = default; |

1444 | /* Initialization from the generic vNULL. */ |

1445 | vec (vnull): m_vec () { } |

1446 | /* Same as default ctor: vec storage must be released manually. */ |

1447 | ~vec () = default; |

1448 | |

1449 | /* Defaulted same as copy ctor. */ |

1450 | vec& operator= (const vec &) = default; |

1451 | |

1452 | /* Prevent implicit conversion from auto_vec. Use auto_vec::to_vec() |

1453 | instead. */ |

1454 | template <size_t N> |

1455 | vec (auto_vec<T, N> &) = delete; |

1456 | |

1457 | template <size_t N> |

1458 | void operator= (auto_vec<T, N> &) = delete; |

1459 | |

1460 | /* Memory allocation and deallocation for the embedded vector. |

1461 | Needed because we cannot have proper ctors/dtors defined. */ |

1462 | void create (unsigned nelems CXX_MEM_STAT_INFO); |

1463 | void release (void); |

1464 | |

1465 | /* Vector operations. */ |

1466 | bool exists (void) const |

1467 | { return m_vec != NULL; } |

1468 | |

1469 | bool is_empty (void) const |

1470 | { return m_vec ? m_vec->is_empty () : true; } |

1471 | |

1472 | unsigned length (void) const |

1473 | { return m_vec ? m_vec->length () : 0; } |

1474 | |

1475 | T *address (void) |

1476 | { return m_vec ? m_vec->m_vecdata : NULL; } |

1477 | |

1478 | const T *address (void) const |

1479 | { return m_vec ? m_vec->m_vecdata : NULL; } |

1480 | |

1481 | T *begin () { return address (); } |

1482 | const T *begin () const { return address (); } |

1483 | T *end () { return begin () + length (); } |

1484 | const T *end () const { return begin () + length (); } |

1485 | const T &operator[] (unsigned ix) const |

1486 | { return (*m_vec)[ix]; } |

1487 | |

1488 | bool operator!=(const vec &other) const |

1489 | { return !(*this == other); } |

1490 | |

1491 | bool operator==(const vec &other) const |

1492 | { return address () == other.address (); } |

1493 | |

1494 | T &operator[] (unsigned ix) |

1495 | { return (*m_vec)[ix]; } |

1496 | |

1497 | T &last (void) |

1498 | { return m_vec->last (); } |

1499 | |

1500 | bool space (int nelems) const |

1501 | { return m_vec ? m_vec->space (nelems) : nelems == 0; } |

1502 | |

1503 | bool iterate (unsigned ix, T *p) const; |

1504 | bool iterate (unsigned ix, T **p) const; |

1505 | vec copy (ALONE_CXX_MEM_STAT_INFO) const; |

1506 | bool reserve (unsigned, bool = false CXX_MEM_STAT_INFO); |

1507 | bool reserve_exact (unsigned CXX_MEM_STAT_INFO); |

1508 | void splice (const vec &); |

1509 | void safe_splice (const vec & CXX_MEM_STAT_INFO); |

1510 | T *quick_push (const T &); |

1511 | T *safe_push (const T &CXX_MEM_STAT_INFO); |

1512 | T &pop (void); |

1513 | void truncate (unsigned); |

1514 | void safe_grow (unsigned, bool = false CXX_MEM_STAT_INFO); |

1515 | void safe_grow_cleared (unsigned, bool = false CXX_MEM_STAT_INFO); |

1516 | void quick_grow (unsigned); |

1517 | void quick_grow_cleared (unsigned); |

1518 | void quick_insert (unsigned, const T &); |

1519 | void safe_insert (unsigned, const T & CXX_MEM_STAT_INFO); |

1520 | void ordered_remove (unsigned); |

1521 | void unordered_remove (unsigned); |

1522 | void block_remove (unsigned, unsigned); |

1523 | void qsort (int (*) (const void *, const void *)); |

1524 | void sort (int (*) (const void *, const void *, void *), void *); |

1525 | void stablesort (int (*) (const void *, const void *, void *), void *); |

1526 | T *bsearch (const void *key, int (*compar)(const void *, const void *)); |

1527 | T *bsearch (const void *key, |

1528 | int (*compar)(const void *, const void *, void *), void *); |

1529 | unsigned lower_bound (T, bool (*)(const T &, const T &)) const; |

1530 | bool contains (const T &search) const; |

1531 | void reverse (void); |

1532 | |

1533 | bool using_auto_storage () const; |

1534 | |

1535 | /* FIXME - This field should be private, but we need to cater to |

1536 | compilers that have stricter notions of PODness for types. */ |

1537 | vec<T, va_heap, vl_embed> *m_vec; |

1538 | }; |

1539 | |

1540 | |

1541 | /* auto_vec is a subclass of vec that automatically manages creating and |

1542 | releasing the internal vector. If N is non zero then it has N elements of |

1543 | internal storage. The default is no internal storage, and you probably only |

1544 | want to ask for internal storage for vectors on the stack because if the |

1545 | size of the vector is larger than the internal storage that space is wasted. |

1546 | */ |

1547 | template<typename T, size_t N /* = 0 */> |

1548 | class auto_vec : public vec<T, va_heap> |

1549 | { |

1550 | public: |

1551 | auto_vec () |

1552 | { |

1553 | m_auto.embedded_init (MAX (N, 2), 0, 1); |

1554 | this->m_vec = &m_auto; |

1555 | } |

1556 | |

1557 | auto_vec (size_t s CXX_MEM_STAT_INFO) |

1558 | { |

1559 | if (s > N) |

1560 | { |

1561 | this->create (s PASS_MEM_STAT); |

1562 | return; |

1563 | } |

1564 | |

1565 | m_auto.embedded_init (MAX (N, 2), 0, 1); |

1566 | this->m_vec = &m_auto; |

1567 | } |

1568 | |

1569 | ~auto_vec () |

1570 | { |

1571 | this->release (); |

1572 | } |

1573 | |

1574 | /* Explicitly convert to the base class. There is no conversion |

1575 | from a const auto_vec because a copy of the returned vec can |

1576 | be used to modify *THIS. |

1577 | This is a legacy function not to be used in new code. */ |

1578 | vec<T, va_heap> to_vec_legacy () { |

1579 | return *static_cast<vec<T, va_heap> *>(this); |

1580 | } |

1581 | |

1582 | private: |

1583 | vec<T, va_heap, vl_embed> m_auto; |

1584 | T m_data[MAX (N - 1, 1)]; |

1585 | }; |

1586 | |

1587 | /* auto_vec is a sub class of vec whose storage is released when it is |

1588 | destroyed. */ |

1589 | template<typename T> |

1590 | class auto_vec<T, 0> : public vec<T, va_heap> |

1591 | { |

1592 | public: |

1593 | auto_vec () { this->m_vec = NULL; } |

1594 | auto_vec (size_t n CXX_MEM_STAT_INFO) { this->create (n PASS_MEM_STAT); } |

1595 | ~auto_vec () { this->release (); } |

1596 | |

1597 | auto_vec (vec<T, va_heap>&& r) |

1598 | { |

1599 | gcc_assert (!r.using_auto_storage ()); |

1600 | this->m_vec = r.m_vec; |

1601 | r.m_vec = NULL; |

1602 | } |

1603 | |

1604 | auto_vec (auto_vec<T> &&r) |

1605 | { |

1606 | gcc_assert (!r.using_auto_storage ()); |

1607 | this->m_vec = r.m_vec; |

1608 | r.m_vec = NULL; |

1609 | } |

1610 | |

1611 | auto_vec& operator= (vec<T, va_heap>&& r) |

1612 | { |

1613 | if (this == &r) |

1614 | return *this; |

1615 | |

1616 | gcc_assert (!r.using_auto_storage ()); |

1617 | this->release (); |

1618 | this->m_vec = r.m_vec; |

1619 | r.m_vec = NULL; |

1620 | return *this; |

1621 | } |

1622 | |

1623 | auto_vec& operator= (auto_vec<T> &&r) |

1624 | { |

1625 | if (this == &r) |

1626 | return *this; |

1627 | |

1628 | gcc_assert (!r.using_auto_storage ()); |

1629 | this->release (); |

1630 | this->m_vec = r.m_vec; |

1631 | r.m_vec = NULL; |

1632 | return *this; |

1633 | } |

1634 | |

1635 | /* Explicitly convert to the base class. There is no conversion |

1636 | from a const auto_vec because a copy of the returned vec can |

1637 | be used to modify *THIS. |

1638 | This is a legacy function not to be used in new code. */ |

1639 | vec<T, va_heap> to_vec_legacy () { |

1640 | return *static_cast<vec<T, va_heap> *>(this); |

1641 | } |

1642 | |

1643 | // You probably don't want to copy a vector, so these are deleted to prevent |

1644 | // unintentional use. If you really need a copy of the vectors contents you |

1645 | // can use copy (). |

1646 | auto_vec(const auto_vec &) = delete; |

1647 | auto_vec &operator= (const auto_vec &) = delete; |

1648 | }; |

1649 | |

1650 | |

1651 | /* Allocate heap memory for pointer V and create the internal vector |

1652 | with space for NELEMS elements. If NELEMS is 0, the internal |

1653 | vector is initialized to empty. */ |

1654 | |

1655 | template<typename T> |

1656 | inline void |

1657 | vec_alloc (vec<T> *&v, unsigned nelems CXX_MEM_STAT_INFO) |

1658 | { |

1659 | v = new vec<T>; |

1660 | v->create (nelems PASS_MEM_STAT); |

1661 | } |

1662 | |

1663 | |

1664 | /* A subclass of auto_vec <char *> that frees all of its elements on |

1665 | deletion. */ |

1666 | |

1667 | class auto_string_vec : public auto_vec <char *> |

1668 | { |

1669 | public: |

1670 | ~auto_string_vec (); |

1671 | }; |

1672 | |

1673 | /* A subclass of auto_vec <T *> that deletes all of its elements on |

1674 | destruction. |

1675 | |

1676 | This is a crude way for a vec to "own" the objects it points to |

1677 | and clean up automatically. |

1678 | |

1679 | For example, no attempt is made to delete elements when an item |

1680 | within the vec is overwritten. |

1681 | |

1682 | We can't rely on gnu::unique_ptr within a container, |

1683 | since we can't rely on move semantics in C++98. */ |

1684 | |

1685 | template <typename T> |

1686 | class auto_delete_vec : public auto_vec <T *> |

1687 | { |

1688 | public: |

1689 | auto_delete_vec () {} |

1690 | auto_delete_vec (size_t s) : auto_vec <T *> (s) {} |

1691 | |

1692 | ~auto_delete_vec (); |

1693 | |

1694 | private: |

1695 | DISABLE_COPY_AND_ASSIGN(auto_delete_vec); |

1696 | }; |

1697 | |

1698 | /* Conditionally allocate heap memory for VEC and its internal vector. */ |

1699 | |

1700 | template<typename T> |

1701 | inline void |

1702 | vec_check_alloc (vec<T, va_heap> *&vec, unsigned nelems CXX_MEM_STAT_INFO) |

1703 | { |

1704 | if (!vec) |

1705 | vec_alloc (vec, nelems PASS_MEM_STAT); |

1706 | } |

1707 | |

1708 | |

1709 | /* Free the heap memory allocated by vector V and set it to NULL. */ |

1710 | |

1711 | template<typename T> |

1712 | inline void |

1713 | vec_free (vec<T> *&v) |

1714 | { |

1715 | if (v == NULL) |

1716 | return; |

1717 | |

1718 | v->release (); |

1719 | delete v; |

1720 | v = NULL; |

1721 | } |

1722 | |

1723 | |

1724 | /* Return iteration condition and update PTR to point to the IX'th |

1725 | element of this vector. Use this to iterate over the elements of a |

1726 | vector as follows, |

1727 | |

1728 | for (ix = 0; v.iterate (ix, &ptr); ix++) |

1729 | continue; */ |

1730 | |

1731 | template<typename T> |

1732 | inline bool |

1733 | vec<T, va_heap, vl_ptr>::iterate (unsigned ix, T *ptr) const |

1734 | { |

1735 | if (m_vec) |

1736 | return m_vec->iterate (ix, ptr); |

1737 | else |

1738 | { |

1739 | *ptr = 0; |

1740 | return false; |

1741 | } |

1742 | } |

1743 | |

1744 | |

1745 | /* Return iteration condition and update *PTR to point to the |

1746 | IX'th element of this vector. Use this to iterate over the |

1747 | elements of a vector as follows, |

1748 | |

1749 | for (ix = 0; v->iterate (ix, &ptr); ix++) |

1750 | continue; |

1751 | |

1752 | This variant is for vectors of objects. */ |

1753 | |

1754 | template<typename T> |

1755 | inline bool |

1756 | vec<T, va_heap, vl_ptr>::iterate (unsigned ix, T **ptr) const |

1757 | { |

1758 | if (m_vec) |

1759 | return m_vec->iterate (ix, ptr); |

1760 | else |

1761 | { |

1762 | *ptr = 0; |

1763 | return false; |

1764 | } |

1765 | } |

1766 | |

1767 | |

1768 | /* Convenience macro for forward iteration. */ |

1769 | #define FOR_EACH_VEC_ELT(V, I, P) \ |

1770 | for (I = 0; (V).iterate ((I), &(P)); ++(I)) |

1771 | |

1772 | #define FOR_EACH_VEC_SAFE_ELT(V, I, P) \ |

1773 | for (I = 0; vec_safe_iterate ((V), (I), &(P)); ++(I)) |

1774 | |

1775 | /* Likewise, but start from FROM rather than 0. */ |

1776 | #define FOR_EACH_VEC_ELT_FROM(V, I, P, FROM) \ |

1777 | for (I = (FROM); (V).iterate ((I), &(P)); ++(I)) |

1778 | |

1779 | /* Convenience macro for reverse iteration. */ |

1780 | #define FOR_EACH_VEC_ELT_REVERSE(V, I, P) \ |

1781 | for (I = (V).length () - 1; \ |

1782 | (V).iterate ((I), &(P)); \ |

1783 | (I)--) |

1784 | |

1785 | #define FOR_EACH_VEC_SAFE_ELT_REVERSE(V, I, P) \ |

1786 | for (I = vec_safe_length (V) - 1; \ |

1787 | vec_safe_iterate ((V), (I), &(P)); \ |

1788 | (I)--) |

1789 | |

1790 | /* auto_string_vec's dtor, freeing all contained strings, automatically |

1791 | chaining up to ~auto_vec <char *>, which frees the internal buffer. */ |

1792 | |

1793 | inline |

1794 | auto_string_vec::~auto_string_vec () |

1795 | { |

1796 | int i; |

1797 | char *str; |

1798 | FOR_EACH_VEC_ELT (*this, i, str) |

1799 | free (str); |

1800 | } |

1801 | |

1802 | /* auto_delete_vec's dtor, deleting all contained items, automatically |

1803 | chaining up to ~auto_vec <T*>, which frees the internal buffer. */ |

1804 | |

1805 | template <typename T> |

1806 | inline |

1807 | auto_delete_vec<T>::~auto_delete_vec () |

1808 | { |

1809 | int i; |

1810 | T *item; |

1811 | FOR_EACH_VEC_ELT (*this, i, item) |

1812 | delete item; |

1813 | } |

1814 | |

1815 | |

1816 | /* Return a copy of this vector. */ |

1817 | |

1818 | template<typename T> |

1819 | inline vec<T, va_heap, vl_ptr> |

1820 | vec<T, va_heap, vl_ptr>::copy (ALONE_MEM_STAT_DECL) const |

1821 | { |

1822 | vec<T, va_heap, vl_ptr> new_vec{ }; |

1823 | if (length ()) |

1824 | new_vec.m_vec = m_vec->copy (ALONE_PASS_MEM_STAT); |

1825 | return new_vec; |

1826 | } |

1827 | |

1828 | |

1829 | /* Ensure that the vector has at least RESERVE slots available (if |

1830 | EXACT is false), or exactly RESERVE slots available (if EXACT is |

1831 | true). |

1832 | |

1833 | This may create additional headroom if EXACT is false. |

1834 | |

1835 | Note that this can cause the embedded vector to be reallocated. |

1836 | Returns true iff reallocation actually occurred. */ |

1837 | |

1838 | template<typename T> |

1839 | inline bool |

1840 | vec<T, va_heap, vl_ptr>::reserve (unsigned nelems, bool exact MEM_STAT_DECL) |

1841 | { |

1842 | if (space (nelems)) |

1843 | return false; |

1844 | |

1845 | /* For now play a game with va_heap::reserve to hide our auto storage if any, |

1846 | this is necessary because it doesn't have enough information to know the |

1847 | embedded vector is in auto storage, and so should not be freed. */ |

1848 | vec<T, va_heap, vl_embed> *oldvec = m_vec; |

1849 | unsigned int oldsize = 0; |

1850 | bool handle_auto_vec = m_vec && using_auto_storage (); |

1851 | if (handle_auto_vec) |

1852 | { |

1853 | m_vec = NULL; |

1854 | oldsize = oldvec->length (); |

1855 | nelems += oldsize; |

1856 | } |

1857 | |

1858 | va_heap::reserve (m_vec, nelems, exact PASS_MEM_STAT); |

1859 | if (handle_auto_vec) |

1860 | { |

1861 | vec_copy_construct (m_vec->address (), oldvec->address (), oldsize); |

1862 | m_vec->m_vecpfx.m_num = oldsize; |

1863 | } |

1864 | |

1865 | return true; |

1866 | } |

1867 | |

1868 | |

1869 | /* Ensure that this vector has exactly NELEMS slots available. This |

1870 | will not create additional headroom. Note this can cause the |

1871 | embedded vector to be reallocated. Returns true iff reallocation |

1872 | actually occurred. */ |

1873 | |

1874 | template<typename T> |

1875 | inline bool |

1876 | vec<T, va_heap, vl_ptr>::reserve_exact (unsigned nelems MEM_STAT_DECL) |

1877 | { |

1878 | return reserve (nelems, true PASS_MEM_STAT); |

1879 | } |

1880 | |

1881 | |

1882 | /* Create the internal vector and reserve NELEMS for it. This is |

1883 | exactly like vec::reserve, but the internal vector is |

1884 | unconditionally allocated from scratch. The old one, if it |

1885 | existed, is lost. */ |

1886 | |

1887 | template<typename T> |

1888 | inline void |

1889 | vec<T, va_heap, vl_ptr>::create (unsigned nelems MEM_STAT_DECL) |

1890 | { |

1891 | m_vec = NULL; |

1892 | if (nelems > 0) |

1893 | reserve_exact (nelems PASS_MEM_STAT); |

1894 | } |

1895 | |

1896 | |

1897 | /* Free the memory occupied by the embedded vector. */ |

1898 | |

1899 | template<typename T> |

1900 | inline void |

1901 | vec<T, va_heap, vl_ptr>::release (void) |

1902 | { |

1903 | if (!m_vec) |

1904 | return; |

1905 | |

1906 | if (using_auto_storage ()) |

1907 | { |

1908 | m_vec->m_vecpfx.m_num = 0; |

1909 | return; |

1910 | } |

1911 | |

1912 | va_heap::release (m_vec); |

1913 | } |

1914 | |

1915 | /* Copy the elements from SRC to the end of this vector as if by memcpy. |

1916 | SRC and this vector must be allocated with the same memory |

1917 | allocation mechanism. This vector is assumed to have sufficient |

1918 | headroom available. */ |

1919 | |

1920 | template<typename T> |

1921 | inline void |

1922 | vec<T, va_heap, vl_ptr>::splice (const vec<T, va_heap, vl_ptr> &src) |

1923 | { |

1924 | if (src.length ()) |

1925 | m_vec->splice (*(src.m_vec)); |

1926 | } |

1927 | |

1928 | |

1929 | /* Copy the elements in SRC to the end of this vector as if by memcpy. |

1930 | SRC and this vector must be allocated with the same mechanism. |

1931 | If there is not enough headroom in this vector, it will be reallocated |

1932 | as needed. */ |

1933 | |

1934 | template<typename T> |

1935 | inline void |

1936 | vec<T, va_heap, vl_ptr>::safe_splice (const vec<T, va_heap, vl_ptr> &src |

1937 | MEM_STAT_DECL) |

1938 | { |

1939 | if (src.length ()) |

1940 | { |

1941 | reserve_exact (src.length ()); |

1942 | splice (src); |

1943 | } |

1944 | } |

1945 | |

1946 | |

1947 | /* Push OBJ (a new element) onto the end of the vector. There must be |

1948 | sufficient space in the vector. Return a pointer to the slot |

1949 | where OBJ was inserted. */ |

1950 | |

1951 | template<typename T> |

1952 | inline T * |

1953 | vec<T, va_heap, vl_ptr>::quick_push (const T &obj) |

1954 | { |

1955 | return m_vec->quick_push (obj); |

1956 | } |

1957 | |

1958 | |

1959 | /* Push a new element OBJ onto the end of this vector. Reallocates |

1960 | the embedded vector, if needed. Return a pointer to the slot where |

1961 | OBJ was inserted. */ |

1962 | |

1963 | template<typename T> |

1964 | inline T * |

1965 | vec<T, va_heap, vl_ptr>::safe_push (const T &obj MEM_STAT_DECL) |

1966 | { |

1967 | reserve (1, false PASS_MEM_STAT); |

1968 | return quick_push (obj); |

1969 | } |

1970 | |

1971 | |

1972 | /* Pop and return the last element off the end of the vector. */ |

1973 | |

1974 | template<typename T> |

1975 | inline T & |

1976 | vec<T, va_heap, vl_ptr>::pop (void) |

1977 | { |

1978 | return m_vec->pop (); |

1979 | } |

1980 | |

1981 | |

1982 | /* Set the length of the vector to LEN. The new length must be less |

1983 | than or equal to the current length. This is an O(1) operation. */ |

1984 | |

1985 | template<typename T> |

1986 | inline void |

1987 | vec<T, va_heap, vl_ptr>::truncate (unsigned size) |

1988 | { |

1989 | if (m_vec) |

1990 | m_vec->truncate (size); |

1991 | else |

1992 | gcc_checking_assert (size == 0); |

1993 | } |

1994 | |

1995 | |

1996 | /* Grow the vector to a specific length. LEN must be as long or |

1997 | longer than the current length. The new elements are |

1998 | uninitialized. Reallocate the internal vector, if needed. */ |

1999 | |

2000 | template<typename T> |

2001 | inline void |

2002 | vec<T, va_heap, vl_ptr>::safe_grow (unsigned len, bool exact MEM_STAT_DECL) |

2003 | { |

2004 | unsigned oldlen = length (); |

2005 | gcc_checking_assert (oldlen <= len); |

2006 | reserve (len - oldlen, exact PASS_MEM_STAT); |

2007 | if (m_vec) |

2008 | m_vec->quick_grow (len); |

2009 | else |

2010 | gcc_checking_assert (len == 0); |

2011 | } |

2012 | |

2013 | |

2014 | /* Grow the embedded vector to a specific length. LEN must be as |

2015 | long or longer than the current length. The new elements are |

2016 | initialized to zero. Reallocate the internal vector, if needed. */ |

2017 | |

2018 | template<typename T> |

2019 | inline void |

2020 | vec<T, va_heap, vl_ptr>::safe_grow_cleared (unsigned len, bool exact |

2021 | MEM_STAT_DECL) |

2022 | { |

2023 | unsigned oldlen = length (); |

2024 | size_t growby = len - oldlen; |

2025 | safe_grow (len, exact PASS_MEM_STAT); |

2026 | if (growby != 0) |

2027 | vec_default_construct (address () + oldlen, growby); |

2028 | } |

2029 | |

2030 | |

2031 | /* Same as vec::safe_grow but without reallocation of the internal vector. |

2032 | If the vector cannot be extended, a runtime assertion will be triggered. */ |

2033 | |

2034 | template<typename T> |

2035 | inline void |

2036 | vec<T, va_heap, vl_ptr>::quick_grow (unsigned len) |

2037 | { |

2038 | gcc_checking_assert (m_vec); |

2039 | m_vec->quick_grow (len); |

2040 | } |

2041 | |

2042 | |

2043 | /* Same as vec::quick_grow_cleared but without reallocation of the |

2044 | internal vector. If the vector cannot be extended, a runtime |

2045 | assertion will be triggered. */ |

2046 | |

2047 | template<typename T> |

2048 | inline void |

2049 | vec<T, va_heap, vl_ptr>::quick_grow_cleared (unsigned len) |

2050 | { |

2051 | gcc_checking_assert (m_vec); |

2052 | m_vec->quick_grow_cleared (len); |

2053 | } |

2054 | |

2055 | |

2056 | /* Insert an element, OBJ, at the IXth position of this vector. There |

2057 | must be sufficient space. */ |

2058 | |

2059 | template<typename T> |

2060 | inline void |

2061 | vec<T, va_heap, vl_ptr>::quick_insert (unsigned ix, const T &obj) |

2062 | { |

2063 | m_vec->quick_insert (ix, obj); |

2064 | } |

2065 | |

2066 | |

2067 | /* Insert an element, OBJ, at the IXth position of the vector. |

2068 | Reallocate the embedded vector, if necessary. */ |

2069 | |

2070 | template<typename T> |

2071 | inline void |

2072 | vec<T, va_heap, vl_ptr>::safe_insert (unsigned ix, const T &obj MEM_STAT_DECL) |

2073 | { |

2074 | reserve (1, false PASS_MEM_STAT); |

2075 | quick_insert (ix, obj); |

2076 | } |

2077 | |

2078 | |

2079 | /* Remove an element from the IXth position of this vector. Ordering of |

2080 | remaining elements is preserved. This is an O(N) operation due to |

2081 | a memmove. */ |

2082 | |

2083 | template<typename T> |

2084 | inline void |

2085 | vec<T, va_heap, vl_ptr>::ordered_remove (unsigned ix) |

2086 | { |

2087 | m_vec->ordered_remove (ix); |

2088 | } |

2089 | |

2090 | |

2091 | /* Remove an element from the IXth position of this vector. Ordering |

2092 | of remaining elements is destroyed. This is an O(1) operation. */ |

2093 | |

2094 | template<typename T> |

2095 | inline void |

2096 | vec<T, va_heap, vl_ptr>::unordered_remove (unsigned ix) |

2097 | { |

2098 | m_vec->unordered_remove (ix); |

2099 | } |

2100 | |

2101 | |

2102 | /* Remove LEN elements starting at the IXth. Ordering is retained. |

2103 | This is an O(N) operation due to memmove. */ |

2104 | |

2105 | template<typename T> |

2106 | inline void |

2107 | vec<T, va_heap, vl_ptr>::block_remove (unsigned ix, unsigned len) |

2108 | { |

2109 | m_vec->block_remove (ix, len); |

2110 | } |

2111 | |

2112 | |

2113 | /* Sort the contents of this vector with qsort. CMP is the comparison |

2114 | function to pass to qsort. */ |

2115 | |

2116 | template<typename T> |

2117 | inline void |

2118 | vec<T, va_heap, vl_ptr>::qsort (int (*cmp) (const void *, const void *)) |

2119 | { |

2120 | if (m_vec) |

2121 | m_vec->qsort (cmp); |

2122 | } |

2123 | |

2124 | /* Sort the contents of this vector with qsort. CMP is the comparison |

2125 | function to pass to qsort. */ |

2126 | |

2127 | template<typename T> |

2128 | inline void |

2129 | vec<T, va_heap, vl_ptr>::sort (int (*cmp) (const void *, const void *, |

2130 | void *), void *data) |

2131 | { |

2132 | if (m_vec) |

2133 | m_vec->sort (cmp, data); |

2134 | } |

2135 | |

2136 | /* Sort the contents of this vector with gcc_stablesort_r. CMP is the |

2137 | comparison function to pass to qsort. */ |

2138 | |

2139 | template<typename T> |

2140 | inline void |

2141 | vec<T, va_heap, vl_ptr>::stablesort (int (*cmp) (const void *, const void *, |

2142 | void *), void *data) |

2143 | { |

2144 | if (m_vec) |

2145 | m_vec->stablesort (cmp, data); |

2146 | } |

2147 | |

2148 | /* Search the contents of the sorted vector with a binary search. |

2149 | CMP is the comparison function to pass to bsearch. */ |

2150 | |

2151 | template<typename T> |

2152 | inline T * |

2153 | vec<T, va_heap, vl_ptr>::bsearch (const void *key, |

2154 | int (*cmp) (const void *, const void *)) |

2155 | { |

2156 | if (m_vec) |

2157 | return m_vec->bsearch (key, cmp); |

2158 | return NULL; |

2159 | } |

2160 | |

2161 | /* Search the contents of the sorted vector with a binary search. |

2162 | CMP is the comparison function to pass to bsearch. */ |

2163 | |

2164 | template<typename T> |

2165 | inline T * |

2166 | vec<T, va_heap, vl_ptr>::bsearch (const void *key, |

2167 | int (*cmp) (const void *, const void *, |

2168 | void *), void *data) |

2169 | { |

2170 | if (m_vec) |

2171 | return m_vec->bsearch (key, cmp, data); |

2172 | return NULL; |

2173 | } |

2174 | |

2175 | |

2176 | /* Find and return the first position in which OBJ could be inserted |

2177 | without changing the ordering of this vector. LESSTHAN is a |

2178 | function that returns true if the first argument is strictly less |

2179 | than the second. */ |

2180 | |

2181 | template<typename T> |

2182 | inline unsigned |

2183 | vec<T, va_heap, vl_ptr>::lower_bound (T obj, |

2184 | bool (*lessthan)(const T &, const T &)) |

2185 | const |

2186 | { |

2187 | return m_vec ? m_vec->lower_bound (obj, lessthan) : 0; |

2188 | } |

2189 | |

2190 | /* Return true if SEARCH is an element of V. Note that this is O(N) in the |

2191 | size of the vector and so should be used with care. */ |

2192 | |

2193 | template<typename T> |

2194 | inline bool |

2195 | vec<T, va_heap, vl_ptr>::contains (const T &search) const |

2196 | { |

2197 | return m_vec ? m_vec->contains (search) : false; |

2198 | } |

2199 | |

2200 | /* Reverse content of the vector. */ |

2201 | |

2202 | template<typename T> |

2203 | inline void |

2204 | vec<T, va_heap, vl_ptr>::reverse (void) |

2205 | { |

2206 | unsigned l = length (); |

2207 | T *ptr = address (); |

2208 | |

2209 | for (unsigned i = 0; i < l / 2; i++) |

2210 | std::swap (ptr[i], ptr[l - i - 1]); |

2211 | } |

2212 | |

2213 | template<typename T> |

2214 | inline bool |

2215 | vec<T, va_heap, vl_ptr>::using_auto_storage () const |

2216 | { |

2217 | return m_vec ? m_vec->m_vecpfx.m_using_auto_storage : false; |

2218 | } |

2219 | |

2220 | /* Release VEC and call release of all element vectors. */ |

2221 | |

2222 | template<typename T> |

2223 | inline void |

2224 | release_vec_vec (vec<vec<T> > &vec) |

2225 | { |

2226 | for (unsigned i = 0; i < vec.length (); i++) |

2227 | vec[i].release (); |

2228 | |

2229 | vec.release (); |

2230 | } |

2231 | |

2232 | // Provide a subset of the std::span functionality. (We can't use std::span |

2233 | // itself because it's a C++20 feature.) |

2234 | // |

2235 | // In addition, provide an invalid value that is distinct from all valid |

2236 | // sequences (including the empty sequence). This can be used to return |

2237 | // failure without having to use std::optional. |

2238 | // |

2239 | // There is no operator bool because it would be ambiguous whether it is |

2240 | // testing for a valid value or an empty sequence. |

2241 | template<typename T> |

2242 | class array_slice |

2243 | { |

2244 | template<typename OtherT> friend class array_slice; |

2245 | |

2246 | public: |

2247 | using value_type = T; |

2248 | using iterator = T *; |

2249 | using const_iterator = const T *; |

2250 | |

2251 | array_slice () : m_base (nullptr), m_size (0) {} |

2252 | |

2253 | template<typename OtherT> |

2254 | array_slice (array_slice<OtherT> other) |

2255 | : m_base (other.m_base), m_size (other.m_size) {} |

2256 | |

2257 | array_slice (iterator base, unsigned int size) |

2258 | : m_base (base), m_size (size) {} |

2259 | |

2260 | template<size_t N> |

2261 | array_slice (T (&array)[N]) : m_base (array), m_size (N) {} |

2262 | |

2263 | template<typename OtherT> |

2264 | array_slice (const vec<OtherT> &v) |

2265 | : m_base (v.address ()), m_size (v.length ()) {} |

2266 | |

2267 | iterator begin () { return m_base; } |

2268 | iterator end () { return m_base + m_size; } |

2269 | |

2270 | const_iterator begin () const { return m_base; } |

2271 | const_iterator end () const { return m_base + m_size; } |

2272 | |

2273 | value_type &front (); |

2274 | value_type &back (); |

2275 | value_type &operator[] (unsigned int i); |

2276 | |

2277 | const value_type &front () const; |

2278 | const value_type &back () const; |

2279 | const value_type &operator[] (unsigned int i) const; |

2280 | |

2281 | size_t size () const { return m_size; } |

2282 | size_t size_bytes () const { return m_size * sizeof (T); } |

2283 | bool empty () const { return m_size == 0; } |

2284 | |

2285 | // An invalid array_slice that represents a failed operation. This is |

2286 | // distinct from an empty slice, which is a valid result in some contexts. |

2287 | static array_slice invalid () { return { nullptr, ~0U }; } |

2288 | |

2289 | // True if the array is valid, false if it is an array like INVALID. |

2290 | bool is_valid () const { return m_base || m_size == 0; } |

2291 | |

2292 | private: |

2293 | iterator m_base; |

2294 | unsigned int m_size; |

2295 | }; |

2296 | |

2297 | template<typename T> |

2298 | inline typename array_slice<T>::value_type & |

2299 | array_slice<T>::front () |

2300 | { |

2301 | gcc_checking_assert (m_size); |

2302 | return m_base[0]; |

2303 | } |

2304 | |

2305 | template<typename T> |

2306 | inline const typename array_slice<T>::value_type & |

2307 | array_slice<T>::front () const |

2308 | { |

2309 | gcc_checking_assert (m_size); |

2310 | return m_base[0]; |

2311 | } |

2312 | |

2313 | template<typename T> |

2314 | inline typename array_slice<T>::value_type & |

2315 | array_slice<T>::back () |

2316 | { |

2317 | gcc_checking_assert (m_size); |

2318 | return m_base[m_size - 1]; |

2319 | } |

2320 | |

2321 | template<typename T> |

2322 | inline const typename array_slice<T>::value_type & |

2323 | array_slice<T>::back () const |

2324 | { |

2325 | gcc_checking_assert (m_size); |

2326 | return m_base[m_size - 1]; |

2327 | } |

2328 | |

2329 | template<typename T> |

2330 | inline typename array_slice<T>::value_type & |

2331 | array_slice<T>::operator[] (unsigned int i) |

2332 | { |

2333 | gcc_checking_assert (i < m_size); |

2334 | return m_base[i]; |

2335 | } |

2336 | |

2337 | template<typename T> |

2338 | inline const typename array_slice<T>::value_type & |

2339 | array_slice<T>::operator[] (unsigned int i) const |

2340 | { |

2341 | gcc_checking_assert (i < m_size); |

2342 | return m_base[i]; |

2343 | } |

2344 | |

2345 | template<typename T> |

2346 | array_slice<T> |

2347 | make_array_slice (T *base, unsigned int size) |

2348 | { |

2349 | return array_slice<T> (base, size); |

2350 | } |

2351 | |

2352 | #if (GCC_VERSION >= 3000) |

2353 | # pragma GCC poison m_vec m_vecpfx m_vecdata |

2354 | #endif |

2355 | |

2356 | #endif // GCC_VEC_H |

2357 |