Line data Source code
1 : // Copyright 2008 the V8 project authors. All rights reserved.
2 : // Redistribution and use in source and binary forms, with or without
3 : // modification, are permitted provided that the following conditions are
4 : // met:
5 : //
6 : // * Redistributions of source code must retain the above copyright
7 : // notice, this list of conditions and the following disclaimer.
8 : // * Redistributions in binary form must reproduce the above
9 : // copyright notice, this list of conditions and the following
10 : // disclaimer in the documentation and/or other materials provided
11 : // with the distribution.
12 : // * Neither the name of Google Inc. nor the names of its
13 : // contributors may be used to endorse or promote products derived
14 : // from this software without specific prior written permission.
15 : //
16 : // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 : // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 : // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19 : // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20 : // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 : // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22 : // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 : // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 : // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 : // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26 : // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 :
28 : #include <stdlib.h>
29 :
30 : #include "src/base/overflowing-math.h"
31 : #include "src/v8.h"
32 : #include "test/cctest/cctest.h"
33 :
34 : #include "src/base/hashmap.h"
35 :
36 : namespace v8 {
37 : namespace internal {
38 : namespace test_hashmap {
39 :
40 : typedef uint32_t (*IntKeyHash)(uint32_t key);
41 :
42 10 : class IntSet {
43 : public:
44 10 : explicit IntSet(IntKeyHash hash) : hash_(hash) {}
45 :
46 800 : void Insert(int x) {
47 800 : CHECK_NE(0, x); // 0 corresponds to (void*)nullptr - illegal key value
48 : v8::base::HashMap::Entry* p =
49 1600 : map_.LookupOrInsert(reinterpret_cast<void*>(x), hash_(x));
50 800 : CHECK_NOT_NULL(p); // insert is set!
51 800 : CHECK_EQ(reinterpret_cast<void*>(x), p->key);
52 : // we don't care about p->value
53 800 : }
54 :
55 770 : void Remove(int x) {
56 770 : CHECK_NE(0, x); // 0 corresponds to (void*)nullptr - illegal key value
57 770 : map_.Remove(reinterpret_cast<void*>(x), hash_(x));
58 770 : }
59 :
60 64850 : bool Present(int x) {
61 : v8::base::HashMap::Entry* p =
62 64850 : map_.Lookup(reinterpret_cast<void*>(x), hash_(x));
63 64850 : if (p != nullptr) {
64 32435 : CHECK_EQ(reinterpret_cast<void*>(x), p->key);
65 : }
66 64850 : return p != nullptr;
67 : }
68 :
69 : void Clear() {
70 : map_.Clear();
71 : }
72 :
73 1600 : uint32_t occupancy() const {
74 : uint32_t count = 0;
75 129840 : for (v8::base::HashMap::Entry* p = map_.Start(); p != nullptr;
76 : p = map_.Next(p)) {
77 64120 : count++;
78 : }
79 3200 : CHECK_EQ(map_.occupancy(), static_cast<double>(count));
80 1600 : return count;
81 : }
82 :
83 : private:
84 : IntKeyHash hash_;
85 : v8::base::HashMap map_;
86 : };
87 :
88 :
89 52585 : static uint32_t Hash(uint32_t key) { return 23; }
90 13835 : static uint32_t CollisionHash(uint32_t key) { return key & 0x3; }
91 :
92 :
93 10 : void TestSet(IntKeyHash hash, int size) {
94 : IntSet set(hash);
95 10 : CHECK_EQ(0u, set.occupancy());
96 :
97 10 : set.Insert(1);
98 10 : set.Insert(2);
99 10 : set.Insert(3);
100 10 : CHECK_EQ(3u, set.occupancy());
101 :
102 10 : set.Insert(2);
103 10 : set.Insert(3);
104 10 : CHECK_EQ(3u, set.occupancy());
105 :
106 10 : CHECK(set.Present(1));
107 10 : CHECK(set.Present(2));
108 10 : CHECK(set.Present(3));
109 10 : CHECK(!set.Present(4));
110 10 : CHECK_EQ(3u, set.occupancy());
111 :
112 10 : set.Remove(1);
113 10 : CHECK(!set.Present(1));
114 10 : CHECK(set.Present(2));
115 10 : CHECK(set.Present(3));
116 10 : CHECK_EQ(2u, set.occupancy());
117 :
118 10 : set.Remove(3);
119 10 : CHECK(!set.Present(1));
120 10 : CHECK(set.Present(2));
121 10 : CHECK(!set.Present(3));
122 10 : CHECK_EQ(1u, set.occupancy());
123 :
124 : set.Clear();
125 10 : CHECK_EQ(0u, set.occupancy());
126 :
127 : // Insert a long series of values.
128 : const int start = 453;
129 : const int factor = 13;
130 : const int offset = 7;
131 10 : const uint32_t n = size;
132 :
133 : int x = start;
134 1510 : for (uint32_t i = 0; i < n; i++) {
135 1500 : CHECK_EQ(i, static_cast<double>(set.occupancy()));
136 750 : set.Insert(x);
137 : x = base::AddWithWraparound(base::MulWithWraparound(x, factor), offset);
138 : }
139 20 : CHECK_EQ(n, static_cast<double>(set.occupancy()));
140 :
141 : // Verify the same sequence of values.
142 : x = start;
143 1510 : for (uint32_t i = 0; i < n; i++) {
144 750 : CHECK(set.Present(x));
145 : x = base::AddWithWraparound(base::MulWithWraparound(x, factor), offset);
146 : }
147 10 : CHECK_EQ(n, static_cast<double>(set.occupancy()));
148 :
149 : // Remove all these values.
150 : x = start;
151 1510 : for (uint32_t i = 0; i < n; i++) {
152 1500 : CHECK_EQ(n - i, static_cast<double>(set.occupancy()));
153 750 : CHECK(set.Present(x));
154 750 : set.Remove(x);
155 750 : CHECK(!set.Present(x));
156 : x = base::AddWithWraparound(base::MulWithWraparound(x, factor), offset);
157 :
158 : // Verify the the expected values are still there.
159 : int y = start;
160 125750 : for (uint32_t j = 0; j < n; j++) {
161 62500 : if (j <= i) {
162 31625 : CHECK(!set.Present(y));
163 : } else {
164 30875 : CHECK(set.Present(y));
165 : }
166 : y = base::AddWithWraparound(base::MulWithWraparound(y, factor), offset);
167 : }
168 : }
169 10 : CHECK_EQ(0u, set.occupancy());
170 10 : }
171 :
172 :
173 26644 : TEST(HashSet) {
174 5 : TestSet(Hash, 100);
175 5 : TestSet(CollisionHash, 50);
176 5 : }
177 :
178 : } // namespace test_hashmap
179 : } // namespace internal
180 79917 : } // namespace v8
|
