16f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin/* 26f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin * Copyright © 2012 Ran Benita <ran234@gmail.com> 36f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin * 46f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin * Permission is hereby granted, free of charge, to any person obtaining a 56f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin * copy of this software and associated documentation files (the "Software"), 66f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin * to deal in the Software without restriction, including without limitation 76f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin * the rights to use, copy, modify, merge, publish, distribute, sublicense, 86f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin * and/or sell copies of the Software, and to permit persons to whom the 96f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin * Software is furnished to do so, subject to the following conditions: 106f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin * 116f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin * The above copyright notice and this permission notice (including the next 126f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin * paragraph) shall be included in all copies or substantial portions of the 136f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin * Software. 146f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin * 156f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 166f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 176f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 186f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 196f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 206f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 216f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin * DEALINGS IN THE SOFTWARE. 226f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin */ 236f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin 246f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin#include <time.h> 256f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin 266f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin#include "test.h" 276f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin#include "atom.h" 286f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin 296f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin#define INTERN_LITERAL(table, literal) \ 306f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin atom_intern(table, literal, sizeof(literal) - 1, false) 316f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin 326f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin#define LOOKUP_LITERAL(table, literal) \ 336f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin atom_lookup(table, literal, sizeof(literal) - 1) 346f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin 356f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempinstatic void 366f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempinrandom_string(char **str_out, size_t *len_out) 376f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin{ 386f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin /* Keep this small, so collisions might happen. */ 396f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin static const char random_chars[] = { 406f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin 'a', 'b', 'c', 'd', 'e', 'f', 'g' 416f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin }; 426f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin 436f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin size_t len; 446f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin char *str; 456f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin 466f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin len = rand() % 15; 476f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin str = malloc(len + 1); 486f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin assert(str); 496f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin 506f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin for (size_t i = 0; i < len; i++) 516f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin str[i] = random_chars[rand() % ARRAY_SIZE(random_chars)]; 526f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin /* Don't always terminate it; should work without. */ 536f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin if (rand() % 2 == 0) 546f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin str[len] = '\0'; 556f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin 566f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin *str_out = str; 576f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin *len_out = len; 586f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin} 596f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin 606f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempinstatic void 616f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempintest_random_strings(void) 626f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin{ 636f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin struct atom_string { 646f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin xkb_atom_t atom; 656f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin char *string; 666f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin size_t len; 676f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin }; 686f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin 696f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin struct atom_table *table; 706f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin struct atom_string *arr; 716f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin int N; 726f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin xkb_atom_t atom; 736f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin const char *string; 746f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin 756f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin table = atom_table_new(); 766f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin assert(table); 776f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin 786f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin srand(clock()); 796f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin 806f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin N = 1 + rand() % 1500; 816f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin arr = calloc(N, sizeof(*arr)); 826f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin assert(arr); 836f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin 846f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin for (int i = 0; i < N; i++) { 856f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin random_string(&arr[i].string, &arr[i].len); 866f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin 876f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin atom = atom_lookup(table, arr[i].string, arr[i].len); 886f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin if (atom != XKB_ATOM_NONE) { 896f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin string = atom_text(table, atom); 906f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin assert(string); 916f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin 926f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin if (arr[i].len != strlen(string) || 936f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin strncmp(string, arr[i].string, arr[i].len) != 0) { 946f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin fprintf(stderr, "got a collision, but strings don't match!\n"); 956f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin fprintf(stderr, "existing length %lu, string %s\n", 966f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin strlen(string), string); 976f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin fprintf(stderr, "new length %lu, string %.*s\n", 986f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin arr[i].len, (int) arr[i].len, arr[i].string); 996f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin assert(false); 1006f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin } 1016f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin 1026f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin /* OK, got a real collision. */ 1036f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin free(arr[i].string); 1046f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin i--; 1056f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin continue; 1066f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin } 1076f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin 1086f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin arr[i].atom = atom_intern(table, arr[i].string, arr[i].len, false); 1096f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin if (arr[i].atom == XKB_ATOM_NONE) { 1106f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin fprintf(stderr, "failed to intern! len: %lu, string: %.*s\n", 1116f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin arr[i].len, (int) arr[i].len, arr[i].string); 1126f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin assert(false); 1136f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin } 1146f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin } 1156f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin 1166f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin for (int i = 0; i < N; i++) { 1176f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin string = atom_text(table, arr[i].atom); 1186f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin assert(string); 1196f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin 1206f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin if (arr[i].len != strlen(string) || 1216f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin strncmp(string, arr[i].string, arr[i].len) != 0) { 1226f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin fprintf(stderr, "looked-up string doesn't match!\n"); 1236f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin fprintf(stderr, "found length %lu, string %s\n", 1246f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin strlen(string), string); 1256f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin fprintf(stderr, "expected length %lu, string %.*s\n", 1266f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin arr[i].len, (int) arr[i].len, arr[i].string); 1276f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin 1286f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin /* Since this is random, we need to dump the failing data, 1296f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin * so we might have some chance to reproduce. */ 1306f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin fprintf(stderr, "START dump of arr, N=%d\n", N); 1316f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin for (int j = 0; j < N; j++) { 1326f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin fprintf(stderr, "%u\t\t%lu\t\t%.*s\n", arr[i].atom, 1336f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin arr[i].len, (int) arr[i].len, arr[i].string); 1346f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin } 1356f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin fprintf(stderr, "END\n"); 1366f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin 1376f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin assert(false); 1386f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin } 1396f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin } 1406f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin 1416f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin for (int i = 0; i < N; i++) 1426f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin free(arr[i].string); 1436f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin free(arr); 1446f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin atom_table_free(table); 1456f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin} 1466f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin 1476f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempinint 1486f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempinmain(void) 1496f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin{ 1506f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin struct atom_table *table; 1516f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin xkb_atom_t atom1, atom2, atom3; 1526f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin 1536f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin table = atom_table_new(); 1546f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin assert(table); 1556f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin 1566f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin assert(atom_text(table, XKB_ATOM_NONE) == NULL); 1576f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin assert(atom_lookup(table, NULL, 0) == XKB_ATOM_NONE); 1586f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin 1596f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin atom1 = INTERN_LITERAL(table, "hello"); 1606f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin assert(atom1 != XKB_ATOM_NONE); 1616f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin assert(atom1 == LOOKUP_LITERAL(table, "hello")); 1626f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin assert(streq(atom_text(table, atom1), "hello")); 1636f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin 1646f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin atom2 = atom_intern(table, "hello", 3, false); 1656f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin assert(atom2 != XKB_ATOM_NONE); 1666f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin assert(atom1 != atom2); 1676f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin assert(streq(atom_text(table, atom2), "hel")); 1686f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin assert(LOOKUP_LITERAL(table, "hel") == atom2); 1696f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin assert(LOOKUP_LITERAL(table, "hell") == XKB_ATOM_NONE); 1706f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin assert(LOOKUP_LITERAL(table, "hello") == atom1); 1716f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin 1726f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin atom3 = atom_intern(table, "", 0, false); 1736f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin assert(atom3 != XKB_ATOM_NONE); 1746f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin assert(LOOKUP_LITERAL(table, "") == atom3); 1756f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin 1766f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin atom_table_free(table); 1776f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin 1786f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin test_random_strings(); 1796f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin 1806f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin return 0; 1816f36ec3ef7a87f9eaa37fc78868dbac2cb958b0Dennis Kempin} 182