1// basisu_containers_impl.h
2// Do not include directly
3
4#ifdef _MSC_VER
5#pragma warning (disable:4127) // warning C4127: conditional expression is constant
6#endif
7
8namespace basisu
9{
10 bool elemental_vector::increase_capacity(uint32_t min_new_capacity, bool grow_hint, uint32_t element_size, object_mover pMover, bool nofail)
11 {
12 assert(m_size <= m_capacity);
13
14 if (sizeof(void *) == sizeof(uint64_t))
15 assert(min_new_capacity < (0x400000000ULL / element_size));
16 else
17 assert(min_new_capacity < (0x7FFF0000U / element_size));
18
19 if (m_capacity >= min_new_capacity)
20 return true;
21
22 size_t new_capacity = min_new_capacity;
23 if ((grow_hint) && (!helpers::is_power_of_2((uint64_t)new_capacity)))
24 {
25 new_capacity = (size_t)helpers::next_pow2((uint64_t)new_capacity);
26
27 assert(new_capacity && (new_capacity > m_capacity));
28
29 if (new_capacity < min_new_capacity)
30 {
31 if (nofail)
32 return false;
33 fprintf(stderr, "vector too large\n");
34 abort();
35 }
36 }
37
38 const size_t desired_size = element_size * new_capacity;
39 size_t actual_size = 0;
40 if (!pMover)
41 {
42 void* new_p = realloc(m_p, desired_size);
43 if (!new_p)
44 {
45 if (nofail)
46 return false;
47
48 char buf[256];
49#ifdef _MSC_VER
50 sprintf_s(buf, sizeof(buf), "vector: realloc() failed allocating %u bytes", (uint32_t)desired_size);
51#else
52 sprintf(buf, "vector: realloc() failed allocating %u bytes", (uint32_t)desired_size);
53#endif
54 fprintf(stderr, "%s", buf);
55 abort();
56 }
57
58#if BASISU_VECTOR_DETERMINISTIC
59 actual_size = desired_size;
60#elif defined(_MSC_VER)
61 actual_size = _msize(new_p);
62#elif HAS_MALLOC_USABLE_SIZE
63 actual_size = malloc_usable_size(new_p);
64#else
65 actual_size = desired_size;
66#endif
67 m_p = new_p;
68 }
69 else
70 {
71 void* new_p = malloc(desired_size);
72 if (!new_p)
73 {
74 if (nofail)
75 return false;
76
77 char buf[256];
78#ifdef _MSC_VER
79 sprintf_s(buf, sizeof(buf), "vector: malloc() failed allocating %u bytes", (uint32_t)desired_size);
80#else
81 sprintf(buf, "vector: malloc() failed allocating %u bytes", (uint32_t)desired_size);
82#endif
83 fprintf(stderr, "%s", buf);
84 abort();
85 }
86
87#if BASISU_VECTOR_DETERMINISTIC
88 actual_size = desired_size;
89#elif defined(_MSC_VER)
90 actual_size = _msize(new_p);
91#elif HAS_MALLOC_USABLE_SIZE
92 actual_size = malloc_usable_size(new_p);
93#else
94 actual_size = desired_size;
95#endif
96
97 (*pMover)(new_p, m_p, m_size);
98
99 if (m_p)
100 free(m_p);
101
102 m_p = new_p;
103 }
104
105 if (actual_size > desired_size)
106 m_capacity = static_cast<uint32_t>(actual_size / element_size);
107 else
108 m_capacity = static_cast<uint32_t>(new_capacity);
109
110 return true;
111 }
112
113#if BASISU_HASHMAP_TEST
114
115#define HASHMAP_TEST_VERIFY(c) do { if (!(c)) handle_hashmap_test_verify_failure(__LINE__); } while(0)
116
117 static void handle_hashmap_test_verify_failure(int line)
118 {
119 fprintf(stderr, "HASHMAP_TEST_VERIFY() faild on line %i\n", line);
120 abort();
121 }
122
123 class counted_obj
124 {
125 public:
126 counted_obj(uint32_t v = 0) :
127 m_val(v)
128 {
129 m_count++;
130 }
131
132 counted_obj(const counted_obj& obj) :
133 m_val(obj.m_val)
134 {
135 m_count++;
136 }
137
138 ~counted_obj()
139 {
140 assert(m_count > 0);
141 m_count--;
142 }
143
144 static uint32_t m_count;
145
146 uint32_t m_val;
147
148 operator size_t() const { return m_val; }
149
150 bool operator== (const counted_obj& rhs) const { return m_val == rhs.m_val; }
151 bool operator== (const uint32_t rhs) const { return m_val == rhs; }
152
153 };
154
155 uint32_t counted_obj::m_count;
156
157 static uint32_t urand32()
158 {
159 uint32_t a = rand();
160 uint32_t b = rand() << 15;
161 uint32_t c = rand() << (32 - 15);
162 return a ^ b ^ c;
163 }
164
165 static int irand32(int l, int h)
166 {
167 assert(l < h);
168 if (l >= h)
169 return l;
170
171 uint32_t range = static_cast<uint32_t>(h - l);
172
173 uint32_t rnd = urand32();
174
175 uint32_t rnd_range = static_cast<uint32_t>((((uint64_t)range) * ((uint64_t)rnd)) >> 32U);
176
177 int result = l + rnd_range;
178 assert((result >= l) && (result < h));
179 return result;
180 }
181
182 void hash_map_test()
183 {
184 {
185 basisu::hash_map<uint64_t, uint64_t> k;
186 basisu::hash_map<uint64_t, uint64_t> l;
187 std::swap(k, l);
188
189 k.begin();
190 k.end();
191 k.clear();
192 k.empty();
193 k.erase(0);
194 k.insert(0, 1);
195 k.find(0);
196 k.get_equals();
197 k.get_hasher();
198 k.get_table_size();
199 k.reset();
200 k.reserve(1);
201 k = l;
202 k.set_equals(l.get_equals());
203 k.set_hasher(l.get_hasher());
204 k.get_table_size();
205 }
206
207 uint32_t seed = 0;
208 for (; ; )
209 {
210 seed++;
211
212 typedef basisu::hash_map<counted_obj, counted_obj> my_hash_map;
213 my_hash_map m;
214
215 const uint32_t n = irand32(0, 100000);
216
217 printf("%u\n", n);
218
219 srand(seed); // r1.seed(seed);
220
221 basisu::vector<int> q;
222
223 uint32_t count = 0;
224 for (uint32_t i = 0; i < n; i++)
225 {
226 uint32_t v = urand32() & 0x7FFFFFFF;
227 my_hash_map::insert_result res = m.insert(counted_obj(v), counted_obj(v ^ 0xdeadbeef));
228 if (res.second)
229 {
230 count++;
231 q.push_back(v);
232 }
233 }
234
235 HASHMAP_TEST_VERIFY(m.size() == count);
236
237 srand(seed);
238
239 my_hash_map cm(m);
240 m.clear();
241 m = cm;
242 cm.reset();
243
244 for (uint32_t i = 0; i < n; i++)
245 {
246 uint32_t v = urand32() & 0x7FFFFFFF;
247 my_hash_map::const_iterator it = m.find(counted_obj(v));
248 HASHMAP_TEST_VERIFY(it != m.end());
249 HASHMAP_TEST_VERIFY(it->first == v);
250 HASHMAP_TEST_VERIFY(it->second == (v ^ 0xdeadbeef));
251 }
252
253 for (uint32_t t = 0; t < 2; t++)
254 {
255 const uint32_t nd = irand32(1, q.size() + 1);
256 for (uint32_t i = 0; i < nd; i++)
257 {
258 uint32_t p = irand32(0, q.size());
259
260 int k = q[p];
261 if (k >= 0)
262 {
263 q[p] = -k - 1;
264
265 bool s = m.erase(counted_obj(k));
266 HASHMAP_TEST_VERIFY(s);
267 }
268 }
269
270 typedef basisu::hash_map<uint32_t, empty_type> uint_hash_set;
271 uint_hash_set s;
272
273 for (uint32_t i = 0; i < q.size(); i++)
274 {
275 int v = q[i];
276
277 if (v >= 0)
278 {
279 my_hash_map::const_iterator it = m.find(counted_obj(v));
280 HASHMAP_TEST_VERIFY(it != m.end());
281 HASHMAP_TEST_VERIFY(it->first == (uint32_t)v);
282 HASHMAP_TEST_VERIFY(it->second == ((uint32_t)v ^ 0xdeadbeef));
283
284 s.insert(v);
285 }
286 else
287 {
288 my_hash_map::const_iterator it = m.find(counted_obj(-v - 1));
289 HASHMAP_TEST_VERIFY(it == m.end());
290 }
291 }
292
293 uint32_t found_count = 0;
294 for (my_hash_map::const_iterator it = m.begin(); it != m.end(); ++it)
295 {
296 HASHMAP_TEST_VERIFY(it->second == ((uint32_t)it->first ^ 0xdeadbeef));
297
298 uint_hash_set::const_iterator fit(s.find((uint32_t)it->first));
299 HASHMAP_TEST_VERIFY(fit != s.end());
300
301 HASHMAP_TEST_VERIFY(fit->first == it->first);
302
303 found_count++;
304 }
305
306 HASHMAP_TEST_VERIFY(found_count == s.size());
307 }
308
309 HASHMAP_TEST_VERIFY(counted_obj::m_count == m.size() * 2);
310 }
311 }
312
313#endif // BASISU_HASHMAP_TEST
314
315} // namespace basisu
316