1 // Protocol Buffers - Google's data interchange format
2 // Copyright 2023 Google LLC. All rights reserved.
3 //
4 // Use of this source code is governed by a BSD-style
5 // license that can be found in the LICENSE file or at
6 // https://developers.google.com/open-source/licenses/bsd
7
8 // Tests for upb_table.
9
10 #include <limits.h>
11 #include <string.h>
12
13 #include <iostream>
14 #include <map>
15 #include <set>
16 #include <string>
17 #include <vector>
18
19 #include <gtest/gtest.h>
20 #include "absl/container/flat_hash_map.h"
21 #include "upb/hash/int_table.h"
22 #include "upb/hash/str_table.h"
23 #include "upb/mem/arena.hpp"
24
25 // Must be last.
26 #include "upb/port/def.inc"
27
28 using std::vector;
29
TEST(Table,StringTable)30 TEST(Table, StringTable) {
31 vector<std::string> keys;
32 keys.push_back("google.protobuf.FileDescriptorSet");
33 keys.push_back("google.protobuf.FileDescriptorProto");
34 keys.push_back("google.protobuf.DescriptorProto");
35 keys.push_back("google.protobuf.DescriptorProto.ExtensionRange");
36 keys.push_back("google.protobuf.FieldDescriptorProto");
37 keys.push_back("google.protobuf.EnumDescriptorProto");
38 keys.push_back("google.protobuf.EnumValueDescriptorProto");
39 keys.push_back("google.protobuf.ServiceDescriptorProto");
40 keys.push_back("google.protobuf.MethodDescriptorProto");
41 keys.push_back("google.protobuf.FileOptions");
42 keys.push_back("google.protobuf.MessageOptions");
43 keys.push_back("google.protobuf.FieldOptions");
44 keys.push_back("google.protobuf.EnumOptions");
45 keys.push_back("google.protobuf.EnumValueOptions");
46 keys.push_back("google.protobuf.ServiceOptions");
47 keys.push_back("google.protobuf.MethodOptions");
48 keys.push_back("google.protobuf.UninterpretedOption");
49 keys.push_back("google.protobuf.UninterpretedOption.NamePart");
50
51 /* Initialize structures. */
52 upb::Arena arena;
53 upb_strtable t;
54 upb_strtable_init(&t, keys.size(), arena.ptr());
55 std::map<std::string, int32_t> m;
56 std::set<std::string> all;
57 for (const auto& key : keys) {
58 all.insert(key);
59 upb_value val = {uint64_t(key[0])};
60 upb_strtable_insert(&t, key.data(), key.size(), val, arena.ptr());
61 m[key] = key[0];
62 }
63
64 /* Test correctness. */
65 for (const auto& key : keys) {
66 upb_value val;
67 bool ok = upb_strtable_lookup2(&t, key.data(), key.size(), &val);
68 EXPECT_TRUE(ok);
69 EXPECT_EQ(val.val, uint64_t(key[0]));
70 EXPECT_EQ(m[key], key[0]);
71 }
72
73 intptr_t iter = UPB_STRTABLE_BEGIN;
74 upb_StringView key;
75 upb_value val;
76 while (upb_strtable_next2(&t, &key, &val, &iter)) {
77 std::set<std::string>::iterator i = all.find(key.data);
78 EXPECT_NE(i, all.end());
79 all.erase(i);
80 }
81 EXPECT_TRUE(all.empty());
82
83 // Test iteration with resizes.
84
85 for (int i = 0; i < 10; i++) {
86 intptr_t iter = UPB_STRTABLE_BEGIN;
87 while (upb_strtable_next2(&t, &key, &val, &iter)) {
88 // Even if we invalidate the iterator it should only return real elements.
89 EXPECT_EQ(val.val, m[key.data]);
90
91 // Force a resize even though the size isn't changing.
92 // Also forces the table size to grow so some new buckets end up empty.
93 bool ok = upb_strtable_resize(&t, 5 + i, arena.ptr());
94 EXPECT_TRUE(ok);
95 }
96 }
97 }
98
99 class IntTableTest : public testing::TestWithParam<int> {
SetUp()100 void SetUp() override {
101 if (GetParam() > 0) {
102 for (int i = 0; i < GetParam(); i++) {
103 keys_.push_back(i + 1);
104 }
105 } else {
106 for (int32_t i = 0; i < 64; i++) {
107 if (i < 32)
108 keys_.push_back(i + 1);
109 else
110 keys_.push_back(10101 + i);
111 }
112 }
113 }
114
115 protected:
116 std::vector<int32_t> keys_;
117 };
118
TEST_P(IntTableTest,TestIntTable)119 TEST_P(IntTableTest, TestIntTable) {
120 /* Initialize structures. */
121 upb::Arena arena;
122 upb_inttable t;
123 upb_inttable_init(&t, arena.ptr());
124 uint32_t largest_key = 0;
125 std::map<uint32_t, uint32_t> m;
126 absl::flat_hash_map<uint32_t, uint32_t> hm;
127 for (const auto& key : keys_) {
128 largest_key = UPB_MAX((int32_t)largest_key, key);
129 upb_value val = upb_value_uint32(key * 2);
130 bool ok = upb_inttable_insert(&t, key, val, arena.ptr());
131 EXPECT_TRUE(ok);
132 m[key] = key * 2;
133 hm[key] = key * 2;
134 }
135 EXPECT_EQ(upb_inttable_count(&t), keys_.size());
136
137 /* Test correctness. */
138 int count = 0;
139 for (uint32_t i = 0; i <= largest_key; i++) {
140 upb_value val;
141 bool ok = upb_inttable_lookup(&t, i, &val);
142 if (ok) { /* Assume map implementation is correct. */
143 EXPECT_EQ(val.val, i * 2);
144 EXPECT_EQ(m[i], i * 2);
145 EXPECT_EQ(hm[i], i * 2);
146 count++;
147 }
148 }
149 EXPECT_EQ(count, keys_.size());
150 EXPECT_EQ(count, upb_inttable_count(&t));
151
152 // Test replace.
153 count = 0;
154 for (uint32_t i = 0; i <= largest_key; i++) {
155 upb_value val = upb_value_uint32(i * 3);
156 bool ok = upb_inttable_replace(&t, i, val);
157 if (ok) { /* Assume map implementation is correct. */
158 m[i] = i * 3;
159 hm[i] = i * 3;
160 count++;
161 }
162 }
163 EXPECT_EQ(count, keys_.size());
164 EXPECT_EQ(count, upb_inttable_count(&t));
165
166 // Compact and test correctness again.
167 upb_inttable_compact(&t, arena.ptr());
168 count = 0;
169 for (uint32_t i = 0; i <= largest_key; i++) {
170 upb_value val;
171 bool ok = upb_inttable_lookup(&t, i, &val);
172 if (ok) { /* Assume map implementation is correct. */
173 EXPECT_EQ(val.val, i * 3);
174 EXPECT_EQ(m[i], i * 3);
175 EXPECT_EQ(hm[i], i * 3);
176 count++;
177 }
178 }
179 EXPECT_EQ(count, keys_.size());
180 EXPECT_EQ(count, upb_inttable_count(&t));
181
182 for (const auto& key : keys_) {
183 upb_value val;
184 bool ok = upb_inttable_remove(&t, key, &val);
185 EXPECT_TRUE(ok);
186 EXPECT_EQ(val.val, (uint32_t)key * 3);
187 count--;
188 EXPECT_EQ(count, upb_inttable_count(&t));
189 }
190 EXPECT_EQ(0, upb_inttable_count(&t));
191 }
192
193 INSTANTIATE_TEST_SUITE_P(IntTableParams, IntTableTest,
194 testing::Values(8, 64, 512, -32));
195
196 /*
197 * This test can't pass right now because the table can't store a value of
198 * (uint64_t)-1.
199 */
TEST(Table,MaxValue)200 TEST(Table, MaxValue) {
201 /*
202 typedef upb::TypedIntTable<uint64_t> Table;
203 Table table;
204 uintptr_t uint64_max = (uint64_t)-1;
205 table.Insert(1, uint64_max);
206 std::pair<bool, uint64_t> found = table.Lookup(1);
207 ASSERT(found.first);
208 ASSERT(found.second == uint64_max);
209 */
210 }
211
TEST(Table,Delete)212 TEST(Table, Delete) {
213 upb::Arena arena;
214 upb_inttable t;
215 upb_inttable_init(&t, arena.ptr());
216 upb_inttable_insert(&t, 0, upb_value_bool(true), arena.ptr());
217 upb_inttable_insert(&t, 2, upb_value_bool(true), arena.ptr());
218 upb_inttable_insert(&t, 4, upb_value_bool(true), arena.ptr());
219 upb_inttable_compact(&t, arena.ptr());
220 upb_inttable_remove(&t, 0, nullptr);
221 upb_inttable_remove(&t, 2, nullptr);
222 upb_inttable_remove(&t, 4, nullptr);
223
224 intptr_t iter = UPB_INTTABLE_BEGIN;
225 uintptr_t key;
226 upb_value val;
227 while (upb_inttable_next(&t, &key, &val, &iter)) {
228 FAIL();
229 }
230 }
231
TEST(Table,Init)232 TEST(Table, Init) {
233 for (int i = 0; i < 2048; i++) {
234 /* Tests that the size calculations in init() (lg2 size for target load)
235 * work for all expected sizes. */
236 upb::Arena arena;
237 upb_strtable t;
238 upb_strtable_init(&t, i, arena.ptr());
239 }
240 }
241