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