Changeset c71c171 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:

73066e61

Parents:

de53138

git-author:

Dzejrou <dzejrou@…> (2018-04-20 00:18:51)

git-committer:

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

Message:

cpp: added constructors, assignments and basic modifiers to std::list

File:

• uspace/lib/cpp/include/impl/list.hpp (modified) (9 diffs)

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

@@ -30 +30 @@
 #define LIBCPP_LIST
 
+#include <cstdlib>
 #include <iterator>
 #include <memory>
 #include <utility>
 
-namespace cpp
+namespace std
 {
+    template<class T, class Allocator = allocator<T>>
+    class list;
+
     namespace aux
     {
@@ -44 +48 @@
             list_node* next;
             list_node* prev;
+
+            template<class... Args>
+            list_node(Args&&... args)
+                : value{forward<Args>(args)...},
+                  next{this}, prev{this}
+            {
+                next = this;
+                prev = this;
+            }
+
+            list_node(const T& val)
+                : value{val}, next{this}, prev{this}
+            {
+                next = this;
+                prev = this;
+            }
+
+            list_node(T&& val)
+                : value{forward<T>(val)}, next{}, prev{}
+            {
+                next = this;
+                prev = this;
+            }
+
+            void append(list_node* node)
+            {
+                node->next = next;
+                node->prev = this;
+                next->prev = node;
+                next = node;
+            }
+
+            void prepend(list_node* node)
+            {
+                node->next = this;
+                node->prev = prev;
+                prev->next = node;
+                prev = node;
+            }
         };
+
+        template<class T>
+        class list_const_iterator;
+
+        template<class T>
+        class list_iterator
+        {
+            public:
+                using reference = typename list<T>::reference;
+
+                list_iterator(list_node<T>* node = nullptr)
+                    : current_{node}
+                { /* DUMMY BODY */ }
+
+                reference operator*()
+                {
+                    return current_->value;
+                }
+
+                list_iterator& operator++()
+                {
+                    if (current_)
+                        current_ = current_->next;
+
+                    return *this;
+                }
+
+                list_iterator operator++(int)
+                {
+                    auto bckp = current_;
+
+                    if (current_)
+                        current_ = current_->next;
+
+                    return list_iterator{bckp};
+                }
+
+                list_iterator& operator--()
+                {
+                    if (current_)
+                        current_ = current_->prev;
+
+                    return *this;
+                }
+
+                list_iterator operator--(int)
+                {
+                    auto bckp = current_;
+
+                    if (current_)
+                        current_ = current_->prev;
+
+                    return list_iterator{bckp};
+                }
+
+                list_node<T>* node()
+                {
+                    return current_;
+                }
+
+            private:
+                list_node<T>* current_;
+        };
+
+        // TODO: const iterator, iterator must be convertible to const iterator
     }
 
@@ -51 +159 @@
      */
 
-    template<class T, class Allocator = allocator<T>>
+    template<class T, class Allocator>
     class list
     {
@@ -57 +165 @@
             using value_type      = T;
             using reference       = value_type&;
-            using const_reference = value_type&;
+            using const_reference = const value_type&;
             using allocator_type  = Allocator;
 
-            using iterator        = void;
-            using const_iterator  = void;
-            using size_type       = void;
-            using difference_type = void;
+            using iterator        = aux::list_iterator<value_type>;
+            using const_iterator  = aux::list_const_iterator<value_type>;
+            using size_type       = size_t;
+            using difference_type = ptrdiff_t;
 
             using pointer       = typename allocator_traits<allocator_type>::pointer;
@@ -69 +177 @@
 
             using reverse_iterator       = std::reverse_iterator<iterator>;
-            using const_reverse_iterator = std::const_reverse_iterator<iterator>;
+            using const_reverse_iterator = std::reverse_iterator<const_iterator>;
 
             /**
@@ -80 +188 @@
 
             explicit list(const allocator_type& alloc)
-                : allocator_{alloc}, head_{nullptr}
+                : allocator_{alloc}, head_{nullptr}, size_{}
             { /* DUMMY BODY */ }
 
             explicit list(size_type n, const allocator_type& alloc = allocator_type{})
