Changeset 9019d85 in mainline
- Timestamp:
- 2018-07-05T21:41:21Z (7 years ago)
- Branches:
- lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
- Children:
- f9ce7cd
- Parents:
- bdc55009
- git-author:
- Dzejrou <dzejrou@…> (2018-04-17 19:05:01)
- git-committer:
- Dzejrou <dzejrou@…> (2018-07-05 21:41:21)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
uspace/lib/cpp/include/impl/deque.hpp
rbdc55009 r9019d85 30 30 #define LIBCPP_DEQUE 31 31 32 #include <algorithm> 32 33 #include <initializer_list> 34 #include <internal/insert_iterator.hpp> 33 35 #include <iterator> 34 36 #include <memory> … … 51 53 52 54 template<class T, class Allocator> 55 class deque_iterator; 56 57 template<class T, class Allocator> 53 58 class deque_const_iterator 54 59 { … … 65 70 { /* DUMMY BODY */ } 66 71 72 deque_const_iterator(const deque_const_iterator& other) 73 : deq_{other.deq_}, idx_{other.idx_} 74 { /* DUMMY BODY */ } 75 67 76 deque_const_iterator& operator=(const deque_const_iterator& other) 68 77 { … … 144 153 { 145 154 return idx_; 155 } 156 157 operator deque_iterator<T, Allocator>() 158 { 159 return deque_iterator{deq_, idx_}; 146 160 } 147 161 … … 180 194 { /* DUMMY BODY */ } 181 195 196 deque_iterator(const deque_iterator& other) 197 : deq_{other.deq_}, idx_{other.idx_} 198 { /* DUMMY BODY */ } 199 182 200 deque_iterator(const deque_const_iterator<T, Allocator>& other) 183 201 : deq_{other.deq_}, idx_{other.idx_} … … 271 289 { 272 290 return idx_; 291 } 292 293 operator deque_const_iterator<T, Allocator>() 294 { 295 return deque_const_iterator{deq_, idx_}; 273 296 } 274 297 … … 675 698 iterator emplace(const_iterator position, Args&&... args) 676 699 { 677 // TODO: implement 700 auto idx = position.idx(); 701 shift_right_(idx, 1); 702 703 allocator_traits<allocator_type>::construct( 704 allocator_, 705 &data_[get_bucket_index_(idx)][get_element_index_(idx)], 706 forward<Args>(args)... 707 ); 708 ++size_; 709 710 return iterator{*this, idx}; 678 711 } 679 712 … … 716 749 iterator insert(const_iterator position, const value_type& value) 717 750 { 718 // TODO: implement 751 auto idx = position.idx(); 752 shift_right_(idx, 1); 753 754 /** 755 * Note: One may notice that when working with the deque 756 * iterator, we use its index without any checks. 757 * This is because a valid iterator will always have 758 * a valid index as functions like pop_back or erase 759 * invalidate iterators. 760 */ 761 data_[get_bucket_index_(idx)][get_element_index_(idx)] = value; 762 ++size_; 763 764 return iterator{*this, idx}; 719 765 } 720 766 721 767 iterator insert(const_iterator position, value_type&& value) 722 768 { 723 // TODO: implement 769 auto idx = position.idx(); 770 shift_right_(idx, 1); 771 772 data_[get_bucket_index_(idx)][get_element_index_(idx)] = forward<value_type>(value); 773 ++size_; 774 775 return iterator{*this, idx}; 724 776 } 725 777 726 778 iterator insert(const_iterator position, size_type n, const value_type& value) 727 779 { 728 // TODO: implement 780 return insert( 781 position, 782 aux::insert_iterator{value}, 783 aux::insert_iterator{n} 784 ); 729 785 } 730 786 … … 732 788 iterator insert(const_iterator position, InputIterator first, InputIterator last) 733 789 { 734 // TODO: implement 790 auto idx = position.idx(); 791 auto count = distance(first, last); 792 793 if (idx < size_ / 2) 794 { 795 shift_left_(idx, count); 796 797 iterator it{*this, idx - 1}; 798 while (first != last) 799 *it++ = *first++; 800 } 801 else 802 { 803 shift_right_(idx, count); 804 805 iterator it{*this, idx}; 806 while (first != last) 807 *it++ = *first++; 808 } 809 810 size_ += count; 811 812 return iterator{*this, idx}; 735 813 } 736 814 737 815 iterator insert(const_iterator position, initializer_list<value_type> init) 738 816 { 739 // TODO: implement817 return insert(position, init.begin(), init.end()); 740 818 } 741 819 … … 746 824 747 825 if (back_bucket_idx_ == 0) 748 { // Means we gotta pop data_[ front_bucket_][bucket_size_ - 1]!826 { // Means we gotta pop data_[back_bucket_ - 1][bucket_size_ - 1]! 749 827 if (data_[back_bucket_]) 750 828 allocator_.deallocate(data_[back_bucket_], bucket_size_); … … 766 844 767 845 if (front_bucket_idx_ >= bucket_size_) 768 { // Means we gotta pop data_[front_bucket_ ][0]!846 { // Means we gotta pop data_[front_bucket_ + 1][0]! 769 847 if (data_[front_bucket_]) 770 848 allocator_.deallocate(data_[front_bucket_], bucket_size_); … … 863 941 fini_(); 864 942 865 if (size < bucket_size_) // Always front_bucket_ != back_bucket_. 866 bucket_count_ = bucket_capacity_ = 2; 867 else if (size % bucket_size_ == 0) 868 bucket_count_ = bucket_capacity_ = size / bucket_size_ + 2; 869 else 870 bucket_count_ = bucket_capacity_ = size / bucket_size_ + 2; 943 bucket_count_ = bucket_capacity_ = size / bucket_size_ + 2; 871 944 872 945 front_bucket_ = 0; … … 889 962 } 890 963 964 void ensure_space_front_(size_type idx, size_type count) 965 { 966 auto free_space = bucket_size_ - elements_in_front_bucket_(); 967 if (front_bucket_idx_ == 0) 968 free_space = 0; 969 970 if (count <= free_space) 971 { 972 front_bucket_idx_ -= count; 973 return; 974 } 975 976 count -= free_space; 977 978 auto buckets_needed = count / bucket_size_; 979 if (count % bucket_size_ != 0) 980 ++buckets_needed; 981 982 for (size_type i = size_type{}; i < buckets_needed; ++i) 983 add_new_bucket_front_(); 984 985 front_bucket_idx_ = bucket_size_ - (count % bucket_size_); 986 } 987 988 void ensure_space_back_(size_type idx, size_type count) 989 { 990 auto free_space = bucket_size_ - back_bucket_idx_; 991 if (count < free_space) 992 return; 993 994 count -= free_space; 995 auto buckets_needed = count / bucket_size_; 996 if (count % bucket_size_ != 0) 997 ++buckets_needed; 998 999 for (size_type i = size_type{}; i < buckets_needed; ++i) 1000 add_new_bucket_back_(); 1001 1002 back_bucket_idx_ = (back_bucket_idx_ + count) % bucket_size_; 1003 } 1004 1005 void shift_right_(size_type idx, size_type count) 1006 { 1007 ensure_space_back_(idx, count); 1008 1009 iterator it{*this, idx}; 1010 copy_backward(it, end(), end() + count - 1); 1011 1012 } 1013 1014 void shift_left_(size_type idx, size_type count) 1015 { 1016 ensure_space_front_(idx, count); 1017 1018 copy( 1019 iterator{*this, count}, 1020 iterator{*this, idx + count - 1}, 1021 iterator{*this, 0} 1022 ); 1023 } 1024 891 1025 void fini_() 892 1026 { … … 914 1048 915 1049 ++back_bucket_; 1050 ++bucket_count_; 916 1051 data_[back_bucket_] = allocator_.allocate(bucket_size_); 917 1052 back_bucket_idx_ = size_type{}; … … 924 1059 925 1060 --front_bucket_; 1061 ++bucket_count_; 926 1062 data_[front_bucket_] = allocator_.allocate(bucket_size_); 927 1063 front_bucket_idx_ = bucket_size_; … … 933 1069 value_type** new_data = new value_type*[bucket_capacity_]; 934 1070 1071 /** 1072 * Note: This currently expands both sides whenever one reaches 1073 * its limit. Might be better to expand only one (or both when 1074 * the other is near its limit)? 1075 */ 935 1076 size_type new_front = bucket_capacity_ / 4; 936 size_type new_back = bucket_capacity_ - bucket_capacity_ / 4- 1;1077 size_type new_back = new_front + bucket_count_ - 1; 937 1078 938 1079 for (size_type i = new_front, j = front_bucket_; i <= new_back; ++i, ++j)
Note:
See TracChangeset
for help on using the changeset viewer.