Changeset 3a06cc6 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:

6e93323

Parents:

9475faf

git-author:

Dzejrou <dzejrou@…> (2018-04-08 18:39:07)

git-committer:

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

Message:

cpp: added a basic deque implementation, currently push/pop/clear/indexed access

File:

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

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

@@ -1 +1 @@
 /*
- * Copyright (c) 2017 Jaroslav Jindrak
+ * Copyright (c) 2018 Jaroslav Jindrak
  * All rights reserved.
  *
@@ -31 +31 @@
 
 #include <initializer_list>
+#include <iterator>
 #include <memory>
 
 namespace std
 {
+    template<class T, class Allocator = allocator<T>>
+    class deque;
 
     namespace aux
@@ -41 +44 @@
         class deque_iterator
         {
-            // TODO: implement
+            using size_type = typename std::deque<T, Allocator>::size_type;
+            using value_type = typename std::deque<T, Allocator>::value_type;
+            using difference_type = size_type;
+
+            public:
+                deque_iterator(deque<T, Allocator>* deq, size_type idx)
+                    : deq_{deq}, idx_{idx}
+                { /* DUMMY BODY */ }
+
+            private:
+                deque<T, Allocator>* deq_;
+                size_type idx_;
         };
 
@@ -55 +69 @@
      */
 
