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 android {
25
26 typedef int SimpleKey;
27 typedef int SimpleValue;
28 typedef key_value_pair_t<SimpleKey, SimpleValue> SimpleEntry;
29 typedef BasicHashtable<SimpleKey, SimpleEntry> SimpleHashtable;
30
31 struct ComplexKey {
32 int k;
33
ComplexKeyandroid::ComplexKey34 explicit ComplexKey(int k) : k(k) {
35 instanceCount += 1;
36 }
37
ComplexKeyandroid::ComplexKey38 ComplexKey(const ComplexKey& other) : k(other.k) {
39 instanceCount += 1;
40 }
41
~ComplexKeyandroid::ComplexKey42 ~ComplexKey() {
43 instanceCount -= 1;
44 }
45
operator ==android::ComplexKey46 bool operator ==(const ComplexKey& other) const {
47 return k == other.k;
48 }
49
operator !=android::ComplexKey50 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
hash_type(const ComplexKey & value)59 template<> inline hash_t hash_type(const ComplexKey& value) {
60 return hash_type(value.k);
61 }
62
63 struct ComplexValue {
64 int v;
65
ComplexValueandroid::ComplexValue66 explicit ComplexValue(int v) : v(v) {
67 instanceCount += 1;
68 }
69
ComplexValueandroid::ComplexValue70 ComplexValue(const ComplexValue& other) : v(other.v) {
71 instanceCount += 1;
72 }
73
~ComplexValueandroid::ComplexValue74 ~ComplexValue() {
75 instanceCount -= 1;
76 }
77
78 static ssize_t instanceCount;
79 };
80
81 ssize_t ComplexValue::instanceCount = 0;
82
83 typedef key_value_pair_t<ComplexKey, ComplexValue> ComplexEntry;
84 typedef BasicHashtable<ComplexKey, ComplexEntry> ComplexHashtable;
85
86 class BasicHashtableTest : public testing::Test {
87 protected:
SetUp()88 virtual void SetUp() {
89 ComplexKey::instanceCount = 0;
90 ComplexValue::instanceCount = 0;
91 }
92
TearDown()93 virtual void TearDown() {
94 ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0));
95 }
96
assertInstanceCount(ssize_t keys,ssize_t values)97 void assertInstanceCount(ssize_t keys, ssize_t values) {
98 if (keys != ComplexKey::instanceCount || values != ComplexValue::instanceCount) {
99 FAIL() << "Expected " << keys << " keys and " << values << " values "
100 "but there were actually " << ComplexKey::instanceCount << " keys and "
101 << ComplexValue::instanceCount << " values";
102 }
103 }
104
105 public:
106 template <typename TKey, typename TEntry>
cookieAt(const BasicHashtable<TKey,TEntry> & h,size_t index,bool * collision,bool * present,hash_t * hash)107 static void cookieAt(const BasicHashtable<TKey, TEntry>& h, size_t index,
108 bool* collision, bool* present, hash_t* hash) {
109 uint32_t cookie = h.cookieAt(index);
110 *collision = cookie & BasicHashtable<TKey, TEntry>::Bucket::COLLISION;
111 *present = cookie & BasicHashtable<TKey, TEntry>::Bucket::PRESENT;
112 *hash = cookie & BasicHashtable<TKey, TEntry>::Bucket::HASH_MASK;
113 }
114
115 template <typename TKey, typename TEntry>
getBuckets(const BasicHashtable<TKey,TEntry> & h)116 static const void* getBuckets(const BasicHashtable<TKey, TEntry>& h) {
117 return h.mBuckets;
118 }
119 };
120
121 template <typename TKey, typename TValue>
add(BasicHashtable<TKey,key_value_pair_t<TKey,TValue>> & h,const TKey & key,const TValue & value)122 static size_t add(BasicHashtable<TKey, key_value_pair_t<TKey, TValue> >& h,
123 const TKey& key, const TValue& value) {
124 return h.add(hash_type(key), key_value_pair_t<TKey, TValue>(key, value));
125 }
126
127 template <typename TKey, typename TValue>
find(BasicHashtable<TKey,key_value_pair_t<TKey,TValue>> & h,ssize_t index,const TKey & key)128 static ssize_t find(BasicHashtable<TKey, key_value_pair_t<TKey, TValue> >& h,
129 ssize_t index, const TKey& key) {
130 return h.find(index, hash_type(key), key);
131 }
132
133 template <typename TKey, typename TValue>
remove(BasicHashtable<TKey,key_value_pair_t<TKey,TValue>> & h,const TKey & key)134 static bool remove(BasicHashtable<TKey, key_value_pair_t<TKey, TValue> >& h,
135 const TKey& key) {
136 ssize_t index = find(h, -1, key);
137 if (index >= 0) {
138 h.removeAt(index);
139 return true;
140 }
141 return false;
142 }
143
144 template <typename TEntry>
145 static void getKeyValue(const TEntry& entry, int* key, int* value);
146
getKeyValue(const SimpleEntry & entry,int * key,int * value)147 template <> void getKeyValue(const SimpleEntry& entry, int* key, int* value) {
148 *key = entry.key;
149 *value = entry.value;
150 }
151
getKeyValue(const ComplexEntry & entry,int * key,int * value)152 template <> void getKeyValue(const ComplexEntry& entry, int* key, int* value) {
153 *key = entry.key.k;
154 *value = entry.value.v;
155 }
156
157 template <typename TKey, typename TValue>
dump(BasicHashtable<TKey,key_value_pair_t<TKey,TValue>> & h)158 static void dump(BasicHashtable<TKey, key_value_pair_t<TKey, TValue> >& h) {
159 ALOGD("hashtable %p, size=%u, capacity=%u, bucketCount=%u",
160 &h, h.size(), h.capacity(), h.bucketCount());
161 for (size_t i = 0; i < h.bucketCount(); i++) {
162 bool collision, present;
163 hash_t hash;
164 BasicHashtableTest::cookieAt(h, i, &collision, &present, &hash);
165 if (present) {
166 int key, value;
167 getKeyValue(h.entryAt(i), &key, &value);
168 ALOGD(" [%3u] = collision=%d, present=%d, hash=0x%08x, key=%3d, value=%3d, "
169 "hash_type(key)=0x%08x",
170 i, collision, present, hash, key, value, hash_type(key));
171 } else {
172 ALOGD(" [%3u] = collision=%d, present=%d",
173 i, collision, present);
174 }
175 }
176 }
177
TEST_F(BasicHashtableTest,DefaultConstructor_WithDefaultProperties)178 TEST_F(BasicHashtableTest, DefaultConstructor_WithDefaultProperties) {
179 SimpleHashtable h;
180
181 EXPECT_EQ(0U, h.size());
182 EXPECT_EQ(3U, h.capacity());
183 EXPECT_EQ(5U, h.bucketCount());
184 EXPECT_EQ(0.75f, h.loadFactor());
185 }
186
TEST_F(BasicHashtableTest,Constructor_WithNonUnityLoadFactor)187 TEST_F(BasicHashtableTest, Constructor_WithNonUnityLoadFactor) {
188 SimpleHashtable h(52, 0.8f);
189
190 EXPECT_EQ(0U, h.size());
191 EXPECT_EQ(77U, h.capacity());
192 EXPECT_EQ(97U, h.bucketCount());
193 EXPECT_EQ(0.8f, h.loadFactor());
194 }
195
TEST_F(BasicHashtableTest,Constructor_WithUnityLoadFactorAndExactCapacity)196 TEST_F(BasicHashtableTest, Constructor_WithUnityLoadFactorAndExactCapacity) {
197 SimpleHashtable h(46, 1.0f);
198
199 EXPECT_EQ(0U, h.size());
200 EXPECT_EQ(46U, h.capacity()); // must be one less than bucketCount because loadFactor == 1.0f
201 EXPECT_EQ(47U, h.bucketCount());
202 EXPECT_EQ(1.0f, h.loadFactor());
203 }
204
TEST_F(BasicHashtableTest,Constructor_WithUnityLoadFactorAndInexactCapacity)205 TEST_F(BasicHashtableTest, Constructor_WithUnityLoadFactorAndInexactCapacity) {
206 SimpleHashtable h(42, 1.0f);
207
208 EXPECT_EQ(0U, h.size());
209 EXPECT_EQ(46U, h.capacity()); // must be one less than bucketCount because loadFactor == 1.0f
210 EXPECT_EQ(47U, h.bucketCount());
211 EXPECT_EQ(1.0f, h.loadFactor());
212 }
213
TEST_F(BasicHashtableTest,FindAddFindRemoveFind_OneEntry)214 TEST_F(BasicHashtableTest, FindAddFindRemoveFind_OneEntry) {
215 SimpleHashtable h;
216 ssize_t index = find(h, -1, 8);
217 ASSERT_EQ(-1, index);
218
219 index = add(h, 8, 1);
220 ASSERT_EQ(1U, h.size());
221
222 ASSERT_EQ(index, find(h, -1, 8));
223 ASSERT_EQ(8, h.entryAt(index).key);
224 ASSERT_EQ(1, h.entryAt(index).value);
225
226 index = find(h, index, 8);
227 ASSERT_EQ(-1, index);
228
229 ASSERT_TRUE(remove(h, 8));
230 ASSERT_EQ(0U, h.size());
231
232 index = find(h, -1, 8);
233 ASSERT_EQ(-1, index);
234 }
235
TEST_F(BasicHashtableTest,FindAddFindRemoveFind_MultipleEntryWithUniqueKey)236 TEST_F(BasicHashtableTest, FindAddFindRemoveFind_MultipleEntryWithUniqueKey) {
237 const size_t N = 11;
238
239 SimpleHashtable h;
240 for (size_t i = 0; i < N; i++) {
241 ssize_t index = find(h, -1, int(i));
242 ASSERT_EQ(-1, index);
243
244 index = add(h, int(i), int(i * 10));
245 ASSERT_EQ(i + 1, h.size());
246
247 ASSERT_EQ(index, find(h, -1, int(i)));
248 ASSERT_EQ(int(i), h.entryAt(index).key);
249 ASSERT_EQ(int(i * 10), h.entryAt(index).value);
250
251 index = find(h, index, int(i));
252 ASSERT_EQ(-1, index);
253 }
254
255 for (size_t i = N; --i > 0; ) {
256 ASSERT_TRUE(remove(h, int(i))) << "i = " << i;
257 ASSERT_EQ(i, h.size());
258
259 ssize_t index = find(h, -1, int(i));
260 ASSERT_EQ(-1, index);
261 }
262 }
263
TEST_F(BasicHashtableTest,FindAddFindRemoveFind_MultipleEntryWithDuplicateKey)264 TEST_F(BasicHashtableTest, FindAddFindRemoveFind_MultipleEntryWithDuplicateKey) {
265 const size_t N = 11;
266 const int K = 1;
267
268 SimpleHashtable h;
269 for (size_t i = 0; i < N; i++) {
270 ssize_t index = find(h, -1, K);
271 if (i == 0) {
272 ASSERT_EQ(-1, index);
273 } else {
274 ASSERT_NE(-1, index);
275 }
276
277 add(h, K, int(i));
278 ASSERT_EQ(i + 1, h.size());
279
280 index = -1;
281 int values = 0;
282 for (size_t j = 0; j <= i; j++) {
283 index = find(h, index, K);
284 ASSERT_GE(index, 0);
285 ASSERT_EQ(K, h.entryAt(index).key);
286 values |= 1 << h.entryAt(index).value;
287 }
288 ASSERT_EQ(values, (1 << (i + 1)) - 1);
289
290 index = find(h, index, K);
291 ASSERT_EQ(-1, index);
292 }
293
294 for (size_t i = N; --i > 0; ) {
295 ASSERT_TRUE(remove(h, K)) << "i = " << i;
296 ASSERT_EQ(i, h.size());
297
298 ssize_t index = -1;
299 for (size_t j = 0; j < i; j++) {
300 index = find(h, index, K);
301 ASSERT_GE(index, 0);
302 ASSERT_EQ(K, h.entryAt(index).key);
303 }
304
305 index = find(h, index, K);
306 ASSERT_EQ(-1, index);
307 }
308 }
309
TEST_F(BasicHashtableTest,Clear_WhenAlreadyEmpty_DoesNothing)310 TEST_F(BasicHashtableTest, Clear_WhenAlreadyEmpty_DoesNothing) {
311 SimpleHashtable h;
312 h.clear();
313
314 EXPECT_EQ(0U, h.size());
315 EXPECT_EQ(3U, h.capacity());
316 EXPECT_EQ(5U, h.bucketCount());
317 EXPECT_EQ(0.75f, h.loadFactor());
318 }
319
TEST_F(BasicHashtableTest,Clear_AfterElementsAdded_RemovesThem)320 TEST_F(BasicHashtableTest, Clear_AfterElementsAdded_RemovesThem) {
321 SimpleHashtable h;
322 add(h, 0, 0);
323 add(h, 1, 0);
324 h.clear();
325
326 EXPECT_EQ(0U, h.size());
327 EXPECT_EQ(3U, h.capacity());
328 EXPECT_EQ(5U, h.bucketCount());
329 EXPECT_EQ(0.75f, h.loadFactor());
330 }
331
TEST_F(BasicHashtableTest,Clear_AfterElementsAdded_DestroysThem)332 TEST_F(BasicHashtableTest, Clear_AfterElementsAdded_DestroysThem) {
333 ComplexHashtable h;
334 add(h, ComplexKey(0), ComplexValue(0));
335 add(h, ComplexKey(1), ComplexValue(0));
336 ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2));
337
338 h.clear();
339 ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0));
340
341 EXPECT_EQ(0U, h.size());
342 EXPECT_EQ(3U, h.capacity());
343 EXPECT_EQ(5U, h.bucketCount());
344 EXPECT_EQ(0.75f, h.loadFactor());
345 }
346
TEST_F(BasicHashtableTest,Remove_AfterElementsAdded_DestroysThem)347 TEST_F(BasicHashtableTest, Remove_AfterElementsAdded_DestroysThem) {
348 ComplexHashtable h;
349 add(h, ComplexKey(0), ComplexValue(0));
350 add(h, ComplexKey(1), ComplexValue(0));
351 ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2));
352
353 ASSERT_TRUE(remove(h, ComplexKey(0)));
354 ASSERT_NO_FATAL_FAILURE(assertInstanceCount(1, 1));
355
356 ASSERT_TRUE(remove(h, ComplexKey(1)));
357 ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0));
358
359 EXPECT_EQ(0U, h.size());
360 EXPECT_EQ(3U, h.capacity());
361 EXPECT_EQ(5U, h.bucketCount());
362 EXPECT_EQ(0.75f, h.loadFactor());
363 }
364
TEST_F(BasicHashtableTest,Destructor_AfterElementsAdded_DestroysThem)365 TEST_F(BasicHashtableTest, Destructor_AfterElementsAdded_DestroysThem) {
366 {
367 ComplexHashtable h;
368 add(h, ComplexKey(0), ComplexValue(0));
369 add(h, ComplexKey(1), ComplexValue(0));
370 ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2));
371 } // h is destroyed here
372
373 ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0));
374 }
375
TEST_F(BasicHashtableTest,Next_WhenEmpty_ReturnsMinusOne)376 TEST_F(BasicHashtableTest, Next_WhenEmpty_ReturnsMinusOne) {
377 SimpleHashtable h;
378
379 ASSERT_EQ(-1, h.next(-1));
380 }
381
TEST_F(BasicHashtableTest,Next_WhenNonEmpty_IteratesOverAllEntries)382 TEST_F(BasicHashtableTest, Next_WhenNonEmpty_IteratesOverAllEntries) {
383 const int N = 88;
384
385 SimpleHashtable h;
386 for (int i = 0; i < N; i++) {
387 add(h, i, i * 10);
388 }
389
390 bool set[N];
391 memset(set, 0, sizeof(bool) * N);
392 int count = 0;
393 for (ssize_t index = -1; (index = h.next(index)) != -1; ) {
394 ASSERT_GE(index, 0);
395 ASSERT_LT(size_t(index), h.bucketCount());
396
397 const SimpleEntry& entry = h.entryAt(index);
398 ASSERT_GE(entry.key, 0);
399 ASSERT_LT(entry.key, N);
400 ASSERT_EQ(false, set[entry.key]);
401 ASSERT_EQ(entry.key * 10, entry.value);
402
403 set[entry.key] = true;
404 count += 1;
405 }
406 ASSERT_EQ(N, count);
407 }
408
TEST_F(BasicHashtableTest,Add_RehashesOnDemand)409 TEST_F(BasicHashtableTest, Add_RehashesOnDemand) {
410 SimpleHashtable h;
411 size_t initialCapacity = h.capacity();
412 size_t initialBucketCount = h.bucketCount();
413
414 for (size_t i = 0; i < initialCapacity; i++) {
415 add(h, int(i), 0);
416 }
417
418 EXPECT_EQ(initialCapacity, h.size());
419 EXPECT_EQ(initialCapacity, h.capacity());
420 EXPECT_EQ(initialBucketCount, h.bucketCount());
421
422 add(h, -1, -1);
423
424 EXPECT_EQ(initialCapacity + 1, h.size());
425 EXPECT_GT(h.capacity(), initialCapacity);
426 EXPECT_GT(h.bucketCount(), initialBucketCount);
427 EXPECT_GT(h.bucketCount(), h.capacity());
428 }
429
TEST_F(BasicHashtableTest,Rehash_WhenCapacityAndBucketCountUnchanged_DoesNothing)430 TEST_F(BasicHashtableTest, Rehash_WhenCapacityAndBucketCountUnchanged_DoesNothing) {
431 ComplexHashtable h;
432 add(h, ComplexKey(0), ComplexValue(0));
433 const void* oldBuckets = getBuckets(h);
434 ASSERT_NE((void*)NULL, oldBuckets);
435 ASSERT_NO_FATAL_FAILURE(assertInstanceCount(1, 1));
436
437 h.rehash(h.capacity(), h.loadFactor());
438
439 ASSERT_EQ(oldBuckets, getBuckets(h));
440 ASSERT_NO_FATAL_FAILURE(assertInstanceCount(1, 1));
441 }
442
TEST_F(BasicHashtableTest,Rehash_WhenEmptyAndHasNoBuckets_ButDoesNotAllocateBuckets)443 TEST_F(BasicHashtableTest, Rehash_WhenEmptyAndHasNoBuckets_ButDoesNotAllocateBuckets) {
444 ComplexHashtable h;
445 ASSERT_EQ((void*)NULL, getBuckets(h));
446 ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0));
447
448 h.rehash(9, 1.0f);
449
450 EXPECT_EQ(0U, h.size());
451 EXPECT_EQ(10U, h.capacity());
452 EXPECT_EQ(11U, h.bucketCount());
453 EXPECT_EQ(1.0f, h.loadFactor());
454 EXPECT_EQ((void*)NULL, getBuckets(h));
455 ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0));
456 }
457
TEST_F(BasicHashtableTest,Rehash_WhenEmptyAndHasBuckets_ReleasesBucketsAndSetsCapacity)458 TEST_F(BasicHashtableTest, Rehash_WhenEmptyAndHasBuckets_ReleasesBucketsAndSetsCapacity) {
459 ComplexHashtable h(10);
460 add(h, ComplexKey(0), ComplexValue(0));
461 ASSERT_TRUE(remove(h, ComplexKey(0)));
462 ASSERT_NE((void*)NULL, getBuckets(h));
463 ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0));
464
465 h.rehash(0, 0.75f);
466
467 EXPECT_EQ(0U, h.size());
468 EXPECT_EQ(3U, h.capacity());
469 EXPECT_EQ(5U, h.bucketCount());
470 EXPECT_EQ(0.75f, h.loadFactor());
471 EXPECT_EQ((void*)NULL, getBuckets(h));
472 ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0));
473 }
474
TEST_F(BasicHashtableTest,Rehash_WhenLessThanCurrentCapacity_ShrinksBuckets)475 TEST_F(BasicHashtableTest, Rehash_WhenLessThanCurrentCapacity_ShrinksBuckets) {
476 ComplexHashtable h(10);
477 add(h, ComplexKey(0), ComplexValue(0));
478 add(h, ComplexKey(1), ComplexValue(1));
479 const void* oldBuckets = getBuckets(h);
480 ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2));
481
482 h.rehash(0, 0.75f);
483
484 EXPECT_EQ(2U, h.size());
485 EXPECT_EQ(3U, h.capacity());
486 EXPECT_EQ(5U, h.bucketCount());
487 EXPECT_EQ(0.75f, h.loadFactor());
488 EXPECT_NE(oldBuckets, getBuckets(h));
489 ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2));
490 }
491
TEST_F(BasicHashtableTest,CopyOnWrite)492 TEST_F(BasicHashtableTest, CopyOnWrite) {
493 ComplexHashtable h1;
494 add(h1, ComplexKey(0), ComplexValue(0));
495 add(h1, ComplexKey(1), ComplexValue(1));
496 const void* originalBuckets = getBuckets(h1);
497 ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2));
498 ssize_t index0 = find(h1, -1, ComplexKey(0));
499 EXPECT_GE(index0, 0);
500
501 // copy constructor acquires shared reference
502 ComplexHashtable h2(h1);
503 ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2));
504 ASSERT_EQ(originalBuckets, getBuckets(h2));
505 EXPECT_EQ(h1.size(), h2.size());
506 EXPECT_EQ(h1.capacity(), h2.capacity());
507 EXPECT_EQ(h1.bucketCount(), h2.bucketCount());
508 EXPECT_EQ(h1.loadFactor(), h2.loadFactor());
509 EXPECT_EQ(index0, find(h2, -1, ComplexKey(0)));
510
511 // operator= acquires shared reference
512 ComplexHashtable h3;
513 h3 = h2;
514 ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2));
515 ASSERT_EQ(originalBuckets, getBuckets(h3));
516 EXPECT_EQ(h1.size(), h3.size());
517 EXPECT_EQ(h1.capacity(), h3.capacity());
518 EXPECT_EQ(h1.bucketCount(), h3.bucketCount());
519 EXPECT_EQ(h1.loadFactor(), h3.loadFactor());
520 EXPECT_EQ(index0, find(h3, -1, ComplexKey(0)));
521
522 // editEntryAt copies shared contents
523 h1.editEntryAt(index0).value.v = 42;
524 ASSERT_NO_FATAL_FAILURE(assertInstanceCount(4, 4));
525 ASSERT_NE(originalBuckets, getBuckets(h1));
526 EXPECT_EQ(42, h1.entryAt(index0).value.v);
527 EXPECT_EQ(0, h2.entryAt(index0).value.v);
528 EXPECT_EQ(0, h3.entryAt(index0).value.v);
529
530 // clear releases reference to shared contents
531 h2.clear();
532 ASSERT_NO_FATAL_FAILURE(assertInstanceCount(4, 4));
533 EXPECT_EQ(0U, h2.size());
534 ASSERT_NE(originalBuckets, getBuckets(h2));
535
536 // operator= acquires shared reference, destroys unshared contents
537 h1 = h3;
538 ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2));
539 ASSERT_EQ(originalBuckets, getBuckets(h1));
540 EXPECT_EQ(h3.size(), h1.size());
541 EXPECT_EQ(h3.capacity(), h1.capacity());
542 EXPECT_EQ(h3.bucketCount(), h1.bucketCount());
543 EXPECT_EQ(h3.loadFactor(), h1.loadFactor());
544 EXPECT_EQ(index0, find(h1, -1, ComplexKey(0)));
545
546 // add copies shared contents
547 add(h1, ComplexKey(2), ComplexValue(2));
548 ASSERT_NO_FATAL_FAILURE(assertInstanceCount(5, 5));
549 ASSERT_NE(originalBuckets, getBuckets(h1));
550 EXPECT_EQ(3U, h1.size());
551 EXPECT_EQ(0U, h2.size());
552 EXPECT_EQ(2U, h3.size());
553
554 // remove copies shared contents
555 h1 = h3;
556 ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2));
557 ASSERT_EQ(originalBuckets, getBuckets(h1));
558 h1.removeAt(index0);
559 ASSERT_NO_FATAL_FAILURE(assertInstanceCount(3, 3));
560 ASSERT_NE(originalBuckets, getBuckets(h1));
561 EXPECT_EQ(1U, h1.size());
562 EXPECT_EQ(0U, h2.size());
563 EXPECT_EQ(2U, h3.size());
564
565 // rehash copies shared contents
566 h1 = h3;
567 ASSERT_NO_FATAL_FAILURE(assertInstanceCount(2, 2));
568 ASSERT_EQ(originalBuckets, getBuckets(h1));
569 h1.rehash(10, 1.0f);
570 ASSERT_NO_FATAL_FAILURE(assertInstanceCount(4, 4));
571 ASSERT_NE(originalBuckets, getBuckets(h1));
572 EXPECT_EQ(2U, h1.size());
573 EXPECT_EQ(0U, h2.size());
574 EXPECT_EQ(2U, h3.size());
575 }
576
577 } // namespace android
578