1282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski// 2282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski// Copyright 2012 The Android Open Source Project 3282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski// 4282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski// Manage a resource ID cache. 5282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 6282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski#define LOG_TAG "ResourceIdCache" 7282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 8282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski#include <utils/String16.h> 9282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski#include <utils/Log.h> 10282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski#include "ResourceIdCache.h" 11282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski#include <map> 12282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 13282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinskistatic size_t mHits = 0; 14282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinskistatic size_t mMisses = 0; 15282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinskistatic size_t mCollisions = 0; 16282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 17282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinskistatic const size_t MAX_CACHE_ENTRIES = 2048; 18282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinskistatic const android::String16 TRUE16("1"); 19282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinskistatic const android::String16 FALSE16("0"); 20282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 21282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinskistruct CacheEntry { 22282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // concatenation of the relevant strings into a single instance 23282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski android::String16 hashedName; 24282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski uint32_t id; 25282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 26282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski CacheEntry() {} 27282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski CacheEntry(const android::String16& name, uint32_t resId) : hashedName(name), id(resId) { } 28282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski}; 29282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 3040e8eefbedcafc51948945647d746daaee092f16Adam Lesinskistatic std::map< uint32_t, CacheEntry > mIdMap; 31282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 32282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 33282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski// djb2; reasonable choice for strings when collisions aren't particularly important 34282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinskistatic inline uint32_t hashround(uint32_t hash, int c) { 35282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return ((hash << 5) + hash) + c; /* hash * 33 + c */ 36282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski} 37282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 38282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinskistatic uint32_t hash(const android::String16& hashableString) { 39282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski uint32_t hash = 5381; 40282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski const char16_t* str = hashableString.string(); 41282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski while (int c = *str++) hash = hashround(hash, c); 42282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return hash; 43282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski} 44282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 45282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinskinamespace android { 46282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 47282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinskistatic inline String16 makeHashableName(const android::String16& package, 48282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski const android::String16& type, 49282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski const android::String16& name, 50282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski bool onlyPublic) { 51282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski String16 hashable = String16(name); 52282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski hashable += type; 53282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski hashable += package; 54282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski hashable += (onlyPublic ? TRUE16 : FALSE16); 55282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return hashable; 56282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski} 57282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 58282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinskiuint32_t ResourceIdCache::lookup(const android::String16& package, 59282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski const android::String16& type, 60282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski const android::String16& name, 61282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski bool onlyPublic) { 62282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski const String16 hashedName = makeHashableName(package, type, name, onlyPublic); 63282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski const uint32_t hashcode = hash(hashedName); 6440e8eefbedcafc51948945647d746daaee092f16Adam Lesinski std::map<uint32_t, CacheEntry>::iterator item = mIdMap.find(hashcode); 65282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (item == mIdMap.end()) { 66282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // cache miss 67282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski mMisses++; 68282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return 0; 69282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 70282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 71282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // legit match? 72282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (hashedName == (*item).second.hashedName) { 73282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski mHits++; 74282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return (*item).second.id; 75282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 76282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 77282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski // collision 78282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski mCollisions++; 79282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski mIdMap.erase(hashcode); 80282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return 0; 81282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski} 82282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 83282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski// returns the resource ID being stored, for callsite convenience 84282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinskiuint32_t ResourceIdCache::store(const android::String16& package, 85282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski const android::String16& type, 86282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski const android::String16& name, 87282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski bool onlyPublic, 88282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski uint32_t resId) { 89282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski if (mIdMap.size() < MAX_CACHE_ENTRIES) { 90282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski const String16 hashedName = makeHashableName(package, type, name, onlyPublic); 91282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski const uint32_t hashcode = hash(hashedName); 92282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski mIdMap[hashcode] = CacheEntry(hashedName, resId); 93282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski } 94282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski return resId; 95282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski} 96282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 97282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinskivoid ResourceIdCache::dump() { 98282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski printf("ResourceIdCache dump:\n"); 99de898ff42912bd7ca1bfb099cd439562496765a4Adam Lesinski printf("Size: %zd\n", mIdMap.size()); 100de898ff42912bd7ca1bfb099cd439562496765a4Adam Lesinski printf("Hits: %zd\n", mHits); 101de898ff42912bd7ca1bfb099cd439562496765a4Adam Lesinski printf("Misses: %zd\n", mMisses); 102de898ff42912bd7ca1bfb099cd439562496765a4Adam Lesinski printf("(Collisions: %zd)\n", mCollisions); 103282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski} 104282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski 105282e181b58cf72b6ca770dc7ca5f91f135444502Adam Lesinski} 106