annotate gcc/vec.c @ 16:04ced10e8804

gcc 7
author kono
date Fri, 27 Oct 2017 22:46:09 +0900
parents f6334be47118
children 84e7813d76e9
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1 /* Vector API for GNU compiler.
16
kono
parents: 14
diff changeset
2 Copyright (C) 2004-2017 Free Software Foundation, Inc.
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
3 Contributed by Nathan Sidwell <nathan@codesourcery.com>
16
kono
parents: 14
diff changeset
4 Re-implemented in C++ by Diego Novillo <dnovillo@google.com>
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
5
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
6 This file is part of GCC.
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
7
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
8 GCC is free software; you can redistribute it and/or modify it under
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
9 the terms of the GNU General Public License as published by the Free
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
10 Software Foundation; either version 3, or (at your option) any later
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
11 version.
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
12
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
16 for more details.
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
17
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
18 You should have received a copy of the GNU General Public License
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
19 along with GCC; see the file COPYING3. If not see
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
20 <http://www.gnu.org/licenses/>. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
21
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
22 /* This file is compiled twice: once for the generator programs
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
23 once for the compiler. */
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
24 #ifdef GENERATOR_FILE
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
25 #include "bconfig.h"
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
26 #else
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
27 #include "config.h"
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
28 #endif
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
29
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
30 #include "system.h"
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
31 #include "coretypes.h"
16
kono
parents: 14
diff changeset
32 #include "hash-table.h"
kono
parents: 14
diff changeset
33 #include "selftest.h"
kono
parents: 14
diff changeset
34 #ifdef GENERATOR_FILE
kono
parents: 14
diff changeset
35 #include "errors.h"
kono
parents: 14
diff changeset
36 #else
kono
parents: 14
diff changeset
37 #include "input.h"
14
f6334be47118 update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
38 #include "diagnostic-core.h"
16
kono
parents: 14
diff changeset
39 #endif
kono
parents: 14
diff changeset
40
kono
parents: 14
diff changeset
41 /* vNULL is an empty type with a template cast operation that returns
kono
parents: 14
diff changeset
42 a zero-initialized vec<T, A, L> instance. Use this when you want
kono
parents: 14
diff changeset
43 to assign nil values to new vec instances or pass a nil vector as
kono
parents: 14
diff changeset
44 a function call argument.
kono
parents: 14
diff changeset
45
kono
parents: 14
diff changeset
46 We use this technique because vec<T, A, L> must be PODs (they are
kono
parents: 14
diff changeset
47 stored in unions and passed in vararg functions), this means that
kono
parents: 14
diff changeset
48 they cannot have ctors/dtors. */
kono
parents: 14
diff changeset
49 vnull vNULL;
kono
parents: 14
diff changeset
50
kono
parents: 14
diff changeset
51 /* Vector memory usage. */
kono
parents: 14
diff changeset
52 struct vec_usage: public mem_usage
kono
parents: 14
diff changeset
53 {
kono
parents: 14
diff changeset
54 /* Default constructor. */
kono
parents: 14
diff changeset
55 vec_usage (): m_items (0), m_items_peak (0) {}
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
56
16
kono
parents: 14
diff changeset
57 /* Constructor. */
kono
parents: 14
diff changeset
58 vec_usage (size_t allocated, size_t times, size_t peak,
kono
parents: 14
diff changeset
59 size_t items, size_t items_peak)
kono
parents: 14
diff changeset
60 : mem_usage (allocated, times, peak),
kono
parents: 14
diff changeset
61 m_items (items), m_items_peak (items_peak) {}
kono
parents: 14
diff changeset
62
kono
parents: 14
diff changeset
63 /* Comparison operator. */
kono
parents: 14
diff changeset
64 inline bool
kono
parents: 14
diff changeset
65 operator< (const vec_usage &second) const
kono
parents: 14
diff changeset
66 {
kono
parents: 14
diff changeset
67 return (m_allocated == second.m_allocated ?
kono
parents: 14
diff changeset
68 (m_peak == second.m_peak ? m_times < second.m_times
kono
parents: 14
diff changeset
69 : m_peak < second.m_peak) : m_allocated < second.m_allocated);
kono
parents: 14
diff changeset
70 }
kono
parents: 14
diff changeset
71
kono
parents: 14
diff changeset
72 /* Sum the usage with SECOND usage. */
kono
parents: 14
diff changeset
73 vec_usage
kono
parents: 14
diff changeset
74 operator+ (const vec_usage &second)
kono
parents: 14
diff changeset
75 {
kono
parents: 14
diff changeset
76 return vec_usage (m_allocated + second.m_allocated,
kono
parents: 14
diff changeset
77 m_times + second.m_times,
kono
parents: 14
diff changeset
78 m_peak + second.m_peak,
kono
parents: 14
diff changeset
79 m_items + second.m_items,
kono
parents: 14
diff changeset
80 m_items_peak + second.m_items_peak);
kono
parents: 14
diff changeset
81 }
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
82
16
kono
parents: 14
diff changeset
83 /* Dump usage coupled to LOC location, where TOTAL is sum of all rows. */
kono
parents: 14
diff changeset
84 inline void
kono
parents: 14
diff changeset
85 dump (mem_location *loc, mem_usage &total) const
kono
parents: 14
diff changeset
86 {
kono
parents: 14
diff changeset
87 char s[4096];
kono
parents: 14
diff changeset
88 sprintf (s, "%s:%i (%s)", loc->get_trimmed_filename (),
kono
parents: 14
diff changeset
89 loc->m_line, loc->m_function);
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
90
16
kono
parents: 14
diff changeset
91 s[48] = '\0';
kono
parents: 14
diff changeset
92
kono
parents: 14
diff changeset
93 fprintf (stderr, "%-48s %10li:%4.1f%%%10li%10li:%4.1f%%%11li%11li\n", s,
kono
parents: 14
diff changeset
94 (long)m_allocated, m_allocated * 100.0 / total.m_allocated,
kono
parents: 14
diff changeset
95 (long)m_peak, (long)m_times, m_times * 100.0 / total.m_times,
kono
parents: 14
diff changeset
96 (long)m_items, (long)m_items_peak);
kono
parents: 14
diff changeset
97 }
kono
parents: 14
diff changeset
98
kono
parents: 14
diff changeset
99 /* Dump footer. */
kono
parents: 14
diff changeset
100 inline void
kono
parents: 14
diff changeset
101 dump_footer ()
kono
parents: 14
diff changeset
102 {
kono
parents: 14
diff changeset
103 print_dash_line ();
kono
parents: 14
diff changeset
104 fprintf (stderr, "%s%55li%25li%17li\n", "Total", (long)m_allocated,
kono
parents: 14
diff changeset
105 (long)m_times, (long)m_items);
kono
parents: 14
diff changeset
106 print_dash_line ();
kono
parents: 14
diff changeset
107 }
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
108
16
kono
parents: 14
diff changeset
109 /* Dump header with NAME. */
kono
parents: 14
diff changeset
110 static inline void
kono
parents: 14
diff changeset
111 dump_header (const char *name)
kono
parents: 14
diff changeset
112 {
kono
parents: 14
diff changeset
113 fprintf (stderr, "%-48s %11s%15s%10s%17s%11s\n", name, "Leak", "Peak",
kono
parents: 14
diff changeset
114 "Times", "Leak items", "Peak items");
kono
parents: 14
diff changeset
115 print_dash_line ();
kono
parents: 14
diff changeset
116 }
kono
parents: 14
diff changeset
117
kono
parents: 14
diff changeset
118 /* Compare wrapper used by qsort method. */
kono
parents: 14
diff changeset
119 static int
kono
parents: 14
diff changeset
120 compare (const void *first, const void *second)
kono
parents: 14
diff changeset
121 {
kono
parents: 14
diff changeset
122 typedef std::pair<mem_location *, vec_usage *> mem_pair_t;
kono
parents: 14
diff changeset
123
kono
parents: 14
diff changeset
124 const mem_pair_t f = *(const mem_pair_t *)first;
kono
parents: 14
diff changeset
125 const mem_pair_t s = *(const mem_pair_t *)second;
kono
parents: 14
diff changeset
126
kono
parents: 14
diff changeset
127 return (*f.second) < (*s.second);
kono
parents: 14
diff changeset
128 }
kono
parents: 14
diff changeset
129
kono
parents: 14
diff changeset
130 /* Current number of items allocated. */
kono
parents: 14
diff changeset
131 size_t m_items;
kono
parents: 14
diff changeset
132 /* Peak value of number of allocated items. */
kono
parents: 14
diff changeset
133 size_t m_items_peak;
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
134 };
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
135
16
kono
parents: 14
diff changeset
136 /* Vector memory description. */
kono
parents: 14
diff changeset
137 static mem_alloc_description <vec_usage> vec_mem_desc;
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
138
16
kono
parents: 14
diff changeset
139 /* Account the overhead. */
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
140
16
kono
parents: 14
diff changeset
141 void
kono
parents: 14
diff changeset
142 vec_prefix::register_overhead (void *ptr, size_t size, size_t elements
kono
parents: 14
diff changeset
143 MEM_STAT_DECL)
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
144 {
16
kono
parents: 14
diff changeset
145 vec_mem_desc.register_descriptor (ptr, VEC_ORIGIN, false
kono
parents: 14
diff changeset
146 FINAL_PASS_MEM_STAT);
kono
parents: 14
diff changeset
147 vec_usage *usage = vec_mem_desc.register_instance_overhead (size, ptr);
kono
parents: 14
diff changeset
148 usage->m_items += elements;
kono
parents: 14
diff changeset
149 if (usage->m_items_peak < usage->m_items)
kono
parents: 14
diff changeset
150 usage->m_items_peak = usage->m_items;
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
151 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
152
16
kono
parents: 14
diff changeset
153 /* Notice that the memory allocated for the vector has been freed. */
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
154
16
kono
parents: 14
diff changeset
155 void
kono
parents: 14
diff changeset
156 vec_prefix::release_overhead (void *ptr, size_t size, bool in_dtor
kono
parents: 14
diff changeset
157 MEM_STAT_DECL)
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
158 {
16
kono
parents: 14
diff changeset
159 if (!vec_mem_desc.contains_descriptor_for_instance (ptr))
kono
parents: 14
diff changeset
160 vec_mem_desc.register_descriptor (ptr, VEC_ORIGIN,
kono
parents: 14
diff changeset
161 false FINAL_PASS_MEM_STAT);
kono
parents: 14
diff changeset
162 vec_mem_desc.release_instance_overhead (ptr, size, in_dtor);
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
163 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
164
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
165
16
kono
parents: 14
diff changeset
166 /* Calculate the number of slots to reserve a vector, making sure that
kono
parents: 14
diff changeset
167 it is of at least DESIRED size by growing ALLOC exponentially. */
kono
parents: 14
diff changeset
168
kono
parents: 14
diff changeset
169 unsigned
kono
parents: 14
diff changeset
170 vec_prefix::calculate_allocation_1 (unsigned alloc, unsigned desired)
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
171 {
16
kono
parents: 14
diff changeset
172 /* We must have run out of room. */
kono
parents: 14
diff changeset
173 gcc_assert (alloc < desired);
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
174
16
kono
parents: 14
diff changeset
175 /* Exponential growth. */
kono
parents: 14
diff changeset
176 if (!alloc)
kono
parents: 14
diff changeset
177 alloc = 4;
kono
parents: 14
diff changeset
178 else if (alloc < 16)
kono
parents: 14
diff changeset
179 /* Double when small. */
kono
parents: 14
diff changeset
180 alloc = alloc * 2;
kono
parents: 14
diff changeset
181 else
kono
parents: 14
diff changeset
182 /* Grow slower when large. */
kono
parents: 14
diff changeset
183 alloc = (alloc * 3 / 2);
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
184
16
kono
parents: 14
diff changeset
185 /* If this is still too small, set it to the right size. */
kono
parents: 14
diff changeset
186 if (alloc < desired)
kono
parents: 14
diff changeset
187 alloc = desired;
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
188 return alloc;
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
189 }
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
190
16
kono
parents: 14
diff changeset
191 /* Dump per-site memory statistics. */
9
77e2b8dfacca update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
192
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
193 void
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
194 dump_vec_loc_statistics (void)
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
195 {
16
kono
parents: 14
diff changeset
196 vec_mem_desc.dump (VEC_ORIGIN);
kono
parents: 14
diff changeset
197 }
kono
parents: 14
diff changeset
198
kono
parents: 14
diff changeset
199 #if CHECKING_P
kono
parents: 14
diff changeset
200 /* Report qsort comparator CMP consistency check failure with P1, P2, P3 as
kono
parents: 14
diff changeset
201 witness elements. */
kono
parents: 14
diff changeset
202 ATTRIBUTE_NORETURN ATTRIBUTE_COLD
kono
parents: 14
diff changeset
203 static void
kono
parents: 14
diff changeset
204 qsort_chk_error (const void *p1, const void *p2, const void *p3,
kono
parents: 14
diff changeset
205 int (*cmp) (const void *, const void *))
kono
parents: 14
diff changeset
206 {
kono
parents: 14
diff changeset
207 if (!p3)
kono
parents: 14
diff changeset
208 {
kono
parents: 14
diff changeset
209 int r1 = cmp (p1, p2), r2 = cmp (p2, p1);
kono
parents: 14
diff changeset
210 error ("qsort comparator not anti-commutative: %d, %d", r1, r2);
kono
parents: 14
diff changeset
211 }
kono
parents: 14
diff changeset
212 else if (p1 == p2)
kono
parents: 14
diff changeset
213 {
kono
parents: 14
diff changeset
214 int r = cmp (p1, p3);
kono
parents: 14
diff changeset
215 error ("qsort comparator non-negative on sorted output: %d", r);
kono
parents: 14
diff changeset
216 }
kono
parents: 14
diff changeset
217 else
kono
parents: 14
diff changeset
218 {
kono
parents: 14
diff changeset
219 int r1 = cmp (p1, p2), r2 = cmp (p2, p3), r3 = cmp (p1, p3);
kono
parents: 14
diff changeset
220 error ("qsort comparator not transitive: %d, %d, %d", r1, r2, r3);
kono
parents: 14
diff changeset
221 }
kono
parents: 14
diff changeset
222 internal_error ("qsort checking failed");
kono
parents: 14
diff changeset
223 }
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
224
16
kono
parents: 14
diff changeset
225 /* Wrapper around qsort with checking that CMP is consistent on given input.
kono
parents: 14
diff changeset
226
kono
parents: 14
diff changeset
227 Strictly speaking, passing invalid (non-transitive, non-anti-commutative)
kono
parents: 14
diff changeset
228 comparators to libc qsort can result in undefined behavior. Therefore we
kono
parents: 14
diff changeset
229 should ideally perform consistency checks prior to invoking qsort, but in
kono
parents: 14
diff changeset
230 order to do that optimally we'd need to sort the array ourselves beforehand
kono
parents: 14
diff changeset
231 with a sorting routine known to be "safe". Instead, we expect that most
kono
parents: 14
diff changeset
232 implementations in practice will still produce some permutation of input
kono
parents: 14
diff changeset
233 array even for invalid comparators, which enables us to perform checks on
kono
parents: 14
diff changeset
234 the output array. */
kono
parents: 14
diff changeset
235 void
kono
parents: 14
diff changeset
236 qsort_chk (void *base, size_t n, size_t size,
kono
parents: 14
diff changeset
237 int (*cmp)(const void *, const void *))
kono
parents: 14
diff changeset
238 {
kono
parents: 14
diff changeset
239 (qsort) (base, n, size, cmp);
kono
parents: 14
diff changeset
240 #if 0
kono
parents: 14
diff changeset
241 #define LIM(n) (n)
kono
parents: 14
diff changeset
242 #else
kono
parents: 14
diff changeset
243 /* Limit overall time complexity to O(n log n). */
kono
parents: 14
diff changeset
244 #define LIM(n) ((n) <= 16 ? (n) : 12 + floor_log2 (n))
kono
parents: 14
diff changeset
245 #endif
kono
parents: 14
diff changeset
246 #define ELT(i) ((const char *) base + (i) * size)
kono
parents: 14
diff changeset
247 #define CMP(i, j) cmp (ELT (i), ELT (j))
kono
parents: 14
diff changeset
248 #define ERR2(i, j) qsort_chk_error (ELT (i), ELT (j), NULL, cmp)
kono
parents: 14
diff changeset
249 #define ERR3(i, j, k) qsort_chk_error (ELT (i), ELT (j), ELT (k), cmp)
kono
parents: 14
diff changeset
250 size_t i1, i2, i, j;
kono
parents: 14
diff changeset
251 /* This outer loop iterates over maximum spans [i1, i2) such that
kono
parents: 14
diff changeset
252 elements within each span compare equal to each other. */
kono
parents: 14
diff changeset
253 for (i1 = 0; i1 < n; i1 = i2)
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
254 {
16
kono
parents: 14
diff changeset
255 /* Position i2 one past last element that compares equal to i1'th. */
kono
parents: 14
diff changeset
256 for (i2 = i1 + 1; i2 < n; i2++)
kono
parents: 14
diff changeset
257 if (CMP (i1, i2))
kono
parents: 14
diff changeset
258 break;
kono
parents: 14
diff changeset
259 else if (CMP (i2, i1))
kono
parents: 14
diff changeset
260 return ERR2 (i1, i2);
kono
parents: 14
diff changeset
261 size_t lim1 = LIM (i2 - i1), lim2 = LIM (n - i2);
kono
parents: 14
diff changeset
262 /* Verify that other pairs within current span compare equal. */
kono
parents: 14
diff changeset
263 for (i = i1 + 1; i + 1 < i2; i++)
kono
parents: 14
diff changeset
264 for (j = i + 1; j < i1 + lim1; j++)
kono
parents: 14
diff changeset
265 if (CMP (i, j))
kono
parents: 14
diff changeset
266 return ERR3 (i, i1, j);
kono
parents: 14
diff changeset
267 else if (CMP (j, i))
kono
parents: 14
diff changeset
268 return ERR2 (i, j);
kono
parents: 14
diff changeset
269 /* Verify that elements within this span compare less than
kono
parents: 14
diff changeset
270 elements beyond the span. */
kono
parents: 14
diff changeset
271 for (i = i1; i < i2; i++)
kono
parents: 14
diff changeset
272 for (j = i2; j < i2 + lim2; j++)
kono
parents: 14
diff changeset
273 if (CMP (i, j) >= 0)
kono
parents: 14
diff changeset
274 return ERR3 (i, i1, j);
kono
parents: 14
diff changeset
275 else if (CMP (j, i) <= 0)
kono
parents: 14
diff changeset
276 return ERR2 (i, j);
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
277 }
16
kono
parents: 14
diff changeset
278 #undef ERR3
kono
parents: 14
diff changeset
279 #undef ERR2
kono
parents: 14
diff changeset
280 #undef CMP
kono
parents: 14
diff changeset
281 #undef ELT
kono
parents: 14
diff changeset
282 #undef LIM
kono
parents: 14
diff changeset
283 }
kono
parents: 14
diff changeset
284 #endif /* #if CHECKING_P */
kono
parents: 14
diff changeset
285
kono
parents: 14
diff changeset
286 #ifndef GENERATOR_FILE
kono
parents: 14
diff changeset
287 #if CHECKING_P
kono
parents: 14
diff changeset
288
kono
parents: 14
diff changeset
289 namespace selftest {
kono
parents: 14
diff changeset
290
kono
parents: 14
diff changeset
291 /* Selftests. */
kono
parents: 14
diff changeset
292
kono
parents: 14
diff changeset
293 /* Call V.safe_push for all ints from START up to, but not including LIMIT.
kono
parents: 14
diff changeset
294 Helper function for selftests. */
kono
parents: 14
diff changeset
295
kono
parents: 14
diff changeset
296 static void
kono
parents: 14
diff changeset
297 safe_push_range (vec <int>&v, int start, int limit)
kono
parents: 14
diff changeset
298 {
kono
parents: 14
diff changeset
299 for (int i = start; i < limit; i++)
kono
parents: 14
diff changeset
300 v.safe_push (i);
kono
parents: 14
diff changeset
301 }
kono
parents: 14
diff changeset
302
kono
parents: 14
diff changeset
303 /* Verify that vec::quick_push works correctly. */
kono
parents: 14
diff changeset
304
kono
parents: 14
diff changeset
305 static void
kono
parents: 14
diff changeset
306 test_quick_push ()
kono
parents: 14
diff changeset
307 {
kono
parents: 14
diff changeset
308 auto_vec <int> v;
kono
parents: 14
diff changeset
309 ASSERT_EQ (0, v.length ());
kono
parents: 14
diff changeset
310 v.reserve (3);
kono
parents: 14
diff changeset
311 ASSERT_EQ (0, v.length ());
kono
parents: 14
diff changeset
312 ASSERT_TRUE (v.space (3));
kono
parents: 14
diff changeset
313 v.quick_push (5);
kono
parents: 14
diff changeset
314 v.quick_push (6);
kono
parents: 14
diff changeset
315 v.quick_push (7);
kono
parents: 14
diff changeset
316 ASSERT_EQ (3, v.length ());
kono
parents: 14
diff changeset
317 ASSERT_EQ (5, v[0]);
kono
parents: 14
diff changeset
318 ASSERT_EQ (6, v[1]);
kono
parents: 14
diff changeset
319 ASSERT_EQ (7, v[2]);
kono
parents: 14
diff changeset
320 }
kono
parents: 14
diff changeset
321
kono
parents: 14
diff changeset
322 /* Verify that vec::safe_push works correctly. */
kono
parents: 14
diff changeset
323
kono
parents: 14
diff changeset
324 static void
kono
parents: 14
diff changeset
325 test_safe_push ()
kono
parents: 14
diff changeset
326 {
kono
parents: 14
diff changeset
327 auto_vec <int> v;
kono
parents: 14
diff changeset
328 ASSERT_EQ (0, v.length ());
kono
parents: 14
diff changeset
329 v.safe_push (5);
kono
parents: 14
diff changeset
330 v.safe_push (6);
kono
parents: 14
diff changeset
331 v.safe_push (7);
kono
parents: 14
diff changeset
332 ASSERT_EQ (3, v.length ());
kono
parents: 14
diff changeset
333 ASSERT_EQ (5, v[0]);
kono
parents: 14
diff changeset
334 ASSERT_EQ (6, v[1]);
kono
parents: 14
diff changeset
335 ASSERT_EQ (7, v[2]);
kono
parents: 14
diff changeset
336 }
kono
parents: 14
diff changeset
337
kono
parents: 14
diff changeset
338 /* Verify that vec::truncate works correctly. */
kono
parents: 14
diff changeset
339
kono
parents: 14
diff changeset
340 static void
kono
parents: 14
diff changeset
341 test_truncate ()
kono
parents: 14
diff changeset
342 {
kono
parents: 14
diff changeset
343 auto_vec <int> v;
kono
parents: 14
diff changeset
344 ASSERT_EQ (0, v.length ());
kono
parents: 14
diff changeset
345 safe_push_range (v, 0, 10);
kono
parents: 14
diff changeset
346 ASSERT_EQ (10, v.length ());
kono
parents: 14
diff changeset
347
kono
parents: 14
diff changeset
348 v.truncate (5);
kono
parents: 14
diff changeset
349 ASSERT_EQ (5, v.length ());
kono
parents: 14
diff changeset
350 }
kono
parents: 14
diff changeset
351
kono
parents: 14
diff changeset
352 /* Verify that vec::safe_grow_cleared works correctly. */
kono
parents: 14
diff changeset
353
kono
parents: 14
diff changeset
354 static void
kono
parents: 14
diff changeset
355 test_safe_grow_cleared ()
kono
parents: 14
diff changeset
356 {
kono
parents: 14
diff changeset
357 auto_vec <int> v;
kono
parents: 14
diff changeset
358 ASSERT_EQ (0, v.length ());
kono
parents: 14
diff changeset
359 v.safe_grow_cleared (50);
kono
parents: 14
diff changeset
360 ASSERT_EQ (50, v.length ());
kono
parents: 14
diff changeset
361 ASSERT_EQ (0, v[0]);
kono
parents: 14
diff changeset
362 ASSERT_EQ (0, v[49]);
0
a06113de4d67 first commit
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
363 }
16
kono
parents: 14
diff changeset
364
kono
parents: 14
diff changeset
365 /* Verify that vec::pop works correctly. */
kono
parents: 14
diff changeset
366
kono
parents: 14
diff changeset
367 static void
kono
parents: 14
diff changeset
368 test_pop ()
kono
parents: 14
diff changeset
369 {
kono
parents: 14
diff changeset
370 auto_vec <int> v;
kono
parents: 14
diff changeset
371 safe_push_range (v, 5, 20);
kono
parents: 14
diff changeset
372 ASSERT_EQ (15, v.length ());
kono
parents: 14
diff changeset
373
kono
parents: 14
diff changeset
374 int last = v.pop ();
kono
parents: 14
diff changeset
375 ASSERT_EQ (19, last);
kono
parents: 14
diff changeset
376 ASSERT_EQ (14, v.length ());
kono
parents: 14
diff changeset
377 }
kono
parents: 14
diff changeset
378
kono
parents: 14
diff changeset
379 /* Verify that vec::safe_insert works correctly. */
kono
parents: 14
diff changeset
380
kono
parents: 14
diff changeset
381 static void
kono
parents: 14
diff changeset
382 test_safe_insert ()
kono
parents: 14
diff changeset
383 {
kono
parents: 14
diff changeset
384 auto_vec <int> v;
kono
parents: 14
diff changeset
385 safe_push_range (v, 0, 10);
kono
parents: 14
diff changeset
386 v.safe_insert (5, 42);
kono
parents: 14
diff changeset
387 ASSERT_EQ (4, v[4]);
kono
parents: 14
diff changeset
388 ASSERT_EQ (42, v[5]);
kono
parents: 14
diff changeset
389 ASSERT_EQ (5, v[6]);
kono
parents: 14
diff changeset
390 ASSERT_EQ (11, v.length ());
kono
parents: 14
diff changeset
391 }
kono
parents: 14
diff changeset
392
kono
parents: 14
diff changeset
393 /* Verify that vec::ordered_remove works correctly. */
kono
parents: 14
diff changeset
394
kono
parents: 14
diff changeset
395 static void
kono
parents: 14
diff changeset
396 test_ordered_remove ()
kono
parents: 14
diff changeset
397 {
kono
parents: 14
diff changeset
398 auto_vec <int> v;
kono
parents: 14
diff changeset
399 safe_push_range (v, 0, 10);
kono
parents: 14
diff changeset
400 v.ordered_remove (5);
kono
parents: 14
diff changeset
401 ASSERT_EQ (4, v[4]);
kono
parents: 14
diff changeset
402 ASSERT_EQ (6, v[5]);
kono
parents: 14
diff changeset
403 ASSERT_EQ (9, v.length ());
kono
parents: 14
diff changeset
404 }
kono
parents: 14
diff changeset
405
kono
parents: 14
diff changeset
406 /* Verify that vec::unordered_remove works correctly. */
kono
parents: 14
diff changeset
407
kono
parents: 14
diff changeset
408 static void
kono
parents: 14
diff changeset
409 test_unordered_remove ()
kono
parents: 14
diff changeset
410 {
kono
parents: 14
diff changeset
411 auto_vec <int> v;
kono
parents: 14
diff changeset
412 safe_push_range (v, 0, 10);
kono
parents: 14
diff changeset
413 v.unordered_remove (5);
kono
parents: 14
diff changeset
414 ASSERT_EQ (9, v.length ());
kono
parents: 14
diff changeset
415 }
kono
parents: 14
diff changeset
416
kono
parents: 14
diff changeset
417 /* Verify that vec::block_remove works correctly. */
kono
parents: 14
diff changeset
418
kono
parents: 14
diff changeset
419 static void
kono
parents: 14
diff changeset
420 test_block_remove ()
kono
parents: 14
diff changeset
421 {
kono
parents: 14
diff changeset
422 auto_vec <int> v;
kono
parents: 14
diff changeset
423 safe_push_range (v, 0, 10);
kono
parents: 14
diff changeset
424 v.block_remove (5, 3);
kono
parents: 14
diff changeset
425 ASSERT_EQ (3, v[3]);
kono
parents: 14
diff changeset
426 ASSERT_EQ (4, v[4]);
kono
parents: 14
diff changeset
427 ASSERT_EQ (8, v[5]);
kono
parents: 14
diff changeset
428 ASSERT_EQ (9, v[6]);
kono
parents: 14
diff changeset
429 ASSERT_EQ (7, v.length ());
kono
parents: 14
diff changeset
430 }
kono
parents: 14
diff changeset
431
kono
parents: 14
diff changeset
432 /* Comparator for use by test_qsort. */
kono
parents: 14
diff changeset
433
kono
parents: 14
diff changeset
434 static int
kono
parents: 14
diff changeset
435 reverse_cmp (const void *p_i, const void *p_j)
kono
parents: 14
diff changeset
436 {
kono
parents: 14
diff changeset
437 return *(const int *)p_j - *(const int *)p_i;
kono
parents: 14
diff changeset
438 }
kono
parents: 14
diff changeset
439
kono
parents: 14
diff changeset
440 /* Verify that vec::qsort works correctly. */
kono
parents: 14
diff changeset
441
kono
parents: 14
diff changeset
442 static void
kono
parents: 14
diff changeset
443 test_qsort ()
kono
parents: 14
diff changeset
444 {
kono
parents: 14
diff changeset
445 auto_vec <int> v;
kono
parents: 14
diff changeset
446 safe_push_range (v, 0, 10);
kono
parents: 14
diff changeset
447 v.qsort (reverse_cmp);
kono
parents: 14
diff changeset
448 ASSERT_EQ (9, v[0]);
kono
parents: 14
diff changeset
449 ASSERT_EQ (8, v[1]);
kono
parents: 14
diff changeset
450 ASSERT_EQ (1, v[8]);
kono
parents: 14
diff changeset
451 ASSERT_EQ (0, v[9]);
kono
parents: 14
diff changeset
452 ASSERT_EQ (10, v.length ());
kono
parents: 14
diff changeset
453 }
kono
parents: 14
diff changeset
454
kono
parents: 14
diff changeset
455 /* Run all of the selftests within this file. */
kono
parents: 14
diff changeset
456
kono
parents: 14
diff changeset
457 void
kono
parents: 14
diff changeset
458 vec_c_tests ()
kono
parents: 14
diff changeset
459 {
kono
parents: 14
diff changeset
460 test_quick_push ();
kono
parents: 14
diff changeset
461 test_safe_push ();
kono
parents: 14
diff changeset
462 test_truncate ();
kono
parents: 14
diff changeset
463 test_safe_grow_cleared ();
kono
parents: 14
diff changeset
464 test_pop ();
kono
parents: 14
diff changeset
465 test_safe_insert ();
kono
parents: 14
diff changeset
466 test_ordered_remove ();
kono
parents: 14
diff changeset
467 test_unordered_remove ();
kono
parents: 14
diff changeset
468 test_block_remove ();
kono
parents: 14
diff changeset
469 test_qsort ();
kono
parents: 14
diff changeset
470 }
kono
parents: 14
diff changeset
471
kono
parents: 14
diff changeset
472 } // namespace selftest
kono
parents: 14
diff changeset
473
kono
parents: 14
diff changeset
474 #endif /* #if CHECKING_P */
kono
parents: 14
diff changeset
475 #endif /* #ifndef GENERATOR_FILE */