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