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