]>
Commit | Line | Data |
---|---|---|
1a95404f EC |
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" | |
1a95404f | 8 | #include "qemu/qht.h" |
9c7d64eb | 9 | #include "qemu/rcu.h" |
1a95404f EC |
10 | |
11 | #define N 5000 | |
12 | ||
13 | static struct qht ht; | |
14 | static int32_t arr[N * 2]; | |
15 | ||
61b8cef1 | 16 | static bool is_equal(const void *ap, const void *bp) |
1a95404f | 17 | { |
61b8cef1 EC |
18 | const int32_t *a = ap; |
19 | const int32_t *b = bp; | |
1a95404f EC |
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 | ||
9c7d64eb | 55 | rcu_read_lock(); |
1a95404f EC |
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; | |
61b8cef1 EC |
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 | } | |
1a95404f EC |
69 | g_assert_true(!!p == expected); |
70 | } | |
9c7d64eb EC |
71 | rcu_read_unlock(); |
72 | ||
1a95404f EC |
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 | { | |
7266ae91 EC |
107 | /* under KVM we might fetch stats from an uninitialized qht */ |
108 | check_n(0); | |
109 | ||
61b8cef1 | 110 | qht_init(&ht, is_equal, 0, mode); |
1a95404f | 111 | |
7266ae91 | 112 | check_n(0); |
1a95404f EC |
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 | } |