Changeset 7f379fe in mainline

Timestamp:

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

Author:

Dzejrou <dzejrou@…>

Branches:

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

Children:

cfeeb61

Parents:

54618da

git-author:

Dzejrou <dzejrou@…> (2018-04-25 20:39:07)

git-committer:

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

Message:

cpp: implemented multi policy operations, fixed constness of some parameters

File:

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

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

@@ -192 +192 @@
             typename Table::iterator,
             typename Table::iterator
-        > equal_range(Table& table, const Key& key)
+        > equal_range(const Table& table, const Key& key)
         {
             auto it = table.find(key);
@@ -202 +202 @@
             typename Table::const_iterator,
             typename Table::const_iterator
-        > equal_range_const(Table& table, const Key& key)
+        > equal_range_const(const Table& table, const Key& key)
         { // Note: We cannot overload by return type, so we use a different name.
             auto it = table.find(key);
@@ -235 +235 @@
         static typename Table::hint_type find_insertion_spot(const Table& table, const Key& key)
         {
-            // TODO: find the right bucket, in that, find the right
-            //       link (if key is already in it, place the new copy
-            //       next to it, otherwise just return head)
+            auto idx = table.get_bucket_idx_(key);
+            auto head = table.table_[idx].head;
+
+            if (head)
+            {
+                auto current = head;
+                do
+                {
+                    if (table.keys_equal(key, table.get_key(current->value)))
+                    {
+                        return make_tuple(
+                            &table.table_[idx],
+                            current,
+                            idx
+                        );
+                    }
+
+                    current = current->next;
+                } while (current != head);
+            }
+
+            return make_tuple(
+                &table.table_[idx],
+                table.table_[idx].head,
+                idx
+            );
         }
 
@@ -243 +266 @@
         static typename Table::size_type erase(Table& table, const Key& key)
         {
-            // TODO: erase all items with given key
+            auto idx = table.get_bucket_idx_(key);
+            auto it = table.begin(it);
+            typename Table::size_type res{};
+
+            while (it != table.end(it))
+            {
+                if (table.keys_equal(key, table.get_key(*it)))
+                {
+                    while (table.keys_equal(key, table.get_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;
+                }
+
+                ++it;
+            }
+
+            return res;
         }
 
@@ -250 +299 @@
             typename Table::iterator,
             typename Table::iterator
-        > equal_range(Table& table, const Key& key)
-        {
-            // TODO: implement
+        > equal_range(const Table& table, const Key& key)
+        {
+            auto first = table.find(key);
+            if (first == table.end())
+                return make_pair(end(), end());
+
+            auto last = first;
+            while (table.keys_equal(key, table.get_key(*last)))
+                ++last;
+
+            // The second iterator points one behind the range.
+            ++last;
+
+            return make_pair(first, last);
         }
 
@@ -259 +319 @@
             typename Table::const_iterator,
             typename Table::const_iterator
-        > equal_range_const(Table& table, const Key& key)
-        {
-            // TODO: implement
+        > equal_range_const(const Table& table, const Key& key)
+        {
+            auto first = table.find(key);
+            if (first == table.end())
+                return make_pair(end(), end());
+
+            auto last = first;
+            while (table.keys_equal(key, table.get_key(*last)))
+                ++last;
+
+            // The second iterator points one behind the range.
+            ++last;
+
+            return make_pair(first, last);
         }
     };