Index: uspace/lib/cpp/include/impl/deque.hpp =================================================================== --- uspace/lib/cpp/include/impl/deque.hpp (revision 9475fafb476c76d60d268d53b092315615d06055) +++ uspace/lib/cpp/include/impl/deque.hpp (revision 3a06cc605fe90574c86f88ec90fbe76a2f55d25c) @@ -1,4 +1,4 @@ /* - * Copyright (c) 2017 Jaroslav Jindrak + * Copyright (c) 2018 Jaroslav Jindrak * All rights reserved. * @@ -31,8 +31,11 @@ #include +#include #include namespace std { + template> + class deque; namespace aux @@ -41,5 +44,16 @@ class deque_iterator { - // TODO: implement + using size_type = typename std::deque::size_type; + using value_type = typename std::deque::value_type; + using difference_type = size_type; + + public: + deque_iterator(deque* deq, size_type idx) + : deq_{deq}, idx_{idx} + { /* DUMMY BODY */ } + + private: + deque* deq_; + size_type idx_; }; @@ -55,5 +69,5 @@ */ - template> + template class deque { @@ -83,6 +97,10 @@ 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,5 +148,5 @@ ~deque() { - // TODO: implement + fini_(); } @@ -236,5 +254,5 @@ size_type size() const noexcept { - // TODO: implement + return size_; } @@ -261,15 +279,15 @@ 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,5 +297,5 @@ } - const_reference at(size_type idx) + const_reference at(size_type idx) const { // TODO: implement @@ -328,20 +346,36 @@ 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); + ++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); + ++size_; + + if (back_bucket_idx_ >= bucket_size_) + add_new_bucket_back_(); } @@ -374,10 +408,45 @@ 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,5 +456,5 @@ } - iterator eraser(cosnt_iteterator first, const_iterator last) + iterator erase(const_iterator first, const_iterator last) { // TODO: implement @@ -400,19 +469,128 @@ 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,4 +599,5 @@ { // TODO: implement + return false; } @@ -427,10 +606,12 @@ { // TODO: implement - } - - template - bool operator=!(const deque& lhs, const deque& rhs) + return false; + } + + template + bool operator!=(const deque& lhs, const deque& rhs) { // TODO: implement + return false; } @@ -439,4 +620,5 @@ { // TODO: implement + return false; } @@ -445,4 +627,5 @@ { // TODO: implement + return false; } @@ -451,4 +634,5 @@ { // TODO: implement + return false; }