Index: uspace/lib/cpp/include/internal/hash_table.hpp =================================================================== --- uspace/lib/cpp/include/internal/hash_table.hpp (revision 65dde9940c2add5780dc916eb2c33c1db66c0a64) +++ uspace/lib/cpp/include/internal/hash_table.hpp (revision 9751280343dac2ca495ff93c50b4675691bcd6fc) @@ -32,4 +32,7 @@ #include #include +#include +#include +#include #include #include @@ -47,903 +50,9 @@ * and two proxies that either use plain Key type or a pair * of a key and a value. + * Additionally, we will use policies to represent both single + * and multi variants of these containers at once. * Note: I am aware the naming is very unimaginative here, * not my strong side :) */ - - template - struct key_value_key_extractor - { - const Key& operator()(const pair& p) const noexcept - { - return p.first; - } - }; - - template - struct key_no_value_key_extractor - { - Key& operator()(Key& k) const noexcept - { - return k; - } - - const Key& operator()(const Key& k) const noexcept - { - return k; - } - }; - - template - struct hash_table_bucket - { - /** - * Note: We use a doubly linked list because - * we need to use hints, which point to the - * element after the hinted spot. - */ - - list_node* head; - - hash_table_bucket() - : head{} - { /* DUMMY BODY */ } - - Size size() const noexcept - { - auto current = head; - Size res{}; - - do - { - ++res; - current = current->next; - } - while (current != head); - - return res; - } - - void append(list_node* node) - { - if (!head) - head = node; - else - head->append(node); - } - - void prepend(list_node* node) - { - if (!head) - head = node; - else - head->prepend(node); - } - - void clear() - { - if (!head) - return; - - auto current = head; - do - { - auto tmp = current; - current = current->next; - delete tmp; - } - while (current != head); - - head = nullptr; - } - - ~hash_table_bucket() - { - clear(); - } - }; - - struct hash_single_policy - { - template - static typename Table::size_type count(const Table& table, const Key& key) - { - return table.find(key) == table.end() ? 0 : 1; - } - - template - static typename Table::place_type find_insertion_spot(const Table& table, const Key& key) - { - auto idx = table.get_bucket_idx_(key); - return make_tuple( - &table.table_[idx], - table.table_[idx].head, - idx - ); - } - - template - static typename Table::size_type erase(Table& table, const Key& key) - { - auto idx = table.get_bucket_idx_(key); - auto head = table.table_[idx].head; - auto current = head; - - do - { - if (table.keys_equal(key, current->value)) - { - --table.size_; - - if (current == head) - { - if (current->next != head) - table.table_[idx].head = current->next; - else - table.table_[idx].head = nullptr; - } - - current->unlink(); - delete current; - - return 1; - } - else - current = current->next; - } - while (current != head); - - return 0; - } - - template - static pair< - typename Table::iterator, - typename Table::iterator - > equal_range(Table& table, const Key& key) - { - auto it = table.find(key); - return make_pair(it, ++it); - } - - template - static pair< - typename Table::const_iterator, - typename Table::const_iterator - > equal_range_const(const Table& table, const Key& key) - { // Note: We cannot overload by return type, so we use a different name. - auto it = table.find(key); - return make_pair(it, ++it); - } - - /** - * Note: We have to duplicate code for emplace, insert(const&) - * and insert(&&) here, because the node (which makes distinction - * between the arguments) is only created if the value isn't - * in the table already. - */ - - template - static pair< - typename Table::iterator, bool - > emplace(Table& table, Args&&... args) - { - using value_type = typename Table::value_type; - using node_type = typename Table::node_type; - using iterator = typename Table::iterator; - - table.increment_size(); - - auto val = value_type{forward(args)...}; - const auto& key = table.get_key(val); - auto [bucket, target, idx] = table.find_insertion_spot(key); - - if (!bucket) - return make_pair(table.end(), false); - - if (target && table.keys_equal(key, target->value)) - { - table.decrement_size(); - - return make_pair( - iterator{ - table.table(), idx, table.bucket_count(), - target - }, - false - ); - } - else - { - auto node = new node_type{move(val)}; - bucket->prepend(node); - - return make_pair(iterator{ - table.table(), idx, - table.bucket_count(), - node - }, true); - } - } - - template - static pair< - typename Table::iterator, bool - > insert(Table& table, const Value& val) - { - using node_type = typename Table::node_type; - using iterator = typename Table::iterator; - - table.increment_size(); - - const auto& key = table.get_key(val); - auto [bucket, target, idx] = table.find_insertion_spot(key); - - if (!bucket) - return make_pair(table.end(), false); - - if (target && table.keys_equal(key, target->value)) - { - table.decrement_size(); - - return make_pair( - iterator{ - table.table(), idx, table.bucket_count(), - target - }, - false - ); - } - else - { - auto node = new node_type{val}; - bucket->prepend(node); - - return make_pair(iterator{ - table.table(), idx, - table.bucket_count(), - node - }, true); - } - } - - template - static pair< - typename Table::iterator, bool - > insert(Table& table, Value&& val) - { - using value_type = typename Table::value_type; - using node_type = typename Table::node_type; - using iterator = typename Table::iterator; - - table.increment_size(); - - const auto& key = table.get_key(val); - auto [bucket, target, idx] = table.find_insertion_spot(key); - - if (!bucket) - return make_pair(table.end(), false); - - if (target && table.keys_equal(key, target->value)) - { - table.decrement_size(); - - return make_pair( - iterator{ - table.table(), idx, table.bucket_count(), - target - }, - false - ); - } - else - { - auto node = new node_type{forward(val)}; - bucket->prepend(node); - - return make_pair(iterator{ - table.table(), idx, - table.bucket_count(), - node - }, true); - } - } - }; - - struct hash_multi_policy - { - template - static typename Table::size_type count(const Table& table, const Key& key) - { - auto head = table.table_[get_bucket_idx_(key)].head; - if (!head) - return 0; - - auto current = head; - typename Table::size_type res = 0; - do - { - if (table.keys_equal(key, current->value)) - ++res; - - current = current->next; - } - while (current != head); - - return res; - } - - template - static typename Table::place_type find_insertion_spot(const Table& table, const Key& key) - { - auto idx = table.get_bucket_idx_(key); - auto head = table.table_[idx].head; - - if (head) - { - auto current = head; - do - { - if (table.keys_equal(key, current->value)) - { - return make_tuple( - &table.table_[idx], - current, - idx - ); - } - - current = current->next; - } while (current != head); - } - - return make_tuple( - &table.table_[idx], - table.table_[idx].head, - idx - ); - } - - template - static typename Table::size_type erase(Table& table, const Key& key) - { - auto idx = table.get_bucket_idx_(key); - auto it = table.begin(it); - typename Table::size_type res{}; - - while (it != table.end(it)) - { - if (table.keys_equal(key, *it)) - { - while (table.keys_equal(key, *it)) - { - auto node = it.node(); - ++it; - ++res; - - node.unlink(); - delete node; - --table.size_; - } - - // Elements with equal keys are next to each other. - return res; - } - - ++it; - } - - return res; - } - - template - static pair< - typename Table::iterator, - typename Table::iterator - > equal_range(Table& table, const Key& key) - { - auto first = table.find(key); - if (first == table.end()) - return make_pair(table.end(), table.end()); - - auto last = first; - do - { - ++last; - } while (table.keys_equal(key, *last)); - - return make_pair(first, last); - } - - template - static pair< - typename Table::const_iterator, - typename Table::const_iterator - > equal_range_const(const Table& table, const Key& key) - { - auto first = table.find(key); - if (first == table.end()) - return make_pair(table.end(), table.end()); - - auto last = first; - do - { - ++last; - } while (table.keys_equal(key, *last)); - - return make_pair(first, last); - } - - template - static pair< - typename Table::iterator, bool - > emplace(Table& table, Args&&... args) - { - using node_type = typename Table::node_type; - - auto node = new node_type{forward(args)...}; - - return insert(table, node); - } - - template - static pair< - typename Table::iterator, bool - > insert(Table& table, const Value& val) - { - using node_type = typename Table::node_type; - - auto node = new node_type{val}; - - return insert(table, node); - } - - template - static pair< - typename Table::iterator, bool - > insert(Table& table, Value&& val) - { - using value_type = typename Table::value_type; - using node_type = typename Table::node_type; - - auto node = new node_type{forward(val)}; - - return insert(table, node); - } - - template - static pair< - typename Table::iterator, bool - > insert(Table& table, typename Table::node_type* node) - { - using iterator = typename Table::iterator; - - table.increment_size(); - - const auto& key = table.get_key(node->value); - auto [bucket, target, idx] = table.find_insertion_spot(key); - - if (!bucket) - return make_pair(table.end(), false); - - if (target && table.keys_equal(key, target->value)) - target->append(node); - else - bucket->prepend(node); - - return make_pair(iterator{ - table.table(), idx, - table.bucket_count(), - node - }, true); - } - }; - - template - class hash_table_const_iterator - { - public: - using value_type = Value; - using size_type = Size; - using const_reference = ConstReference; - using const_pointer = ConstPointer; - using difference_type = ptrdiff_t; - - using iterator_category = forward_iterator_tag; - - hash_table_const_iterator(const hash_table_bucket* table = nullptr, - size_type idx = size_type{}, size_type max_idx = size_type{}, - const list_node* current = nullptr) - : table_{table}, idx_{idx}, max_idx_{max_idx}, current_{current} - { /* DUMMY BODY */ } - - hash_table_const_iterator(const hash_table_const_iterator&) = default; - hash_table_const_iterator& operator=(const hash_table_const_iterator&) = default; - - const_reference operator*() const - { - return current_->value; - } - - const_pointer operator->() const - { - return ¤t_->value; - } - - hash_table_const_iterator& operator++() - { - current_ = current_->next; - if (current_ == table_[idx_].head) - { - if (idx_ < max_idx_) - { - while (!table_[++idx_].head && idx_ < max_idx_) - { /* DUMMY BODY */ } - - if (idx_ < max_idx_) - current_ = table_[idx_].head; - else - current_ = nullptr; - } - else - current_ = nullptr; - } - - return *this; - } - - hash_table_const_iterator operator++(int) - { - auto tmp_current = current_; - auto tmp_idx = idx_; - - current_ = current_->next; - if (current_ == table_[idx_].head) - { - if (idx_ < max_idx_) - { - while (!table_[++idx_].head && idx_ < max_idx_) - { /* DUMMY BODY */ } - - if (idx_ < max_idx_) - current_ = table_[idx_].head; - else - current_ = nullptr; - } - else - current_ = nullptr; - } - - return hash_table_const_iterator{ - table_, tmp_idx, max_idx_, tmp_current - }; - } - - list_node* node() - { - return const_cast*>(current_); - } - - const list_node* node() const - { - return current_; - } - - size_type idx() const - { - return idx_; - } - - private: - const hash_table_bucket* table_; - size_type idx_; - size_type max_idx_; - const list_node* current_; - }; - - template - bool operator==(const hash_table_const_iterator& lhs, - const hash_table_const_iterator& rhs) - { - return lhs.node() == rhs.node(); - } - - template - bool operator!=(const hash_table_const_iterator& lhs, - const hash_table_const_iterator& rhs) - { - return !(lhs == rhs); - } - - template - class hash_table_iterator - { - public: - using value_type = Value; - using size_type = Size; - using reference = Reference; - using pointer = Pointer; - using difference_type = ptrdiff_t; - - using iterator_category = forward_iterator_tag; - - hash_table_iterator(hash_table_bucket* table = nullptr, - size_type idx = size_type{}, size_type max_idx = size_type{}, - list_node* current = nullptr) - : table_{table}, idx_{idx}, max_idx_{max_idx}, current_{current} - { /* DUMMY BODY */ } - - hash_table_iterator(const hash_table_iterator&) = default; - hash_table_iterator& operator=(const hash_table_iterator&) = default; - - reference operator*() - { - return current_->value; - } - - pointer operator->() - { - return ¤t_->value; - } - - hash_table_iterator& operator++() - { - current_ = current_->next; - if (current_ == table_[idx_].head) - { - if (idx_ < max_idx_) - { - while (!table_[++idx_].head && idx_ < max_idx_) - { /* DUMMY BODY */ } - - if (idx_ < max_idx_) - current_ = table_[idx_].head; - else - current_ = nullptr; - } - else - current_ = nullptr; - } - - return *this; - } - - hash_table_iterator operator++(int) - { - auto tmp_current = current_; - auto tmp_idx = idx_; - - current_ = current_->next; - if (current_ == table_[idx_].head) - { - if (idx_ < max_idx_) - { - while (!table_[++idx_].head && idx_ < max_idx_) - { /* DUMMY BODY */ } - - if (idx_ < max_idx_) - current_ = table_[idx_].head; - else - current_ = nullptr; - } - else - current_ = nullptr; - } - - return hash_table_iterator{ - table_, tmp_idx, max_idx_, tmp_current - }; - } - - list_node* node() - { - return current_; - } - - const list_node* node() const - { - return current_; - } - - size_type idx() const - { - return idx_; - } - - template - operator hash_table_const_iterator< - Value, ConstRef, ConstPtr, Size - >() const - { - return hash_table_const_iterator{ - table_, idx_, max_idx_, current_ - }; - } - - private: - hash_table_bucket* table_; - size_type idx_; - size_type max_idx_; - list_node* current_; - }; - - template - bool operator==(const hash_table_iterator& lhs, - const hash_table_iterator& rhs) - { - return lhs.node() == rhs.node(); - } - - template - bool operator!=(const hash_table_iterator& lhs, - const hash_table_iterator& rhs) - { - return !(lhs == rhs); - } - - template - class hash_table_const_local_iterator - { - public: - using value_type = Value; - using const_reference = ConstReference; - using const_pointer = ConstPointer; - using difference_type = ptrdiff_t; - - using iterator_category = forward_iterator_tag; - - // TODO: requirement for forward iterator is default constructibility, fix others! - hash_table_const_local_iterator(const list_node* head = nullptr, - const list_node* current = nullptr) - : head_{head}, current_{current} - { /* DUMMY BODY */ } - - hash_table_const_local_iterator(const hash_table_const_local_iterator&) = default; - hash_table_const_local_iterator& operator=(const hash_table_const_local_iterator&) = default; - - const_reference operator*() const - { - return current_->value; - } - - const_pointer operator->() const - { - return ¤t_->value; - } - - hash_table_const_local_iterator& operator++() - { - current_ = current_->next; - if (current_ == head_) - current_ = nullptr; - - return *this; - } - - hash_table_const_local_iterator operator++(int) - { - auto tmp = current_; - current_ = current_->next; - if (current_ == head_) - current_ = nullptr; - - return hash_table_const_local_iterator{head_, tmp}; - } - - - list_node* node() - { - return const_cast*>(current_); - } - - const list_node* node() const - { - return current_; - } - - private: - const list_node* head_; - const list_node* current_; - }; - - template - bool operator==(const hash_table_const_local_iterator& lhs, - const hash_table_const_local_iterator& rhs) - { - return lhs.node() == rhs.node(); - } - - template - bool operator!=(const hash_table_const_local_iterator& lhs, - const hash_table_const_local_iterator& rhs) - { - return !(lhs == rhs); - } - - template - class hash_table_local_iterator - { - public: - using value_type = Value; - using reference = Reference; - using pointer = Pointer; - using difference_type = ptrdiff_t; - - using iterator_category = forward_iterator_tag; - - hash_table_local_iterator(list_node* head = nullptr, - list_node* current = nullptr) - : head_{head}, current_{current} - { /* DUMMY BODY */ } - - hash_table_local_iterator(const hash_table_local_iterator&) = default; - hash_table_local_iterator& operator=(const hash_table_local_iterator&) = default; - - reference operator*() - { - return current_->value; - } - - pointer operator->() - { - return ¤t_->value; - } - - hash_table_local_iterator& operator++() - { - current_ = current_->next; - if (current_ == head_) - current_ = nullptr; - - return *this; - } - - hash_table_local_iterator operator++(int) - { - auto tmp = current_; - current_ = current_->next; - if (current_ == head_) - current_ = nullptr; - - return hash_table_local_iterator{head_, tmp}; - } - - list_node* node() - { - return current_; - } - - const list_node* node() const - { - return current_; - } - - template - operator hash_table_const_local_iterator< - Value, ConstRef, ConstPtr - >() const - { - return hash_table_const_local_iterator< - value_type, ConstRef, ConstPtr - >{head_, current_}; - } - - private: - list_node* head_; - list_node* current_; - }; - - template - bool operator==(const hash_table_local_iterator& lhs, - const hash_table_local_iterator& rhs) - { - return lhs.node() == rhs.node(); - } - - template - bool operator!=(const hash_table_local_iterator& lhs, - const hash_table_local_iterator& rhs) - { - return !(lhs == rhs); - } template< Index: uspace/lib/cpp/include/internal/hash_table_bucket.hpp =================================================================== --- uspace/lib/cpp/include/internal/hash_table_bucket.hpp (revision 9751280343dac2ca495ff93c50b4675691bcd6fc) +++ uspace/lib/cpp/include/internal/hash_table_bucket.hpp (revision 9751280343dac2ca495ff93c50b4675691bcd6fc) @@ -0,0 +1,106 @@ +/* + * Copyright (c) 2018 Jaroslav Jindrak + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef LIBCPP_INTERNAL_HASH_TABLE_BUCKET +#define LIBCPP_INTERNAL_HASH_TABLE_BUCKET + +#include + +namespace std::aux +{ + template + struct hash_table_bucket + { + /** + * Note: We use a doubly linked list because + * we need to use hints, which point to the + * element after the hinted spot. + */ + + list_node* head; + + hash_table_bucket() + : head{} + { /* DUMMY BODY */ } + + Size size() const noexcept + { + auto current = head; + Size res{}; + + do + { + ++res; + current = current->next; + } + while (current != head); + + return res; + } + + void append(list_node* node) + { + if (!head) + head = node; + else + head->append(node); + } + + void prepend(list_node* node) + { + if (!head) + head = node; + else + head->prepend(node); + } + + void clear() + { + if (!head) + return; + + auto current = head; + do + { + auto tmp = current; + current = current->next; + delete tmp; + } + while (current != head); + + head = nullptr; + } + + ~hash_table_bucket() + { + clear(); + } + }; +} + +#endif Index: uspace/lib/cpp/include/internal/hash_table_iterators.hpp =================================================================== --- uspace/lib/cpp/include/internal/hash_table_iterators.hpp (revision 9751280343dac2ca495ff93c50b4675691bcd6fc) +++ uspace/lib/cpp/include/internal/hash_table_iterators.hpp (revision 9751280343dac2ca495ff93c50b4675691bcd6fc) @@ -0,0 +1,447 @@ +/* + * Copyright (c) 2018 Jaroslav Jindrak + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef LIBCPP_INTERNAL_HASH_TABLE_ITERATORS +#define LIBCPP_INTERNAL_HASH_TABLE_ITERATORS + +#include +#include +#include + +namespace std::aux +{ + template + class hash_table_const_iterator + { + public: + using value_type = Value; + using size_type = Size; + using const_reference = ConstReference; + using const_pointer = ConstPointer; + using difference_type = ptrdiff_t; + + using iterator_category = forward_iterator_tag; + + hash_table_const_iterator(const hash_table_bucket* table = nullptr, + size_type idx = size_type{}, size_type max_idx = size_type{}, + const list_node* current = nullptr) + : table_{table}, idx_{idx}, max_idx_{max_idx}, current_{current} + { /* DUMMY BODY */ } + + hash_table_const_iterator(const hash_table_const_iterator&) = default; + hash_table_const_iterator& operator=(const hash_table_const_iterator&) = default; + + const_reference operator*() const + { + return current_->value; + } + + const_pointer operator->() const + { + return ¤t_->value; + } + + hash_table_const_iterator& operator++() + { + current_ = current_->next; + if (current_ == table_[idx_].head) + { + if (idx_ < max_idx_) + { + while (!table_[++idx_].head && idx_ < max_idx_) + { /* DUMMY BODY */ } + + if (idx_ < max_idx_) + current_ = table_[idx_].head; + else + current_ = nullptr; + } + else + current_ = nullptr; + } + + return *this; + } + + hash_table_const_iterator operator++(int) + { + auto tmp_current = current_; + auto tmp_idx = idx_; + + current_ = current_->next; + if (current_ == table_[idx_].head) + { + if (idx_ < max_idx_) + { + while (!table_[++idx_].head && idx_ < max_idx_) + { /* DUMMY BODY */ } + + if (idx_ < max_idx_) + current_ = table_[idx_].head; + else + current_ = nullptr; + } + else + current_ = nullptr; + } + + return hash_table_const_iterator{ + table_, tmp_idx, max_idx_, tmp_current + }; + } + + list_node* node() + { + return const_cast*>(current_); + } + + const list_node* node() const + { + return current_; + } + + size_type idx() const + { + return idx_; + } + + private: + const hash_table_bucket* table_; + size_type idx_; + size_type max_idx_; + const list_node* current_; + }; + + template + bool operator==(const hash_table_const_iterator& lhs, + const hash_table_const_iterator& rhs) + { + return lhs.node() == rhs.node(); + } + + template + bool operator!=(const hash_table_const_iterator& lhs, + const hash_table_const_iterator& rhs) + { + return !(lhs == rhs); + } + + template + class hash_table_iterator + { + public: + using value_type = Value; + using size_type = Size; + using reference = Reference; + using pointer = Pointer; + using difference_type = ptrdiff_t; + + using iterator_category = forward_iterator_tag; + + hash_table_iterator(hash_table_bucket* table = nullptr, + size_type idx = size_type{}, size_type max_idx = size_type{}, + list_node* current = nullptr) + : table_{table}, idx_{idx}, max_idx_{max_idx}, current_{current} + { /* DUMMY BODY */ } + + hash_table_iterator(const hash_table_iterator&) = default; + hash_table_iterator& operator=(const hash_table_iterator&) = default; + + reference operator*() + { + return current_->value; + } + + pointer operator->() + { + return ¤t_->value; + } + + hash_table_iterator& operator++() + { + current_ = current_->next; + if (current_ == table_[idx_].head) + { + if (idx_ < max_idx_) + { + while (!table_[++idx_].head && idx_ < max_idx_) + { /* DUMMY BODY */ } + + if (idx_ < max_idx_) + current_ = table_[idx_].head; + else + current_ = nullptr; + } + else + current_ = nullptr; + } + + return *this; + } + + hash_table_iterator operator++(int) + { + auto tmp_current = current_; + auto tmp_idx = idx_; + + current_ = current_->next; + if (current_ == table_[idx_].head) + { + if (idx_ < max_idx_) + { + while (!table_[++idx_].head && idx_ < max_idx_) + { /* DUMMY BODY */ } + + if (idx_ < max_idx_) + current_ = table_[idx_].head; + else + current_ = nullptr; + } + else + current_ = nullptr; + } + + return hash_table_iterator{ + table_, tmp_idx, max_idx_, tmp_current + }; + } + + list_node* node() + { + return current_; + } + + const list_node* node() const + { + return current_; + } + + size_type idx() const + { + return idx_; + } + + template + operator hash_table_const_iterator< + Value, ConstRef, ConstPtr, Size + >() const + { + return hash_table_const_iterator{ + table_, idx_, max_idx_, current_ + }; + } + + private: + hash_table_bucket* table_; + size_type idx_; + size_type max_idx_; + list_node* current_; + }; + + template + bool operator==(const hash_table_iterator& lhs, + const hash_table_iterator& rhs) + { + return lhs.node() == rhs.node(); + } + + template + bool operator!=(const hash_table_iterator& lhs, + const hash_table_iterator& rhs) + { + return !(lhs == rhs); + } + + template + class hash_table_const_local_iterator + { + public: + using value_type = Value; + using const_reference = ConstReference; + using const_pointer = ConstPointer; + using difference_type = ptrdiff_t; + + using iterator_category = forward_iterator_tag; + + // TODO: requirement for forward iterator is default constructibility, fix others! + hash_table_const_local_iterator(const list_node* head = nullptr, + const list_node* current = nullptr) + : head_{head}, current_{current} + { /* DUMMY BODY */ } + + hash_table_const_local_iterator(const hash_table_const_local_iterator&) = default; + hash_table_const_local_iterator& operator=(const hash_table_const_local_iterator&) = default; + + const_reference operator*() const + { + return current_->value; + } + + const_pointer operator->() const + { + return ¤t_->value; + } + + hash_table_const_local_iterator& operator++() + { + current_ = current_->next; + if (current_ == head_) + current_ = nullptr; + + return *this; + } + + hash_table_const_local_iterator operator++(int) + { + auto tmp = current_; + current_ = current_->next; + if (current_ == head_) + current_ = nullptr; + + return hash_table_const_local_iterator{head_, tmp}; + } + + + list_node* node() + { + return const_cast*>(current_); + } + + const list_node* node() const + { + return current_; + } + + private: + const list_node* head_; + const list_node* current_; + }; + + template + bool operator==(const hash_table_const_local_iterator& lhs, + const hash_table_const_local_iterator& rhs) + { + return lhs.node() == rhs.node(); + } + + template + bool operator!=(const hash_table_const_local_iterator& lhs, + const hash_table_const_local_iterator& rhs) + { + return !(lhs == rhs); + } + + template + class hash_table_local_iterator + { + public: + using value_type = Value; + using reference = Reference; + using pointer = Pointer; + using difference_type = ptrdiff_t; + + using iterator_category = forward_iterator_tag; + + hash_table_local_iterator(list_node* head = nullptr, + list_node* current = nullptr) + : head_{head}, current_{current} + { /* DUMMY BODY */ } + + hash_table_local_iterator(const hash_table_local_iterator&) = default; + hash_table_local_iterator& operator=(const hash_table_local_iterator&) = default; + + reference operator*() + { + return current_->value; + } + + pointer operator->() + { + return ¤t_->value; + } + + hash_table_local_iterator& operator++() + { + current_ = current_->next; + if (current_ == head_) + current_ = nullptr; + + return *this; + } + + hash_table_local_iterator operator++(int) + { + auto tmp = current_; + current_ = current_->next; + if (current_ == head_) + current_ = nullptr; + + return hash_table_local_iterator{head_, tmp}; + } + + list_node* node() + { + return current_; + } + + const list_node* node() const + { + return current_; + } + + template + operator hash_table_const_local_iterator< + Value, ConstRef, ConstPtr + >() const + { + return hash_table_const_local_iterator< + value_type, ConstRef, ConstPtr + >{head_, current_}; + } + + private: + list_node* head_; + list_node* current_; + }; + + template + bool operator==(const hash_table_local_iterator& lhs, + const hash_table_local_iterator& rhs) + { + return lhs.node() == rhs.node(); + } + + template + bool operator!=(const hash_table_local_iterator& lhs, + const hash_table_local_iterator& rhs) + { + return !(lhs == rhs); + } +} + +#endif Index: uspace/lib/cpp/include/internal/hash_table_policies.hpp =================================================================== --- uspace/lib/cpp/include/internal/hash_table_policies.hpp (revision 9751280343dac2ca495ff93c50b4675691bcd6fc) +++ uspace/lib/cpp/include/internal/hash_table_policies.hpp (revision 9751280343dac2ca495ff93c50b4675691bcd6fc) @@ -0,0 +1,433 @@ +/* + * Copyright (c) 2018 Jaroslav Jindrak + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef LIBCPP_INTERNAL_HASH_TABLE_POLICIES +#define LIBCPP_INTERNAL_HASH_TABLE_POLICIES + +#include + +namespace std::aux +{ + struct hash_single_policy + { + template + static typename Table::size_type count(const Table& table, const Key& key) + { + return table.find(key) == table.end() ? 0 : 1; + } + + template + static typename Table::place_type find_insertion_spot(const Table& table, const Key& key) + { + auto idx = table.get_bucket_idx_(key); + return make_tuple( + &table.table_[idx], + table.table_[idx].head, + idx + ); + } + + template + static typename Table::size_type erase(Table& table, const Key& key) + { + auto idx = table.get_bucket_idx_(key); + auto head = table.table_[idx].head; + auto current = head; + + do + { + if (table.keys_equal(key, current->value)) + { + --table.size_; + + if (current == head) + { + if (current->next != head) + table.table_[idx].head = current->next; + else + table.table_[idx].head = nullptr; + } + + current->unlink(); + delete current; + + return 1; + } + else + current = current->next; + } + while (current != head); + + return 0; + } + + template + static pair< + typename Table::iterator, + typename Table::iterator + > equal_range(Table& table, const Key& key) + { + auto it = table.find(key); + return make_pair(it, ++it); + } + + template + static pair< + typename Table::const_iterator, + typename Table::const_iterator + > equal_range_const(const Table& table, const Key& key) + { // Note: We cannot overload by return type, so we use a different name. + auto it = table.find(key); + return make_pair(it, ++it); + } + + /** + * Note: We have to duplicate code for emplace, insert(const&) + * and insert(&&) here, because the node (which makes distinction + * between the arguments) is only created if the value isn't + * in the table already. + */ + + template + static pair< + typename Table::iterator, bool + > emplace(Table& table, Args&&... args) + { + using value_type = typename Table::value_type; + using node_type = typename Table::node_type; + using iterator = typename Table::iterator; + + table.increment_size(); + + auto val = value_type{forward(args)...}; + const auto& key = table.get_key(val); + auto [bucket, target, idx] = table.find_insertion_spot(key); + + if (!bucket) + return make_pair(table.end(), false); + + if (target && table.keys_equal(key, target->value)) + { + table.decrement_size(); + + return make_pair( + iterator{ + table.table(), idx, table.bucket_count(), + target + }, + false + ); + } + else + { + auto node = new node_type{move(val)}; + bucket->prepend(node); + + return make_pair(iterator{ + table.table(), idx, + table.bucket_count(), + node + }, true); + } + } + + template + static pair< + typename Table::iterator, bool + > insert(Table& table, const Value& val) + { + using node_type = typename Table::node_type; + using iterator = typename Table::iterator; + + table.increment_size(); + + const auto& key = table.get_key(val); + auto [bucket, target, idx] = table.find_insertion_spot(key); + + if (!bucket) + return make_pair(table.end(), false); + + if (target && table.keys_equal(key, target->value)) + { + table.decrement_size(); + + return make_pair( + iterator{ + table.table(), idx, table.bucket_count(), + target + }, + false + ); + } + else + { + auto node = new node_type{val}; + bucket->prepend(node); + + return make_pair(iterator{ + table.table(), idx, + table.bucket_count(), + node + }, true); + } + } + + template + static pair< + typename Table::iterator, bool + > insert(Table& table, Value&& val) + { + using value_type = typename Table::value_type; + using node_type = typename Table::node_type; + using iterator = typename Table::iterator; + + table.increment_size(); + + const auto& key = table.get_key(val); + auto [bucket, target, idx] = table.find_insertion_spot(key); + + if (!bucket) + return make_pair(table.end(), false); + + if (target && table.keys_equal(key, target->value)) + { + table.decrement_size(); + + return make_pair( + iterator{ + table.table(), idx, table.bucket_count(), + target + }, + false + ); + } + else + { + auto node = new node_type{forward(val)}; + bucket->prepend(node); + + return make_pair(iterator{ + table.table(), idx, + table.bucket_count(), + node + }, true); + } + } + }; + + struct hash_multi_policy + { + template + static typename Table::size_type count(const Table& table, const Key& key) + { + auto head = table.table_[get_bucket_idx_(key)].head; + if (!head) + return 0; + + auto current = head; + typename Table::size_type res = 0; + do + { + if (table.keys_equal(key, current->value)) + ++res; + + current = current->next; + } + while (current != head); + + return res; + } + + template + static typename Table::place_type find_insertion_spot(const Table& table, const Key& key) + { + auto idx = table.get_bucket_idx_(key); + auto head = table.table_[idx].head; + + if (head) + { + auto current = head; + do + { + if (table.keys_equal(key, current->value)) + { + return make_tuple( + &table.table_[idx], + current, + idx + ); + } + + current = current->next; + } while (current != head); + } + + return make_tuple( + &table.table_[idx], + table.table_[idx].head, + idx + ); + } + + template + static typename Table::size_type erase(Table& table, const Key& key) + { + auto idx = table.get_bucket_idx_(key); + auto it = table.begin(it); + typename Table::size_type res{}; + + while (it != table.end(it)) + { + if (table.keys_equal(key, *it)) + { + while (table.keys_equal(key, *it)) + { + auto node = it.node(); + ++it; + ++res; + + node.unlink(); + delete node; + --table.size_; + } + + // Elements with equal keys are next to each other. + return res; + } + + ++it; + } + + return res; + } + + template + static pair< + typename Table::iterator, + typename Table::iterator + > equal_range(Table& table, const Key& key) + { + auto first = table.find(key); + if (first == table.end()) + return make_pair(table.end(), table.end()); + + auto last = first; + do + { + ++last; + } while (table.keys_equal(key, *last)); + + return make_pair(first, last); + } + + template + static pair< + typename Table::const_iterator, + typename Table::const_iterator + > equal_range_const(const Table& table, const Key& key) + { + auto first = table.find(key); + if (first == table.end()) + return make_pair(table.end(), table.end()); + + auto last = first; + do + { + ++last; + } while (table.keys_equal(key, *last)); + + return make_pair(first, last); + } + + template + static pair< + typename Table::iterator, bool + > emplace(Table& table, Args&&... args) + { + using node_type = typename Table::node_type; + + auto node = new node_type{forward(args)...}; + + return insert(table, node); + } + + template + static pair< + typename Table::iterator, bool + > insert(Table& table, const Value& val) + { + using node_type = typename Table::node_type; + + auto node = new node_type{val}; + + return insert(table, node); + } + + template + static pair< + typename Table::iterator, bool + > insert(Table& table, Value&& val) + { + using value_type = typename Table::value_type; + using node_type = typename Table::node_type; + + auto node = new node_type{forward(val)}; + + return insert(table, node); + } + + template + static pair< + typename Table::iterator, bool + > insert(Table& table, typename Table::node_type* node) + { + using iterator = typename Table::iterator; + + table.increment_size(); + + const auto& key = table.get_key(node->value); + auto [bucket, target, idx] = table.find_insertion_spot(key); + + if (!bucket) + return make_pair(table.end(), false); + + if (target && table.keys_equal(key, target->value)) + target->append(node); + else + bucket->prepend(node); + + return make_pair(iterator{ + table.table(), idx, + table.bucket_count(), + node + }, true); + } + }; +} + +#endif Index: uspace/lib/cpp/include/internal/key_extractors.hpp =================================================================== --- uspace/lib/cpp/include/internal/key_extractors.hpp (revision 9751280343dac2ca495ff93c50b4675691bcd6fc) +++ uspace/lib/cpp/include/internal/key_extractors.hpp (revision 9751280343dac2ca495ff93c50b4675691bcd6fc) @@ -0,0 +1,60 @@ +/* + * Copyright (c) 2018 Jaroslav Jindrak + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef LIBCPP_INTERNAL_KEY_EXTRACTORS +#define LIBCPP_INTERNAL_KEY_EXTRACTORS + +#include + +namespace std::aux +{ + template + struct key_value_key_extractor + { + const Key& operator()(const pair& p) const noexcept + { + return p.first; + } + }; + + template + struct key_no_value_key_extractor + { + Key& operator()(Key& k) const noexcept + { + return k; + } + + const Key& operator()(const Key& k) const noexcept + { + return k; + } + }; +} + +#endif