1 /*
2 * Copyright © 2018 Intel Corporation
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining a
5 * copy of this software and associated documentation files (the "Software"),
6 * to deal in the Software without restriction, including without limitation
7 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8 * and/or sell copies of the Software, and to permit persons to whom the
9 * Software is furnished to do so, subject to the following conditions:
10 *
11 * The above copyright notice and this permission notice (including the next
12 * paragraph) shall be included in all copies or substantial portions of the
13 * Software.
14 *
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
18 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
20 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
21 * IN THE SOFTWARE.
22 */
23
24 #include <gtest/gtest.h>
25 #include "util/hash_table.h"
26 #include "util/set.h"
27
TEST(set,basic)28 TEST(set, basic)
29 {
30 struct set *s = _mesa_set_create(NULL, _mesa_hash_pointer,
31 _mesa_key_pointer_equal);
32 struct set_entry *entry;
33
34 const void *a = (const void *)10;
35 const void *b = (const void *)20;
36
37 _mesa_set_add(s, a);
38 _mesa_set_add(s, b);
39 EXPECT_EQ(s->entries, 2);
40
41 _mesa_set_add(s, a);
42 EXPECT_EQ(s->entries, 2);
43
44 entry = _mesa_set_search(s, a);
45 EXPECT_TRUE(entry);
46 EXPECT_EQ(entry->key, a);
47
48 _mesa_set_remove(s, entry);
49 EXPECT_EQ(s->entries, 1);
50
51 entry = _mesa_set_search(s, a);
52 EXPECT_FALSE(entry);
53
54 _mesa_set_clear(s, NULL);
55 EXPECT_EQ(s->entries, 0);
56 EXPECT_EQ(s->deleted_entries, 0);
57 set_foreach(s, he) {
58 GTEST_FAIL();
59 }
60
61 _mesa_set_add(s, a);
62 _mesa_set_add(s, b);
63 EXPECT_EQ(s->entries, 2);
64 unsigned count = s->entries;
65 set_foreach_remove(s, he) {
66 EXPECT_TRUE(he->key == a || he->key == b);
67 EXPECT_EQ(s->entries, count--);
68 EXPECT_EQ(s->deleted_entries, 0);
69 }
70 EXPECT_EQ(s->entries, 0);
71 set_foreach(s, he) {
72 GTEST_FAIL();
73 }
74
75 _mesa_set_destroy(s, NULL);
76 }
77
TEST(set,clone)78 TEST(set, clone)
79 {
80 struct set *s = _mesa_set_create(NULL, _mesa_hash_pointer,
81 _mesa_key_pointer_equal);
82 struct set_entry *entry;
83
84 const void *a = (const void *)10;
85 const void *b = (const void *)20;
86 const void *c = (const void *)30;
87
88 _mesa_set_add(s, a);
89 _mesa_set_add(s, b);
90 _mesa_set_add(s, c);
91
92 entry = _mesa_set_search(s, c);
93 EXPECT_TRUE(entry);
94 EXPECT_EQ(entry->key, c);
95
96 _mesa_set_remove(s, entry);
97 EXPECT_EQ(s->entries, 2);
98
99 struct set *clone = _mesa_set_clone(s, NULL);
100 EXPECT_EQ(clone->entries, 2);
101
102 EXPECT_TRUE(_mesa_set_search(clone, a));
103 EXPECT_TRUE(_mesa_set_search(clone, b));
104 EXPECT_FALSE(_mesa_set_search(clone, c));
105
106 _mesa_set_destroy(s, NULL);
107 _mesa_set_destroy(clone, NULL);
108 }
109
TEST(set,remove_key)110 TEST(set, remove_key)
111 {
112 struct set *s = _mesa_set_create(NULL, _mesa_hash_pointer,
113 _mesa_key_pointer_equal);
114
115 const void *a = (const void *)10;
116 const void *b = (const void *)20;
117 const void *c = (const void *)30;
118
119 _mesa_set_add(s, a);
120 _mesa_set_add(s, b);
121 EXPECT_EQ(s->entries, 2);
122
123 /* Remove existing key. */
124 _mesa_set_remove_key(s, a);
125 EXPECT_EQ(s->entries, 1);
126 EXPECT_FALSE(_mesa_set_search(s, a));
127 EXPECT_TRUE(_mesa_set_search(s, b));
128
129 /* Remove non-existing key. */
130 _mesa_set_remove_key(s, c);
131 EXPECT_EQ(s->entries, 1);
132 EXPECT_FALSE(_mesa_set_search(s, a));
133 EXPECT_TRUE(_mesa_set_search(s, b));
134
135 _mesa_set_destroy(s, NULL);
136 }
137
hash_int(const void * p)138 static uint32_t hash_int(const void *p)
139 {
140 int i = *(const int *)p;
141 return i;
142 }
143
cmp_int(const void * p1,const void * p2)144 static bool cmp_int(const void *p1, const void *p2)
145 {
146 int i1 = *(const int *)p1, i2 = *(const int *)p2;
147 return i1 == i2;
148 }
149
TEST(set,search_or_add)150 TEST(set, search_or_add)
151 {
152 struct set *s = _mesa_set_create(NULL, hash_int, cmp_int);
153
154 int a = 10, b = 20, c = 20, d = 30;
155
156 _mesa_set_add(s, &a);
157 _mesa_set_add(s, &b);
158 EXPECT_EQ(s->entries, 2);
159
160 bool found = false;
161 struct set_entry *entry = _mesa_set_search_or_add(s, &c, &found);
162 EXPECT_EQ(entry->key, (void *)&b);
163 EXPECT_EQ(found, true);
164 EXPECT_EQ(s->entries, 2);
165
166 found = false;
167 struct set_entry *entry3 = _mesa_set_search_or_add(s, &d, &found);
168 EXPECT_EQ(entry3->key, &d);
169 EXPECT_EQ(found, false);
170 EXPECT_EQ(s->entries, 3);
171
172 _mesa_set_destroy(s, NULL);
173 }
174