1#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
168