Index: uspace/lib/cpp/include/impl/unordered_map.hpp =================================================================== --- uspace/lib/cpp/include/impl/unordered_map.hpp (revision ed9df7db8c0a247865da615722cabf12e7934373) +++ uspace/lib/cpp/include/impl/unordered_map.hpp (revision e912cdf9ea7214d5ca7bfcefed6f6ff200d21189) @@ -241,6 +241,24 @@ pair emplace(Args&&... args) { - // TODO: currently there is code repetition in - // 3 places, try to find a way to reduce it + /** + * Note: Some of these modifier functions start off + * by incrementing the table's element count and + * decrement it when insertion does not take place. + * This is because we need to cause rehashing if + * there are too many elements, but rehashing itself + * would invalidate all pointers we get from + * find_insertion_spot, which would require us to + * do another find. But this way we avoid two searches + * with the possibility of a rehash that is not necessary + * (but hardly a bad thing as the table needs just one + * element more to rehash). + * + * Also, there are 3 functions with similar bodies, + * but the duplicit code cannot be moved to a common + * sub-function because all three require different + * handling of the value (move, forward and copy). + */ + table_.increment_size(); + auto val = value_type{forward(args)...}; auto key = table_.get_key(val); @@ -249,34 +267,30 @@ auto idx = get<2>(spot); - if (bucket->head) + if (!bucket) + return make_pair(end(), false); + + auto target = table_.find_node_or_return_head(key, *bucket); + if (target && table_.keys_equal(key, target->value)) { - auto head = bucket->head; - auto current = bucket->head; - - do - { - if (table_.keys_equal(key, current->value)) - { - return make_pair(iterator{ - table_.table(), idx, - table_.bucket_count(), - current - }, false); - } - else - current = current->next; - } - while (current != head); + table_.decrement_size(); + return make_pair( + iterator{ + table_.table(), idx, table_.bucket_count(), + target + }, + false + ); } - - auto node = new node_type{move(val)}; - bucket->append(node); - table_.increment_size(); - - return make_pair(iterator{ - table_.table(), idx, - table_.bucket_count(), - node - }, true); + else + { + auto node = new node_type{move(val)}; + bucket->append(node); + + return make_pair(iterator{ + table_.table(), idx, + table_.bucket_count(), + node + }, true); + } } @@ -289,4 +303,6 @@ pair insert(const value_type& val) { + table_.increment_size(); + auto key = table_.get_key(val); auto spot = table_.find_insertion_spot(key); @@ -294,38 +310,36 @@ auto idx = get<2>(spot); - if (bucket->head) + if (!bucket) + return make_pair(end(), false); + + auto target = table_.find_node_or_return_head(key, *bucket); + if (target && table_.keys_equal(key, target->value)) { - auto head = bucket->head; - auto current = bucket->head; - - do - { - if (table_.keys_equal(key, current->value)) - { - return make_pair(iterator{ - table_.table(), idx, - table_.bucket_count(), - current - }, false); - } - else - current = current->next; - } - while (current != head); + table_.decrement_size(); + return make_pair( + iterator{ + table_.table(), idx, table_.bucket_count(), + target + }, + false + ); } - - auto node = new node_type{val}; - bucket->append(node); + else + { + auto node = new node_type{val}; + bucket->append(node); + + return make_pair(iterator{ + table_.table(), idx, + table_.bucket_count(), + node + }, true); + } + } + + pair insert(value_type&& val) + { table_.increment_size(); - return make_pair(iterator{ - table_.table(), idx, - table_.bucket_count(), - node - }, true); - } - - pair insert(value_type&& val) - { auto key = table_.get_key(val); auto spot = table_.find_insertion_spot(key); @@ -333,35 +347,30 @@ auto idx = get<2>(spot); - if (bucket->head) + if (!bucket) + return make_pair(end(), false); + + auto target = table_.find_node_or_return_head(key, *bucket); + if (target && table_.keys_equal(key, target->value)) { - auto head = bucket->head; - auto current = bucket->head; - - do - { - if (table_.keys_equal(key, current->value)) - { - return make_pair(iterator{ - table_.table(), idx, - table_.bucket_count(), - current - }, false); - } - else - current = current->next; - } - while (current != head); + table_.decrement_size(); + return make_pair( + iterator{ + table_.table(), idx, table_.bucket_count(), + target + }, + false + ); } - - auto node = new node_type{forward(val)}; - bucket->append(node); - table_.increment_size(); - // TODO: problem: rehashing here would invalidate the intel we have... - - return make_pair(iterator{ - table_.table(), idx, - table_.bucket_count(), - node - }, true); + else + { + auto node = new node_type{forward(val)}; + bucket->append(node); + + return make_pair(iterator{ + table_.table(), idx, + table_.bucket_count(), + node + }, true); + } } Index: uspace/lib/cpp/include/internal/hash_table.hpp =================================================================== --- uspace/lib/cpp/include/internal/hash_table.hpp (revision ed9df7db8c0a247865da615722cabf12e7934373) +++ uspace/lib/cpp/include/internal/hash_table.hpp (revision e912cdf9ea7214d5ca7bfcefed6f6ff200d21189) @@ -1002,9 +1002,8 @@ void max_load_factor(float factor) { - /** - * Note: According to the standard, this function - * can have no effect. - */ - // TODO: change max factor and rehash if needed + if (factor > 0.f) + max_load_factor_ = factor; + + rehash_if_needed(); } @@ -1081,10 +1080,4 @@ } - void set_hint(const_iterator hint) - { - // TODO: hint_ should be a ptr and we extract it here, - // then set it to nullptr after each operation - } - hint_type find_insertion_spot(const key_type& key) { @@ -1129,4 +1122,34 @@ { ++size_; + + rehash_if_needed(); + } + + void decrement_size() + { + --size_; + } + + node_type* find_node_or_return_head(const key_type& key, + const hash_table_bucket& bucket) + { + if (bucket.head) + { + auto head = bucket.head; + auto current = bucket.head; + + do + { + if (keys_equal(key, current->value)) + return current; + else + current = current->next; + } + while (current != head); + + return head; + } + else + return nullptr; }