Emilio G. Cota | 1a95404 | 2016-06-08 14:55:29 -0400 | [diff] [blame] | 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" |
Emilio G. Cota | 1a95404 | 2016-06-08 14:55:29 -0400 | [diff] [blame] | 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 | qht_init(&ht, 0, mode); |
| 99 | |
| 100 | insert(0, N); |
| 101 | check(0, N, true); |
| 102 | check_n(N); |
| 103 | check(-N, -1, false); |
| 104 | iter_check(N); |
| 105 | |
| 106 | rm(101, 102); |
| 107 | check_n(N - 1); |
| 108 | insert(N, N * 2); |
| 109 | check_n(N + N - 1); |
| 110 | rm(N, N * 2); |
| 111 | check_n(N - 1); |
| 112 | insert(101, 102); |
| 113 | check_n(N); |
| 114 | |
| 115 | rm(10, 200); |
| 116 | check_n(N - 190); |
| 117 | insert(150, 200); |
| 118 | check_n(N - 190 + 50); |
| 119 | insert(10, 150); |
| 120 | check_n(N); |
| 121 | |
| 122 | rm(1, 2); |
| 123 | check_n(N - 1); |
| 124 | qht_reset_size(&ht, 0); |
| 125 | check_n(0); |
| 126 | check(0, N, false); |
| 127 | |
| 128 | qht_destroy(&ht); |
| 129 | } |
| 130 | |
| 131 | static void qht_test(unsigned int mode) |
| 132 | { |
| 133 | qht_do_test(mode, 0); |
| 134 | qht_do_test(mode, 1); |
| 135 | qht_do_test(mode, 2); |
| 136 | qht_do_test(mode, 8); |
| 137 | qht_do_test(mode, 16); |
| 138 | qht_do_test(mode, 8192); |
| 139 | qht_do_test(mode, 16384); |
| 140 | } |
| 141 | |
| 142 | static void test_default(void) |
| 143 | { |
| 144 | qht_test(0); |
| 145 | } |
| 146 | |
| 147 | static void test_resize(void) |
| 148 | { |
| 149 | qht_test(QHT_MODE_AUTO_RESIZE); |
| 150 | } |
| 151 | |
| 152 | int main(int argc, char *argv[]) |
| 153 | { |
| 154 | g_test_init(&argc, &argv, NULL); |
| 155 | g_test_add_func("/qht/mode/default", test_default); |
| 156 | g_test_add_func("/qht/mode/resize", test_resize); |
| 157 | return g_test_run(); |
| 158 | } |