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/v8.h"
31 : #include "test/cctest/cctest.h"
32 :
33 : #include "src/base/hashmap.h"
34 :
35 : namespace v8 {
36 : namespace internal {
37 : namespace test_hashmap {
38 :
39 : typedef uint32_t (*IntKeyHash)(uint32_t key);
40 :
41 : class IntSet {
42 : public:
43 12 : explicit IntSet(IntKeyHash hash) : hash_(hash) {}
44 :
45 960 : void Insert(int x) {
46 960 : CHECK_NE(0, x); // 0 corresponds to (void*)nullptr - illegal key value
47 : v8::base::HashMap::Entry* p =
48 1920 : map_.LookupOrInsert(reinterpret_cast<void*>(x), hash_(x));
49 960 : CHECK_NOT_NULL(p); // insert is set!
50 960 : CHECK_EQ(reinterpret_cast<void*>(x), p->key);
51 : // we don't care about p->value
52 960 : }
53 :
54 924 : void Remove(int x) {
55 924 : CHECK_NE(0, x); // 0 corresponds to (void*)nullptr - illegal key value
56 924 : map_.Remove(reinterpret_cast<void*>(x), hash_(x));
57 924 : }
58 :
59 77820 : bool Present(int x) {
60 : v8::base::HashMap::Entry* p =
61 77820 : map_.Lookup(reinterpret_cast<void*>(x), hash_(x));
62 77820 : if (p != nullptr) {
63 38922 : CHECK_EQ(reinterpret_cast<void*>(x), p->key);
64 : }
65 77820 : return p != nullptr;
66 : }
67 :
68 : void Clear() {
69 : map_.Clear();
70 : }
71 :
72 1920 : uint32_t occupancy() const {
73 : uint32_t count = 0;
74 82704 : for (v8::base::HashMap::Entry* p = map_.Start(); p != nullptr;
75 : p = map_.Next(p)) {
76 76944 : count++;
77 : }
78 3840 : CHECK_EQ(map_.occupancy(), static_cast<double>(count));
79 1920 : return count;
80 : }
81 :
82 : private:
83 : IntKeyHash hash_;
84 : v8::base::HashMap map_;
85 : };
86 :
87 :
88 63102 : static uint32_t Hash(uint32_t key) { return 23; }
89 16602 : static uint32_t CollisionHash(uint32_t key) { return key & 0x3; }
90 :
91 :
92 12 : void TestSet(IntKeyHash hash, int size) {
93 : IntSet set(hash);
94 12 : CHECK_EQ(0u, set.occupancy());
95 :
96 12 : set.Insert(1);
97 12 : set.Insert(2);
98 12 : set.Insert(3);
99 12 : CHECK_EQ(3u, set.occupancy());
100 :
101 12 : set.Insert(2);
102 12 : set.Insert(3);
103 12 : CHECK_EQ(3u, set.occupancy());
104 :
105 12 : CHECK(set.Present(1));
106 12 : CHECK(set.Present(2));
107 12 : CHECK(set.Present(3));
108 12 : CHECK(!set.Present(4));
109 12 : CHECK_EQ(3u, set.occupancy());
110 :
111 12 : set.Remove(1);
112 12 : CHECK(!set.Present(1));
113 12 : CHECK(set.Present(2));
114 12 : CHECK(set.Present(3));
115 12 : CHECK_EQ(2u, set.occupancy());
116 :
117 12 : set.Remove(3);
118 12 : CHECK(!set.Present(1));
119 12 : CHECK(set.Present(2));
120 12 : CHECK(!set.Present(3));
121 12 : CHECK_EQ(1u, set.occupancy());
122 :
123 : set.Clear();
124 12 : CHECK_EQ(0u, set.occupancy());
125 :
126 : // Insert a long series of values.
127 : const int start = 453;
128 : const int factor = 13;
129 : const int offset = 7;
130 12 : const uint32_t n = size;
131 :
132 : int x = start;
133 912 : for (uint32_t i = 0; i < n; i++) {
134 1800 : CHECK_EQ(i, static_cast<double>(set.occupancy()));
135 900 : set.Insert(x);
136 900 : x = x * factor + offset;
137 : }
138 24 : CHECK_EQ(n, static_cast<double>(set.occupancy()));
139 :
140 : // Verify the same sequence of values.
141 : x = start;
142 900 : for (uint32_t i = 0; i < n; i++) {
143 900 : CHECK(set.Present(x));
144 900 : x = x * factor + offset;
145 : }
146 12 : CHECK_EQ(n, static_cast<double>(set.occupancy()));
147 :
148 : // Remove all these values.
149 : x = start;
150 900 : for (uint32_t i = 0; i < n; i++) {
151 1800 : CHECK_EQ(n - i, static_cast<double>(set.occupancy()));
152 900 : CHECK(set.Present(x));
153 900 : set.Remove(x);
154 900 : CHECK(!set.Present(x));
155 900 : x = x * factor + offset;
156 :
157 : // Verify the the expected values are still there.
158 : int y = start;
159 75900 : for (uint32_t j = 0; j < n; j++) {
160 75000 : if (j <= i) {
161 37950 : CHECK(!set.Present(y));
162 : } else {
163 37050 : CHECK(set.Present(y));
164 : }
165 75000 : y = y * factor + offset;
166 : }
167 : }
168 12 : CHECK_EQ(0u, set.occupancy());
169 12 : }
170 :
171 :
172 23724 : TEST(HashSet) {
173 6 : TestSet(Hash, 100);
174 6 : TestSet(CollisionHash, 50);
175 6 : }
176 :
177 : } // namespace test_hashmap
178 : } // namespace internal
179 71154 : } // namespace v8
|
