Changeset e9027b5 in mainline for uspace/lib/cpp/include/internal/hash_table.hpp

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:

f67b4ef

Parents:

871cfe0c

git-author:

Dzejrou <dzejrou@…> (2018-04-23 18:58:08)

git-committer:

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

Message:

cpp: fixed some iterator constness issues, added erase to hash_table

File:

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

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

@@ -121 +121 @@
             );
         }
+
+        template<class Table, class Key>
+        static typename Table::size_type erase(Table& table, const Key& key)
+        {
+            auto idx = table.get_bucket_idx_(key);
+            auto head = table.table_[idx].head;
+            auto current = head;
+
+            do
+            {
+                if (table.key_eq_(key, table.key_extractor_(current->value)))
+                {
+                    --table.size_;
+
+                    if (current == head)
+                    {
+                        if (current->next != head)
+                            table.table_[idx].head = current->next;
+                        else
+                            table.table_[idx].head = nullptr;
+                    }
+
+                    current->unlink();
+                    delete current;
+
+                    return 1;
+                }
+                else
+                    current = current->next;
+            }
+            while (current != head);
+
+            return 0;
+        }
     };
 
@@ -154 +188 @@
             //       link (if key is already in it, place the new copy
             //       next to it, otherwise just return head)
+        }
+
+        template<class Table, class Key>
+        static typename Table::size_type erase(Table& table, const Key& key)
+        {
+            // TODO: erase all items with given key
         }
     };
@@ -169 +209 @@
             using iterator_category = forward_iterator_tag;
 
-            hash_table_const_iterator(hash_table_bucket<value_type, size_type>* table = nullptr,
+            hash_table_const_iterator(const hash_table_bucket<value_type, size_type>* table = nullptr,
                                       size_type idx = size_type{}, size_type max_idx = size_type{},
-                                      list_node<value_type>* current = nullptr)
+                                      const list_node<value_type>* current = nullptr)
                 : table_{table}, idx_{idx}, max_idx_{max_idx}, current_{current}
             { /* DUMMY BODY */ }
@@ -239 +279 @@
             list_node<value_type>* node()
             {
+                return const_cast<list_node<value_type>*>(current_);
+            }
+
+            const list_node<value_type>* node() const
+            {
                 return current_;
             }
 
-            const list_node<value_type>* node() const
-            {
-                return current_;
+            size_type idx() const
+            {
+                return idx_;
             }
 
         private:
-            hash_table_bucket<value_type, size_type>* table_;
+            const hash_table_bucket<value_type, size_type>* table_;
             size_type idx_;
             size_type max_idx_;
-            list_node<value_type>* current_;
+            const list_node<value_type>* current_;
     };
 
@@ -358 +403 @@
             }
 
+            size_type idx() const
+            {
+                return idx_;
+            }
+
             template<class ConstRef, class ConstPtr>
             operator hash_table_const_iterator<
@@ -363 +413 @@
             >() const
             {
-                return hash_table_const_iterator{
+                return hash_table_const_iterator<value_type, ConstRef, ConstPtr, size_type>{
                     table_, idx_, max_idx_, current_
                 };
@@ -401 +451 @@
 
             // TODO: requirement for forward iterator is default constructibility, fix others!
-            hash_table_const_local_iterator(list_node<value_type>* head = nullptr,
-                                            list_node<value_type>* current = nullptr)
+            hash_table_const_local_iterator(const list_node<value_type>* head = nullptr,
+                                            const list_node<value_type>* current = nullptr)
                 : head_{head}, current_{current}
             { /* DUMMY BODY */ }
@@ -438 +488 @@
             }
 
+
             list_node<value_type>* node()
             {
+                return const_cast<list_node<value_type>*>(current_);
+            }
+
+            const list_node<value_type>* node() const
+            {
                 return current_;
             }
 
-            const list_node<value_type>* node() const
-            {
-                return current_;
-            }
-
         private:
-            list_node<value_type>* head_;
-            list_node<value_type>* current_;
+            const list_node<value_type>* head_;
+            const list_node<value_type>* current_;
     };
 
@@ -530 +581 @@
             >() const
             {
-                return hash_table_const_local_iterator{head_, current_};
+                return hash_table_const_local_iterator<
+                    value_type, ConstRef, ConstPtr
+                >{head_, current_};
             }
 
@@ -659 +712 @@
 
                 ++size_;
+                // TODO: if we go over max load factor, rehash
             }
 
@@ -673 +727 @@
 
                 ++size_;
+                // TODO: if we go over max load factor, rehash
             }
 
             size_type erase(const key_type& key)
             {
-                // TODO: implement
+                return Policy::erase(*this, key);
             }
 
             iterator erase(const_iterator it)
             {
-                // TODO: implement
+                auto node = it.node();
+                auto idx = it.idx();
+
+                /**
+                 * Note: This way we will continue on the next bucket
+                 *       if this is the last element in its bucket.
+                 */
+                iterator res{table_, idx, size_, node};
+                ++res;
+
+                if (table_[idx].head == node)
+                {
+                    if (node->next != node)
+                        table_[idx].head = node->next;
+                    else
+                        table_[idx].head = nullptr;
+                }
+
+                node->unlink();
+                delete node;
+
+                return res;
             }