ResourceIdCache.cpp revision de898ff42912bd7ca1bfb099cd439562496765a4 
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: %zd\n", mIdMap.size());
102    printf("Hits:   %zd\n", mHits);
103    printf("Misses: %zd\n", mMisses);
104    printf("(Collisions: %zd)\n", mCollisions);
105}
106
107}
108