blob: 0d908c694797c5a2ca3a95661bd1700d5c773b0e [file] [log] [blame]
#ifndef ANDROID_RENDERSCRIPT_MAP_H
#define ANDROID_RENDERSCRIPT_MAP_H
#include <stddef.h>
namespace android {
namespace renderscript {
template <class T1, class T2>
class Pair {
public:
Pair() {}
Pair(T1 f1, T2 f2) : first(f1), second(f2) {}
T1 first;
T2 second;
};
template <class T1, class T2>
Pair<T1, T2> make_pair(T1 first, T2 second) {
return Pair<T1, T2>(first, second);
}
#define MAP_LOG_NUM_BUCKET 8
#define MAP_NUM_BUCKET (1 << MAP_LOG_NUM_BUCKET)
#define MAP_NUM_BUCKET_MASK (MAP_NUM_BUCKET - 1)
template <class KeyType, class ValueType>
class Map {
private:
typedef Pair<KeyType, ValueType> MapEntry;
struct LinkNode {
MapEntry entry;
LinkNode* next;
};
public:
Map() : endIterator(MAP_NUM_BUCKET, nullptr, this) {
for (size_t i = 0; i < MAP_NUM_BUCKET; i++) { bucket[i] = nullptr; }
}
~Map() {
for (size_t i = 0; i < MAP_NUM_BUCKET; i++) {
LinkNode* p = bucket[i];
LinkNode* next;
while (p != nullptr) {
next = p->next;
delete p;
p = next;
}
}
}
ValueType& operator[](const KeyType& key) {
const size_t index = hash(key) & MAP_NUM_BUCKET_MASK;
LinkNode* node = bucket[index];
LinkNode* prev = nullptr;
while (node != nullptr) {
if (node->entry.first == key) {
return node->entry.second;
}
prev = node;
node = node->next;
}
node = new LinkNode();
node->entry.first = key;
node->next = nullptr;
if (prev == nullptr) {
bucket[index] = node;
} else {
prev->next = node;
}
return node->entry.second;
}
class iterator {
friend class Map;
public:
iterator& operator++() {
LinkNode* next;
next = node->next;
if (next != nullptr) {
node = next;
return *this;
}
while (++bucket_index < MAP_NUM_BUCKET) {
next = map->bucket[bucket_index];
if (next != nullptr) {
node = next;
return *this;
}
}
node = nullptr;
return *this;
}
bool operator==(const iterator& other) const {
return node == other.node && bucket_index == other.bucket_index &&
map == other.map;
}
bool operator!=(const iterator& other) const {
return node != other.node || bucket_index != other.bucket_index ||
map != other.map;
}
const MapEntry& operator*() const {
return node->entry;
}
protected:
iterator(size_t index, LinkNode* n, const Map* m) : bucket_index(index), node(n), map(m) {}
private:
size_t bucket_index;
LinkNode* node;
const Map* map;
};
iterator begin() const {
for (size_t i = 0; i < MAP_NUM_BUCKET; i++) {
LinkNode* node = bucket[i];
if (node != nullptr) {
return iterator(i, node, this);
}
}
return end();
}
const iterator& end() const { return endIterator; }
iterator begin() { return ((const Map*)this)->begin(); }
const iterator& end() { return endIterator; }
iterator find(const KeyType& key) const {
const size_t index = hash(key) & MAP_NUM_BUCKET_MASK;
LinkNode* node = bucket[index];
while (node != nullptr) {
if (node->entry.first == key) {
return iterator(index, node, this);
}
node = node->next;
}
return end();
}
private:
size_t hash(const KeyType& key) const { return ((size_t)key) >> 4; }
LinkNode* bucket[MAP_NUM_BUCKET];
const iterator endIterator;
};
} // namespace renderscript
} // namespace android
#endif // ANDROID_RENDERSCRIPT_MAP_H