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

2 | Copyright (C) 2004-2017 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.c. */ |

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

198 | void release_overhead (void *, size_t, bool CXX_MEM_STAT_INFO); |

199 | static unsigned calculate_allocation (vec_prefix *, unsigned, bool); |

200 | static unsigned calculate_allocation_1 (unsigned, unsigned); |

201 | |

202 | /* Note that vec_prefix should be a base class for vec, but we use |

203 | offsetof() on vector fields of tree structures (e.g., |

204 | tree_binfo::base_binfos), and offsetof only supports base types. |

205 | |

206 | To compensate, we make vec_prefix a field inside vec and make |

207 | vec a friend class of vec_prefix so it can access its fields. */ |

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

209 | |

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

211 | friend struct va_gc; |

212 | friend struct va_gc_atomic; |

213 | friend struct va_heap; |

214 | |

215 | unsigned m_alloc : 31; |

216 | unsigned m_using_auto_storage : 1; |

217 | unsigned m_num; |

218 | }; |

219 | |

220 | /* Calculate the number of slots to reserve a vector, making sure that |

221 | RESERVE slots are free. If EXACT grow exactly, otherwise grow |

222 | exponentially. PFX is the control data for the vector. */ |

223 | |

224 | inline unsigned |

225 | vec_prefix::calculate_allocation (vec_prefix *pfx, unsigned reserve, |

226 | bool exact) |

227 | { |

228 | if (exact) |

229 | return (pfx ? pfx->m_num : 0) + reserve; |

230 | else if (!pfx) |

231 | return MAX (4, reserve); |

232 | return calculate_allocation_1 (pfx->m_alloc, pfx->m_num + reserve); |

233 | } |

234 | |

235 | template<typename, typename, typename> struct vec; |

236 | |

237 | /* Valid vector layouts |

238 | |

239 | vl_embed - Embeddable vector that uses the trailing array idiom. |

240 | vl_ptr - Space efficient vector that uses a pointer to an |

241 | embeddable vector. */ |

242 | struct vl_embed { }; |

243 | struct vl_ptr { }; |

244 | |

245 | |

246 | /* Types of supported allocations |

247 | |

248 | va_heap - Allocation uses malloc/free. |

249 | va_gc - Allocation uses ggc_alloc. |

250 | va_gc_atomic - Same as GC, but individual elements of the array |

251 | do not need to be marked during collection. */ |

252 | |

253 | /* Allocator type for heap vectors. */ |

254 | struct va_heap |

255 | { |

256 | /* Heap vectors are frequently regular instances, so use the vl_ptr |

257 | layout for them. */ |

258 | typedef vl_ptr default_layout; |

259 | |

260 | template<typename T> |

261 | static void reserve (vec<T, va_heap, vl_embed> *&, unsigned, bool |

262 | CXX_MEM_STAT_INFO); |

263 | |

264 | template<typename T> |

265 | static void release (vec<T, va_heap, vl_embed> *&); |

266 | }; |

267 | |

268 | |