-    template<class T, class Allocator = allocator<T>>
+    template<class T, class Allocator>
     class deque
     {
@@ -83 +97 @@
 
             explicit deque(const allocator_type& alloc)
-            {
-                // TODO: implement
+                : allocator_{alloc}, front_bucket_idx_{bucket_size_},
+                  back_bucket_idx_{0}, front_bucket_{default_front_},
+                  back_bucket_{default_back_}, bucket_count_{default_bucket_count_},
+                  bucket_capacity_{default_bucket_capacity_}, size_{}, data_{}
+            {
+                init_();
             }
 
@@ -130 +148 @@
             ~deque()
             {
-                // TODO: implement
+                fini_();
             }
 
@@ -236 +254 @@
             size_type size() const noexcept
             {
-                // TODO: implement
+                return size_;
             }
 
@@ -261 +279 @@
             bool empty() const noexcept
             {
-                // TODO: implement
+                return size_ == size_type{};
             }
 
             reference operator[](size_type idx)
             {
-                // TODO: implement
-            }
-
-            const_reference operator[](size_type idx)
-            {
-                // TODO: implement
+                return data_[get_bucket_index_(idx)][get_element_index_(idx)];
+            }
+
+            const_reference operator[](size_type idx) const
+            {
+                return data_[get_bucket_index_(idx)][get_element_index_(idx)];
             }
 
@@ -279 +297 @@
             }
 
-            const_reference at(size_type idx)
+            const_reference at(size_type idx) const
             {
                 // TODO: implement
@@ -328 +346 @@
             void push_front(const value_type& value)
             {
-                // TODO: implement
+                if (front_bucket_idx_ == 0)
+                    add_new_bucket_front_();
+
+                data_[front_bucket_][--front_bucket_idx_] = value;
+                ++size_;
             }
 
             void push_front(value_type&& value)
             {
-                // TODO: implement
+                if (front_bucket_idx_ == 0)
+                    add_new_bucket_front_();
+
+                data_[front_bucket_][--front_bucket_idx_] = forward<value_type>(value);
+                ++size_;
             }
 
             void push_back(const value_type& value)
             {
-                // TODO: implement
+                data_[back_bucket_][back_bucket_idx_++] = value;
+                ++size_;
+
+                if (back_bucket_idx_ >= bucket_size_)
+                    add_new_bucket_back_();
             }
 
             void push_back(value_type&& value)
             {
-                // TODO: implement
+                data_[back_bucket_][back_bucket_idx_++] = forward<value_type>(value);
+                ++size_;
+
+                if (back_bucket_idx_ >= bucket_size_)
+                    add_new_bucket_back_();
             }
 
@@ -374 +408 @@
             void pop_back()
             {
-                // TODO: implement
+                if (empty())
+                    return;
+
+                if (back_bucket_idx_ == 0)
+                { // Means we gotta pop data_[front_bucket_][bucket_size_ - 1]!
+                    if (data_[back_bucket_])
+                        allocator_.deallocate(data_[back_bucket_], bucket_size_);
+
+                    --back_bucket_;
+                    back_bucket_idx_ = bucket_size_ - 1;
+                }
+                else
+                    --back_bucket_idx_;
+
+                allocator_.destroy(&data_[back_bucket_][back_bucket_idx_]);
+                --size_;
             }
 
             void pop_front()
             {
-                // TODO: implement
+                if (empty())
+                    return;
+
+                if (front_bucket_idx_ >= bucket_size_)
+                { // Means we gotta pop data_[front_bucket_][0]!
+                    if (data_[front_bucket_])
+                        allocator_.deallocate(data_[front_bucket_], bucket_size_);
+
+                    ++front_bucket_;
+                    front_bucket_idx_ = 1;
+
+                    allocator_.destroy(&data_[front_bucket_][0]);
+                }
+                else
+                {
+                    allocator_.destroy(&data_[front_bucket_][front_bucket_idx_]);
+
+                    ++front_bucket_idx_;
+                }
+
+                --size_;
             }
 
@@ -387 +456 @@
             }
 
-            iterator eraser(cosnt_iteterator first, const_iterator last)
+            iterator erase(const_iterator first, const_iterator last)
             {
                 // TODO: implement
@@ -400 +469 @@
             void clear() noexcept
             {
-                // TODO: implement
-            }
-
-        private:
+                fini_();
+
+                front_bucket_ = default_front_;
+                back_bucket_ = default_back_;
+                bucket_count_ = default_bucket_count_;
+                bucket_capacity_ = default_bucket_capacity_;
+                size_ = size_type{};
+
+                init_();
+            }
+
+        /* private: */
             allocator_type allocator_;
 
+            /**
+             * Note: In our implementation, front_bucket_idx_
+             *       points at the first element and back_bucket_idx_
+             *       points at the one past last element. Because of this,
+             *       some operations may be done in inverse order
+             *       depending on the side they are applied to.
+             */
             size_type front_bucket_idx_;
             size_type back_bucket_idx_;
+            size_type front_bucket_;
+            size_type back_bucket_;
 
             static constexpr size_type bucket_size_{16};
+            static constexpr size_type default_bucket_count_{2};
+            static constexpr size_type default_bucket_capacity_{4};
+            static constexpr size_type default_front_{1};
+            static constexpr size_type default_back_{2};
 
             size_type bucket_count_;
             size_type bucket_capacity_;
+            size_type size_{};
 
             value_type** data_;
+
+            void init_()
+            {
+                data_ = new value_type*[bucket_capacity_];
+
+                for (size_type i = front_bucket_; i <= back_bucket_; ++i)
+                    data_[i] = allocator_.allocate(bucket_size_);
+            }
+
+            void fini_()
+            {
+                for (size_type i = front_bucket_; i <= back_bucket_; ++i)
+                    allocator_.deallocate(data_[i], bucket_size_);
+
+                delete[] data_;
+                data_ = nullptr;
+            }
+
+            bool has_bucket_space_back_() const
+            {
+                return back_bucket_ < bucket_capacity_ - 1;
+            }
+
+            bool has_bucket_space_front_() const
+            {
+                return front_bucket_ > 0;
+            }
+
+            void add_new_bucket_back_()
+            {
+                if (!has_bucket_space_back_())
+                    expand_();
+
+                ++back_bucket_;
+                data_[back_bucket_] = allocator_.allocate(bucket_size_);
+                back_bucket_idx_ = size_type{};
+            }
+
+            void add_new_bucket_front_()
+            {
+                if (!has_bucket_space_front_())
+                    expand_();
+
+                --front_bucket_;
+                data_[front_bucket_] = allocator_.allocate(bucket_size_);
+                front_bucket_idx_ = bucket_size_;
+            }
+
+            void expand_()
+            {
+                bucket_capacity_ *= 2;
+                value_type** new_data = new value_type*[bucket_capacity_];
+
+                size_type new_front = bucket_capacity_ / 4;
+                size_type new_back = bucket_capacity_ - bucket_capacity_ / 4 - 1;
+
+                for (size_type i = new_front, j = front_bucket_; i <= new_back; ++i, ++j)
+                    new_data[i] = move(data_[j]);
+                std::swap(data_, new_data);
+
+                delete[] new_data;
+                front_bucket_ = new_front;
+                back_bucket_ = new_back;
+            }
+
+            size_type get_bucket_index_(size_type idx) const
+            {
+                if (idx < elements_in_front_bucket_())
+                    return front_bucket_;
+
+                idx -= elements_in_front_bucket_();
+                return idx / bucket_size_ + front_bucket_ + 1;
+            }
+
+            size_type get_element_index_(size_type idx) const
+            {
+                if (idx < elements_in_front_bucket_())
+                    return bucket_size_ - elements_in_front_bucket_() + idx;
+
+                idx -= elements_in_front_bucket_();
+                return idx % bucket_size_;
+            }
+
+            size_type elements_in_front_bucket_() const
+            {
+                return bucket_size_ - front_bucket_idx_;
+            }
     };
 
@@ -421 +599 @@
     {
         // TODO: implement
+        return false;
     }
 
@@ -427 +606 @@
     {
         // TODO: implement
-    }
-
-    template<class T, class Allocator>
-    bool operator=!(const deque<T, Allocator>& lhs, const deque<T, Allocator>& rhs)
+        return false;
+    }
+
+    template<class T, class Allocator>
+    bool operator!=(const deque<T, Allocator>& lhs, const deque<T, Allocator>& rhs)
     {
         // TODO: implement
+        return false;
     }
 
@@ -439 +620 @@
     {
         // TODO: implement
+        return false;
     }
 
@@ -445 +627 @@
     {
         // TODO: implement
+        return false;
     }
 
@@ -451 +634 @@
     {
         // TODO: implement
+        return false;
     }