xref: /aosp_15_r20/frameworks/rs/rsMap.h (revision e1eccf28f96817838ad6867f7f39d2351ec11f56)
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