Line data Source code
1 : /*
2 : * Copyright (c) 2010, Andrea Mazzoleni. All rights reserved.
3 : *
4 : * Redistribution and use in source and binary forms, with or without
5 : * modification, are permitted provided that the following conditions
6 : * are met:
7 : *
8 : * 1. Redistributions of source code must retain the above copyright
9 : * notice, this list of conditions and the following disclaimer.
10 : *
11 : * 2. Redistributions in binary form must reproduce the above copyright
12 : * notice, this list of conditions and the following disclaimer in the
13 : * documentation and/or other materials provided with the distribution.
14 : *
15 : * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
16 : * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17 : * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
18 : * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
19 : * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
20 : * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
21 : * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
22 : * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
23 : * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
24 : * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
25 : * POSSIBILITY OF SUCH DAMAGE.
26 : */
27 :
28 : /**
29 : * Tommy check program.
30 : *
31 : * Simply run it without any options. If it terminates printing "OK" all the
32 : * checks are succesful.
33 : */
34 :
35 : #include <math.h>
36 : #include <stdlib.h>
37 : #include <stdio.h>
38 : #include <string.h>
39 : #include <stddef.h>
40 : #include <time.h>
41 : #include <errno.h>
42 : #include <assert.h>
43 :
44 : #if defined(__linux)
45 : #include <stdint.h>
46 : #include <unistd.h>
47 : #include <sys/time.h>
48 : #endif
49 :
50 : #if defined(__MACH__)
51 : #include <mach/mach_time.h>
52 : #endif
53 :
54 : #include "tommyds/tommy.h"
55 :
56 : #define TOMMY_SIZE 1000000
57 :
58 : #define PAYLOAD 16 /**< Size of payload data for objects */
59 :
60 : struct object {
61 : int value;
62 : tommy_node node;
63 : char payload[PAYLOAD];
64 : };
65 :
66 : unsigned compare_counter;
67 :
68 93619455 : int compare(const void* void_a, const void* void_b)
69 : {
70 93619455 : const struct object* a = void_a;
71 93619455 : const struct object* b = void_b;
72 :
73 93619455 : ++compare_counter;
74 :
75 93619455 : if (a->value < b->value)
76 44315313 : return -1;
77 49304142 : if (a->value > b->value)
78 42346062 : return 1;
79 6958080 : return 0;
80 : }
81 :
82 : struct object_vector {
83 : int value;
84 : char payload[PAYLOAD];
85 : };
86 :
87 73248608 : int compare_vector(const void* void_a, const void* void_b)
88 : {
89 73248608 : const struct object_vector* a = void_a;
90 73248608 : const struct object_vector* b = void_b;
91 :
92 73248608 : ++compare_counter;
93 :
94 73248608 : if (a->value < b->value)
95 32724901 : return -1;
96 40523707 : if (a->value > b->value)
97 34939766 : return 1;
98 5583941 : return 0;
99 : }
100 :
101 : struct object_hash {
102 : int value;
103 : tommy_node node;
104 : char payload[PAYLOAD];
105 : };
106 :
107 : struct object_tree {
108 : int value;
109 : tommy_tree_node node;
110 : char payload[PAYLOAD];
111 : };
112 :
113 : struct object_trie {
114 : int value;
115 : tommy_trie_node node;
116 : char payload[PAYLOAD];
117 : };
118 :
119 : struct object_trie_inplace {
120 : int value;
121 : tommy_trie_inplace_node node;
122 : char payload[PAYLOAD];
123 : };
124 :
125 : /******************************************************************************/
126 : /* time */
127 :
128 : #if defined(_WIN32)
129 : static LARGE_INTEGER win_frequency;
130 : #endif
131 :
132 1 : static void nano_init(void)
133 : {
134 : #if defined(_WIN32)
135 : if (!QueryPerformanceFrequency(&win_frequency)) {
136 : win_frequency.QuadPart = 0;
137 : }
138 : #endif
139 1 : }
140 :
141 74 : static tommy_uint64_t nano(void)
142 : {
143 : tommy_uint64_t ret;
144 : #if defined(_WIN32)
145 : LARGE_INTEGER t;
146 :
147 : if (!QueryPerformanceCounter(&t))
148 : return 0;
149 :
150 : ret = (t.QuadPart / win_frequency.QuadPart) * 1000000000;
151 :
152 : ret += (t.QuadPart % win_frequency.QuadPart) * 1000000000 / win_frequency.QuadPart;
153 : #elif defined(__MACH__)
154 : mach_timebase_info_data_t info;
155 : kern_return_t r;
156 : tommy_uint64_t t;
157 :
158 : t = mach_absolute_time();
159 :
160 : r = mach_timebase_info(&info);
161 : if (r != 0)
162 : /* LCOV_EXCL_START */
163 : abort();
164 : /* LCOV_EXCL_STOP */
165 :
166 : ret = (t / info.denom) * info.numer;
167 :
168 : ret += (t % info.denom) * info.numer / info.denom;
169 : #elif defined(__linux)
170 : struct timespec ts;
171 : int r;
172 :
173 74 : r = clock_gettime(CLOCK_MONOTONIC, &ts);
174 74 : if (r != 0)
175 : /* LCOV_EXCL_START */
176 : abort();
177 : /* LCOV_EXCL_STOP */
178 :
179 74 : ret = ts.tv_sec * (tommy_uint64_t)1000000000 + ts.tv_nsec;
180 : #else
181 : struct timeval tv;
182 : int r;
183 :
184 : r = gettimeofday(&tv, 0);
185 : if (r != 0)
186 : /* LCOV_EXCL_START */
187 : abort();
188 : /* LCOV_EXCL_STOP */
189 :
190 : ret = tv.tv_sec * (tommy_uint64_t)1000000000 + tv.tv_usec * 1000;
191 : #endif
192 74 : return ret;
193 : }
194 :
195 : /******************************************************************************/
196 : /* random */
197 :
198 : /**
199 : * Pseudo random number generator.
200 : * Note that using (rand() % max) in Visual C results in totally bogus values,
201 : * with *strong* cache effects when accessing elements in a not really random order.
202 : * This happen because Visual C uses a simple linear congruential generator with only 32 bits.
203 : */
204 : tommy_uint64_t SEED = 0;
205 :
206 3009981 : unsigned rnd(unsigned max)
207 : {
208 : unsigned r;
209 : tommy_uint64_t divider;
210 :
211 : loop:
212 : /* linear congruential generator from MMIX by Donald Knuth, http://en.wikipedia.org/wiki/Linear_congruential_generator */
213 : #ifdef _MSC_VER
214 : divider = 0xFFFFFFFFFFFFFFFF / max;
215 : SEED = SEED * 6364136223846793005 + 1442695040888963407;
216 : #else
217 3009981 : divider = 0xFFFFFFFFFFFFFFFFULL / max;
218 3009981 : SEED = SEED * 6364136223846793005LL + 1442695040888963407LL;
219 : #endif
220 :
221 3009981 : r = (unsigned)(SEED / divider);
222 :
223 : /* it may happen as the divider is approximated down */
224 3009981 : if (r >= max)
225 : /* LCOV_EXCL_START */
226 : goto loop;
227 : /* LCOV_EXCL_STOP */
228 :
229 3009981 : return r;
230 : }
231 :
232 : /******************************************************************************/
233 : /* helper */
234 :
235 6 : unsigned isqrt(unsigned n)
236 : {
237 : unsigned root, remain, place;
238 :
239 6 : root = 0;
240 :
241 6 : remain = n;
242 :
243 6 : place = 0x40000000;
244 :
245 48 : while (place > remain)
246 36 : place /= 4;
247 :
248 72 : while (place) {
249 60 : if (remain >= root + place) {
250 36 : remain -= root + place;
251 36 : root += 2 * place;
252 : }
253 :
254 60 : root /= 2;
255 60 : place /= 4;
256 : }
257 :
258 6 : return root;
259 : }
260 :
261 : /**
262 : * Cache clearing buffer.
263 : */
264 : static unsigned char the_cache[16*1024*1024];
265 : static const char* the_str;
266 : static tommy_uint64_t the_start;
267 :
268 37 : void cache_clear(void)
269 : {
270 : unsigned i;
271 :
272 : /* read & write */
273 19398693 : for(i=0;i<sizeof(the_cache);i += 32)
274 19398656 : the_cache[i] += 1;
275 :
276 : #ifdef WIN32
277 : Sleep(0);
278 : #endif
279 37 : }
280 :
281 37 : void start(const char* str)
282 : {
283 37 : cache_clear();
284 37 : compare_counter = 0;
285 37 : the_str = str;
286 37 : the_start = nano();
287 37 : }
288 :
289 37 : void stop()
290 : {
291 37 : tommy_uint64_t the_stop = nano();
292 37 : printf("%25s %8u [ms], %8u [compare]\n", the_str, (unsigned)((the_stop - the_start) / 1000000), compare_counter);
293 37 : }
294 :
295 : #define START(s) start(s)
296 : #define STOP() stop()
297 :
298 : /******************************************************************************/
299 : /* test */
300 :
301 : static unsigned the_count;
302 :
303 40742500 : static void count_callback(void* data)
304 : {
305 : (void)data;
306 40742500 : ++the_count;
307 40742500 : }
308 :
309 3255673 : static void count_arg_callback(void* arg, void* data)
310 : {
311 3255673 : unsigned* count = arg;
312 : (void)data;
313 3255673 : ++*count;
314 3255673 : }
315 :
316 26998173 : static int search_callback(const void* arg, const void* obj)
317 : {
318 26998173 : return arg != obj;
319 : }
320 :
321 : struct hash32_test {
322 : char* data;
323 : tommy_uint32_t len;
324 : tommy_uint32_t hash;
325 : } HASH32[] = {
326 : { "", 0, 0x8614384c },
327 : { "a", 1, 0x12c16c36 },
328 : { "abc", 3, 0xc58e8af5 },
329 : { "message digest", 14, 0x006b32f1 },
330 : { "abcdefghijklmnopqrstuvwxyz", 26, 0x7e6fcfe0 },
331 : { "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789", 62, 0x8604adf8 },
332 : { "The quick brown fox jumps over the lazy dog", 43, 0xdeba3d3a },
333 : { "\x00", 1, 0x4a7d1c33 },
334 : { "\x16\x27", 2, 0x8b50899b },
335 : { "\xe2\x56\xb4", 3, 0x60406493 },
336 : { "\xc9\x4d\x9c\xda", 4, 0xa049144a },
337 : { "\x79\xf1\x29\x69\x5d", 5, 0x4da2c2f1 },
338 : { "\x00\x7e\xdf\x1e\x31\x1c", 6, 0x59de30cf },
339 : { "\x2a\x4c\xe1\xff\x9e\x6f\x53", 7, 0x219e149c },
340 : { "\xba\x02\xab\x18\x30\xc5\x0e\x8a", 8, 0x25067520 },
341 : { "\xec\x4e\x7a\x72\x1e\x71\x2a\xc9\x33", 9, 0xa1f368d8 },
342 : { "\xfd\xe2\x9c\x0f\x72\xb7\x08\xea\xd0\x78", 10, 0x805fc63d },
343 : { "\x65\xc4\x8a\xb8\x80\x86\x9a\x79\x00\xb7\xae", 11, 0x7f75dd0f },
344 : { "\x77\xe9\xd7\x80\x0e\x3f\x5c\x43\xc8\xc2\x46\x39", 12, 0xb9154382 },
345 : { "\x87\xd8\x61\x61\x4c\x89\x17\x4e\xa1\xa4\xef\x13\xa9", 13, 0x2bdd05d7 },
346 : { "\xfe\xa6\x5b\xc2\xda\xe8\x95\xd4\x64\xab\x4c\x39\x58\x29", 14, 0xabffeb9f },
347 : { "\x94\x49\xc0\x78\xa0\x80\xda\xc7\x71\x4e\x17\x37\xa9\x7c\x40", 15, 0x886da0b4 },
348 : { "\x53\x7e\x36\xb4\x2e\xc9\xb9\xcc\x18\x3e\x9a\x5f\xfc\xb7\xb0\x61", 16, 0x34ed2af3 },
349 : { 0, 0, 0 }
350 : };
351 :
352 : struct strhash32_test {
353 : char* data;
354 : tommy_uint32_t hash;
355 : } STRHASH32[] = {
356 : { "", 0x0af1416d },
357 : { "a", 0x68fa0f3f },
358 : { "abc", 0xfc68ffc5 },
359 : { "message digest", 0x08477b63 },
360 : { "abcdefghijklmnopqrstuvwxyz", 0x5b9c25e5 },
361 : { "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789", 0x1e530ce7 },
362 : { "The quick brown fox jumps over the lazy dog", 0xaf93eefe },
363 : { "\xff", 0xfc88801b },
364 : { "\x16\x27", 0xcd7216db },
365 : { "\xe2\x56\xb4", 0x05f98d02 },
366 : { "\xc9\x4d\x9c\xda", 0xf65206f8 },
367 : { "\x79\xf1\x29\x69\x5d", 0x72bd6bda },
368 : { "\xff\x7e\xdf\x1e\x31\x1c", 0x57dfb9b4 },
369 : { "\x2a\x4c\xe1\xff\x9e\x6f\x53", 0x499ff634 },
370 : { "\xba\x02\xab\x18\x30\xc5\x0e\x8a", 0xe896b7ce },
371 : { "\xec\x4e\x7a\x72\x1e\x71\x2a\xc9\x33", 0xfe3939f0 },
372 : { "\xfd\xe2\x9c\x0f\x72\xb7\x08\xea\xd0\x78", 0x4351d482 },
373 : { "\x65\xc4\x8a\xb8\x80\x86\x9a\x79\xff\xb7\xae", 0x88e92135 },
374 : { "\x77\xe9\xd7\x80\x0e\x3f\x5c\x43\xc8\xc2\x46\x39", 0x01109c16 },
375 : { "\x87\xd8\x61\x61\x4c\x89\x17\x4e\xa1\xa4\xef\x13\xa9", 0xbcb050dc },
376 : { "\xfe\xa6\x5b\xc2\xda\xe8\x95\xd4\x64\xab\x4c\x39\x58\x29", 0xbe5e1fd5 },
377 : { "\x94\x49\xc0\x78\xa0\x80\xda\xc7\x71\x4e\x17\x37\xa9\x7c\x40", 0x70d8c97f },
378 : { "\x53\x7e\x36\xb4\x2e\xc9\xb9\xcc\x18\x3e\x9a\x5f\xfc\xb7\xb0\x61", 0x957440a9 },
379 : { 0, 0 }
380 : };
381 :
382 : struct hash64_test {
383 : char* data;
384 : tommy_uint32_t len;
385 : tommy_uint64_t hash;
386 : } HASH64[] = {
387 : { "", 0, 0x8614384cb5165fbfULL },
388 : { "a", 1, 0x1a2e0298a8e94a3dULL },
389 : { "abc", 3, 0x7555796b7a7d21ebULL },
390 : { "message digest", 14, 0x9411a57d04b92fb4ULL },
391 : { "abcdefghijklmnopqrstuvwxyz", 26, 0x3ca3f8d2b4e69832ULL },
392 : { "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789", 62, 0x6dae542ba0015a4dULL },
393 : { "The quick brown fox jumps over the lazy dog", 43, 0xe06d8cbb3d2ea1a6ULL },
394 : { "\x00", 1, 0x201e664fb5f2c021ULL },
395 : { "\x16\x27", 2, 0xef42fa8032c4b775ULL },
396 : { "\xe2\x56\xb4", 3, 0x6e6c498a6688466cULL },
397 : { "\xc9\x4d\x9c\xda", 4, 0x5195005419905423ULL },
398 : { "\x79\xf1\x29\x69\x5d", 5, 0x221235b48afee7c1ULL },
399 : { "\x00\x7e\xdf\x1e\x31\x1c", 6, 0x1b1f18b9266f095bULL },
400 : { "\x2a\x4c\xe1\xff\x9e\x6f\x53", 7, 0x2cbafa8e741d49caULL },
401 : { "\xba\x02\xab\x18\x30\xc5\x0e\x8a", 8, 0x4677f04c06e0758dULL },
402 : { "\xec\x4e\x7a\x72\x1e\x71\x2a\xc9\x33", 9, 0x5afe09e8214e2163ULL },
403 : { "\xfd\xe2\x9c\x0f\x72\xb7\x08\xea\xd0\x78", 10, 0x115b6276d209fab6ULL },
404 : { "\x65\xc4\x8a\xb8\x80\x86\x9a\x79\x00\xb7\xae", 11, 0xd0636d2f01cf3a3eULL },
405 : { "\x77\xe9\xd7\x80\x0e\x3f\x5c\x43\xc8\xc2\x46\x39", 12, 0x6d259f5fef74f93eULL },
406 : { "\x87\xd8\x61\x61\x4c\x89\x17\x4e\xa1\xa4\xef\x13\xa9", 13, 0x23449c3baf93ac39ULL },
407 : { "\xfe\xa6\x5b\xc2\xda\xe8\x95\xd4\x64\xab\x4c\x39\x58\x29", 14, 0x9b85ba28d7854d69ULL },
408 : { "\x94\x49\xc0\x78\xa0\x80\xda\xc7\x71\x4e\x17\x37\xa9\x7c\x40", 15, 0x3617c833193a359fULL },
409 : { "\x53\x7e\x36\xb4\x2e\xc9\xb9\xcc\x18\x3e\x9a\x5f\xfc\xb7\xb0\x61", 16, 0x5dbf9ff58e274dd9ULL },
410 : { 0, 0, 0 }
411 : };
412 :
413 : struct inthash32_test {
414 : tommy_uint32_t value;
415 : tommy_uint32_t hash;
416 : } INTHASH32[] = {
417 : { 0x00000000, 0x00000000 },
418 : { 0x00000001, 0xc2b73583 },
419 : { 0x00000002, 0xe90f1258 },
420 : { 0x00000004, 0x7a10c2d3 },
421 : { 0x00000008, 0x200c3457 },
422 : { 0x00000010, 0xeb97690a },
423 : { 0x00000020, 0x7fb291d3 },
424 : { 0x00000040, 0xf50601d8 },
425 : { 0x00000080, 0x727dbaed },
426 : { 0x00000100, 0x7ef5f77d },
427 : { 0x00000200, 0x91a480dc },
428 : { 0x00000400, 0x2bad9acc },
429 : { 0x00000800, 0xfe4d150e },
430 : { 0x00001000, 0xc3add476 },
431 : { 0x00002000, 0x23946174 },
432 : { 0x00004000, 0x987cfc43 },
433 : { 0x00008000, 0x630cdf68 },
434 : { 0x00010000, 0x0ac3a767 },
435 : { 0x00020000, 0xad086d5b },
436 : { 0x00040000, 0x1126ccdf },
437 : { 0x00080000, 0x4370dbc4 },
438 : { 0x00100000, 0xefd6e5e6 },
439 : { 0x00200000, 0x9a93c1b5 },
440 : { 0x00400000, 0x10114902 },
441 : { 0x00800000, 0x96117e60 },
442 : { 0x01000000, 0x5dec9f58 },
443 : { 0x02000000, 0xfee234c7 },
444 : { 0x04000000, 0x36137e26 },
445 : { 0x08000000, 0x6c26fc4c },
446 : { 0x10000000, 0xd84df898 },
447 : { 0x20000000, 0xb099f131 },
448 : { 0x40000000, 0x6131e262 },
449 : { 0x80000000, 0xc263c4c4 },
450 : { 0x00204a16, 0xd8b97461 },
451 : { 0x05542a27, 0x65d0057a },
452 : { 0x169c39e2, 0x7c2ff59a },
453 : { 0x2eab4956, 0xa8ba89bd },
454 : { 0x0bb0b8b4, 0xb790c8de },
455 : { 0x0bd068c9, 0x92d30546 },
456 : { 0x3e5d224d, 0xd610bf1d },
457 : { 0x436c8d9c, 0x27b09019 },
458 : { 0x3a2adfda, 0xdfde9385 },
459 : { 0x1dd8ca79, 0xc7c10d7b },
460 : { 0x6a67c4f1, 0xf92a788d },
461 : { 0x7742fa29, 0x892c3519 },
462 : { 0x48b62d69, 0x7f642f55 },
463 : { 0x472e195d, 0xea2c49e5 },
464 : { 0x0681a900, 0x4de5c929 },
465 : { 0x622ebb7e, 0x35a7e306 },
466 : { 0x026bccdf, 0xa7e4b630 },
467 : { 0x204d531e, 0x43ebd664 },
468 : { 0x262b5331, 0x7a9a161f },
469 : { 0x7020241c, 0xbaed3ef7 },
470 : { 0x440a0e2a, 0x0b8c5b29 },
471 : { 0x75cb1c4c, 0x19555414 },
472 : { 0x41f9a5e1, 0xc6acbc6b },
473 : { 0x67bc26ff, 0x54e4411f },
474 : { 0x181e279e, 0x979c834f },
475 : { 0x7172c06f, 0xe6a179ff },
476 : { 0x4909e153, 0x198e5e0f },
477 : { 0x09d3bfba, 0x109a6f17 },
478 : { 0x685ae502, 0xf9d57a4b },
479 : { 0x7e10e8ab, 0x09765bec },
480 : { 0x0f262618, 0xe16404cd },
481 : { 0x726b8230, 0x55e478b4 },
482 : { 0, 0 }
483 : };
484 :
485 : struct inthash64_test {
486 : tommy_uint64_t value;
487 : tommy_uint64_t hash;
488 : } INTHASH64[] = {
489 : { 0x0000000000000000ULL, 0x77cfa1eef01bca90ULL },
490 : { 0x0000000000000001ULL, 0x5bca7c69b794f8ceULL },
491 : { 0x0000000000000002ULL, 0xb795033f6f2a0674ULL },
492 : { 0x0000000000000004ULL, 0x6f2a25235e544a31ULL },
493 : { 0x0000000000000008ULL, 0xde543f7b3ca87ecbULL },
494 : { 0x0000000000000010ULL, 0xbca87eec7950fd82ULL },
495 : { 0x0000000000000020ULL, 0x7950fddef2a1fb10ULL },
496 : { 0x0000000000000040ULL, 0xf2a1fbbde543f620ULL },
497 : { 0x0000000000000080ULL, 0xe543f9324a87efadULL },
498 : { 0x0000000000000100ULL, 0xca87f25e950fdf4eULL },
499 : { 0x0000000000000200ULL, 0x950fe4bd2a1fbe9cULL },
500 : { 0x0000000000000400ULL, 0x2a1fc968543f7d14ULL },
501 : { 0x0000000000000800ULL, 0x543f92d0a87efa28ULL },
502 : { 0x0000000000001000ULL, 0xa87f259f50fdf44cULL },
503 : { 0x0000000000002000ULL, 0x50fe4b3ea1fbe898ULL },
504 : { 0x0000000000004000ULL, 0xa1fc967bc3f7d12dULL },
505 : { 0x0000000000008000ULL, 0x43f92da207efa3afULL },
506 : { 0x0000000000010000ULL, 0x87f25b4e8fdf4773ULL },
507 : { 0x0000000000020000ULL, 0x0fe4b6a71fbe8efaULL },
508 : { 0x0000000000040000ULL, 0x1fc96d4ebf7d1df5ULL },
509 : { 0x0000000000080000ULL, 0x3f92da9dfefa3bebULL },
510 : { 0x0000000000100000ULL, 0x7f25b53c7df477d7ULL },
511 : { 0x0000000000200000ULL, 0xfe4b6a797be8efafULL },
512 : { 0x0000000000400000ULL, 0xfc96d4f377d1df5fULL },
513 : { 0x0000000000800000ULL, 0xf92da9e76fa3bebfULL },
514 : { 0x0000000001000000ULL, 0xf25b39f0df4749c2ULL },
515 : { 0x0000000002000000ULL, 0xe4b673e1be8e9384ULL },
516 : { 0x0000000004000000ULL, 0xc96ce7c3fd1d2709ULL },
517 : { 0x0000000008000000ULL, 0x92d9cf87fa3a4e12ULL },
518 : { 0x0000000010000000ULL, 0x25b39f0ff4749c24ULL },
519 : { 0x0000000020000000ULL, 0x4b673e1fe8e93848ULL },
520 : { 0x0000000040000000ULL, 0x96ce7c3a51d27085ULL },
521 : { 0x0000000080000000ULL, 0x2d9cf88523a4e10bULL },
522 : { 0x0000000100000000ULL, 0x5b39f10ac749c217ULL },
523 : { 0x0000000200000000ULL, 0xb673e2060e93842fULL },
524 : { 0x0000000400000000ULL, 0x6ce7c40c9d27085fULL },
525 : { 0x0000000800000000ULL, 0xdc8387ff3f0e10aaULL },
526 : { 0x0000001000000000ULL, 0xb9070fee7e1c2154ULL },
527 : { 0x0000002000000000ULL, 0x720e1fdcfc3842a8ULL },
528 : { 0x0000004000000000ULL, 0xe41c3fa478708545ULL },
529 : { 0x0000008000000000ULL, 0xc8387f58f0e10a8aULL },
530 : { 0x0000010000000000ULL, 0x9364fec267021515ULL },
531 : { 0x0000020000000000ULL, 0x26c9fd954e042a2bULL },
532 : { 0x0000040000000000ULL, 0x4d93fb2a9c085456ULL },
533 : { 0x0000080000000000ULL, 0x9b27f6553810a8acULL },
534 : { 0x0000100000000000ULL, 0xae84159b600d1cc8ULL },
535 : { 0x0000200000000000ULL, 0x455932ec903fc254ULL },
536 : { 0x0000400000000000ULL, 0xa2d36aa0d044b36fULL },
537 : { 0x0000800000000000ULL, 0x7b8ef94d0d2d2844ULL },
538 : { 0x0001000000000000ULL, 0xd802248d5ba62df7ULL },
539 : { 0x0002000000000000ULL, 0x2c298f47af1d015eULL },
540 : { 0x0004000000000000ULL, 0x93a4e2a055abc2f5ULL },
541 : { 0x0008000000000000ULL, 0x6f9511373b7145b2ULL },
542 : { 0x0010000000000000ULL, 0x6305c0717e1d40d4ULL },
543 : { 0x0020000000000000ULL, 0x6237df27b416b76bULL },
544 : { 0x0040000000000000ULL, 0x042bc5ffe77f439eULL },
545 : { 0x0080000000000000ULL, 0x7241900621a8c72bULL },
546 : { 0x0100000000000000ULL, 0x6a298a4b4ecb2ec6ULL },
547 : { 0x0200000000000000ULL, 0x789742a5659f92fbULL },
548 : { 0x0400000000000000ULL, 0x794ee951db0365e6ULL },
549 : { 0x0800000000000000ULL, 0x745424e0b94aec3cULL },
550 : { 0x1000000000000000ULL, 0x726e27d005120de7ULL },
551 : { 0x2000000000000000ULL, 0x6898adb511c8513eULL },
552 : { 0x4000000000000000ULL, 0x59dbb96b3414d7ecULL },
553 : { 0x8000000000000000ULL, 0x3be7d0f7780de548ULL },
554 : { 0x0cead30e6469f5c5ULL, 0x0f3b67e6407d0ed9ULL },
555 : { 0x028a2bec206c7b8aULL, 0xa9be0155bf452972ULL },
556 : { 0x56e5747a306eac4eULL, 0x308451cac91706c3ULL },
557 : { 0x6058b11e57287c72ULL, 0x6f8b3e2b8bf1abc4ULL },
558 : { 0x4fec8f2a00cc2071ULL, 0x11f1e965f20a45a4ULL },
559 : { 0x4f0bdf33102febc9ULL, 0x6102a774aa4baacfULL },
560 : { 0x17e067e262adc6fdULL, 0x5878e9adb48c4d7cULL },
561 : { 0x41374f0f3f94939cULL, 0x55d43d2febf8b7dfULL },
562 : { 0x59d163b72870b072ULL, 0x98ee8d1508e8ff20ULL },
563 : { 0x702b00ea2f01f008ULL, 0x1abf9db8b3306341ULL },
564 : { 0x433b78782f7cc0d0ULL, 0xd33358a085d11f6aULL },
565 : { 0x45789bc436c34865ULL, 0xa573c24e116ccf0dULL },
566 : { 0x15e7f9b85580528aULL, 0x6d594ec1bb5651dfULL },
567 : { 0x6e52ea866a56f880ULL, 0x5dac61fbbe7d64ffULL },
568 : { 0x06baec796275d69aULL, 0x193424cca0b43145ULL },
569 : { 0x2ac9d0b77bbdcc00ULL, 0x44b2175a2c313151ULL },
570 : { 0x2299ab770a8223aeULL, 0x404514aa9d8e5c65ULL },
571 : { 0x568e90d709816de9ULL, 0x08907c8b20d9fb59ULL },
572 : { 0x3b6b460e67b34680ULL, 0xfc77f1ea859b024eULL },
573 : { 0x418fde5c48db0e3fULL, 0x2e6a2d8cbe2d4412ULL },
574 : { 0x5e8fa3c84b12c543ULL, 0xa9354017412aba12ULL },
575 : { 0x49fad5466f937fc2ULL, 0xe81aeb4429b6264aULL },
576 : { 0x2ab116877b7b6839ULL, 0xb189fec8b0994d6eULL },
577 : { 0x16a5916132482fd8ULL, 0xa7c48eb9f12b7d37ULL },
578 : { 0x6d24a54c0e51b961ULL, 0x701631d776a5b0e2ULL },
579 : { 0x7a39bf1767d47a89ULL, 0x6bd08da7d7095b7aULL },
580 : { 0x11c7f9a173bf8d4eULL, 0x451390b96dcad08dULL },
581 : { 0x10411fef57d4fca4ULL, 0x49bd093dc8d7e040ULL },
582 : { 0x001079a900860713ULL, 0x81ab2baf1bf59632ULL },
583 : { 0x4b1b9ca618b2a5feULL, 0x152cb5a46ef65f99ULL },
584 : { 0x036db8c22ffea95bULL, 0x08a263ec4de57fa9ULL },
585 : { 0x64861ee83b7d6ddaULL, 0xd344a694800cea8cULL },
586 : { 0, 0 }
587 : };
588 :
589 1 : void test_hash(void)
590 : {
591 : unsigned i;
592 : unsigned char buffer[16];
593 1 : unsigned COUNT = 1024*1024*16;
594 : tommy_uint32_t hash32;
595 : tommy_uint64_t hash64;
596 :
597 1 : START("hash_test_vectors");
598 :
599 24 : for(i=0;HASH32[i].data;++i) {
600 23 : if (tommy_hash_u32(0xa766795d, HASH32[i].data, HASH32[i].len) != HASH32[i].hash)
601 : /* LCOV_EXCL_START */
602 : abort();
603 : /* LCOV_EXCL_STOP */
604 : }
605 :
606 24 : for(i=0;STRHASH32[i].data;++i) {
607 23 : if (tommy_strhash_u32(0xa766795d, STRHASH32[i].data) != STRHASH32[i].hash)
608 : /* LCOV_EXCL_START */
609 : abort();
610 : /* LCOV_EXCL_STOP */
611 : }
612 :
613 24 : for(i=0;HASH64[i].data;++i) {
614 23 : if (tommy_hash_u64(0x2f022773a766795dULL, HASH64[i].data, HASH64[i].len) != HASH64[i].hash)
615 : /* LCOV_EXCL_START */
616 : abort();
617 : /* LCOV_EXCL_STOP */
618 : }
619 :
620 66 : for(i=0;INTHASH32[i].value || !i;++i) {
621 65 : if (tommy_inthash_u32(INTHASH32[i].value) != INTHASH32[i].hash)
622 : /* LCOV_EXCL_START */
623 : abort();
624 : /* LCOV_EXCL_STOP */
625 : }
626 :
627 98 : for(i=0;INTHASH64[i].value || !i;++i) {
628 97 : if (tommy_inthash_u64(INTHASH64[i].value) != INTHASH64[i].hash)
629 : /* LCOV_EXCL_START */
630 : abort();
631 : /* LCOV_EXCL_STOP */
632 : }
633 :
634 1 : STOP();
635 :
636 1 : memset(buffer, 0xAA, sizeof(buffer));
637 1 : buffer[sizeof(buffer) - 1] = 0;
638 :
639 1 : hash32 = 0;
640 1 : hash64 = 0;
641 :
642 1 : START("hash_u32");
643 :
644 16777217 : for(i=0;i<COUNT;++i) {
645 16777216 : hash32 = tommy_hash_u32(hash32, buffer, sizeof(buffer));
646 : }
647 :
648 1 : STOP();
649 :
650 1 : START("strhash_u32");
651 :
652 16777217 : for(i=0;i<COUNT;++i) {
653 16777216 : hash32 = tommy_strhash_u32(hash32, buffer);
654 : }
655 :
656 1 : STOP();
657 :
658 1 : START("hash_u64");
659 :
660 16777217 : for(i=0;i<COUNT;++i) {
661 16777216 : hash64 = tommy_hash_u64(hash64, buffer, sizeof(buffer));
662 : }
663 :
664 1 : STOP();
665 1 : }
666 :
667 1 : void test_alloc(void)
668 : {
669 1 : const unsigned size = 10 * TOMMY_SIZE;
670 : unsigned i;
671 : tommy_allocator alloc;
672 : void** PTR;
673 :
674 1 : PTR = malloc(size * sizeof(void*));
675 :
676 : /* ensure at least pointer alignment */
677 1 : tommy_allocator_init(&alloc, sizeof(void*), 1);
678 1 : if (alloc.align_size < sizeof(void*))
679 : /* LCOV_EXCL_START */
680 : abort();
681 : /* LCOV_EXCL_STOP */
682 1 : tommy_allocator_done(&alloc);
683 :
684 : /* ensure correct alignment */
685 1 : tommy_allocator_init(&alloc, sizeof(void*) - 1, sizeof(void*));
686 1 : if (alloc.block_size != sizeof(void*))
687 : /* LCOV_EXCL_START */
688 : abort();
689 : /* LCOV_EXCL_STOP */
690 1 : tommy_allocator_done(&alloc);
691 :
692 : /* check big blocks */
693 1 : tommy_allocator_init(&alloc, 128000, 64);
694 1 : if (tommy_allocator_alloc(&alloc) == 0)
695 : /* LCOV_EXCL_START */
696 : abort();
697 : /* LCOV_EXCL_STOP */
698 1 : tommy_allocator_done(&alloc);
699 :
700 1 : tommy_allocator_init(&alloc, 64, 64);
701 :
702 1 : START("alloc");
703 10000001 : for(i=0;i<size;++i) {
704 10000000 : PTR[i] = tommy_allocator_alloc(&alloc);
705 : }
706 1 : STOP();
707 :
708 1 : START("free");
709 10000001 : for(i=0;i<size;++i) {
710 10000000 : tommy_allocator_free(&alloc, PTR[i]);
711 : }
712 1 : STOP();
713 :
714 1 : tommy_allocator_done(&alloc);
715 :
716 1 : free(PTR);
717 1 : }
718 :
719 5 : void test_list_order(tommy_node* list)
720 : {
721 : tommy_node* node;
722 :
723 5 : node = list;
724 5000010 : while (node) {
725 5000000 : if (node->next) {
726 4999995 : const struct object* a = node->data;
727 4999995 : const struct object* b = node->next->data;
728 : /* check order */
729 4999995 : if (a->value > b->value)
730 : /* LCOV_EXCL_START */
731 : abort();
732 : /* LCOV_EXCL_STOP */
733 : /* check order for stable sort */
734 4999995 : if (a->value == b->value && a > b)
735 : /* LCOV_EXCL_START */
736 : abort();
737 : /* LCOV_EXCL_STOP */
738 : }
739 5000000 : node = node->next;
740 : }
741 5 : }
742 :
743 1 : void test_list(void)
744 : {
745 : struct object* LIST;
746 : struct object_vector* VECTOR;
747 : tommy_node* list;
748 : unsigned i;
749 1 : const unsigned size = TOMMY_SIZE;
750 :
751 1 : LIST = malloc(size * sizeof(struct object));
752 1 : VECTOR = malloc(size * sizeof(struct object_vector));
753 :
754 1000001 : for(i=0;i<size;++i) {
755 1000000 : VECTOR[i].value = LIST[i].value = 0;
756 : }
757 :
758 1 : tommy_list_init(&list);
759 :
760 : /* sort an empty list */
761 1 : tommy_list_sort(&list, compare);
762 :
763 1 : if (!tommy_list_empty(&list))
764 : /* LCOV_EXCL_START */
765 : abort();
766 : /* LCOV_EXCL_STOP */
767 :
768 1 : if (tommy_list_tail(&list) != 0)
769 : /* LCOV_EXCL_START */
770 : abort();
771 : /* LCOV_EXCL_STOP */
772 :
773 1 : if (tommy_list_head(&list) != 0)
774 : /* LCOV_EXCL_START */
775 : abort();
776 : /* LCOV_EXCL_STOP */
777 :
778 1000001 : for(i=0;i<size;++i) {
779 1000000 : VECTOR[i].value = LIST[i].value = rnd(size);
780 1000000 : tommy_list_insert_tail(&list, &LIST[i].node, &LIST[i]);
781 : }
782 :
783 1 : if (tommy_list_tail(&list) == 0)
784 : /* LCOV_EXCL_START */
785 : abort();
786 : /* LCOV_EXCL_STOP */
787 :
788 1 : if (tommy_list_head(&list) == 0)
789 : /* LCOV_EXCL_START */
790 : abort();
791 : /* LCOV_EXCL_STOP */
792 :
793 1 : START("sort random");
794 1 : tommy_list_sort(&list, compare);
795 1 : STOP();
796 :
797 1 : START("C qsort random");
798 1 : qsort(VECTOR, size, sizeof(VECTOR[0]), compare_vector);
799 1 : STOP();
800 :
801 1 : test_list_order(list);
802 :
803 : /* forward order with some (1%) random values */
804 1 : list = 0;
805 1000001 : for(i=0;i<size;++i) {
806 1000000 : VECTOR[i].value = LIST[i].value = i;
807 1000000 : if (rnd(100) == 0)
808 9981 : VECTOR[i].value = LIST[i].value = rnd(size);
809 1000000 : tommy_list_insert_tail(&list, &LIST[i].node, &LIST[i]);
810 : }
811 :
812 1 : START("sort partially ordered");
813 1 : tommy_list_sort(&list, compare);
814 1 : STOP();
815 :
816 1 : START("C qsort partially ordered");
817 1 : qsort(VECTOR, size, sizeof(VECTOR[0]), compare_vector);
818 1 : STOP();
819 :
820 1 : test_list_order(list);
821 :
822 : /* forward order */
823 1 : list = 0;
824 1000001 : for(i=0;i<size;++i) {
825 1000000 : VECTOR[i].value = LIST[i].value = i;
826 1000000 : tommy_list_insert_tail(&list, &LIST[i].node, &LIST[i]);
827 : }
828 :
829 1 : START("sort forward");
830 1 : tommy_list_sort(&list, compare);
831 1 : STOP();
832 :
833 1 : START("C qsort forward");
834 1 : qsort(VECTOR, size, sizeof(VECTOR[0]), compare_vector);
835 1 : STOP();
836 :
837 1 : test_list_order(list);
838 :
839 : /* backward order */
840 1 : list = 0;
841 1000001 : for(i=0;i<size;++i) {
842 1000000 : VECTOR[i].value = LIST[i].value = size - 1 - i;
843 1000000 : tommy_list_insert_tail(&list, &LIST[i].node, &LIST[i]);
844 : }
845 :
846 1 : START("sort backward");
847 1 : tommy_list_sort(&list, compare);
848 1 : STOP();
849 :
850 1 : START("C qsort backward");
851 1 : qsort(VECTOR, size, sizeof(VECTOR[0]), compare_vector);
852 1 : STOP();
853 :
854 1 : test_list_order(list);
855 :
856 : /* use a small range of random value to insert a lot of duplicates */
857 1 : list = 0;
858 1000001 : for(i=0;i<size;++i) {
859 1000000 : VECTOR[i].value = LIST[i].value = rnd(size / 1000 + 2);
860 1000000 : tommy_list_insert_tail(&list, &LIST[i].node, &LIST[i]);
861 : }
862 :
863 1 : START("sort random duplicate");
864 1 : tommy_list_sort(&list, compare);
865 1 : STOP();
866 :
867 1 : START("C qsort random duplicate");
868 1 : qsort(VECTOR, size, sizeof(VECTOR[0]), compare_vector);
869 1 : STOP();
870 :
871 1 : test_list_order(list);
872 :
873 1 : free(LIST);
874 1 : free(VECTOR);
875 1 : }
876 :
877 1 : void test_tree(void)
878 : {
879 : tommy_tree tree;
880 : struct object_tree* OBJ;
881 : unsigned i;
882 1 : const unsigned size = TOMMY_SIZE / 4;
883 :
884 1 : OBJ = malloc(size * sizeof(struct object_tree));
885 :
886 1 : START("tree");
887 1 : tommy_tree_init(&tree, &compare);
888 :
889 : /* forward order */
890 250001 : for(i=0;i<size;++i)
891 250000 : OBJ[i].value = i;
892 :
893 : /* insert */
894 250001 : for(i=0;i<size;++i)
895 250000 : if (tommy_tree_insert(&tree, &OBJ[i].node, &OBJ[i]) != &OBJ[i])
896 : /* LCOV_EXCL_START */
897 : abort();
898 : /* LCOV_EXCL_STOP */
899 :
900 1 : if (tommy_tree_memory_usage(&tree) < size * sizeof(tommy_tree_node))
901 : /* LCOV_EXCL_START */
902 : abort();
903 : /* LCOV_EXCL_STOP */
904 :
905 1 : if (tommy_tree_count(&tree) != size)
906 : /* LCOV_EXCL_START */
907 : abort();
908 : /* LCOV_EXCL_STOP */
909 :
910 1 : the_count = 0;
911 1 : tommy_tree_foreach(&tree, count_callback);
912 1 : if (the_count != size)
913 : /* LCOV_EXCL_START */
914 : abort();
915 : /* LCOV_EXCL_STOP */
916 :
917 1 : the_count = 0;
918 1 : tommy_tree_foreach_arg(&tree, count_arg_callback, &the_count);
919 1 : if (the_count != size)
920 : /* LCOV_EXCL_START */
921 : abort();
922 : /* LCOV_EXCL_STOP */
923 :
924 : /* search present */
925 125001 : for(i=0;i<size/2;++i) {
926 125000 : if (tommy_tree_search(&tree, &OBJ[i]) == 0)
927 : /* LCOV_EXCL_START */
928 : abort();
929 : /* LCOV_EXCL_STOP */
930 125000 : if (tommy_tree_search_compare(&tree, &compare, &OBJ[i]) == 0)
931 : /* LCOV_EXCL_START */
932 : abort();
933 : /* LCOV_EXCL_STOP */
934 : }
935 :
936 : /* insert existing */
937 250001 : for(i=0;i<size;++i) {
938 : struct object_tree EXTRA;
939 250000 : EXTRA.value = i;
940 250000 : if (tommy_tree_insert(&tree, &EXTRA.node, &EXTRA) == &EXTRA)
941 : /* LCOV_EXCL_START */
942 : abort();
943 : /* LCOV_EXCL_STOP */
944 : }
945 :
946 : /* remove existing */
947 125001 : for(i=0;i<size/2;++i)
948 125000 : tommy_tree_remove_existing(&tree, &OBJ[i].node);
949 :
950 : /* remove missing */
951 125001 : for(i=0;i<size/2;++i)
952 125000 : if (tommy_tree_remove(&tree, &OBJ[i]) != 0)
953 : /* LCOV_EXCL_START */
954 : abort();
955 : /* LCOV_EXCL_STOP */
956 :
957 : /* search missing */
958 125001 : for(i=0;i<size/2;++i) {
959 125000 : if (tommy_tree_search(&tree, &OBJ[i]) != 0)
960 : /* LCOV_EXCL_START */
961 : abort();
962 : /* LCOV_EXCL_STOP */
963 125000 : if (tommy_tree_search_compare(&tree, &compare, &OBJ[i]) != 0)
964 : /* LCOV_EXCL_START */
965 : abort();
966 : /* LCOV_EXCL_STOP */
967 : }
968 :
969 : /* remove present */
970 125001 : for(i=0;i<size/2;++i)
971 125000 : if (tommy_tree_remove(&tree, &OBJ[size/2+i]) == 0)
972 : /* LCOV_EXCL_START */
973 : abort();
974 : /* LCOV_EXCL_STOP */
975 :
976 : /* reverse order */
977 250001 : for(i=0;i<size;++i)
978 250000 : OBJ[i].value = size - i;
979 :
980 : /* insert */
981 250001 : for(i=0;i<size;++i)
982 250000 : if (tommy_tree_insert(&tree, &OBJ[i].node, &OBJ[i]) != &OBJ[i])
983 : /* LCOV_EXCL_START */
984 : abort();
985 : /* LCOV_EXCL_STOP */
986 :
987 : /* remove all */
988 250001 : for(i=0;i<size;++i)
989 250000 : tommy_tree_remove_existing(&tree, &OBJ[i].node);
990 :
991 : /* random order */
992 250001 : for(i=0;i<size;++i)
993 250000 : OBJ[i].value = tommy_inthash_u32(i);
994 :
995 : /* insert */
996 250001 : for(i=0;i<size;++i)
997 250000 : if (tommy_tree_insert(&tree, &OBJ[i].node, &OBJ[i]) != &OBJ[i])
998 : /* LCOV_EXCL_START */
999 : abort();
1000 : /* LCOV_EXCL_STOP */
1001 :
1002 : /* remove all */
1003 250001 : for(i=0;i<size;++i)
1004 250000 : tommy_tree_remove_existing(&tree, &OBJ[i].node);
1005 :
1006 1 : STOP();
1007 1 : }
1008 :
1009 1 : void test_array(void)
1010 : {
1011 : tommy_array array;
1012 : tommy_uintptr_t i;
1013 1 : const unsigned size = 50 * TOMMY_SIZE;
1014 :
1015 1 : tommy_array_init(&array);
1016 :
1017 : /* no op */
1018 1 : tommy_array_grow(&array, 0);
1019 :
1020 1 : START("array init");
1021 50000001 : for(i=0;i<size;++i) {
1022 50000000 : tommy_array_grow(&array, i + 1);
1023 50000000 : if (tommy_array_get(&array, i) != 0)
1024 : /* LCOV_EXCL_START */
1025 : abort();
1026 : /* LCOV_EXCL_STOP */
1027 : }
1028 1 : STOP();
1029 :
1030 1 : START("array set");
1031 50000001 : for(i=0;i<size;++i) {
1032 50000000 : tommy_array_set(&array, i, (void*)i);
1033 : }
1034 1 : STOP();
1035 :
1036 1 : START("array get");
1037 50000001 : for(i=0;i<size;++i) {
1038 50000000 : if (tommy_array_get(&array, i) != (void*)i)
1039 : /* LCOV_EXCL_START */
1040 : abort();
1041 : /* LCOV_EXCL_STOP */
1042 : }
1043 1 : STOP();
1044 :
1045 1 : if (tommy_array_memory_usage(&array) < size * sizeof(void*))
1046 : /* LCOV_EXCL_START */
1047 : abort();
1048 : /* LCOV_EXCL_STOP */
1049 :
1050 1 : tommy_array_done(&array);
1051 1 : }
1052 :
1053 1 : void test_arrayof(void)
1054 : {
1055 : tommy_arrayof arrayof;
1056 : unsigned i;
1057 1 : const unsigned size = 50 * TOMMY_SIZE;
1058 :
1059 1 : tommy_arrayof_init(&arrayof, sizeof(unsigned));
1060 :
1061 : /* no op */
1062 1 : tommy_arrayof_grow(&arrayof, 0);
1063 :
1064 1 : START("arrayof init");
1065 50000001 : for(i=0;i<size;++i) {
1066 50000000 : tommy_arrayof_grow(&arrayof, i + 1);
1067 50000000 : unsigned* ref = tommy_arrayof_ref(&arrayof, i);
1068 50000000 : if (*ref != 0)
1069 : /* LCOV_EXCL_START */
1070 : abort();
1071 : /* LCOV_EXCL_STOP */
1072 : }
1073 1 : STOP();
1074 :
1075 1 : START("arrayof set");
1076 50000001 : for(i=0;i<size;++i) {
1077 50000000 : unsigned* ref = tommy_arrayof_ref(&arrayof, i);
1078 50000000 : *ref = i;
1079 : }
1080 1 : STOP();
1081 :
1082 1 : START("arrayof get");
1083 50000001 : for(i=0;i<size;++i) {
1084 50000000 : unsigned* ref = tommy_arrayof_ref(&arrayof, i);
1085 50000000 : if (*ref != i)
1086 : /* LCOV_EXCL_START */
1087 : abort();
1088 : /* LCOV_EXCL_STOP */
1089 : }
1090 1 : STOP();
1091 :
1092 1 : if (tommy_arrayof_memory_usage(&arrayof) < size * sizeof(unsigned))
1093 : /* LCOV_EXCL_START */
1094 : abort();
1095 : /* LCOV_EXCL_STOP */
1096 :
1097 1 : tommy_arrayof_done(&arrayof);
1098 1 : }
1099 :
1100 1 : void test_arrayblk(void)
1101 : {
1102 : tommy_arrayblk arrayblk;
1103 : tommy_uintptr_t i;
1104 1 : const unsigned size = 50 * TOMMY_SIZE;
1105 :
1106 1 : tommy_arrayblk_init(&arrayblk);
1107 :
1108 : /* no op */
1109 1 : tommy_arrayblk_grow(&arrayblk, 0);
1110 :
1111 1 : START("arrayblk init");
1112 50000001 : for(i=0;i<size;++i) {
1113 50000000 : tommy_arrayblk_grow(&arrayblk, i + 1);
1114 50000000 : if (tommy_arrayblk_get(&arrayblk, i) != 0)
1115 : /* LCOV_EXCL_START */
1116 : abort();
1117 : /* LCOV_EXCL_STOP */
1118 : }
1119 1 : STOP();
1120 :
1121 1 : START("arrayblk set");
1122 50000001 : for(i=0;i<size;++i) {
1123 50000000 : tommy_arrayblk_set(&arrayblk, i, (void*)i);
1124 : }
1125 1 : STOP();
1126 :
1127 1 : START("arrayblk get");
1128 50000001 : for(i=0;i<size;++i) {
1129 50000000 : if (tommy_arrayblk_get(&arrayblk, i) != (void*)i)
1130 : /* LCOV_EXCL_START */
1131 : abort();
1132 : /* LCOV_EXCL_STOP */
1133 : }
1134 1 : STOP();
1135 :
1136 1 : if (tommy_arrayblk_memory_usage(&arrayblk) < size * sizeof(void*))
1137 : /* LCOV_EXCL_START */
1138 : abort();
1139 : /* LCOV_EXCL_STOP */
1140 :
1141 1 : tommy_arrayblk_done(&arrayblk);
1142 1 : }
1143 :
1144 1 : void test_arrayblkof(void)
1145 : {
1146 : tommy_arrayblkof arrayblkof;
1147 : unsigned i;
1148 1 : const unsigned size = 50 * TOMMY_SIZE;
1149 :
1150 1 : tommy_arrayblkof_init(&arrayblkof, sizeof(unsigned));
1151 :
1152 : /* no op */
1153 1 : tommy_arrayblkof_grow(&arrayblkof, 0);
1154 :
1155 1 : START("arrayblkof init");
1156 50000001 : for(i=0;i<size;++i) {
1157 50000000 : tommy_arrayblkof_grow(&arrayblkof, i + 1);
1158 50000000 : unsigned* ref = tommy_arrayblkof_ref(&arrayblkof, i);
1159 50000000 : if (*ref != 0)
1160 : /* LCOV_EXCL_START */
1161 : abort();
1162 : /* LCOV_EXCL_STOP */
1163 : }
1164 1 : STOP();
1165 :
1166 1 : START("arrayblkof set");
1167 50000001 : for(i=0;i<size;++i) {
1168 50000000 : unsigned* ref = tommy_arrayblkof_ref(&arrayblkof, i);
1169 50000000 : *ref = i;
1170 : }
1171 1 : STOP();
1172 :
1173 1 : START("arrayblkof get");
1174 50000001 : for(i=0;i<size;++i) {
1175 50000000 : unsigned* ref = tommy_arrayblkof_ref(&arrayblkof, i);
1176 50000000 : if (*ref != i)
1177 : /* LCOV_EXCL_START */
1178 : abort();
1179 : /* LCOV_EXCL_STOP */
1180 : }
1181 1 : STOP();
1182 :
1183 1 : if (tommy_arrayblkof_memory_usage(&arrayblkof) < size * sizeof(unsigned))
1184 : /* LCOV_EXCL_START */
1185 : abort();
1186 : /* LCOV_EXCL_STOP */
1187 :
1188 1 : tommy_arrayblkof_done(&arrayblkof);
1189 1 : }
1190 :
1191 1 : void test_hashtable(void)
1192 : {
1193 : tommy_hashtable hashtable;
1194 : struct object_hash* HASH;
1195 : unsigned i, j, n;
1196 : unsigned limit;
1197 1 : const unsigned size = TOMMY_SIZE;
1198 1 : const unsigned module = TOMMY_SIZE / 4;
1199 :
1200 1 : HASH = malloc(size * sizeof(struct object_hash));
1201 :
1202 1000001 : for(i=0;i<size;++i)
1203 1000000 : HASH[i].value = i % module;
1204 :
1205 : /* initialize a very small hashtable */
1206 1 : tommy_hashtable_init(&hashtable, 1);
1207 :
1208 : /* check that we allocated space for more elements */
1209 1 : if (hashtable.bucket_max == 1)
1210 : /* LCOV_EXCL_START */
1211 : abort();
1212 : /* LCOV_EXCL_STOP */
1213 :
1214 : /* destroy it as empty */
1215 1 : tommy_hashtable_done(&hashtable);
1216 :
1217 1 : START("hashtable stack");
1218 1 : limit = 5 * isqrt(size);
1219 5002 : for(n=0;n<=limit;++n) {
1220 : /* last iteration is full size */
1221 5001 : if (n == limit)
1222 1 : n = limit = size;
1223 :
1224 5001 : tommy_hashtable_init(&hashtable, limit / 2);
1225 :
1226 : /* insert */
1227 13502501 : for(i=0;i<n;++i)
1228 13497500 : tommy_hashtable_insert(&hashtable, &HASH[i].node, &HASH[i], HASH[i].value);
1229 :
1230 5001 : if (tommy_hashtable_memory_usage(&hashtable) < n * sizeof(void*))
1231 : /* LCOV_EXCL_START */
1232 : abort();
1233 : /* LCOV_EXCL_STOP */
1234 :
1235 5001 : if (tommy_hashtable_count(&hashtable) != n)
1236 : /* LCOV_EXCL_START */
1237 : abort();
1238 : /* LCOV_EXCL_STOP */
1239 :
1240 5001 : the_count = 0;
1241 5001 : tommy_hashtable_foreach(&hashtable, count_callback);
1242 5001 : if (the_count != n)
1243 : /* LCOV_EXCL_START */
1244 : abort();
1245 : /* LCOV_EXCL_STOP */
1246 :
1247 : /* remove in backward order */
1248 6752501 : for(i=0;i<n/2;++i)
1249 6747500 : tommy_hashtable_remove_existing(&hashtable, &HASH[n-i-1].node);
1250 :
1251 : /* remove missing */
1252 6752501 : for(i=0;i<n/2;++i)
1253 6747500 : if (tommy_hashtable_remove(&hashtable, search_callback, &HASH[n-i-1], HASH[n-i-1].value) != 0)
1254 : /* LCOV_EXCL_START */
1255 : abort();
1256 : /* LCOV_EXCL_STOP */
1257 :
1258 : /* remove search */
1259 6752501 : for(i=0;i<n/2;++i)
1260 6747500 : if (tommy_hashtable_remove(&hashtable, search_callback, &HASH[n/2-i-1], HASH[n/2-i-1].value) == 0)
1261 : /* LCOV_EXCL_START */
1262 : abort();
1263 : /* LCOV_EXCL_STOP */
1264 :
1265 5001 : tommy_hashtable_done(&hashtable);
1266 : }
1267 1 : STOP();
1268 :
1269 1 : START("hashtable queue");
1270 1 : limit = isqrt(size) / 16;
1271 64 : for(n=0;n<=limit;++n) {
1272 : /* last iteration is full size */
1273 63 : if (n == limit)
1274 1 : n = limit = size;
1275 :
1276 63 : tommy_hashtable_init(&hashtable, limit / 2);
1277 :
1278 : /* insert first run */
1279 1001954 : for(j=0,i=0;i<n;++i)
1280 1001891 : tommy_hashtable_insert(&hashtable, &HASH[i].node, &HASH[i], HASH[i].value);
1281 :
1282 63 : the_count = 0;
1283 63 : tommy_hashtable_foreach_arg(&hashtable, count_arg_callback, &the_count);
1284 63 : if (the_count != n)
1285 : /* LCOV_EXCL_START */
1286 : abort();
1287 : /* LCOV_EXCL_STOP */
1288 :
1289 : /* insert all the others */
1290 61998172 : for(;i<size;++i,++j) {
1291 : /* insert one */
1292 61998109 : tommy_hashtable_insert(&hashtable, &HASH[i].node, &HASH[i], HASH[i].value);
1293 :
1294 : /* remove one */
1295 61998109 : tommy_hashtable_remove_existing(&hashtable, &HASH[j].node);
1296 : }
1297 :
1298 1001954 : for(;j<size;++j)
1299 1001891 : if (tommy_hashtable_remove(&hashtable, search_callback, &HASH[j], HASH[j].value) == 0)
1300 : /* LCOV_EXCL_START */
1301 : abort();
1302 : /* LCOV_EXCL_STOP */
1303 :
1304 63 : tommy_hashtable_done(&hashtable);
1305 : }
1306 1 : STOP();
1307 1 : }
1308 :
1309 1 : void test_hashdyn(void)
1310 : {
1311 : tommy_hashdyn hashdyn;
1312 : struct object_hash* HASH;
1313 : unsigned i, j, n;
1314 : unsigned limit;
1315 1 : const unsigned size = TOMMY_SIZE;
1316 1 : const unsigned module = TOMMY_SIZE / 4;
1317 :
1318 1 : HASH = malloc(size * sizeof(struct object_hash));
1319 :
1320 1000001 : for(i=0;i<size;++i)
1321 1000000 : HASH[i].value = i % module;
1322 :
1323 1 : START("hashdyn stack");
1324 1 : limit = 5 * isqrt(size);
1325 5002 : for(n=0;n<=limit;++n) {
1326 : /* last iteration is full size */
1327 5001 : if (n == limit)
1328 1 : n = limit = size;
1329 :
1330 5001 : tommy_hashdyn_init(&hashdyn);
1331 :
1332 : /* insert */
1333 13502501 : for(i=0;i<n;++i)
1334 13497500 : tommy_hashdyn_insert(&hashdyn, &HASH[i].node, &HASH[i], HASH[i].value);
1335 :
1336 5001 : if (tommy_hashdyn_memory_usage(&hashdyn) < n * sizeof(void*))
1337 : /* LCOV_EXCL_START */
1338 : abort();
1339 : /* LCOV_EXCL_STOP */
1340 :
1341 5001 : if (tommy_hashdyn_count(&hashdyn) != n)
1342 : /* LCOV_EXCL_START */
1343 : abort();
1344 : /* LCOV_EXCL_STOP */
1345 :
1346 5001 : the_count = 0;
1347 5001 : tommy_hashdyn_foreach(&hashdyn, count_callback);
1348 5001 : if (the_count != n)
1349 : /* LCOV_EXCL_START */
1350 : abort();
1351 : /* LCOV_EXCL_STOP */
1352 :
1353 : /* remove in backward order */
1354 6752501 : for(i=0;i<n/2;++i)
1355 6747500 : tommy_hashdyn_remove_existing(&hashdyn, &HASH[n-i-1].node);
1356 :
1357 : /* remove missing */
1358 6752501 : for(i=0;i<n/2;++i)
1359 6747500 : if (tommy_hashdyn_remove(&hashdyn, search_callback, &HASH[n-i-1], HASH[n-i-1].value) != 0)
1360 : /* LCOV_EXCL_START */
1361 : abort();
1362 : /* LCOV_EXCL_STOP */
1363 :
1364 : /* remove search */
1365 6752501 : for(i=0;i<n/2;++i)
1366 6747500 : if (tommy_hashdyn_remove(&hashdyn, search_callback, &HASH[n/2-i-1], HASH[n/2-i-1].value) == 0)
1367 : /* LCOV_EXCL_START */
1368 : abort();
1369 : /* LCOV_EXCL_STOP */
1370 :
1371 5001 : tommy_hashdyn_done(&hashdyn);
1372 : }
1373 1 : STOP();
1374 :
1375 1 : START("hashdyn queue");
1376 1 : limit = isqrt(size) / 16;
1377 64 : for(n=0;n<=limit;++n) {
1378 : /* last iteration is full size */
1379 63 : if (n == limit)
1380 1 : n = limit = size;
1381 :
1382 63 : tommy_hashdyn_init(&hashdyn);
1383 :
1384 : /* insert first run */
1385 1001954 : for(j=0,i=0;i<n;++i)
1386 1001891 : tommy_hashdyn_insert(&hashdyn, &HASH[i].node, &HASH[i], HASH[i].value);
1387 :
1388 63 : the_count = 0;
1389 63 : tommy_hashdyn_foreach_arg(&hashdyn, count_arg_callback, &the_count);
1390 63 : if (the_count != n)
1391 : /* LCOV_EXCL_START */
1392 : abort();
1393 : /* LCOV_EXCL_STOP */
1394 :
1395 : /* insert all the others */
1396 61998172 : for(;i<size;++i,++j) {
1397 : /* insert one */
1398 61998109 : tommy_hashdyn_insert(&hashdyn, &HASH[i].node, &HASH[i], HASH[i].value);
1399 :
1400 : /* remove one */
1401 61998109 : tommy_hashdyn_remove_existing(&hashdyn, &HASH[j].node);
1402 : }
1403 :
1404 1001954 : for(;j<size;++j)
1405 1001891 : if (tommy_hashdyn_remove(&hashdyn, search_callback, &HASH[j], HASH[j].value) == 0)
1406 : /* LCOV_EXCL_START */
1407 : abort();
1408 : /* LCOV_EXCL_STOP */
1409 :
1410 63 : tommy_hashdyn_done(&hashdyn);
1411 : }
1412 1 : STOP();
1413 1 : }
1414 :
1415 1 : void test_hashlin(void)
1416 : {
1417 : tommy_hashlin hashlin;
1418 : struct object_hash* HASH;
1419 : unsigned i, j, n;
1420 : unsigned limit;
1421 1 : const unsigned size = TOMMY_SIZE;
1422 1 : const unsigned module = TOMMY_SIZE / 4;
1423 : tommy_hashlin_node* bucket;
1424 :
1425 1 : HASH = malloc(size * sizeof(struct object_hash));
1426 :
1427 1000001 : for(i=0;i<size;++i)
1428 1000000 : HASH[i].value = i % module;
1429 :
1430 1 : tommy_hashlin_init(&hashlin);
1431 :
1432 : /* insert */
1433 1000001 : for(i=0;i<size;++i)
1434 1000000 : tommy_hashlin_insert(&hashlin, &HASH[i].node, &HASH[i], HASH[i].value);
1435 :
1436 : /* get the bucket of the last element */
1437 1 : bucket = tommy_hashlin_bucket(&hashlin, module - 1);
1438 1 : if (bucket == 0)
1439 : /* LCOV_EXCL_START */
1440 : abort();
1441 : /* LCOV_EXCL_STOP */
1442 :
1443 : /* deinitialize without removing elements to force deallocation */
1444 1 : tommy_hashlin_done(&hashlin);
1445 :
1446 1 : START("hashlin stack");
1447 1 : limit = 5 * isqrt(size);
1448 5002 : for(n=0;n<=limit;++n) {
1449 : /* last iteration is full size */
1450 5001 : if (n == limit)
1451 1 : n = limit = size;
1452 :
1453 5001 : tommy_hashlin_init(&hashlin);
1454 :
1455 : /* insert */
1456 13502501 : for(i=0;i<n;++i)
1457 13497500 : tommy_hashlin_insert(&hashlin, &HASH[i].node, &HASH[i], HASH[i].value);
1458 :
1459 5001 : if (tommy_hashlin_memory_usage(&hashlin) < n * sizeof(void*))
1460 : /* LCOV_EXCL_START */
1461 : abort();
1462 : /* LCOV_EXCL_STOP */
1463 :
1464 5001 : if (tommy_hashlin_count(&hashlin) != n)
1465 : /* LCOV_EXCL_START */
1466 : abort();
1467 : /* LCOV_EXCL_STOP */
1468 :
1469 5001 : the_count = 0;
1470 5001 : tommy_hashlin_foreach(&hashlin, count_callback);
1471 5001 : if (the_count != n)
1472 : /* LCOV_EXCL_START */
1473 : abort();
1474 : /* LCOV_EXCL_STOP */
1475 :
1476 : /* remove in backward order */
1477 6752501 : for(i=0;i<n/2;++i)
1478 6747500 : tommy_hashlin_remove_existing(&hashlin, &HASH[n-i-1].node);
1479 :
1480 : /* remove missing */
1481 6752501 : for(i=0;i<n/2;++i)
1482 6747500 : if (tommy_hashlin_remove(&hashlin, search_callback, &HASH[n-i-1], HASH[n-i-1].value) != 0)
1483 : /* LCOV_EXCL_START */
1484 : abort();
1485 : /* LCOV_EXCL_STOP */
1486 :
1487 : /* remove search */
1488 6752501 : for(i=0;i<n/2;++i)
1489 6747500 : if (tommy_hashlin_remove(&hashlin, search_callback, &HASH[n/2-i-1], HASH[n/2-i-1].value) == 0)
1490 : /* LCOV_EXCL_START */
1491 : abort();
1492 : /* LCOV_EXCL_STOP */
1493 :
1494 5001 : tommy_hashlin_done(&hashlin);
1495 : }
1496 1 : STOP();
1497 :
1498 1 : START("hashlin queue");
1499 1 : limit = isqrt(size) / 16;
1500 64 : for(n=0;n<=limit;++n) {
1501 : /* last iteration is full size */
1502 63 : if (n == limit)
1503 1 : n = limit = size;
1504 :
1505 63 : tommy_hashlin_init(&hashlin);
1506 :
1507 : /* insert first run */
1508 1001954 : for(j=0,i=0;i<n;++i)
1509 1001891 : tommy_hashlin_insert(&hashlin, &HASH[i].node, &HASH[i], HASH[i].value);
1510 :
1511 63 : the_count = 0;
1512 63 : tommy_hashlin_foreach_arg(&hashlin, count_arg_callback, &the_count);
1513 63 : if (the_count != n)
1514 : /* LCOV_EXCL_START */
1515 : abort();
1516 : /* LCOV_EXCL_STOP */
1517 :
1518 : /* insert all the others */
1519 61998172 : for(;i<size;++i,++j) {
1520 : /* insert one */
1521 61998109 : tommy_hashlin_insert(&hashlin, &HASH[i].node, &HASH[i], HASH[i].value);
1522 :
1523 : /* remove one */
1524 61998109 : tommy_hashlin_remove_existing(&hashlin, &HASH[j].node);
1525 : }
1526 :
1527 1001954 : for(;j<size;++j)
1528 1001891 : if (tommy_hashlin_remove(&hashlin, search_callback, &HASH[j], HASH[j].value) == 0)
1529 : /* LCOV_EXCL_START */
1530 : abort();
1531 : /* LCOV_EXCL_STOP */
1532 :
1533 63 : tommy_hashlin_done(&hashlin);
1534 : }
1535 1 : STOP();
1536 1 : }
1537 :
1538 1 : void test_trie(void)
1539 : {
1540 : tommy_trie trie;
1541 : tommy_allocator alloc;
1542 : struct object_trie* OBJ;
1543 : struct object_trie DUP[2];
1544 : unsigned i;
1545 1 : const unsigned size = TOMMY_SIZE * 4;
1546 :
1547 1 : OBJ = malloc(size * sizeof(struct object_trie));
1548 :
1549 4000001 : for(i=0;i<size;++i)
1550 4000000 : OBJ[i].value = i;
1551 :
1552 1 : START("trie");
1553 1 : tommy_allocator_init(&alloc, TOMMY_TRIE_BLOCK_SIZE, TOMMY_TRIE_BLOCK_SIZE);
1554 1 : tommy_trie_init(&trie, &alloc);
1555 :
1556 : /* insert */
1557 4000001 : for(i=0;i<size;++i)
1558 4000000 : tommy_trie_insert(&trie, &OBJ[i].node, &OBJ[i], OBJ[i].value);
1559 :
1560 1 : if (tommy_trie_memory_usage(&trie) < size * sizeof(tommy_trie_node))
1561 : /* LCOV_EXCL_START */
1562 : abort();
1563 : /* LCOV_EXCL_STOP */
1564 :
1565 1 : if (tommy_allocator_memory_usage(&alloc) < trie.node_count * TOMMY_TRIE_BLOCK_SIZE)
1566 : /* LCOV_EXCL_START */
1567 : abort();
1568 : /* LCOV_EXCL_STOP */
1569 :
1570 1 : if (tommy_trie_count(&trie) != size)
1571 : /* LCOV_EXCL_START */
1572 : abort();
1573 : /* LCOV_EXCL_STOP */
1574 :
1575 : /* insert duplicate */
1576 3 : for(i=0;i<2;++i) {
1577 2 : DUP[i].value = 0;
1578 2 : tommy_trie_insert(&trie, &DUP[i].node, &DUP[i], DUP[i].value);
1579 : }
1580 :
1581 : /* search present */
1582 2000001 : for(i=0;i<size/2;++i)
1583 2000000 : if (tommy_trie_search(&trie, OBJ[i].value) == 0)
1584 : /* LCOV_EXCL_START */
1585 : abort();
1586 : /* LCOV_EXCL_STOP */
1587 :
1588 : /* remove first duplicate */
1589 1 : tommy_trie_remove_existing(&trie, &DUP[0].node);
1590 :
1591 : /* remove existing */
1592 2000001 : for(i=0;i<size/2;++i)
1593 2000000 : tommy_trie_remove_existing(&trie, &OBJ[i].node);
1594 :
1595 : /* remove missing using the same bucket of the duplicate */
1596 1 : if (tommy_trie_remove(&trie, 1) != 0)
1597 : /* LCOV_EXCL_START */
1598 : abort();
1599 : /* LCOV_EXCL_STOP */
1600 :
1601 : /* search missing using the same bucket of the duplicate */
1602 1 : if (tommy_trie_search(&trie, 1) != 0)
1603 : /* LCOV_EXCL_START */
1604 : abort();
1605 : /* LCOV_EXCL_STOP */
1606 :
1607 : /* remove second duplicate */
1608 1 : tommy_trie_remove_existing(&trie, &DUP[1].node);
1609 :
1610 : /* remove missing */
1611 2000001 : for(i=0;i<size/2;++i)
1612 2000000 : if (tommy_trie_remove(&trie, OBJ[i].value) != 0)
1613 : /* LCOV_EXCL_START */
1614 : abort();
1615 : /* LCOV_EXCL_STOP */
1616 :
1617 : /* search missing */
1618 2000001 : for(i=0;i<size/2;++i)
1619 2000000 : if (tommy_trie_search(&trie, OBJ[i].value) != 0)
1620 : /* LCOV_EXCL_START */
1621 : abort();
1622 : /* LCOV_EXCL_STOP */
1623 :
1624 : /* remove present */
1625 2000001 : for(i=0;i<size/2;++i)
1626 2000000 : if (tommy_trie_remove(&trie, OBJ[size/2+i].value) == 0)
1627 : /* LCOV_EXCL_START */
1628 : abort();
1629 : /* LCOV_EXCL_STOP */
1630 :
1631 1 : tommy_allocator_done(&alloc);
1632 1 : STOP();
1633 1 : }
1634 :
1635 1 : void test_trie_inplace(void)
1636 : {
1637 : tommy_trie_inplace trie_inplace;
1638 : struct object_trie_inplace* OBJ;
1639 : struct object_trie_inplace DUP[2];
1640 : unsigned i;
1641 1 : const unsigned size = TOMMY_SIZE * 4;
1642 :
1643 1 : OBJ = malloc(size * sizeof(struct object_trie_inplace));
1644 :
1645 4000001 : for(i=0;i<size;++i)
1646 4000000 : OBJ[i].value = i;
1647 :
1648 1 : START("trie_inplace");
1649 1 : tommy_trie_inplace_init(&trie_inplace);
1650 :
1651 : /* insert */
1652 4000001 : for(i=0;i<size;++i)
1653 4000000 : tommy_trie_inplace_insert(&trie_inplace, &OBJ[i].node, &OBJ[i], OBJ[i].value);
1654 :
1655 1 : if (tommy_trie_inplace_memory_usage(&trie_inplace) < size * sizeof(tommy_trie_inplace_node))
1656 : /* LCOV_EXCL_START */
1657 : abort();
1658 : /* LCOV_EXCL_STOP */
1659 :
1660 1 : if (tommy_trie_inplace_count(&trie_inplace) != size)
1661 : /* LCOV_EXCL_START */
1662 : abort();
1663 : /* LCOV_EXCL_STOP */
1664 :
1665 : /* insert duplicates */
1666 3 : for(i=0;i<2;++i) {
1667 2 : DUP[i].value = 0;
1668 2 : tommy_trie_inplace_insert(&trie_inplace, &DUP[i].node, &DUP[i], DUP[i].value);
1669 : }
1670 :
1671 : /* search present */
1672 2000001 : for(i=0;i<size/2;++i)
1673 2000000 : if (tommy_trie_inplace_search(&trie_inplace, OBJ[i].value) == 0)
1674 : /* LCOV_EXCL_START */
1675 : abort();
1676 : /* LCOV_EXCL_STOP */
1677 :
1678 : /* remove first duplicate */
1679 1 : tommy_trie_inplace_remove_existing(&trie_inplace, &DUP[0].node);
1680 :
1681 : /* remove existing */
1682 2000001 : for(i=0;i<size/2;++i)
1683 2000000 : tommy_trie_inplace_remove_existing(&trie_inplace, &OBJ[i].node);
1684 :
1685 : /* remove second duplicate */
1686 1 : tommy_trie_inplace_remove_existing(&trie_inplace, &DUP[1].node);
1687 :
1688 : /* remove missing */
1689 2000001 : for(i=0;i<size/2;++i)
1690 2000000 : if (tommy_trie_inplace_remove(&trie_inplace, OBJ[i].value) != 0)
1691 : /* LCOV_EXCL_START */
1692 : abort();
1693 : /* LCOV_EXCL_STOP */
1694 :
1695 : /* search missing */
1696 2000001 : for(i=0;i<size/2;++i)
1697 2000000 : if (tommy_trie_inplace_search(&trie_inplace, OBJ[i].value) != 0)
1698 : /* LCOV_EXCL_START */
1699 : abort();
1700 : /* LCOV_EXCL_STOP */
1701 :
1702 : /* remove present */
1703 2000001 : for(i=0;i<size/2;++i)
1704 2000000 : if (tommy_trie_inplace_remove(&trie_inplace, OBJ[size/2+i].value) == 0)
1705 : /* LCOV_EXCL_START */
1706 : abort();
1707 : /* LCOV_EXCL_STOP */
1708 :
1709 1 : STOP();
1710 1 : }
1711 :
1712 1 : int main() {
1713 1 : nano_init();
1714 :
1715 1 : printf("Tommy check program.\n");
1716 :
1717 1 : test_hash();
1718 1 : test_alloc();
1719 1 : test_list();
1720 1 : test_tree();
1721 1 : test_array();
1722 1 : test_arrayof();
1723 1 : test_arrayblk();
1724 1 : test_arrayblkof();
1725 1 : test_hashtable();
1726 1 : test_hashdyn();
1727 1 : test_hashlin();
1728 1 : test_trie();
1729 1 : test_trie_inplace();
1730 :
1731 1 : printf("OK\n");
1732 :
1733 1 : return EXIT_SUCCESS;
1734 : }
1735 :
|
