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 31 arr[i] = i; 32 hash = i; 33 34 qht_insert(&ht, &arr[i], hash); 35 } 36 } 37 38 static void rm(int init, int end) 39 { 40 int i; 41 42 for (i = init; i < end; i++) { 43 uint32_t hash; 44 45 hash = arr[i]; 46 g_assert_true(qht_remove(&ht, &arr[i], hash)); 47 } 48 } 49 50 static void check(int a, int b, bool expected) 51 { 52 struct qht_stats stats; 53 int i; 54 55 rcu_read_lock(); 56 for (i = a; i < b; i++) { 57 void *p; 58 uint32_t hash; 59 int32_t val; 60 61 val = i; 62 hash = i; 63 /* test both lookup variants; results should be the same */ 64 if (i % 2) { 65 p = qht_lookup(&ht, &val, hash); 66 } else { 67 p = qht_lookup_custom(&ht, &val, hash, is_equal); 68 } 69 g_assert_true(!!p == expected); 70 } 71 rcu_read_unlock(); 72 73 qht_statistics_init(&ht, &stats); 74 if (stats.used_head_buckets) { 75 g_assert_cmpfloat(qdist_avg(&stats.chain), >=, 1.0); 76 } 77 g_assert_cmpuint(stats.head_buckets, >, 0); 78 qht_statistics_destroy(&stats); 79 } 80 81 static void count_func(struct qht *ht, void *p, uint32_t hash, void *userp) 82 { 83 unsigned int *curr = userp; 84 85 (*curr)++; 86 } 87 88 static void check_n(size_t expected) 89 { 90 struct qht_stats stats; 91 92 qht_statistics_init(&ht, &stats); 93 g_assert_cmpuint(stats.entries, ==, expected); 94 qht_statistics_destroy(&stats); 95 } 96 97 static void iter_check(unsigned int count) 98 { 99 unsigned int curr = 0; 100 101 qht_iter(&ht, count_func, &curr); 102 g_assert_cmpuint(curr, ==, count); 103 } 104 105 static void qht_do_test(unsigned int mode, size_t init_entries) 106 { 107 /* under KVM we might fetch stats from an uninitialized qht */ 108 check_n(0); 109 110 qht_init(&ht, is_equal, 0, mode); 111 112 check_n(0); 113 insert(0, N); 114 check(0, N, true); 115 check_n(N); 116 check(-N, -1, false); 117 iter_check(N); 118 119 rm(101, 102); 120 check_n(N - 1); 121 insert(N, N * 2); 122 check_n(N + N - 1); 123 rm(N, N * 2); 124 check_n(N - 1); 125 insert(101, 102); 126 check_n(N); 127 128 rm(10, 200); 129 check_n(N - 190); 130 insert(150, 200); 131 check_n(N - 190 + 50); 132 insert(10, 150); 133 check_n(N); 134 135 rm(1, 2); 136 check_n(N - 1); 137 qht_reset_size(&ht, 0); 138 check_n(0); 139 check(0, N, false); 140 141 qht_destroy(&ht); 142 } 143 144 static void qht_test(unsigned int mode) 145 { 146 qht_do_test(mode, 0); 147 qht_do_test(mode, 1); 148 qht_do_test(mode, 2); 149 qht_do_test(mode, 8); 150 qht_do_test(mode, 16); 151 qht_do_test(mode, 8192); 152 qht_do_test(mode, 16384); 153 } 154 155 static void test_default(void) 156 { 157 qht_test(0); 158 } 159 160 static void test_resize(void) 161 { 162 qht_test(QHT_MODE_AUTO_RESIZE); 163 } 164 165 int main(int argc, char *argv[]) 166 { 167 g_test_init(&argc, &argv, NULL); 168 g_test_add_func("/qht/mode/default", test_default); 169 g_test_add_func("/qht/mode/resize", test_resize); 170 return g_test_run(); 171 } 172