diff options
| -rw-r--r-- | include/utils/BlobCache.h | 181 | ||||
| -rw-r--r-- | libs/utils/Android.mk | 1 | ||||
| -rw-r--r-- | libs/utils/BlobCache.cpp | 232 | ||||
| -rw-r--r-- | libs/utils/tests/Android.mk | 1 | ||||
| -rw-r--r-- | libs/utils/tests/BlobCache_test.cpp | 257 |
5 files changed, 672 insertions, 0 deletions
diff --git a/include/utils/BlobCache.h b/include/utils/BlobCache.h new file mode 100644 index 0000000..8f76d72 --- /dev/null +++ b/include/utils/BlobCache.h @@ -0,0 +1,181 @@ +/* + ** Copyright 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. + */ + +#ifndef ANDROID_BLOB_CACHE_H +#define ANDROID_BLOB_CACHE_H + +#include <stddef.h> + +#include <utils/RefBase.h> +#include <utils/SortedVector.h> +#include <utils/threads.h> + +namespace android { + +// A BlobCache is an in-memory cache for binary key/value pairs. All the public +// methods are thread-safe. +// +// The cache contents can be serialized to a file and reloaded in a subsequent +// execution of the program. This serialization is non-portable and should only +// be loaded by the device that generated it. +class BlobCache : public RefBase { +public: + + // Create an empty blob cache. The blob cache will cache key/value pairs + // with key and value sizes less than or equal to maxKeySize and + // maxValueSize, respectively. The total combined size of ALL cache entries + // (key sizes plus value sizes) will not exceed maxTotalSize. + BlobCache(size_t maxKeySize, size_t maxValueSize, size_t maxTotalSize); + + // set inserts a new binary value into the cache and associates it with the + // given binary key. If the key or value are too large for the cache then + // the cache remains unchanged. This includes the case where a different + // value was previously associated with the given key - the old value will + // remain in the cache. If the given key and value are small enough to be + // put in the cache (based on the maxKeySize, maxValueSize, and maxTotalSize + // values specified to the BlobCache constructor), then the key/value pair + // will be in the cache after set returns. Note, however, that a subsequent + // call to set may evict old key/value pairs from the cache. + // + // Preconditions: + // key != NULL + // 0 < keySize + // value != NULL + // 0 < valueSize + void set(const void* key, size_t keySize, const void* value, + size_t valueSize); + + // The get function retrieves from the cache the binary value associated + // with a given binary key. If the key is present in the cache then the + // length of the binary value associated with that key is returned. If the + // value argument is non-NULL and the size of the cached value is less than + // valueSize bytes then the cached value is copied into the buffer pointed + // to by the value argument. If the key is not present in the cache then 0 + // is returned and the buffer pointed to by the value argument is not + // modified. + // + // Note that when calling get multiple times with the same key, the later + // calls may fail, returning 0, even if earlier calls succeeded. The return + // value must be checked for each call. + // + // Preconditions: + // key != NULL + // 0 < keySize + // 0 <= valueSize + size_t get(const void* key, size_t keySize, void* value, size_t valueSize); + +private: + // Copying is disallowed. + BlobCache(const BlobCache&); + void operator=(const BlobCache&); + + // clean evicts a randomly chosen set of entries from the cache such that + // the total size of all remaining entries is less than mMaxTotalSize/2. + void clean(); + + // isCleanable returns true if the cache is full enough for the clean method + // to have some effect, and false otherwise. + bool isCleanable() const; + + // A Blob is an immutable sized unstructured data blob. + class Blob : public RefBase { + public: + Blob(const void* data, size_t size, bool copyData); + ~Blob(); + + bool operator<(const Blob& rhs) const; + + const void* getData() const; + size_t getSize() const; + + private: + // Copying is not allowed. + Blob(const Blob&); + void operator=(const Blob&); + + // mData points to the buffer containing the blob data. + const void* mData; + + // mSize is the size of the blob data in bytes. + size_t mSize; + + // mOwnsData indicates whether or not this Blob object should free the + // memory pointed to by mData when the Blob gets destructed. + bool mOwnsData; + }; + + // A CacheEntry is a single key/value pair in the cache. + class CacheEntry { + public: + CacheEntry(); + CacheEntry(const sp<Blob>& key, const sp<Blob>& value); + CacheEntry(const CacheEntry& ce); + + bool operator<(const CacheEntry& rhs) const; + const CacheEntry& operator=(const CacheEntry&); + + sp<Blob> getKey() const; + sp<Blob> getValue() const; + + void setValue(const sp<Blob>& value); + + private: + + // mKey is the key that identifies the cache entry. + sp<Blob> mKey; + + // mValue is the cached data associated with the key. + sp<Blob> mValue; + }; + + // mMaxKeySize is the maximum key size that will be cached. Calls to + // BlobCache::set with a keySize parameter larger than mMaxKeySize will + // simply not add the key/value pair to the cache. + const size_t mMaxKeySize; + + // mMaxValueSize is the maximum value size that will be cached. Calls to + // BlobCache::set with a valueSize parameter larger than mMaxValueSize will + // simply not add the key/value pair to the cache. + const size_t mMaxValueSize; + + // mMaxTotalSize is the maximum size that all cache entries can occupy. This + // includes space for both keys and values. When a call to BlobCache::set + // would otherwise cause this limit to be exceeded, either the key/value + // pair passed to BlobCache::set will not be cached or other cache entries + // will be evicted from the cache to make room for the new entry. + const size_t mMaxTotalSize; + + // mTotalSize is the total combined size of all keys and values currently in + // the cache. + size_t mTotalSize; + + // mRandState is the pseudo-random number generator state. It is passed to + // nrand48 to generate random numbers when needed. It must be protected by + // mMutex. + unsigned short mRandState[3]; + + // mCacheEntries stores all the cache entries that are resident in memory. + // Cache entries are added to it by the 'set' method. + SortedVector<CacheEntry> mCacheEntries; + + // mMutex is used to synchronize access to all member variables. It must be + // locked any time the member variables are written or read. + Mutex mMutex; +}; + +} + +#endif // ANDROID_BLOB_CACHE_H diff --git a/libs/utils/Android.mk b/libs/utils/Android.mk index e8d40ba..093189c 100644 --- a/libs/utils/Android.mk +++ b/libs/utils/Android.mk @@ -21,6 +21,7 @@ commonSources:= \ Asset.cpp \ AssetDir.cpp \ AssetManager.cpp \ + BlobCache.cpp \ BufferedTextOutput.cpp \ CallStack.cpp \ Debug.cpp \ diff --git a/libs/utils/BlobCache.cpp b/libs/utils/BlobCache.cpp new file mode 100644 index 0000000..1298fa7 --- /dev/null +++ b/libs/utils/BlobCache.cpp @@ -0,0 +1,232 @@ +/* + ** Copyright 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 "BlobCache" +//#define LOG_NDEBUG 0 + +#include <stdlib.h> +#include <string.h> + +#include <utils/BlobCache.h> +#include <utils/Log.h> + +namespace android { + +BlobCache::BlobCache(size_t maxKeySize, size_t maxValueSize, size_t maxTotalSize): + mMaxKeySize(maxKeySize), + mMaxValueSize(maxValueSize), + mMaxTotalSize(maxTotalSize), + mTotalSize(0) { + nsecs_t now = systemTime(SYSTEM_TIME_MONOTONIC); + mRandState[0] = (now >> 0) & 0xFFFF; + mRandState[1] = (now >> 16) & 0xFFFF; + mRandState[2] = (now >> 32) & 0xFFFF; + LOGV("initializing random seed using %lld", now); +} + +void BlobCache::set(const void* key, size_t keySize, const void* value, + size_t valueSize) { + if (mMaxKeySize < keySize) { + LOGV("set: not caching because the key is too large: %d (limit: %d)", + keySize, mMaxKeySize); + return; + } + if (mMaxValueSize < valueSize) { + LOGV("set: not caching because the value is too large: %d (limit: %d)", + valueSize, mMaxValueSize); + return; + } + if (mMaxTotalSize < keySize + valueSize) { + LOGV("set: not caching because the combined key/value size is too " + "large: %d (limit: %d)", keySize + valueSize, mMaxTotalSize); + return; + } + if (keySize == 0) { + LOGW("set: not caching because keySize is 0"); + return; + } + if (valueSize <= 0) { + LOGW("set: not caching because valueSize is 0"); + return; + } + + Mutex::Autolock lock(mMutex); + sp<Blob> dummyKey(new Blob(key, keySize, false)); + CacheEntry dummyEntry(dummyKey, NULL); + + while (true) { + + ssize_t index = mCacheEntries.indexOf(dummyEntry); + if (index < 0) { + // Create a new cache entry. + sp<Blob> keyBlob(new Blob(key, keySize, true)); + sp<Blob> valueBlob(new Blob(value, valueSize, true)); + size_t newTotalSize = mTotalSize + keySize + valueSize; + if (mMaxTotalSize < newTotalSize) { + if (isCleanable()) { + // Clean the cache and try again. + clean(); + continue; + } else { + LOGV("set: not caching new key/value pair because the " + "total cache size limit would be exceeded: %d " + "(limit: %d)", + keySize + valueSize, mMaxTotalSize); + break; + } + } + mCacheEntries.add(CacheEntry(keyBlob, valueBlob)); + mTotalSize = newTotalSize; + LOGV("set: created new cache entry with %d byte key and %d byte value", + keySize, valueSize); + } else { + // Update the existing cache entry. + sp<Blob> valueBlob(new Blob(value, valueSize, true)); + sp<Blob> oldValueBlob(mCacheEntries[index].getValue()); + size_t newTotalSize = mTotalSize + valueSize - oldValueBlob->getSize(); + if (mMaxTotalSize < newTotalSize) { + if (isCleanable()) { + // Clean the cache and try again. + clean(); + continue; + } else { + LOGV("set: not caching new value because the total cache " + "size limit would be exceeded: %d (limit: %d)", + keySize + valueSize, mMaxTotalSize); + break; + } + } + mCacheEntries.editItemAt(index).setValue(valueBlob); + mTotalSize = newTotalSize; + LOGV("set: updated existing cache entry with %d byte key and %d byte " + "value", keySize, valueSize); + } + break; + } +} + +size_t BlobCache::get(const void* key, size_t keySize, void* value, + size_t valueSize) { + if (mMaxKeySize < keySize) { + LOGV("get: not searching because the key is too large: %d (limit %d)", + keySize, mMaxKeySize); + return 0; + } + Mutex::Autolock lock(mMutex); + sp<Blob> dummyKey(new Blob(key, keySize, false)); + CacheEntry dummyEntry(dummyKey, NULL); + ssize_t index = mCacheEntries.indexOf(dummyEntry); + if (index < 0) { + LOGV("get: no cache entry found for key of size %d", keySize); + return 0; + } + + // The key was found. Return the value if the caller's buffer is large + // enough. + sp<Blob> valueBlob(mCacheEntries[index].getValue()); + size_t valueBlobSize = valueBlob->getSize(); + if (valueBlobSize <= valueSize) { + LOGV("get: copying %d bytes to caller's buffer", valueBlobSize); + memcpy(value, valueBlob->getData(), valueBlobSize); + } else { + LOGV("get: caller's buffer is too small for value: %d (needs %d)", + valueSize, valueBlobSize); + } + return valueBlobSize; +} + +void BlobCache::clean() { + // Remove a random cache entry until the total cache size gets below half + // the maximum total cache size. + while (mTotalSize > mMaxTotalSize / 2) { + size_t i = size_t(nrand48(mRandState) % (mCacheEntries.size())); + const CacheEntry& entry(mCacheEntries[i]); + mTotalSize -= entry.getKey()->getSize() + entry.getValue()->getSize(); + mCacheEntries.removeAt(i); + } +} + +bool BlobCache::isCleanable() const { + return mTotalSize > mMaxTotalSize / 2; +} + +BlobCache::Blob::Blob(const void* data, size_t size, bool copyData): + mData(copyData ? malloc(size) : data), + mSize(size), + mOwnsData(copyData) { + if (copyData) { + memcpy(const_cast<void*>(mData), data, size); + } +} + +BlobCache::Blob::~Blob() { + if (mOwnsData) { + free(const_cast<void*>(mData)); + } +} + +bool BlobCache::Blob::operator<(const Blob& rhs) const { + if (mSize == rhs.mSize) { + return memcmp(mData, rhs.mData, mSize) < 0; + } else { + return mSize < rhs.mSize; + } +} + +const void* BlobCache::Blob::getData() const { + return mData; +} + +size_t BlobCache::Blob::getSize() const { + return mSize; +} + +BlobCache::CacheEntry::CacheEntry() { +} + +BlobCache::CacheEntry::CacheEntry(const sp<Blob>& key, const sp<Blob>& value): + mKey(key), + mValue(value) { +} + +BlobCache::CacheEntry::CacheEntry(const CacheEntry& ce): + mKey(ce.mKey), + mValue(ce.mValue) { +} + +bool BlobCache::CacheEntry::operator<(const CacheEntry& rhs) const { + return *mKey < *rhs.mKey; +} + +const BlobCache::CacheEntry& BlobCache::CacheEntry::operator=(const CacheEntry& rhs) { + mKey = rhs.mKey; + mValue = rhs.mValue; + return *this; +} + +sp<BlobCache::Blob> BlobCache::CacheEntry::getKey() const { + return mKey; +} + +sp<BlobCache::Blob> BlobCache::CacheEntry::getValue() const { + return mValue; +} + +void BlobCache::CacheEntry::setValue(const sp<Blob>& value) { + mValue = value; +} + +} // namespace android diff --git a/libs/utils/tests/Android.mk b/libs/utils/tests/Android.mk index 72d4876..87ad98e 100644 --- a/libs/utils/tests/Android.mk +++ b/libs/utils/tests/Android.mk @@ -6,6 +6,7 @@ ifneq ($(TARGET_SIMULATOR),true) # Build the unit tests. test_src_files := \ + BlobCache_test.cpp \ ObbFile_test.cpp \ Looper_test.cpp \ String8_test.cpp \ diff --git a/libs/utils/tests/BlobCache_test.cpp b/libs/utils/tests/BlobCache_test.cpp new file mode 100644 index 0000000..653ea5e --- /dev/null +++ b/libs/utils/tests/BlobCache_test.cpp @@ -0,0 +1,257 @@ +/* + ** Copyright 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. + */ + +#include <gtest/gtest.h> + +#include <utils/BlobCache.h> + +namespace android { + +class BlobCacheTest : public ::testing::Test { +protected: + enum { + MAX_KEY_SIZE = 6, + MAX_VALUE_SIZE = 8, + MAX_TOTAL_SIZE = 13, + }; + + virtual void SetUp() { + mBC = new BlobCache(MAX_KEY_SIZE, MAX_VALUE_SIZE, MAX_TOTAL_SIZE); + } + + virtual void TearDown() { + mBC.clear(); + } + + sp<BlobCache> mBC; +}; + +TEST_F(BlobCacheTest, CacheSingleValueSucceeds) { + char buf[4] = { 0xee, 0xee, 0xee, 0xee }; + mBC->set("abcd", 4, "efgh", 4); + ASSERT_EQ(size_t(4), mBC->get("abcd", 4, buf, 4)); + ASSERT_EQ('e', buf[0]); + ASSERT_EQ('f', buf[1]); + ASSERT_EQ('g', buf[2]); + ASSERT_EQ('h', buf[3]); +} + +TEST_F(BlobCacheTest, CacheTwoValuesSucceeds) { + char buf[2] = { 0xee, 0xee }; + mBC->set("ab", 2, "cd", 2); + mBC->set("ef", 2, "gh", 2); + ASSERT_EQ(size_t(2), mBC->get("ab", 2, buf, 2)); + ASSERT_EQ('c', buf[0]); + ASSERT_EQ('d', buf[1]); + ASSERT_EQ(size_t(2), mBC->get("ef", 2, buf, 2)); + ASSERT_EQ('g', buf[0]); + ASSERT_EQ('h', buf[1]); +} + +TEST_F(BlobCacheTest, GetOnlyWritesInsideBounds) { + char buf[6] = { 0xee, 0xee, 0xee, 0xee, 0xee, 0xee }; + mBC->set("abcd", 4, "efgh", 4); + ASSERT_EQ(size_t(4), mBC->get("abcd", 4, buf+1, 4)); + ASSERT_EQ(0xee, buf[0]); + ASSERT_EQ('e', buf[1]); + ASSERT_EQ('f', buf[2]); + ASSERT_EQ('g', buf[3]); + ASSERT_EQ('h', buf[4]); + ASSERT_EQ(0xee, buf[5]); +} + +TEST_F(BlobCacheTest, GetOnlyWritesIfBufferIsLargeEnough) { + char buf[3] = { 0xee, 0xee, 0xee }; + mBC->set("abcd", 4, "efgh", 4); + ASSERT_EQ(size_t(4), mBC->get("abcd", 4, buf, 3)); + ASSERT_EQ(0xee, buf[0]); + ASSERT_EQ(0xee, buf[1]); + ASSERT_EQ(0xee, buf[2]); +} + +TEST_F(BlobCacheTest, GetDoesntAccessNullBuffer) { + mBC->set("abcd", 4, "efgh", 4); + ASSERT_EQ(size_t(4), mBC->get("abcd", 4, NULL, 0)); +} + +TEST_F(BlobCacheTest, MultipleSetsCacheLatestValue) { + char buf[4] = { 0xee, 0xee, 0xee, 0xee }; + mBC->set("abcd", 4, "efgh", 4); + mBC->set("abcd", 4, "ijkl", 4); + ASSERT_EQ(size_t(4), mBC->get("abcd", 4, buf, 4)); + ASSERT_EQ('i', buf[0]); + ASSERT_EQ('j', buf[1]); + ASSERT_EQ('k', buf[2]); + ASSERT_EQ('l', buf[3]); +} + +TEST_F(BlobCacheTest, SecondSetKeepsFirstValueIfTooLarge) { + char buf[MAX_VALUE_SIZE+1] = { 0xee, 0xee, 0xee, 0xee }; + mBC->set("abcd", 4, "efgh", 4); + mBC->set("abcd", 4, buf, MAX_VALUE_SIZE+1); + ASSERT_EQ(size_t(4), mBC->get("abcd", 4, buf, 4)); + ASSERT_EQ('e', buf[0]); + ASSERT_EQ('f', buf[1]); + ASSERT_EQ('g', buf[2]); + ASSERT_EQ('h', buf[3]); +} + +TEST_F(BlobCacheTest, DoesntCacheIfKeyIsTooBig) { + char key[MAX_KEY_SIZE+1]; + char buf[4] = { 0xee, 0xee, 0xee, 0xee }; + for (int i = 0; i < MAX_KEY_SIZE+1; i++) { + key[i] = 'a'; + } + mBC->set(key, MAX_KEY_SIZE+1, "bbbb", 4); + ASSERT_EQ(size_t(0), mBC->get(key, MAX_KEY_SIZE+1, buf, 4)); + ASSERT_EQ(0xee, buf[0]); + ASSERT_EQ(0xee, buf[1]); + ASSERT_EQ(0xee, buf[2]); + ASSERT_EQ(0xee, buf[3]); +} + +TEST_F(BlobCacheTest, DoesntCacheIfValueIsTooBig) { + char buf[MAX_VALUE_SIZE+1]; + for (int i = 0; i < MAX_VALUE_SIZE+1; i++) { + buf[i] = 'b'; + } + mBC->set("abcd", 4, buf, MAX_VALUE_SIZE+1); + for (int i = 0; i < MAX_VALUE_SIZE+1; i++) { + buf[i] = 0xee; + } + ASSERT_EQ(size_t(0), mBC->get("abcd", 4, buf, MAX_VALUE_SIZE+1)); + for (int i = 0; i < MAX_VALUE_SIZE+1; i++) { + SCOPED_TRACE(i); + ASSERT_EQ(0xee, buf[i]); + } +} + +TEST_F(BlobCacheTest, DoesntCacheIfKeyValuePairIsTooBig) { + // Check a testing assumptions + ASSERT_TRUE(MAX_TOTAL_SIZE < MAX_KEY_SIZE + MAX_VALUE_SIZE); + ASSERT_TRUE(MAX_KEY_SIZE < MAX_TOTAL_SIZE); + + enum { bufSize = MAX_TOTAL_SIZE - MAX_KEY_SIZE + 1 }; + + char key[MAX_KEY_SIZE]; + char buf[bufSize]; + for (int i = 0; i < MAX_KEY_SIZE; i++) { + key[i] = 'a'; + } + for (int i = 0; i < bufSize; i++) { + buf[i] = 'b'; + } + + mBC->set(key, MAX_KEY_SIZE, buf, MAX_VALUE_SIZE); + ASSERT_EQ(size_t(0), mBC->get(key, MAX_KEY_SIZE, NULL, 0)); +} + +TEST_F(BlobCacheTest, CacheMaxKeySizeSucceeds) { + char key[MAX_KEY_SIZE]; + char buf[4] = { 0xee, 0xee, 0xee, 0xee }; + for (int i = 0; i < MAX_KEY_SIZE; i++) { + key[i] = 'a'; + } + mBC->set(key, MAX_KEY_SIZE, "wxyz", 4); + ASSERT_EQ(size_t(4), mBC->get(key, MAX_KEY_SIZE, buf, 4)); + ASSERT_EQ('w', buf[0]); + ASSERT_EQ('x', buf[1]); + ASSERT_EQ('y', buf[2]); + ASSERT_EQ('z', buf[3]); +} + +TEST_F(BlobCacheTest, CacheMaxValueSizeSucceeds) { + char buf[MAX_VALUE_SIZE]; + for (int i = 0; i < MAX_VALUE_SIZE; i++) { + buf[i] = 'b'; + } + mBC->set("abcd", 4, buf, MAX_VALUE_SIZE); + for (int i = 0; i < MAX_VALUE_SIZE; i++) { + buf[i] = 0xee; + } + ASSERT_EQ(size_t(MAX_VALUE_SIZE), mBC->get("abcd", 4, buf, + MAX_VALUE_SIZE)); + for (int i = 0; i < MAX_VALUE_SIZE; i++) { + SCOPED_TRACE(i); + ASSERT_EQ('b', buf[i]); + } +} + +TEST_F(BlobCacheTest, CacheMaxKeyValuePairSizeSucceeds) { + // Check a testing assumption + ASSERT_TRUE(MAX_KEY_SIZE < MAX_TOTAL_SIZE); + + enum { bufSize = MAX_TOTAL_SIZE - MAX_KEY_SIZE }; + + char key[MAX_KEY_SIZE]; + char buf[bufSize]; + for (int i = 0; i < MAX_KEY_SIZE; i++) { + key[i] = 'a'; + } + for (int i = 0; i < bufSize; i++) { + buf[i] = 'b'; + } + + mBC->set(key, MAX_KEY_SIZE, buf, bufSize); + ASSERT_EQ(size_t(bufSize), mBC->get(key, MAX_KEY_SIZE, NULL, 0)); +} + +TEST_F(BlobCacheTest, CacheMinKeyAndValueSizeSucceeds) { + char buf[1] = { 0xee }; + mBC->set("x", 1, "y", 1); + ASSERT_EQ(size_t(1), mBC->get("x", 1, buf, 1)); + ASSERT_EQ('y', buf[0]); +} + +TEST_F(BlobCacheTest, CacheSizeDoesntExceedTotalLimit) { + for (int i = 0; i < 256; i++) { + uint8_t k = i; + mBC->set(&k, 1, "x", 1); + } + int numCached = 0; + for (int i = 0; i < 256; i++) { + uint8_t k = i; + if (mBC->get(&k, 1, NULL, 0) == 1) { + numCached++; + } + } + ASSERT_GE(MAX_TOTAL_SIZE / 2, numCached); +} + +TEST_F(BlobCacheTest, ExceedingTotalLimitHalvesCacheSize) { + // Fill up the entire cache with 1 char key/value pairs. + const int maxEntries = MAX_TOTAL_SIZE / 2; + for (int i = 0; i < maxEntries; i++) { + uint8_t k = i; + mBC->set(&k, 1, "x", 1); + } + // Insert one more entry, causing a cache overflow. + { + uint8_t k = maxEntries; + mBC->set(&k, 1, "x", 1); + } + // Count the number of entries in the cache. + int numCached = 0; + for (int i = 0; i < maxEntries+1; i++) { + uint8_t k = i; + if (mBC->get(&k, 1, NULL, 0) == 1) { + numCached++; + } + } + ASSERT_EQ(maxEntries/2 + 1, numCached); +} + +} // namespace android |