cirrus: fix off-by-one in cirrus_bitblt_rop_bkwd_transp_*_16
[qemu.git] / tests / test-qht.c
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 *obj, const void *userp)
17 {
18 const int32_t *a = obj;
19 const int32_t *b = userp;
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 p = qht_lookup(&ht, is_equal, &val, hash);
64 g_assert_true(!!p == expected);
65 }
66 rcu_read_unlock();
67
68 qht_statistics_init(&ht, &stats);
69 if (stats.used_head_buckets) {
70 g_assert_cmpfloat(qdist_avg(&stats.chain), >=, 1.0);
71 }
72 g_assert_cmpuint(stats.head_buckets, >, 0);
73 qht_statistics_destroy(&stats);
74 }
75
76 static void count_func(struct qht *ht, void *p, uint32_t hash, void *userp)
77 {
78 unsigned int *curr = userp;
79
80 (*curr)++;
81 }
82
83 static void check_n(size_t expected)
84 {
85 struct qht_stats stats;
86
87 qht_statistics_init(&ht, &stats);
88 g_assert_cmpuint(stats.entries, ==, expected);
89 qht_statistics_destroy(&stats);
90 }
91
92 static void iter_check(unsigned int count)
93 {
94 unsigned int curr = 0;
95
96 qht_iter(&ht, count_func, &curr);
97 g_assert_cmpuint(curr, ==, count);
98 }
99
100 static void qht_do_test(unsigned int mode, size_t init_entries)
101 {
102 /* under KVM we might fetch stats from an uninitialized qht */
103 check_n(0);
104
105 qht_init(&ht, 0, mode);
106
107 check_n(0);
108 insert(0, N);
109 check(0, N, true);
110 check_n(N);
111 check(-N, -1, false);
112 iter_check(N);
113
114 rm(101, 102);
115 check_n(N - 1);
116 insert(N, N * 2);
117 check_n(N + N - 1);
118 rm(N, N * 2);
119 check_n(N - 1);
120 insert(101, 102);
121 check_n(N);
122
123 rm(10, 200);
124 check_n(N - 190);
125 insert(150, 200);
126 check_n(N - 190 + 50);
127 insert(10, 150);
128 check_n(N);
129
130 rm(1, 2);
131 check_n(N - 1);
132 qht_reset_size(&ht, 0);
133 check_n(0);
134 check(0, N, false);
135
136 qht_destroy(&ht);
137 }
138
139 static void qht_test(unsigned int mode)
140 {
141 qht_do_test(mode, 0);
142 qht_do_test(mode, 1);
143 qht_do_test(mode, 2);
144 qht_do_test(mode, 8);
145 qht_do_test(mode, 16);
146 qht_do_test(mode, 8192);
147 qht_do_test(mode, 16384);
148 }
149
150 static void test_default(void)
151 {
152 qht_test(0);
153 }
154
155 static void test_resize(void)
156 {
157 qht_test(QHT_MODE_AUTO_RESIZE);
158 }
159
160 int main(int argc, char *argv[])
161 {
162 g_test_init(&argc, &argv, NULL);
163 g_test_add_func("/qht/mode/default", test_default);
164 g_test_add_func("/qht/mode/resize", test_resize);
165 return g_test_run();
166 }