diff options
Diffstat (limited to 'kernel/hashlib.h')
| -rw-r--r-- | kernel/hashlib.h | 58 |
1 files changed, 51 insertions, 7 deletions
diff --git a/kernel/hashlib.h b/kernel/hashlib.h index 996bda38e..592d6e577 100644 --- a/kernel/hashlib.h +++ b/kernel/hashlib.h @@ -569,7 +569,7 @@ public: return entries[i].udata.second; } - T at(const K &key, const T &defval) const + const T& at(const K &key, const T &defval) const { int hash = do_hash(key); int i = do_lookup(key, hash); @@ -642,6 +642,7 @@ protected: entry_t() { } entry_t(const K &udata, int next) : udata(udata), next(next) { } + entry_t(K &&udata, int next) : udata(std::move(udata)), next(next) { } }; std::vector<int> hashtable; @@ -745,11 +746,24 @@ protected: int do_insert(const K &value, int &hash) { if (hashtable.empty()) { - entries.push_back(entry_t(value, -1)); + entries.emplace_back(value, -1); do_rehash(); hash = do_hash(value); } else { - entries.push_back(entry_t(value, hashtable[hash])); + entries.emplace_back(value, hashtable[hash]); + hashtable[hash] = entries.size() - 1; + } + return entries.size() - 1; + } + + int do_insert(K &&rvalue, int &hash) + { + if (hashtable.empty()) { + entries.emplace_back(std::forward<K>(rvalue), -1); + do_rehash(); + hash = do_hash(rvalue); + } else { + entries.emplace_back(std::forward<K>(rvalue), hashtable[hash]); hashtable[hash] = entries.size() - 1; } return entries.size() - 1; @@ -847,6 +861,22 @@ public: return std::pair<iterator, bool>(iterator(this, i), true); } + std::pair<iterator, bool> insert(K &&rvalue) + { + int hash = do_hash(rvalue); + int i = do_lookup(rvalue, hash); + if (i >= 0) + return std::pair<iterator, bool>(iterator(this, i), false); + i = do_insert(std::forward<K>(rvalue), hash); + return std::pair<iterator, bool>(iterator(this, i), true); + } + + template<typename... Args> + std::pair<iterator, bool> emplace(Args&&... args) + { + return insert(K(std::forward<Args>(args)...)); + } + int erase(const K &key) { int hash = do_hash(key); @@ -961,7 +991,21 @@ class idict pool<K, OPS> database; public: - typedef typename pool<K, OPS>::const_iterator const_iterator; + class const_iterator : public std::iterator<std::forward_iterator_tag, K> + { + friend class idict; + protected: + const idict &container; + int index; + const_iterator(const idict &container, int index) : container(container), index(index) { } + public: + const_iterator() { } + const_iterator operator++() { index++; return *this; } + bool operator==(const const_iterator &other) const { return index == other.index; } + bool operator!=(const const_iterator &other) const { return index != other.index; } + const K &operator*() const { return container[index]; } + const K *operator->() const { return &container[index]; } + }; int operator()(const K &key) { @@ -1019,9 +1063,9 @@ public: bool empty() const { return database.empty(); } void clear() { database.clear(); } - const_iterator begin() const { return database.begin(); } - const_iterator element(int n) const { return database.element(n); } - const_iterator end() const { return database.end(); } + const_iterator begin() const { return const_iterator(*this, offset); } + const_iterator element(int n) const { return const_iterator(*this, n); } + const_iterator end() const { return const_iterator(*this, offset + size()); } }; template<typename K, typename OPS> |