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