blob: f68b85147e924f35b8baa85026158dcca303f2cc [file] [log] [blame]
Yang Niff2bb542015-02-02 14:33:47 -08001#ifndef ANDOID_RENDERSCRIPT_MAP_H
2#define ANDOID_RENDERSCRIPT_MAP_H
3
4#include <stddef.h>
5
6namespace android {
7namespace renderscript {
8
9template <class T1, class T2>
10class Pair {
11public:
12 Pair() {}
13 Pair(T1 f1, T2 f2) : first(f1), second(f2) {}
14
15 T1 first;
16 T2 second;
17};
18
19template <class T1, class T2>
20Pair<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
28template <class KeyType, class ValueType>
29class Map {
30private:
31 typedef Pair<KeyType, ValueType> MapEntry;
32
33 struct LinkNode {
34 MapEntry entry;
35 LinkNode* next;
36 };
37
38public:
39 Map() : endIterator(MAP_NUM_BUCKET, nullptr, this) {
40 for (size_t i = 0; i < MAP_NUM_BUCKET; i++) { bucket[i] = nullptr; }
41 }
42
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:
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
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
137 const iterator& end() const { return endIterator; }
138
139 iterator begin() { return ((const Map*)this)->begin(); }
140
141 const iterator& end() { return endIterator; }
142
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
157private:
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 // ANDOID_RENDERSCRIPT_MAP_H