1 /* 2 * Copyright 2012 Ran Benita <ran234 (at) gmail.com> 3 * 4 * Permission is hereby granted, free of charge, to any person obtaining a 5 * copy of this software and associated documentation files (the "Software"), 6 * to deal in the Software without restriction, including without limitation 7 * the rights to use, copy, modify, merge, publish, distribute, sublicense, 8 * and/or sell copies of the Software, and to permit persons to whom the 9 * Software is furnished to do so, subject to the following conditions: 10 * 11 * The above copyright notice and this permission notice (including the next 12 * paragraph) shall be included in all copies or substantial portions of the 13 * Software. 14 * 15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 18 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 20 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 21 * DEALINGS IN THE SOFTWARE. 22 */ 23 24 #include <time.h> 25 26 #include "test.h" 27 #include "atom.h" 28 29 #define INTERN_LITERAL(table, literal) \ 30 atom_intern(table, literal, sizeof(literal) - 1, false) 31 32 #define LOOKUP_LITERAL(table, literal) \ 33 atom_lookup(table, literal, sizeof(literal) - 1) 34 35 static void 36 random_string(char **str_out, size_t *len_out) 37 { 38 /* Keep this small, so collisions might happen. */ 39 static const char random_chars[] = { 40 'a', 'b', 'c', 'd', 'e', 'f', 'g' 41 }; 42 43 size_t len; 44 char *str; 45 46 len = rand() % 15; 47 str = malloc(len + 1); 48 assert(str); 49 50 for (size_t i = 0; i < len; i++) 51 str[i] = random_chars[rand() % ARRAY_SIZE(random_chars)]; 52 /* Don't always terminate it; should work without. */ 53 if (rand() % 2 == 0) 54 str[len] = '\0'; 55 56 *str_out = str; 57 *len_out = len; 58 } 59 60 static void 61 test_random_strings(void) 62 { 63 struct atom_string { 64 xkb_atom_t atom; 65 char *string; 66 size_t len; 67 }; 68 69 struct atom_table *table; 70 struct atom_string *arr; 71 int N; 72 xkb_atom_t atom; 73 const char *string; 74 75 table = atom_table_new(); 76 assert(table); 77 78 srand(clock()); 79 80 N = 1 + rand() % 1500; 81 arr = calloc(N, sizeof(*arr)); 82 assert(arr); 83 84 for (int i = 0; i < N; i++) { 85 random_string(&arr[i].string, &arr[i].len); 86 87 atom = atom_lookup(table, arr[i].string, arr[i].len); 88 if (atom != XKB_ATOM_NONE) { 89 string = atom_text(table, atom); 90 assert(string); 91 92 if (arr[i].len != strlen(string) || 93 strncmp(string, arr[i].string, arr[i].len) != 0) { 94 fprintf(stderr, "got a collision, but strings don't match!\n"); 95 fprintf(stderr, "existing length %lu, string %s\n", 96 strlen(string), string); 97 fprintf(stderr, "new length %lu, string %.*s\n", 98 arr[i].len, (int) arr[i].len, arr[i].string); 99 assert(false); 100 } 101 102 /* OK, got a real collision. */ 103 free(arr[i].string); 104 i--; 105 continue; 106 } 107 108 arr[i].atom = atom_intern(table, arr[i].string, arr[i].len, false); 109 if (arr[i].atom == XKB_ATOM_NONE) { 110 fprintf(stderr, "failed to intern! len: %lu, string: %.*s\n", 111 arr[i].len, (int) arr[i].len, arr[i].string); 112 assert(false); 113 } 114 } 115 116 for (int i = 0; i < N; i++) { 117 string = atom_text(table, arr[i].atom); 118 assert(string); 119 120 if (arr[i].len != strlen(string) || 121 strncmp(string, arr[i].string, arr[i].len) != 0) { 122 fprintf(stderr, "looked-up string doesn't match!\n"); 123 fprintf(stderr, "found length %lu, string %s\n", 124 strlen(string), string); 125 fprintf(stderr, "expected length %lu, string %.*s\n", 126 arr[i].len, (int) arr[i].len, arr[i].string); 127 128 /* Since this is random, we need to dump the failing data, 129 * so we might have some chance to reproduce. */ 130 fprintf(stderr, "START dump of arr, N=%d\n", N); 131 for (int j = 0; j < N; j++) { 132 fprintf(stderr, "%u\t\t%lu\t\t%.*s\n", arr[i].atom, 133 arr[i].len, (int) arr[i].len, arr[i].string); 134 } 135 fprintf(stderr, "END\n"); 136 137 assert(false); 138 } 139 } 140 141 for (int i = 0; i < N; i++) 142 free(arr[i].string); 143 free(arr); 144 atom_table_free(table); 145 } 146 147 int 148 main(void) 149 { 150 struct atom_table *table; 151 xkb_atom_t atom1, atom2, atom3; 152 153 table = atom_table_new(); 154 assert(table); 155 156 assert(atom_text(table, XKB_ATOM_NONE) == NULL); 157 assert(atom_lookup(table, NULL, 0) == XKB_ATOM_NONE); 158 159 atom1 = INTERN_LITERAL(table, "hello"); 160 assert(atom1 != XKB_ATOM_NONE); 161 assert(atom1 == LOOKUP_LITERAL(table, "hello")); 162 assert(streq(atom_text(table, atom1), "hello")); 163 164 atom2 = atom_intern(table, "hello", 3, false); 165 assert(atom2 != XKB_ATOM_NONE); 166 assert(atom1 != atom2); 167 assert(streq(atom_text(table, atom2), "hel")); 168 assert(LOOKUP_LITERAL(table, "hel") == atom2); 169 assert(LOOKUP_LITERAL(table, "hell") == XKB_ATOM_NONE); 170 assert(LOOKUP_LITERAL(table, "hello") == atom1); 171 172 atom3 = atom_intern(table, "", 0, false); 173 assert(atom3 != XKB_ATOM_NONE); 174 assert(LOOKUP_LITERAL(table, "") == atom3); 175 176 atom_table_free(table); 177 178 test_random_strings(); 179 180 return 0; 181 } 182