269 | /* Allocator for heap memory. Ensure there are at least RESERVE free |

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

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

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

273 | |

274 | template<typename T> |

275 | inline void |

276 | va_heap::reserve (vec<T, va_heap, vl_embed> *&v, unsigned reserve, bool exact |

277 | MEM_STAT_DECL) |

278 | { |

279 | unsigned alloc |

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

281 | gcc_checking_assert (alloc); |

282 | |

283 | if (GATHER_STATISTICS && v) |

284 | v->m_vecpfx.release_overhead (v, v->allocated (), false); |

285 | |

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

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

288 | v = static_cast <vec<T, va_heap, vl_embed> *> (xrealloc (v, size)); |

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

290 | |

291 | if (GATHER_STATISTICS) |

292 | v->m_vecpfx.register_overhead (v, alloc, nelem PASS_MEM_STAT); |

293 | } |

294 | |

295 | |

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

297 | |

298 | template<typename T> |

299 | void |

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

301 | { |

302 | if (v == NULL) |

303 | return; |

304 | |

305 | if (GATHER_STATISTICS) |

306 | v->m_vecpfx.release_overhead (v, v->allocated (), true); |

307 | ::free (v); |

308 | v = NULL; |

309 | } |

310 | |

311 | |

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

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

314 | |

315 | struct va_gc |

316 | { |

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

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

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

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

321 | typedef vl_embed default_layout; |

322 | |

323 | template<typename T, typename A> |

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

325 | CXX_MEM_STAT_INFO); |

326 | |

327 | template<typename T, typename A> |

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

329 | }; |

330 | |

331 | |

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

333 | |

334 | template<typename T, typename A> |

335 | inline void |

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

337 | { |

338 | if (v) |

339 | ::ggc_free (v); |

340 | v = NULL; |

341 | } |

342 | |

343 | |

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

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

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

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

348 | |

349 | template<typename T, typename A> |

350 | void |

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

352 | MEM_STAT_DECL) |

353 | { |

354 | unsigned alloc |

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

356 | if (!alloc) |

357 | { |

358 | ::ggc_free (v); |

359 | v = NULL; |

360 | return; |

361 | } |

362 | |

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

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

365 | |

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

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

368 | |

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

370 | size_t vec_offset = sizeof (vec_prefix); |

371 | size_t elt_size = sizeof (T); |

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

373 | |

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

375 | size = vec_offset + alloc * elt_size; |

376 | |

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

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

379 | PASS_MEM_STAT)); |

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

381 | } |

382 | |

383 | |

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

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

386 | completely inherited from va_gc. */ |

387 | struct va_gc_atomic : va_gc |

388 | { |

389 | }; |

390 | |

391 | |

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

393 | most commonly used strategies. |

394 | |

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

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

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

398 | themselves. |

399 | |

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

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

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

403 | template<typename T, |

404 | typename A = va_heap, |

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

406 | struct GTY((user)) vec |

407 | { |

408 | }; |

409 | |

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

411 | |

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

413 | the compiler like this: |

414 | |

415 | DEFINE_DEBUG_VEC (TYPE) |

416 | |

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

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

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

420 | |

421 | template<typename T> |

422 | void |

423 | debug_helper (vec<T> &ref) |

424 | { |

425 | unsigned i; |

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

427 | { |

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

429 | debug_slim (ref[i]); |

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

431 | } |

432 | } |

433 | |

434 | /* We need a separate va_gc variant here because default template |

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

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

437 | above debug_helper. */ |

438 | |

439 | template<typename T> |

440 | void |

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

442 | { |

443 | unsigned i; |

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

445 | { |

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

447 | debug_slim (ref[i]); |

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

449 | } |

450 | } |

451 | |

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

453 | functions for a type T. */ |

454 | |

455 | #define DEFINE_DEBUG_VEC(T) \ |

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

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

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

459 | DEBUG_FUNCTION void \ |

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

461 | { \ |

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

463 | } \ |

464 | DEBUG_FUNCTION void \ |

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

466 | { \ |

467 | if (ptr) \ |

468 | debug (*ptr); \ |

469 | else \ |

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

471 | } \ |

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

473 | DEBUG_FUNCTION void \ |

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

475 | { \ |

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

477 | } \ |

478 | DEBUG_FUNCTION void \ |

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

480 | { \ |

481 | if (ptr) \ |

482 | debug (*ptr); \ |

483 | else \ |

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

485 | } |

486 | |

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

488 | |

489 | template <typename T> |

490 | inline void |

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

492 | { |

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

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

495 | } |

496 | |

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

498 | |

499 | template <typename T> |

500 | inline void |

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

502 | { |

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

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

505 | } |

506 | |

507 | /* Type to provide NULL values for vec<T, A, L>. This is used to |

508 | provide nil initializers for vec instances. Since vec must be |

509 | a POD, we cannot have proper ctor/dtor for it. To initialize |

510 | a vec instance, you can assign it the value vNULL. This isn't |

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

512 | are zero-initialized by default. */ |

513 | struct vnull |

514 | { |

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

516 | CONSTEXPR operator vec<T, A, L> () { return vec<T, A, L>(); } |

517 | }; |

518 | extern vnull vNULL; |

519 | |

520 | |

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

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

523 | contiguous memory block. |

524 | |

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

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

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

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

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

530 | could be a vector type. |

531 | |

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

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

534 | allocation variants are not available). |

535 | |

536 | Properties: |

537 | |

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

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

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

541 | in the vector plus its control data. |

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

