1e735f23018b398f45bd052b63616d7a45e29515bJeff Brown/* 2e735f23018b398f45bd052b63616d7a45e29515bJeff Brown * Copyright (C) 2011 The Android Open Source Project 3e735f23018b398f45bd052b63616d7a45e29515bJeff Brown * 4e735f23018b398f45bd052b63616d7a45e29515bJeff Brown * Licensed under the Apache License, Version 2.0 (the "License"); 5e735f23018b398f45bd052b63616d7a45e29515bJeff Brown * you may not use this file except in compliance with the License. 6e735f23018b398f45bd052b63616d7a45e29515bJeff Brown * You may obtain a copy of the License at 7e735f23018b398f45bd052b63616d7a45e29515bJeff Brown * 8e735f23018b398f45bd052b63616d7a45e29515bJeff Brown * http://www.apache.org/licenses/LICENSE-2.0 9e735f23018b398f45bd052b63616d7a45e29515bJeff Brown * 10e735f23018b398f45bd052b63616d7a45e29515bJeff Brown * Unless required by applicable law or agreed to in writing, software 11e735f23018b398f45bd052b63616d7a45e29515bJeff Brown * distributed under the License is distributed on an "AS IS" BASIS, 12e735f23018b398f45bd052b63616d7a45e29515bJeff Brown * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13e735f23018b398f45bd052b63616d7a45e29515bJeff Brown * See the License for the specific language governing permissions and 14e735f23018b398f45bd052b63616d7a45e29515bJeff Brown * limitations under the License. 15e735f23018b398f45bd052b63616d7a45e29515bJeff Brown */ 16e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 17e735f23018b398f45bd052b63616d7a45e29515bJeff Brown#define LOG_TAG "BasicHashtable" 18e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 19e735f23018b398f45bd052b63616d7a45e29515bJeff Brown#include <math.h> 20e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 21e735f23018b398f45bd052b63616d7a45e29515bJeff Brown#include <utils/Log.h> 22e735f23018b398f45bd052b63616d7a45e29515bJeff Brown#include <utils/BasicHashtable.h> 23e735f23018b398f45bd052b63616d7a45e29515bJeff Brown#include <utils/misc.h> 24e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 25e735f23018b398f45bd052b63616d7a45e29515bJeff Brownnamespace android { 26e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 27e735f23018b398f45bd052b63616d7a45e29515bJeff BrownBasicHashtableImpl::BasicHashtableImpl(size_t entrySize, bool hasTrivialDestructor, 28e735f23018b398f45bd052b63616d7a45e29515bJeff Brown size_t minimumInitialCapacity, float loadFactor) : 29e735f23018b398f45bd052b63616d7a45e29515bJeff Brown mBucketSize(entrySize + sizeof(Bucket)), mHasTrivialDestructor(hasTrivialDestructor), 30e735f23018b398f45bd052b63616d7a45e29515bJeff Brown mLoadFactor(loadFactor), mSize(0), 31e735f23018b398f45bd052b63616d7a45e29515bJeff Brown mFilledBuckets(0), mBuckets(NULL) { 32e735f23018b398f45bd052b63616d7a45e29515bJeff Brown determineCapacity(minimumInitialCapacity, mLoadFactor, &mBucketCount, &mCapacity); 33e735f23018b398f45bd052b63616d7a45e29515bJeff Brown} 34e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 35e735f23018b398f45bd052b63616d7a45e29515bJeff BrownBasicHashtableImpl::BasicHashtableImpl(const BasicHashtableImpl& other) : 36e735f23018b398f45bd052b63616d7a45e29515bJeff Brown mBucketSize(other.mBucketSize), mHasTrivialDestructor(other.mHasTrivialDestructor), 37e735f23018b398f45bd052b63616d7a45e29515bJeff Brown mCapacity(other.mCapacity), mLoadFactor(other.mLoadFactor), 38e735f23018b398f45bd052b63616d7a45e29515bJeff Brown mSize(other.mSize), mFilledBuckets(other.mFilledBuckets), 39e735f23018b398f45bd052b63616d7a45e29515bJeff Brown mBucketCount(other.mBucketCount), mBuckets(other.mBuckets) { 40e735f23018b398f45bd052b63616d7a45e29515bJeff Brown if (mBuckets) { 41e735f23018b398f45bd052b63616d7a45e29515bJeff Brown SharedBuffer::bufferFromData(mBuckets)->acquire(); 42e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 43e735f23018b398f45bd052b63616d7a45e29515bJeff Brown} 44e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 450d8f3d6c452883ab7295573c4ff7437d68d1d936Alex RayBasicHashtableImpl::~BasicHashtableImpl() 460d8f3d6c452883ab7295573c4ff7437d68d1d936Alex Ray{ 470d8f3d6c452883ab7295573c4ff7437d68d1d936Alex Ray} 480d8f3d6c452883ab7295573c4ff7437d68d1d936Alex Ray 49e735f23018b398f45bd052b63616d7a45e29515bJeff Brownvoid BasicHashtableImpl::dispose() { 50e735f23018b398f45bd052b63616d7a45e29515bJeff Brown if (mBuckets) { 51e735f23018b398f45bd052b63616d7a45e29515bJeff Brown releaseBuckets(mBuckets, mBucketCount); 52e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 53e735f23018b398f45bd052b63616d7a45e29515bJeff Brown} 54e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 55e735f23018b398f45bd052b63616d7a45e29515bJeff Brownvoid BasicHashtableImpl::clone() { 56e735f23018b398f45bd052b63616d7a45e29515bJeff Brown if (mBuckets) { 57e735f23018b398f45bd052b63616d7a45e29515bJeff Brown void* newBuckets = allocateBuckets(mBucketCount); 58e735f23018b398f45bd052b63616d7a45e29515bJeff Brown copyBuckets(mBuckets, newBuckets, mBucketCount); 59e735f23018b398f45bd052b63616d7a45e29515bJeff Brown releaseBuckets(mBuckets, mBucketCount); 60e735f23018b398f45bd052b63616d7a45e29515bJeff Brown mBuckets = newBuckets; 61e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 62e735f23018b398f45bd052b63616d7a45e29515bJeff Brown} 63e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 64e735f23018b398f45bd052b63616d7a45e29515bJeff Brownvoid BasicHashtableImpl::setTo(const BasicHashtableImpl& other) { 65e735f23018b398f45bd052b63616d7a45e29515bJeff Brown if (mBuckets) { 66e735f23018b398f45bd052b63616d7a45e29515bJeff Brown releaseBuckets(mBuckets, mBucketCount); 67e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 68e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 69e735f23018b398f45bd052b63616d7a45e29515bJeff Brown mCapacity = other.mCapacity; 70e735f23018b398f45bd052b63616d7a45e29515bJeff Brown mLoadFactor = other.mLoadFactor; 71e735f23018b398f45bd052b63616d7a45e29515bJeff Brown mSize = other.mSize; 72e735f23018b398f45bd052b63616d7a45e29515bJeff Brown mFilledBuckets = other.mFilledBuckets; 73e735f23018b398f45bd052b63616d7a45e29515bJeff Brown mBucketCount = other.mBucketCount; 74e735f23018b398f45bd052b63616d7a45e29515bJeff Brown mBuckets = other.mBuckets; 75e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 76e735f23018b398f45bd052b63616d7a45e29515bJeff Brown if (mBuckets) { 77e735f23018b398f45bd052b63616d7a45e29515bJeff Brown SharedBuffer::bufferFromData(mBuckets)->acquire(); 78e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 79e735f23018b398f45bd052b63616d7a45e29515bJeff Brown} 80e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 81e735f23018b398f45bd052b63616d7a45e29515bJeff Brownvoid BasicHashtableImpl::clear() { 82e735f23018b398f45bd052b63616d7a45e29515bJeff Brown if (mBuckets) { 83e735f23018b398f45bd052b63616d7a45e29515bJeff Brown if (mFilledBuckets) { 84e735f23018b398f45bd052b63616d7a45e29515bJeff Brown SharedBuffer* sb = SharedBuffer::bufferFromData(mBuckets); 85e735f23018b398f45bd052b63616d7a45e29515bJeff Brown if (sb->onlyOwner()) { 86e735f23018b398f45bd052b63616d7a45e29515bJeff Brown destroyBuckets(mBuckets, mBucketCount); 87b6ea175b6b4d0aaac85ed6cd8ccac01ab896486bRaph Levien for (size_t i = 0; i < mBucketCount; i++) { 88e735f23018b398f45bd052b63616d7a45e29515bJeff Brown Bucket& bucket = bucketAt(mBuckets, i); 89e735f23018b398f45bd052b63616d7a45e29515bJeff Brown bucket.cookie = 0; 90e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 91e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } else { 92e735f23018b398f45bd052b63616d7a45e29515bJeff Brown releaseBuckets(mBuckets, mBucketCount); 93e735f23018b398f45bd052b63616d7a45e29515bJeff Brown mBuckets = NULL; 94e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 95e735f23018b398f45bd052b63616d7a45e29515bJeff Brown mFilledBuckets = 0; 96e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 97e735f23018b398f45bd052b63616d7a45e29515bJeff Brown mSize = 0; 98e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 99e735f23018b398f45bd052b63616d7a45e29515bJeff Brown} 100e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 101e735f23018b398f45bd052b63616d7a45e29515bJeff Brownssize_t BasicHashtableImpl::next(ssize_t index) const { 102e735f23018b398f45bd052b63616d7a45e29515bJeff Brown if (mSize) { 103e735f23018b398f45bd052b63616d7a45e29515bJeff Brown while (size_t(++index) < mBucketCount) { 104e735f23018b398f45bd052b63616d7a45e29515bJeff Brown const Bucket& bucket = bucketAt(mBuckets, index); 105e735f23018b398f45bd052b63616d7a45e29515bJeff Brown if (bucket.cookie & Bucket::PRESENT) { 106e735f23018b398f45bd052b63616d7a45e29515bJeff Brown return index; 107e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 108e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 109e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 110e735f23018b398f45bd052b63616d7a45e29515bJeff Brown return -1; 111e735f23018b398f45bd052b63616d7a45e29515bJeff Brown} 112e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 113e735f23018b398f45bd052b63616d7a45e29515bJeff Brownssize_t BasicHashtableImpl::find(ssize_t index, hash_t hash, 114e735f23018b398f45bd052b63616d7a45e29515bJeff Brown const void* __restrict__ key) const { 115e735f23018b398f45bd052b63616d7a45e29515bJeff Brown if (!mSize) { 116e735f23018b398f45bd052b63616d7a45e29515bJeff Brown return -1; 117e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 118e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 119e735f23018b398f45bd052b63616d7a45e29515bJeff Brown hash = trimHash(hash); 120e735f23018b398f45bd052b63616d7a45e29515bJeff Brown if (index < 0) { 121e735f23018b398f45bd052b63616d7a45e29515bJeff Brown index = chainStart(hash, mBucketCount); 122e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 123e735f23018b398f45bd052b63616d7a45e29515bJeff Brown const Bucket& bucket = bucketAt(mBuckets, size_t(index)); 124e735f23018b398f45bd052b63616d7a45e29515bJeff Brown if (bucket.cookie & Bucket::PRESENT) { 125e735f23018b398f45bd052b63616d7a45e29515bJeff Brown if (compareBucketKey(bucket, key)) { 126e735f23018b398f45bd052b63616d7a45e29515bJeff Brown return index; 127e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 128e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } else { 129e735f23018b398f45bd052b63616d7a45e29515bJeff Brown if (!(bucket.cookie & Bucket::COLLISION)) { 130e735f23018b398f45bd052b63616d7a45e29515bJeff Brown return -1; 131e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 132e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 133e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 134e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 135e735f23018b398f45bd052b63616d7a45e29515bJeff Brown size_t inc = chainIncrement(hash, mBucketCount); 136e735f23018b398f45bd052b63616d7a45e29515bJeff Brown for (;;) { 137e735f23018b398f45bd052b63616d7a45e29515bJeff Brown index = chainSeek(index, inc, mBucketCount); 138e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 139e735f23018b398f45bd052b63616d7a45e29515bJeff Brown const Bucket& bucket = bucketAt(mBuckets, size_t(index)); 140e735f23018b398f45bd052b63616d7a45e29515bJeff Brown if (bucket.cookie & Bucket::PRESENT) { 141e735f23018b398f45bd052b63616d7a45e29515bJeff Brown if ((bucket.cookie & Bucket::HASH_MASK) == hash 142e735f23018b398f45bd052b63616d7a45e29515bJeff Brown && compareBucketKey(bucket, key)) { 143e735f23018b398f45bd052b63616d7a45e29515bJeff Brown return index; 144e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 145e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 146e735f23018b398f45bd052b63616d7a45e29515bJeff Brown if (!(bucket.cookie & Bucket::COLLISION)) { 147e735f23018b398f45bd052b63616d7a45e29515bJeff Brown return -1; 148e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 149e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 150e735f23018b398f45bd052b63616d7a45e29515bJeff Brown} 151e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 152e735f23018b398f45bd052b63616d7a45e29515bJeff Brownsize_t BasicHashtableImpl::add(hash_t hash, const void* entry) { 153e735f23018b398f45bd052b63616d7a45e29515bJeff Brown if (!mBuckets) { 154e735f23018b398f45bd052b63616d7a45e29515bJeff Brown mBuckets = allocateBuckets(mBucketCount); 155e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } else { 156e735f23018b398f45bd052b63616d7a45e29515bJeff Brown edit(); 157e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 158e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 159e735f23018b398f45bd052b63616d7a45e29515bJeff Brown hash = trimHash(hash); 160e735f23018b398f45bd052b63616d7a45e29515bJeff Brown for (;;) { 161e735f23018b398f45bd052b63616d7a45e29515bJeff Brown size_t index = chainStart(hash, mBucketCount); 162e735f23018b398f45bd052b63616d7a45e29515bJeff Brown Bucket* bucket = &bucketAt(mBuckets, size_t(index)); 163e735f23018b398f45bd052b63616d7a45e29515bJeff Brown if (bucket->cookie & Bucket::PRESENT) { 164e735f23018b398f45bd052b63616d7a45e29515bJeff Brown size_t inc = chainIncrement(hash, mBucketCount); 165e735f23018b398f45bd052b63616d7a45e29515bJeff Brown do { 166e735f23018b398f45bd052b63616d7a45e29515bJeff Brown bucket->cookie |= Bucket::COLLISION; 167e735f23018b398f45bd052b63616d7a45e29515bJeff Brown index = chainSeek(index, inc, mBucketCount); 168e735f23018b398f45bd052b63616d7a45e29515bJeff Brown bucket = &bucketAt(mBuckets, size_t(index)); 169e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } while (bucket->cookie & Bucket::PRESENT); 170e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 171e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 172e735f23018b398f45bd052b63616d7a45e29515bJeff Brown uint32_t collision = bucket->cookie & Bucket::COLLISION; 173e735f23018b398f45bd052b63616d7a45e29515bJeff Brown if (!collision) { 174e735f23018b398f45bd052b63616d7a45e29515bJeff Brown if (mFilledBuckets >= mCapacity) { 175e735f23018b398f45bd052b63616d7a45e29515bJeff Brown rehash(mCapacity * 2, mLoadFactor); 176e735f23018b398f45bd052b63616d7a45e29515bJeff Brown continue; 177e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 178e735f23018b398f45bd052b63616d7a45e29515bJeff Brown mFilledBuckets += 1; 179e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 180e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 181e735f23018b398f45bd052b63616d7a45e29515bJeff Brown bucket->cookie = collision | Bucket::PRESENT | hash; 182e735f23018b398f45bd052b63616d7a45e29515bJeff Brown mSize += 1; 183e735f23018b398f45bd052b63616d7a45e29515bJeff Brown initializeBucketEntry(*bucket, entry); 184e735f23018b398f45bd052b63616d7a45e29515bJeff Brown return index; 185e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 186e735f23018b398f45bd052b63616d7a45e29515bJeff Brown} 187e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 188e735f23018b398f45bd052b63616d7a45e29515bJeff Brownvoid BasicHashtableImpl::removeAt(size_t index) { 189e735f23018b398f45bd052b63616d7a45e29515bJeff Brown edit(); 190e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 191e735f23018b398f45bd052b63616d7a45e29515bJeff Brown Bucket& bucket = bucketAt(mBuckets, index); 192e735f23018b398f45bd052b63616d7a45e29515bJeff Brown bucket.cookie &= ~Bucket::PRESENT; 193e735f23018b398f45bd052b63616d7a45e29515bJeff Brown if (!(bucket.cookie & Bucket::COLLISION)) { 194e735f23018b398f45bd052b63616d7a45e29515bJeff Brown mFilledBuckets -= 1; 195e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 196e735f23018b398f45bd052b63616d7a45e29515bJeff Brown mSize -= 1; 197e735f23018b398f45bd052b63616d7a45e29515bJeff Brown if (!mHasTrivialDestructor) { 198e735f23018b398f45bd052b63616d7a45e29515bJeff Brown destroyBucketEntry(bucket); 199e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 200e735f23018b398f45bd052b63616d7a45e29515bJeff Brown} 201e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 202e735f23018b398f45bd052b63616d7a45e29515bJeff Brownvoid BasicHashtableImpl::rehash(size_t minimumCapacity, float loadFactor) { 203e735f23018b398f45bd052b63616d7a45e29515bJeff Brown if (minimumCapacity < mSize) { 204e735f23018b398f45bd052b63616d7a45e29515bJeff Brown minimumCapacity = mSize; 205e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 206e735f23018b398f45bd052b63616d7a45e29515bJeff Brown size_t newBucketCount, newCapacity; 207e735f23018b398f45bd052b63616d7a45e29515bJeff Brown determineCapacity(minimumCapacity, loadFactor, &newBucketCount, &newCapacity); 208e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 209e735f23018b398f45bd052b63616d7a45e29515bJeff Brown if (newBucketCount != mBucketCount || newCapacity != mCapacity) { 210e735f23018b398f45bd052b63616d7a45e29515bJeff Brown if (mBuckets) { 211e735f23018b398f45bd052b63616d7a45e29515bJeff Brown void* newBuckets; 212e735f23018b398f45bd052b63616d7a45e29515bJeff Brown if (mSize) { 213e735f23018b398f45bd052b63616d7a45e29515bJeff Brown newBuckets = allocateBuckets(newBucketCount); 214e735f23018b398f45bd052b63616d7a45e29515bJeff Brown for (size_t i = 0; i < mBucketCount; i++) { 215e735f23018b398f45bd052b63616d7a45e29515bJeff Brown const Bucket& fromBucket = bucketAt(mBuckets, i); 216e735f23018b398f45bd052b63616d7a45e29515bJeff Brown if (fromBucket.cookie & Bucket::PRESENT) { 217e735f23018b398f45bd052b63616d7a45e29515bJeff Brown hash_t hash = fromBucket.cookie & Bucket::HASH_MASK; 218e735f23018b398f45bd052b63616d7a45e29515bJeff Brown size_t index = chainStart(hash, newBucketCount); 219e735f23018b398f45bd052b63616d7a45e29515bJeff Brown Bucket* toBucket = &bucketAt(newBuckets, size_t(index)); 220e735f23018b398f45bd052b63616d7a45e29515bJeff Brown if (toBucket->cookie & Bucket::PRESENT) { 221e735f23018b398f45bd052b63616d7a45e29515bJeff Brown size_t inc = chainIncrement(hash, newBucketCount); 222e735f23018b398f45bd052b63616d7a45e29515bJeff Brown do { 223e735f23018b398f45bd052b63616d7a45e29515bJeff Brown toBucket->cookie |= Bucket::COLLISION; 224e735f23018b398f45bd052b63616d7a45e29515bJeff Brown index = chainSeek(index, inc, newBucketCount); 225e735f23018b398f45bd052b63616d7a45e29515bJeff Brown toBucket = &bucketAt(newBuckets, size_t(index)); 226e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } while (toBucket->cookie & Bucket::PRESENT); 227e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 228e735f23018b398f45bd052b63616d7a45e29515bJeff Brown toBucket->cookie = Bucket::PRESENT | hash; 229e735f23018b398f45bd052b63616d7a45e29515bJeff Brown initializeBucketEntry(*toBucket, fromBucket.entry); 230e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 231e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 232e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } else { 233e735f23018b398f45bd052b63616d7a45e29515bJeff Brown newBuckets = NULL; 234e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 235e735f23018b398f45bd052b63616d7a45e29515bJeff Brown releaseBuckets(mBuckets, mBucketCount); 236e735f23018b398f45bd052b63616d7a45e29515bJeff Brown mBuckets = newBuckets; 237e735f23018b398f45bd052b63616d7a45e29515bJeff Brown mFilledBuckets = mSize; 238e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 239e735f23018b398f45bd052b63616d7a45e29515bJeff Brown mBucketCount = newBucketCount; 240e735f23018b398f45bd052b63616d7a45e29515bJeff Brown mCapacity = newCapacity; 241e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 242e735f23018b398f45bd052b63616d7a45e29515bJeff Brown mLoadFactor = loadFactor; 243e735f23018b398f45bd052b63616d7a45e29515bJeff Brown} 244e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 245e735f23018b398f45bd052b63616d7a45e29515bJeff Brownvoid* BasicHashtableImpl::allocateBuckets(size_t count) const { 246e735f23018b398f45bd052b63616d7a45e29515bJeff Brown size_t bytes = count * mBucketSize; 247e735f23018b398f45bd052b63616d7a45e29515bJeff Brown SharedBuffer* sb = SharedBuffer::alloc(bytes); 248e735f23018b398f45bd052b63616d7a45e29515bJeff Brown LOG_ALWAYS_FATAL_IF(!sb, "Could not allocate %u bytes for hashtable with %u buckets.", 249e735f23018b398f45bd052b63616d7a45e29515bJeff Brown uint32_t(bytes), uint32_t(count)); 250e735f23018b398f45bd052b63616d7a45e29515bJeff Brown void* buckets = sb->data(); 251e735f23018b398f45bd052b63616d7a45e29515bJeff Brown for (size_t i = 0; i < count; i++) { 252e735f23018b398f45bd052b63616d7a45e29515bJeff Brown Bucket& bucket = bucketAt(buckets, i); 253e735f23018b398f45bd052b63616d7a45e29515bJeff Brown bucket.cookie = 0; 254e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 255e735f23018b398f45bd052b63616d7a45e29515bJeff Brown return buckets; 256e735f23018b398f45bd052b63616d7a45e29515bJeff Brown} 257e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 258e735f23018b398f45bd052b63616d7a45e29515bJeff Brownvoid BasicHashtableImpl::releaseBuckets(void* __restrict__ buckets, size_t count) const { 259e735f23018b398f45bd052b63616d7a45e29515bJeff Brown SharedBuffer* sb = SharedBuffer::bufferFromData(buckets); 260e735f23018b398f45bd052b63616d7a45e29515bJeff Brown if (sb->release(SharedBuffer::eKeepStorage) == 1) { 261e735f23018b398f45bd052b63616d7a45e29515bJeff Brown destroyBuckets(buckets, count); 262e735f23018b398f45bd052b63616d7a45e29515bJeff Brown SharedBuffer::dealloc(sb); 263e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 264e735f23018b398f45bd052b63616d7a45e29515bJeff Brown} 265e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 266e735f23018b398f45bd052b63616d7a45e29515bJeff Brownvoid BasicHashtableImpl::destroyBuckets(void* __restrict__ buckets, size_t count) const { 267e735f23018b398f45bd052b63616d7a45e29515bJeff Brown if (!mHasTrivialDestructor) { 268e735f23018b398f45bd052b63616d7a45e29515bJeff Brown for (size_t i = 0; i < count; i++) { 269e735f23018b398f45bd052b63616d7a45e29515bJeff Brown Bucket& bucket = bucketAt(buckets, i); 270e735f23018b398f45bd052b63616d7a45e29515bJeff Brown if (bucket.cookie & Bucket::PRESENT) { 271e735f23018b398f45bd052b63616d7a45e29515bJeff Brown destroyBucketEntry(bucket); 272e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 273e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 274e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 275e735f23018b398f45bd052b63616d7a45e29515bJeff Brown} 276e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 277e735f23018b398f45bd052b63616d7a45e29515bJeff Brownvoid BasicHashtableImpl::copyBuckets(const void* __restrict__ fromBuckets, 278e735f23018b398f45bd052b63616d7a45e29515bJeff Brown void* __restrict__ toBuckets, size_t count) const { 279e735f23018b398f45bd052b63616d7a45e29515bJeff Brown for (size_t i = 0; i < count; i++) { 280e735f23018b398f45bd052b63616d7a45e29515bJeff Brown const Bucket& fromBucket = bucketAt(fromBuckets, i); 281e735f23018b398f45bd052b63616d7a45e29515bJeff Brown Bucket& toBucket = bucketAt(toBuckets, i); 282e735f23018b398f45bd052b63616d7a45e29515bJeff Brown toBucket.cookie = fromBucket.cookie; 283e735f23018b398f45bd052b63616d7a45e29515bJeff Brown if (fromBucket.cookie & Bucket::PRESENT) { 284e735f23018b398f45bd052b63616d7a45e29515bJeff Brown initializeBucketEntry(toBucket, fromBucket.entry); 285e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 286e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 287e735f23018b398f45bd052b63616d7a45e29515bJeff Brown} 288e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 289e735f23018b398f45bd052b63616d7a45e29515bJeff Brown// Table of 31-bit primes where each prime is no less than twice as large 290e735f23018b398f45bd052b63616d7a45e29515bJeff Brown// as the previous one. Generated by "primes.py". 291e735f23018b398f45bd052b63616d7a45e29515bJeff Brownstatic size_t PRIMES[] = { 292e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 5, 293e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 11, 294e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 23, 295e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 47, 296e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 97, 297e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 197, 298e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 397, 299e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 797, 300e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 1597, 301e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 3203, 302e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 6421, 303e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 12853, 304e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 25717, 305e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 51437, 306e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 102877, 307e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 205759, 308e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 411527, 309e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 823117, 310e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 1646237, 311e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 3292489, 312e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 6584983, 313e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 13169977, 314e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 26339969, 315e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 52679969, 316e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 105359939, 317e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 210719881, 318e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 421439783, 319e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 842879579, 320e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 1685759167, 321e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 0, 322e735f23018b398f45bd052b63616d7a45e29515bJeff Brown}; 323e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 324e735f23018b398f45bd052b63616d7a45e29515bJeff Brownvoid BasicHashtableImpl::determineCapacity(size_t minimumCapacity, float loadFactor, 325e735f23018b398f45bd052b63616d7a45e29515bJeff Brown size_t* __restrict__ outBucketCount, size_t* __restrict__ outCapacity) { 326e735f23018b398f45bd052b63616d7a45e29515bJeff Brown LOG_ALWAYS_FATAL_IF(loadFactor <= 0.0f || loadFactor > 1.0f, 327e735f23018b398f45bd052b63616d7a45e29515bJeff Brown "Invalid load factor %0.3f. Must be in the range (0, 1].", loadFactor); 328e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 329e735f23018b398f45bd052b63616d7a45e29515bJeff Brown size_t count = ceilf(minimumCapacity / loadFactor) + 1; 330e735f23018b398f45bd052b63616d7a45e29515bJeff Brown size_t i = 0; 331e735f23018b398f45bd052b63616d7a45e29515bJeff Brown while (count > PRIMES[i] && i < NELEM(PRIMES)) { 332e735f23018b398f45bd052b63616d7a45e29515bJeff Brown i++; 333e735f23018b398f45bd052b63616d7a45e29515bJeff Brown } 334e735f23018b398f45bd052b63616d7a45e29515bJeff Brown count = PRIMES[i]; 335e735f23018b398f45bd052b63616d7a45e29515bJeff Brown LOG_ALWAYS_FATAL_IF(!count, "Could not determine required number of buckets for " 336e735f23018b398f45bd052b63616d7a45e29515bJeff Brown "hashtable with minimum capacity %u and load factor %0.3f.", 337e735f23018b398f45bd052b63616d7a45e29515bJeff Brown uint32_t(minimumCapacity), loadFactor); 338e735f23018b398f45bd052b63616d7a45e29515bJeff Brown *outBucketCount = count; 339e735f23018b398f45bd052b63616d7a45e29515bJeff Brown *outCapacity = ceilf((count - 1) * loadFactor); 340e735f23018b398f45bd052b63616d7a45e29515bJeff Brown} 341e735f23018b398f45bd052b63616d7a45e29515bJeff Brown 342e735f23018b398f45bd052b63616d7a45e29515bJeff Brown}; // namespace android 343