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>
12 using namespace std;
13
14
15 static size_t mHits = 0;
16 static size_t mMisses = 0;
17 static size_t mCollisions = 0;
18
19 static const size_t MAX_CACHE_ENTRIES = 2048;
20 static const android::String16 TRUE16("1");
21 static const android::String16 FALSE16("0");
22
23 struct CacheEntry {
24 // concatenation of the relevant strings into a single instance
25 android::String16 hashedName;
26 uint32_t id;
27
CacheEntryCacheEntry28 CacheEntry() {}
CacheEntryCacheEntry29 CacheEntry(const android::String16& name, uint32_t resId) : hashedName(name), id(resId) { }
30 };
31
32 static map< uint32_t, CacheEntry > mIdMap;
33
34
35 // djb2; reasonable choice for strings when collisions aren't particularly important
hashround(uint32_t hash,int c)36 static inline uint32_t hashround(uint32_t hash, int c) {
37 return ((hash << 5) + hash) + c; /* hash * 33 + c */
38 }
39
hash(const android::String16 & hashableString)40 static 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
47 namespace android {
48
makeHashableName(const android::String16 & package,const android::String16 & type,const android::String16 & name,bool onlyPublic)49 static 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
lookup(const android::String16 & package,const android::String16 & type,const android::String16 & name,bool onlyPublic)60 uint32_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
store(const android::String16 & package,const android::String16 & type,const android::String16 & name,bool onlyPublic,uint32_t resId)86 uint32_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
dump()99 void 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