543 | - The vector cannot grow nor shrink. |

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

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

546 | |

547 | template<typename T, typename A> |

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

549 | { |

550 | public: |

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

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

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

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

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

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

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

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

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

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

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

562 | T &last (void); |

563 | bool space (unsigned) const; |

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

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

566 | vec *copy (ALONE_CXX_MEM_STAT_INFO) const; |

567 | void splice (const vec &); |

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

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

570 | T &pop (void); |

571 | void truncate (unsigned); |

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

573 | void ordered_remove (unsigned); |

574 | void unordered_remove (unsigned); |

575 | void block_remove (unsigned, unsigned); |

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

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

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

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

580 | static size_t embedded_size (unsigned); |

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

582 | void quick_grow (unsigned len); |

583 | void quick_grow_cleared (unsigned len); |

584 | |

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

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

587 | |

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

589 | friend struct va_gc; |

590 | friend struct va_gc_atomic; |

591 | friend struct va_heap; |

592 | |

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

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

595 | vec_prefix m_vecpfx; |

596 | T m_vecdata[1]; |

597 | }; |

598 | |

599 | |

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

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

602 | provided via free functions for these reasons: |

603 | |

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

605 | |

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

607 | the pointer will change its value. |

608 | |

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

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

611 | |

612 | |

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

614 | return true. */ |

615 | template<typename T, typename A> |

616 | inline bool |

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

618 | { |

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

620 | } |

621 | |

622 | |

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

624 | template<typename T, typename A> |

625 | inline unsigned |

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

627 | { |

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

629 | } |

630 | |

631 | |

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

633 | template<typename T, typename A> |

634 | inline T * |

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

636 | { |

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

638 | } |

639 | |

640 | |

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

642 | template<typename T, typename A> |

643 | inline bool |

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

645 | { |

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

647 | } |

648 | |

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

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

651 | template<typename T, typename A> |

652 | inline bool |

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

654 | CXX_MEM_STAT_INFO) |

655 | { |

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

657 | if (extend) |

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

659 | return extend; |

660 | } |

661 | |

662 | template<typename T, typename A> |

663 | inline bool |

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

665 | CXX_MEM_STAT_INFO) |

666 | { |

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

668 | } |

669 | |

670 | |

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

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

673 | |

674 | template<typename T, typename A> |

675 | inline void |

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

677 | { |

678 | v = NULL; |

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

680 | } |

681 | |

682 | |

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

684 | |

685 | template<typename T, typename A> |

686 | inline void |

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

688 | { |

689 | A::release (v); |

690 | } |

691 | |

692 | |

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

694 | template<typename T, typename A> |

695 | inline void |

696 | vec_safe_grow (vec<T, A, vl_embed> *&v, unsigned len CXX_MEM_STAT_INFO) |

697 | { |

698 | unsigned oldlen = vec_safe_length (v); |

699 | gcc_checking_assert (len >= oldlen); |

700 | vec_safe_reserve_exact (v, len - oldlen PASS_MEM_STAT); |

701 | v->quick_grow (len); |

702 | } |

703 | |

704 | |

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

706 | template<typename T, typename A> |

707 | inline void |

708 | vec_safe_grow_cleared (vec<T, A, vl_embed> *&v, unsigned len CXX_MEM_STAT_INFO) |

709 | { |

710 | unsigned oldlen = vec_safe_length (v); |

711 | vec_safe_grow (v, len PASS_MEM_STAT); |

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

713 | } |

714 | |

715 | |

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

717 | template<typename T, typename A> |

718 | inline bool |

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

720 | { |

721 | if (v) |

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

723 | else |

724 | { |

725 | *ptr = 0; |

726 | return false; |

727 | } |

728 | } |

729 | |

730 | template<typename T, typename A> |

731 | inline bool |

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

733 | { |

734 | if (v) |

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

736 | else |

737 | { |

738 | *ptr = 0; |

739 | return false; |

740 | } |

741 | } |

742 | |

743 | |

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

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

746 | template<typename T, typename A> |

747 | inline T * |

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

749 | { |

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

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

752 | } |

753 | |

754 | |

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

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

757 | template<typename T, typename A> |

758 | inline void |

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

760 | CXX_MEM_STAT_INFO) |

761 | { |

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

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

764 | } |

