1 #ifndef ANDROID_RENDERSCRIPT_MAP_H
2 #define ANDROID_RENDERSCRIPT_MAP_H
3 
4 #include <stddef.h>
5 
6 namespace android {
7 namespace renderscript {
8 
9 template <class T1, class T2>
10 class Pair {
11 public:
Pair()12     Pair() {}
Pair(T1 f1,T2 f2)13     Pair(T1 f1, T2 f2) : first(f1), second(f2) {}
14 
15     T1 first;
16     T2 second;
17 };
18 
19 template <class T1, class T2>
make_pair(T1 first,T2 second)20 Pair<T1, T2> make_pair(T1 first, T2 second) {
21     return Pair<T1, T2>(first, second);
22 }
23 
24 #define MAP_LOG_NUM_BUCKET 8
25 #define MAP_NUM_BUCKET (1 << MAP_LOG_NUM_BUCKET)
26 #define MAP_NUM_BUCKET_MASK (MAP_NUM_BUCKET - 1)
27 
28 template <class KeyType, class ValueType>
29 class Map {
30 private:
31     typedef Pair<KeyType, ValueType> MapEntry;
32 
33     struct LinkNode {
34         MapEntry entry;
35         LinkNode* next;
36     };
37 
38 public:
Map()39     Map() : endIterator(MAP_NUM_BUCKET, nullptr, this) {
40         for (size_t i = 0; i < MAP_NUM_BUCKET; i++) { bucket[i] = nullptr; }
41     }
42 
~Map()43     ~Map() {
44         for (size_t i = 0; i < MAP_NUM_BUCKET; i++) {
45             LinkNode* p = bucket[i];
46             LinkNode* next;
47             while (p != nullptr) {
48                 next = p->next;
49                 delete p;
50                 p = next;
51             }
52         }
53     }
54 
55     ValueType& operator[](const KeyType& key) {
56         const size_t index = hash(key) & MAP_NUM_BUCKET_MASK;
57         LinkNode* node = bucket[index];
58         LinkNode* prev = nullptr;
59 
60         while (node != nullptr) {
61             if (node->entry.first == key) {
62                 return node->entry.second;
63             }
64             prev = node;
65             node = node->next;
66         }
67 
68         node = new LinkNode();
69         node->entry.first = key;
70         node->next = nullptr;
71         if (prev == nullptr) {
72             bucket[index] = node;
73         } else {
74             prev->next = node;
75         }
76         return node->entry.second;
77     }
78 
79     class iterator {
80         friend class Map;
81     public:
82         iterator& operator++() {
83             LinkNode* next;
84 
85             next = node->next;
86             if (next != nullptr) {
87                 node = next;
88                 return *this;
89             }
90 
91             while (++bucket_index < MAP_NUM_BUCKET) {
92                 next = map->bucket[bucket_index];
93                 if (next != nullptr) {
94                     node = next;
95                     return *this;
96                 }
97             }
98 
99             node = nullptr;
100             return *this;
101         }
102 
103         bool operator==(const iterator& other) const {
104             return node == other.node && bucket_index == other.bucket_index &&
105                     map == other.map;
106         }
107 
108         bool operator!=(const iterator& other) const {
109             return node != other.node || bucket_index != other.bucket_index ||
110                     map != other.map;
111         }
112 
113         const MapEntry& operator*() const {
114             return node->entry;
115         }
116 
117     protected:
iterator(size_t index,LinkNode * n,const Map * m)118         iterator(size_t index, LinkNode* n, const Map* m) : bucket_index(index), node(n), map(m) {}
119 
120     private:
121         size_t bucket_index;
122         LinkNode* node;
123         const Map* map;
124     };
125 
begin()126     iterator begin() const {
127         for (size_t i = 0; i < MAP_NUM_BUCKET; i++) {
128             LinkNode* node = bucket[i];
129             if (node != nullptr) {
130                 return iterator(i, node, this);
131             }
132         }
133 
134         return end();
135     }
136 
end()137     const iterator& end() const { return endIterator; }
138 
begin()139     iterator begin() { return ((const Map*)this)->begin(); }
140 
end()141     const iterator& end() { return endIterator; }
142 
find(const KeyType & key)143     iterator find(const KeyType& key) const {
144         const size_t index = hash(key) & MAP_NUM_BUCKET_MASK;
145         LinkNode* node = bucket[index];
146 
147         while (node != nullptr) {
148             if (node->entry.first == key) {
149                 return iterator(index, node, this);
150             }
151             node = node->next;
152         }
153 
154         return end();
155     }
156 
157 private:
hash(const KeyType & key)158     size_t hash(const KeyType& key) const { return ((size_t)key) >> 4; }
159 
160     LinkNode* bucket[MAP_NUM_BUCKET];
161     const iterator endIterator;
162 };
163 
164 }  // namespace renderscript
165 }  // namespace android
166 
167 #endif  // ANDROID_RENDERSCRIPT_MAP_H
168