diff options
Diffstat (limited to 'libutils/BasicHashtable.cpp')
| -rw-r--r-- | libutils/BasicHashtable.cpp | 342 |
1 files changed, 342 insertions, 0 deletions
diff --git a/libutils/BasicHashtable.cpp b/libutils/BasicHashtable.cpp new file mode 100644 index 0000000..491d9e9 --- /dev/null +++ b/libutils/BasicHashtable.cpp @@ -0,0 +1,342 @@ +/* + * Copyright (C) 2011 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#define LOG_TAG "BasicHashtable" + +#include <math.h> + +#include <utils/Log.h> +#include <utils/BasicHashtable.h> +#include <utils/misc.h> + +namespace android { + +BasicHashtableImpl::BasicHashtableImpl(size_t entrySize, bool hasTrivialDestructor, + size_t minimumInitialCapacity, float loadFactor) : + mBucketSize(entrySize + sizeof(Bucket)), mHasTrivialDestructor(hasTrivialDestructor), + mLoadFactor(loadFactor), mSize(0), + mFilledBuckets(0), mBuckets(NULL) { + determineCapacity(minimumInitialCapacity, mLoadFactor, &mBucketCount, &mCapacity); +} + +BasicHashtableImpl::BasicHashtableImpl(const BasicHashtableImpl& other) : + mBucketSize(other.mBucketSize), mHasTrivialDestructor(other.mHasTrivialDestructor), + mCapacity(other.mCapacity), mLoadFactor(other.mLoadFactor), + mSize(other.mSize), mFilledBuckets(other.mFilledBuckets), + mBucketCount(other.mBucketCount), mBuckets(other.mBuckets) { + if (mBuckets) { + SharedBuffer::bufferFromData(mBuckets)->acquire(); + } +} + +BasicHashtableImpl::~BasicHashtableImpl() +{ +} + +void BasicHashtableImpl::dispose() { + if (mBuckets) { + releaseBuckets(mBuckets, mBucketCount); + } +} + +void BasicHashtableImpl::clone() { + if (mBuckets) { + void* newBuckets = allocateBuckets(mBucketCount); + copyBuckets(mBuckets, newBuckets, mBucketCount); + releaseBuckets(mBuckets, mBucketCount); + mBuckets = newBuckets; + } +} + +void BasicHashtableImpl::setTo(const BasicHashtableImpl& other) { + if (mBuckets) { + releaseBuckets(mBuckets, mBucketCount); + } + + mCapacity = other.mCapacity; + mLoadFactor = other.mLoadFactor; + mSize = other.mSize; + mFilledBuckets = other.mFilledBuckets; + mBucketCount = other.mBucketCount; + mBuckets = other.mBuckets; + + if (mBuckets) { + SharedBuffer::bufferFromData(mBuckets)->acquire(); + } +} + +void BasicHashtableImpl::clear() { + if (mBuckets) { + if (mFilledBuckets) { + SharedBuffer* sb = SharedBuffer::bufferFromData(mBuckets); + if (sb->onlyOwner()) { + destroyBuckets(mBuckets, mBucketCount); + for (size_t i = 0; i < mBucketCount; i++) { + Bucket& bucket = bucketAt(mBuckets, i); + bucket.cookie = 0; + } + } else { + releaseBuckets(mBuckets, mBucketCount); + mBuckets = NULL; + } + mFilledBuckets = 0; + } + mSize = 0; + } +} + +ssize_t BasicHashtableImpl::next(ssize_t index) const { + if (mSize) { + while (size_t(++index) < mBucketCount) { + const Bucket& bucket = bucketAt(mBuckets, index); + if (bucket.cookie & Bucket::PRESENT) { + return index; + } + } + } + return -1; +} + +ssize_t BasicHashtableImpl::find(ssize_t index, hash_t hash, + const void* __restrict__ key) const { + if (!mSize) { + return -1; + } + + hash = trimHash(hash); + if (index < 0) { + index = chainStart(hash, mBucketCount); + + const Bucket& bucket = bucketAt(mBuckets, size_t(index)); + if (bucket.cookie & Bucket::PRESENT) { + if (compareBucketKey(bucket, key)) { + return index; + } + } else { + if (!(bucket.cookie & Bucket::COLLISION)) { + return -1; + } + } + } + + size_t inc = chainIncrement(hash, mBucketCount); + for (;;) { + index = chainSeek(index, inc, mBucketCount); + + const Bucket& bucket = bucketAt(mBuckets, size_t(index)); + if (bucket.cookie & Bucket::PRESENT) { + if ((bucket.cookie & Bucket::HASH_MASK) == hash + && compareBucketKey(bucket, key)) { + return index; + } + } + if (!(bucket.cookie & Bucket::COLLISION)) { + return -1; + } + } +} + +size_t BasicHashtableImpl::add(hash_t hash, const void* entry) { + if (!mBuckets) { + mBuckets = allocateBuckets(mBucketCount); + } else { + edit(); + } + + hash = trimHash(hash); + for (;;) { + size_t index = chainStart(hash, mBucketCount); + Bucket* bucket = &bucketAt(mBuckets, size_t(index)); + if (bucket->cookie & Bucket::PRESENT) { + size_t inc = chainIncrement(hash, mBucketCount); + do { + bucket->cookie |= Bucket::COLLISION; + index = chainSeek(index, inc, mBucketCount); + bucket = &bucketAt(mBuckets, size_t(index)); + } while (bucket->cookie & Bucket::PRESENT); + } + + uint32_t collision = bucket->cookie & Bucket::COLLISION; + if (!collision) { + if (mFilledBuckets >= mCapacity) { + rehash(mCapacity * 2, mLoadFactor); + continue; + } + mFilledBuckets += 1; + } + + bucket->cookie = collision | Bucket::PRESENT | hash; + mSize += 1; + initializeBucketEntry(*bucket, entry); + return index; + } +} + +void BasicHashtableImpl::removeAt(size_t index) { + edit(); + + Bucket& bucket = bucketAt(mBuckets, index); + bucket.cookie &= ~Bucket::PRESENT; + if (!(bucket.cookie & Bucket::COLLISION)) { + mFilledBuckets -= 1; + } + mSize -= 1; + if (!mHasTrivialDestructor) { + destroyBucketEntry(bucket); + } +} + +void BasicHashtableImpl::rehash(size_t minimumCapacity, float loadFactor) { + if (minimumCapacity < mSize) { + minimumCapacity = mSize; + } + size_t newBucketCount, newCapacity; + determineCapacity(minimumCapacity, loadFactor, &newBucketCount, &newCapacity); + + if (newBucketCount != mBucketCount || newCapacity != mCapacity) { + if (mBuckets) { + void* newBuckets; + if (mSize) { + newBuckets = allocateBuckets(newBucketCount); + for (size_t i = 0; i < mBucketCount; i++) { + const Bucket& fromBucket = bucketAt(mBuckets, i); + if (fromBucket.cookie & Bucket::PRESENT) { + hash_t hash = fromBucket.cookie & Bucket::HASH_MASK; + size_t index = chainStart(hash, newBucketCount); + Bucket* toBucket = &bucketAt(newBuckets, size_t(index)); + if (toBucket->cookie & Bucket::PRESENT) { + size_t inc = chainIncrement(hash, newBucketCount); + do { + toBucket->cookie |= Bucket::COLLISION; + index = chainSeek(index, inc, newBucketCount); + toBucket = &bucketAt(newBuckets, size_t(index)); + } while (toBucket->cookie & Bucket::PRESENT); + } + toBucket->cookie = Bucket::PRESENT | hash; + initializeBucketEntry(*toBucket, fromBucket.entry); + } + } + } else { + newBuckets = NULL; + } + releaseBuckets(mBuckets, mBucketCount); + mBuckets = newBuckets; + mFilledBuckets = mSize; + } + mBucketCount = newBucketCount; + mCapacity = newCapacity; + } + mLoadFactor = loadFactor; +} + +void* BasicHashtableImpl::allocateBuckets(size_t count) const { + size_t bytes = count * mBucketSize; + SharedBuffer* sb = SharedBuffer::alloc(bytes); + LOG_ALWAYS_FATAL_IF(!sb, "Could not allocate %u bytes for hashtable with %u buckets.", + uint32_t(bytes), uint32_t(count)); + void* buckets = sb->data(); + for (size_t i = 0; i < count; i++) { + Bucket& bucket = bucketAt(buckets, i); + bucket.cookie = 0; + } + return buckets; +} + +void BasicHashtableImpl::releaseBuckets(void* __restrict__ buckets, size_t count) const { + SharedBuffer* sb = SharedBuffer::bufferFromData(buckets); + if (sb->release(SharedBuffer::eKeepStorage) == 1) { + destroyBuckets(buckets, count); + SharedBuffer::dealloc(sb); + } +} + +void BasicHashtableImpl::destroyBuckets(void* __restrict__ buckets, size_t count) const { + if (!mHasTrivialDestructor) { + for (size_t i = 0; i < count; i++) { + Bucket& bucket = bucketAt(buckets, i); + if (bucket.cookie & Bucket::PRESENT) { + destroyBucketEntry(bucket); + } + } + } +} + +void BasicHashtableImpl::copyBuckets(const void* __restrict__ fromBuckets, + void* __restrict__ toBuckets, size_t count) const { + for (size_t i = 0; i < count; i++) { + const Bucket& fromBucket = bucketAt(fromBuckets, i); + Bucket& toBucket = bucketAt(toBuckets, i); + toBucket.cookie = fromBucket.cookie; + if (fromBucket.cookie & Bucket::PRESENT) { + initializeBucketEntry(toBucket, fromBucket.entry); + } + } +} + +// Table of 31-bit primes where each prime is no less than twice as large +// as the previous one. Generated by "primes.py". +static size_t PRIMES[] = { + 5, + 11, + 23, + 47, + 97, + 197, + 397, + 797, + 1597, + 3203, + 6421, + 12853, + 25717, + 51437, + 102877, + 205759, + 411527, + 823117, + 1646237, + 3292489, + 6584983, + 13169977, + 26339969, + 52679969, + 105359939, + 210719881, + 421439783, + 842879579, + 1685759167, + 0, +}; + +void BasicHashtableImpl::determineCapacity(size_t minimumCapacity, float loadFactor, + size_t* __restrict__ outBucketCount, size_t* __restrict__ outCapacity) { + LOG_ALWAYS_FATAL_IF(loadFactor <= 0.0f || loadFactor > 1.0f, + "Invalid load factor %0.3f. Must be in the range (0, 1].", loadFactor); + + size_t count = ceilf(minimumCapacity / loadFactor) + 1; + size_t i = 0; + while (count > PRIMES[i] && i < NELEM(PRIMES)) { + i++; + } + count = PRIMES[i]; + LOG_ALWAYS_FATAL_IF(!count, "Could not determine required number of buckets for " + "hashtable with minimum capacity %u and load factor %0.3f.", + uint32_t(minimumCapacity), loadFactor); + *outBucketCount = count; + *outCapacity = ceilf((count - 1) * loadFactor); +} + +}; // namespace android |