Branch data Line data Source code
1 : : /* Vector API for GNU compiler.
2 : : Copyright (C) 2004-2025 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 : : /* 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. */
42 : : class vec_usage: public mem_usage
43 : : {
44 : : public:
45 : : /* Default constructor. */
46 : 0 : vec_usage (): m_items (0), m_items_peak (0), m_element_size (0) {}
47 : :
48 : : /* Constructor. */
49 : 0 : vec_usage (size_t allocated, size_t times, size_t peak,
50 : : size_t items, size_t items_peak, size_t element_size)
51 : 0 : : mem_usage (allocated, times, peak),
52 : 0 : m_items (items), m_items_peak (items_peak),
53 : 0 : m_element_size (element_size) {}
54 : :
55 : : /* Sum the usage with SECOND usage. */
56 : : vec_usage
57 : 0 : operator+ (const vec_usage &second)
58 : : {
59 : 0 : return vec_usage (m_allocated + second.m_allocated,
60 : 0 : m_times + second.m_times,
61 : 0 : m_peak + second.m_peak,
62 : 0 : m_items + second.m_items,
63 : 0 : 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 : 0 : dump (mem_location *loc, mem_usage &total) const
69 : : {
70 : 0 : char s[4096];
71 : 0 : sprintf (s, "%s:%i (%s)", loc->get_trimmed_filename (),
72 : : loc->m_line, loc->m_function);
73 : :
74 : 0 : s[48] = '\0';
75 : :
76 : 0 : fprintf (stderr,
77 : : "%-48s %10" PRIu64 PRsa (10) ":%4.1f%%" PRsa (9) "%10" PRIu64
78 : : ":%4.1f%%" PRsa (10) PRsa (10) "\n",
79 : : s,
80 : 0 : (uint64_t)m_element_size,
81 : 0 : SIZE_AMOUNT (m_allocated),
82 : 0 : m_allocated * 100.0 / total.m_allocated,
83 : 0 : SIZE_AMOUNT (m_peak), (uint64_t)m_times,
84 : 0 : m_times * 100.0 / total.m_times,
85 : 0 : SIZE_AMOUNT (m_items), SIZE_AMOUNT (m_items_peak));
86 : 0 : }
87 : :
88 : : /* Dump footer. */
89 : : inline void
90 : 0 : dump_footer ()
91 : : {
92 : 0 : fprintf (stderr, "%s" PRsa (64) PRsa (25) PRsa (16) "\n",
93 : 0 : "Total", SIZE_AMOUNT (m_allocated),
94 : 0 : SIZE_AMOUNT (m_times), SIZE_AMOUNT (m_items));
95 : 0 : }
96 : :
97 : : /* Dump header with NAME. */
98 : : static inline void
99 : 0 : dump_header (const char *name)
100 : : {
101 : 0 : fprintf (stderr, "%-48s %10s%11s%16s%10s%17s%11s\n", name, "sizeof(T)",
102 : : "Leak", "Peak", "Times", "Leak items", "Peak items");
103 : 0 : }
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. */
114 : : static mem_alloc_description <vec_usage> vec_mem_desc;
115 : :
116 : : /* Account the overhead. */
117 : :
118 : : void
119 : 0 : vec_prefix::register_overhead (void *ptr, size_t elements,
120 : : size_t element_size MEM_STAT_DECL)
121 : : {
122 : 0 : vec_mem_desc.register_descriptor (ptr, VEC_ORIGIN, false
123 : : FINAL_PASS_MEM_STAT);
124 : 0 : vec_usage *usage
125 : 0 : = vec_mem_desc.register_instance_overhead (elements * element_size, ptr);
126 : 0 : usage->m_element_size = element_size;
127 : 0 : usage->m_items += elements;
128 : 0 : if (usage->m_items_peak < usage->m_items)
129 : 0 : usage->m_items_peak = usage->m_items;
130 : 0 : }
131 : :
132 : : /* Notice that the memory allocated for the vector has been freed. */
133 : :
134 : : void
135 : 0 : vec_prefix::release_overhead (void *ptr, size_t size, size_t elements,
136 : : bool in_dtor MEM_STAT_DECL)
137 : : {
138 : 0 : if (!vec_mem_desc.contains_descriptor_for_instance (ptr))
139 : 0 : vec_mem_desc.register_descriptor (ptr, VEC_ORIGIN,
140 : : false FINAL_PASS_MEM_STAT);
141 : 0 : vec_usage *usage = vec_mem_desc.release_instance_overhead (ptr, size,
142 : : in_dtor);
143 : 0 : usage->m_items -= elements;
144 : 0 : }
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 : :
149 : : unsigned
150 : 842384852 : vec_prefix::calculate_allocation_1 (unsigned alloc, unsigned desired)
151 : : {
152 : : /* We must have run out of room. */
153 : 842384852 : gcc_assert (alloc < desired);
154 : :
155 : : /* Exponential growth. */
156 : 842384852 : if (!alloc)
157 : : alloc = 4;
158 : 842384852 : else if (alloc < 16)
159 : : /* Double when small. */
160 : 699684529 : alloc = alloc * 2;
161 : : else
162 : : /* Grow slower when large. */
163 : 142700323 : alloc = (alloc * 3 / 2);
164 : :
165 : : /* If this is still too small, set it to the right size. */
166 : 842384852 : if (alloc < desired)
167 : : alloc = desired;
168 : 842384852 : return alloc;
169 : : }
170 : :
171 : : /* Dump per-site memory statistics. */
172 : :
173 : : void
174 : 0 : dump_vec_loc_statistics (void)
175 : : {
176 : 0 : vec_mem_desc.dump (VEC_ORIGIN);
177 : 0 : }
178 : :
179 : : /* Gets the next token from STR delimited by DELIMS (deliminator not included
180 : : in returned string).
181 : :
182 : : Updates STR to be the remaining string after the given token.
183 : :
184 : : STR and DELIMS must both be valid string_slices.
185 : :
186 : : If there aren't any of the chars in DELIM in STR (ie no more tokens in STR)
187 : : then returns the string, and updates STR to be invalid. */
188 : : string_slice
189 : 367 : string_slice::tokenize (string_slice *str, string_slice delims)
190 : : {
191 : 367 : const char *ptr = str->begin ();
192 : :
193 : 367 : gcc_assert (str->is_valid () && delims.is_valid ());
194 : :
195 : 2799 : for (; ptr < str->end (); ptr++)
196 : 5194 : for (char c : delims)
197 : 2762 : if (*ptr == c)
198 : : {
199 : : /* Update the input string to be the remaining string. */
200 : 62 : const char *str_begin = str->begin ();
201 : 62 : *str = string_slice (ptr + 1, str->end ());
202 : 62 : return string_slice (str_begin, ptr);
203 : : }
204 : :
205 : : /* If no deliminators between the start and end, return the whole string. */
206 : 305 : string_slice res = *str;
207 : 305 : *str = string_slice::invalid ();
208 : 305 : return res;
209 : : }
210 : :
211 : : /* Compares the string_slices STR1 and STR2 giving a lexograpical ordering.
212 : : Returns -1 if STR1 comes before STR2, 1 if STR1 comes after, and 0 if the
213 : : string_slices have the same contents. */
214 : :
215 : : int
216 : 32 : string_slice::strcmp (string_slice str1, string_slice str2)
217 : : {
218 : 56 : for (unsigned int i = 0; i < str1.size () && i < str2.size (); i++)
219 : : {
220 : 32 : if (str1[i] < str2[i])
221 : : return -1;
222 : 28 : if (str1[i] > str2[i])
223 : : return 1;
224 : : }
225 : :
226 : 24 : if (str1.size () < str2.size ())
227 : : return -1;
228 : 20 : if (str1.size () > str2.size ())
229 : 8 : return 1;
230 : : return 0;
231 : : }
232 : :
233 : : string_slice
234 : 323 : string_slice::strip ()
235 : : {
236 : 323 : const char *start = this->begin ();
237 : 323 : const char *end = this->end ();
238 : :
239 : 710 : while (start < end && ISSPACE (*start))
240 : 64 : start++;
241 : 359 : while (end > start && ISSPACE (*(end-1)))
242 : 36 : end--;
243 : :
244 : 323 : return string_slice (start, end);
245 : : }
246 : :
247 : : #if CHECKING_P
248 : : /* Report qsort comparator CMP consistency check failure with P1, P2, P3 as
249 : : witness elements. */
250 : : ATTRIBUTE_NORETURN ATTRIBUTE_COLD
251 : : static void
252 : 0 : qsort_chk_error (const void *p1, const void *p2, const void *p3,
253 : : sort_r_cmp_fn *cmp, void *data)
254 : : {
255 : 0 : if (!p3)
256 : : {
257 : 0 : int r1 = cmp (p1, p2, data), r2 = cmp (p2, p1, data);
258 : 0 : error ("qsort comparator not anti-symmetric: %d, %d", r1, r2);
259 : : }
260 : 0 : else if (p1 == p2)
261 : : {
262 : 0 : int r = cmp (p1, p3, data);
263 : 0 : error ("qsort comparator non-negative on sorted output: %d", r);
264 : : }
265 : : else
266 : : {
267 : 0 : int r1 = cmp (p1, p2, data);
268 : 0 : int r2 = cmp (p2, p3, data);
269 : 0 : int r3 = cmp (p1, p3, data);
270 : 0 : error ("qsort comparator not transitive: %d, %d, %d", r1, r2, r3);
271 : : }
272 : 0 : internal_error ("qsort checking failed");
273 : : }
274 : :
275 : : /* Verify anti-symmetry and transitivity for comparator CMP on sorted array
276 : : of N SIZE-sized elements pointed to by BASE. */
277 : : void
278 : 170008157 : qsort_chk (void *base, size_t n, size_t size, sort_r_cmp_fn *cmp, void *data)
279 : : {
280 : : #if 0
281 : : #define LIM(n) (n)
282 : : #else
283 : : /* Limit overall time complexity to O(n log n). */
284 : : #define LIM(n) ((n) <= 16 ? (n) : 12 + floor_log2 (n))
285 : : #endif
286 : : #define ELT(i) ((const char *) base + (i) * size)
287 : : #define CMP(i, j) cmp (ELT (i), ELT (j), data)
288 : : #define ERR2(i, j) qsort_chk_error (ELT (i), ELT (j), NULL, cmp, data)
289 : : #define ERR3(i, j, k) qsort_chk_error (ELT (i), ELT (j), ELT (k), cmp, data)
290 : 170008157 : size_t i1, i2, i, j;
291 : : /* This outer loop iterates over maximum spans [i1, i2) such that
292 : : elements within each span compare equal to each other. */
293 : 1332773640 : for (i1 = 0; i1 < n; i1 = i2)
294 : : {
295 : : /* Position i2 one past last element that compares equal to i1'th. */
296 : 1259816809 : for (i2 = i1 + 1; i2 < n; i2++)
297 : 1089808652 : if (CMP (i1, i2))
298 : : break;
299 : 97051326 : else if (CMP (i2, i1))
300 : 0 : ERR2 (i1, i2);
301 : 1162765483 : size_t lim1 = LIM (i2 - i1), lim2 = LIM (n - i2);
302 : : /* Verify that other pairs within current span compare equal. */
303 : 1249407503 : for (i = i1 + 1; i + 1 < i2; i++)
304 : 188158364 : for (j = i + 1; j < i1 + lim1; j++)
305 : 101516344 : if (CMP (i, j))
306 : 0 : ERR3 (i, i1, j);
307 : 101516344 : else if (CMP (j, i))
308 : 0 : ERR2 (i, j);
309 : : /* Verify that elements within this span compare less than
310 : : elements beyond the span. */
311 : 2422582292 : for (i = i1; i < i2; i++)
312 : 13305780087 : for (j = i2; j < i2 + lim2; j++)
313 : 12045963278 : if (CMP (i, j) >= 0)
314 : 0 : ERR3 (i, i1, j);
315 : 12045963278 : else if (CMP (j, i) <= 0)
316 : 0 : ERR2 (i, j);
317 : : }
318 : : #undef ERR3
319 : : #undef ERR2
320 : : #undef CMP
321 : : #undef ELT
322 : : #undef LIM
323 : 170008157 : }
324 : : #endif /* #if CHECKING_P */
325 : :
326 : : #ifndef GENERATOR_FILE
327 : : #if CHECKING_P
328 : :
329 : : namespace selftest {
330 : :
331 : : /* Selftests. */
332 : :
333 : : /* Call V.safe_push for all ints from START up to, but not including LIMIT.
334 : : Helper function for selftests. */
335 : :
336 : : static void
337 : 52 : safe_push_range (vec <int>&v, int start, int limit)
338 : : {
339 : 540 : for (int i = start; i < limit; i++)
340 : 488 : v.safe_push (i);
341 : 52 : }
342 : :
343 : : /* Verify forms of initialization. */
344 : :
345 : : static void
346 : 4 : test_init ()
347 : : {
348 : 4 : {
349 : 4 : vec<int> v1{ };
350 : 4 : ASSERT_EQ (0, v1.length ());
351 : :
352 : 4 : vec<int> v2 (v1);
353 : 4 : ASSERT_EQ (0, v2.length ());
354 : : }
355 : :
356 : 4 : {
357 : 4 : vec<int> v1 = vec<int>();
358 : 4 : ASSERT_EQ (0, v1.length ());
359 : :
360 : 4 : vec<int> v2 = v1;
361 : 4 : ASSERT_EQ (0, v2.length ());
362 : : }
363 : :
364 : 4 : {
365 : 4 : vec<int> v1 (vNULL);
366 : 4 : ASSERT_EQ (0, v1.length ());
367 : 4 : v1.safe_push (1);
368 : :
369 : 4 : vec<int> v2 (v1);
370 : 4 : ASSERT_EQ (1, v1.length ());
371 : 4 : v2.safe_push (1);
372 : :
373 : 4 : ASSERT_EQ (2, v1.length ());
374 : 4 : ASSERT_EQ (2, v2.length ());
375 : 4 : v1.release ();
376 : : }
377 : 4 : }
378 : :
379 : : /* Verify that vec::quick_push works correctly. */
380 : :
381 : : static void
382 : 4 : test_quick_push ()
383 : : {
384 : 4 : auto_vec <int> v;
385 : 4 : ASSERT_EQ (0, v.length ());
386 : 4 : v.reserve (3);
387 : 4 : ASSERT_EQ (0, v.length ());
388 : 4 : ASSERT_TRUE (v.space (3));
389 : 4 : v.quick_push (5);
390 : 4 : v.quick_push (6);
391 : 4 : v.quick_push (7);
392 : 4 : ASSERT_EQ (3, v.length ());
393 : 4 : ASSERT_EQ (5, v[0]);
394 : 4 : ASSERT_EQ (6, v[1]);
395 : 4 : ASSERT_EQ (7, v[2]);
396 : 4 : }
397 : :
398 : : /* Verify that vec::safe_push works correctly. */
399 : :
400 : : static void
401 : 4 : test_safe_push ()
402 : : {
403 : 4 : auto_vec <int> v;
404 : 4 : ASSERT_EQ (0, v.length ());
405 : 4 : v.safe_push (5);
406 : 4 : v.safe_push (6);
407 : 4 : v.safe_push (7);
408 : 4 : ASSERT_EQ (3, v.length ());
409 : 4 : ASSERT_EQ (5, v[0]);
410 : 4 : ASSERT_EQ (6, v[1]);
411 : 4 : ASSERT_EQ (7, v[2]);
412 : 4 : }
413 : :
414 : : /* Verify that vec::truncate works correctly. */
415 : :
416 : : static void
417 : 4 : test_truncate ()
418 : : {
419 : 4 : auto_vec <int> v;
420 : 4 : ASSERT_EQ (0, v.length ());
421 : 4 : safe_push_range (v, 0, 10);
422 : 4 : ASSERT_EQ (10, v.length ());
423 : :
424 : 4 : v.truncate (5);
425 : 4 : ASSERT_EQ (5, v.length ());
426 : 4 : }
427 : :
428 : : /* Verify that vec::safe_grow_cleared works correctly. */
429 : :
430 : : static void
431 : 4 : test_safe_grow_cleared ()
432 : : {
433 : 4 : auto_vec <int> v;
434 : 4 : ASSERT_EQ (0, v.length ());
435 : 4 : v.safe_grow_cleared (50, true);
436 : 4 : ASSERT_EQ (50, v.length ());
437 : 4 : ASSERT_EQ (0, v[0]);
438 : 4 : ASSERT_EQ (0, v[49]);
439 : 4 : }
440 : :
441 : : /* Verify that vec::pop works correctly. */
442 : :
443 : : static void
444 : 4 : test_pop ()
445 : : {
446 : 4 : auto_vec <int> v;
447 : 4 : safe_push_range (v, 5, 20);
448 : 4 : ASSERT_EQ (15, v.length ());
449 : :
450 : 4 : int last = v.pop ();
451 : 4 : ASSERT_EQ (19, last);
452 : 4 : ASSERT_EQ (14, v.length ());
453 : 4 : }
454 : :
455 : : /* Verify that vec::safe_insert works correctly. */
456 : :
457 : : static void
458 : 4 : test_safe_insert ()
459 : : {
460 : 4 : auto_vec <int> v;
461 : 4 : safe_push_range (v, 0, 10);
462 : 4 : v.safe_insert (5, 42);
463 : 4 : ASSERT_EQ (4, v[4]);
464 : 4 : ASSERT_EQ (42, v[5]);
465 : 4 : ASSERT_EQ (5, v[6]);
466 : 4 : ASSERT_EQ (11, v.length ());
467 : 4 : }
468 : :
469 : : /* Verify that vec::ordered_remove works correctly. */
470 : :
471 : : static void
472 : 4 : test_ordered_remove ()
473 : : {
474 : 4 : auto_vec <int> v;
475 : 4 : safe_push_range (v, 0, 10);
476 : 4 : v.ordered_remove (5);
477 : 4 : ASSERT_EQ (4, v[4]);
478 : 4 : ASSERT_EQ (6, v[5]);
479 : 4 : ASSERT_EQ (9, v.length ());
480 : 4 : }
481 : :
482 : : /* Verify that vec::ordered_remove_if works correctly. */
483 : :
484 : : static void
485 : 4 : test_ordered_remove_if (void)
486 : : {
487 : 4 : auto_vec <int> v;
488 : 4 : safe_push_range (v, 0, 10);
489 : 4 : unsigned ix, ix2;
490 : 4 : int *elem_ptr;
491 : 44 : VEC_ORDERED_REMOVE_IF (v, ix, ix2, elem_ptr,
492 : 4 : *elem_ptr == 5 || *elem_ptr == 7);
493 : 4 : ASSERT_EQ (4, v[4]);
494 : 4 : ASSERT_EQ (6, v[5]);
495 : 4 : ASSERT_EQ (8, v[6]);
496 : 4 : ASSERT_EQ (8, v.length ());
497 : :
498 : 4 : v.truncate (0);
499 : 4 : safe_push_range (v, 0, 10);
500 : 28 : VEC_ORDERED_REMOVE_IF_FROM_TO (v, ix, ix2, elem_ptr, 0, 6,
501 : 4 : *elem_ptr == 5 || *elem_ptr == 7);
502 : 4 : ASSERT_EQ (4, v[4]);
503 : 4 : ASSERT_EQ (6, v[5]);
504 : 4 : ASSERT_EQ (7, v[6]);
505 : 4 : ASSERT_EQ (9, v.length ());
506 : :
507 : 4 : v.truncate (0);
508 : 4 : safe_push_range (v, 0, 10);
509 : 24 : VEC_ORDERED_REMOVE_IF_FROM_TO (v, ix, ix2, elem_ptr, 0, 5,
510 : 4 : *elem_ptr == 5 || *elem_ptr == 7);
511 : 12 : VEC_ORDERED_REMOVE_IF_FROM_TO (v, ix, ix2, elem_ptr, 8, 10,
512 : 4 : *elem_ptr == 5 || *elem_ptr == 7);
513 : 4 : ASSERT_EQ (4, v[4]);
514 : 4 : ASSERT_EQ (5, v[5]);
515 : 4 : ASSERT_EQ (6, v[6]);
516 : 4 : ASSERT_EQ (10, v.length ());
517 : :
518 : 4 : v.truncate (0);
519 : 4 : safe_push_range (v, 0, 10);
520 : 44 : VEC_ORDERED_REMOVE_IF (v, ix, ix2, elem_ptr, *elem_ptr == 5);
521 : 4 : ASSERT_EQ (4, v[4]);
522 : 4 : ASSERT_EQ (6, v[5]);
523 : 4 : ASSERT_EQ (7, v[6]);
524 : 4 : ASSERT_EQ (9, v.length ());
525 : 4 : }
526 : :
527 : : /* Verify that vec::unordered_remove works correctly. */
528 : :
529 : : static void
530 : 4 : test_unordered_remove ()
531 : : {
532 : 4 : auto_vec <int> v;
533 : 4 : safe_push_range (v, 0, 10);
534 : 4 : v.unordered_remove (5);
535 : 4 : ASSERT_EQ (9, v.length ());
536 : 4 : }
537 : :
538 : : /* Verify that vec::block_remove works correctly. */
539 : :
540 : : static void
541 : 4 : test_block_remove ()
542 : : {
543 : 4 : auto_vec <int> v;
544 : 4 : safe_push_range (v, 0, 10);
545 : 4 : v.block_remove (5, 3);
546 : 4 : ASSERT_EQ (3, v[3]);
547 : 4 : ASSERT_EQ (4, v[4]);
548 : 4 : ASSERT_EQ (8, v[5]);
549 : 4 : ASSERT_EQ (9, v[6]);
550 : 4 : ASSERT_EQ (7, v.length ());
551 : 4 : }
552 : :
553 : : /* Comparator for use by test_qsort. */
554 : :
555 : : static int
556 : 492 : reverse_cmp (const void *p_i, const void *p_j)
557 : : {
558 : 492 : return *(const int *)p_j - *(const int *)p_i;
559 : : }
560 : :
561 : : /* Verify that vec::qsort works correctly. */
562 : :
563 : : static void
564 : 4 : test_qsort ()
565 : : {
566 : 4 : auto_vec <int> v;
567 : 4 : safe_push_range (v, 0, 10);
568 : 4 : v.qsort (reverse_cmp);
569 : 4 : ASSERT_EQ (9, v[0]);
570 : 4 : ASSERT_EQ (8, v[1]);
571 : 4 : ASSERT_EQ (1, v[8]);
572 : 4 : ASSERT_EQ (0, v[9]);
573 : 4 : ASSERT_EQ (10, v.length ());
574 : 4 : }
575 : :
576 : : /* Verify that vec::reverse works correctly. */
577 : :
578 : : static void
579 : 4 : test_reverse ()
580 : : {
581 : : /* Reversing an empty vec ought to be a no-op. */
582 : 4 : {
583 : 4 : auto_vec <int> v;
584 : 4 : ASSERT_EQ (0, v.length ());
585 : 4 : v.reverse ();
586 : 4 : ASSERT_EQ (0, v.length ());
587 : 4 : }
588 : :
589 : : /* Verify reversing a vec with even length. */
590 : 4 : {
591 : 4 : auto_vec <int> v;
592 : 4 : safe_push_range (v, 0, 4);
593 : 4 : v.reverse ();
594 : 4 : ASSERT_EQ (3, v[0]);
595 : 4 : ASSERT_EQ (2, v[1]);
596 : 4 : ASSERT_EQ (1, v[2]);
597 : 4 : ASSERT_EQ (0, v[3]);
598 : 4 : ASSERT_EQ (4, v.length ());
599 : 4 : }
600 : :
601 : : /* Verify reversing a vec with odd length. */
602 : 4 : {
603 : 4 : auto_vec <int> v;
604 : 4 : safe_push_range (v, 0, 3);
605 : 4 : v.reverse ();
606 : 4 : ASSERT_EQ (2, v[0]);
607 : 4 : ASSERT_EQ (1, v[1]);
608 : 4 : ASSERT_EQ (0, v[2]);
609 : 4 : ASSERT_EQ (3, v.length ());
610 : 4 : }
611 : 4 : }
612 : :
613 : : /* A test class that increments a counter every time its dtor is called. */
614 : :
615 : : class count_dtor
616 : : {
617 : : public:
618 : 8 : count_dtor (int *counter) : m_counter (counter) {}
619 : 8 : ~count_dtor () { (*m_counter)++; }
620 : :
621 : : private:
622 : : int *m_counter;
623 : : };
624 : :
625 : : /* Verify that auto_delete_vec deletes the elements within it. */
626 : :
627 : : static void
628 : 4 : test_auto_delete_vec ()
629 : : {
630 : 4 : int dtor_count = 0;
631 : 4 : {
632 : 4 : auto_delete_vec <count_dtor> v;
633 : 4 : v.safe_push (new count_dtor (&dtor_count));
634 : 4 : v.safe_push (new count_dtor (&dtor_count));
635 : 4 : }
636 : 4 : ASSERT_EQ (dtor_count, 2);
637 : 4 : }
638 : :
639 : : /* Verify accesses to vector elements are done indirectly. */
640 : :
641 : : static void
642 : 4 : test_auto_alias ()
643 : : {
644 : 4 : volatile int i = 1;
645 : 4 : auto_vec<int, 8> v;
646 : 4 : v.quick_grow (2);
647 : 4 : v[0] = 1;
648 : 4 : v[1] = 2;
649 : 4 : int val;
650 : 8 : for (int ix = i; v.iterate (ix, &val); ix++)
651 : 4 : ASSERT_EQ (val, 2);
652 : 4 : ASSERT_EQ (val, 0);
653 : 4 : }
654 : :
655 : : static void
656 : 4 : test_string_slice_initializers ()
657 : : {
658 : 4 : string_slice str1 = string_slice ();
659 : 4 : ASSERT_TRUE (str1.is_valid ());
660 : 4 : ASSERT_EQ (str1.size (), 0);
661 : :
662 : 4 : string_slice str2 = string_slice ("Test string");
663 : 4 : ASSERT_TRUE (str2.is_valid ());
664 : 4 : ASSERT_EQ (str2.size (), 11);
665 : :
666 : 4 : string_slice str3 = "Test string the second";
667 : 4 : ASSERT_TRUE (str3.is_valid ());
668 : 4 : ASSERT_EQ (str3.size (), 22);
669 : :
670 : 4 : string_slice str4 = string_slice ("Test string", 4);
671 : 4 : ASSERT_TRUE (str4.is_valid ());
672 : 4 : ASSERT_EQ (str4.size (), 4);
673 : 4 : }
674 : :
675 : : static void
676 : 4 : test_string_slice_tokenize ()
677 : : {
678 : 4 : string_slice test_string_slice = "";
679 : 4 : string_slice test_delims = ",";
680 : :
681 : 4 : ASSERT_EQ (string_slice::tokenize (&test_string_slice, test_delims), "");
682 : 8 : ASSERT_FALSE (test_string_slice.is_valid ());
683 : :
684 : 4 : test_string_slice = ",";
685 : 4 : test_delims = ",";
686 : 4 : ASSERT_EQ (string_slice::tokenize (&test_string_slice, test_delims),
687 : : string_slice (""));
688 : 4 : ASSERT_EQ (string_slice::tokenize (&test_string_slice, test_delims),
689 : : string_slice (""));
690 : 8 : ASSERT_FALSE (test_string_slice.is_valid ());
691 : :
692 : 4 : test_string_slice = ",test.,.test, , test ";
693 : 4 : test_delims = ",.";
694 : 4 : ASSERT_EQ (string_slice::tokenize (&test_string_slice, test_delims), "");
695 : 4 : ASSERT_EQ (string_slice::tokenize (&test_string_slice, test_delims), "test");
696 : 4 : ASSERT_EQ (string_slice::tokenize (&test_string_slice, test_delims), "");
697 : 4 : ASSERT_EQ (string_slice::tokenize (&test_string_slice, test_delims), "");
698 : 4 : ASSERT_EQ (string_slice::tokenize (&test_string_slice, test_delims), "test");
699 : 4 : ASSERT_EQ (string_slice::tokenize (&test_string_slice, test_delims), " ");
700 : 4 : ASSERT_EQ (string_slice::tokenize (&test_string_slice, test_delims),
701 : : " test ");
702 : 8 : ASSERT_FALSE (test_string_slice.is_valid ());
703 : :
704 : 4 : const char *test_string
705 : : = "This is the test string, it \0 is for testing, 123 ,,";
706 : 4 : test_string_slice = string_slice (test_string, 52);
707 : 4 : test_delims = string_slice (",\0", 2);
708 : :
709 : 4 : ASSERT_EQ (string_slice::tokenize (&test_string_slice, test_delims),
710 : : "This is the test string");
711 : 4 : ASSERT_EQ (string_slice::tokenize (&test_string_slice, test_delims),
712 : : " it ");
713 : 4 : ASSERT_EQ (string_slice::tokenize (&test_string_slice, test_delims),
714 : : " is for testing");
715 : 4 : ASSERT_EQ (string_slice::tokenize (&test_string_slice, test_delims),
716 : : " 123 ");
717 : 4 : ASSERT_EQ (string_slice::tokenize (&test_string_slice, test_delims),
718 : : "");
719 : 4 : ASSERT_EQ (string_slice::tokenize (&test_string_slice, test_delims),
720 : : "");
721 : 8 : ASSERT_FALSE (test_string_slice.is_valid ());
722 : 4 : }
723 : :
724 : : static void
725 : 4 : test_string_slice_strcmp ()
726 : : {
727 : 4 : ASSERT_EQ (string_slice::strcmp (string_slice (),
728 : : string_slice ()), 0);
729 : 4 : ASSERT_EQ (string_slice::strcmp (string_slice ("test"),
730 : : string_slice ()), 1);
731 : 4 : ASSERT_EQ (string_slice::strcmp (string_slice (),
732 : : string_slice ("test")), -1);
733 : 4 : ASSERT_EQ (string_slice::strcmp (string_slice ("test"),
734 : : string_slice ("test")), 0);
735 : 4 : ASSERT_EQ (string_slice::strcmp (string_slice ("a"),
736 : : string_slice ("b")), -1);
737 : 4 : ASSERT_EQ (string_slice::strcmp (string_slice ("b"),
738 : : string_slice ("a")), 1);
739 : 4 : ASSERT_EQ (string_slice::strcmp (string_slice ("ab", 1),
740 : : string_slice ("a")), 0);
741 : 4 : ASSERT_EQ (string_slice::strcmp (string_slice ("ab", 2),
742 : : string_slice ("a")), 1);
743 : 4 : }
744 : :
745 : : static void
746 : 4 : test_string_slice_equality ()
747 : : {
748 : 4 : ASSERT_TRUE (string_slice () == string_slice ());
749 : 4 : ASSERT_FALSE (string_slice ("test") == string_slice ());
750 : 4 : ASSERT_FALSE ("test" == string_slice ());
751 : 4 : ASSERT_FALSE (string_slice () == string_slice ("test"));
752 : 4 : ASSERT_FALSE (string_slice () == "test");
753 : 4 : ASSERT_TRUE (string_slice ("test") == string_slice ("test"));
754 : 4 : ASSERT_TRUE ("test" == string_slice ("test"));
755 : 4 : ASSERT_TRUE (string_slice ("test") == "test");
756 : 4 : ASSERT_FALSE (string_slice ("a") == string_slice ("b"));
757 : 4 : ASSERT_FALSE ("a" == string_slice ("b"));
758 : 4 : ASSERT_FALSE (string_slice ("a") == "b");
759 : 4 : ASSERT_FALSE (string_slice ("b") == string_slice ("a"));
760 : 4 : ASSERT_TRUE (string_slice ("ab", 1) == string_slice ("a"));
761 : 4 : ASSERT_TRUE (string_slice ("ab", 1) == "a");
762 : 4 : ASSERT_FALSE (string_slice ("ab", 2) == string_slice ("a"));
763 : 4 : ASSERT_FALSE (string_slice ("ab", 2) == "a");
764 : 4 : }
765 : :
766 : : static void
767 : 4 : test_string_slice_inequality ()
768 : : {
769 : 4 : ASSERT_FALSE (string_slice () != string_slice ());
770 : 4 : ASSERT_TRUE (string_slice ("test") != string_slice ());
771 : 4 : ASSERT_TRUE ("test" != string_slice ());
772 : 4 : ASSERT_TRUE (string_slice () != string_slice ("test"));
773 : 4 : ASSERT_TRUE (string_slice () != "test");
774 : 4 : ASSERT_FALSE (string_slice ("test") != string_slice ("test"));
775 : 4 : ASSERT_FALSE ("test" != string_slice ("test"));
776 : 4 : ASSERT_FALSE (string_slice ("test") != "test");
777 : 4 : ASSERT_TRUE (string_slice ("a") != string_slice ("b"));
778 : 4 : ASSERT_TRUE ("a" != string_slice ("b"));
779 : 4 : ASSERT_TRUE (string_slice ("a") != "b");
780 : 4 : ASSERT_TRUE (string_slice ("b") != string_slice ("a"));
781 : 4 : ASSERT_FALSE (string_slice ("ab", 1) != string_slice ("a"));
782 : 4 : ASSERT_FALSE (string_slice ("ab", 1) != "a");
783 : 4 : ASSERT_TRUE (string_slice ("ab", 2) != string_slice ("a"));
784 : 4 : ASSERT_TRUE (string_slice ("ab", 2) != "a");
785 : 4 : }
786 : :
787 : : static void
788 : 4 : test_string_slice_invalid ()
789 : : {
790 : 4 : ASSERT_FALSE (string_slice::invalid ().is_valid ());
791 : 4 : ASSERT_FALSE (string_slice (NULL, 1).is_valid ());
792 : 4 : ASSERT_TRUE (string_slice (NULL, (size_t) 0).is_valid ());
793 : 4 : ASSERT_TRUE (string_slice ("Test", (size_t) 0).is_valid ());
794 : 4 : ASSERT_TRUE (string_slice ().is_valid ());
795 : 4 : }
796 : :
797 : : static void
798 : 4 : test_string_slice_strip ()
799 : : {
800 : 4 : ASSERT_EQ (string_slice (" test ").strip (), string_slice ("test"));
801 : 4 : ASSERT_EQ (string_slice ("\t test string\t \n ").strip (),
802 : : string_slice ("test string"));
803 : 4 : ASSERT_EQ (string_slice ("test").strip (), string_slice ("test"));
804 : 4 : ASSERT_EQ (string_slice ().strip (), string_slice ());
805 : 4 : ASSERT_EQ (string_slice ("\t \n \t ").strip (), string_slice ());
806 : 4 : }
807 : :
808 : : /* Run all of the selftests within this file. */
809 : :
810 : : void
811 : 4 : vec_cc_tests ()
812 : : {
813 : 4 : test_init ();
814 : 4 : test_quick_push ();
815 : 4 : test_safe_push ();
816 : 4 : test_truncate ();
817 : 4 : test_safe_grow_cleared ();
818 : 4 : test_pop ();
819 : 4 : test_safe_insert ();
820 : 4 : test_ordered_remove ();
821 : 4 : test_ordered_remove_if ();
822 : 4 : test_unordered_remove ();
823 : 4 : test_block_remove ();
824 : 4 : test_qsort ();
825 : 4 : test_reverse ();
826 : 4 : test_auto_delete_vec ();
827 : 4 : test_auto_alias ();
828 : 4 : test_string_slice_initializers ();
829 : 4 : test_string_slice_tokenize ();
830 : 4 : test_string_slice_strcmp ();
831 : 4 : test_string_slice_equality ();
832 : 4 : test_string_slice_inequality ();
833 : 4 : test_string_slice_invalid ();
834 : 4 : test_string_slice_strip ();
835 : 4 : }
836 : :
837 : : } // namespace selftest
838 : :
839 : : #endif /* #if CHECKING_P */
840 : : #endif /* #ifndef GENERATOR_FILE */
|
