diff options
author | Sergio Giro | 2015-10-01 05:19:32 -0500 |
---|---|---|
committer | Colin Cross | 2015-10-01 15:18:13 -0500 |
commit | a5f71e075a194eab9ac8bbc8f1c4e500582e7d0b (patch) | |
tree | dbedf7bb120cb59c58d7b35c3dadbf53435e080f /libutils/tests | |
parent | 9db5e1a247fa3d7ed6ab96b069163348f6c92e2c (diff) | |
download | platform-system-core-a5f71e075a194eab9ac8bbc8f1c4e500582e7d0b.tar.gz platform-system-core-a5f71e075a194eab9ac8bbc8f1c4e500582e7d0b.tar.xz platform-system-core-a5f71e075a194eab9ac8bbc8f1c4e500582e7d0b.zip |
system/core: remove BasicHashtable
Towards deprecation of SharedBuffer
Change-Id: Id6d1c8637583df38b6f28398b6804d9c1e96472a
(cherry picked from commit f84a4906fa950a238e8775a8c931e07632f6023d)
Diffstat (limited to 'libutils/tests')
-rw-r--r-- | libutils/tests/Android.mk | 1 | ||||
-rw-r--r-- | libutils/tests/BasicHashtable_test.cpp | 582 |
2 files changed, 0 insertions, 583 deletions
diff --git a/libutils/tests/Android.mk b/libutils/tests/Android.mk index d4a45fd72..47415ab05 100644 --- a/libutils/tests/Android.mk +++ b/libutils/tests/Android.mk | |||
@@ -22,7 +22,6 @@ include $(CLEAR_VARS) | |||
22 | LOCAL_MODULE := libutils_tests | 22 | LOCAL_MODULE := libutils_tests |
23 | 23 | ||
24 | LOCAL_SRC_FILES := \ | 24 | LOCAL_SRC_FILES := \ |
25 | BasicHashtable_test.cpp \ | ||
26 | BlobCache_test.cpp \ | 25 | BlobCache_test.cpp \ |
27 | BitSet_test.cpp \ | 26 | BitSet_test.cpp \ |
28 | Looper_test.cpp \ | 27 | Looper_test.cpp \ |
diff --git a/libutils/tests/BasicHashtable_test.cpp b/libutils/tests/BasicHashtable_test.cpp deleted file mode 100644 index 4b3a71728..000000000 --- a/libutils/tests/BasicHashtable_test.cpp +++ /dev/null | |||
@@ -1,582 +0,0 @@ | |||
1 | /* | ||
2 | * Copyright (C) 2011 The Android Open Source Project | ||
3 | * | ||
4 | * Licensed under the Apache License, Version 2.0 (the "License"); | ||
5 | * you may not use this file except in compliance with the License. | ||
6 | * You may obtain a copy of the License at | ||
7 | * | ||
8 | * http://www.apache.org/licenses/LICENSE-2.0 | ||
9 | * | ||
10 | * Unless required by applicable law or agreed to in writing, software | ||
11 | * distributed under the License is distributed on an "AS IS" BASIS, | ||
12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | ||
13 | * See the License for the specific language governing permissions and | ||
14 | * limitations under the License. | ||
15 | */ | ||
16 | |||
17 | #define LOG_TAG "BasicHashtable_test" | ||
18 | |||
19 | #include <utils/BasicHashtable.h> | ||
20 | #include <cutils/log.h> | ||
21 | #include <gtest/gtest.h> | ||
22 | #include <unistd.h> | ||
23 | |||
24 | namespace { | ||
25 | |||
26 | typedef int SimpleKey; | ||
27 | typedef int SimpleValue; | ||
28 | typedef android::key_value_pair_t<SimpleKey, SimpleValue> SimpleEntry; | ||
29 | typedef android::BasicHashtable<SimpleKey, SimpleEntry> SimpleHashtable; | ||
30 | |||
31 | struct ComplexKey { | ||
32 | int k; | ||
33 | |||
34 | explicit ComplexKey(int k) : k(k) { | ||
35 | instanceCount += 1; | ||
36 | } | ||
37 | |||
38 | ComplexKey(const ComplexKey& other) : k(other.k) { | ||
39 | instanceCount += 1; | ||
40 | } | ||
41 | |||
42 | ~ComplexKey() { | ||
43 | instanceCount -= 1; | ||
44 | } | ||
45 | |||
46 | bool operator ==(const ComplexKey& other) const { | ||
47 | return k == other.k; | ||
48 | } | ||
49 | |||
50 | bool operator !=(const ComplexKey& other) const { | ||
51 | return k != other.k; | ||
52 | } | ||
53 | |||
54 | static ssize_t instanceCount; | ||
55 | }; | ||
56 | |||
57 | ssize_t ComplexKey::instanceCount = 0; | ||
58 | |||
59 | struct ComplexValue { | ||
60 | int v; | ||
61 | |||
62 | explicit ComplexValue(int v) : v(v) { | ||
63 | instanceCount += 1; | ||
64 | } | ||
65 | |||
66 | ComplexValue(const ComplexValue& other) : v(other.v) { | ||
67 | instanceCount += 1; | ||
68 | } | ||
69 | |||
70 | ~ComplexValue() { | ||
71 | instanceCount -= 1; | ||
72 | } | ||
73 | |||
74 | static ssize_t instanceCount; | ||
75 | }; | ||
76 | |||
77 | ssize_t ComplexValue::instanceCount = 0; | ||
78 | |||
79 | } // namespace | ||
80 | |||
81 | |||
82 | namespace android { | ||
83 | |||
84 | typedef key_value_pair_t<ComplexKey, ComplexValue> ComplexEntry; | ||
85 | typedef BasicHashtable<ComplexKey, ComplexEntry> ComplexHashtable; | ||
86 | |||
87 | template<> inline hash_t hash_type(const ComplexKey& value) { | ||
88 | return hash_type(value.k); | ||
89 | } | ||
90 | |||
91 | class BasicHashtableTest : public testing::Test { | ||
92 | protected: | ||
93 | virtual void SetUp() { | ||
94 | ComplexKey::instanceCount = 0; | ||
95 | ComplexValue::instanceCount = 0; | ||
96 | } | ||
97 | |||
98 | virtual void TearDown() { | ||
99 | ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0)); | ||
100 | } | ||
101 | |||
102 | void assertInstanceCount(ssize_t keys, ssize_t values) { | ||
103 | if (keys != ComplexKey::instanceCount || values != ComplexValue::instanceCount) { | ||
104 | FAIL() << "Expected " << keys << " keys and " << values << " values " | ||
105 | "but there were actually " << ComplexKey::instanceCount << " keys and " | ||
106 | << ComplexValue::instanceCount << " values"; | ||
107 | } | ||
108 | } | ||
109 | |||
110 | public: | ||
111 | template <typename TKey, typename TEntry> | ||
112 | static void cookieAt(const BasicHashtable<TKey, TEntry>& h, size_t index, | ||
113 | bool* collision, bool* present, hash_t* hash) { | ||
114 | uint32_t cookie = h.cookieAt(index); | ||
115 | *collision = cookie & BasicHashtable<TKey, TEntry>::Bucket::COLLISION; | ||
116 | *present = cookie & BasicHashtable<TKey, TEntry>::Bucket::PRESENT; | ||
117 | *hash = cookie & BasicHashtable<TKey, TEntry>::Bucket::HASH_MASK; | ||
118 | } | ||
119 | |||
120 | template <typename TKey, typename TEntry> | ||
121 | static const void* getBuckets(const BasicHashtable<TKey, TEntry>& h) { | ||
122 | return h.mBuckets; | ||
123 | } | ||
124 | }; | ||
125 | |||
126 | template <typename TKey, typename TValue> | ||
127 | static size_t add(BasicHashtable<TKey, key_value_pair_t<TKey, TValue> >& h, | ||
128 | const TKey& key, const TValue& value) { | ||
129 | return h.add(hash_type(key), key_value_pair_t<TKey, TValue>(key, value)); | ||
130 | } | ||
131 | |||
132 | template <typename TKey, typename TValue> | ||
133 | static ssize_t find(BasicHashtable<TKey, key_value_pair_t<TKey, TValue> >& h, | ||
134 | ssize_t index, const TKey& key) { | ||
135 | return h.find(index, hash_type(key), key); | ||
136 | } | ||
137 | |||
138 | template <typename TKey, typename TValue> | ||
139 | static bool remove(BasicHashtable<TKey, key_value_pair_t<TKey, TValue> >& h, | ||
140 | const TKey& key) { | ||
141 | ssize_t index = find(h, -1, key); | ||
142 | if (index >= 0) { | ||
143 | h.removeAt(index); | ||
144 | return true; | ||
145 | } | ||
146 | return false; | ||
147 | } | ||
148 | |||
149 | template <typename TEntry> | ||
150 | static void getKeyValue(const TEntry& entry, int* key, int* value); | ||
151 | |||
152 | template <> void getKeyValue(const SimpleEntry& entry, int* key, int* value) { | ||
153 | *key = entry.key; | ||
154 | *value = entry.value; | ||
155 | } | ||
156 | |||
157 | template <> void getKeyValue(const ComplexEntry& entry, int* key, int* value) { | ||
158 | *key = entry.key.k; | ||
159 | *value = entry.value.v; | ||
160 | } | ||
161 | |||
162 | template <typename TKey, typename TValue> | ||
163 | static void dump(BasicHashtable<TKey, key_value_pair_t<TKey, TValue> >& h) { | ||
164 | ALOGD("hashtable %p, size=%u, capacity=%u, bucketCount=%u", | ||
165 | &h, h.size(), h.capacity(), h.bucketCount()); | ||
166 | for (size_t i = 0; i < h.bucketCount(); i++) { | ||
167 | bool collision, present; | ||
168 | hash_t hash; | ||
169 | BasicHashtableTest::cookieAt(h, i, &collision, &present, &hash); | ||
170 | if (present) { | ||
171 | int key, value; | ||
172 | getKeyValue(h.entryAt(i), &key, &value); | ||
173 | ALOGD(" [%3u] = collision=%d, present=%d, hash=0x%08x, key=%3d, value=%3d, " | ||
174 | "hash_type(key)=0x%08x", | ||
175 | i, collision, present, hash, key, value, hash_type(key)); | ||
176 | } else { | ||
177 | ALOGD(" [%3u] = collision=%d, present=%d", | ||
178 | i, collision, present); | ||
179 | } | ||
180 | } | ||
181 | } | ||
182 | |||
183 | TEST_F(BasicHashtableTest, DefaultConstructor_WithDefaultProperties) { | ||
184 | SimpleHashtable h; | ||
185 | |||
186 | EXPECT_EQ(0U, h.size()); | ||
187 | EXPECT_EQ(3U, h.capacity()); | ||
188 | EXPECT_EQ(5U, h.bucketCount()); | ||
189 | EXPECT_EQ(0.75f, h.loadFactor()); | ||
190 | } | ||
191 | |||
192 | TEST_F(BasicHashtableTest, Constructor_WithNonUnityLoadFactor) { | ||
193 | SimpleHashtable h(52, 0.8f); | ||
194 | |||
195 | EXPECT_EQ(0U, h.size()); | ||
196 | EXPECT_EQ(77U, h.capacity()); | ||
197 | EXPECT_EQ(97U, h.bucketCount()); | ||
198 | EXPECT_EQ(0.8f, h.loadFactor()); | ||
199 | } | ||
200 | |||
201 | TEST_F(BasicHashtableTest, Constructor_WithUnityLoadFactorAndExactCapacity) { | ||
202 | SimpleHashtable h(46, 1.0f); | ||
203 | |||
204 | EXPECT_EQ(0U, h.size()); | ||
205 | EXPECT_EQ(46U, h.capacity()); // must be one less than bucketCount because loadFactor == 1.0f | ||
206 | EXPECT_EQ(47U, h.bucketCount()); | ||
207 | EXPECT_EQ(1.0f, h.loadFactor()); | ||
208 | } | ||
209 | |||
210 | TEST_F(BasicHashtableTest, Constructor_WithUnityLoadFactorAndInexactCapacity) { | ||
211 | SimpleHashtable h(42, 1.0f); | ||
212 | |||
213 | EXPECT_EQ(0U, h.size()); | ||
214 | EXPECT_EQ(46U, h.capacity()); // must be one less than bucketCount because loadFactor == 1.0f | ||
215 | EXPECT_EQ(47U, h.bucketCount()); | ||
216 | EXPECT_EQ(1.0f, h.loadFactor()); | ||
217 | } | ||
218 | |||
219 | TEST_F(BasicHashtableTest, FindAddFindRemoveFind_OneEntry) { | ||
220 | SimpleHashtable h; | ||
221 | ssize_t index = find(h, -1, 8); | ||
222 | ASSERT_EQ(-1, index); | ||
223 | |||
224 | index = add(h, 8, 1); | ||
225 | ASSERT_EQ(1U, h.size()); | ||
226 | |||
227 | ASSERT_EQ(index, find(h, -1, 8)); | ||
228 | ASSERT_EQ(8, h.entryAt(index).key); | ||
229 | ASSERT_EQ(1, h.entryAt(index).value); | ||
230 | |||
231 | index = find(h, index, 8); | ||
232 | ASSERT_EQ(-1, index); | ||
233 | |||
234 | ASSERT_TRUE(remove(h, 8)); | ||
235 | ASSERT_EQ(0U, h.size()); | ||
236 | |||
237 | index = find(h, -1, 8); | ||
238 | ASSERT_EQ(-1, index); | ||
239 | } | ||
240 | |||
241 | TEST_F(BasicHashtableTest, FindAddFindRemoveFind_MultipleEntryWithUniqueKey) { | ||
242 | const size_t N = 11; | ||
243 | |||
244 | SimpleHashtable h; | ||
245 | for (size_t i = 0; i < N; i++) { | ||
246 | ssize_t index = find(h, -1, int(i)); | ||
247 | ASSERT_EQ(-1, index); | ||
248 | |||
249 | index = add(h, int(i), int(i * 10)); | ||
250 | ASSERT_EQ(i + 1, h.size()); | ||
251 | |||
252 | ASSERT_EQ(index, find(h, -1, int(i))); | ||
253 | ASSERT_EQ(int(i), h.entryAt(index).key); | ||
254 | ASSERT_EQ(int(i * 10), h.entryAt(index).value); | ||
255 | |||
256 | index = find(h, index, int(i)); | ||
257 | ASSERT_EQ(-1, index); | ||
258 | } | ||
259 | |||
260 | for (size_t i = N; --i > 0; ) { | ||
261 | ASSERT_TRUE(remove(h, int(i))) << "i = " << i; | ||
262 | ASSERT_EQ(i, h.size()); | ||
263 | |||
264 | ssize_t index = find(h, -1, int(i)); | ||
265 | ASSERT_EQ(-1, index); | ||
266 | } | ||
267 | } | ||
268 | |||
269 | TEST_F(BasicHashtableTest, FindAddFindRemoveFind_MultipleEntryWithDuplicateKey) { | ||
270 | const size_t N = 11; | ||
271 | const int K = 1; | ||
272 | |||
273 | SimpleHashtable h; | ||
274 | for (size_t i = 0; i < N; i++) { | ||
275 | ssize_t index = find(h, -1, K); | ||
276 | if (i == 0) { | ||
277 | ASSERT_EQ(-1, index); | ||
278 | } else { | ||
279 | ASSERT_NE(-1, index); | ||
280 | } | ||
281 | |||
282 | add(h, K, int(i)); | ||
283 | ASSERT_EQ(i + 1, h.size()); | ||
284 | |||
285 | index = -1; | ||
286 | int values = 0; | ||
287 | for (size_t j = 0; j <= i; j++) { | ||
288 | index = find(h, index, K); | ||
289 | ASSERT_GE(index, 0); | ||
290 | ASSERT_EQ(K, h.entryAt(index).key); | ||
291 | values |= 1 << h.entryAt(index).value; | ||
292 | } | ||
293 | ASSERT_EQ(values, (1 << (i + 1)) - 1); | ||
294 | |||
295 | index = find(h, index, K); | ||
296 | ASSERT_EQ(-1, index); | ||
297 | } | ||
298 | |||
299 | for (size_t i = N; --i > 0; ) { | ||
300 | ASSERT_TRUE(remove(h, K)) << "i = " << i; | ||
301 | ASSERT_EQ(i, h.size()); | ||
302 | |||
303 | ssize_t index = -1; | ||
304 | for (size_t j = 0; j < i; j++) { | ||
305 | index = find(h, index, K); | ||
306 | ASSERT_GE(index, 0); | ||
307 | ASSERT_EQ(K, h.entryAt(index).key); | ||
308 | } | ||
309 | |||
310 | index = find(h, index, K); | ||
311 | ASSERT_EQ(-1, index); | ||
312 | } | ||
313 | } | ||
314 | |||
315 | TEST_F(BasicHashtableTest, Clear_WhenAlreadyEmpty_DoesNothing) { | ||
316 | SimpleHashtable h; | ||
317 | h.clear(); | ||
318 | |||
319 | EXPECT_EQ(0U, h.size()); | ||
320 | EXPECT_EQ(3U, h.capacity()); | ||
321 | EXPECT_EQ(5U, h.bucketCount()); | ||
322 | EXPECT_EQ(0.75f, h.loadFactor()); | ||
323 | } | ||
324 | |||
325 | TEST_F(BasicHashtableTest, Clear_AfterElementsAdded_RemovesThem) { | ||
326 | SimpleHashtable h; | ||
327 | add(h, 0, 0); | ||
328 | add(h, 1, 0); | ||
329 | h.clear(); | ||
330 | |||
331 | EXPECT_EQ(0U, h.size()); | ||
332 | EXPECT_EQ(3U, h.capacity()); | ||
333 | EXPECT_EQ(5U, h.bucketCount()); | ||
334 | EXPECT_EQ(0.75f, h.loadFactor()); | ||
335 | } | ||
336 | |||
337 | TEST_F(BasicHashtableTest, Clear_AfterElementsAdded_DestroysThem) { | ||
338 | ComplexHashtable h; | ||
339 | add(h, ComplexKey(0), ComplexValue(0)); | ||
340 | add(h, ComplexKey(1), ComplexValue(0)); | ||
341 | ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2)); | ||
342 | |||
343 | h.clear(); | ||
344 | ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0)); | ||
345 | |||
346 | EXPECT_EQ(0U, h.size()); | ||
347 | EXPECT_EQ(3U, h.capacity()); | ||
348 | EXPECT_EQ(5U, h.bucketCount()); | ||
349 | EXPECT_EQ(0.75f, h.loadFactor()); | ||
350 | } | ||
351 | |||
352 | TEST_F(BasicHashtableTest, Remove_AfterElementsAdded_DestroysThem) { | ||
353 | ComplexHashtable h; | ||
354 | add(h, ComplexKey(0), ComplexValue(0)); | ||
355 | add(h, ComplexKey(1), ComplexValue(0)); | ||
356 | ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2)); | ||
357 | |||
358 | ASSERT_TRUE(remove(h, ComplexKey(0))); | ||
359 | ASSERT_NO_FATAL_FAILURE(assertInstanceCount(1, 1)); | ||
360 | |||
361 | ASSERT_TRUE(remove(h, ComplexKey(1))); | ||
362 | ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0)); | ||
363 | |||
364 | EXPECT_EQ(0U, h.size()); | ||
365 | EXPECT_EQ(3U, h.capacity()); | ||
366 | EXPECT_EQ(5U, h.bucketCount()); | ||
367 | EXPECT_EQ(0.75f, h.loadFactor()); | ||
368 | } | ||
369 | |||
370 | TEST_F(BasicHashtableTest, Destructor_AfterElementsAdded_DestroysThem) { | ||
371 | { | ||
372 | ComplexHashtable h; | ||
373 | add(h, ComplexKey(0), ComplexValue(0)); | ||
374 | add(h, ComplexKey(1), ComplexValue(0)); | ||
375 | ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2)); | ||
376 | } // h is destroyed here | ||
377 | |||
378 | ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0)); | ||
379 | } | ||
380 | |||
381 | TEST_F(BasicHashtableTest, Next_WhenEmpty_ReturnsMinusOne) { | ||
382 | SimpleHashtable h; | ||
383 | |||
384 | ASSERT_EQ(-1, h.next(-1)); | ||
385 | } | ||
386 | |||
387 | TEST_F(BasicHashtableTest, Next_WhenNonEmpty_IteratesOverAllEntries) { | ||
388 | const int N = 88; | ||
389 | |||
390 | SimpleHashtable h; | ||
391 | for (int i = 0; i < N; i++) { | ||
392 | add(h, i, i * 10); | ||
393 | } | ||
394 | |||
395 | bool set[N]; | ||
396 | memset(set, 0, sizeof(bool) * N); | ||
397 | int count = 0; | ||
398 | for (ssize_t index = -1; (index = h.next(index)) != -1; ) { | ||
399 | ASSERT_GE(index, 0); | ||
400 | ASSERT_LT(size_t(index), h.bucketCount()); | ||
401 | |||
402 | const SimpleEntry& entry = h.entryAt(index); | ||
403 | ASSERT_GE(entry.key, 0); | ||
404 | ASSERT_LT(entry.key, N); | ||
405 | ASSERT_FALSE(set[entry.key]); | ||
406 | ASSERT_EQ(entry.key * 10, entry.value); | ||
407 | |||
408 | set[entry.key] = true; | ||
409 | count += 1; | ||
410 | } | ||
411 | ASSERT_EQ(N, count); | ||
412 | } | ||
413 | |||
414 | TEST_F(BasicHashtableTest, Add_RehashesOnDemand) { | ||
415 | SimpleHashtable h; | ||
416 | size_t initialCapacity = h.capacity(); | ||
417 | size_t initialBucketCount = h.bucketCount(); | ||
418 | |||
419 | for (size_t i = 0; i < initialCapacity; i++) { | ||
420 | add(h, int(i), 0); | ||
421 | } | ||
422 | |||
423 | EXPECT_EQ(initialCapacity, h.size()); | ||
424 | EXPECT_EQ(initialCapacity, h.capacity()); | ||
425 | EXPECT_EQ(initialBucketCount, h.bucketCount()); | ||
426 | |||
427 | add(h, -1, -1); | ||
428 | |||
429 | EXPECT_EQ(initialCapacity + 1, h.size()); | ||
430 | EXPECT_GT(h.capacity(), initialCapacity); | ||
431 | EXPECT_GT(h.bucketCount(), initialBucketCount); | ||
432 | EXPECT_GT(h.bucketCount(), h.capacity()); | ||
433 | } | ||
434 | |||
435 | TEST_F(BasicHashtableTest, Rehash_WhenCapacityAndBucketCountUnchanged_DoesNothing) { | ||
436 | ComplexHashtable h; | ||
437 | add(h, ComplexKey(0), ComplexValue(0)); | ||
438 | const void* oldBuckets = getBuckets(h); | ||
439 | ASSERT_NE((void*)NULL, oldBuckets); | ||
440 | ASSERT_NO_FATAL_FAILURE(assertInstanceCount(1, 1)); | ||
441 | |||
442 | h.rehash(h.capacity(), h.loadFactor()); | ||
443 | |||
444 | ASSERT_EQ(oldBuckets, getBuckets(h)); | ||
445 | ASSERT_NO_FATAL_FAILURE(assertInstanceCount(1, 1)); | ||
446 | } | ||
447 | |||
448 | TEST_F(BasicHashtableTest, Rehash_WhenEmptyAndHasNoBuckets_ButDoesNotAllocateBuckets) { | ||
449 | ComplexHashtable h; | ||
450 | ASSERT_EQ((void*)NULL, getBuckets(h)); | ||
451 | ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0)); | ||
452 | |||
453 | h.rehash(9, 1.0f); | ||
454 | |||
455 | EXPECT_EQ(0U, h.size()); | ||
456 | EXPECT_EQ(10U, h.capacity()); | ||
457 | EXPECT_EQ(11U, h.bucketCount()); | ||
458 | EXPECT_EQ(1.0f, h.loadFactor()); | ||
459 | EXPECT_EQ((void*)NULL, getBuckets(h)); | ||
460 | ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0)); | ||
461 | } | ||
462 | |||
463 | TEST_F(BasicHashtableTest, Rehash_WhenEmptyAndHasBuckets_ReleasesBucketsAndSetsCapacity) { | ||
464 | ComplexHashtable h(10); | ||
465 | add(h, ComplexKey(0), ComplexValue(0)); | ||
466 | ASSERT_TRUE(remove(h, ComplexKey(0))); | ||
467 | ASSERT_NE((void*)NULL, getBuckets(h)); | ||
468 | ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0)); | ||
469 | |||
470 | h.rehash(0, 0.75f); | ||
471 | |||
472 | EXPECT_EQ(0U, h.size()); | ||
473 | EXPECT_EQ(3U, h.capacity()); | ||
474 | EXPECT_EQ(5U, h.bucketCount()); | ||
475 | EXPECT_EQ(0.75f, h.loadFactor()); | ||
476 | EXPECT_EQ((void*)NULL, getBuckets(h)); | ||
477 | ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0)); | ||
478 | } | ||
479 | |||
480 | TEST_F(BasicHashtableTest, Rehash_WhenLessThanCurrentCapacity_ShrinksBuckets) { | ||
481 | ComplexHashtable h(10); | ||
482 | add(h, ComplexKey(0), ComplexValue(0)); | ||
483 | add(h, ComplexKey(1), ComplexValue(1)); | ||
484 | const void* oldBuckets = getBuckets(h); | ||
485 | ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2)); | ||
486 | |||
487 | h.rehash(0, 0.75f); | ||
488 | |||
489 | EXPECT_EQ(2U, h.size()); | ||
490 | EXPECT_EQ(3U, h.capacity()); | ||
491 | EXPECT_EQ(5U, h.bucketCount()); | ||
492 | EXPECT_EQ(0.75f, h.loadFactor()); | ||
493 | EXPECT_NE(oldBuckets, getBuckets(h)); | ||
494 | ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2)); | ||
495 | } | ||
496 | |||
497 | TEST_F(BasicHashtableTest, CopyOnWrite) { | ||
498 | ComplexHashtable h1; | ||
499 | add(h1, ComplexKey(0), ComplexValue(0)); | ||
500 | add(h1, ComplexKey(1), ComplexValue(1)); | ||
501 | const void* originalBuckets = getBuckets(h1); | ||
502 | ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2)); | ||
503 | ssize_t index0 = find(h1, -1, ComplexKey(0)); | ||
504 | EXPECT_GE(index0, 0); | ||
505 | |||
506 | // copy constructor acquires shared reference | ||
507 | ComplexHashtable h2(h1); | ||
508 | ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2)); | ||
509 | ASSERT_EQ(originalBuckets, getBuckets(h2)); | ||
510 | EXPECT_EQ(h1.size(), h2.size()); | ||
511 | EXPECT_EQ(h1.capacity(), h2.capacity()); | ||
512 | EXPECT_EQ(h1.bucketCount(), h2.bucketCount()); | ||
513 | EXPECT_EQ(h1.loadFactor(), h2.loadFactor()); | ||
514 | EXPECT_EQ(index0, find(h2, -1, ComplexKey(0))); | ||
515 | |||
516 | // operator= acquires shared reference | ||
517 | ComplexHashtable h3; | ||
518 | h3 = h2; | ||
519 | ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2)); | ||
520 | ASSERT_EQ(originalBuckets, getBuckets(h3)); | ||
521 | EXPECT_EQ(h1.size(), h3.size()); | ||
522 | EXPECT_EQ(h1.capacity(), h3.capacity()); | ||
523 | EXPECT_EQ(h1.bucketCount(), h3.bucketCount()); | ||
524 | EXPECT_EQ(h1.loadFactor(), h3.loadFactor()); | ||
525 | EXPECT_EQ(index0, find(h3, -1, ComplexKey(0))); | ||
526 | |||
527 | // editEntryAt copies shared contents | ||
528 | h1.editEntryAt(index0).value.v = 42; | ||
529 | ASSERT_NO_FATAL_FAILURE(assertInstanceCount(4, 4)); | ||
530 | ASSERT_NE(originalBuckets, getBuckets(h1)); | ||
531 | EXPECT_EQ(42, h1.entryAt(index0).value.v); | ||
532 | EXPECT_EQ(0, h2.entryAt(index0).value.v); | ||
533 | EXPECT_EQ(0, h3.entryAt(index0).value.v); | ||
534 | |||
535 | // clear releases reference to shared contents | ||
536 | h2.clear(); | ||
537 | ASSERT_NO_FATAL_FAILURE(assertInstanceCount(4, 4)); | ||
538 | EXPECT_EQ(0U, h2.size()); | ||
539 | ASSERT_NE(originalBuckets, getBuckets(h2)); | ||
540 | |||
541 | // operator= acquires shared reference, destroys unshared contents | ||
542 | h1 = h3; | ||
543 | ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2)); | ||
544 | ASSERT_EQ(originalBuckets, getBuckets(h1)); | ||
545 | EXPECT_EQ(h3.size(), h1.size()); | ||
546 | EXPECT_EQ(h3.capacity(), h1.capacity()); | ||
547 | EXPECT_EQ(h3.bucketCount(), h1.bucketCount()); | ||
548 | EXPECT_EQ(h3.loadFactor(), h1.loadFactor()); | ||
549 | EXPECT_EQ(index0, find(h1, -1, ComplexKey(0))); | ||
550 | |||
551 | // add copies shared contents | ||
552 | add(h1, ComplexKey(2), ComplexValue(2)); | ||
553 | ASSERT_NO_FATAL_FAILURE(assertInstanceCount(5, 5)); | ||
554 | ASSERT_NE(originalBuckets, getBuckets(h1)); | ||
555 | EXPECT_EQ(3U, h1.size()); | ||
556 | EXPECT_EQ(0U, h2.size()); | ||
557 | EXPECT_EQ(2U, h3.size()); | ||
558 | |||
559 | // remove copies shared contents | ||
560 | h1 = h3; | ||
561 | ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2)); | ||
562 | ASSERT_EQ(originalBuckets, getBuckets(h1)); | ||
563 | h1.removeAt(index0); | ||
564 | ASSERT_NO_FATAL_FAILURE(assertInstanceCount(3, 3)); | ||
565 | ASSERT_NE(originalBuckets, getBuckets(h1)); | ||
566 | EXPECT_EQ(1U, h1.size()); | ||
567 | EXPECT_EQ(0U, h2.size()); | ||
568 | EXPECT_EQ(2U, h3.size()); | ||
569 | |||
570 | // rehash copies shared contents | ||
571 | h1 = h3; | ||
572 | ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2)); | ||
573 | ASSERT_EQ(originalBuckets, getBuckets(h1)); | ||
574 | h1.rehash(10, 1.0f); | ||
575 | ASSERT_NO_FATAL_FAILURE(assertInstanceCount(4, 4)); | ||
576 | ASSERT_NE(originalBuckets, getBuckets(h1)); | ||
577 | EXPECT_EQ(2U, h1.size()); | ||
578 | EXPECT_EQ(0U, h2.size()); | ||
579 | EXPECT_EQ(2U, h3.size()); | ||
580 | } | ||
581 | |||
582 | } // namespace android | ||