?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
TODO epan/dissectors/asn1/kerberos/packet-kerberos-template.c new GSS flags
[wireshark-sm.git] / wsutil / wmem / wmem_test.c
bloba104afa732e7123508cef828f6f587621a734537
1 /* wmem_test.c
2 * Wireshark Memory Manager Tests
3 * Copyright 2012, Evan Huus <eapache@gmail.com>
4 *
5 * Wireshark - Network traffic analyzer
6 * By Gerald Combs <gerald@wireshark.org>
7 * Copyright 1998 Gerald Combs
8 *
9 * SPDX-License-Identifier: GPL-2.0-or-later
10 */
11
12 #include "config.h"
13
14 #include <stdio.h>
15 #include <glib.h>
16
17 #include "wmem.h"
18 #include "wmem_tree-int.h"
19 #include "wmem_allocator.h"
20 #include "wmem_allocator_block.h"
21 #include "wmem_allocator_block_fast.h"
22 #include "wmem_allocator_simple.h"
23 #include "wmem_allocator_strict.h"
24
25 #include <wsutil/time_util.h>
26
27 #define STRING_80 "12345678901234567890123456789012345678901234567890123456789012345678901234567890"
28 #define MAX_ALLOC_SIZE (1024*64)
29 #define MAX_SIMULTANEOUS_ALLOCS 1024
30 #define CONTAINER_ITERS 10000
31
32 typedef void (*wmem_verify_func)(wmem_allocator_t *allocator);
33
34 /* A local copy of wmem_allocator_new that ignores the
35 * WIRESHARK_DEBUG_WMEM_OVERRIDE variable so that test functions are
36 * guaranteed to actually get the allocator type they asked for */
37 static wmem_allocator_t *
38 wmem_allocator_force_new(const wmem_allocator_type_t type)
39 {
40 wmem_allocator_t *allocator;
41
42 allocator = wmem_new(NULL, wmem_allocator_t);
43 allocator->type = type;
44 allocator->callbacks = NULL;
45 allocator->in_scope = true;
46
47 switch (type) {
48 case WMEM_ALLOCATOR_SIMPLE:
49 wmem_simple_allocator_init(allocator);
50 break;
51 case WMEM_ALLOCATOR_BLOCK:
52 wmem_block_allocator_init(allocator);
53 break;
54 case WMEM_ALLOCATOR_BLOCK_FAST:
55 wmem_block_fast_allocator_init(allocator);
56 break;
57 case WMEM_ALLOCATOR_STRICT:
58 wmem_strict_allocator_init(allocator);
59 break;
60 default:
61 g_assert_not_reached();
62 /* This is necessary to squelch MSVC errors; is there
63 any way to tell it that g_assert_not_reached()
64 never returns? */
65 return NULL;
66 };
67
68 return allocator;
69 }
70
71 /* A helper for generating pseudo-random strings. Just uses glib's random number
72 * functions to generate 'numbers' in the printable character range. */
73 static char *
74 wmem_test_rand_string(wmem_allocator_t *allocator, int minlen, int maxlen)
75 {
76 char *str;
77 int len, i;
78
79 len = g_random_int_range(minlen, maxlen);
80
81 /* +1 for null-terminator */
82 str = (char*)wmem_alloc(allocator, len + 1);
83 str[len] = '\0';
84
85 for (i=0; i<len; i++) {
86 /* ASCII normal printable range is 32 (space) to 126 (tilde) */
87 str[i] = (char) g_random_int_range(32, 126);
88 }
89
90 return str;
91 }
92
93 static int
94 wmem_test_compare_uint32(const void *a, const void *b)
95 {
96 uint32_t l, r;
97
98 l = *(const uint32_t*)a;
99 r = *(const uint32_t*)b;
100
101 return l - r;
102 }
103
104 /* Some helpers for properly testing callback functionality */
105 wmem_allocator_t *expected_allocator;
106 void *expected_user_data;
107 wmem_cb_event_t expected_event;
108 int cb_called_count;
109 int cb_continue_count;
110 bool value_seen[CONTAINER_ITERS];
111
112 static bool
113 wmem_test_cb(wmem_allocator_t *allocator, wmem_cb_event_t event,
114 void *user_data)
115 {
116 g_assert_true(allocator == expected_allocator);
117 g_assert_true(event == expected_event);
118
119 cb_called_count++;
120
121 return *(bool*)user_data;
122 }
123
124 static bool
125 wmem_test_foreach_cb(const void *key _U_, void *value, void *user_data)
126 {
127 g_assert_true(user_data == expected_user_data);
128
129 g_assert_true(! value_seen[GPOINTER_TO_INT(value)]);
130 value_seen[GPOINTER_TO_INT(value)] = true;
131
132 cb_called_count++;
133 cb_continue_count--;
134
135 return (cb_continue_count == 0);
136 }
137
138 /* ALLOCATOR TESTING FUNCTIONS (/wmem/allocator/) */
139
140 static void
141 wmem_test_allocator_callbacks(void)
142 {
143 wmem_allocator_t *allocator;
144 bool t = true;
145 bool f = false;
146 unsigned cb_id;
147
148 allocator = wmem_allocator_new(WMEM_ALLOCATOR_STRICT);
149
150 expected_allocator = allocator;
151
152 wmem_register_callback(expected_allocator, &wmem_test_cb, &f);
153 wmem_register_callback(expected_allocator, &wmem_test_cb, &f);
154 cb_id = wmem_register_callback(expected_allocator, &wmem_test_cb, &t);
155 wmem_register_callback(expected_allocator, &wmem_test_cb, &t);
156 wmem_register_callback(expected_allocator, &wmem_test_cb, &f);
157
158 expected_event = WMEM_CB_FREE_EVENT;
159
160 cb_called_count = 0;
161 wmem_free_all(allocator);
162 g_assert_true(cb_called_count == 5);
163
164 cb_called_count = 0;
165 wmem_free_all(allocator);
166 g_assert_true(cb_called_count == 2);
167
168 cb_called_count = 0;
169 wmem_free_all(allocator);
170 g_assert_true(cb_called_count == 2);
171
172 wmem_unregister_callback(allocator, cb_id);
173 cb_called_count = 0;
174 wmem_free_all(allocator);
175 g_assert_true(cb_called_count == 1);
176
177 cb_id = wmem_register_callback(expected_allocator, &wmem_test_cb, &f);
178 wmem_register_callback(expected_allocator, &wmem_test_cb, &t);
179
180 cb_called_count = 0;
181 wmem_free_all(allocator);
182 g_assert_true(cb_called_count == 3);
183
184 wmem_unregister_callback(allocator, cb_id);
185 cb_called_count = 0;
186 wmem_free_all(allocator);
187 g_assert_true(cb_called_count == 2);
188
189 wmem_register_callback(expected_allocator, &wmem_test_cb, &t);
190
191 expected_event = WMEM_CB_DESTROY_EVENT;
192 cb_called_count = 0;
193 wmem_destroy_allocator(allocator);
194 g_assert_true(cb_called_count == 3);
195 }
196
197 static void
198 wmem_test_allocator_det(wmem_allocator_t *allocator, wmem_verify_func verify,
199 unsigned len)
200 {
201 int i;
202 char *ptrs[MAX_SIMULTANEOUS_ALLOCS];
203
204 /* we use wmem_alloc0 in part because it tests slightly more code, but
205 * primarily so that if the allocator doesn't give us enough memory or
206 * gives us memory that includes its own metadata, we write to it and
207 * things go wrong, causing the tests to fail */
208 for (i=0; i<MAX_SIMULTANEOUS_ALLOCS; i++) {
209 ptrs[i] = (char *)wmem_alloc0(allocator, len);
210 }
211 for (i=MAX_SIMULTANEOUS_ALLOCS-1; i>=0; i--) {
212 /* no wmem_realloc0 so just use memset manually */
213 ptrs[i] = (char *)wmem_realloc(allocator, ptrs[i], 4*len);
214 memset(ptrs[i], 0, 4*len);
215 }
216 for (i=0; i<MAX_SIMULTANEOUS_ALLOCS; i++) {
217 wmem_free(allocator, ptrs[i]);
218 }
219
220 if (verify) (*verify)(allocator);
221 wmem_free_all(allocator);
222 wmem_gc(allocator);
223 if (verify) (*verify)(allocator);
224 }
225
226 static void
227 wmem_test_allocator_jumbo(wmem_allocator_type_t type, wmem_verify_func verify)
228 {
229 wmem_allocator_t *allocator;
230 char *ptr, *ptr1;
231
232 allocator = wmem_allocator_force_new(type);
233
234 ptr = (char*)wmem_alloc0(allocator, 4*1024*1024);
235 wmem_free(allocator, ptr);
236 wmem_gc(allocator);
237 ptr = (char*)wmem_alloc0(allocator, 4*1024*1024);
238
239 if (verify) (*verify)(allocator);
240 wmem_free(allocator, ptr);
241 wmem_gc(allocator);
242 if (verify) (*verify)(allocator);
243
244 ptr = (char *)wmem_alloc0(allocator, 10*1024*1024);
245 ptr1 = (char *)wmem_alloc0(allocator, 13*1024*1024);
246 ptr1 = (char *)wmem_realloc(allocator, ptr1, 10*1024*1024);
247 memset(ptr1, 0, 10*1024*1024);
248 ptr = (char *)wmem_realloc(allocator, ptr, 13*1024*1024);
249 memset(ptr, 0, 13*1024*1024);
250 if (verify) (*verify)(allocator);
251 wmem_gc(allocator);
252 if (verify) (*verify)(allocator);
253 wmem_free(allocator, ptr1);
254 if (verify) (*verify)(allocator);
255 wmem_free_all(allocator);
256 wmem_gc(allocator);
257 if (verify) (*verify)(allocator);
258
259 wmem_destroy_allocator(allocator);
260 }
261
262 static void
263 wmem_test_allocator(wmem_allocator_type_t type, wmem_verify_func verify,
264 int iterations)
265 {
266 int i;
267 char *ptrs[MAX_SIMULTANEOUS_ALLOCS];
268 wmem_allocator_t *allocator;
269
270 allocator = wmem_allocator_force_new(type);
271
272 if (verify) (*verify)(allocator);
273
274 /* start with some fairly simple deterministic tests */
275
276 wmem_test_allocator_det(allocator, verify, 8);
277
278 wmem_test_allocator_det(allocator, verify, 64);
279
280 wmem_test_allocator_det(allocator, verify, 512);
281
282 for (i=0; i<MAX_SIMULTANEOUS_ALLOCS; i++) {
283 ptrs[i] = wmem_alloc0_array(allocator, char, 32);
284 }
285
286 if (verify) (*verify)(allocator);
287 wmem_free_all(allocator);
288 wmem_gc(allocator);
289 if (verify) (*verify)(allocator);
290
291 /* now do some random fuzz-like tests */
292
293 /* reset our ptr array */
294 for (i=0; i<MAX_SIMULTANEOUS_ALLOCS; i++) {
295 ptrs[i] = NULL;
296 }
297
298 /* Run enough iterations to fill the array 32 times */
299 for (i=0; i<iterations; i++) {
300 int ptrs_index;
301 int new_size;
302
303 /* returns value 0 <= x < MAX_SIMULTANEOUS_ALLOCS which is a valid
304 * index into ptrs */
305 ptrs_index = g_test_rand_int_range(0, MAX_SIMULTANEOUS_ALLOCS);
306
307 if (ptrs[ptrs_index] == NULL) {
308 /* if that index is unused, allocate some random amount of memory
309 * between 0 and MAX_ALLOC_SIZE */
310 new_size = g_test_rand_int_range(0, MAX_ALLOC_SIZE);
311
312 ptrs[ptrs_index] = (char *) wmem_alloc0(allocator, new_size);
313 }
314 else if (g_test_rand_bit()) {
315 /* the index is used, and our random bit has determined we will be
316 * reallocating instead of freeing. Do so to some random size
317 * between 0 and MAX_ALLOC_SIZE, then manually zero the
318 * new memory */
319 new_size = g_test_rand_int_range(0, MAX_ALLOC_SIZE);
320
321 ptrs[ptrs_index] = (char *) wmem_realloc(allocator,
322 ptrs[ptrs_index], new_size);
323
324 if (new_size)
325 memset(ptrs[ptrs_index], 0, new_size);
326 }
327 else {
328 /* the index is used, and our random bit has determined we will be
329 * freeing instead of reallocating. Do so and NULL the pointer for
330 * the next iteration. */
331 wmem_free(allocator, ptrs[ptrs_index]);
332 ptrs[ptrs_index] = NULL;
333 }
334 if (verify) (*verify)(allocator);
335 }
336
337 wmem_destroy_allocator(allocator);
338 }
339
340 static void
341 wmem_test_allocator_block(void)
342 {
343 wmem_test_allocator(WMEM_ALLOCATOR_BLOCK, &wmem_block_verify,
344 MAX_SIMULTANEOUS_ALLOCS*64);
345 wmem_test_allocator_jumbo(WMEM_ALLOCATOR_BLOCK, &wmem_block_verify);
346 }
347
348 static void
349 wmem_test_allocator_block_fast(void)
350 {
351 wmem_test_allocator(WMEM_ALLOCATOR_BLOCK_FAST, NULL,
352 MAX_SIMULTANEOUS_ALLOCS*4);
353 wmem_test_allocator_jumbo(WMEM_ALLOCATOR_BLOCK, NULL);
354 }
355
356 static void
357 wmem_test_allocator_simple(void)
358 {
359 wmem_test_allocator(WMEM_ALLOCATOR_SIMPLE, NULL,
360 MAX_SIMULTANEOUS_ALLOCS*64);
361 wmem_test_allocator_jumbo(WMEM_ALLOCATOR_SIMPLE, NULL);
362 }
363
364 static void
365 wmem_test_allocator_strict(void)
366 {
367 wmem_test_allocator(WMEM_ALLOCATOR_STRICT, &wmem_strict_check_canaries,
368 MAX_SIMULTANEOUS_ALLOCS*64);
369 wmem_test_allocator_jumbo(WMEM_ALLOCATOR_STRICT, &wmem_strict_check_canaries);
370 }
371
372 /* UTILITY TESTING FUNCTIONS (/wmem/utils/) */
373
374 static void
375 wmem_test_miscutls(void)
376 {
377 wmem_allocator_t *allocator;
378 const char *source = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
379 char *ret;
380
381 allocator = wmem_allocator_new(WMEM_ALLOCATOR_STRICT);
382
383 ret = (char*) wmem_memdup(allocator, NULL, 0);
384 g_assert_true(ret == NULL);
385
386 ret = (char*) wmem_memdup(allocator, source, 5);
387 ret[4] = '\0';
388 g_assert_cmpstr(ret, ==, "ABCD");
389
390 ret = (char*) wmem_memdup(allocator, source, 1);
391 g_assert_true(ret[0] == 'A');
392 wmem_strict_check_canaries(allocator);
393
394 ret = (char*) wmem_memdup(allocator, source, 10);
395 ret[9] = '\0';
396 g_assert_cmpstr(ret, ==, "ABCDEFGHI");
397
398 wmem_destroy_allocator(allocator);
399 }
400
401 static void
402 wmem_test_strutls(void)
403 {
404 wmem_allocator_t *allocator;
405 const char *orig_str;
406 char *new_str;
407
408 allocator = wmem_allocator_new(WMEM_ALLOCATOR_STRICT);
409
410 orig_str = "TEST1";
411 new_str = wmem_strdup(allocator, orig_str);
412 g_assert_cmpstr(new_str, ==, orig_str);
413 new_str[0] = 'X';
414 g_assert_cmpstr(new_str, >, orig_str);
415 wmem_strict_check_canaries(allocator);
416
417 orig_str = "TEST123456789";
418 new_str = wmem_strndup(allocator, orig_str, 6);
419 g_assert_cmpstr(new_str, ==, "TEST12");
420 g_assert_cmpstr(new_str, <, orig_str);
421 new_str[0] = 'X';
422 g_assert_cmpstr(new_str, >, orig_str);
423 wmem_strict_check_canaries(allocator);
424
425 new_str = wmem_strdup_printf(allocator, "abc %s %% %d", "boo", 23);
426 g_assert_cmpstr(new_str, ==, "abc boo % 23");
427 new_str = wmem_strdup_printf(allocator, "%s", STRING_80);
428 g_assert_cmpstr(new_str, ==, STRING_80);
429 wmem_strict_check_canaries(allocator);
430
431 orig_str = "Short String";
432 new_str = wmem_strdup_printf(allocator, "TEST %s", orig_str);
433 g_assert_cmpstr(new_str, ==, "TEST Short String");
434
435 orig_str = "Very Long..............................."
436 "........................................"
437 "........................................"
438 "........................................"
439 "........................................"
440 "........................................"
441 "..................................String";
442 new_str = wmem_strdup_printf(allocator, "TEST %s", orig_str);
443 g_assert_cmpstr(new_str, ==,
444 "TEST Very Long..............................."
445 "........................................"
446 "........................................"
447 "........................................"
448 "........................................"
449 "........................................"
450 "..................................String");
451
452 wmem_destroy_allocator(allocator);
453 }
454
455 #define RESOURCE_USAGE_START get_resource_usage(&start_utime, &start_stime)
456
457 #define RESOURCE_USAGE_END \
458 get_resource_usage(&end_utime, &end_stime); \
459 utime_ms = (end_utime - start_utime) * 1000.0; \
460 stime_ms = (end_stime - start_stime) * 1000.0
461
462 /* NOTE: You have to run "wmem_test -m perf" to run the performance tests. */
463 static void
464 wmem_test_stringperf(void)
465 {
466 #define LOOP_COUNT (1 * 1000 * 1000)
467 wmem_allocator_t *allocator;
468 #ifdef _WIN32
469 char buffer[1];
470 #endif
471 char **str_ptr = g_new(char *, LOOP_COUNT);
472 char *s_val = "test string";
473 double d_val = 1000.2;
474 unsigned u_val = 54321;
475 int i_val = -12345;
476 int i;
477 double start_utime, start_stime, end_utime, end_stime, utime_ms, stime_ms;
478
479 allocator = wmem_allocator_new(WMEM_ALLOCATOR_BLOCK);
480
481 /* C99 snprintf */
482
483 RESOURCE_USAGE_START;
484 for (i = 0; i < LOOP_COUNT; i++) {
485 snprintf(NULL, 0, "%s", s_val);
486 }
487 RESOURCE_USAGE_END;
488 g_test_minimized_result(utime_ms + stime_ms,
489 "snprintf 1 string: u %.3f ms s %.3f ms", utime_ms, stime_ms);
490
491 RESOURCE_USAGE_START;
492 for (i = 0; i < LOOP_COUNT; i++) {
493 snprintf(NULL, 0, "%s%s%s%s%s", s_val, s_val, s_val, s_val, s_val);
494 }
495 RESOURCE_USAGE_END;
496 g_test_minimized_result(utime_ms + stime_ms,
497 "snprintf 5 strings: u %.3f ms s %.3f ms", utime_ms, stime_ms);
498
499 RESOURCE_USAGE_START;
500 for (i = 0; i < LOOP_COUNT; i++) {
501 snprintf(NULL, 0, "%s%u%3.5f%02d", s_val, u_val, d_val, i_val);
502 }
503 RESOURCE_USAGE_END;
504 g_test_minimized_result(utime_ms + stime_ms,
505 "snprintf mixed args: u %.3f ms s %.3f ms", utime_ms, stime_ms);
506
507 /* GLib g_snprintf (can use C99 or Gnulib) */
508
509 RESOURCE_USAGE_START;
510 for (i = 0; i < LOOP_COUNT; i++) {
511 g_snprintf(NULL, 0, "%s", s_val);
512 }
513 RESOURCE_USAGE_END;
514 g_test_minimized_result(utime_ms + stime_ms,
515 "g_printf_string_upper_bound (via g_snprintf) 1 string: u %.3f ms s %.3f ms", utime_ms, stime_ms);
516
517 RESOURCE_USAGE_START;
518 for (i = 0; i < LOOP_COUNT; i++) {
519 g_snprintf(NULL, 0, "%s%s%s%s%s", s_val, s_val, s_val, s_val, s_val);
520 }
521 RESOURCE_USAGE_END;
522 g_test_minimized_result(utime_ms + stime_ms,
523 "g_printf_string_upper_bound (via g_snprintf) 5 strings: u %.3f ms s %.3f ms", utime_ms, stime_ms);
524
525 RESOURCE_USAGE_START;
526 for (i = 0; i < LOOP_COUNT; i++) {
527 g_snprintf(NULL, 0, "%s%u%3.5f%02d", s_val, u_val, d_val, i_val);
528 }
529 RESOURCE_USAGE_END;
530 g_test_minimized_result(utime_ms + stime_ms,
531 "g_printf_string_upper_bound (via g_snprintf) mixed args: u %.3f ms s %.3f ms", utime_ms, stime_ms);
532
533 /* Windows _snprintf_s */
534
535 #ifdef _WIN32
536 RESOURCE_USAGE_START;
537 for (i = 0; i < LOOP_COUNT; i++) {
538 _snprintf_s(buffer, 1, _TRUNCATE, "%s", s_val);
539 }
540 RESOURCE_USAGE_END;
541 g_test_minimized_result(utime_ms + stime_ms,
542 "_snprintf_s upper bound 1 string: u %.3f ms s %.3f ms", utime_ms, stime_ms);
543
544 RESOURCE_USAGE_START;
545 for (i = 0; i < LOOP_COUNT; i++) {
546 _snprintf_s(buffer, 1, _TRUNCATE, "%s%s%s%s%s", s_val, s_val, s_val, s_val, s_val);
547 }
548 RESOURCE_USAGE_END;
549 g_test_minimized_result(utime_ms + stime_ms,
550 "_snprintf_s upper bound 5 strings: u %.3f ms s %.3f ms", utime_ms, stime_ms);
551
552 RESOURCE_USAGE_START;
553 for (i = 0; i < LOOP_COUNT; i++) {
554 _snprintf_s(buffer, 1, _TRUNCATE, "%s%u%3.5f%02d", s_val, u_val, d_val, i_val);
555 }
556 RESOURCE_USAGE_END;
557 g_test_minimized_result(utime_ms + stime_ms,
558 "_snprintf_s upper bound mixed args: u %.3f ms s %.3f ms", utime_ms, stime_ms);
559 #endif
560
561 /* GLib strdup */
562
563 RESOURCE_USAGE_START;
564 for (i = 0; i < LOOP_COUNT; i++) {
565 str_ptr[i] = g_strdup_printf("%s%s", s_val, s_val);
566 }
567 RESOURCE_USAGE_END;
568 g_test_minimized_result(utime_ms + stime_ms,
569 "g_strdup_printf 2 strings: u %.3f ms s %.3f ms", utime_ms, stime_ms);
570 for (i = 0; i < LOOP_COUNT; i++) {
571 g_free(str_ptr[i]);
572 }
573
574 RESOURCE_USAGE_START;
575 for (i = 0; i < LOOP_COUNT; i++) {
576 str_ptr[i] = g_strdup_printf("%s%s%s%s%s", s_val, s_val, s_val, s_val, s_val);
577 }
578 RESOURCE_USAGE_END;
579 g_test_minimized_result(utime_ms + stime_ms,
580 "g_strdup_printf 5 strings: u %.3f ms s %.3f ms", utime_ms, stime_ms);
581 for (i = 0; i < LOOP_COUNT; i++) {
582 g_free(str_ptr[i]);
583 }
584
585 /* wmem strdup null allocator */
586
587 RESOURCE_USAGE_START;
588 for (i = 0; i < LOOP_COUNT; i++) {
589 str_ptr[i] = wmem_strdup_printf(NULL, "%s%s", s_val, s_val);
590 }
591 RESOURCE_USAGE_END;
592 g_test_minimized_result(utime_ms + stime_ms,
593 "wmem_strdup_printf() 2 strings: u %.3f ms s %.3f ms", utime_ms, stime_ms);
594 for (i = 0; i < LOOP_COUNT; i++) {
595 g_free(str_ptr[i]);
596 }
597
598 RESOURCE_USAGE_START;
599 for (i = 0; i < LOOP_COUNT; i++) {
600 str_ptr[i] = wmem_strdup_printf(NULL, "%s%s%s%s%s", s_val, s_val, s_val, s_val, s_val);
601 }
602 RESOURCE_USAGE_END;
603 g_test_minimized_result(utime_ms + stime_ms,
604 "wmem_strdup_printf(NULL) 5 strings: u %.3f ms s %.3f ms", utime_ms, stime_ms);
605 for (i = 0; i < LOOP_COUNT; i++) {
606 g_free(str_ptr[i]);
607 }
608
609 /* wmem strdup strict allocator */
610
611 RESOURCE_USAGE_START;
612 for (i = 0; i < LOOP_COUNT; i++) {
613 wmem_strdup_printf(allocator, "%s%s", s_val, s_val);
614 }
615 RESOURCE_USAGE_END;
616 g_test_minimized_result(utime_ms + stime_ms,
617 "wmem_strdup_printf(allocator) 2 strings: u %.3f ms s %.3f ms", utime_ms, stime_ms);
618
619 RESOURCE_USAGE_START;
620 for (i = 0; i < LOOP_COUNT; i++) {
621 wmem_strdup_printf(allocator, "%s%s%s%s%s", s_val, s_val, s_val, s_val, s_val);
622 }
623 RESOURCE_USAGE_END;
624 g_test_minimized_result(utime_ms + stime_ms,
625 "wmem_strdup_printf(allocator) 5 strings: u %.3f ms s %.3f ms", utime_ms, stime_ms);
626
627 wmem_destroy_allocator(allocator);
628 g_free(str_ptr);
629 }
630
631 /* DATA STRUCTURE TESTING FUNCTIONS (/wmem/datastruct/) */
632
633 static void
634 wmem_test_array(void)
635 {
636 wmem_allocator_t *allocator;
637 wmem_array_t *array;
638 unsigned int i, j, k;
639 uint32_t val, *buf;
640 uint32_t vals[8];
641 uint32_t *raw;
642 uint32_t lastint;
643
644 allocator = wmem_allocator_new(WMEM_ALLOCATOR_STRICT);
645
646 array = wmem_array_new(allocator, sizeof(uint32_t));
647 g_assert_true(array);
648 g_assert_true(wmem_array_get_count(array) == 0);
649
650 for (i=0; i<CONTAINER_ITERS; i++) {
651 val = i;
652 wmem_array_append_one(array, val);
653 g_assert_true(wmem_array_get_count(array) == i+1);
654
655 val = *(uint32_t*)wmem_array_index(array, i);
656 g_assert_true(val == i);
657 g_assert_true(wmem_array_try_index(array, i, &val) == 0);
658 g_assert_true(val == i);
659 g_assert_true(wmem_array_try_index(array, i+1, &val) < 0);
660
661 }
662 wmem_strict_check_canaries(allocator);
663
664 for (i=0; i<CONTAINER_ITERS; i++) {
665 val = *(uint32_t*)wmem_array_index(array, i);
666 g_assert_true(val == i);
667 g_assert_true(wmem_array_try_index(array, i, &val) == 0);
668 g_assert_true(val == i);
669 }
670
671 wmem_destroy_array(array);
672
673 array = wmem_array_sized_new(allocator, sizeof(uint32_t), 73);
674 wmem_array_set_null_terminator(array);
675 for (i=0; i<75; i++)
676 g_assert_true(wmem_array_try_index(array, i, &val) < 0);
677
678 for (i=0; i<CONTAINER_ITERS; i++) {
679 for (j=0; j<8; j++) {
680 vals[j] = i+j;
681 }
682
683 wmem_array_append(array, vals, 8);
684 g_assert_true(wmem_array_get_count(array) == 8*(i+1));
685 }
686 wmem_strict_check_canaries(allocator);
687
688 buf = (uint32_t*)wmem_array_get_raw(array);
689 for (i=0; i<CONTAINER_ITERS; i++) {
690 for (j=0; j<8; j++) {
691 g_assert_true(buf[i*8 + j] == i+j);
692 }
693 }
694
695 wmem_array_sort(array, wmem_test_compare_uint32);
696 for (i=0, k=0; i<8; i++) {
697 for (j=0; j<=i; j++, k++) {
698 val = *(uint32_t*)wmem_array_index(array, k);
699 g_assert_true(val == i);
700 g_assert_true(wmem_array_try_index(array, k, &val) == 0);
701 g_assert_true(val == i);
702 }
703 }
704 for (j=k; k<8*(CONTAINER_ITERS+1)-j; k++) {
705 val = *(uint32_t*)wmem_array_index(array, k);
706 g_assert_true(val == ((k-j)/8)+8);
707 g_assert_true(wmem_array_try_index(array, k, &val) == 0);
708 g_assert_true(val == ((k-j)/8)+8);
709 }
710 for (i=0; i<7; i++) {
711 for (j=0; j<7-i; j++, k++) {
712 val = *(uint32_t*)wmem_array_index(array, k);
713 g_assert_true(val == CONTAINER_ITERS+i);
714 g_assert_true(wmem_array_try_index(array, k, &val) == 0);
715 g_assert_true(val == CONTAINER_ITERS+i);
716 }
717 }
718 g_assert_true(k == wmem_array_get_count(array));
719
720 lastint = 77;
721 wmem_array_append_one(array, lastint);
722
723 raw = (uint32_t*)wmem_array_get_raw(array);
724 g_assert_true(raw[wmem_array_get_count(array)] == 0);
725 g_assert_true(raw[wmem_array_get_count(array) - 1] == lastint);
726
727 wmem_destroy_array(array);
728
729 wmem_destroy_allocator(allocator);
730 }
731
732 static void
733 check_val_list(void * val, void * val_to_check)
734 {
735 g_assert_true(val == val_to_check);
736 }
737
738 static int
739 str_compare(const void *a, const void *b)
740 {
741 return strcmp((const char*)a, (const char*)b);
742 }
743
744 static void
745 wmem_test_list(void)
746 {
747 wmem_allocator_t *allocator;
748 wmem_list_t *list;
749 wmem_list_frame_t *frame;
750 unsigned int i;
751 int int1;
752 int int2;
753 char* str1;
754 char* str2;
755
756 allocator = wmem_allocator_new(WMEM_ALLOCATOR_STRICT);
757
758 list = wmem_list_new(allocator);
759 g_assert_true(list);
760 g_assert_true(wmem_list_count(list) == 0);
761
762 frame = wmem_list_head(list);
763 g_assert_true(frame == NULL);
764
765 for (i=0; i<CONTAINER_ITERS; i++) {
766 wmem_list_prepend(list, GINT_TO_POINTER(i));
767 g_assert_true(wmem_list_count(list) == i+1);
768 g_assert_true(wmem_list_find(list, GINT_TO_POINTER(i)));
769
770 frame = wmem_list_head(list);
771 g_assert_true(frame);
772 g_assert_true(wmem_list_frame_data(frame) == GINT_TO_POINTER(i));
773 }
774 wmem_strict_check_canaries(allocator);
775
776 i = CONTAINER_ITERS - 1;
777 frame = wmem_list_head(list);
778 while (frame) {
779 g_assert_true(wmem_list_frame_data(frame) == GINT_TO_POINTER(i));
780 i--;
781 frame = wmem_list_frame_next(frame);
782 }
783
784 i = 0;
785 frame = wmem_list_tail(list);
786 while (frame) {
787 g_assert_true(wmem_list_frame_data(frame) == GINT_TO_POINTER(i));
788 i++;
789 frame = wmem_list_frame_prev(frame);
790 }
791
792 i = CONTAINER_ITERS - 2;
793 while (wmem_list_count(list) > 1) {
794 wmem_list_remove(list, GINT_TO_POINTER(i));
795 i--;
796 }
797 wmem_list_remove(list, GINT_TO_POINTER(CONTAINER_ITERS - 1));
798 g_assert_true(wmem_list_count(list) == 0);
799 g_assert_true(wmem_list_head(list) == NULL);
800 g_assert_true(wmem_list_tail(list) == NULL);
801
802 for (i=0; i<CONTAINER_ITERS; i++) {
803 wmem_list_append(list, GINT_TO_POINTER(i));
804 g_assert_true(wmem_list_count(list) == i+1);
805
806 frame = wmem_list_head(list);
807 g_assert_true(frame);
808 }
809 wmem_strict_check_canaries(allocator);
810
811 i = 0;
812 frame = wmem_list_head(list);
813 while (frame) {
814 g_assert_true(wmem_list_frame_data(frame) == GINT_TO_POINTER(i));
815 i++;
816 frame = wmem_list_frame_next(frame);
817 }
818
819 i = CONTAINER_ITERS - 1;
820 frame = wmem_list_tail(list);
821 while (frame) {
822 g_assert_true(wmem_list_frame_data(frame) == GINT_TO_POINTER(i));
823 i--;
824 frame = wmem_list_frame_prev(frame);
825 }
826
827 wmem_destroy_allocator(allocator);
828
829 list = wmem_list_new(NULL);
830 for (i=0; i<CONTAINER_ITERS; i++) {
831 wmem_list_prepend(list, GINT_TO_POINTER(i));
832 }
833 g_assert_true(wmem_list_count(list) == CONTAINER_ITERS);
834 wmem_destroy_list(list);
835
836 list = wmem_list_new(NULL);
837 for (i=0; i<CONTAINER_ITERS; i++) {
838 wmem_list_append(list, GINT_TO_POINTER(1));
839 }
840 wmem_list_foreach(list, check_val_list, GINT_TO_POINTER(1));
841 wmem_destroy_list(list);
842
843 list = wmem_list_new(NULL);
844 wmem_list_insert_sorted(list, GINT_TO_POINTER(5), wmem_compare_int);
845 wmem_list_insert_sorted(list, GINT_TO_POINTER(8), wmem_compare_int);
846 wmem_list_insert_sorted(list, GINT_TO_POINTER(1), wmem_compare_int);
847 wmem_list_insert_sorted(list, GINT_TO_POINTER(2), wmem_compare_int);
848 wmem_list_insert_sorted(list, GINT_TO_POINTER(9), wmem_compare_int);
849 g_assert_true(wmem_list_count(list) == 5);
850 frame = wmem_list_head(list);
851 int1 = GPOINTER_TO_INT(wmem_list_frame_data(frame));
852 while ((frame = wmem_list_frame_next(frame))) {
853 int2 = GPOINTER_TO_INT(wmem_list_frame_data(frame));
854 g_assert_true(int1 <= int2);
855 int1 = int2;
856 }
857 wmem_destroy_list(list);
858
859 list = wmem_list_new(NULL);
860 wmem_list_insert_sorted(list, GINT_TO_POINTER(5), wmem_compare_int);
861 wmem_list_insert_sorted(list, GINT_TO_POINTER(1), wmem_compare_int);
862 wmem_list_insert_sorted(list, GINT_TO_POINTER(7), wmem_compare_int);
863 wmem_list_insert_sorted(list, GINT_TO_POINTER(3), wmem_compare_int);
864 wmem_list_insert_sorted(list, GINT_TO_POINTER(2), wmem_compare_int);
865 wmem_list_insert_sorted(list, GINT_TO_POINTER(2), wmem_compare_int);
866 g_assert_true(wmem_list_count(list) == 6);
867 frame = wmem_list_head(list);
868 int1 = GPOINTER_TO_INT(wmem_list_frame_data(frame));
869 while ((frame = wmem_list_frame_next(frame))) {
870 int2 = GPOINTER_TO_INT(wmem_list_frame_data(frame));
871 g_assert_true(int1 <= int2);
872 int1 = int2;
873 }
874 wmem_destroy_list(list);
875
876 list = wmem_list_new(NULL);
877 wmem_list_insert_sorted(list, "abc", str_compare);
878 wmem_list_insert_sorted(list, "bcd", str_compare);
879 wmem_list_insert_sorted(list, "aaa", str_compare);
880 wmem_list_insert_sorted(list, "bbb", str_compare);
881 wmem_list_insert_sorted(list, "zzz", str_compare);
882 wmem_list_insert_sorted(list, "ggg", str_compare);
883 g_assert_true(wmem_list_count(list) == 6);
884 frame = wmem_list_head(list);
885 str1 = (char*)wmem_list_frame_data(frame);
886 while ((frame = wmem_list_frame_next(frame))) {
887 str2 = (char*)wmem_list_frame_data(frame);
888 g_assert_true(strcmp(str1, str2) <= 0);
889 str1 = str2;
890 }
891 wmem_destroy_list(list);
892 }
893
894 static void
895 check_val_map(void * key _U_, void * val, void * user_data)
896 {
897 g_assert_true(val == user_data);
898 }
899
900 static gboolean
901 equal_val_map(void * key _U_, void * val, void * user_data)
902 {
903 return val == user_data;
904 }
905
906 static void
907 wmem_test_map(void)
908 {
909 wmem_allocator_t *allocator, *extra_allocator;
910 wmem_map_t *map;
911 char *str_key;
912 const void *str_key_ret;
913 unsigned int i;
914 unsigned int *key_ret;
915 unsigned int *value_ret;
916 void *ret;
917
918 allocator = wmem_allocator_new(WMEM_ALLOCATOR_STRICT);
919 extra_allocator = wmem_allocator_new(WMEM_ALLOCATOR_STRICT);
920
921 /* insertion, lookup and removal of simple integer keys */
922 map = wmem_map_new(allocator, g_direct_hash, g_direct_equal);
923 g_assert_true(map);
924
925 for (i=0; i<CONTAINER_ITERS; i++) {
926 ret = wmem_map_insert(map, GINT_TO_POINTER(i), GINT_TO_POINTER(777777));
927 g_assert_true(ret == NULL);
928 ret = wmem_map_insert(map, GINT_TO_POINTER(i), GINT_TO_POINTER(i));
929 g_assert_true(ret == GINT_TO_POINTER(777777));
930 ret = wmem_map_insert(map, GINT_TO_POINTER(i), GINT_TO_POINTER(i));
931 g_assert_true(ret == GINT_TO_POINTER(i));
932 }
933 for (i=0; i<CONTAINER_ITERS; i++) {
934 ret = wmem_map_lookup(map, GINT_TO_POINTER(i));
935 g_assert_true(ret == GINT_TO_POINTER(i));
936 g_assert_true(wmem_map_contains(map, GINT_TO_POINTER(i)) == true);
937 g_assert_true(wmem_map_lookup_extended(map, GINT_TO_POINTER(i), NULL, NULL));
938 key_ret = NULL;
939 g_assert_true(wmem_map_lookup_extended(map, GINT_TO_POINTER(i), GINT_TO_POINTER(&key_ret), NULL));
940 g_assert_true(key_ret == GINT_TO_POINTER(i));
941 value_ret = NULL;
942 g_assert_true(wmem_map_lookup_extended(map, GINT_TO_POINTER(i), NULL, GINT_TO_POINTER(&value_ret)));
943 g_assert_true(value_ret == GINT_TO_POINTER(i));
944 key_ret = NULL;
945 value_ret = NULL;
946 g_assert_true(wmem_map_lookup_extended(map, GINT_TO_POINTER(i), GINT_TO_POINTER(&key_ret), GINT_TO_POINTER(&value_ret)));
947 g_assert_true(key_ret == GINT_TO_POINTER(i));
948 g_assert_true(value_ret == GINT_TO_POINTER(i));
949 ret = wmem_map_remove(map, GINT_TO_POINTER(i));
950 g_assert_true(ret == GINT_TO_POINTER(i));
951 g_assert_true(wmem_map_contains(map, GINT_TO_POINTER(i)) == false);
952 ret = wmem_map_lookup(map, GINT_TO_POINTER(i));
953 g_assert_true(ret == NULL);
954 ret = wmem_map_remove(map, GINT_TO_POINTER(i));
955 g_assert_true(ret == NULL);
956 }
957 wmem_free_all(allocator);
958
959 /* test auto-reset functionality */
960 map = wmem_map_new_autoreset(allocator, extra_allocator, g_direct_hash, g_direct_equal);
961 g_assert_true(map);
962 for (i=0; i<CONTAINER_ITERS; i++) {
963 ret = wmem_map_insert(map, GINT_TO_POINTER(i), GINT_TO_POINTER(777777));
964 g_assert_true(ret == NULL);
965 ret = wmem_map_insert(map, GINT_TO_POINTER(i), GINT_TO_POINTER(i));
966 g_assert_true(ret == GINT_TO_POINTER(777777));
967 ret = wmem_map_insert(map, GINT_TO_POINTER(i), GINT_TO_POINTER(i));
968 g_assert_true(ret == GINT_TO_POINTER(i));
969 }
970 wmem_free_all(extra_allocator);
971 for (i=0; i<CONTAINER_ITERS; i++) {
972 g_assert_true(wmem_map_lookup(map, GINT_TO_POINTER(i)) == NULL);
973 }
974 wmem_free_all(allocator);
975
976 map = wmem_map_new(allocator, wmem_str_hash, g_str_equal);
977 g_assert_true(map);
978
979 /* string keys and for-each */
980 for (i=0; i<CONTAINER_ITERS; i++) {
981 str_key = wmem_test_rand_string(allocator, 1, 64);
982 wmem_map_insert(map, str_key, GINT_TO_POINTER(i));
983 ret = wmem_map_lookup(map, str_key);
984 g_assert_true(ret == GINT_TO_POINTER(i));
985 g_assert_true(wmem_map_contains(map, str_key) == true);
986 str_key_ret = NULL;
987 value_ret = NULL;
988 g_assert_true(wmem_map_lookup_extended(map, str_key, &str_key_ret, GINT_TO_POINTER(&value_ret)) == true);
989 g_assert_true(g_str_equal(str_key_ret, str_key));
990 g_assert_true(value_ret == GINT_TO_POINTER(i));
991 }
992
993 /* test foreach */
994 map = wmem_map_new(allocator, wmem_str_hash, g_str_equal);
995 g_assert_true(map);
996 for (i=0; i<CONTAINER_ITERS; i++) {
997 str_key = wmem_test_rand_string(allocator, 1, 64);
998 wmem_map_insert(map, str_key, GINT_TO_POINTER(2));
999 }
1000 wmem_map_foreach(map, check_val_map, GINT_TO_POINTER(2));
1001 g_assert_true(wmem_map_find(map, equal_val_map, GINT_TO_POINTER(2)) == GINT_TO_POINTER(2));
1002 wmem_map_foreach_remove(map, equal_val_map, GINT_TO_POINTER(2));
1003 g_assert_true(wmem_map_size(map) == 0);
1004
1005 /* test size */
1006 map = wmem_map_new(allocator, g_direct_hash, g_direct_equal);
1007 g_assert_true(map);
1008 for (i=0; i<CONTAINER_ITERS; i++) {
1009 wmem_map_insert(map, GINT_TO_POINTER(i), GINT_TO_POINTER(i));
1010 }
1011 g_assert_true(wmem_map_size(map) == CONTAINER_ITERS);
1012
1013 for (i=0; i<CONTAINER_ITERS; i+=2) {
1014 wmem_map_foreach_remove(map, equal_val_map, GINT_TO_POINTER(i));
1015 }
1016 g_assert_true(wmem_map_size(map) == CONTAINER_ITERS/2);
1017
1018 wmem_destroy_allocator(extra_allocator);
1019 wmem_destroy_allocator(allocator);
1020 }
1021
1022 static void
1023 wmem_test_queue(void)
1024 {
1025 wmem_allocator_t *allocator;
1026 wmem_queue_t *queue;
1027 unsigned int i;
1028
1029 allocator = wmem_allocator_new(WMEM_ALLOCATOR_STRICT);
1030
1031 queue = wmem_queue_new(allocator);
1032 g_assert_true(queue);
1033 g_assert_true(wmem_queue_count(queue) == 0);
1034
1035 for (i=0; i<CONTAINER_ITERS; i++) {
1036 wmem_queue_push(queue, GINT_TO_POINTER(i));
1037
1038 g_assert_true(wmem_queue_count(queue) == i+1);
1039 g_assert_true(wmem_queue_peek(queue) == GINT_TO_POINTER(0));
1040 }
1041 wmem_strict_check_canaries(allocator);
1042
1043 for (i=0; i<CONTAINER_ITERS; i++) {
1044 g_assert_true(wmem_queue_peek(queue) == GINT_TO_POINTER(i));
1045 g_assert_true(wmem_queue_pop(queue) == GINT_TO_POINTER(i));
1046 g_assert_true(wmem_queue_count(queue) == CONTAINER_ITERS-i-1);
1047 }
1048 g_assert_true(wmem_queue_count(queue) == 0);
1049
1050 wmem_destroy_queue(queue);
1051
1052 wmem_destroy_allocator(allocator);
1053 }
1054
1055 static void
1056 wmem_test_stack(void)
1057 {
1058 wmem_allocator_t *allocator;
1059 wmem_stack_t *stack;
1060 unsigned int i;
1061
1062 allocator = wmem_allocator_new(WMEM_ALLOCATOR_STRICT);
1063
1064 stack = wmem_stack_new(allocator);
1065 g_assert_true(stack);
1066 g_assert_true(wmem_stack_count(stack) == 0);
1067
1068 for (i=0; i<CONTAINER_ITERS; i++) {
1069 wmem_stack_push(stack, GINT_TO_POINTER(i));
1070
1071 g_assert_true(wmem_stack_count(stack) == i+1);
1072 g_assert_true(wmem_stack_peek(stack) == GINT_TO_POINTER(i));
1073 }
1074 wmem_strict_check_canaries(allocator);
1075
1076 for (i=CONTAINER_ITERS; i>0; i--) {
1077 g_assert_true(wmem_stack_peek(stack) == GINT_TO_POINTER(i-1));
1078 g_assert_true(wmem_stack_pop(stack) == GINT_TO_POINTER(i-1));
1079 g_assert_true(wmem_stack_count(stack) == i-1);
1080 }
1081 g_assert_true(wmem_stack_count(stack) == 0);
1082
1083 wmem_destroy_stack(stack);
1084
1085 wmem_destroy_allocator(allocator);
1086 }
1087
1088 static void
1089 wmem_test_strbuf(void)
1090 {
1091 wmem_allocator_t *allocator;
1092 wmem_strbuf_t *strbuf;
1093 int i;
1094
1095 allocator = wmem_allocator_new(WMEM_ALLOCATOR_STRICT);
1096
1097 strbuf = wmem_strbuf_new(allocator, "TEST");
1098 g_assert_true(strbuf);
1099 g_assert_cmpstr(wmem_strbuf_get_str(strbuf), ==, "TEST");
1100 g_assert_cmpuint(wmem_strbuf_get_len(strbuf), ==, 4);
1101
1102 wmem_strbuf_append(strbuf, "FUZZ");
1103 g_assert_cmpstr(wmem_strbuf_get_str(strbuf), ==, "TESTFUZZ");
1104 g_assert_cmpuint(wmem_strbuf_get_len(strbuf), ==, 8);
1105
1106 wmem_strbuf_append_printf(strbuf, "%d%s", 3, "a");
1107 g_assert_cmpstr(wmem_strbuf_get_str(strbuf), ==, "TESTFUZZ3a");
1108 g_assert_cmpuint(wmem_strbuf_get_len(strbuf), ==, 10);
1109
1110 wmem_strbuf_append_c(strbuf, 'q');
1111 g_assert_cmpstr(wmem_strbuf_get_str(strbuf), ==, "TESTFUZZ3aq");
1112 g_assert_cmpuint(wmem_strbuf_get_len(strbuf), ==, 11);
1113
1114 wmem_strbuf_append_unichar(strbuf, g_utf8_get_char("\xC2\xA9"));
1115 g_assert_cmpstr(wmem_strbuf_get_str(strbuf), ==, "TESTFUZZ3aq\xC2\xA9");
1116 g_assert_cmpuint(wmem_strbuf_get_len(strbuf), ==, 13);
1117
1118 wmem_strbuf_append_c_count(strbuf, '+', 8);
1119 g_assert_cmpstr(wmem_strbuf_get_str(strbuf), ==, "TESTFUZZ3aq\xC2\xA9++++++++");
1120 g_assert_cmpuint(wmem_strbuf_get_len(strbuf), ==, 21);
1121
1122 wmem_strbuf_truncate(strbuf, 32);
1123 wmem_strbuf_truncate(strbuf, 24);
1124 wmem_strbuf_truncate(strbuf, 16);
1125 wmem_strbuf_truncate(strbuf, 13);
1126 g_assert_cmpstr(wmem_strbuf_get_str(strbuf), ==, "TESTFUZZ3aq\xC2\xA9");
1127 g_assert_cmpuint(wmem_strbuf_get_len(strbuf), ==, 13);
1128
1129 wmem_strbuf_truncate(strbuf, 3);
1130 g_assert_cmpstr(wmem_strbuf_get_str(strbuf), ==, "TES");
1131 g_assert_cmpuint(wmem_strbuf_get_len(strbuf), ==, 3);
1132
1133 wmem_strbuf_append_len(strbuf, "TFUZZ1234", 5);
1134 g_assert_cmpstr(wmem_strbuf_get_str(strbuf), ==, "TESTFUZZ");
1135 g_assert_cmpuint(wmem_strbuf_get_len(strbuf), ==, 8);
1136
1137 wmem_free_all(allocator);
1138
1139 strbuf = wmem_strbuf_new(allocator, "TEST");
1140 for (i=0; i<1024; i++) {
1141 if (g_test_rand_bit()) {
1142 wmem_strbuf_append(strbuf, "ABC");
1143 }
1144 else {
1145 wmem_strbuf_append_printf(strbuf, "%d%d", 3, 777);
1146 }
1147 wmem_strict_check_canaries(allocator);
1148 }
1149 g_assert_true(strlen(wmem_strbuf_get_str(strbuf)) ==
1150 wmem_strbuf_get_len(strbuf));
1151
1152 wmem_destroy_allocator(allocator);
1153 }
1154
1155 static void
1156 wmem_test_strbuf_validate(void)
1157 {
1158 wmem_strbuf_t *strbuf;
1159 const char *endptr;
1160
1161 strbuf = wmem_strbuf_new(NULL, "TEST\xEF ABC");
1162 g_assert_false(wmem_strbuf_utf8_validate(strbuf, &endptr));
1163 g_assert_true(endptr == &strbuf->str[4]);
1164 wmem_strbuf_destroy(strbuf);
1165
1166 strbuf = wmem_strbuf_new(NULL, NULL);
1167 wmem_strbuf_append_len(strbuf, "TEST\x00\x00 ABC", 10);
1168 g_assert_true(wmem_strbuf_utf8_validate(strbuf, &endptr));
1169 wmem_strbuf_destroy(strbuf);
1170
1171 strbuf = wmem_strbuf_new(NULL, NULL);
1172 wmem_strbuf_append_len(strbuf, "TEST\x00\xEF ABC", 10);
1173 g_assert_false(wmem_strbuf_utf8_validate(strbuf, &endptr));
1174 g_assert_true(endptr == &strbuf->str[5]);
1175 wmem_strbuf_destroy(strbuf);
1176
1177 strbuf = wmem_strbuf_new(NULL, NULL);
1178 wmem_strbuf_append_len(strbuf, "TEST\x00 ABC \x00 DEF \x00", 17);
1179 g_assert_true(wmem_strbuf_utf8_validate(strbuf, &endptr));
1180 wmem_strbuf_destroy(strbuf);
1181 }
1182
1183 static void
1184 wmem_test_tree(void)
1185 {
1186 wmem_allocator_t *allocator, *extra_allocator;
1187 wmem_tree_t *tree;
1188 uint32_t i;
1189 uint32_t rand_int;
1190 int seen_values = 0;
1191 int j;
1192 uint32_t int_key;
1193 char *str_key;
1194 #define WMEM_TREE_MAX_KEY_COUNT 8
1195 #define WMEM_TREE_MAX_KEY_LEN 4
1196 int key_count;
1197 wmem_tree_key_t keys[WMEM_TREE_MAX_KEY_COUNT];
1198
1199 allocator = wmem_allocator_new(WMEM_ALLOCATOR_STRICT);
1200 extra_allocator = wmem_allocator_new(WMEM_ALLOCATOR_STRICT);
1201
1202 tree = wmem_tree_new(allocator);
1203 g_assert_true(tree);
1204 g_assert_true(wmem_tree_is_empty(tree));
1205
1206 /* test basic 32-bit key operations */
1207 for (i=0; i<CONTAINER_ITERS; i++) {
1208 g_assert_true(wmem_tree_lookup32(tree, i) == NULL);
1209 if (i > 0) {
1210 g_assert_true(wmem_tree_lookup32_le_full(tree, i, &int_key) == GINT_TO_POINTER(i-1));
1211 g_assert_true(int_key == i - 1);
1212 }
1213 wmem_tree_insert32(tree, i, GINT_TO_POINTER(i));
1214 g_assert_true(wmem_tree_lookup32(tree, i) == GINT_TO_POINTER(i));
1215 g_assert_true(!wmem_tree_is_empty(tree));
1216 }
1217 g_assert_true(wmem_tree_count(tree) == CONTAINER_ITERS);
1218
1219 rand_int = ((uint32_t)g_test_rand_int()) % CONTAINER_ITERS;
1220 wmem_tree_remove32(tree, rand_int);
1221 g_assert_true(wmem_tree_lookup32(tree, rand_int) == NULL);
1222 if (rand_int > 0) {
1223 g_assert_true(wmem_tree_lookup32_le(tree, rand_int) == GINT_TO_POINTER(rand_int - 1));
1224 }
1225 if (rand_int + 1 < CONTAINER_ITERS) {
1226 g_assert_true(wmem_tree_lookup32_ge(tree, rand_int) == GINT_TO_POINTER(rand_int + 1));
1227 }
1228 g_assert_true(wmem_tree_count(tree) == CONTAINER_ITERS - 1);
1229 wmem_free_all(allocator);
1230
1231 tree = wmem_tree_new(allocator);
1232 for (i=0; i<CONTAINER_ITERS; i++) {
1233 do {
1234 rand_int = g_test_rand_int();
1235 } while (wmem_tree_lookup32(tree, rand_int));
1236 wmem_tree_insert32(tree, rand_int, GINT_TO_POINTER(i));
1237 g_assert_true(wmem_tree_lookup32(tree, rand_int) == GINT_TO_POINTER(i));
1238 }
1239 g_assert_true(wmem_tree_count(tree) == CONTAINER_ITERS);
1240 wmem_free_all(allocator);
1241
1242 /* test auto-reset functionality */
1243 tree = wmem_tree_new_autoreset(allocator, extra_allocator);
1244 for (i=0; i<CONTAINER_ITERS; i++) {
1245 g_assert_true(wmem_tree_lookup32(tree, i) == NULL);
1246 wmem_tree_insert32(tree, i, GINT_TO_POINTER(i));
1247 g_assert_true(wmem_tree_lookup32(tree, i) == GINT_TO_POINTER(i));
1248 }
1249 g_assert_true(wmem_tree_count(tree) == CONTAINER_ITERS);
1250 wmem_free_all(extra_allocator);
1251 g_assert_true(wmem_tree_count(tree) == 0);
1252 for (i=0; i<CONTAINER_ITERS; i++) {
1253 g_assert_true(wmem_tree_lookup32(tree, i) == NULL);
1254 g_assert_true(wmem_tree_lookup32_le(tree, i) == NULL);
1255 }
1256 wmem_free_all(allocator);
1257
1258 /* test array key functionality */
1259 tree = wmem_tree_new(allocator);
1260 key_count = g_random_int_range(1, WMEM_TREE_MAX_KEY_COUNT);
1261 for (j=0; j<key_count; j++) {
1262 keys[j].length = g_random_int_range(1, WMEM_TREE_MAX_KEY_LEN);
1263 }
1264 keys[key_count].length = 0;
1265 for (i=0; i<CONTAINER_ITERS; i++) {
1266 for (j=0; j<key_count; j++) {
1267 keys[j].key = (uint32_t*)wmem_test_rand_string(allocator,
1268 (keys[j].length*4), (keys[j].length*4)+1);
1269 }
1270 wmem_tree_insert32_array(tree, keys, GINT_TO_POINTER(i));
1271 g_assert_true(wmem_tree_lookup32_array(tree, keys) == GINT_TO_POINTER(i));
1272 }
1273 wmem_free_all(allocator);
1274
1275 tree = wmem_tree_new(allocator);
1276 keys[0].length = 1;
1277 keys[0].key = wmem_new(allocator, uint32_t);
1278 *(keys[0].key) = 0;
1279 keys[1].length = 0;
1280 for (i=0; i<CONTAINER_ITERS; i++) {
1281 wmem_tree_insert32_array(tree, keys, GINT_TO_POINTER(i));
1282 *(keys[0].key) += 4;
1283 }
1284 *(keys[0].key) = 0;
1285 for (i=0; i<CONTAINER_ITERS; i++) {
1286 g_assert_true(wmem_tree_lookup32_array(tree, keys) == GINT_TO_POINTER(i));
1287 for (j=0; j<3; j++) {
1288 (*(keys[0].key)) += 1;
1289 g_assert_true(wmem_tree_lookup32_array_le(tree, keys) ==
1290 GINT_TO_POINTER(i));
1291 }
1292 *(keys[0].key) += 1;
1293 }
1294 wmem_free_all(allocator);
1295
1296 /* test string key functionality */
1297 tree = wmem_tree_new(allocator);
1298 for (i=0; i<CONTAINER_ITERS; i++) {
1299 str_key = wmem_test_rand_string(allocator, 1, 64);
1300 wmem_tree_insert_string(tree, str_key, GINT_TO_POINTER(i), 0);
1301 g_assert_true(wmem_tree_lookup_string(tree, str_key, 0) ==
1302 GINT_TO_POINTER(i));
1303 }
1304 wmem_free_all(allocator);
1305
1306 tree = wmem_tree_new(allocator);
1307 for (i=0; i<CONTAINER_ITERS; i++) {
1308 str_key = wmem_test_rand_string(allocator, 1, 64);
1309 wmem_tree_insert_string(tree, str_key, GINT_TO_POINTER(i),
1310 WMEM_TREE_STRING_NOCASE);
1311 g_assert_true(wmem_tree_lookup_string(tree, str_key,
1312 WMEM_TREE_STRING_NOCASE) == GINT_TO_POINTER(i));
1313 }
1314 wmem_free_all(allocator);
1315
1316 /* test for-each functionality */
1317 tree = wmem_tree_new(allocator);
1318 expected_user_data = GINT_TO_POINTER(g_test_rand_int());
1319 for (i=0; i<CONTAINER_ITERS; i++) {
1320 int tmp;
1321 do {
1322 tmp = g_test_rand_int();
1323 } while (wmem_tree_lookup32(tree, tmp));
1324 value_seen[i] = false;
1325 wmem_tree_insert32(tree, tmp, GINT_TO_POINTER(i));
1326 }
1327
1328 cb_called_count = 0;
1329 cb_continue_count = CONTAINER_ITERS;
1330 wmem_tree_foreach(tree, wmem_test_foreach_cb, expected_user_data);
1331 g_assert_true(cb_called_count == CONTAINER_ITERS);
1332 g_assert_true(cb_continue_count == 0);
1333
1334 for (i=0; i<CONTAINER_ITERS; i++) {
1335 g_assert_true(value_seen[i]);
1336 value_seen[i] = false;
1337 }
1338
1339 cb_called_count = 0;
1340 cb_continue_count = 10;
1341 wmem_tree_foreach(tree, wmem_test_foreach_cb, expected_user_data);
1342 g_assert_true(cb_called_count == 10);
1343 g_assert_true(cb_continue_count == 0);
1344
1345 for (i=0; i<CONTAINER_ITERS; i++) {
1346 if (value_seen[i]) {
1347 seen_values++;
1348 }
1349 }
1350 g_assert_true(seen_values == 10);
1351
1352 wmem_destroy_allocator(extra_allocator);
1353 wmem_destroy_allocator(allocator);
1354 }
1355
1356
1357 /* to be used as userdata in the callback wmem_test_itree_check_overlap_cb*/
1358 typedef struct wmem_test_itree_user_data {
1359 wmem_range_t range;
1360 unsigned counter;
1361 } wmem_test_itree_user_data_t;
1362
1363
1364 /* increase userData counter in case the range match the userdata range */
1365 static bool
1366 wmem_test_itree_check_overlap_cb (const void *key, void *value _U_, void *userData)
1367 {
1368 const wmem_range_t *ckey = (const wmem_range_t *)key;
1369 struct wmem_test_itree_user_data * d = (struct wmem_test_itree_user_data *)userData;
1370 g_assert_true(key);
1371 g_assert_true(d);
1372
1373 if(wmem_itree_range_overlap(ckey, &d->range)) {
1374 d->counter++;
1375 }
1376
1377 return false;
1378 }
1379
1380
1381 static bool
1382 wmem_test_overlap(uint64_t low, uint64_t high, uint64_t lowbis, uint64_t highbis)
1383 {
1384 wmem_range_t r1 = {low, high, 0};
1385 wmem_range_t r2 = {lowbis, highbis, 0};
1386 return wmem_itree_range_overlap(&r1, &r2);
1387 }
1388
1389 static void
1390 wmem_test_itree(void)
1391 {
1392 wmem_allocator_t *allocator, *extra_allocator;
1393 wmem_itree_t *tree;
1394 int i = 0;
1395 int32_t max_rand = 0;
1396 wmem_test_itree_user_data_t userData;
1397 wmem_range_t range, r2;
1398
1399 allocator = wmem_allocator_new(WMEM_ALLOCATOR_STRICT);
1400 extra_allocator = wmem_allocator_new(WMEM_ALLOCATOR_STRICT);
1401
1402 tree = wmem_itree_new(allocator);
1403 g_assert_true(tree);
1404 g_assert_true(wmem_itree_is_empty(tree));
1405
1406 wmem_free_all(allocator);
1407
1408 /* make sure that wmem_test_overlap is correct (well it's no proof but...)*/
1409 g_assert_true(wmem_test_overlap(0, 10, 0, 4));
1410 g_assert_true(wmem_test_overlap(0, 10, 9, 14));
1411 g_assert_true(wmem_test_overlap(5, 10, 3, 8));
1412 g_assert_true(wmem_test_overlap(5, 10, 1, 12));
1413 g_assert_true(!wmem_test_overlap(0, 10, 11, 12));
1414
1415 /* Generate a reference range, then fill an itree with random ranges,
1416 then we count greedily the number of overlapping ranges and compare
1417 the result with the optimized result
1418 */
1419
1420 userData.counter = 0;
1421
1422 tree = wmem_itree_new(allocator);
1423
1424 /* even though keys are uint64_t, we use INT32_MAX as a max because of the type returned by
1425 g_test_rand_int_range.
1426 */
1427 max_rand = INT32_MAX;
1428 r2.max_edge = range.max_edge = 0;
1429 range.low = g_test_rand_int_range(0, max_rand);
1430 range.high = g_test_rand_int_range( (int32_t)range.low, (int32_t)max_rand);
1431 userData.range = range;
1432
1433 for (i=0; i<CONTAINER_ITERS; i++) {
1434
1435 wmem_list_t *results = NULL;
1436
1437 /* reset the search */
1438 userData.counter = 0;
1439 r2.low = (uint64_t)g_test_rand_int_range(0, 100);
1440 r2.high = (uint64_t)g_test_rand_int_range( (int32_t)r2.low, 100);
1441
1442 wmem_itree_insert(tree, r2.low, r2.high, GINT_TO_POINTER(i));
1443
1444 /* greedy search */
1445 wmem_tree_foreach(tree, wmem_test_itree_check_overlap_cb, &userData);
1446
1447 /* Optimized search */
1448 results = wmem_itree_find_intervals(tree, allocator, range.low, range.high);
1449
1450 /* keep it as a loop instead of wmem_list_count in case one */
1451 g_assert_true(wmem_list_count(results) == userData.counter);
1452 }
1453
1454 wmem_destroy_allocator(extra_allocator);
1455 wmem_destroy_allocator(allocator);
1456 }
1457
1458
1459 int
1460 main(int argc, char **argv)
1461 {
1462 int ret;
1463
1464 wmem_init();
1465
1466 g_test_init(&argc, &argv, NULL);
1467
1468 g_test_add_func("/wmem/allocator/block", wmem_test_allocator_block);
1469 g_test_add_func("/wmem/allocator/blk_fast", wmem_test_allocator_block_fast);
1470 g_test_add_func("/wmem/allocator/simple", wmem_test_allocator_simple);
1471 g_test_add_func("/wmem/allocator/strict", wmem_test_allocator_strict);
1472 g_test_add_func("/wmem/allocator/callbacks", wmem_test_allocator_callbacks);
1473
1474 g_test_add_func("/wmem/utils/misc", wmem_test_miscutls);
1475 g_test_add_func("/wmem/utils/strings", wmem_test_strutls);
1476
1477 if (g_test_perf()) {
1478 g_test_add_func("/wmem/utils/stringperf", wmem_test_stringperf);
1479 }
1480
1481 g_test_add_func("/wmem/datastruct/array", wmem_test_array);
1482 g_test_add_func("/wmem/datastruct/list", wmem_test_list);
1483 g_test_add_func("/wmem/datastruct/map", wmem_test_map);
1484 g_test_add_func("/wmem/datastruct/queue", wmem_test_queue);
1485 g_test_add_func("/wmem/datastruct/stack", wmem_test_stack);
1486 g_test_add_func("/wmem/datastruct/strbuf", wmem_test_strbuf);
1487 g_test_add_func("/wmem/datastruct/strbuf/validate", wmem_test_strbuf_validate);
1488 g_test_add_func("/wmem/datastruct/tree", wmem_test_tree);
1489 g_test_add_func("/wmem/datastruct/itree", wmem_test_itree);
1490
1491 ret = g_test_run();
1492
1493 wmem_cleanup();
1494
1495 return ret;
1496 }
1497
1498 /*
1499 * Editor modelines - https://www.wireshark.org/tools/modelines.html
1500 *
1501 * Local variables:
1502 * c-basic-offset: 4
1503 * tab-width: 8
1504 * indent-tabs-mode: nil
1505 * End:
1506 *
1507 * vi: set shiftwidth=4 tabstop=8 expandtab:
1508 * :indentSize=4:tabSize=8:noTabs=true:
1509 */
Metzes wireshark repo