libutils: add a binary blob cache implementation.
This change adds an implementation of a cache that stores key/value
pairs of unstructured binary blobs.
Change-Id: Idd01fdabedfa3aed6d359a6efb0592967af52651
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