1/* Vector API for GNU compiler.
2 Copyright (C) 2004-2024 Free Software Foundation, Inc.
3 Contributed by Nathan Sidwell <nathan@codesourcery.com>
4 Re-implemented in C++ by Diego Novillo <dnovillo@google.com>
5
6This file is part of GCC.
7
8GCC is free software; you can redistribute it and/or modify it under
9the terms of the GNU General Public License as published by the Free
10Software Foundation; either version 3, or (at your option) any later
11version.
12
13GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14WARRANTY; without even the implied warranty of MERCHANTABILITY or
15FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16for more details.
17
18You should have received a copy of the GNU General Public License
19along with GCC; see the file COPYING3. If not see
20<http://www.gnu.org/licenses/>. */
21
22/* This file is compiled twice: once for the generator programs
23 once for the compiler. */
24#ifdef GENERATOR_FILE
25#include "bconfig.h"
26#else
27#include "config.h"
28#endif
29
30#include "system.h"
31#include "coretypes.h"
32#include "hash-table.h"
33#include "selftest.h"
34#ifdef GENERATOR_FILE
35#include "errors.h"
36#else
37#include "input.h"
38#include "diagnostic-core.h"
39#endif
40
41/* Vector memory usage. */
42class vec_usage: public mem_usage
43{
44public:
45 /* Default constructor. */
46 vec_usage (): m_items (0), m_items_peak (0), m_element_size (0) {}
47
48 /* Constructor. */
49 vec_usage (size_t allocated, size_t times, size_t peak,
50 size_t items, size_t items_peak, size_t element_size)
51 : mem_usage (allocated, times, peak),
52 m_items (items), m_items_peak (items_peak),
53 m_element_size (element_size) {}
54
55 /* Sum the usage with SECOND usage. */
56 vec_usage
57 operator+ (const vec_usage &second)
58 {
59 return vec_usage (m_allocated + second.m_allocated,
60 m_times + second.m_times,
61 m_peak + second.m_peak,
62 m_items + second.m_items,
63 m_items_peak + second.m_items_peak, 0);
64 }
65
66 /* Dump usage coupled to LOC location, where TOTAL is sum of all rows. */
67 inline void
68 dump (mem_location *loc, mem_usage &total) const
69 {
70 char s[4096];
71 sprintf (s: s, format: "%s:%i (%s)", loc->get_trimmed_filename (),
72 loc->m_line, loc->m_function);
73
74 s[48] = '\0';
75
76 fprintf (stderr,
77 format: "%-48s %10" PRIu64 PRsa (10) ":%4.1f%%" PRsa (9) "%10" PRIu64
78 ":%4.1f%%" PRsa (10) PRsa (10) "\n",
79 s,
80 (uint64_t)m_element_size,
81 SIZE_AMOUNT (m_allocated),
82 m_allocated * 100.0 / total.m_allocated,
83 SIZE_AMOUNT (m_peak), (uint64_t)m_times,
84 m_times * 100.0 / total.m_times,
85 SIZE_AMOUNT (m_items), SIZE_AMOUNT (m_items_peak));
86 }
87
88 /* Dump footer. */
89 inline void
90 dump_footer ()
91 {
92 fprintf (stderr, format: "%s" PRsa (64) PRsa (25) PRsa (16) "\n",
93 "Total", SIZE_AMOUNT (m_allocated),
94 SIZE_AMOUNT (m_times), SIZE_AMOUNT (m_items));
95 }
96
97 /* Dump header with NAME. */
98 static inline void
99 dump_header (const char *name)
100 {
101 fprintf (stderr, format: "%-48s %10s%11s%16s%10s%17s%11s\n", name, "sizeof(T)",
102 "Leak", "Peak", "Times", "Leak items", "Peak items");
103 }
104
105 /* Current number of items allocated. */
106 size_t m_items;
107 /* Peak value of number of allocated items. */
108 size_t m_items_peak;
109 /* Size of element of the vector. */
110 size_t m_element_size;
111};
112
113/* Vector memory description. */
114static mem_alloc_description <vec_usage> vec_mem_desc;
115
116/* Account the overhead. */
117
118void
119vec_prefix::register_overhead (void *ptr, size_t elements,
120 size_t element_size MEM_STAT_DECL)
121{
122 vec_mem_desc.register_descriptor (ptr, origin: VEC_ORIGIN, ggc: false
123 FINAL_PASS_MEM_STAT);
124 vec_usage *usage
125 = vec_mem_desc.register_instance_overhead (size: elements * element_size, ptr);
126 usage->m_element_size = element_size;
127 usage->m_items += elements;
128 if (usage->m_items_peak < usage->m_items)
129 usage->m_items_peak = usage->m_items;
130}
131
132/* Notice that the memory allocated for the vector has been freed. */
133
134void
135vec_prefix::release_overhead (void *ptr, size_t size, size_t elements,
136 bool in_dtor MEM_STAT_DECL)
137{
138 if (!vec_mem_desc.contains_descriptor_for_instance (ptr))
139 vec_mem_desc.register_descriptor (ptr, origin: VEC_ORIGIN,
140 ggc: false FINAL_PASS_MEM_STAT);
141 vec_usage *usage = vec_mem_desc.release_instance_overhead (ptr, size,
142 remove_from_map: in_dtor);
143 usage->m_items -= elements;
144}
145
146/* Calculate the number of slots to reserve a vector, making sure that
147 it is of at least DESIRED size by growing ALLOC exponentially. */
148
149unsigned
150vec_prefix::calculate_allocation_1 (unsigned alloc, unsigned desired)
151{
152 /* We must have run out of room. */
153 gcc_assert (alloc < desired);
154
155 /* Exponential growth. */
156 if (!alloc)
157 alloc = 4;
158 else if (alloc < 16)
159 /* Double when small. */
160 alloc = alloc * 2;
161 else
162 /* Grow slower when large. */
163 alloc = (alloc * 3 / 2);
164
165 /* If this is still too small, set it to the right size. */
166 if (alloc < desired)
167 alloc = desired;
168 return alloc;
169}
170
171/* Dump per-site memory statistics. */
172
173void
174dump_vec_loc_statistics (void)
175{
176 vec_mem_desc.dump (origin: VEC_ORIGIN);
177}
178
179#if CHECKING_P
180/* Report qsort comparator CMP consistency check failure with P1, P2, P3 as
181 witness elements. */
182ATTRIBUTE_NORETURN ATTRIBUTE_COLD
183static void
184qsort_chk_error (const void *p1, const void *p2, const void *p3,
185 sort_r_cmp_fn *cmp, void *data)
186{
187 if (!p3)
188 {
189 int r1 = cmp (p1, p2, data), r2 = cmp (p2, p1, data);
190 error ("qsort comparator not anti-symmetric: %d, %d", r1, r2);
191 }
192 else if (p1 == p2)
193 {
194 int r = cmp (p1, p3, data);
195 error ("qsort comparator non-negative on sorted output: %d", r);
196 }
197 else
198 {
199 int r1 = cmp (p1, p2, data);
200 int r2 = cmp (p2, p3, data);
201 int r3 = cmp (p1, p3, data);
202 error ("qsort comparator not transitive: %d, %d, %d", r1, r2, r3);
203 }
204 internal_error ("qsort checking failed");
205}
206
207/* Verify anti-symmetry and transitivity for comparator CMP on sorted array
208 of N SIZE-sized elements pointed to by BASE. */
209void
210qsort_chk (void *base, size_t n, size_t size, sort_r_cmp_fn *cmp, void *data)
211{
212#if 0
213#define LIM(n) (n)
214#else
215 /* Limit overall time complexity to O(n log n). */
216#define LIM(n) ((n) <= 16 ? (n) : 12 + floor_log2 (n))
217#endif
218#define ELT(i) ((const char *) base + (i) * size)
219#define CMP(i, j) cmp (ELT (i), ELT (j), data)
220#define ERR2(i, j) qsort_chk_error (ELT (i), ELT (j), NULL, cmp, data)
221#define ERR3(i, j, k) qsort_chk_error (ELT (i), ELT (j), ELT (k), cmp, data)
222 size_t i1, i2, i, j;
223 /* This outer loop iterates over maximum spans [i1, i2) such that
224 elements within each span compare equal to each other. */
225 for (i1 = 0; i1 < n; i1 = i2)
226 {
227 /* Position i2 one past last element that compares equal to i1'th. */
228 for (i2 = i1 + 1; i2 < n; i2++)
229 if (CMP (i1, i2))
230 break;
231 else if (CMP (i2, i1))
232 ERR2 (i1, i2);
233 size_t lim1 = LIM (i2 - i1), lim2 = LIM (n - i2);
234 /* Verify that other pairs within current span compare equal. */
235 for (i = i1 + 1; i + 1 < i2; i++)
236 for (j = i + 1; j < i1 + lim1; j++)
237 if (CMP (i, j))
238 ERR3 (i, i1, j);
239 else if (CMP (j, i))
240 ERR2 (i, j);
241 /* Verify that elements within this span compare less than
242 elements beyond the span. */
243 for (i = i1; i < i2; i++)
244 for (j = i2; j < i2 + lim2; j++)
245 if (CMP (i, j) >= 0)
246 ERR3 (i, i1, j);
247 else if (CMP (j, i) <= 0)
248 ERR2 (i, j);
249 }
250#undef ERR3
251#undef ERR2
252#undef CMP
253#undef ELT
254#undef LIM
255}
256#endif /* #if CHECKING_P */
257
258#ifndef GENERATOR_FILE
259#if CHECKING_P
260
261namespace selftest {
262
263/* Selftests. */
264
265/* Call V.safe_push for all ints from START up to, but not including LIMIT.
266 Helper function for selftests. */
267
268static void
269safe_push_range (vec <int>&v, int start, int limit)
270{
271 for (int i = start; i < limit; i++)
272 v.safe_push (i);
273}
274
275/* Verify forms of initialization. */
276
277static void
278test_init ()
279{
280 {
281 vec<int> v1{ };
282 ASSERT_EQ (0, v1.length ());
283
284 vec<int> v2 (v1);
285 ASSERT_EQ (0, v2.length ());
286 }
287
288 {
289 vec<int> v1 = vec<int>();
290 ASSERT_EQ (0, v1.length ());
291
292 vec<int> v2 = v1;
293 ASSERT_EQ (0, v2.length ());
294 }
295
296 {
297 vec<int> v1 (vNULL);
298 ASSERT_EQ (0, v1.length ());
299 v1.safe_push (1);
300
301 vec<int> v2 (v1);
302 ASSERT_EQ (1, v1.length ());
303 v2.safe_push (1);
304
305 ASSERT_EQ (2, v1.length ());
306 ASSERT_EQ (2, v2.length ());
307 v1.release ();
308 }
309}
310
311/* Verify that vec::quick_push works correctly. */
312
313static void
314test_quick_push ()
315{
316 auto_vec <int> v;
317 ASSERT_EQ (0, v.length ());
318 v.reserve (3);
319 ASSERT_EQ (0, v.length ());
320 ASSERT_TRUE (v.space (3));
321 v.quick_push (5);
322 v.quick_push (6);
323 v.quick_push (7);
324 ASSERT_EQ (3, v.length ());
325 ASSERT_EQ (5, v[0]);
326 ASSERT_EQ (6, v[1]);
327 ASSERT_EQ (7, v[2]);
328}
329
330/* Verify that vec::safe_push works correctly. */
331
332static void
333test_safe_push ()
334{
335 auto_vec <int> v;
336 ASSERT_EQ (0, v.length ());
337 v.safe_push (5);
338 v.safe_push (6);
339 v.safe_push (7);
340 ASSERT_EQ (3, v.length ());
341 ASSERT_EQ (5, v[0]);
342 ASSERT_EQ (6, v[1]);
343 ASSERT_EQ (7, v[2]);
344}
345
346/* Verify that vec::truncate works correctly. */
347
348static void
349test_truncate ()
350{
351 auto_vec <int> v;
352 ASSERT_EQ (0, v.length ());
353 safe_push_range (v, 0, 10);
354 ASSERT_EQ (10, v.length ());
355
356 v.truncate (5);
357 ASSERT_EQ (5, v.length ());
358}
359
360/* Verify that vec::safe_grow_cleared works correctly. */
361
362static void
363test_safe_grow_cleared ()
364{
365 auto_vec <int> v;
366 ASSERT_EQ (0, v.length ());
367 v.safe_grow_cleared (50, true);
368 ASSERT_EQ (50, v.length ());
369 ASSERT_EQ (0, v[0]);
370 ASSERT_EQ (0, v[49]);
371}
372
373/* Verify that vec::pop works correctly. */
374
375static void
376test_pop ()
377{
378 auto_vec <int> v;
379 safe_push_range (v, 5, 20);
380 ASSERT_EQ (15, v.length ());
381
382 int last = v.pop ();
383 ASSERT_EQ (19, last);
384 ASSERT_EQ (14, v.length ());
385}
386
387/* Verify that vec::safe_insert works correctly. */
388
389static void
390test_safe_insert ()
391{
392 auto_vec <int> v;
393 safe_push_range (v, 0, 10);
394 v.safe_insert (5, 42);
395 ASSERT_EQ (4, v[4]);
396 ASSERT_EQ (42, v[5]);
397 ASSERT_EQ (5, v[6]);
398 ASSERT_EQ (11, v.length ());
399}
400
401/* Verify that vec::ordered_remove works correctly. */
402
403static void
404test_ordered_remove ()
405{
406 auto_vec <int> v;
407 safe_push_range (v, 0, 10);
408 v.ordered_remove (5);
409 ASSERT_EQ (4, v[4]);
410 ASSERT_EQ (6, v[5]);
411 ASSERT_EQ (9, v.length ());
412}
413
414/* Verify that vec::ordered_remove_if works correctly. */
415
416static void
417test_ordered_remove_if (void)
418{
419 auto_vec <int> v;
420 safe_push_range (v, 0, 10);
421 unsigned ix, ix2;
422 int *elem_ptr;
423 VEC_ORDERED_REMOVE_IF (v, ix, ix2, elem_ptr,
424 *elem_ptr == 5 || *elem_ptr == 7);
425 ASSERT_EQ (4, v[4]);
426 ASSERT_EQ (6, v[5]);
427 ASSERT_EQ (8, v[6]);
428 ASSERT_EQ (8, v.length ());
429
430 v.truncate (0);
431 safe_push_range (v, 0, 10);
432 VEC_ORDERED_REMOVE_IF_FROM_TO (v, ix, ix2, elem_ptr, 0, 6,
433 *elem_ptr == 5 || *elem_ptr == 7);
434 ASSERT_EQ (4, v[4]);
435 ASSERT_EQ (6, v[5]);
436 ASSERT_EQ (7, v[6]);
437 ASSERT_EQ (9, v.length ());
438
439 v.truncate (0);
440 safe_push_range (v, 0, 10);
441 VEC_ORDERED_REMOVE_IF_FROM_TO (v, ix, ix2, elem_ptr, 0, 5,
442 *elem_ptr == 5 || *elem_ptr == 7);
443 VEC_ORDERED_REMOVE_IF_FROM_TO (v, ix, ix2, elem_ptr, 8, 10,
444 *elem_ptr == 5 || *elem_ptr == 7);
445 ASSERT_EQ (4, v[4]);
446 ASSERT_EQ (5, v[5]);
447 ASSERT_EQ (6, v[6]);
448 ASSERT_EQ (10, v.length ());
449
450 v.truncate (0);
451 safe_push_range (v, 0, 10);
452 VEC_ORDERED_REMOVE_IF (v, ix, ix2, elem_ptr, *elem_ptr == 5);
453 ASSERT_EQ (4, v[4]);
454 ASSERT_EQ (6, v[5]);
455 ASSERT_EQ (7, v[6]);
456 ASSERT_EQ (9, v.length ());
457}
458
459/* Verify that vec::unordered_remove works correctly. */
460
461static void
462test_unordered_remove ()
463{
464 auto_vec <int> v;
465 safe_push_range (v, 0, 10);
466 v.unordered_remove (5);
467 ASSERT_EQ (9, v.length ());
468}
469
470/* Verify that vec::block_remove works correctly. */
471
472static void
473test_block_remove ()
474{
475 auto_vec <int> v;
476 safe_push_range (v, 0, 10);
477 v.block_remove (5, 3);
478 ASSERT_EQ (3, v[3]);
479 ASSERT_EQ (4, v[4]);
480 ASSERT_EQ (8, v[5]);
481 ASSERT_EQ (9, v[6]);
482 ASSERT_EQ (7, v.length ());
483}
484
485/* Comparator for use by test_qsort. */
486
487static int
488reverse_cmp (const void *p_i, const void *p_j)
489{
490 return *(const int *)p_j - *(const int *)p_i;
491}
492
493/* Verify that vec::qsort works correctly. */
494
495static void
496test_qsort ()
497{
498 auto_vec <int> v;
499 safe_push_range (v, 0, 10);
500 v.qsort (reverse_cmp);
501 ASSERT_EQ (9, v[0]);
502 ASSERT_EQ (8, v[1]);
503 ASSERT_EQ (1, v[8]);
504 ASSERT_EQ (0, v[9]);
505 ASSERT_EQ (10, v.length ());
506}
507
508/* Verify that vec::reverse works correctly. */
509
510static void
511test_reverse ()
512{
513 /* Reversing an empty vec ought to be a no-op. */
514 {
515 auto_vec <int> v;
516 ASSERT_EQ (0, v.length ());
517 v.reverse ();
518 ASSERT_EQ (0, v.length ());
519 }
520
521 /* Verify reversing a vec with even length. */
522 {
523 auto_vec <int> v;
524 safe_push_range (v, 0, 4);
525 v.reverse ();
526 ASSERT_EQ (3, v[0]);
527 ASSERT_EQ (2, v[1]);
528 ASSERT_EQ (1, v[2]);
529 ASSERT_EQ (0, v[3]);
530 ASSERT_EQ (4, v.length ());
531 }
532
533 /* Verify reversing a vec with odd length. */
534 {
535 auto_vec <int> v;
536 safe_push_range (v, 0, 3);
537 v.reverse ();
538 ASSERT_EQ (2, v[0]);
539 ASSERT_EQ (1, v[1]);
540 ASSERT_EQ (0, v[2]);
541 ASSERT_EQ (3, v.length ());
542 }
543}
544
545/* A test class that increments a counter every time its dtor is called. */
546
547class count_dtor
548{
549 public:
550 count_dtor (int *counter) : m_counter (counter) {}
551 ~count_dtor () { (*m_counter)++; }
552
553 private:
554 int *m_counter;
555};
556
557/* Verify that auto_delete_vec deletes the elements within it. */
558
559static void
560test_auto_delete_vec ()
561{
562 int dtor_count = 0;
563 {
564 auto_delete_vec <count_dtor> v;
565 v.safe_push (new count_dtor (&dtor_count));
566 v.safe_push (new count_dtor (&dtor_count));
567 }
568 ASSERT_EQ (dtor_count, 2);
569}
570
571/* Verify accesses to vector elements are done indirectly. */
572
573static void
574test_auto_alias ()
575{
576 volatile int i = 1;
577 auto_vec<int, 8> v;
578 v.quick_grow (2);
579 v[0] = 1;
580 v[1] = 2;
581 int val;
582 for (int ix = i; v.iterate (ix, &val); ix++)
583 ASSERT_EQ (val, 2);
584 ASSERT_EQ (val, 0);
585}
586
587/* Run all of the selftests within this file. */
588
589void
590vec_cc_tests ()
591{
592 test_init ();
593 test_quick_push ();
594 test_safe_push ();
595 test_truncate ();
596 test_safe_grow_cleared ();
597 test_pop ();
598 test_safe_insert ();
599 test_ordered_remove ();
600 test_ordered_remove_if ();
601 test_unordered_remove ();
602 test_block_remove ();
603 test_qsort ();
604 test_reverse ();
605 test_auto_delete_vec ();
606 test_auto_alias ();
607}
608
609} // namespace selftest
610
611#endif /* #if CHECKING_P */
612#endif /* #ifndef GENERATOR_FILE */
613

source code of gcc/vec.cc