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: 12 Pair() {} 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> 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: 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 157 private: 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
