move libs/utils to libutils

Change-Id: I6cf4268599460791414882f91eeb88a992fbd29d

1 files changed, 0 insertions, 342 deletions

diff --git a/libs/utils/BasicHashtable.cpp b/libs/utils/BasicHashtable.cpp
deleted file mode 100644
index 491d9e9..0000000
--- a/libs/utils/BasicHashtable.cpp
+++ /dev/null
@@ -1,342 +0,0 @@
-/*
- * 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