166fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown/* 266fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown * Copyright (C) 2011 The Android Open Source Project 366fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown * 466fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown * Licensed under the Apache License, Version 2.0 (the "License"); 566fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown * you may not use this file except in compliance with the License. 666fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown * You may obtain a copy of the License at 766fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown * 866fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown * http://www.apache.org/licenses/LICENSE-2.0 966fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown * 1066fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown * Unless required by applicable law or agreed to in writing, software 1166fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown * distributed under the License is distributed on an "AS IS" BASIS, 1266fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 1366fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown * See the License for the specific language governing permissions and 1466fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown * limitations under the License. 1566fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown */ 1666fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 1766fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown#define LOG_TAG "BasicHashtable" 1866fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 1966fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown#include <math.h> 2066fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 2166fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown#include <utils/Log.h> 2266fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown#include <utils/BasicHashtable.h> 2366fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown#include <utils/misc.h> 2466fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 2566fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brownnamespace android { 2666fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 2766fbde305047b7a606d083a9ec8994fa693cc7d7Jeff BrownBasicHashtableImpl::BasicHashtableImpl(size_t entrySize, bool hasTrivialDestructor, 2866fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown size_t minimumInitialCapacity, float loadFactor) : 2966fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown mBucketSize(entrySize + sizeof(Bucket)), mHasTrivialDestructor(hasTrivialDestructor), 3066fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown mLoadFactor(loadFactor), mSize(0), 3166fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown mFilledBuckets(0), mBuckets(NULL) { 3266fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown determineCapacity(minimumInitialCapacity, mLoadFactor, &mBucketCount, &mCapacity); 3366fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown} 3466fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 3566fbde305047b7a606d083a9ec8994fa693cc7d7Jeff BrownBasicHashtableImpl::BasicHashtableImpl(const BasicHashtableImpl& other) : 3666fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown mBucketSize(other.mBucketSize), mHasTrivialDestructor(other.mHasTrivialDestructor), 3766fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown mCapacity(other.mCapacity), mLoadFactor(other.mLoadFactor), 3866fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown mSize(other.mSize), mFilledBuckets(other.mFilledBuckets), 3966fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown mBucketCount(other.mBucketCount), mBuckets(other.mBuckets) { 4066fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown if (mBuckets) { 4166fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown SharedBuffer::bufferFromData(mBuckets)->acquire(); 4266fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown } 4366fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown} 4466fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 4566fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brownvoid BasicHashtableImpl::dispose() { 4666fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown if (mBuckets) { 4766fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown releaseBuckets(mBuckets, mBucketCount); 4866fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown } 4966fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown} 5066fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 5166fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brownvoid BasicHashtableImpl::clone() { 5266fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown if (mBuckets) { 5366fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown void* newBuckets = allocateBuckets(mBucketCount); 5466fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown copyBuckets(mBuckets, newBuckets, mBucketCount); 5566fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown releaseBuckets(mBuckets, mBucketCount); 5666fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown mBuckets = newBuckets; 5766fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown } 5866fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown} 5966fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 6066fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brownvoid BasicHashtableImpl::setTo(const BasicHashtableImpl& other) { 6166fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown if (mBuckets) { 6266fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown releaseBuckets(mBuckets, mBucketCount); 6366fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown } 6466fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 6566fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown mCapacity = other.mCapacity; 6666fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown mLoadFactor = other.mLoadFactor; 6766fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown mSize = other.mSize; 6866fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown mFilledBuckets = other.mFilledBuckets; 6966fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown mBucketCount = other.mBucketCount; 7066fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown mBuckets = other.mBuckets; 7166fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 7266fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown if (mBuckets) { 7366fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown SharedBuffer::bufferFromData(mBuckets)->acquire(); 7466fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown } 7566fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown} 7666fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 7766fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brownvoid BasicHashtableImpl::clear() { 7866fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown if (mBuckets) { 7966fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown if (mFilledBuckets) { 8066fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown SharedBuffer* sb = SharedBuffer::bufferFromData(mBuckets); 8166fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown if (sb->onlyOwner()) { 8266fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown destroyBuckets(mBuckets, mBucketCount); 838185e47822465a5c7a9cc6e56a11f16996855d79Raph Levien for (size_t i = 0; i < mBucketCount; i++) { 8466fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown Bucket& bucket = bucketAt(mBuckets, i); 8566fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown bucket.cookie = 0; 8666fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown } 8766fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown } else { 8866fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown releaseBuckets(mBuckets, mBucketCount); 8966fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown mBuckets = NULL; 9066fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown } 9166fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown mFilledBuckets = 0; 9266fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown } 9366fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown mSize = 0; 9466fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown } 9566fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown} 9666fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 9766fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brownssize_t BasicHashtableImpl::next(ssize_t index) const { 9866fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown if (mSize) { 9966fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown while (size_t(++index) < mBucketCount) { 10066fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown const Bucket& bucket = bucketAt(mBuckets, index); 10166fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown if (bucket.cookie & Bucket::PRESENT) { 10266fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown return index; 10366fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown } 10466fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown } 10566fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown } 10666fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown return -1; 10766fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown} 10866fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 10966fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brownssize_t BasicHashtableImpl::find(ssize_t index, hash_t hash, 11066fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown const void* __restrict__ key) const { 11166fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown if (!mSize) { 11266fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown return -1; 11366fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown } 11466fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 11566fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown hash = trimHash(hash); 11666fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown if (index < 0) { 11766fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown index = chainStart(hash, mBucketCount); 11866fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 11966fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown const Bucket& bucket = bucketAt(mBuckets, size_t(index)); 12066fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown if (bucket.cookie & Bucket::PRESENT) { 12166fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown if (compareBucketKey(bucket, key)) { 12266fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown return index; 12366fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown } 12466fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown } else { 12566fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown if (!(bucket.cookie & Bucket::COLLISION)) { 12666fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown return -1; 12766fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown } 12866fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown } 12966fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown } 13066fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 13166fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown size_t inc = chainIncrement(hash, mBucketCount); 13266fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown for (;;) { 13366fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown index = chainSeek(index, inc, mBucketCount); 13466fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 13566fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown const Bucket& bucket = bucketAt(mBuckets, size_t(index)); 13666fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown if (bucket.cookie & Bucket::PRESENT) { 13766fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown if ((bucket.cookie & Bucket::HASH_MASK) == hash 13866fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown && compareBucketKey(bucket, key)) { 13966fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown return index; 14066fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown } 14166fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown } 14266fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown if (!(bucket.cookie & Bucket::COLLISION)) { 14366fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown return -1; 14466fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown } 14566fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown } 14666fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown} 14766fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 14866fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brownsize_t BasicHashtableImpl::add(hash_t hash, const void* entry) { 14966fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown if (!mBuckets) { 15066fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown mBuckets = allocateBuckets(mBucketCount); 15166fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown } else { 15266fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown edit(); 15366fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown } 15466fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 15566fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown hash = trimHash(hash); 15666fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown for (;;) { 15766fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown size_t index = chainStart(hash, mBucketCount); 15866fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown Bucket* bucket = &bucketAt(mBuckets, size_t(index)); 15966fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown if (bucket->cookie & Bucket::PRESENT) { 16066fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown size_t inc = chainIncrement(hash, mBucketCount); 16166fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown do { 16266fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown bucket->cookie |= Bucket::COLLISION; 16366fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown index = chainSeek(index, inc, mBucketCount); 16466fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown bucket = &bucketAt(mBuckets, size_t(index)); 16566fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown } while (bucket->cookie & Bucket::PRESENT); 16666fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown } 16766fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 16866fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown uint32_t collision = bucket->cookie & Bucket::COLLISION; 16966fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown if (!collision) { 17066fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown if (mFilledBuckets >= mCapacity) { 17166fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown rehash(mCapacity * 2, mLoadFactor); 17266fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown continue; 17366fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown } 17466fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown mFilledBuckets += 1; 17566fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown } 17666fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 17766fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown bucket->cookie = collision | Bucket::PRESENT | hash; 17866fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown mSize += 1; 17966fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown initializeBucketEntry(*bucket, entry); 18066fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown return index; 18166fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown } 18266fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown} 18366fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 18466fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brownvoid BasicHashtableImpl::removeAt(size_t index) { 18566fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown edit(); 18666fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 18766fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown Bucket& bucket = bucketAt(mBuckets, index); 18866fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown bucket.cookie &= ~Bucket::PRESENT; 18966fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown if (!(bucket.cookie & Bucket::COLLISION)) { 19066fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown mFilledBuckets -= 1; 19166fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown } 19266fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown mSize -= 1; 19366fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown if (!mHasTrivialDestructor) { 19466fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown destroyBucketEntry(bucket); 19566fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown } 19666fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown} 19766fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 19866fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brownvoid BasicHashtableImpl::rehash(size_t minimumCapacity, float loadFactor) { 19966fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown if (minimumCapacity < mSize) { 20066fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown minimumCapacity = mSize; 20166fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown } 20266fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown size_t newBucketCount, newCapacity; 20366fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown determineCapacity(minimumCapacity, loadFactor, &newBucketCount, &newCapacity); 20466fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 20566fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown if (newBucketCount != mBucketCount || newCapacity != mCapacity) { 20666fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown if (mBuckets) { 20766fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown void* newBuckets; 20866fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown if (mSize) { 20966fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown newBuckets = allocateBuckets(newBucketCount); 21066fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown for (size_t i = 0; i < mBucketCount; i++) { 21166fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown const Bucket& fromBucket = bucketAt(mBuckets, i); 21266fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown if (fromBucket.cookie & Bucket::PRESENT) { 21366fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown hash_t hash = fromBucket.cookie & Bucket::HASH_MASK; 21466fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown size_t index = chainStart(hash, newBucketCount); 21566fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown Bucket* toBucket = &bucketAt(newBuckets, size_t(index)); 21666fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown if (toBucket->cookie & Bucket::PRESENT) { 21766fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown size_t inc = chainIncrement(hash, newBucketCount); 21866fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown do { 21966fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown toBucket->cookie |= Bucket::COLLISION; 22066fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown index = chainSeek(index, inc, newBucketCount); 22166fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown toBucket = &bucketAt(newBuckets, size_t(index)); 22266fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown } while (toBucket->cookie & Bucket::PRESENT); 22366fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown } 22466fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown toBucket->cookie = Bucket::PRESENT | hash; 22566fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown initializeBucketEntry(*toBucket, fromBucket.entry); 22666fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown } 22766fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown } 22866fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown } else { 22966fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown newBuckets = NULL; 23066fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown } 23166fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown releaseBuckets(mBuckets, mBucketCount); 23266fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown mBuckets = newBuckets; 23366fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown mFilledBuckets = mSize; 23466fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown } 23566fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown mBucketCount = newBucketCount; 23666fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown mCapacity = newCapacity; 23766fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown } 23866fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown mLoadFactor = loadFactor; 23966fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown} 24066fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 24166fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brownvoid* BasicHashtableImpl::allocateBuckets(size_t count) const { 24266fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown size_t bytes = count * mBucketSize; 24366fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown SharedBuffer* sb = SharedBuffer::alloc(bytes); 24466fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown LOG_ALWAYS_FATAL_IF(!sb, "Could not allocate %u bytes for hashtable with %u buckets.", 24566fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown uint32_t(bytes), uint32_t(count)); 24666fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown void* buckets = sb->data(); 24766fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown for (size_t i = 0; i < count; i++) { 24866fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown Bucket& bucket = bucketAt(buckets, i); 24966fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown bucket.cookie = 0; 25066fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown } 25166fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown return buckets; 25266fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown} 25366fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 25466fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brownvoid BasicHashtableImpl::releaseBuckets(void* __restrict__ buckets, size_t count) const { 25566fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown SharedBuffer* sb = SharedBuffer::bufferFromData(buckets); 25666fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown if (sb->release(SharedBuffer::eKeepStorage) == 1) { 25766fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown destroyBuckets(buckets, count); 25866fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown SharedBuffer::dealloc(sb); 25966fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown } 26066fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown} 26166fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 26266fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brownvoid BasicHashtableImpl::destroyBuckets(void* __restrict__ buckets, size_t count) const { 26366fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown if (!mHasTrivialDestructor) { 26466fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown for (size_t i = 0; i < count; i++) { 26566fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown Bucket& bucket = bucketAt(buckets, i); 26666fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown if (bucket.cookie & Bucket::PRESENT) { 26766fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown destroyBucketEntry(bucket); 26866fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown } 26966fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown } 27066fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown } 27166fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown} 27266fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 27366fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brownvoid BasicHashtableImpl::copyBuckets(const void* __restrict__ fromBuckets, 27466fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown void* __restrict__ toBuckets, size_t count) const { 27566fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown for (size_t i = 0; i < count; i++) { 27666fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown const Bucket& fromBucket = bucketAt(fromBuckets, i); 27766fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown Bucket& toBucket = bucketAt(toBuckets, i); 27866fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown toBucket.cookie = fromBucket.cookie; 27966fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown if (fromBucket.cookie & Bucket::PRESENT) { 28066fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown initializeBucketEntry(toBucket, fromBucket.entry); 28166fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown } 28266fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown } 28366fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown} 28466fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 28566fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown// Table of 31-bit primes where each prime is no less than twice as large 28666fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown// as the previous one. Generated by "primes.py". 28766fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brownstatic size_t PRIMES[] = { 28866fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 5, 28966fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 11, 29066fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 23, 29166fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 47, 29266fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 97, 29366fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 197, 29466fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 397, 29566fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 797, 29666fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 1597, 29766fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 3203, 29866fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 6421, 29966fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 12853, 30066fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 25717, 30166fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 51437, 30266fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 102877, 30366fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 205759, 30466fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 411527, 30566fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 823117, 30666fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 1646237, 30766fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 3292489, 30866fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 6584983, 30966fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 13169977, 31066fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 26339969, 31166fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 52679969, 31266fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 105359939, 31366fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 210719881, 31466fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 421439783, 31566fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 842879579, 31666fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 1685759167, 31766fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 0, 31866fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown}; 31966fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 32066fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brownvoid BasicHashtableImpl::determineCapacity(size_t minimumCapacity, float loadFactor, 32166fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown size_t* __restrict__ outBucketCount, size_t* __restrict__ outCapacity) { 32266fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown LOG_ALWAYS_FATAL_IF(loadFactor <= 0.0f || loadFactor > 1.0f, 32366fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown "Invalid load factor %0.3f. Must be in the range (0, 1].", loadFactor); 32466fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 32566fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown size_t count = ceilf(minimumCapacity / loadFactor) + 1; 32666fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown size_t i = 0; 32766fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown while (count > PRIMES[i] && i < NELEM(PRIMES)) { 32866fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown i++; 32966fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown } 33066fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown count = PRIMES[i]; 33166fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown LOG_ALWAYS_FATAL_IF(!count, "Could not determine required number of buckets for " 33266fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown "hashtable with minimum capacity %u and load factor %0.3f.", 33366fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown uint32_t(minimumCapacity), loadFactor); 33466fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown *outBucketCount = count; 33566fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown *outCapacity = ceilf((count - 1) * loadFactor); 33666fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown} 33766fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown 33866fbde305047b7a606d083a9ec8994fa693cc7d7Jeff Brown}; // namespace android 339