Changeset b22ccaa in mainline

Timestamp:

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

Author:

Dzejrou <dzejrou@…>

Branches:

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

Children:

7ea90cf

Parents:

1fafb3e

git-author:

Dzejrou <dzejrou@…> (2018-04-27 23:47:12)

git-committer:

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

Message:

cpp: fixed iterators & copy construction, added equality checking for hash tables

File:

• uspace/lib/cpp/include/internal/hash_table.hpp (modified) (9 diffs)

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

@@ -577 +577 @@
                     if (idx_ < max_idx_)
                     {
-                        while (!table_[++idx_].head)
+                        while (!table_[++idx_].head && idx_ < max_idx_)
                         { /* DUMMY BODY */ }
 
@@ -602 +602 @@
                     if (idx_ < max_idx_)
                     {
-                        while (!table_[++idx_].head)
+                        while (!table_[++idx_].head && idx_ < max_idx_)
                         { /* DUMMY BODY */ }
 
@@ -693 +693 @@
                     if (idx_ < max_idx_)
                     {
-                        while (!table_[++idx_].head)
+                        while (!table_[++idx_].head && idx_ < max_idx_)
                         { /* DUMMY BODY */ }
 
@@ -718 +718 @@
                     if (idx_ < max_idx_)
                     {
-                        while (!table_[++idx_].head)
+                        while (!table_[++idx_].head && idx_ < max_idx_)
                         { /* DUMMY BODY */ }
 
@@ -996 +996 @@
             {
                 for (const auto& x: other)
-                {
-                    auto spot = find_insertion_spot(key_extractor_(x));
-                    insert(spot, x);
-                }
+                    insert(x);
             }
 
@@ -1048 +1045 @@
             iterator begin() noexcept
             {
+                auto idx = first_filled_bucket_();
                 return iterator{
-                    table_, size_type{}, bucket_count_,
-                    table_[0].head
+                    table_, idx, bucket_count_,
+                    table_[idx].head
                 };
             }
@@ -1071 +1069 @@
             const_iterator cbegin() const noexcept
             {
+                auto idx = first_filled_bucket_();
                 return const_iterator{
-                    table_, size_type{}, bucket_count_,
-                    table_[0].head
+                    table_, idx, bucket_count_,
+                    table_[idx].head
                 };
             }
@@ -1348 +1347 @@
             bool is_eq_to(const hash_table& other) const
             {
-                // TODO: implement
-                return false;
+                if (size() != other.size())
+                    return false;
+
+                auto it = begin();
+                while (it != end())
+                {
+                    /**
+                     * For each key K we will check how many
+                     * instances of K are there in the table.
+                     * Then we will check if the count for K
+                     * is equal to that amount.
+                     */
+
+                    size_type cnt{};
+                    auto tmp = it;
+
+                    while (key_eq_(key_extractor_(*it), key_extractor_(*tmp)))
+                    {
+                        ++cnt;
+                        if (++tmp == end())
+                            break;
+                    }
+
+                    auto other_cnt = other.count(key_extractor_(*it));
+                    if (cnt != other_cnt)
+                        return false;
+
+                    it = tmp; // tmp  is one past *it's key.
+                }
+
+                return true;
             }
 
@@ -1431 +1459 @@
             }
 
+            size_type first_filled_bucket_() const
+            {
+                size_type res{};
+                while (res < bucket_count_)
+                {
+                    if (table_[res].head)
+                        return res;
+                    ++res;
+                }
+
+                /**
+                 * Note: This is used for iterators,
+                 *       so we need to return a valid index.
+                 *       But since table_[0].head is nullptr
+                 *       we know that if we return 0 the
+                 *       created iterator will test as equal
+                 *       to end().
+                 */
+                return 0;
+            }
+
             friend Policy;
     };