765 | |

766 | |

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

768 | template<typename T, typename A> |

769 | inline void |

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

771 | { |

772 | if (v) |

773 | v->truncate (size); |

774 | } |

775 | |

776 | |

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

778 | template<typename T, typename A> |

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

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

781 | { |

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

783 | } |

784 | |

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

786 | Reallocate DST, if necessary. */ |

787 | template<typename T, typename A> |

788 | inline void |

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

790 | CXX_MEM_STAT_INFO) |

791 | { |

792 | unsigned src_len = vec_safe_length (src); |

793 | if (src_len) |

794 | { |

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

796 | PASS_MEM_STAT); |

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

798 | } |

799 | } |

800 | |

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

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

803 | |

804 | template<typename T, typename A> |

805 | inline bool |

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

807 | { |

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

809 | } |

810 | |

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

812 | domain of the vector. */ |

813 | |

814 | template<typename T, typename A> |

815 | inline const T & |

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

817 | { |

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

819 | return m_vecdata[ix]; |

820 | } |

821 | |

822 | template<typename T, typename A> |

823 | inline T & |

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

825 | { |

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

827 | return m_vecdata[ix]; |

828 | } |

829 | |

830 | |

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

832 | |

833 | template<typename T, typename A> |

834 | inline T & |

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

836 | { |

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

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

839 | } |

840 | |

841 | |

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

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

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

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

846 | will. */ |

847 | |

848 | template<typename T, typename A> |

849 | inline bool |

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

851 | { |

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

853 | } |

854 | |

855 | |

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

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

858 | vector as follows, |

859 | |

860 | for (ix = 0; vec<T, A>::iterate (v, ix, &ptr); ix++) |

861 | continue; */ |

862 | |

863 | template<typename T, typename A> |

864 | inline bool |

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

866 | { |

867 | if (ix < m_vecpfx.m_num) |

868 | { |

869 | *ptr = m_vecdata[ix]; |

870 | return true; |

871 | } |

872 | else |

873 | { |

874 | *ptr = 0; |

875 | return false; |

876 | } |

877 | } |

878 | |

879 | |

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

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

882 | elements of a vector as follows, |

883 | |

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

885 | continue; |

886 | |

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

888 | |

889 | template<typename T, typename A> |

890 | inline bool |

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

892 | { |

893 | if (ix < m_vecpfx.m_num) |

894 | { |

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

896 | return true; |

897 | } |

898 | else |

899 | { |

900 | *ptr = 0; |

901 | return false; |

902 | } |

903 | } |

904 | |

905 | |

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

907 | |

908 | template<typename T, typename A> |

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

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

911 | { |

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

913 | unsigned len = length (); |

914 | if (len) |

915 | { |

916 | vec_alloc (new_vec, len PASS_MEM_STAT); |

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

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

919 | } |

920 | return new_vec; |

921 | } |

922 | |

923 | |

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

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

926 | |

927 | template<typename T, typename A> |

928 | inline void |

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

930 | { |

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

932 | if (len) |

933 | { |

934 | gcc_checking_assert (space (len)); |

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

936 | m_vecpfx.m_num += len; |

937 | } |

938 | } |

939 | |

940 | template<typename T, typename A> |

941 | inline void |

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

943 | { |

944 | if (src) |

945 | splice (*src); |

946 | } |

947 | |

948 | |

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

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

951 | where OBJ was inserted. */ |

952 | |

953 | template<typename T, typename A> |

954 | inline T * |

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

956 | { |

957 | gcc_checking_assert (space (1)); |

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

959 | *slot = obj; |

960 | return slot; |

961 | } |

962 | |

963 | |

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

965 | |

966 | template<typename T, typename A> |

967 | inline T & |

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

969 | { |

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

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

972 | } |

973 | |

974 | |

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

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

977 | |

978 | template<typename T, typename A> |

979 | inline void |

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

981 | { |

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

983 | m_vecpfx.m_num = size; |

984 | } |

985 | |

986 | |

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

988 | must be sufficient space. */ |

989 | |

990 | template<typename T, typename A> |

991 | inline void |

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

993 | { |

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

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

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

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

998 | *slot = obj; |

999 | } |

1000 | |

1001 | |

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

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

1004 | memmove. */ |

1005 | |

