Changeset 5072c67 in mainline

Timestamp:

2018-07-05T21:41:20Z (6 years ago)

Author:

Dzejrou <dzejrou@…>

Branches:

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

Children:

a44c35d

Parents:

806ce18

git-author:

Dzejrou <dzejrou@…> (2018-04-11 19:14:16)

git-committer:

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

Message:

cpp: finished constructors, fixed iterators, added misc operations

File:

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

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

@@ -61 +61 @@
                 using iterator_category = random_access_iterator_tag;
 
-                deque_const_iterator(deque<T, Allocator>& deq, size_type idx)
+                deque_const_iterator(const deque<T, Allocator>& deq, size_type idx)
                     : deq_{deq}, idx_{idx}
                 { /* DUMMY BODY */ }
@@ -136 +136 @@
                 }
 
+                difference_type operator-(const deque_const_iterator& rhs)
+                {
+                    return idx_ - rhs.idx_;
+                }
+
                 size_type idx() const
                 {
@@ -142 +147 @@
 
             private:
-                deque<T, Allocator>& deq_;
+                const deque<T, Allocator>& deq_;
                 size_type idx_;
         };
@@ -258 +263 @@
                 }
 
+                difference_type operator-(const deque_iterator& rhs)
+                {
+                    return idx_ - rhs.idx_;
+                }
+
                 size_type idx() const
                 {
@@ -324 +334 @@
 
             explicit deque(size_type n, const allocator_type& alloc = allocator_type{})
-            {
-                // TODO: implement
+                : allocator_{alloc}, front_bucket_idx_{bucket_size_}, back_bucket_idx_{},
+                  front_bucket_{}, back_bucket_{}, bucket_count_{},
+                  bucket_capacity_{}, size_{n}, data_{}
+            {
+                prepare_for_size_(n);
+                init_();
+
+                for (size_type i = 0; i < size_; ++i)
+                    allocator_.construct(&(*this)[i]);
+                back_bucket_idx_ = size_ % bucket_size_;
             }
 
             deque(size_type n, const value_type& value, const allocator_type& alloc = allocator_type{})
-            {
-                // TODO: implement
+                : allocator_{alloc}, front_bucket_idx_{bucket_size_}, back_bucket_idx_{},
+                  front_bucket_{}, back_bucket_{}, bucket_count_{},
+                  bucket_capacity_{}, size_{n}, data_{}
+            {
+                prepare_for_size_(n);
+                init_();
+
+                for (size_type i = 0; i < size_; ++i)
+                    (*this)[i] = value;
+                back_bucket_idx_ = size_ % bucket_size_;
             }
 
             template<class InputIterator>
-            deque(InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type{})
-            {
-                // TODO: implement
+            deque(InputIterator first, InputIterator last,
+                  const allocator_type& alloc = allocator_type{})
+                : allocator_{alloc}, front_bucket_idx_{bucket_size_},
+                  back_bucket_idx_{}, front_bucket_{}, back_bucket_{},
+                  bucket_count_{}, bucket_capacity_{}, size_{},
+                  data_{}
+            {
+                copy_from_range_(first, last);
             }
 
             deque(const deque& other)
-            {
-                // TODO: implement
-            }
+                : deque{other.begin(), other.end(), other.allocator_}
+            { /* DUMMY BODY */ }
 
             deque(deque&& other)
-            {
-                // TODO: implement
+                : allocator_{move(other.allocator_)},
+                  front_bucket_idx_{other.front_bucket_idx_},
+                  back_bucket_idx_{other.front_bucket_idx_},
+                  front_bucket_{other.front_bucket_},
+                  back_bucket_{other.back_bucket_},
+                  bucket_count_{other.bucket_count_},
+                  bucket_capacity_{other.bucket_capacity_},
+                  size_{other.size_}, data_{other.data_}
+            {
+                other.data_ = nullptr;
+                other.clear();
             }
 
             deque(const deque& other, const allocator_type& alloc)
-            {
-                // TODO: implement
-            }
+                : deque{other.begin(), other.end(), alloc}
+            { /* DUMMY BODY */ }
 
             deque(deque&& other, const allocator_type& alloc)
-            {
-                // TODO: implement
+                : allocator_{alloc},
+                  front_bucket_idx_{other.front_bucket_idx_},
+                  back_bucket_idx_{other.front_bucket_idx_},
+                  front_bucket_{other.front_bucket_},
+                  back_bucket_{other.back_bucket_},
+                  bucket_count_{other.bucket_count_},
+                  bucket_capacity_{other.bucket_capacity_},
+                  size_{other.size_}, data_{other.data_}
+            {
+                other.data_ = nullptr;
+                other.clear();
             }
 
             deque(initializer_list<T> init, const allocator_type& alloc = allocator_type{})
-            {
-                // TODO: implement
+                : allocator_{alloc}, front_bucket_idx_{bucket_size_},
+                  back_bucket_idx_{}, front_bucket_{}, back_bucket_{},
+                  bucket_count_{}, bucket_capacity_{}, size_{},
+                  data_{}
+            {
+                copy_from_range_(init.begin(), init.end());
             }
 
@@ -377 +428 @@
                 noexcept(allocator_traits<allocator_type>::is_always_equal::value)
             {
-                // TODO: implement
+                swap(other);
+                other.clear();
             }
 
@@ -512 +564 @@
             reference at(size_type idx)
             {
-                // TODO: implement
+                // TODO: bounds checking
+                return operator[](idx);
             }
 
             const_reference at(size_type idx) const
             {
-                // TODO: implement
+                // TODO: bounds checking
+                return operator[](idx);
             }
 
             reference front()
             {
-                // TODO: implement
+                return *begin();
             }
 
             const_reference front() const
             {
-                // TODO: implement
+                return *cbegin();
             }
 
             reference back()
             {
-                // TODO: implement
+                auto tmp = end();
+
+                return *(--tmp);
             }
 
             const_reference back() const
             {
-                // TODO: implement
+                auto tmp = cend();
+
+                return *(--tmp);
             }
 
@@ -687 +745 @@
             void clear() noexcept
             {
-                fini_();
+                if (data_)
+                    fini_();
 
                 front_bucket_ = default_front_;
@@ -733 +792 @@
             }
 
+            void prepare_for_size_(size_type size)
+            {
+                if (data_)
+                    fini_();
+
+                if (size < bucket_size_) // Always front_bucket_ != back_bucket_.
+                    bucket_count_ = bucket_capacity_ = 2;
+                else if (size % bucket_size_ == 0)
+                    bucket_count_ = bucket_capacity_ = size / bucket_size_ + 1;
+                else
+                    bucket_count_ = bucket_capacity_ = size / bucket_size_ + 2;
+
+                front_bucket_ = 0;
+                back_bucket_ = bucket_capacity_ - 1;
+            }
+
+            template<class Iterator>
+            void copy_from_range_(Iterator first, Iterator last)
+            {
+                size_ = distance(first, last);
+                prepare_for_size_(size_);
+                init_();
+
+                auto it = begin();
+                while (first != last)
+                    *it++ = *first++;
+
+                // Remainder is the amount of elements in the last bucket.
+                back_bucket_idx_ = size_ % bucket_size_;
+            }
+
             void fini_()
             {