Changeset f2ba4c79 in mainline for uspace/lib/cpp/include/internal/hash_table_policies.hpp

Timestamp:

2018-07-05T21:41:24Z (7 years ago)

Author:

Dzejrou <dzejrou@…>

Branches:

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

Children:

c7d7368

Parents:

4727aacd

git-author:

Dzejrou <dzejrou@…> (2018-05-14 22:54:41)

git-committer:

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

Message:

cpp: added unordered_map tests and fixed bugs found by them

File:

• uspace/lib/cpp/include/internal/hash_table_policies.hpp (modified) (4 diffs)

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

@@ -60 +60 @@
             auto current = head;
 
+            if (!current)
+                return 0;
+
             do
             {
@@ -246 +249 @@
         static typename Table::size_type count(const Table& table, const Key& key)
         {
-            auto head = table.table_[get_bucket_idx_(key)].head;
+            auto head = table.table_[table.get_bucket_idx_(key)].head;
             if (!head)
                 return 0;
@@ -299 +302 @@
         {
             auto idx = table.get_bucket_idx_(key);
-            auto it = table.begin(it);
+            auto head = table.table_[idx].head;
+            auto current = head;
+            table.table_[idx].head = nullptr;
+
+            if (!current)
+                return 0;
+
+            /**
+             * We traverse the list and delete if the keys
+             * equal, if they don't we append the nodes back
+             * to the bucket.
+             */
             typename Table::size_type res{};
 
-            while (it != table.end(it))
-            {
-                if (table.keys_equal(key, *it))
+            do
+            {
+                auto tmp = current;
+                current = current->next;
+
+                if (!table.keys_equal(key, tmp->value))
+                    table.table_[idx].append(tmp);
+                else
                 {
-                    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;
+                    ++res;
+                    --table.size_;
+
+                    delete tmp;
                 }
-
-                ++it;
-            }
+            }
+            while (current != head);
 
             return res;
@@ -407 +416 @@
 
             if (!bucket)
-                return make_pair(table.end(), false);
+                table.end();
 
             if (target && table.keys_equal(key, target->value))