1 #include "test/jemalloc_test.h" 2 3 TEST_BEGIN(test_new_delete) 4 { 5 ckh_t ckh; 6 7 assert_false(ckh_new(&ckh, 2, ckh_string_hash, ckh_string_keycomp), 8 "Unexpected ckh_new() error"); 9 ckh_delete(&ckh); 10 11 assert_false(ckh_new(&ckh, 3, ckh_pointer_hash, ckh_pointer_keycomp), 12 "Unexpected ckh_new() error"); 13 ckh_delete(&ckh); 14 } 15 TEST_END 16 17 TEST_BEGIN(test_count_insert_search_remove) 18 { 19 ckh_t ckh; 20 const char *strs[] = { 21 "a string", 22 "A string", 23 "a string.", 24 "A string." 25 }; 26 const char *missing = "A string not in the hash table."; 27 size_t i; 28 29 assert_false(ckh_new(&ckh, 2, ckh_string_hash, ckh_string_keycomp), 30 "Unexpected ckh_new() error"); 31 assert_zu_eq(ckh_count(&ckh), 0, 32 "ckh_count() should return %zu, but it returned %zu", ZU(0), 33 ckh_count(&ckh)); 34 35 /* Insert. */ 36 for (i = 0; i < sizeof(strs)/sizeof(const char *); i++) { 37 ckh_insert(&ckh, strs[i], strs[i]); 38 assert_zu_eq(ckh_count(&ckh), i+1, 39 "ckh_count() should return %zu, but it returned %zu", i+1, 40 ckh_count(&ckh)); 41 } 42 43 /* Search. */ 44 for (i = 0; i < sizeof(strs)/sizeof(const char *); i++) { 45 union { 46 void *p; 47 const char *s; 48 } k, v; 49 void **kp, **vp; 50 const char *ks, *vs; 51 52 kp = (i & 1) ? &k.p : NULL; 53 vp = (i & 2) ? &v.p : NULL; 54 k.p = NULL; 55 v.p = NULL; 56 assert_false(ckh_search(&ckh, strs[i], kp, vp), 57 "Unexpected ckh_search() error"); 58 59 ks = (i & 1) ? strs[i] : (const char *)NULL; 60 vs = (i & 2) ? strs[i] : (const char *)NULL; 61 assert_ptr_eq((void *)ks, (void *)k.s, 62 "Key mismatch, i=%zu", i); 63 assert_ptr_eq((void *)vs, (void *)v.s, 64 "Value mismatch, i=%zu", i); 65 } 66 assert_true(ckh_search(&ckh, missing, NULL, NULL), 67 "Unexpected ckh_search() success"); 68 69 /* Remove. */ 70 for (i = 0; i < sizeof(strs)/sizeof(const char *); i++) { 71 union { 72 void *p; 73 const char *s; 74 } k, v; 75 void **kp, **vp; 76 const char *ks, *vs; 77 78 kp = (i & 1) ? &k.p : NULL; 79 vp = (i & 2) ? &v.p : NULL; 80 k.p = NULL; 81 v.p = NULL; 82 assert_false(ckh_remove(&ckh, strs[i], kp, vp), 83 "Unexpected ckh_remove() error"); 84 85 ks = (i & 1) ? strs[i] : (const char *)NULL; 86 vs = (i & 2) ? strs[i] : (const char *)NULL; 87 assert_ptr_eq((void *)ks, (void *)k.s, 88 "Key mismatch, i=%zu", i); 89 assert_ptr_eq((void *)vs, (void *)v.s, 90 "Value mismatch, i=%zu", i); 91 assert_zu_eq(ckh_count(&ckh), 92 sizeof(strs)/sizeof(const char *) - i - 1, 93 "ckh_count() should return %zu, but it returned %zu", 94 sizeof(strs)/sizeof(const char *) - i - 1, 95 ckh_count(&ckh)); 96 } 97 98 ckh_delete(&ckh); 99 } 100 TEST_END 101 102 TEST_BEGIN(test_insert_iter_remove) 103 { 104 #define NITEMS ZU(1000) 105 ckh_t ckh; 106 void **p[NITEMS]; 107 void *q, *r; 108 size_t i; 109 110 assert_false(ckh_new(&ckh, 2, ckh_pointer_hash, ckh_pointer_keycomp), 111 "Unexpected ckh_new() error"); 112 113 for (i = 0; i < NITEMS; i++) { 114 p[i] = mallocx(i+1, 0); 115 assert_ptr_not_null(p[i], "Unexpected mallocx() failure"); 116 } 117 118 for (i = 0; i < NITEMS; i++) { 119 size_t j; 120 121 for (j = i; j < NITEMS; j++) { 122 assert_false(ckh_insert(&ckh, p[j], p[j]), 123 "Unexpected ckh_insert() failure"); 124 assert_false(ckh_search(&ckh, p[j], &q, &r), 125 "Unexpected ckh_search() failure"); 126 assert_ptr_eq(p[j], q, "Key pointer mismatch"); 127 assert_ptr_eq(p[j], r, "Value pointer mismatch"); 128 } 129 130 assert_zu_eq(ckh_count(&ckh), NITEMS, 131 "ckh_count() should return %zu, but it returned %zu", 132 NITEMS, ckh_count(&ckh)); 133 134 for (j = i + 1; j < NITEMS; j++) { 135 assert_false(ckh_search(&ckh, p[j], NULL, NULL), 136 "Unexpected ckh_search() failure"); 137 assert_false(ckh_remove(&ckh, p[j], &q, &r), 138 "Unexpected ckh_remove() failure"); 139 assert_ptr_eq(p[j], q, "Key pointer mismatch"); 140 assert_ptr_eq(p[j], r, "Value pointer mismatch"); 141 assert_true(ckh_search(&ckh, p[j], NULL, NULL), 142 "Unexpected ckh_search() success"); 143 assert_true(ckh_remove(&ckh, p[j], &q, &r), 144 "Unexpected ckh_remove() success"); 145 } 146 147 { 148 bool seen[NITEMS]; 149 size_t tabind; 150 151 memset(seen, 0, sizeof(seen)); 152 153 for (tabind = 0; ckh_iter(&ckh, &tabind, &q, &r) == 154 false;) { 155 size_t k; 156 157 assert_ptr_eq(q, r, "Key and val not equal"); 158 159 for (k = 0; k < NITEMS; k++) { 160 if (p[k] == q) { 161 assert_false(seen[k], 162 "Item %zu already seen", k); 163 seen[k] = true; 164 break; 165 } 166 } 167 } 168 169 for (j = 0; j < i + 1; j++) 170 assert_true(seen[j], "Item %zu not seen", j); 171 for (; j < NITEMS; j++) 172 assert_false(seen[j], "Item %zu seen", j); 173 } 174 } 175 176 for (i = 0; i < NITEMS; i++) { 177 assert_false(ckh_search(&ckh, p[i], NULL, NULL), 178 "Unexpected ckh_search() failure"); 179 assert_false(ckh_remove(&ckh, p[i], &q, &r), 180 "Unexpected ckh_remove() failure"); 181 assert_ptr_eq(p[i], q, "Key pointer mismatch"); 182 assert_ptr_eq(p[i], r, "Value pointer mismatch"); 183 assert_true(ckh_search(&ckh, p[i], NULL, NULL), 184 "Unexpected ckh_search() success"); 185 assert_true(ckh_remove(&ckh, p[i], &q, &r), 186 "Unexpected ckh_remove() success"); 187 dallocx(p[i], 0); 188 } 189 190 assert_zu_eq(ckh_count(&ckh), 0, 191 "ckh_count() should return %zu, but it returned %zu", ZU(0), 192 ckh_count(&ckh)); 193 ckh_delete(&ckh); 194 #undef NITEMS 195 } 196 TEST_END 197 198 int 199 main(void) 200 { 201 202 return (test( 203 test_new_delete, 204 test_count_insert_search_remove, 205 test_insert_iter_remove)); 206 } 207
