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
28TEST(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
78TEST(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
110TEST(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
138static uint32_t hash_int(const void *p)
139{
140   int i = *(const int *)p;
141   return i;
142}
143
144static 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
150TEST(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