-                : allocator_{alloc}, head_{nullptr}
-            {
-                for (size_type i = 0; i < n; ++i)
-                {
-                    auto node = append_new_();
-                    allocator_.construct(&node->value);
-                }
+                : allocator_{alloc}, head_{nullptr}, size_{}
+            {
+                init_(
+                    aux::insert_iterator<value_type>{value_type{}},
+                    aux::insert_iterator<value_type>{size_}
+                );
             }
 
             list(size_type n, const value_type& val,
                  const allocator_type& alloc = allocator_type{})
-                : allocator_{alloc}, head_{nullptr}
-            {
-                for (size_type i = 0; i < n; ++i)
-                {
-                    auto node = append_new_();
-                    allocator_.construct(&node->value, val);
-                }
+                : allocator_{alloc}, head_{nullptr}, size_{}
+            {
+                init_(
+                    aux::insert_iterator<value_type>{val},
+                    aux::insert_iterator<value_type>{n}
+                );
             }
 
@@ -107 +213 @@
             list(InputIterator first, InputIterator last,
                  const allocator_type& alloc = allocator_type{})
-                : allocator_{alloc}, head_{nullptr}
+                : allocator_{alloc}, head_{nullptr}, size_{}
+            {
+                init_(first, last);
+            }
+
+            list(const list& other)
+                : list{other, other.allocator_}
+            { /* DUMMY BODY */ }
+
+            list(list&& other)
+                : allocator_{move(other.allocator_)},
+                  head_{move(other.head_)},
+                  size_{move(other.size_)}
+            {
+                other.head_ = nullptr;
+            }
+
+            list(const list& other, const allocator_type alloc)
+                : allocator_{alloc}, head_{nullptr}, size_{other.size_}
+            {
+                init_(other.begin(), other.end());
+            }
+
+            list(list&& other, const allocator_type& alloc)
+                : allocator_{alloc},
+                  head_{move(other.head_)},
+                  size_{move(other.size_)}
+            {
+                other.head_ = nullptr;
+            }
+
+            list(initializer_list<value_type> init, const allocator_type& alloc)
+                : allocator_{alloc}, head_{nullptr}, size_{}
+            {
+                init_(init.begin(), init.end());
+            }
+
+            ~list()
+            {
+                fini_();
+            }
+
+            list& operator=(const list& other)
+            {
+                fini_();
+
+                allocator_ = other.allocator_;
+
+                init_(other.begin(), other.end());
+            }
+
+            list& operator=(list&& other)
+                noexcept(allocator_traits<allocator_type>::is_always_equal::value)
+            {
+                fini_();
+
+                allocator_ = move(other.allocator_);
+
+                init_(
+                    make_move_iterator(other.begin()),
+                    make_move_iterator(other.end())
+                );
+            }
+
+            list& operator=(initializer_list<value_type> init)
+            {
+                fini_();
+
+                init_(init.begin(), init.end());
+            }
+
+            template<class InputIterator>
+            void assign(InputIterator first, InputIterator last)
+            {
+                fini_();
+
+                init_(first, last);
+            }
+
+            void assign(size_type n, const value_type& val)
+            {
+                fini_();
+
+                init_(
+                    aux::insert_iterator<value_type>{val},
+                    aux::insert_iterator<value_type>{n}
+                );
+            }
+
+            void assign(initializer_list<value_type> init)
+            {
+                fini_();
+
+                init_(init.begin(), init.end());
+            }
+
+            allocator_type get_allocator() const noexcept
+            {
+                return allocator_;
+            }
+
+            iterator begin() noexcept
+            {
+                return iterator{head_};
+            }
+
+            const_iterator begin() const noexcept
+            {
+                return cbegin();
+            }
+
+            iterator end() noexcept
+            {
+                return iterator{};
+            }
+
+            const_iterator end() const noexcept
+            {
+                return cend();
+            }
+
+            reverse_iterator rbegin() noexcept
+            {
+                return make_reverse_iterator(end());
+            }
+
+            const_reverse_iterator rbegin() const noexcept
+            {
+                return make_reverse_iterator(cend());
+            }
+
+            reverse_iterator rend() noexcept
+            {
+                return make_reverse_iterator(begin());
+            }
+
+            const_reverse_iterator rend() const noexcept
+            {
+                return make_reverse_iterator(cbegin());
+            }
+
+            const_iterator cbegin() const noexcept
+            {
+                return const_iterator{head_};
+            }
+
+            const_iterator cend() const noexcept
+            {
+                return const_iterator{};
+            }
+
+            const_reverse_iterator crbegin() const noexcept
+            {
+                return rbegin();
+            }
+
+            /**
+             * 23.3.5.3, capacity:
+             */
+
+            bool empty() const noexcept
+            {
+                return size_ == 0;
+            }
+
+            size_type size() const noexcept
+            {
+                return size_;
+            }
+
+            size_type max_size() const noexcept
+            {
+                return allocator_traits<allocator_type>::max_size(allocator_);
+            }
+
+            void resize(size_type sz)
+            {
+                // TODO: implement
+            }
+
+            void resize(size_type sz, const value_type& val)
+            {
+                // TODO: implement
+            }
+
+            reference front()
+            {
+                // TODO: bounds checking
+                return head_->value;
+            }
+
+            const_reference front() const
+            {
+                // TODO: bounds checking
+                return head_->value;
+            }
+
+            reference back()
+            {
+                // TODO: bounds checking
+                return head_->prev->value;
+            }
+
+            const_reference back() const
+            {
+                // TODO: bounds checking
+                return head_->prev->value;
+            }
+
+            /**
+             * 23.3.5.4, modifiers:
+             * Note: These should have no effect when an exception
+             *       is thrown while inserting, but since the only
+             *       functions that can throw are the constructors,
+             *       creating the node before any modifications to the
+             *       list itself will satisfy this requirement.
+             */
+
+            template<class... Args>
+            void emplace_front(Args&&... args)
+            {
+                prepend_new_(forward<Args>(args)...);
+            }
+
+            void pop_front()
+            {
+                if (head_)
+                {
+                    --size_;
+
+                    if (head_->next == head_)
+                    {
+                        delete head_;
+                        head_ = nullptr;
+                    }
+                    else
+                    {
+                        auto tmp = head_;
+                        head_->prev->next = head_->next;
+                        head_->next->prev = head_->prev;
+                        head_ = head_->next;
+
+                        delete tmp;
+                    }
+                }
+            }
+
+            template<class... Args>
+            void emplace_back(Args&&... args)
+            {
+                append_new_(forward<Args>(args)...);
+            }
+
+            void push_front(const value_type& value)
+            {
+                prepend_new_(value);
+            }
+
+            void push_front(value_type&& value)
+            {
+                prepend_new_(forward<value_type>(value));
+            }
+
+            void push_back(const value_type& value)
+            {
+                append_new_(value);
+            }
+
+            void push_back(value_type&& value)
+            {
+                append_new_(forward<value_type>(value));
+            }
+
+            void pop_back()
+            {
+                if (head_)
+                {
+                    --size_;
+                    auto target = head_->prev;
+
+                    if (!target)
+                    {
+                        delete head_;
+                        head_ = nullptr;
+                    }
+                    else
+                    {
+                        auto tmp = target;
+                        target->prev->next = target->next;
+                        target->next->prev = target->prev;
+                        target = target->next;
+
+                        delete tmp;
+                    }
+                }
+            }
+
+        /* private: */
+            allocator_type allocator_;
+            aux::list_node<value_type>* head_;
+            size_type size_;
+
+            template<class InputIterator>
+            void init_(InputIterator first, InputIterator last)
             {
                 while (first != last)
@@ -116 +525 @@
             }
 
-            list(const list& other)
-                : allocator_{other.allocator_}, head_{nullptr}
-            {
-                auto tmp = other.head_;
-
-                while (tmp->next != other.head_)
-                {
-                    auto node = append_new_();
-                    allocator_.construct(&node->value, tmp->value);
-                }
-            }
-
-            list(list&& other)
-            {
-                // TODO:
-            }
-
-        private:
-            allocator_type allocator_;
-            list_node<T>* head_;
-
-            list_node<T>* append_new_()
-            {
-                auto node = new aux::list_node<T>{};
+            void fini_()
+            {
+                if (!head_)
+                    return;
+
+                for (size_type i = size_type{}; i < size_; ++i)
+                {
+                    head_ = head_->next;
+                    delete head_->prev;
+                }
+
+                head_ = nullptr;
+                size_ = size_type{};
+            }
+
+            template<class... Args>
+            aux::list_node<value_type>* append_new_(Args&&... args)
+            {
+                auto node = new aux::list_node<value_type>{forward<Args>(args)...};
                 auto last = get_last_();
 
@@ -145 +549 @@
                     head_ = node;
                 else
-                {
-                    last->next = node;
-                    node->prev = last;
-
-                    node->next = head_;
-                    head_->prev = node;
-                }
+                    last->append(node);
+
+                ++size_;
 
                 return node;
             }
 
-            list_node<T>* get_last_()
+            template<class... Args>
+            aux::list_node<value_type>* prepend_new_(Args&&... args)
+            {
+                auto node = new aux::list_node<value_type>{forward<Args>(args)...};
+
+                if (!head_)
+                    head_ = node;
+                else
+                {
+                    head_->prepend(node);
+                    head_ = head_->prev;
+                }
+
+                ++size_;
+
+                return node;
+            }
+
+            aux::list_node<value_type>* get_last_()
             {
                 if (!head_)
                     return nullptr;
 
-                auto node = head_;
-
-                while (node->next != head_)
-                    node = node->next;
+                return head_->prev;
+            }
+
+            template<class InputIterator>
+            void insert_range_(InputIterator first, InputIterator last,
+                               aux::list_node<value_type>* where = nullptr)
+            {
+                if (first == last)
+                    return;
+
+                if (!where)
+                    where = get_last_();
+
+                while (first != last)
+                {
+                    where->append(new aux::list_node<value_type>{*first++});
+                    where = where->next;
+                }
             }
     };