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
ComplexKey__anond76edae20111::ComplexKey34 explicit ComplexKey(int k) : k(k) {
35 instanceCount += 1;
36 }
37
ComplexKey__anond76edae20111::ComplexKey38 ComplexKey(const ComplexKey& other) : k(other.k) {
39 instanceCount += 1;
40 }
41
~ComplexKey__anond76edae20111::ComplexKey42 ~ComplexKey() {
43 instanceCount -= 1;
44 }
45
operator ==__anond76edae20111::ComplexKey46 bool operator ==(const ComplexKey& other) const {
47 return k == other.k;
48 }
49
operator !=__anond76edae20111::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
59 struct ComplexValue {
60 int v;
61
ComplexValue__anond76edae20111::ComplexValue62 explicit ComplexValue(int v) : v(v) {
63 instanceCount += 1;
64 }
65
ComplexValue__anond76edae20111::ComplexValue66 ComplexValue(const ComplexValue& other) : v(other.v) {
67 instanceCount += 1;
68 }
69
~ComplexValue__anond76edae20111::ComplexValue70 ~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
hash_type(const ComplexKey & value)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:
SetUp()93 virtual void SetUp() {
94 ComplexKey::instanceCount = 0;
95 ComplexValue::instanceCount = 0;
96 }
97
TearDown()98 virtual void TearDown() {
99 ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0));
100 }
101
assertInstanceCount(ssize_t keys,ssize_t values)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>
cookieAt(const BasicHashtable<TKey,TEntry> & h,size_t index,bool * collision,bool * present,hash_t * hash)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>
getBuckets(const BasicHashtable<TKey,TEntry> & h)121 static const void* getBuckets(const BasicHashtable<TKey, TEntry>& h) {
122 return h.mBuckets;
123 }
124 };
125
126 template <typename TKey, typename TValue>
add(BasicHashtable<TKey,key_value_pair_t<TKey,TValue>> & h,const TKey & key,const TValue & value)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>
find(BasicHashtable<TKey,key_value_pair_t<TKey,TValue>> & h,ssize_t index,const TKey & key)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>
remove(BasicHashtable<TKey,key_value_pair_t<TKey,TValue>> & h,const TKey & key)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
getKeyValue(const SimpleEntry & entry,int * key,int * value)152 template <> void getKeyValue(const SimpleEntry& entry, int* key, int* value) {
153 *key = entry.key;
154 *value = entry.value;
155 }
156
getKeyValue(const ComplexEntry & entry,int * key,int * value)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>
dump(BasicHashtable<TKey,key_value_pair_t<TKey,TValue>> & h)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
TEST_F(BasicHashtableTest,DefaultConstructor_WithDefaultProperties)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
TEST_F(BasicHashtableTest,Constructor_WithNonUnityLoadFactor)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
TEST_F(BasicHashtableTest,Constructor_WithUnityLoadFactorAndExactCapacity)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
TEST_F(BasicHashtableTest,Constructor_WithUnityLoadFactorAndInexactCapacity)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
TEST_F(BasicHashtableTest,FindAddFindRemoveFind_OneEntry)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
TEST_F(BasicHashtableTest,FindAddFindRemoveFind_MultipleEntryWithUniqueKey)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
TEST_F(BasicHashtableTest,FindAddFindRemoveFind_MultipleEntryWithDuplicateKey)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
TEST_F(BasicHashtableTest,Clear_WhenAlreadyEmpty_DoesNothing)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
TEST_F(BasicHashtableTest,Clear_AfterElementsAdded_RemovesThem)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
TEST_F(BasicHashtableTest,Clear_AfterElementsAdded_DestroysThem)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
TEST_F(BasicHashtableTest,Remove_AfterElementsAdded_DestroysThem)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
TEST_F(BasicHashtableTest,Destructor_AfterElementsAdded_DestroysThem)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
TEST_F(BasicHashtableTest,Next_WhenEmpty_ReturnsMinusOne)381 TEST_F(BasicHashtableTest, Next_WhenEmpty_ReturnsMinusOne) {
382 SimpleHashtable h;
383
384 ASSERT_EQ(-1, h.next(-1));
385 }
386
TEST_F(BasicHashtableTest,Next_WhenNonEmpty_IteratesOverAllEntries)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
TEST_F(BasicHashtableTest,Add_RehashesOnDemand)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
TEST_F(BasicHashtableTest,Rehash_WhenCapacityAndBucketCountUnchanged_DoesNothing)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
TEST_F(BasicHashtableTest,Rehash_WhenEmptyAndHasNoBuckets_ButDoesNotAllocateBuckets)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
TEST_F(BasicHashtableTest,Rehash_WhenEmptyAndHasBuckets_ReleasesBucketsAndSetsCapacity)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
TEST_F(BasicHashtableTest,Rehash_WhenLessThanCurrentCapacity_ShrinksBuckets)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
TEST_F(BasicHashtableTest,CopyOnWrite)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
583