Changeset f2ba4c79 in mainline

Timestamp:

2018-07-05T21:41:24Z (6 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

Location:

uspace/lib/cpp

Files:

• Makefile (modified) (1 diff)
• include/internal/hash_table_iterators.hpp (modified) (1 diff)
• include/internal/hash_table_policies.hpp (modified) (4 diffs)
• include/internal/test/tests.hpp (modified) (1 diff)

uspace/lib/cpp/Makefile

@@ -64 +64 @@
         src/internal/test/test.cpp \
         src/internal/test/tuple.cpp \
+        src/internal/test/unordered_map.cpp \
         src/internal/test/vector.cpp
 

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

@@ -142 +142 @@
         using non_const_iterator_type = hash_table_iterator<
             Value, get_non_const_ref_t<ConstReference>,
-            get_non_const_ptr<ConstPointer>, Size
+            get_non_const_ptr_t<ConstPointer>, Size
         >;
 

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))

uspace/lib/cpp/include/internal/test/tests.hpp

@@ -195 +195 @@
             void test_multi_bounds_and_ranges();
     };
+
+    class unordered_map_test: public test_suite
+    {
+        public:
+            bool run(bool) override;
+            const char* name() override;
+
+        private:
+            void test_constructors_and_assignment();
+            void test_histogram();
+            void test_emplace_insert();
+            void test_multi();
+
+            template<class Iterator, class Container>
+            void test_contains(const char* tname, Iterator first,
+                               Iterator last, const Container& cont)
+            {
+                if (!assert_contains(first, last, cont))
+                {
+                    report(false, tname);
+                    ++failed_;
+                    ok_ = false;
+                }
+                else
+                {
+                    report(true, tname);
+                    ++succeeded_;
+                }
+            }
+
+            template<class Iterator1, class Iterator2, class Container>
+            void test_contains_multi(const char* tname, Iterator1 first1,
+                               Iterator1 last1, Iterator2 first2,
+                               const Container& cont)
+            {
+                if (!assert_contains_multi(first1, last1, first2, cont))
+                {
+                    report(false, tname);
+                    ++failed_;
+                    ok_ = false;
+                }
+                else
+                {
+                    report(true, tname);
+                    ++succeeded_;
+                }
+            }
+
+            template<class Iterator, class Container>
+            bool assert_contains(Iterator first, Iterator last, const Container& cont)
+            {
+                while (first != last)
+                {
+                    if (cont.find(*first++) == cont.end())
+                        return false;
+                }
+
+                return true;
+            }
+
+            template<class Iterator1, class Iterator2, class Container>
+            bool assert_contains_multi(Iterator1 first1, Iterator1 last1,
+                                       Iterator2 first2, const Container& cont)
+            {
+                while (first1 != last1)
+                {
+                    if (cont.count(*first1++) != *first2++)
+                        return false;
+                }
+
+                return true;
+            }
+    };
 }