1006 | template<typename T, typename A> |

1007 | inline void |

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

1009 | { |

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

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

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

1013 | } |

1014 | |

1015 | |

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

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

1018 | |

1019 | template<typename T, typename A> |

1020 | inline void |

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

1022 | { |

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

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

1025 | } |

1026 | |

1027 | |

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

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

1030 | |

1031 | template<typename T, typename A> |

1032 | inline void |

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

1034 | { |

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

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

1037 | m_vecpfx.m_num -= len; |

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

1039 | } |

1040 | |

1041 | |

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

1043 | function to pass to qsort. */ |

1044 | |

1045 | template<typename T, typename A> |

1046 | inline void |

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

1048 | { |

1049 | if (length () > 1) |

1050 | ::qsort (address (), length (), sizeof (T), cmp); |

1051 | } |

1052 | |

1053 | |

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

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

1056 | |

1057 | template<typename T, typename A> |

1058 | inline T * |

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

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

1061 | { |

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

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

1064 | size_t size = sizeof (T); |

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

1066 | size_t l, u, idx; |

1067 | const void *p; |

1068 | int comparison; |

1069 | |

1070 | l = 0; |

1071 | u = nmemb; |

1072 | while (l < u) |

1073 | { |

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

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

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

1077 | if (comparison < 0) |

1078 | u = idx; |

1079 | else if (comparison > 0) |

1080 | l = idx + 1; |

1081 | else |

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

1083 | } |

1084 | |

1085 | return NULL; |

1086 | } |

1087 | |

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

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

1090 | |

1091 | template<typename T, typename A> |

1092 | inline bool |

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

1094 | { |

1095 | unsigned int len = length (); |

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

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

1098 | return true; |

1099 | |

1100 | return false; |

1101 | } |

1102 | |

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

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

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

1106 | than the second. */ |

1107 | |

1108 | template<typename T, typename A> |

1109 | unsigned |

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

1111 | const |

1112 | { |

1113 | unsigned int len = length (); |

1114 | unsigned int half, middle; |

1115 | unsigned int first = 0; |

1116 | while (len > 0) |

1117 | { |

1118 | half = len / 2; |

1119 | middle = first; |

1120 | middle += half; |

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

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

1123 | { |

1124 | first = middle; |

1125 | ++first; |

1126 | len = len - half - 1; |

1127 | } |

1128 | else |

1129 | len = half; |

1130 | } |

1131 | return first; |

1132 | } |

1133 | |

1134 | |

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

1136 | embeddable vec inside another data structure. |

1137 | |

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

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

1140 | final member): |

1141 | |

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

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

1144 | |

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

1146 | |

1147 | template<typename T, typename A> |

1148 | inline size_t |

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

1150 | { |

1151 | typedef vec<T, A, vl_embed> vec_embedded; |

1152 | return offsetof (vec_embedded, m_vecdata) + alloc * sizeof (T); |

1153 | } |

1154 | |

1155 | |

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

1157 | NUM active elements. */ |

1158 | |

1159 | template<typename T, typename A> |

1160 | inline void |

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

1162 | { |

1163 | m_vecpfx.m_alloc = alloc; |

1164 | m_vecpfx.m_using_auto_storage = aut; |

1165 | m_vecpfx.m_num = num; |

1166 | } |

1167 | |

1168 | |

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

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

1171 | |

1172 | template<typename T, typename A> |

1173 | inline void |

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

1175 | { |

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

1177 | m_vecpfx.m_num = len; |

1178 | } |

1179 | |

1180 | |

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

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

1183 | |

1184 | template<typename T, typename A> |

1185 | inline void |

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

1187 | { |

1188 | unsigned oldlen = length (); |

1189 | size_t growby = len - oldlen; |

1190 | quick_grow (len); |

1191 | if (growby != 0) |

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

1193 | } |

1194 | |

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

1196 | |

1197 | template<typename T> |

1198 | void |

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

1200 | { |

1201 | extern void gt_ggc_mx (T &); |

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

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

1204 | } |

1205 | |

1206 | template<typename T> |

1207 | void |

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

1209 | { |

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

1211 | be traversed. */ |

1212 | } |

1213 | |

1214 | |

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

1216 | |

1217 | template<typename T, typename A> |

