Index: uspace/lib/cpp/include/internal/hash_table.hpp =================================================================== --- uspace/lib/cpp/include/internal/hash_table.hpp (revision 7320ca676d38bc80f8d525702594c1a4ca8e661b) +++ uspace/lib/cpp/include/internal/hash_table.hpp (revision 1d5424a62e28964b27026e710e31a143b8244dec) @@ -79,4 +79,8 @@ list_node* head; + hash_table_bucket() + : head{} + { /* DUMMY BODY */ } + Size size() const noexcept { @@ -104,4 +108,7 @@ void clear() { + if (!head) + return; + auto current = head; do @@ -176,4 +183,24 @@ 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(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); + } }; @@ -215,4 +242,22 @@ { // TODO: erase all items with given key + } + + template + static pair< + typename Table::iterator, + typename Table::iterator + > equal_range(Table& table, const Key& key) + { + // TODO: implement + } + + template + static pair< + typename Table::const_iterator, + typename Table::const_iterator + > equal_range_const(Table& table, const Key& key) + { + // TODO: implement } }; @@ -656,5 +701,5 @@ hash_table(size_type buckets, float max_load_factor = 1.f) - : table_{new hash_table_bucket[buckets]}, + : table_{new hash_table_bucket[buckets]()}, bucket_count_{buckets}, size_{}, hasher_{}, key_eq_{}, key_extractor_{}, max_load_factor_{max_load_factor} @@ -714,18 +759,28 @@ template - iterator emplace(Allocator& alloc, Args&&... args) - { - // TODO: implement - } - - void insert(const hint_type& where, const value_type& val) + void emplace(const hint_type& where, Allocator& alloc, Args&&... args) { if (!hint_ok_(where)) return; - auto node = new list_node{val}; + auto node = new list_node{forward(args)...}; if (get<1>(where) == nullptr) // Append here will create a new head. get<0>(where)->append(node); else // Prepending before an exact position is common in the standard. + get<1>(where)->prepend(node); + + ++size_; + // TODO: if we go over max load factor, rehash + } + + void insert(const hint_type& where, const value_type& val) + { + if (!hint_ok_(where)) + return; + + auto node = new list_node{val}; + if (get<1>(where) == nullptr) + get<0>(where)->append(node); + else get<1>(where)->prepend(node); @@ -787,7 +842,6 @@ } - template void swap(hash_table& other) - noexcept(allocator_traits::is_always_equal::value && + noexcept(allocator_traits::is_always_equal::value && noexcept(swap(declval(), declval())) && noexcept(swap(declval(), declval()))) @@ -813,10 +867,40 @@ iterator find(const key_type& key) { - // TODO: implement + auto idx = get_bucket_idx_(key); + auto head = table_[idx].head; + + if (!head) + return end(); + + auto current = head; + do + { + if (key_eq_(key, key_extractor_(current->value))) + return iterator{table_, idx, size_, current}; + current = current->next; + } + while (current != head); + + return end(); } const_iterator find(const key_type& key) const { - // TODO: implement + auto idx = get_bucket_idx_(key); + auto head = table_[idx].head; + + if (!head) + return end(); + + auto current = head; + do + { + if (key_eq_(key, key_extractor_(current->value))) + return iterator{table_, idx, size_, current}; + current = current->next; + } + while (current != head); + + return end(); } @@ -828,10 +912,10 @@ pair equal_range(const key_type& key) { - // TODO: implement + return Policy::equal_range(*this, key); } pair equal_range(const key_type& key) const { - // TODO: implement + return Policy::equal_range_const(*this, key); } @@ -903,17 +987,64 @@ * can have no effect. */ - } - - void rehash(size_type n) - { - // TODO: implement - // TODO: exception thrown in rehash means the rehash - // has no effect, so we create a new table, insert in it - // and then swap - } - - void reserve(size_type n) - { - // TODO: implement + // TODO: change max factor and rehash if needed + } + + void rehash(size_type count) + { + if (count < size_ / max_load_factor_) + count = size_ / max_load_factor_; + + // Note: This is the only place where an exception can be + // thrown (no mem) in this function, so wrap it + // in try-catch-rethrow. + hash_table new_table{count, max_load_factor_}; + + for (std::size_t i = 0; i < bucket_count_; ++i) + { + auto head = table_[i].head; + if (!head) + continue; + + auto current = head; + + do + { + auto next = current->next; + + current->next = current; + current->prev = current; + + auto where = Policy::find_insertion_spot( + new_table, key_extractor_(current->value) + ); + + /** + * Note: We're rehashing, so we know each + * key can be inserted. + */ + auto new_bucket = get<0>(where); + auto new_successor = get<1>(where); + + if (new_successor) + new_successor->append(current); + else + new_bucket->append(current); + + current = next; + } while (current != head); + + table_[i].head = nullptr; + } + + new_table.size_ = size_; + swap(new_table); + + delete[] new_table.table_; + new_table.table_ = nullptr; + } + + void reserve(size_type count) + { + rehash(count / max_load_factor_ + 1); } @@ -927,5 +1058,6 @@ { // Lists are deleted in ~hash_table_bucket. - delete[] table_; + if (table_) + delete[] table_; } @@ -966,4 +1098,6 @@ // that is something like: // return get<1>(hint)->prev->key == key || !bucket.contains(key) + // TODO: also, make it public and make hint usage one level above? + // (since we already have insert with decisive hint) return get<0>(hint) != nullptr && get<2>(hint) < bucket_count_; }