libutils/BasicHashtable.cpp - android-core - Git at Google

 /*
  * 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
	/*
	* 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