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