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 rm(int init, int end) 45 { 46 int i; 47 48 for (i = init; i < end; i++) { 49 uint32_t hash; 50 51 hash = arr[i]; 52 g_assert_true(qht_remove(&ht, &arr[i], hash)); 53 } 54 } 55 56 static void check(int a, int b, bool expected) 57 { 58 struct qht_stats stats; 59 int i; 60 61 rcu_read_lock(); 62 for (i = a; i < b; i++) { 63 void *p; 64 uint32_t hash; 65 int32_t val; 66 67 val = i; 68 hash = i; 69 /* test both lookup variants; results should be the same */ 70 if (i % 2) { 71 p = qht_lookup(&ht, &val, hash); 72 } else { 73 p = qht_lookup_custom(&ht, &val, hash, is_equal); 74 } 75 g_assert_true(!!p == expected); 76 } 77 rcu_read_unlock(); 78 79 qht_statistics_init(&ht, &stats); 80 if (stats.used_head_buckets) { 81 g_assert_cmpfloat(qdist_avg(&stats.chain), >=, 1.0); 82 } 83 g_assert_cmpuint(stats.head_buckets, >, 0); 84 qht_statistics_destroy(&stats); 85 } 86 87 static void count_func(struct qht *ht, void *p, uint32_t hash, void *userp) 88 { 89 unsigned int *curr = userp; 90 91 (*curr)++; 92 } 93 94 static void check_n(size_t expected) 95 { 96 struct qht_stats stats; 97 98 qht_statistics_init(&ht, &stats); 99 g_assert_cmpuint(stats.entries, ==, expected); 100 qht_statistics_destroy(&stats); 101 } 102 103 static void iter_check(unsigned int count) 104 { 105 unsigned int curr = 0; 106 107 qht_iter(&ht, count_func, &curr); 108 g_assert_cmpuint(curr, ==, count); 109 } 110 111 static void sum_func(struct qht *ht, void *p, uint32_t hash, void *userp) 112 { 113 uint32_t *sum = userp; 114 uint32_t a = *(uint32_t *)p; 115 116 *sum += a; 117 } 118 119 static void iter_sum_check(unsigned int expected) 120 { 121 unsigned int sum = 0; 122 123 qht_iter(&ht, sum_func, &sum); 124 g_assert_cmpuint(sum, ==, expected); 125 } 126 127 static bool rm_mod_func(struct qht *ht, void *p, uint32_t hash, void *userp) 128 { 129 uint32_t a = *(uint32_t *)p; 130 unsigned int mod = *(unsigned int *)userp; 131 132 return a % mod == 0; 133 } 134 135 static void iter_rm_mod(unsigned int mod) 136 { 137 qht_iter_remove(&ht, rm_mod_func, &mod); 138 } 139 140 static void iter_rm_mod_check(unsigned int mod) 141 { 142 unsigned int expected = 0; 143 unsigned int i; 144 145 for (i = 0; i < N; i++) { 146 if (i % mod == 0) { 147 continue; 148 } 149 expected += i; 150 } 151 iter_sum_check(expected); 152 } 153 154 static void qht_do_test(unsigned int mode, size_t init_entries) 155 { 156 /* under KVM we might fetch stats from an uninitialized qht */ 157 check_n(0); 158 159 qht_init(&ht, is_equal, 0, mode); 160 161 check_n(0); 162 insert(0, N); 163 check(0, N, true); 164 check_n(N); 165 check(-N, -1, false); 166 iter_check(N); 167 168 rm(101, 102); 169 check_n(N - 1); 170 insert(N, N * 2); 171 check_n(N + N - 1); 172 rm(N, N * 2); 173 check_n(N - 1); 174 insert(101, 102); 175 check_n(N); 176 177 rm(10, 200); 178 check_n(N - 190); 179 insert(150, 200); 180 check_n(N - 190 + 50); 181 insert(10, 150); 182 check_n(N); 183 184 qht_reset(&ht); 185 insert(0, N); 186 iter_rm_mod(10); 187 iter_rm_mod_check(10); 188 check_n(N * 9 / 10); 189 qht_reset_size(&ht, 0); 190 check_n(0); 191 check(0, N, false); 192 193 qht_destroy(&ht); 194 } 195 196 static void qht_test(unsigned int mode) 197 { 198 qht_do_test(mode, 0); 199 qht_do_test(mode, 1); 200 qht_do_test(mode, 2); 201 qht_do_test(mode, 8); 202 qht_do_test(mode, 16); 203 qht_do_test(mode, 8192); 204 qht_do_test(mode, 16384); 205 } 206 207 static void test_default(void) 208 { 209 qht_test(0); 210 } 211 212 static void test_resize(void) 213 { 214 qht_test(QHT_MODE_AUTO_RESIZE); 215 } 216 217 int main(int argc, char *argv[]) 218 { 219 g_test_init(&argc, &argv, NULL); 220 g_test_add_func("/qht/mode/default", test_default); 221 g_test_add_func("/qht/mode/resize", test_resize); 222 return g_test_run(); 223 } 224