diff --git a/libs/utils/BasicHashtable.cpp b/libs/utils/BasicHashtable.cpp
new file mode 100644
index 0000000..fb8ec9f
--- /dev/null
+++ b/libs/utils/BasicHashtable.cpp
@@ -0,0 +1,338 @@
+/*
+ * 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();
+    }
+}
+
+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 < mSize; 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