1// SPDX-License-Identifier: GPL-3.0-or-later
2
3#include "test_engine_impl.h"
4
5#include <mos/lib/structures/hashmap.h>
6#include <mos/lib/structures/hashmap_common.h>
7#include <mos/mos_global.h>
8
9#define HASHMAP_MAGIC MOS_FOURCC('H', 'M', 'a', 'p')
10
11MOS_TEST_CASE(hashmap_init_simple_macro)
12{
13 hashmap_t map = { 0 };
14 hashmap_common_type_init(&map, 64, string);
15 MOS_TEST_CHECK(map.magic, HASHMAP_MAGIC);
16 MOS_TEST_CHECK(map.capacity, 64);
17 MOS_TEST_CHECK(map.size, 0);
18 MOS_TEST_CHECK(map.hash_func, hashmap_hash_string);
19 MOS_TEST_CHECK(map.key_compare_func, hashmap_compare_string);
20 MOS_TEST_CHECK(map.entries != NULL, true);
21 hashmap_deinit(map: &map);
22}
23
24MOS_TEST_CASE(hashmap_put_single)
25{
26 hashmap_t map = { 0 };
27 hashmap_common_type_init(&map, 135, string);
28 MOS_TEST_CHECK(map.magic, HASHMAP_MAGIC);
29
30 MOS_TEST_CHECK(map.capacity, 135);
31 MOS_TEST_CHECK(map.size, 0);
32 void *old = hashmap_put(map: &map, key: (ptr_t) "foo", value: "bar");
33 MOS_TEST_CHECK(old, NULL);
34 MOS_TEST_CHECK(map.capacity, 135);
35 MOS_TEST_CHECK(map.size, 1);
36
37 MOS_TEST_CHECK_STRING((const char *) hashmap_get(&map, (ptr_t) "foo"), "bar");
38 hashmap_deinit(map: &map);
39}
40
41MOS_TEST_CASE(hashmap_get_function)
42{
43 hashmap_t map = { 0 };
44 hashmap_common_type_init(&map, 1, string);
45 MOS_TEST_CHECK(map.magic, HASHMAP_MAGIC);
46 MOS_TEST_CHECK(map.capacity, 1);
47 MOS_TEST_CHECK(map.size, 0);
48
49 hashmap_put(map: &map, key: (ptr_t) "foo", value: "foo1");
50 MOS_TEST_CHECK(map.capacity, 1);
51 MOS_TEST_CHECK(map.size, 1);
52 MOS_TEST_CHECK_STRING((const char *) hashmap_get(&map, (ptr_t) "foo"), "foo1");
53
54 hashmap_put(map: &map, key: (ptr_t) "bar", value: "bar1");
55 MOS_TEST_CHECK(map.capacity, 1);
56 MOS_TEST_CHECK(map.size, 2);
57 MOS_TEST_CHECK_STRING((const char *) hashmap_get(&map, (ptr_t) "bar"), "bar1");
58
59 hashmap_put(map: &map, key: (ptr_t) "bar", value: "bar2");
60 MOS_TEST_CHECK(map.capacity, 1);
61 MOS_TEST_CHECK(map.size, 2);
62 MOS_TEST_CHECK_STRING((const char *) hashmap_get(&map, (ptr_t) "bar"), "bar2");
63
64 hashmap_deinit(map: &map);
65}
66
67MOS_TEST_CASE(hashmap_put_multiple)
68{
69 hashmap_t map = { 0 };
70 const char *old;
71 hashmap_common_type_init(&map, 135, string);
72 MOS_TEST_CHECK(map.magic, HASHMAP_MAGIC);
73 MOS_TEST_CHECK(map.capacity, 135);
74 MOS_TEST_CHECK(map.size, 0);
75
76 old = hashmap_put(map: &map, key: (ptr_t) "foo", value: "foo1");
77 MOS_TEST_CHECK(old, NULL);
78 MOS_TEST_CHECK(map.capacity, 135);
79 MOS_TEST_CHECK(map.size, 1);
80 MOS_TEST_CHECK_STRING((const char *) hashmap_get(&map, (ptr_t) "foo"), "foo1");
81
82 old = hashmap_put(map: &map, key: (ptr_t) "foo", value: "foo2");
83 MOS_TEST_CHECK(map.capacity, 135);
84 MOS_TEST_CHECK(map.size, 1);
85 MOS_TEST_CHECK_STRING(old, "foo1");
86 MOS_TEST_CHECK_STRING((const char *) hashmap_get(&map, (ptr_t) "foo"), "foo2");
87
88 old = hashmap_put(map: &map, key: (ptr_t) "bar", value: "bar1");
89 MOS_TEST_CHECK(old, NULL);
90 MOS_TEST_CHECK(map.capacity, 135);
91 MOS_TEST_CHECK(map.size, 2);
92 MOS_TEST_CHECK_STRING((const char *) hashmap_get(&map, (ptr_t) "bar"), "bar1");
93 MOS_TEST_CHECK_STRING((const char *) hashmap_get(&map, (ptr_t) "foo"), "foo2");
94
95 old = hashmap_put(map: &map, key: (ptr_t) "bar", value: "bar2");
96 MOS_TEST_CHECK(map.capacity, 135);
97 MOS_TEST_CHECK(map.size, 2);
98 MOS_TEST_CHECK_STRING(old, "bar1");
99 MOS_TEST_CHECK_STRING((const char *) hashmap_get(&map, (ptr_t) "bar"), "bar2");
100 MOS_TEST_CHECK_STRING((const char *) hashmap_get(&map, (ptr_t) "foo"), "foo2");
101 hashmap_deinit(map: &map);
102}
103
104MOS_TEST_CASE(hashmap_put_overflow)
105{
106 hashmap_t map = { 0 };
107 const char *old;
108 hashmap_common_type_init(&map, 1, string);
109 MOS_TEST_CHECK(map.magic, HASHMAP_MAGIC);
110 MOS_TEST_CHECK(map.capacity, 1);
111 MOS_TEST_CHECK(map.size, 0);
112
113 old = hashmap_put(map: &map, key: (ptr_t) "foo", value: "foo1");
114 MOS_TEST_CHECK(old, NULL);
115 MOS_TEST_CHECK(map.capacity, 1);
116 MOS_TEST_CHECK(map.size, 1);
117 MOS_TEST_CHECK_STRING((const char *) hashmap_get(&map, (ptr_t) "foo"), "foo1");
118
119 old = hashmap_put(map: &map, key: (ptr_t) "bar", value: "bar1");
120 MOS_TEST_CHECK(old, NULL);
121 MOS_TEST_CHECK(map.capacity, 1);
122 MOS_TEST_CHECK(map.size, 2);
123 MOS_TEST_CHECK_STRING((const char *) hashmap_get(&map, (ptr_t) "bar"), "bar1");
124 MOS_TEST_CHECK_STRING((const char *) hashmap_get(&map, (ptr_t) "foo"), "foo1");
125
126 old = hashmap_put(map: &map, key: (ptr_t) "bar", value: "bar2");
127 MOS_TEST_CHECK_STRING(old, "bar1");
128 MOS_TEST_CHECK(map.capacity, 1);
129 MOS_TEST_CHECK(map.size, 2);
130 MOS_TEST_CHECK_STRING((const char *) hashmap_get(&map, (ptr_t) "bar"), "bar2");
131 MOS_TEST_CHECK_STRING((const char *) hashmap_get(&map, (ptr_t) "foo"), "foo1");
132
133 hashmap_deinit(map: &map);
134}
135
136MOS_TEST_CASE(hashmap_remove_function)
137{
138 const char *old;
139 hashmap_t map = { 0 };
140 hashmap_common_type_init(&map, 10, string);
141 MOS_TEST_CHECK(map.magic, HASHMAP_MAGIC);
142 MOS_TEST_CHECK(map.capacity, 10);
143 MOS_TEST_CHECK(map.size, 0);
144
145 old = hashmap_put(map: &map, key: (ptr_t) "foo", value: "foo1");
146 MOS_TEST_CHECK(map.capacity, 10);
147 MOS_TEST_CHECK(map.size, 1);
148 MOS_TEST_CHECK(old, NULL);
149 MOS_TEST_CHECK_STRING((const char *) hashmap_get(&map, (ptr_t) "foo"), "foo1");
150
151 old = hashmap_remove(map: &map, key: (ptr_t) "foo");
152 MOS_TEST_CHECK(map.capacity, 10);
153 MOS_TEST_CHECK(map.size, 0);
154 MOS_TEST_CHECK_STRING(old, "foo1");
155 const char *nothing = hashmap_get(map: &map, key: (ptr_t) "foo");
156 MOS_TEST_CHECK(nothing, NULL);
157
158 old = hashmap_remove(map: &map, key: (ptr_t) "foo");
159 MOS_TEST_CHECK(old, NULL);
160 MOS_TEST_CHECK(map.capacity, 10);
161 MOS_TEST_CHECK(map.size, 0);
162
163 MOS_TEST_CHECK(hashmap_get(&map, (ptr_t) "foo"), NULL);
164 hashmap_deinit(map: &map);
165}
166
167static size_t test_hashmap_foreach_count = 0;
168
169bool test_foreach_function(uintn key, void *value, void *data)
170{
171 MOS_UNUSED(key);
172 MOS_UNUSED(value);
173 MOS_UNUSED(data);
174 test_hashmap_foreach_count++;
175 return true;
176}
177
178bool test_foreach_stop_at_quux(uintn key, void *value, void *data)
179{
180 MOS_UNUSED(data);
181 MOS_UNUSED(value);
182 test_hashmap_foreach_count++;
183 if (strcmp(str1: (void *) key, str2: "quux") == 0)
184 return false;
185 return true;
186}
187
188MOS_TEST_CASE(hashmap_foreach_function)
189{
190 hashmap_t map = { 0 };
191 hashmap_common_type_init(&map, 10, string);
192 MOS_TEST_CHECK(map.magic, HASHMAP_MAGIC);
193 MOS_TEST_CHECK(map.capacity, 10);
194 MOS_TEST_CHECK(map.size, 0);
195 hashmap_put(map: &map, key: (ptr_t) "foo", value: "foo1");
196 hashmap_put(map: &map, key: (ptr_t) "bar", value: "bar1");
197 hashmap_put(map: &map, key: (ptr_t) "baz", value: "baz1");
198 hashmap_put(map: &map, key: (ptr_t) "qux", value: "qux1");
199 hashmap_put(map: &map, key: (ptr_t) "quux", value: "quux1");
200 hashmap_put(map: &map, key: (ptr_t) "corge", value: "corge1");
201 hashmap_put(map: &map, key: (ptr_t) "grault", value: "grault1");
202 hashmap_put(map: &map, key: (ptr_t) "garply", value: "garply1");
203 hashmap_put(map: &map, key: (ptr_t) "waldo", value: "waldo1");
204 hashmap_put(map: &map, key: (ptr_t) "fred", value: "fred1");
205 hashmap_put(map: &map, key: (ptr_t) "plugh", value: "plugh1");
206 hashmap_put(map: &map, key: (ptr_t) "xyzzy", value: "xyzzy1");
207
208 test_hashmap_foreach_count = 0;
209 hashmap_foreach(map: &map, func: test_foreach_function, NULL);
210 MOS_TEST_CHECK(test_hashmap_foreach_count, map.size);
211
212 test_hashmap_foreach_count = 0;
213 hashmap_foreach(map: &map, func: test_foreach_stop_at_quux, NULL);
214 MOS_TEST_CHECK(test_hashmap_foreach_count, 4);
215 hashmap_deinit(map: &map);
216}
217