1218 | void |

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

1220 | { |

1221 | extern void gt_pch_nx (T &); |

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

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

1224 | } |

1225 | |

1226 | template<typename T, typename A> |

1227 | void |

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

1229 | { |

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

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

1232 | } |

1233 | |

1234 | template<typename T, typename A> |

1235 | void |

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

1237 | { |

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

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

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

1241 | } |

1242 | |

1243 | |

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

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

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

1247 | only take a single word of storage. |

1248 | |

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

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

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

1252 | structure containing them. |

1253 | |

1254 | Properties: |

1255 | |

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

1257 | contiguous block. |

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

1259 | - Vector data may grow and shrink. |

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

1261 | indirection. |

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

1263 | |

1264 | |

1265 | Limitations: |

1266 | |

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

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

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

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

1271 | |

1272 | template<typename T> |

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

1274 | { |

1275 | public: |

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

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

1278 | void create (unsigned nelems CXX_MEM_STAT_INFO); |

1279 | void release (void); |

1280 | |

1281 | /* Vector operations. */ |

1282 | bool exists (void) const |

1283 | { return m_vec != NULL; } |

1284 | |

1285 | bool is_empty (void) const |

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

1287 | |

1288 | unsigned length (void) const |

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

1290 | |

1291 | T *address (void) |

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

1293 | |

1294 | const T *address (void) const |

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

1296 | |

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

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

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

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

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

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

1303 | |

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

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

1306 | |

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

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

1309 | |

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

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

1312 | |

1313 | T &last (void) |

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

1315 | |

1316 | bool space (int nelems) const |

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

1318 | |

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

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

1321 | vec copy (ALONE_CXX_MEM_STAT_INFO) const; |

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

1323 | bool reserve_exact (unsigned CXX_MEM_STAT_INFO); |

1324 | void splice (const vec &); |

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

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

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

1328 | T &pop (void); |

1329 | void truncate (unsigned); |

1330 | void safe_grow (unsigned CXX_MEM_STAT_INFO); |

1331 | void safe_grow_cleared (unsigned CXX_MEM_STAT_INFO); |

1332 | void quick_grow (unsigned); |

1333 | void quick_grow_cleared (unsigned); |

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

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

1336 | void ordered_remove (unsigned); |

1337 | void unordered_remove (unsigned); |

1338 | void block_remove (unsigned, unsigned); |

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

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

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

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

1343 | |

1344 | bool using_auto_storage () const; |

1345 | |

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

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

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

1349 | }; |

1350 | |

1351 | |

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

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

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

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

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

1357 | */ |

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

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

1360 | { |

1361 | public: |

1362 | auto_vec () |

1363 | { |

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

1365 | this->m_vec = &m_auto; |

1366 | } |

1367 | |

1368 | auto_vec (size_t s) |

1369 | { |

1370 | if (s > N) |

1371 | { |

1372 | this->create (s); |

1373 | return; |

1374 | } |

1375 | |

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

1377 | this->m_vec = &m_auto; |

1378 | } |

1379 | |

1380 | ~auto_vec () |

1381 | { |

1382 | this->release (); |

1383 | } |

1384 | |

1385 | private: |

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

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

1388 | }; |

1389 | |

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

1391 | destroyed. */ |

1392 | template<typename T> |

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

1394 | { |

1395 | public: |

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

1397 | auto_vec (size_t n) { this->create (n); } |

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

1399 | }; |

1400 | |

1401 | |

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

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

1404 | vector is initialized to empty. */ |

1405 | |

1406 | template<typename T> |

1407 | inline void |

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

1409 | { |

1410 | v = new vec<T>; |

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

1412 | } |

1413 | |

1414 | |

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

1416 | |

1417 | template<typename T> |

1418 | inline void |

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

1420 | { |

1421 | if (!vec) |

1422 | vec_alloc (vec, nelems PASS_MEM_STAT); |

1423 | } |

1424 | |

1425 | |

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

1427 | |

1428 | template<typename T> |

1429 | inline void |

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

1431 | { |

1432 | if (v == NULL) |

1433 | return; |

1434 | |

1435 | v->release (); |

1436 | delete v; |

1437 | v = NULL; |

1438 | } |

1439 | |

1440 | |

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

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

1443 | vector as follows, |

