libutils/BasicHashtable.cpp

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