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