Index: uspace/lib/cpp/include/impl/deque.hpp =================================================================== --- uspace/lib/cpp/include/impl/deque.hpp (revision bdc55009daf9f21e2f3aaea983dcf975641df0d3) +++ uspace/lib/cpp/include/impl/deque.hpp (revision 9019d859956c53074cbfb4e383a8a0b4bf5563aa) @@ -30,5 +30,7 @@ #define LIBCPP_DEQUE +#include #include +#include #include #include @@ -51,4 +53,7 @@ template + class deque_iterator; + + template class deque_const_iterator { @@ -65,4 +70,8 @@ { /* DUMMY BODY */ } + deque_const_iterator(const deque_const_iterator& other) + : deq_{other.deq_}, idx_{other.idx_} + { /* DUMMY BODY */ } + deque_const_iterator& operator=(const deque_const_iterator& other) { @@ -144,4 +153,9 @@ { return idx_; + } + + operator deque_iterator() + { + return deque_iterator{deq_, idx_}; } @@ -180,4 +194,8 @@ { /* DUMMY BODY */ } + deque_iterator(const deque_iterator& other) + : deq_{other.deq_}, idx_{other.idx_} + { /* DUMMY BODY */ } + deque_iterator(const deque_const_iterator& other) : deq_{other.deq_}, idx_{other.idx_} @@ -271,4 +289,9 @@ { return idx_; + } + + operator deque_const_iterator() + { + return deque_const_iterator{deq_, idx_}; } @@ -675,5 +698,15 @@ iterator emplace(const_iterator position, Args&&... args) { - // TODO: implement + auto idx = position.idx(); + shift_right_(idx, 1); + + allocator_traits::construct( + allocator_, + &data_[get_bucket_index_(idx)][get_element_index_(idx)], + forward(args)... + ); + ++size_; + + return iterator{*this, idx}; } @@ -716,15 +749,38 @@ iterator insert(const_iterator position, const value_type& value) { - // TODO: implement + auto idx = position.idx(); + shift_right_(idx, 1); + + /** + * Note: One may notice that when working with the deque + * iterator, we use its index without any checks. + * This is because a valid iterator will always have + * a valid index as functions like pop_back or erase + * invalidate iterators. + */ + data_[get_bucket_index_(idx)][get_element_index_(idx)] = value; + ++size_; + + return iterator{*this, idx}; } iterator insert(const_iterator position, value_type&& value) { - // TODO: implement + auto idx = position.idx(); + shift_right_(idx, 1); + + data_[get_bucket_index_(idx)][get_element_index_(idx)] = forward(value); + ++size_; + + return iterator{*this, idx}; } iterator insert(const_iterator position, size_type n, const value_type& value) { - // TODO: implement + return insert( + position, + aux::insert_iterator{value}, + aux::insert_iterator{n} + ); } @@ -732,10 +788,32 @@ iterator insert(const_iterator position, InputIterator first, InputIterator last) { - // TODO: implement + auto idx = position.idx(); + auto count = distance(first, last); + + if (idx < size_ / 2) + { + shift_left_(idx, count); + + iterator it{*this, idx - 1}; + while (first != last) + *it++ = *first++; + } + else + { + shift_right_(idx, count); + + iterator it{*this, idx}; + while (first != last) + *it++ = *first++; + } + + size_ += count; + + return iterator{*this, idx}; } iterator insert(const_iterator position, initializer_list init) { - // TODO: implement + return insert(position, init.begin(), init.end()); } @@ -746,5 +824,5 @@ if (back_bucket_idx_ == 0) - { // Means we gotta pop data_[front_bucket_][bucket_size_ - 1]! + { // Means we gotta pop data_[back_bucket_ - 1][bucket_size_ - 1]! if (data_[back_bucket_]) allocator_.deallocate(data_[back_bucket_], bucket_size_); @@ -766,5 +844,5 @@ if (front_bucket_idx_ >= bucket_size_) - { // Means we gotta pop data_[front_bucket_][0]! + { // Means we gotta pop data_[front_bucket_ + 1][0]! if (data_[front_bucket_]) allocator_.deallocate(data_[front_bucket_], bucket_size_); @@ -863,10 +941,5 @@ 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_ + 2; - else - bucket_count_ = bucket_capacity_ = size / bucket_size_ + 2; + bucket_count_ = bucket_capacity_ = size / bucket_size_ + 2; front_bucket_ = 0; @@ -889,4 +962,65 @@ } + void ensure_space_front_(size_type idx, size_type count) + { + auto free_space = bucket_size_ - elements_in_front_bucket_(); + if (front_bucket_idx_ == 0) + free_space = 0; + + if (count <= free_space) + { + front_bucket_idx_ -= count; + return; + } + + count -= free_space; + + auto buckets_needed = count / bucket_size_; + if (count % bucket_size_ != 0) + ++buckets_needed; + + for (size_type i = size_type{}; i < buckets_needed; ++i) + add_new_bucket_front_(); + + front_bucket_idx_ = bucket_size_ - (count % bucket_size_); + } + + void ensure_space_back_(size_type idx, size_type count) + { + auto free_space = bucket_size_ - back_bucket_idx_; + if (count < free_space) + return; + + count -= free_space; + auto buckets_needed = count / bucket_size_; + if (count % bucket_size_ != 0) + ++buckets_needed; + + for (size_type i = size_type{}; i < buckets_needed; ++i) + add_new_bucket_back_(); + + back_bucket_idx_ = (back_bucket_idx_ + count) % bucket_size_; + } + + void shift_right_(size_type idx, size_type count) + { + ensure_space_back_(idx, count); + + iterator it{*this, idx}; + copy_backward(it, end(), end() + count - 1); + + } + + void shift_left_(size_type idx, size_type count) + { + ensure_space_front_(idx, count); + + copy( + iterator{*this, count}, + iterator{*this, idx + count - 1}, + iterator{*this, 0} + ); + } + void fini_() { @@ -914,4 +1048,5 @@ ++back_bucket_; + ++bucket_count_; data_[back_bucket_] = allocator_.allocate(bucket_size_); back_bucket_idx_ = size_type{}; @@ -924,4 +1059,5 @@ --front_bucket_; + ++bucket_count_; data_[front_bucket_] = allocator_.allocate(bucket_size_); front_bucket_idx_ = bucket_size_; @@ -933,6 +1069,11 @@ value_type** new_data = new value_type*[bucket_capacity_]; + /** + * Note: This currently expands both sides whenever one reaches + * its limit. Might be better to expand only one (or both when + * the other is near its limit)? + */ size_type new_front = bucket_capacity_ / 4; - size_type new_back = bucket_capacity_ - bucket_capacity_ / 4 - 1; + size_type new_back = new_front + bucket_count_ - 1; for (size_type i = new_front, j = front_bucket_; i <= new_back; ++i, ++j)