BasicHashtable_test.cpp revision 9d4536835248525f32f1504a3d28d5bbfa0a2910 
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
24namespace android {
25
26typedef int SimpleKey;
27typedef int SimpleValue;
28typedef key_value_pair_t<SimpleKey, SimpleValue> SimpleEntry;
29typedef BasicHashtable<SimpleKey, SimpleEntry> SimpleHashtable;
30
31struct 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
57ssize_t ComplexKey::instanceCount = 0;
58
59template<> inline hash_t hash_type(const ComplexKey& value) {
60    return hash_type(value.k);
61}
62
63struct ComplexValue {
64    int v;
65
66    explicit ComplexValue(int v) : v(v) {
67        instanceCount += 1;
68    }
69
70    ComplexValue(const ComplexValue& other) : v(other.v) {
71        instanceCount += 1;
72    }
73
74    ~ComplexValue() {
75        instanceCount -= 1;
76    }
77
78    static ssize_t instanceCount;
79};
80
81ssize_t ComplexValue::instanceCount = 0;
82
83typedef key_value_pair_t<ComplexKey, ComplexValue> ComplexEntry;
84typedef BasicHashtable<ComplexKey, ComplexEntry> ComplexHashtable;
85
86class BasicHashtableTest : public testing::Test {
87protected:
88    virtual void SetUp() {
89        ComplexKey::instanceCount = 0;
90        ComplexValue::instanceCount = 0;
91    }
92
93    virtual void TearDown() {
94        ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0));
95    }
96
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
105public:
106    template <typename TKey, typename TEntry>
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>
116    static const void* getBuckets(const BasicHashtable<TKey, TEntry>& h) {
117        return h.mBuckets;
118    }
119};
120
121template <typename TKey, typename TValue>
122static 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
127template <typename TKey, typename TValue>
128static 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
133template <typename TKey, typename TValue>
134static 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
144template <typename TEntry>
145static void getKeyValue(const TEntry& entry, int* key, int* value);
146
147template <> void getKeyValue(const SimpleEntry& entry, int* key, int* value) {
148    *key = entry.key;
149    *value = entry.value;
150}
151
152template <> void getKeyValue(const ComplexEntry& entry, int* key, int* value) {
153    *key = entry.key.k;
154    *value = entry.value.v;
155}
156
157template <typename TKey, typename TValue>
158static 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
178TEST_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
187TEST_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
196TEST_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
205TEST_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
214TEST_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
236TEST_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
264TEST_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
310TEST_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
320TEST_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
332TEST_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
347TEST_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
365TEST_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
376TEST_F(BasicHashtableTest, Next_WhenEmpty_ReturnsMinusOne) {
377    SimpleHashtable h;
378
379    ASSERT_EQ(-1, h.next(-1));
380}
381
382TEST_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
409TEST_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
430TEST_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
443TEST_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
458TEST_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
475TEST_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
492TEST_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