1d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate// 2d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate// Copyright 2012 The Android Open Source Project 3d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate// 4d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate// Manage a resource ID cache. 5d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate 6d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate#define LOG_TAG "ResourceIdCache" 7d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate 8d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate#include <utils/String16.h> 9d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate#include <utils/Log.h> 10d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate#include "ResourceIdCache.h" 11d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate#include <map> 12d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tateusing namespace std; 13d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate 14d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate 15d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tatestatic size_t mHits = 0; 16d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tatestatic size_t mMisses = 0; 17d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tatestatic size_t mCollisions = 0; 18d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate 19d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tatestatic const size_t MAX_CACHE_ENTRIES = 2048; 20d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tatestatic const android::String16 TRUE16("1"); 21d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tatestatic const android::String16 FALSE16("0"); 22d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate 23d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tatestruct CacheEntry { 24d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate // concatenation of the relevant strings into a single instance 25d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate android::String16 hashedName; 26d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate uint32_t id; 27d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate 28d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate CacheEntry() {} 29d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate CacheEntry(const android::String16& name, uint32_t resId) : hashedName(name), id(resId) { } 30d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate}; 31d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate 32d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tatestatic map< uint32_t, CacheEntry > mIdMap; 33d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate 34d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate 35d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate// djb2; reasonable choice for strings when collisions aren't particularly important 36d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tatestatic inline uint32_t hashround(uint32_t hash, int c) { 37d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate return ((hash << 5) + hash) + c; /* hash * 33 + c */ 38d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate} 39d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate 40d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tatestatic uint32_t hash(const android::String16& hashableString) { 41d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate uint32_t hash = 5381; 42d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate const char16_t* str = hashableString.string(); 43d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate while (int c = *str++) hash = hashround(hash, c); 44d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate return hash; 45d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate} 46d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate 47d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tatenamespace android { 48d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate 49d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tatestatic inline String16 makeHashableName(const android::String16& package, 50d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate const android::String16& type, 51d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate const android::String16& name, 52d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate bool onlyPublic) { 53d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate String16 hashable = String16(name); 54d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate hashable += type; 55d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate hashable += package; 56d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate hashable += (onlyPublic ? TRUE16 : FALSE16); 57d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate return hashable; 58d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate} 59d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate 60d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tateuint32_t ResourceIdCache::lookup(const android::String16& package, 61d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate const android::String16& type, 62d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate const android::String16& name, 63d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate bool onlyPublic) { 64d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate const String16 hashedName = makeHashableName(package, type, name, onlyPublic); 65d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate const uint32_t hashcode = hash(hashedName); 66d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate map<uint32_t, CacheEntry>::iterator item = mIdMap.find(hashcode); 67d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate if (item == mIdMap.end()) { 68d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate // cache miss 69d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate mMisses++; 70d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate return 0; 71d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate } 72d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate 73d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate // legit match? 74d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate if (hashedName == (*item).second.hashedName) { 75d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate mHits++; 76d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate return (*item).second.id; 77d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate } 78d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate 79d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate // collision 80d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate mCollisions++; 81d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate mIdMap.erase(hashcode); 82d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate return 0; 83d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate} 84d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate 85d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate// returns the resource ID being stored, for callsite convenience 86d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tateuint32_t ResourceIdCache::store(const android::String16& package, 87d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate const android::String16& type, 88d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate const android::String16& name, 89d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate bool onlyPublic, 90d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate uint32_t resId) { 91d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate if (mIdMap.size() < MAX_CACHE_ENTRIES) { 92d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate const String16 hashedName = makeHashableName(package, type, name, onlyPublic); 93d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate const uint32_t hashcode = hash(hashedName); 94d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate mIdMap[hashcode] = CacheEntry(hashedName, resId); 95d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate } 96d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate return resId; 97d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate} 98d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate 99d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tatevoid ResourceIdCache::dump() { 100d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate printf("ResourceIdCache dump:\n"); 101d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate printf("Size: %ld\n", mIdMap.size()); 102d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate printf("Hits: %ld\n", mHits); 103d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate printf("Misses: %ld\n", mMisses); 104d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate printf("(Collisions: %ld)\n", mCollisions); 105d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate} 106d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate 107d8dde13a63565dcd72bcf03a5088407b737ba793Christopher Tate} 108