diff --git a/include/utils/BasicHashtable.h b/include/utils/BasicHashtable.h
index fdf9738..7a6c96c 100644
--- a/include/utils/BasicHashtable.h
+++ b/include/utils/BasicHashtable.h
@@ -328,6 +328,14 @@
         BasicHashtableImpl::rehash(minimumCapacity, loadFactor);
     }
 
+    /* Determines whether there is room to add another entry without rehashing.
+     * When this returns true, a subsequent add() operation is guaranteed to
+     * complete without performing a rehash.
+     */
+    inline bool hasMoreRoom() const {
+        return mCapacity > mFilledBuckets;
+    }
+
 protected:
     static inline const TEntry& entryFor(const Bucket& bucket) {
         return reinterpret_cast<const TEntry&>(bucket.entry);
diff --git a/include/utils/JenkinsHash.h b/include/utils/JenkinsHash.h
new file mode 100644
index 0000000..e964e6f
--- /dev/null
+++ b/include/utils/JenkinsHash.h
@@ -0,0 +1,44 @@
+/*
+ * Copyright (C) 2012 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.
+ */
+
+/* Implementation of Jenkins one-at-a-time hash function. These choices are
+ * optimized for code size and portability, rather than raw speed. But speed
+ * should still be quite good.
+ **/
+
+#include <utils/TypeHelpers.h>
+
+namespace android {
+
+/* The Jenkins hash of a sequence of 32 bit words A, B, C is:
+ * Whiten(Mix(Mix(Mix(0, A), B), C)) */
+
+inline uint32_t JenkinsHashMix(uint32_t hash, uint32_t data) {
+    hash += data;
+    hash += (hash << 10);
+    hash ^= (hash >> 6);
+    return hash;
+}
+
+hash_t JenkinsHashWhiten(uint32_t hash);
+
+/* Helpful utility functions for hashing data in 32 bit chunks */
+uint32_t JenkinsHashMixBytes(uint32_t hash, const uint8_t* bytes, size_t size);
+
+uint32_t JenkinsHashMixShorts(uint32_t hash, const uint16_t* shorts, size_t size);
+
+}
+
diff --git a/include/utils/LruCache.h b/include/utils/LruCache.h
new file mode 100644
index 0000000..af39315
--- /dev/null
+++ b/include/utils/LruCache.h
@@ -0,0 +1,199 @@
+/*
+ * Copyright (C) 2012 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.
+ */
+
+#include <utils/BasicHashtable.h>
+#include <utils/GenerationCache.h>
+#include <utils/UniquePtr.h>
+
+namespace android {
+
+// OnEntryRemoved is defined in GenerationCache.h, but maybe should move here.
+
+template <typename TKey, typename TValue>
+class LruCache {
+public:
+    explicit LruCache(uint32_t maxCapacity);
+
+    enum Capacity {
+        kUnlimitedCapacity,
+    };
+
+    void setOnEntryRemovedListener(OnEntryRemoved<TKey, TValue>* listener);
+    size_t size() const;
+    const TValue& get(const TKey& key);
+    bool put(const TKey& key, const TValue& value);
+    bool remove(const TKey& key);
+    bool removeOldest();
+    void clear();
+
+private:
+    LruCache(const LruCache& that);  // disallow copy constructor
+
+    struct Entry {
+        TKey key;
+        TValue value;
+        Entry* parent;
+        Entry* child;
+
+        Entry(TKey key_, TValue value_) : key(key_), value(value_), parent(NULL), child(NULL) {
+        }
+        const TKey& getKey() const { return key; }
+    };
+
+    void attachToCache(Entry& entry);
+    void detachFromCache(Entry& entry);
+    void rehash(size_t newCapacity);
+
+    UniquePtr<BasicHashtable<TKey, Entry> > mTable;
+    OnEntryRemoved<TKey, TValue>* mListener;
+    Entry* mOldest;
+    Entry* mYoungest;
+    uint32_t mMaxCapacity;
+    TValue mNullValue;
+};
+
+// Implementation is here, because it's fully templated
+template <typename TKey, typename TValue>
+LruCache<TKey, TValue>::LruCache(uint32_t maxCapacity): mMaxCapacity(maxCapacity),
+    mNullValue(NULL), mTable(new BasicHashtable<TKey, Entry>), mYoungest(NULL), mOldest(NULL),
+    mListener(NULL) {
+};
+
+template<typename K, typename V>
+void LruCache<K, V>::setOnEntryRemovedListener(OnEntryRemoved<K, V>* listener) {
+    mListener = listener;
+}
+
+template <typename TKey, typename TValue>
+size_t LruCache<TKey, TValue>::size() const {
+    return mTable->size();
+}
+
+template <typename TKey, typename TValue>
+const TValue& LruCache<TKey, TValue>::get(const TKey& key) {
+    hash_t hash = hash_type(key);
+    ssize_t index = mTable->find(-1, hash, key);
+    if (index == -1) {
+        return mNullValue;
+    }
+    Entry& entry = mTable->editEntryAt(index);
+    detachFromCache(entry);
+    attachToCache(entry);
+    return entry.value;
+}
+
+template <typename TKey, typename TValue>
+bool LruCache<TKey, TValue>::put(const TKey& key, const TValue& value) {
+    if (mMaxCapacity != kUnlimitedCapacity && size() >= mMaxCapacity) {
+        removeOldest();
+    }
+
+    hash_t hash = hash_type(key);
+    ssize_t index = mTable->find(-1, hash, key);
+    if (index >= 0) {
+        return false;
+    }
+    if (!mTable->hasMoreRoom()) {
+        rehash(mTable->capacity() * 2);
+    }
+
+    // Would it be better to initialize a blank entry and assign key, value?
+    Entry initEntry(key, value);
+    index = mTable->add(hash, initEntry);
+    Entry& entry = mTable->editEntryAt(index);
+    attachToCache(entry);
+    return true;
+}
+
+template <typename TKey, typename TValue>
+bool LruCache<TKey, TValue>::remove(const TKey& key) {
+    hash_t hash = hash_type(key);
+    ssize_t index = mTable->find(-1, hash, key);
+    if (index < 0) {
+        return false;
+    }
+    Entry& entry = mTable->editEntryAt(index);
+    if (mListener) {
+        (*mListener)(entry.key, entry.value);
+    }
+    detachFromCache(entry);
+    mTable->removeAt(index);
+    return true;
+}
+
+template <typename TKey, typename TValue>
+bool LruCache<TKey, TValue>::removeOldest() {
+    if (mOldest != NULL) {
+        return remove(mOldest->key);
+        // TODO: should probably abort if false
+    }
+    return false;
+}
+
+template <typename TKey, typename TValue>
+void LruCache<TKey, TValue>::clear() {
+    if (mListener) {
+        for (Entry* p = mOldest; p != NULL; p = p->child) {
+            (*mListener)(p->key, p->value);
+        }
+    }
+    mYoungest = NULL;
+    mOldest = NULL;
+    mTable->clear();
+}
+
+template <typename TKey, typename TValue>
+void LruCache<TKey, TValue>::attachToCache(Entry& entry) {
+    if (mYoungest == NULL) {
+        mYoungest = mOldest = &entry;
+    } else {
+        entry.parent = mYoungest;
+        mYoungest->child = &entry;
+        mYoungest = &entry;
+    }
+}
+
+template <typename TKey, typename TValue>
+void LruCache<TKey, TValue>::detachFromCache(Entry& entry) {
+    if (entry.parent != NULL) {
+        entry.parent->child = entry.child;
+    } else {
+        mOldest = entry.child;
+    }
+    if (entry.child != NULL) {
+        entry.child->parent = entry.parent;
+    } else {
+        mYoungest = entry.parent;
+    }
+
+    entry.parent = NULL;
+    entry.child = NULL;
+}
+
+template <typename TKey, typename TValue>
+void LruCache<TKey, TValue>::rehash(size_t newCapacity) {
+    UniquePtr<BasicHashtable<TKey, Entry> > oldTable(mTable.release());
+    Entry* oldest = mOldest;
+
+    mOldest = NULL;
+    mYoungest = NULL;
+    mTable.reset(new BasicHashtable<TKey, Entry>(newCapacity));
+    for (Entry* p = oldest; p != NULL; p = p->child) {
+        put(p->key, p->value);
+    }
+}
+
+}
diff --git a/include/utils/TypeHelpers.h b/include/utils/TypeHelpers.h
index 2bf33c3..13c9081 100644
--- a/include/utils/TypeHelpers.h
+++ b/include/utils/TypeHelpers.h
@@ -291,7 +291,7 @@
 ANDROID_REINTERPRET_HASH(float, uint32_t)
 ANDROID_REINTERPRET_HASH(double, uint64_t)
 
-template <typename T> inline hash_t hash_type(const T*& value) {
+template <typename T> inline hash_t hash_type(T* const & value) {
     return hash_type(uintptr_t(value));
 }
 
diff --git a/libs/utils/Android.mk b/libs/utils/Android.mk
index c9f8fd4..73a98d5 100644
--- a/libs/utils/Android.mk
+++ b/libs/utils/Android.mk
@@ -25,6 +25,7 @@
 	Debug.cpp \
 	FileMap.cpp \
 	Flattenable.cpp \
+	JenkinsHash.cpp \
 	LinearTransform.cpp \
 	Log.cpp \
 	PropertyMap.cpp \
diff --git a/libs/utils/BasicHashtable.cpp b/libs/utils/BasicHashtable.cpp
index fb8ec9f..fd51b7b 100644
--- a/libs/utils/BasicHashtable.cpp
+++ b/libs/utils/BasicHashtable.cpp
@@ -80,7 +80,7 @@
             SharedBuffer* sb = SharedBuffer::bufferFromData(mBuckets);
             if (sb->onlyOwner()) {
                 destroyBuckets(mBuckets, mBucketCount);
-                for (size_t i = 0; i < mSize; i++) {
+                for (size_t i = 0; i < mBucketCount; i++) {
                     Bucket& bucket = bucketAt(mBuckets, i);
                     bucket.cookie = 0;
                 }
diff --git a/libs/utils/JenkinsHash.cpp b/libs/utils/JenkinsHash.cpp
new file mode 100644
index 0000000..52c9bb7
--- /dev/null
+++ b/libs/utils/JenkinsHash.cpp
@@ -0,0 +1,64 @@
+/*
+ * Copyright (C) 2012 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.
+ */
+
+/* Implementation of Jenkins one-at-a-time hash function. These choices are
+ * optimized for code size and portability, rather than raw speed. But speed
+ * should still be quite good.
+ **/
+
+#include <utils/JenkinsHash.h>
+
+namespace android {
+
+hash_t JenkinsHashWhiten(uint32_t hash) {
+    hash += (hash << 3);
+    hash ^= (hash >> 11);
+    hash += (hash << 15);
+    return hash;
+}
+
+uint32_t JenkinsHashMixBytes(uint32_t hash, const uint8_t* bytes, size_t size) {
+    hash = JenkinsHashMix(hash, (uint32_t)size);
+    size_t i;
+    for (i = 0; i < (size & -4); i += 4) {
+        uint32_t data = bytes[i] | (bytes[i+1] << 8) | (bytes[i+2] << 16) | (bytes[i+3] << 24);
+        hash = JenkinsHashMix(hash, data);
+    }
+    if (size & 3) {
+        uint32_t data = bytes[i];
+        data |= ((size & 3) > 1) ? (bytes[i+1] << 8) : 0;
+        data |= ((size & 3) > 2) ? (bytes[i+2] << 16) : 0;
+        hash = JenkinsHashMix(hash, data);
+    }
+    return hash;
+}
+
+uint32_t JenkinsHashMixShorts(uint32_t hash, const uint16_t* shorts, size_t size) {
+    hash = JenkinsHashMix(hash, (uint32_t)size);
+    size_t i;
+    for (i = 0; i < (size & -2); i += 2) {
+        uint32_t data = shorts[i] | (shorts[i+1] << 16);
+        hash = JenkinsHashMix(hash, data);
+    }
+    if (size & 1) {
+        uint32_t data = shorts[i];
+        hash = JenkinsHashMix(hash, data);
+    }
+    return hash;
+}
+
+}
+
diff --git a/libs/utils/tests/Android.mk b/libs/utils/tests/Android.mk
index 5b2b5b1..a2ca9c8 100644
--- a/libs/utils/tests/Android.mk
+++ b/libs/utils/tests/Android.mk
@@ -7,6 +7,7 @@
     BasicHashtable_test.cpp \
     BlobCache_test.cpp \
     Looper_test.cpp \
+    LruCache_test.cpp \
     String8_test.cpp \
     Unicode_test.cpp \
     Vector_test.cpp \
diff --git a/libs/utils/tests/LruCache_test.cpp b/libs/utils/tests/LruCache_test.cpp
new file mode 100644
index 0000000..e573952
--- /dev/null
+++ b/libs/utils/tests/LruCache_test.cpp
@@ -0,0 +1,291 @@
+/*
+ * Copyright (C) 2012 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.
+ */
+
+#include <stdlib.h>
+#include <utils/JenkinsHash.h>
+#include <utils/LruCache.h>
+#include <cutils/log.h>
+#include <gtest/gtest.h>
+
+namespace android {
+
+typedef int SimpleKey;
+typedef const char* StringValue;
+
+struct ComplexKey {
+    int k;
+
+    explicit ComplexKey(int k) : k(k) {
+        instanceCount += 1;
+    }
+
+    ComplexKey(const ComplexKey& other) : k(other.k) {
+        instanceCount += 1;
+    }
+
+    ~ComplexKey() {
+        instanceCount -= 1;
+    }
+
+    bool operator ==(const ComplexKey& other) const {
+        return k == other.k;
+    }
+
+    bool operator !=(const ComplexKey& other) const {
+        return k != other.k;
+    }
+
+    static ssize_t instanceCount;
+};
+
+ssize_t ComplexKey::instanceCount = 0;
+
+template<> inline hash_t hash_type(const ComplexKey& value) {
+    return hash_type(value.k);
+}
+
+struct ComplexValue {
+    int v;
+
+    explicit ComplexValue(int v) : v(v) {
+        instanceCount += 1;
+    }
+
+    ComplexValue(const ComplexValue& other) : v(other.v) {
+        instanceCount += 1;
+    }
+
+    ~ComplexValue() {
+        instanceCount -= 1;
+    }
+
+    static ssize_t instanceCount;
+};
+
+ssize_t ComplexValue::instanceCount = 0;
+
+typedef LruCache<ComplexKey, ComplexValue> ComplexCache;
+
+class EntryRemovedCallback : public OnEntryRemoved<SimpleKey, StringValue> {
+public:
+    EntryRemovedCallback() : callbackCount(0), lastKey(-1), lastValue(NULL) { }
+    ~EntryRemovedCallback() {}
+    void operator()(SimpleKey& k, StringValue& v) {
+        callbackCount += 1;
+        lastKey = k;
+        lastValue = v;
+    }
+    ssize_t callbackCount;
+    SimpleKey lastKey;
+    StringValue lastValue;
+};
+
+class LruCacheTest : public testing::Test {
+protected:
+    virtual void SetUp() {
+        ComplexKey::instanceCount = 0;
+        ComplexValue::instanceCount = 0;
+    }
+
+    virtual void TearDown() {
+        ASSERT_NO_FATAL_FAILURE(assertInstanceCount(0, 0));
+    }
+
+    void assertInstanceCount(ssize_t keys, ssize_t values) {
+        if (keys != ComplexKey::instanceCount || values != ComplexValue::instanceCount) {
+            FAIL() << "Expected " << keys << " keys and " << values << " values "
+                    "but there were actually " << ComplexKey::instanceCount << " keys and "
+                    << ComplexValue::instanceCount << " values";
+        }
+    }
+};
+
+TEST_F(LruCacheTest, Empty) {
+    LruCache<SimpleKey, StringValue> cache(100);
+
+    EXPECT_EQ(NULL, cache.get(0));
+    EXPECT_EQ(0u, cache.size());
+}
+
+TEST_F(LruCacheTest, Simple) {
+    LruCache<SimpleKey, StringValue> cache(100);
+
+    cache.put(1, "one");
+    cache.put(2, "two");
+    cache.put(3, "three");
+    EXPECT_STREQ("one", cache.get(1));
+    EXPECT_STREQ("two", cache.get(2));
+    EXPECT_STREQ("three", cache.get(3));
+    EXPECT_EQ(3u, cache.size());
+}
+
+TEST_F(LruCacheTest, MaxCapacity) {
+    LruCache<SimpleKey, StringValue> cache(2);
+
+    cache.put(1, "one");
+    cache.put(2, "two");
+    cache.put(3, "three");
+    EXPECT_EQ(NULL, cache.get(1));
+    EXPECT_STREQ("two", cache.get(2));
+    EXPECT_STREQ("three", cache.get(3));
+    EXPECT_EQ(2u, cache.size());
+}
+
+TEST_F(LruCacheTest, RemoveLru) {
+    LruCache<SimpleKey, StringValue> cache(100);
+
+    cache.put(1, "one");
+    cache.put(2, "two");
+    cache.put(3, "three");
+    cache.removeOldest();
+    EXPECT_EQ(NULL, cache.get(1));
+    EXPECT_STREQ("two", cache.get(2));
+    EXPECT_STREQ("three", cache.get(3));
+    EXPECT_EQ(2u, cache.size());
+}
+
+TEST_F(LruCacheTest, GetUpdatesLru) {
+    LruCache<SimpleKey, StringValue> cache(100);
+
+    cache.put(1, "one");
+    cache.put(2, "two");
+    cache.put(3, "three");
+    EXPECT_STREQ("one", cache.get(1));
+    cache.removeOldest();
+    EXPECT_STREQ("one", cache.get(1));
+    EXPECT_EQ(NULL, cache.get(2));
+    EXPECT_STREQ("three", cache.get(3));
+    EXPECT_EQ(2u, cache.size());
+}
+
+uint32_t hash_int(int x) {
+    return JenkinsHashWhiten(JenkinsHashMix(0, x));
+}
+
+TEST_F(LruCacheTest, StressTest) {
+    const size_t kCacheSize = 512;
+    LruCache<SimpleKey, StringValue> cache(512);
+    const size_t kNumKeys = 16 * 1024;
+    const size_t kNumIters = 100000;
+    char* strings[kNumKeys];
+
+    for (size_t i = 0; i < kNumKeys; i++) {
+        strings[i] = (char *)malloc(16);
+        sprintf(strings[i], "%d", i);
+    }
+
+    srandom(12345);
+    int hitCount = 0;
+    for (size_t i = 0; i < kNumIters; i++) {
+        int index = random() % kNumKeys;
+        uint32_t key = hash_int(index);
+        const char *val = cache.get(key);
+        if (val != NULL) {
+            EXPECT_EQ(strings[index], val);
+            hitCount++;
+        } else {
+            cache.put(key, strings[index]);
+        }
+    }
+    size_t expectedHitCount = kNumIters * kCacheSize / kNumKeys;
+    EXPECT_LT(int(expectedHitCount * 0.9), hitCount);
+    EXPECT_GT(int(expectedHitCount * 1.1), hitCount);
+    EXPECT_EQ(kCacheSize, cache.size());
+
+    for (size_t i = 0; i < kNumKeys; i++) {
+        free((void *)strings[i]);
+    }
+}
+
+TEST_F(LruCacheTest, NoLeak) {
+    ComplexCache cache(100);
+
+    cache.put(ComplexKey(0), ComplexValue(0));
+    cache.put(ComplexKey(1), ComplexValue(1));
+    EXPECT_EQ(2, cache.size());
+    assertInstanceCount(2, 3);  // the null value counts as an instance
+}
+
+TEST_F(LruCacheTest, Clear) {
+    ComplexCache cache(100);
+
+    cache.put(ComplexKey(0), ComplexValue(0));
+    cache.put(ComplexKey(1), ComplexValue(1));
+    EXPECT_EQ(2, cache.size());
+    assertInstanceCount(2, 3);
+    cache.clear();
+    assertInstanceCount(0, 1);
+}
+
+TEST_F(LruCacheTest, ClearNoDoubleFree) {
+    {
+        ComplexCache cache(100);
+
+        cache.put(ComplexKey(0), ComplexValue(0));
+        cache.put(ComplexKey(1), ComplexValue(1));
+        EXPECT_EQ(2, cache.size());
+        assertInstanceCount(2, 3);
+        cache.removeOldest();
+        cache.clear();
+        assertInstanceCount(0, 1);
+    }
+    assertInstanceCount(0, 0);
+}
+
+TEST_F(LruCacheTest, ClearReuseOk) {
+    ComplexCache cache(100);
+
+    cache.put(ComplexKey(0), ComplexValue(0));
+    cache.put(ComplexKey(1), ComplexValue(1));
+    EXPECT_EQ(2, cache.size());
+    assertInstanceCount(2, 3);
+    cache.clear();
+    assertInstanceCount(0, 1);
+    cache.put(ComplexKey(0), ComplexValue(0));
+    cache.put(ComplexKey(1), ComplexValue(1));
+    EXPECT_EQ(2, cache.size());
+    assertInstanceCount(2, 3);
+}
+
+TEST_F(LruCacheTest, Callback) {
+    LruCache<SimpleKey, StringValue> cache(100);
+    EntryRemovedCallback callback;
+    cache.setOnEntryRemovedListener(&callback);
+
+    cache.put(1, "one");
+    cache.put(2, "two");
+    cache.put(3, "three");
+    EXPECT_EQ(3, cache.size());
+    cache.removeOldest();
+    EXPECT_EQ(1, callback.callbackCount);
+    EXPECT_EQ(1, callback.lastKey);
+    EXPECT_STREQ("one", callback.lastValue);
+}
+
+TEST_F(LruCacheTest, CallbackOnClear) {
+    LruCache<SimpleKey, StringValue> cache(100);
+    EntryRemovedCallback callback;
+    cache.setOnEntryRemovedListener(&callback);
+
+    cache.put(1, "one");
+    cache.put(2, "two");
+    cache.put(3, "three");
+    EXPECT_EQ(3, cache.size());
+    cache.clear();
+    EXPECT_EQ(3, callback.callbackCount);
+}
+
+}