Changeset 108ad4cf 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:

3be3752

Parents:

a4453e1

git-author:

Dzejrou <dzejrou@…> (2018-04-24 23:59:56)

git-committer:

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

Message:

cpp: added the rest of the basic insert/emplace functions

File:

• uspace/lib/cpp/include/impl/unordered_map.hpp (modified) (4 diffs)

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

@@ -34 +34 @@
 #include <functional>
 #include <memory>
+#include <type_traits>
 #include <utility>
 
@@ -240 +241 @@
             pair<iterator, bool> emplace(Args&&... args)
             {
-                // TODO: implement
+                // TODO: currently there is code repetition in
+                //       3 places, try to find a way to reduce it
+                auto val = value_type{forward<Args>(args)...};
+                auto key = table_.get_key(val);
+                auto spot = table_.find_insertion_spot(key);
+                auto bucket = get<0>(spot);
+                auto idx = get<2>(spot);
+
+                if (bucket->head)
+                {
+                    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);
+                }
+
+                auto node = new node_type{move(val)};
+                bucket->append(node);
+
+                return make_pair(iterator{
+                    table_.table(), idx,
+                    table_.bucket_count(),
+                    node
+                }, true);
             }
 
             template<class... Args>
-            iterator emplace_hint(const_iterator position, Args&&... args)
-            {
-                // TODO: implement
+            iterator emplace_hint(const_iterator, Args&&... args)
+            {
+                return emplace(forward<Args>(args)...).first;
             }
 
             pair<iterator, bool> insert(const value_type& val)
             {
-                // TODO: implement
+                auto key = table_.get_key(val);
+                auto spot = table_.find_insertion_spot(key);
+                auto bucket = get<0>(spot);
+                auto idx = get<2>(spot);
+
+                if (bucket->head)
+                {
+                    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);
+                }
+
+                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)
             {
-                // TODO: implement
-            }
-
-            template<class T>
+                auto key = table_.get_key(val);
+                auto spot = table_.find_insertion_spot(key);
+                auto bucket = get<0>(spot);
+                auto idx = get<2>(spot);
+
+                if (bucket->head)
+                {
+                    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);
+                }
+
+                auto node = new node_type{forward<value_type>(val)};
+                bucket->append(node);
+
+                return make_pair(iterator{
+                    table_.table(), idx,
+                    table_.bucket_count(),
+                    node
+                }, true);
+            }
+
+            template<
+                class T,
+                class = enable_if_t<is_constructible_v<value_type, T&&>, void>
+            >
             pair<iterator, bool> insert(T&& val)
             {
-                // TODO: implement
-            }
-
-            iterator insert(const_iterator hint, const value_type& val)
-            {
-                // TODO: implement
-            }
-
-            iterator insert(const_iterator hint, value_type&& val)
-            {
-                // TODO: implement
-            }
-
-            template<class T>
+                return emplace(forward<T>(val));
+            }
+
+            iterator insert(const_iterator, const value_type& val)
+            {
+                return insert(val).first;
+            }
+
+            iterator insert(const_iterator, value_type&& val)
+            {
+                return insert(forward<value_type>(val)).first;
+            }
+
+            template<
+                class T,
+                class = enable_if_t<is_constructible_v<value_type, T&&>, void>
+            >
             iterator insert(const_iterator hint, T&& val)
             {
-                // TODO: implement
+                return emplace_hint(hint, forward<T>(val));
             }
 
@@ -284 +393 @@
             void insert(InputIterator first, InputIterator last)
             {
-                // TODO: implement
+                while (first != last)
+                    insert(*first++);
             }
 
@@ -357 +467 @@
                 return iterator{
                     table_.table(), first.idx(),
-                    table_.size(), table_.head(first.idx())
+                    table_.bucket_count(), table_.head(first.idx())
                 };
             }