BlobCache.h revision 111280a8de1700f718744f48d163789473b9da30
158c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis/* 258c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis ** Copyright 2011, The Android Open Source Project 358c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis ** 458c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis ** Licensed under the Apache License, Version 2.0 (the "License"); 558c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis ** you may not use this file except in compliance with the License. 658c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis ** You may obtain a copy of the License at 758c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis ** 858c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis ** http://www.apache.org/licenses/LICENSE-2.0 958c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis ** 1058c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis ** Unless required by applicable law or agreed to in writing, software 1158c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis ** distributed under the License is distributed on an "AS IS" BASIS, 1258c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 1358c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis ** See the License for the specific language governing permissions and 1458c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis ** limitations under the License. 1558c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis */ 1658c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis 1758c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis#ifndef ANDROID_BLOB_CACHE_H 1858c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis#define ANDROID_BLOB_CACHE_H 1958c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis 2058c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis#include <stddef.h> 2158c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis 2258c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis#include <utils/RefBase.h> 2358c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis#include <utils/SortedVector.h> 2458c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis#include <utils/threads.h> 2558c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis 2658c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennisnamespace android { 2758c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis 2858c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis// A BlobCache is an in-memory cache for binary key/value pairs. All the public 2958c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis// methods are thread-safe. 3058c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis// 3158c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis// The cache contents can be serialized to a file and reloaded in a subsequent 3258c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis// execution of the program. This serialization is non-portable and should only 3358c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis// be loaded by the device that generated it. 3458c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennisclass BlobCache : public RefBase { 3558c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennispublic: 3658c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis 3758c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // Create an empty blob cache. The blob cache will cache key/value pairs 3858c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // with key and value sizes less than or equal to maxKeySize and 3958c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // maxValueSize, respectively. The total combined size of ALL cache entries 4058c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // (key sizes plus value sizes) will not exceed maxTotalSize. 4158c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis BlobCache(size_t maxKeySize, size_t maxValueSize, size_t maxTotalSize); 4258c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis 4358c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // set inserts a new binary value into the cache and associates it with the 4458c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // given binary key. If the key or value are too large for the cache then 4558c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // the cache remains unchanged. This includes the case where a different 4658c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // value was previously associated with the given key - the old value will 4758c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // remain in the cache. If the given key and value are small enough to be 4858c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // put in the cache (based on the maxKeySize, maxValueSize, and maxTotalSize 4958c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // values specified to the BlobCache constructor), then the key/value pair 5058c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // will be in the cache after set returns. Note, however, that a subsequent 5158c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // call to set may evict old key/value pairs from the cache. 5258c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // 5358c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // Preconditions: 5458c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // key != NULL 5558c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // 0 < keySize 5658c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // value != NULL 5758c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // 0 < valueSize 5858c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis void set(const void* key, size_t keySize, const void* value, 5958c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis size_t valueSize); 6058c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis 6158c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // The get function retrieves from the cache the binary value associated 6258c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // with a given binary key. If the key is present in the cache then the 6358c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // length of the binary value associated with that key is returned. If the 6458c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // value argument is non-NULL and the size of the cached value is less than 6558c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // valueSize bytes then the cached value is copied into the buffer pointed 6658c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // to by the value argument. If the key is not present in the cache then 0 6758c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // is returned and the buffer pointed to by the value argument is not 6858c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // modified. 6958c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // 7058c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // Note that when calling get multiple times with the same key, the later 7158c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // calls may fail, returning 0, even if earlier calls succeeded. The return 7258c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // value must be checked for each call. 7358c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // 7458c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // Preconditions: 7558c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // key != NULL 7658c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // 0 < keySize 7758c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // 0 <= valueSize 7858c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis size_t get(const void* key, size_t keySize, void* value, size_t valueSize); 7958c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis 8058c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennisprivate: 8158c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // Copying is disallowed. 8258c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis BlobCache(const BlobCache&); 8358c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis void operator=(const BlobCache&); 8458c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis 85111280a8de1700f718744f48d163789473b9da30Kenny Root // A random function helper to get around MinGW not having nrand48() 86111280a8de1700f718744f48d163789473b9da30Kenny Root long int blob_random(); 87111280a8de1700f718744f48d163789473b9da30Kenny Root 8858c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // clean evicts a randomly chosen set of entries from the cache such that 8958c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // the total size of all remaining entries is less than mMaxTotalSize/2. 9058c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis void clean(); 9158c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis 9258c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // isCleanable returns true if the cache is full enough for the clean method 9358c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // to have some effect, and false otherwise. 9458c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis bool isCleanable() const; 9558c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis 9658c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // A Blob is an immutable sized unstructured data blob. 9758c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis class Blob : public RefBase { 9858c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis public: 9958c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis Blob(const void* data, size_t size, bool copyData); 10058c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis ~Blob(); 10158c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis 10258c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis bool operator<(const Blob& rhs) const; 10358c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis 10458c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis const void* getData() const; 10558c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis size_t getSize() const; 10658c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis 10758c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis private: 10858c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // Copying is not allowed. 10958c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis Blob(const Blob&); 11058c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis void operator=(const Blob&); 11158c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis 11258c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // mData points to the buffer containing the blob data. 11358c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis const void* mData; 11458c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis 11558c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // mSize is the size of the blob data in bytes. 11658c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis size_t mSize; 11758c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis 11858c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // mOwnsData indicates whether or not this Blob object should free the 11958c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // memory pointed to by mData when the Blob gets destructed. 12058c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis bool mOwnsData; 12158c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis }; 12258c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis 12358c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // A CacheEntry is a single key/value pair in the cache. 12458c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis class CacheEntry { 12558c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis public: 12658c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis CacheEntry(); 12758c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis CacheEntry(const sp<Blob>& key, const sp<Blob>& value); 12858c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis CacheEntry(const CacheEntry& ce); 12958c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis 13058c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis bool operator<(const CacheEntry& rhs) const; 13158c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis const CacheEntry& operator=(const CacheEntry&); 13258c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis 13358c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis sp<Blob> getKey() const; 13458c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis sp<Blob> getValue() const; 13558c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis 13658c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis void setValue(const sp<Blob>& value); 13758c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis 13858c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis private: 13958c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis 14058c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // mKey is the key that identifies the cache entry. 14158c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis sp<Blob> mKey; 14258c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis 14358c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // mValue is the cached data associated with the key. 14458c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis sp<Blob> mValue; 14558c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis }; 14658c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis 14758c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // mMaxKeySize is the maximum key size that will be cached. Calls to 14858c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // BlobCache::set with a keySize parameter larger than mMaxKeySize will 14958c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // simply not add the key/value pair to the cache. 15058c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis const size_t mMaxKeySize; 15158c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis 15258c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // mMaxValueSize is the maximum value size that will be cached. Calls to 15358c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // BlobCache::set with a valueSize parameter larger than mMaxValueSize will 15458c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // simply not add the key/value pair to the cache. 15558c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis const size_t mMaxValueSize; 15658c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis 15758c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // mMaxTotalSize is the maximum size that all cache entries can occupy. This 15858c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // includes space for both keys and values. When a call to BlobCache::set 15958c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // would otherwise cause this limit to be exceeded, either the key/value 16058c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // pair passed to BlobCache::set will not be cached or other cache entries 16158c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // will be evicted from the cache to make room for the new entry. 16258c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis const size_t mMaxTotalSize; 16358c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis 16458c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // mTotalSize is the total combined size of all keys and values currently in 16558c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // the cache. 16658c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis size_t mTotalSize; 16758c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis 16858c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // mRandState is the pseudo-random number generator state. It is passed to 16958c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // nrand48 to generate random numbers when needed. It must be protected by 17058c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // mMutex. 17158c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis unsigned short mRandState[3]; 17258c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis 17358c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // mCacheEntries stores all the cache entries that are resident in memory. 17458c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // Cache entries are added to it by the 'set' method. 17558c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis SortedVector<CacheEntry> mCacheEntries; 17658c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis 17758c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // mMutex is used to synchronize access to all member variables. It must be 17858c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis // locked any time the member variables are written or read. 17958c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis Mutex mMutex; 18058c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis}; 18158c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis 18258c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis} 18358c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis 18458c8dd2aa9a8931a53923054679fb31fecc696c9Jamie Gennis#endif // ANDROID_BLOB_CACHE_H 185