1444 | |

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

1446 | continue; */ |

1447 | |

1448 | template<typename T> |

1449 | inline bool |

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

1451 | { |

1452 | if (m_vec) |

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

1454 | else |

1455 | { |

1456 | *ptr = 0; |

1457 | return false; |

1458 | } |

1459 | } |

1460 | |

1461 | |

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

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

1464 | elements of a vector as follows, |

1465 | |

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

1467 | continue; |

1468 | |

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

1470 | |

1471 | template<typename T> |

1472 | inline bool |

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

1474 | { |

1475 | if (m_vec) |

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

1477 | else |

1478 | { |

1479 | *ptr = 0; |

1480 | return false; |

1481 | } |

1482 | } |

1483 | |

1484 | |

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

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

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

1488 | |

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

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

1491 | |

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

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

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

1495 | |

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

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

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

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

1500 | (I)--) |

1501 | |

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

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

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

1505 | (I)--) |

1506 | |

1507 | |

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

1509 | |

1510 | template<typename T> |

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

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

1513 | { |

1514 | vec<T, va_heap, vl_ptr> new_vec = vNULL; |

1515 | if (length ()) |

1516 | new_vec.m_vec = m_vec->copy (); |

1517 | return new_vec; |

1518 | } |

1519 | |

1520 | |

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

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

1523 | true). |

1524 | |

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

1526 | |

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

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

1529 | |

1530 | template<typename T> |

1531 | inline bool |

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

1533 | { |

1534 | if (space (nelems)) |

1535 | return false; |

1536 | |

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

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

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

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

1541 | unsigned int oldsize = 0; |

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

1543 | if (handle_auto_vec) |

1544 | { |

1545 | m_vec = NULL; |

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

1547 | nelems += oldsize; |

1548 | } |

1549 | |

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

1551 | if (handle_auto_vec) |

1552 | { |

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

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

1555 | } |

1556 | |

1557 | return true; |

1558 | } |

1559 | |

1560 | |

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

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

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

1564 | actually occurred. */ |

1565 | |

1566 | template<typename T> |

1567 | inline bool |

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

1569 | { |

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

1571 | } |

1572 | |

1573 | |

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

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

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

1577 | existed, is lost. */ |

1578 | |

1579 | template<typename T> |

1580 | inline void |

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

1582 | { |

1583 | m_vec = NULL; |

1584 | if (nelems > 0) |

1585 | reserve_exact (nelems PASS_MEM_STAT); |

1586 | } |

1587 | |

1588 | |

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

1590 | |

1591 | template<typename T> |

1592 | inline void |

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

1594 | { |

1595 | if (!m_vec) |

1596 | return; |

1597 | |

1598 | if (using_auto_storage ()) |

1599 | { |

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

1601 | return; |

1602 | } |

1603 | |

1604 | va_heap::release (m_vec); |

1605 | } |

1606 | |

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

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

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

1610 | headroom available. */ |

1611 | |

1612 | template<typename T> |

1613 | inline void |

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

1615 | { |

1616 | if (src.m_vec) |

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

1618 | } |

1619 | |

1620 | |

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

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

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

1624 | as needed. */ |

1625 | |

1626 | template<typename T> |

1627 | inline void |

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

1629 | MEM_STAT_DECL) |

1630 | { |

1631 | if (src.length ()) |

1632 | { |

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

1634 | splice (src); |

1635 | } |

1636 | } |

1637 | |

1638 | |

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

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

1641 | where OBJ was inserted. */ |

1642 | |

1643 | template<typename T> |

1644 | inline T * |

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

1646 | { |

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

1648 | } |

1649 | |

1650 | |

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

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

1653 | OBJ was inserted. */ |

1654 | |

1655 | template<typename T> |

1656 | inline T * |

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

1658 | { |

1659 | reserve (1, false PASS_MEM_STAT); |

1660 | return quick_push (obj); |

1661 | } |

1662 | |

1663 | |

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

1665 | |

1666 | template<typename T> |

1667 | inline T & |

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

1669 | { |

1670 | return m_vec->pop (); |

1671 | } |

1672 | |

1673 | |

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

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

1676 | |

1677 | template<typename T> |

1678 | inline void |

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

