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