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