diff options
Diffstat (limited to 'core')
| -rw-r--r-- | core/hash_map.h | 90 | ||||
| -rw-r--r-- | core/ordered_hash_map.h | 315 | ||||
| -rw-r--r-- | core/pair.h | 10 |
3 files changed, 377 insertions, 38 deletions
diff --git a/core/hash_map.h b/core/hash_map.h index 2d7249e2fc..3cf0f637f6 100644 --- a/core/hash_map.h +++ b/core/hash_map.h @@ -102,17 +102,31 @@ public: } }; -private: - struct Entry { + struct Element { + private: + friend class HashMap; uint32_t hash; - Entry *next; + Element *next; + Element() { next = 0; } Pair pair; - Entry() { next = 0; } + public: + const TKey &key() const { + return pair.key; + } + + TData &value() { + return pair.data; + } + + const TData &value() const { + return pair.value(); + } }; - Entry **hash_table; +private: + Element **hash_table; uint8_t hash_table_power; uint32_t elements; @@ -120,7 +134,7 @@ private: ERR_FAIL_COND(hash_table); - hash_table = memnew_arr(Entry *, (1 << MIN_HASH_TABLE_POWER)); + hash_table = memnew_arr(Element *, (1 << MIN_HASH_TABLE_POWER)); hash_table_power = MIN_HASH_TABLE_POWER; elements = 0; @@ -168,7 +182,7 @@ private: if (new_hash_table_power == -1) return; - Entry **new_hash_table = memnew_arr(Entry *, (1 << new_hash_table_power)); + Element **new_hash_table = memnew_arr(Element *, (1 << new_hash_table_power)); if (!new_hash_table) { ERR_PRINT("Out of Memory"); @@ -184,7 +198,7 @@ private: while (hash_table[i]) { - Entry *se = hash_table[i]; + Element *se = hash_table[i]; hash_table[i] = se->next; int new_pos = se->hash & ((1 << new_hash_table_power) - 1); se->next = new_hash_table[new_pos]; @@ -199,12 +213,12 @@ private: } /* I want to have only one function.. */ - _FORCE_INLINE_ const Entry *get_entry(const TKey &p_key) const { + _FORCE_INLINE_ const Element *get_element(const TKey &p_key) const { uint32_t hash = Hasher::hash(p_key); uint32_t index = hash & ((1 << hash_table_power) - 1); - Entry *e = hash_table[index]; + Element *e = hash_table[index]; while (e) { @@ -221,10 +235,10 @@ private: return NULL; } - Entry *create_entry(const TKey &p_key) { + Element *create_element(const TKey &p_key) { - /* if entry doesn't exist, create it */ - Entry *e = memnew(Entry); + /* if element doesn't exist, create it */ + Element *e = memnew(Element); ERR_FAIL_COND_V(!e, NULL); /* out of memory */ uint32_t hash = Hasher::hash(p_key); uint32_t index = hash & ((1 << hash_table_power) - 1); @@ -248,7 +262,7 @@ private: if (!p_t.hash_table || p_t.hash_table_power == 0) return; /* not copying from empty table */ - hash_table = memnew_arr(Entry *, 1 << p_t.hash_table_power); + hash_table = memnew_arr(Element *, 1 << p_t.hash_table_power); hash_table_power = p_t.hash_table_power; elements = p_t.elements; @@ -256,11 +270,11 @@ private: hash_table[i] = NULL; - const Entry *e = p_t.hash_table[i]; + const Element *e = p_t.hash_table[i]; while (e) { - Entry *le = memnew(Entry); /* local entry */ + Element *le = memnew(Element); /* local element */ *le = *e; /* copy data */ @@ -274,30 +288,30 @@ private: } public: - void set(const TKey &p_key, const TData &p_data) { - - set(Pair(p_key, p_data)); + Element *set(const TKey &p_key, const TData &p_data) { + return set(Pair(p_key, p_data)); } - void set(const Pair &p_pair) { + Element *set(const Pair &p_pair) { - Entry *e = NULL; + Element *e = NULL; if (!hash_table) make_hash_table(); // if no table, make one else - e = const_cast<Entry *>(get_entry(p_pair.key)); + e = const_cast<Element *>(get_element(p_pair.key)); /* if we made it up to here, the pair doesn't exist, create and assign */ if (!e) { - e = create_entry(p_pair.key); + e = create_element(p_pair.key); if (!e) - return; + return NULL; check_hash_table(); // perform mantenience routine } e->pair.data = p_pair.data; + return e; } bool has(const TKey &p_key) const { @@ -335,7 +349,7 @@ public: if (!hash_table) return NULL; - Entry *e = const_cast<Entry *>(get_entry(p_key)); + Element *e = const_cast<Element *>(get_element(p_key)); if (e) return &e->pair.data; @@ -348,7 +362,7 @@ public: if (!hash_table) return NULL; - const Entry *e = const_cast<Entry *>(get_entry(p_key)); + const Element *e = const_cast<Element *>(get_element(p_key)); if (e) return &e->pair.data; @@ -370,7 +384,7 @@ public: uint32_t hash = p_custom_hash; uint32_t index = hash & ((1 << hash_table_power) - 1); - Entry *e = hash_table[index]; + Element *e = hash_table[index]; while (e) { @@ -396,7 +410,7 @@ public: uint32_t hash = p_custom_hash; uint32_t index = hash & ((1 << hash_table_power) - 1); - const Entry *e = hash_table[index]; + const Element *e = hash_table[index]; while (e) { @@ -425,8 +439,8 @@ public: uint32_t hash = Hasher::hash(p_key); uint32_t index = hash & ((1 << hash_table_power) - 1); - Entry *e = hash_table[index]; - Entry *p = NULL; + Element *e = hash_table[index]; + Element *p = NULL; while (e) { /* checking hash first avoids comparing key, which may take longer */ @@ -463,16 +477,16 @@ public: } inline TData &operator[](const TKey &p_key) { //assignment - Entry *e = NULL; + Element *e = NULL; if (!hash_table) make_hash_table(); // if no table, make one else - e = const_cast<Entry *>(get_entry(p_key)); + e = const_cast<Element *>(get_element(p_key)); /* if we made it up to here, the pair doesn't exist, create */ if (!e) { - e = create_entry(p_key); + e = create_element(p_key); CRASH_COND(!e); check_hash_table(); // perform mantenience routine } @@ -510,14 +524,14 @@ public: } else { /* get the next key */ - const Entry *e = get_entry(*p_key); + const Element *e = get_element(*p_key); ERR_FAIL_COND_V(!e, NULL); /* invalid key supplied */ if (e->next) { /* if there is a "next" in the list, return that */ return &e->next->pair.key; } else { - /* go to next entries */ + /* go to next elements */ uint32_t index = e->hash & ((1 << hash_table_power) - 1); index++; for (int i = index; i < (1 << hash_table_power); i++) { @@ -552,7 +566,7 @@ public: while (hash_table[i]) { - Entry *e = hash_table[i]; + Element *e = hash_table[i]; hash_table[i] = e->next; memdelete(e); } @@ -582,7 +596,7 @@ public: return; for (int i = 0; i < (1 << hash_table_power); i++) { - Entry *e = hash_table[i]; + Element *e = hash_table[i]; while (e) { *p_pairs = &e->pair; p_pairs++; @@ -596,7 +610,7 @@ public: return; for (int i = 0; i < (1 << hash_table_power); i++) { - Entry *e = hash_table[i]; + Element *e = hash_table[i]; while (e) { p_keys->push_back(e->pair.key); e = e->next; diff --git a/core/ordered_hash_map.h b/core/ordered_hash_map.h new file mode 100644 index 0000000000..3e619d2b2e --- /dev/null +++ b/core/ordered_hash_map.h @@ -0,0 +1,315 @@ +/*************************************************************************/ +/* ordered_hash_map.h */ +/*************************************************************************/ +/* This file is part of: */ +/* GODOT ENGINE */ +/* http://www.godotengine.org */ +/*************************************************************************/ +/* Copyright (c) 2007-2017 Juan Linietsky, Ariel Manzur. */ +/* Copyright (c) 2014-2017 Godot Engine contributors (cf. AUTHORS.md) */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining */ +/* a copy of this software and associated documentation files (the */ +/* "Software"), to deal in the Software without restriction, including */ +/* without limitation the rights to use, copy, modify, merge, publish, */ +/* distribute, sublicense, and/or sell copies of the Software, and to */ +/* permit persons to whom the Software is furnished to do so, subject to */ +/* the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be */ +/* included in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ +/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ +/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/ +/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ +/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ +/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ +/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ +/*************************************************************************/ +#ifndef ORDERED_HASH_MAP_H +#define ORDERED_HASH_MAP_H + +#include "hash_map.h" +#include "list.h" +#include "pair.h" + +/** + * A hash map which allows to iterate elements in insertion order. + * Insertion, lookup, deletion have O(1) complexity. + * The API aims to be consistent with Map rather than HashMap, because the + * former is more frequently used and is more coherent with the rest of the + * codebase. + * Deletion during iteration is safe and will preserve the order. + */ +template <class K, class V, class Hasher = HashMapHasherDefault, class Comparator = HashMapComparatorDefault<K>, uint8_t MIN_HASH_TABLE_POWER = 3, uint8_t RELATIONSHIP = 8> +class OrderedHashMap { + typedef List<Pair<const K *, V> > InternalList; + typedef HashMap<K, typename InternalList::Element *, Hasher, Comparator, MIN_HASH_TABLE_POWER, RELATIONSHIP> InternalMap; + + InternalList list; + InternalMap map; + +public: + class Element { + friend class OrderedHashMap<K, V, Hasher, Comparator, MIN_HASH_TABLE_POWER, RELATIONSHIP>; + + typename InternalList::Element *list_element; + typename InternalList::Element *next_element; + typename InternalList::Element *prev_element; + + Element(typename InternalList::Element *p_element) { + list_element = p_element; + + if (list_element) { + next_element = list_element->next(); + prev_element = list_element->prev(); + } + } + + public: + _FORCE_INLINE_ Element() + : list_element(NULL), next_element(NULL), prev_element(NULL) { + } + + Element next() const { + return Element(next_element); + } + + Element prev() const { + return Element(prev_element); + } + + Element(const Element &other) + : list_element(other.list_element), + prev_element(other.prev_element), + next_element(other.next_element) { + } + + Element &operator=(const Element &other) { + list_element = other.list_element; + next_element = other.next_element; + prev_element = other.prev_element; + return *this; + } + + friend bool operator==(const Element &, const Element &); + friend bool operator!=(const Element &, const Element &); + + operator bool() const { + return (list_element != NULL); + } + + const K &key() const { + CRASH_COND(!list_element); + return *(list_element->get().first); + }; + + V &value() { + CRASH_COND(!list_element); + return list_element->get().second; + }; + + const V &value() const { + CRASH_COND(!list_element); + return list_element->get().second; + }; + + V &get() { + CRASH_COND(!list_element); + return list_element->get().second; + }; + + const V &get() const { + CRASH_COND(!list_element); + return list_element->get().second; + }; + }; + + class ConstElement { + friend class OrderedHashMap<K, V, Hasher, Comparator, MIN_HASH_TABLE_POWER, RELATIONSHIP>; + + const typename InternalList::Element *list_element; + + ConstElement(const typename InternalList::Element *p_element) + : list_element(p_element) { + } + + public: + _FORCE_INLINE_ ConstElement() + : list_element(NULL) { + } + + ConstElement(const ConstElement &other) + : list_element(other.list_element) { + } + + ConstElement &operator=(const ConstElement &other) { + list_element = other.list_element; + return *this; + } + + ConstElement next() const { + return ConstElement(list_element ? list_element->next() : NULL); + } + + ConstElement prev() const { + return ConstElement(list_element ? list_element->prev() : NULL); + } + + friend bool operator==(const ConstElement &, const ConstElement &); + friend bool operator!=(const ConstElement &, const ConstElement &); + + operator bool() const { + return (list_element != NULL); + } + + const K &key() const { + CRASH_COND(!list_element); + return *(list_element->get().first); + }; + + const V &value() const { + CRASH_COND(!list_element); + return list_element->get().second; + }; + + const V &get() const { + CRASH_COND(!list_element); + return list_element->get().second; + }; + }; + + ConstElement find(const K &p_key) const { + typename InternalList::Element **list_element = map.getptr(p_key); + if (list_element) { + return ConstElement(*list_element); + } + return ConstElement(NULL); + } + + Element find(const K &p_key) { + typename InternalList::Element **list_element = map.getptr(p_key); + if (list_element) { + return Element(*list_element); + } + return Element(NULL); + } + + Element insert(const K &p_key, const V &p_value) { + typename InternalList::Element **list_element = map.getptr(p_key); + if (list_element) { + (*list_element)->get().second = p_value; + return Element(*list_element); + } + typename InternalList::Element *new_element = list.push_back(Pair<const K *, V>(NULL, p_value)); + typename InternalMap::Element *e = map.set(p_key, new_element); + new_element->get().first = &e->key(); + + return Element(new_element); + } + + void erase(Element &p_element) { + map.erase(p_element.key()); + list.erase(p_element.list_element); + p_element.list_element = NULL; + } + + bool erase(const K &p_key) { + typename InternalList::Element **list_element = map.getptr(p_key); + if (list_element) { + list.erase(*list_element); + map.erase(p_key); + return true; + } + return false; + } + + inline bool has(const K &p_key) const { + return map.has(p_key); + } + + const V &operator[](const K &p_key) const { + ConstElement e = find(p_key); + CRASH_COND(!e); + return e.value(); + } + + V &operator[](const K &p_key) { + Element e = find(p_key); + if (!e) { + // consistent with Map behaviour + e = insert(p_key, V()); + } + return e.value(); + } + + inline Element front() { + return Element(list.front()); + } + + inline Element back() { + return Element(list.back()); + } + + inline ConstElement front() const { + return ConstElement(list.front()); + } + + inline ConstElement back() const { + return ConstElement(list.back()); + } + + inline bool empty() const { return list.empty(); } + inline int size() const { return list.size(); } + + void clear() { + map.clear(); + list.clear(); + } + +private: + void _copy_from(const OrderedHashMap &p_map) { + for (ConstElement E = p_map.front(); E; E = E.next()) { + insert(E.key(), E.value()); + } + } + +public: + void operator=(const OrderedHashMap &p_map) { + _copy_from(p_map); + } + + OrderedHashMap(const OrderedHashMap &p_map) { + _copy_from(p_map); + } + + _FORCE_INLINE_ OrderedHashMap() { + } +}; + +template <class K, class V, class Hasher, class Comparator, uint8_t MIN_HASH_TABLE_POWER, uint8_t RELATIONSHIP> +bool operator==(const typename OrderedHashMap<K, V, Hasher, Comparator, MIN_HASH_TABLE_POWER, RELATIONSHIP>::Element &first, + const typename OrderedHashMap<K, V, Hasher, Comparator, MIN_HASH_TABLE_POWER, RELATIONSHIP>::Element &second) { + return (first.list_element == second.list_element); +} + +template <class K, class V, class Hasher, class Comparator, uint8_t MIN_HASH_TABLE_POWER, uint8_t RELATIONSHIP> +bool operator!=(const typename OrderedHashMap<K, V, Hasher, Comparator, MIN_HASH_TABLE_POWER, RELATIONSHIP>::Element &first, + const typename OrderedHashMap<K, V, Hasher, Comparator, MIN_HASH_TABLE_POWER, RELATIONSHIP>::Element &second) { + return (first.list_element != second.list_element); +} + +template <class K, class V, class Hasher, class Comparator, uint8_t MIN_HASH_TABLE_POWER, uint8_t RELATIONSHIP> +bool operator==(const typename OrderedHashMap<K, V, Hasher, Comparator, MIN_HASH_TABLE_POWER, RELATIONSHIP>::ConstElement &first, + const typename OrderedHashMap<K, V, Hasher, Comparator, MIN_HASH_TABLE_POWER, RELATIONSHIP>::ConstElement &second) { + return (first.list_element == second.list_element); +} + +template <class K, class V, class Hasher, class Comparator, uint8_t MIN_HASH_TABLE_POWER, uint8_t RELATIONSHIP> +bool operator!=(const typename OrderedHashMap<K, V, Hasher, Comparator, MIN_HASH_TABLE_POWER, RELATIONSHIP>::ConstElement &first, + const typename OrderedHashMap<K, V, Hasher, Comparator, MIN_HASH_TABLE_POWER, RELATIONSHIP>::ConstElement &second) { + return (first.list_element != second.list_element); +} + +#endif // ORDERED_HASH_MAP_H
\ No newline at end of file diff --git a/core/pair.h b/core/pair.h index d4b1897537..620f9e2108 100644 --- a/core/pair.h +++ b/core/pair.h @@ -44,6 +44,16 @@ struct Pair { }; template <class F, class S> +bool operator==(const Pair<F, S> &pair, const Pair<F, S> &other) { + return (pair.first == other.first) && (pair.second == other.second); +} + +template <class F, class S> +bool operator!=(const Pair<F, S> &pair, const Pair<F, S> &other) { + return (pair.first != other.first) || (pair.second != other.second); +} + +template <class F, class S> struct PairSort { bool operator()(const Pair<F, S> &A, const Pair<F, S> &B) const { |