Changeset e912cdf in mainline

Timestamp:

2018-07-05T21:41:21Z (6 years ago)

Author:

Dzejrou <dzejrou@…>

Branches:

lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export

Children:

5ae8168

Parents:

ed9df7d

git-author:

Dzejrou <dzejrou@…> (2018-04-25 16:45:01)

git-committer:

Dzejrou <dzejrou@…> (2018-07-05 21:41:21)

Message:

cpp: refactored unordered_map's insertion functions and moved some logic to the underlying hash table, added rehashing to insertion when it's needed

Location:

uspace/lib/cpp/include

Files:

• impl/unordered_map.hpp (modified) (5 diffs)
• internal/hash_table.hpp (modified) (3 diffs)

uspace/lib/cpp/include/impl/unordered_map.hpp

@@ -241 +241 @@
             pair<iterator, bool> 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>(args)...};
                 auto key = table_.get_key(val);
@@ -249 +267 @@
                 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 +303 @@
             pair<iterator, bool> insert(const value_type& val)
             {
+                table_.increment_size();
+
                 auto key = table_.get_key(val);
                 auto spot = table_.find_insertion_spot(key);
@@ -294 +310 @@
                 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<iterator, bool> insert(value_type&& val)
+            {
                 table_.increment_size();
 
-                return make_pair(iterator{
-                    table_.table(), idx,
-                    table_.bucket_count(),
-                    node
-                }, true);
-            }
-
-            pair<iterator, bool> insert(value_type&& val)
-            {
                 auto key = table_.get_key(val);
                 auto spot = table_.find_insertion_spot(key);
@@ -333 +347 @@
                 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<value_type>(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<value_type>(val)};
+                    bucket->append(node);
+
+                    return make_pair(iterator{
+                        table_.table(), idx,
+                        table_.bucket_count(),
+                        node
+                    }, true);
+                }
             }
 

uspace/lib/cpp/include/internal/hash_table.hpp

@@ -1002 +1002 @@
             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 +1080 @@
             }
 
-            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 +1122 @@
             {
                 ++size_;
+
+                rehash_if_needed();
+            }
+
+            void decrement_size()
+            {
+                --size_;
+            }
+
+            node_type* find_node_or_return_head(const key_type& key,
+                                                const hash_table_bucket<value_type, size_type>& 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;
             }