1680 | { |

1681 | if (m_vec) |

1682 | m_vec->truncate (size); |

1683 | else |

1684 | gcc_checking_assert (size == 0); |

1685 | } |

1686 | |

1687 | |

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

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

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

1691 | |

1692 | template<typename T> |

1693 | inline void |

1694 | vec<T, va_heap, vl_ptr>::safe_grow (unsigned len MEM_STAT_DECL) |

1695 | { |

1696 | unsigned oldlen = length (); |

1697 | gcc_checking_assert (oldlen <= len); |

1698 | reserve_exact (len - oldlen PASS_MEM_STAT); |

1699 | if (m_vec) |

1700 | m_vec->quick_grow (len); |

1701 | else |

1702 | gcc_checking_assert (len == 0); |

1703 | } |

1704 | |

1705 | |

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

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

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

1709 | |

1710 | template<typename T> |

1711 | inline void |

1712 | vec<T, va_heap, vl_ptr>::safe_grow_cleared (unsigned len MEM_STAT_DECL) |

1713 | { |

1714 | unsigned oldlen = length (); |

1715 | size_t growby = len - oldlen; |

1716 | safe_grow (len PASS_MEM_STAT); |

1717 | if (growby != 0) |

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

1719 | } |

1720 | |

1721 | |

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

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

1724 | |

1725 | template<typename T> |

1726 | inline void |

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

1728 | { |

1729 | gcc_checking_assert (m_vec); |

1730 | m_vec->quick_grow (len); |

1731 | } |

1732 | |

1733 | |

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

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

1736 | assertion will be triggered. */ |

1737 | |

1738 | template<typename T> |

1739 | inline void |

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

1741 | { |

1742 | gcc_checking_assert (m_vec); |

1743 | m_vec->quick_grow_cleared (len); |

1744 | } |

1745 | |

1746 | |

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

1748 | must be sufficient space. */ |

1749 | |

1750 | template<typename T> |

1751 | inline void |

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

1753 | { |

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

1755 | } |

1756 | |

1757 | |

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

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

1760 | |

1761 | template<typename T> |

1762 | inline void |

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

1764 | { |

1765 | reserve (1, false PASS_MEM_STAT); |

1766 | quick_insert (ix, obj); |

1767 | } |

1768 | |

1769 | |

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

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

1772 | a memmove. */ |

1773 | |

1774 | template<typename T> |

1775 | inline void |

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

1777 | { |

1778 | m_vec->ordered_remove (ix); |

1779 | } |

1780 | |

1781 | |

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

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

1784 | |

1785 | template<typename T> |

1786 | inline void |

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

1788 | { |

1789 | m_vec->unordered_remove (ix); |

1790 | } |

1791 | |

1792 | |

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

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

1795 | |

1796 | template<typename T> |

1797 | inline void |

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

1799 | { |

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

1801 | } |

1802 | |

1803 | |

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

1805 | function to pass to qsort. */ |

1806 | |

1807 | template<typename T> |

1808 | inline void |

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

1810 | { |

1811 | if (m_vec) |

1812 | m_vec->qsort (cmp); |

1813 | } |

1814 | |

1815 | |

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

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

1818 | |

1819 | template<typename T> |

1820 | inline T * |

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

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

1823 | { |

1824 | if (m_vec) |

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

1826 | return NULL; |

1827 | } |

1828 | |

1829 | |

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

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

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

1833 | than the second. */ |

1834 | |

1835 | template<typename T> |

1836 | inline unsigned |

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

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

1839 | const |

1840 | { |

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

1842 | } |

1843 | |

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

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

1846 | |

1847 | template<typename T> |

1848 | inline bool |

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

1850 | { |

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

1852 | } |

1853 | |

1854 | template<typename T> |

1855 | inline bool |

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

1857 | { |

1858 | return m_vec->m_vecpfx.m_using_auto_storage; |

1859 | } |

1860 | |

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

1862 | |

1863 | template<typename T> |

1864 | inline void |

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

1866 | { |

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

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

1869 | |

1870 | vec.release (); |

1871 | } |

1872 | |

1873 | #if (GCC_VERSION >= 3000) |

1874 | # pragma GCC poison m_vec m_vecpfx m_vecdata |

1875 | #endif |

1876 | |

1877 | #endif // GCC_VEC_H |

1878 |