1 /* 2 * Copyright (C) 2016, Emilio G. Cota <cota@braap.org> 3 * 4 * License: GNU GPL, version 2 or later. 5 * See the COPYING file in the top-level directory. 6 */ 7 #include "qemu/osdep.h" 8 #include "qemu/qht.h" 9 #include "qemu/rcu.h" 10 11 #define N 5000 12 13 static struct qht ht; 14 static int32_t arr[N * 2]; 15 16 static bool is_equal(const void *ap, const void *bp) 17 { 18 const int32_t *a = ap; 19 const int32_t *b = bp; 20 21 return *a == *b; 22 } 23 24 static void insert(int a, int b) 25 { 26 int i; 27 28 for (i = a; i < b; i++) { 29 uint32_t hash; 30 void *existing; 31 bool inserted; 32 33 arr[i] = i; 34 hash = i; 35 36 inserted = qht_insert(&ht, &arr[i], hash, NULL); 37 g_assert_true(inserted); 38 inserted = qht_insert(&ht, &arr[i], hash, &existing); 39 g_assert_false(inserted); 40 g_assert_true(existing == &arr[i]); 41 } 42 } 43 44 static void do_rm(int init, int end, bool exist) 45 { 46 int i; 47 48 for (i = init; i < end; i++) { 49 uint32_t hash; 50 51 hash = arr[i]; 52 if (exist) { 53 g_assert_true(qht_remove(&ht, &arr[i], hash)); 54 } else { 55 g_assert_false(qht_remove(&ht, &arr[i], hash)); 56 } 57 } 58 } 59 60 static void rm(int init, int end) 61 { 62 do_rm(init, end, true); 63 } 64 65 static void rm_nonexist(int init, int end) 66 { 67 do_rm(init, end, false); 68 } 69 70 static void check(int a, int b, bool expected) 71 { 72 struct qht_stats stats; 73 int i; 74 75 rcu_read_lock(); 76 for (i = a; i < b; i++) { 77 void *p; 78 uint32_t hash; 79 int32_t val; 80 81 val = i; 82 hash = i; 83 /* test both lookup variants; results should be the same */ 84 if (i % 2) { 85 p = qht_lookup(&ht, &val, hash); 86 } else { 87 p = qht_lookup_custom(&ht, &val, hash, is_equal); 88 } 89 g_assert_true(!!p == expected); 90 } 91 rcu_read_unlock(); 92 93 qht_statistics_init(&ht, &stats); 94 if (stats.used_head_buckets) { 95 g_assert_cmpfloat(qdist_avg(&stats.chain), >=, 1.0); 96 } 97 g_assert_cmpuint(stats.head_buckets, >, 0); 98 qht_statistics_destroy(&stats); 99 } 100 101 static void count_func(struct qht *ht, void *p, uint32_t hash, void *userp) 102 { 103 unsigned int *curr = userp; 104 105 (*curr)++; 106 } 107 108 static void check_n(size_t expected) 109 { 110 struct qht_stats stats; 111 112 qht_statistics_init(&ht, &stats); 113 g_assert_cmpuint(stats.entries, ==, expected); 114 qht_statistics_destroy(&stats); 115 } 116 117 static void iter_check(unsigned int count) 118 { 119 unsigned int curr = 0; 120 121 qht_iter(&ht, count_func, &curr); 122 g_assert_cmpuint(curr, ==, count); 123 } 124 125 static void sum_func(struct qht *ht, void *p, uint32_t hash, void *userp) 126 { 127 uint32_t *sum = userp; 128 uint32_t a = *(uint32_t *)p; 129 130 *sum += a; 131 } 132 133 static void iter_sum_check(unsigned int expected) 134 { 135 unsigned int sum = 0; 136 137 qht_iter(&ht, sum_func, &sum); 138 g_assert_cmpuint(sum, ==, expected); 139 } 140 141 static bool rm_mod_func(struct qht *ht, void *p, uint32_t hash, void *userp) 142 { 143 uint32_t a = *(uint32_t *)p; 144 unsigned int mod = *(unsigned int *)userp; 145 146 return a % mod == 0; 147 } 148 149 static void iter_rm_mod(unsigned int mod) 150 { 151 qht_iter_remove(&ht, rm_mod_func, &mod); 152 } 153 154 static void iter_rm_mod_check(unsigned int mod) 155 { 156 unsigned int expected = 0; 157 unsigned int i; 158 159 for (i = 0; i < N; i++) { 160 if (i % mod == 0) { 161 continue; 162 } 163 expected += i; 164 } 165 iter_sum_check(expected); 166 } 167 168 static void qht_do_test(unsigned int mode, size_t init_entries) 169 { 170 /* under KVM we might fetch stats from an uninitialized qht */ 171 check_n(0); 172 173 qht_init(&ht, is_equal, 0, mode); 174 rm_nonexist(0, 4); 175 insert(0, 4); 176 rm_nonexist(5, 6); 177 insert(4, 6); 178 rm_nonexist(7, 8); 179 iter_rm_mod(1); 180 181 check_n(0); 182 rm_nonexist(0, 10); 183 insert(0, N); 184 check(0, N, true); 185 check_n(N); 186 check(-N, -1, false); 187 iter_check(N); 188 189 rm(101, 102); 190 check_n(N - 1); 191 insert(N, N * 2); 192 check_n(N + N - 1); 193 rm(N, N * 2); 194 check_n(N - 1); 195 insert(101, 102); 196 check_n(N); 197 198 rm(10, 200); 199 check_n(N - 190); 200 insert(150, 200); 201 check_n(N - 190 + 50); 202 insert(10, 150); 203 check_n(N); 204 205 qht_reset(&ht); 206 insert(0, N); 207 rm_nonexist(N, N + 32); 208 iter_rm_mod(10); 209 iter_rm_mod_check(10); 210 check_n(N * 9 / 10); 211 qht_reset_size(&ht, 0); 212 check_n(0); 213 check(0, N, false); 214 215 qht_destroy(&ht); 216 } 217 218 static void qht_test(unsigned int mode) 219 { 220 qht_do_test(mode, 0); 221 qht_do_test(mode, 1); 222 qht_do_test(mode, 2); 223 qht_do_test(mode, 8); 224 qht_do_test(mode, 16); 225 qht_do_test(mode, 8192); 226 qht_do_test(mode, 16384); 227 } 228 229 static void test_default(void) 230 { 231 qht_test(0); 232 } 233 234 static void test_resize(void) 235 { 236 qht_test(QHT_MODE_AUTO_RESIZE); 237 } 238 239 int main(int argc, char *argv[]) 240 { 241 g_test_init(&argc, &argv, NULL); 242 g_test_add_func("/qht/mode/default", test_default); 243 g_test_add_func("/qht/mode/resize", test_resize); 244 return g_test_run(); 245 } 246