1 // Copyright (c) 2020 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "gn/string_atom.h"
6
7 #include "util/test/test.h"
8
9 #include <algorithm>
10 #include <array>
11 #include <set>
12 #include <string>
13 #include <vector>
14
TEST(StringAtomTest,EmptyString)15 TEST(StringAtomTest, EmptyString) {
16 StringAtom key1;
17 StringAtom key2("");
18
19 ASSERT_STREQ(key1.str().c_str(), "");
20 ASSERT_STREQ(key2.str().c_str(), "");
21 ASSERT_EQ(&key1.str(), &key2.str());
22 }
23
TEST(StringAtomTest,Find)24 TEST(StringAtomTest, Find) {
25 StringAtom empty;
26 EXPECT_EQ(empty.str(), std::string());
27
28 StringAtom foo("foo");
29 EXPECT_EQ(foo.str(), std::string("foo"));
30
31 StringAtom foo2("foo");
32 EXPECT_EQ(&foo.str(), &foo2.str());
33 }
34
35 // Default compare should always be ordered.
TEST(StringAtomTest,DefaultCompare)36 TEST(StringAtomTest, DefaultCompare) {
37 auto foo = StringAtom("foo");
38 auto bar = StringAtom("bar");
39 auto zoo = StringAtom("zoo");
40
41 EXPECT_TRUE(bar < foo);
42 EXPECT_TRUE(foo < zoo);
43 EXPECT_TRUE(bar < zoo);
44 }
45
TEST(StringAtomTest,NormalSet)46 TEST(StringAtomTest, NormalSet) {
47 std::set<StringAtom> set;
48 auto foo_ret = set.insert(std::string_view("foo"));
49 auto bar_ret = set.insert(std::string_view("bar"));
50 auto zoo_ret = set.insert(std::string_view("zoo"));
51
52 StringAtom foo_key("foo");
53 EXPECT_EQ(*foo_ret.first, foo_key);
54
55 auto foo_it = set.find(foo_key);
56 EXPECT_NE(foo_it, set.end());
57 EXPECT_EQ(*foo_it, foo_key);
58
59 EXPECT_EQ(set.find(std::string_view("bar")), bar_ret.first);
60 EXPECT_EQ(set.find(std::string_view("zoo")), zoo_ret.first);
61
62 // Normal sets are always ordered according to the key value.
63 auto it = set.begin();
64 EXPECT_EQ(it, bar_ret.first);
65 ++it;
66
67 EXPECT_EQ(it, foo_ret.first);
68 ++it;
69
70 EXPECT_EQ(it, zoo_ret.first);
71 ++it;
72
73 EXPECT_EQ(it, set.end());
74 }
75
TEST(StringAtomTest,FastSet)76 TEST(StringAtomTest, FastSet) {
77 std::set<StringAtom, StringAtom::PtrCompare> set;
78
79 auto foo_ret = set.insert(std::string_view("foo"));
80 auto bar_ret = set.insert(std::string_view("bar"));
81 auto zoo_ret = set.insert(std::string_view("zoo"));
82
83 auto atom_to_ptr = [](const StringAtom& atom) -> const std::string* {
84 return &atom.str();
85 };
86
87 EXPECT_TRUE(foo_ret.second);
88 EXPECT_TRUE(bar_ret.second);
89 EXPECT_TRUE(zoo_ret.second);
90
91 const std::string* foo_ptr = atom_to_ptr(*foo_ret.first);
92 const std::string* bar_ptr = atom_to_ptr(*bar_ret.first);
93 const std::string* zoo_ptr = atom_to_ptr(*zoo_ret.first);
94
95 StringAtom foo_key("foo");
96 EXPECT_EQ(foo_ptr, atom_to_ptr(foo_key));
97
98 auto foo_it = set.find(foo_key);
99 EXPECT_NE(foo_it, set.end());
100 EXPECT_EQ(*foo_it, foo_key);
101
102 EXPECT_EQ(set.find(std::string_view("bar")), bar_ret.first);
103 EXPECT_EQ(set.find(std::string_view("zoo")), zoo_ret.first);
104
105 // Fast sets are ordered according to the key pointer.
106 // Even though a bump allocator is used to allocate AtomString
107 // strings, there is no guarantee that the global StringAtom
108 // set was not already populated by a different test previously,
109 // which means the pointers value need to be sorted before
110 // iterating over the set for comparison.
111 std::array<const std::string*, 3> ptrs = {
112 foo_ptr,
113 bar_ptr,
114 zoo_ptr,
115 };
116 std::sort(ptrs.begin(), ptrs.end());
117
118 auto it = set.begin();
119 EXPECT_EQ(atom_to_ptr(*it), ptrs[0]);
120 ++it;
121
122 EXPECT_EQ(atom_to_ptr(*it), ptrs[1]);
123 ++it;
124
125 EXPECT_EQ(atom_to_ptr(*it), ptrs[2]);
126 ++it;
127
128 EXPECT_EQ(it, set.end());
129 }
130
TEST(StringAtom,AllocMoreThanASingleSlabOfKeys)131 TEST(StringAtom, AllocMoreThanASingleSlabOfKeys) {
132 // Verify that allocating more than 128 string keys works properly.
133 const size_t kMaxCount = 16384;
134 std::vector<StringAtom> keys;
135
136 // Small lambda to create a string for the n-th key.
137 auto string_for = [](size_t index) -> std::string {
138 return std::to_string(index) + "_key";
139 };
140
141 for (size_t nn = 0; nn < kMaxCount; ++nn) {
142 keys.push_back(StringAtom(string_for(nn)));
143 }
144
145 for (size_t nn = 0; nn < kMaxCount; ++nn) {
146 ASSERT_EQ(keys[nn].str(), string_for(nn));
147 }
148 }
149