1 /*
2 * Copyright (c) 2015, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
24
25 #include "precompiled.hpp"
26 #include "memory/allocation.hpp"
27 #include "memory/resourceArea.hpp"
28 #include "utilities/debug.hpp"
29 #include "utilities/resourceHash.hpp"
30
31 #ifndef PRODUCT
32
33 /////////////// Unit tests ///////////////
34
35 class TestResourceHashtable : public AllStatic {
36 typedef void* K;
37 typedef int V;
38
39 static unsigned identity_hash(const K& k) {
40 return (unsigned)(uintptr_t)k;
41 }
42
43 static unsigned bad_hash(const K& k) {
44 return 1;
45 }
46
47 class EqualityTestIter {
48 public:
49 bool do_entry(K const& k, V const& v) {
50 assert((uintptr_t)k == (uintptr_t)v, "");
51 return true; // continue iteration
52 }
53 };
54
55 template<
56 unsigned (*HASH) (K const&) = primitive_hash<K>,
57 bool (*EQUALS)(K const&, K const&) = primitive_equals<K>,
58 unsigned SIZE = 256,
59 ResourceObj::allocation_type ALLOC_TYPE = ResourceObj::RESOURCE_AREA,
60 MEMFLAGS MEM_TYPE = mtInternal
61 >
62 class Runner : public AllStatic {
63 static void* as_K(uintptr_t val) { return (void*)val; }
64
65 public:
66 static void test_small() {
67 EqualityTestIter et;
68 ResourceHashtable<K, V, HASH, EQUALS, SIZE, ALLOC_TYPE, MEM_TYPE> rh;
69
70 assert(!rh.contains(as_K(0x1)), "");
71
72 assert(rh.put(as_K(0x1), 0x1), "");
73 assert(rh.contains(as_K(0x1)), "");
74
75 assert(!rh.put(as_K(0x1), 0x1), "");
76
77 assert(rh.put(as_K(0x2), 0x2), "");
78 assert(rh.put(as_K(0x3), 0x3), "");
79 assert(rh.put(as_K(0x4), 0x4), "");
80 assert(rh.put(as_K(0x5), 0x5), "");
81
82 assert(!rh.remove(as_K(0x0)), "");
83 rh.iterate(&et);
84
85 assert(rh.remove(as_K(0x1)), "");
86 rh.iterate(&et);
87
88 }
89
90 // We use keys with the low bits cleared since the default hash will do some shifting
91 static void test_small_shifted() {
92 EqualityTestIter et;
93 ResourceHashtable<K, V, HASH, EQUALS, SIZE, ALLOC_TYPE, MEM_TYPE> rh;
94
95 assert(!rh.contains(as_K(0x10)), "");
96
97 assert(rh.put(as_K(0x10), 0x10), "");
98 assert(rh.contains(as_K(0x10)), "");
99
100 assert(!rh.put(as_K(0x10), 0x10), "");
101
102 assert(rh.put(as_K(0x20), 0x20), "");
103 assert(rh.put(as_K(0x30), 0x30), "");
104 assert(rh.put(as_K(0x40), 0x40), "");
105 assert(rh.put(as_K(0x50), 0x50), "");
106
107 assert(!rh.remove(as_K(0x00)), "");
108
109 assert(rh.remove(as_K(0x10)), "");
110
111 rh.iterate(&et);
112 }
113
114 static void test(unsigned num_elements = SIZE) {
115 EqualityTestIter et;
116 ResourceHashtable<K, V, HASH, EQUALS, SIZE, ALLOC_TYPE, MEM_TYPE> rh;
117
118 for (uintptr_t i = 0; i < num_elements; ++i) {
119 assert(rh.put(as_K(i), i), "");
120 }
121
122 rh.iterate(&et);
123
124 for (uintptr_t i = num_elements; i > 0; --i) {
125 uintptr_t index = i - 1;
126 assert(rh.remove(as_K(index)), "");
127 }
128 rh.iterate(&et);
129 for (uintptr_t i = num_elements; i > 0; --i) {
130 uintptr_t index = i - 1;
131 assert(!rh.remove(as_K(index)), "");
132 }
133 rh.iterate(&et);
134 }
135 };
136
137 public:
138 static void run_tests() {
139 {
140 ResourceMark rm;
141 Runner<>::test_small();
142 Runner<>::test_small_shifted();
143 Runner<>::test();
144 }
145
146 {
147 ResourceMark rm;
148 Runner<identity_hash>::test_small();
149 Runner<identity_hash>::test_small_shifted();
150 Runner<identity_hash>::test();
151 }
152
153 {
154 ResourceMark rm;
155 Runner<bad_hash>::test_small();
156 Runner<bad_hash>::test_small_shifted();
157 Runner<bad_hash>::test();
158 }
159
160
161 assert(Thread::current()->resource_area()->nesting() == 0, "this code depends on not having an active ResourceMark");
162 // The following test calls will cause an assert if resource allocations occur since we don't have an active mark
163 Runner<primitive_hash<K>, primitive_equals<K>, 512, ResourceObj::C_HEAP>::test_small();
164 Runner<primitive_hash<K>, primitive_equals<K>, 512, ResourceObj::C_HEAP>::test_small_shifted();
165 Runner<primitive_hash<K>, primitive_equals<K>, 512, ResourceObj::C_HEAP>::test();
166
167 Runner<bad_hash, primitive_equals<K>, 512, ResourceObj::C_HEAP>::test_small();
168 Runner<bad_hash, primitive_equals<K>, 512, ResourceObj::C_HEAP>::test_small_shifted();
169 Runner<bad_hash, primitive_equals<K>, 512, ResourceObj::C_HEAP>::test();
170
171 Runner<identity_hash, primitive_equals<K>, 1, ResourceObj::C_HEAP>::test_small();
172 Runner<identity_hash, primitive_equals<K>, 1, ResourceObj::C_HEAP>::test_small_shifted();
173 Runner<identity_hash, primitive_equals<K>, 1, ResourceObj::C_HEAP>::test(512);
174 }
175 };
176
177 void TestResourcehash_test() {
178 TestResourceHashtable::run_tests();
179 }
180
181 #endif // not PRODUCT
182
|
1 /*
2 * Copyright (c) 2015, 2016, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23
24 #include "precompiled.hpp"
25 #include "memory/allocation.hpp"
26 #include "memory/resourceArea.hpp"
27 #include "unittest.hpp"
28 #include "utilities/debug.hpp"
29 #include "utilities/resourceHash.hpp"
30
31 class CommonResourceHashtableTest : public ::testing::Test {
32 protected:
33 typedef void* K;
34 typedef int V;
35 const static MEMFLAGS MEM_TYPE = mtInternal;
36
37 static unsigned identity_hash(const K& k) {
38 return (unsigned) (uintptr_t) k;
39 }
40
41 static unsigned bad_hash(const K& k) {
42 return 1;
43 }
44
45 static void* as_K(uintptr_t val) {
46 return (void*) val;
47 }
48
49 class EqualityTestIter {
50 public:
51
52 bool do_entry(K const& k, V const& v) {
53 if ((uintptr_t) k != (uintptr_t) v) {
54 EXPECT_EQ((uintptr_t) k, (uintptr_t) v);
55 return false;
56 } else {
57 return true; // continue iteration
58 }
59 }
60 };
61 };
62
63 class SmallResourceHashtableTest : public CommonResourceHashtableTest {
64 protected:
65
66 template<
67 unsigned (*HASH) (K const&) = primitive_hash<K>,
68 bool (*EQUALS)(K const&, K const&) = primitive_equals<K>,
69 unsigned SIZE = 256,
70 ResourceObj::allocation_type ALLOC_TYPE = ResourceObj::RESOURCE_AREA
71 >
72 class Runner : public AllStatic {
73 public:
74
75 static void test(V step) {
76 EqualityTestIter et;
77 ResourceHashtable<K, V, HASH, EQUALS, SIZE, ALLOC_TYPE, MEM_TYPE> rh;
78
79 ASSERT_FALSE(rh.contains(as_K(step)));
80
81 ASSERT_TRUE(rh.put(as_K(step), step));
82 ASSERT_TRUE(rh.contains(as_K(step)));
83
84 ASSERT_FALSE(rh.put(as_K(step), step));
85
86 ASSERT_TRUE(rh.put(as_K(2 * step), 2 * step));
87 ASSERT_TRUE(rh.put(as_K(3 * step), 3 * step));
88 ASSERT_TRUE(rh.put(as_K(4 * step), 4 * step));
89 ASSERT_TRUE(rh.put(as_K(5 * step), 5 * step));
90
91 ASSERT_FALSE(rh.remove(as_K(0x0)));
92
93 rh.iterate(&et);
94 if (::testing::Test::HasFailure()) {
95 return;
96 }
97
98 ASSERT_TRUE(rh.remove(as_K(step)));
99 rh.iterate(&et);
100 }
101 };
102 };
103
104 TEST_F(SmallResourceHashtableTest, default) {
105 ResourceMark rm;
106 Runner<>::test(0x1);
107 }
108
109 TEST_F(SmallResourceHashtableTest, default_shifted) {
110 ResourceMark rm;
111 Runner<>::test(0x10);
112 }
113
114 TEST_F(SmallResourceHashtableTest, bad_hash) {
115 ResourceMark rm;
116 Runner<bad_hash>::test(0x1);
117 }
118
119 TEST_F(SmallResourceHashtableTest, bad_hash_shifted) {
120 ResourceMark rm;
121 Runner<bad_hash>::test(0x10);
122 }
123
124 TEST_F(SmallResourceHashtableTest, identity_hash) {
125 ResourceMark rm;
126 Runner<identity_hash>::test(0x1);
127 }
128
129 TEST_F(SmallResourceHashtableTest, identity_hash_shifted) {
130 ResourceMark rm;
131 Runner<identity_hash>::test(0x10);
132 }
133
134 TEST_F(SmallResourceHashtableTest, primitive_hash_no_rm) {
135 Runner<primitive_hash<K>, primitive_equals<K>, 512, ResourceObj::C_HEAP>::test(0x1);
136 }
137
138 TEST_F(SmallResourceHashtableTest, primitive_hash_no_rm_shifted) {
139 Runner<primitive_hash<K>, primitive_equals<K>, 512, ResourceObj::C_HEAP>::test(0x10);
140 }
141
142 TEST_F(SmallResourceHashtableTest, bad_hash_no_rm) {
143 Runner<bad_hash, primitive_equals<K>, 512, ResourceObj::C_HEAP>::test(0x1);
144 }
145
146 TEST_F(SmallResourceHashtableTest, bad_hash_no_rm_shifted) {
147 Runner<bad_hash, primitive_equals<K>, 512, ResourceObj::C_HEAP>::test(0x10);
148 }
149
150 TEST_F(SmallResourceHashtableTest, identity_hash_no_rm) {
151 Runner<identity_hash, primitive_equals<K>, 1, ResourceObj::C_HEAP>::test(0x1);
152 }
153
154 TEST_F(SmallResourceHashtableTest, identity_hash_no_rm_shifted) {
155 Runner<identity_hash, primitive_equals<K>, 1, ResourceObj::C_HEAP>::test(0x10);
156 }
157
158 class GenericResourceHashtableTest : public CommonResourceHashtableTest {
159 protected:
160
161 template<
162 unsigned (*HASH) (K const&) = primitive_hash<K>,
163 bool (*EQUALS)(K const&, K const&) = primitive_equals<K>,
164 unsigned SIZE = 256,
165 ResourceObj::allocation_type ALLOC_TYPE = ResourceObj::RESOURCE_AREA
166 >
167 class Runner : public AllStatic {
168 public:
169
170 static void test(unsigned num_elements = SIZE) {
171 EqualityTestIter et;
172 ResourceHashtable<K, V, HASH, EQUALS, SIZE, ALLOC_TYPE, MEM_TYPE> rh;
173
174 for (uintptr_t i = 0; i < num_elements; ++i) {
175 ASSERT_TRUE(rh.put(as_K(i), i));
176 }
177
178 rh.iterate(&et);
179 if (::testing::Test::HasFailure()) {
180 return;
181 }
182
183 for (uintptr_t i = num_elements; i > 0; --i) {
184 uintptr_t index = i - 1;
185 ASSERT_TRUE((rh.remove(as_K(index))));
186 }
187
188 rh.iterate(&et);
189 if (::testing::Test::HasFailure()) {
190 return;
191 }
192 for (uintptr_t i = num_elements; i > 0; --i) {
193 uintptr_t index = i - 1;
194 ASSERT_FALSE(rh.remove(as_K(index)));
195 }
196 rh.iterate(&et);
197 }
198 };
199 };
200
201 TEST_F(GenericResourceHashtableTest, default) {
202 ResourceMark rm;
203 Runner<>::test();
204 }
205
206 TEST_F(GenericResourceHashtableTest, bad_hash) {
207 ResourceMark rm;
208 Runner<bad_hash>::test();
209 }
210
211 TEST_F(GenericResourceHashtableTest, identity_hash) {
212 ResourceMark rm;
213 Runner<identity_hash>::test();
214 }
215
216 TEST_F(GenericResourceHashtableTest, primitive_hash_no_rm) {
217 Runner<primitive_hash<K>, primitive_equals<K>, 512, ResourceObj::C_HEAP>::test();
218 }
219
220 TEST_F(GenericResourceHashtableTest, bad_hash_no_rm) {
221 Runner<bad_hash, primitive_equals<K>, 512, ResourceObj::C_HEAP>::test();
222 }
223
224 TEST_F(GenericResourceHashtableTest, identity_hash_no_rm) {
225 Runner<identity_hash, primitive_equals<K>, 1, ResourceObj::C_HEAP>::test(512);
226 }
|