diff options
author | Anton Samokhvalov <pg83@yandex.ru> | 2022-02-10 16:45:15 +0300 |
---|---|---|
committer | Daniil Cherednik <dcherednik@yandex-team.ru> | 2022-02-10 16:45:15 +0300 |
commit | 72cb13b4aff9bc9cf22e49251bc8fd143f82538f (patch) | |
tree | da2c34829458c7d4e74bdfbdf85dff449e9e7fb8 /library/cpp/containers/paged_vector | |
parent | 778e51ba091dc39e7b7fcab2b9cf4dbedfb6f2b5 (diff) | |
download | ydb-72cb13b4aff9bc9cf22e49251bc8fd143f82538f.tar.gz |
Restoring authorship annotation for Anton Samokhvalov <pg83@yandex.ru>. Commit 1 of 2.
Diffstat (limited to 'library/cpp/containers/paged_vector')
-rw-r--r-- | library/cpp/containers/paged_vector/paged_vector.cpp | 2 | ||||
-rw-r--r-- | library/cpp/containers/paged_vector/paged_vector.h | 812 | ||||
-rw-r--r-- | library/cpp/containers/paged_vector/ut/paged_vector_ut.cpp | 624 | ||||
-rw-r--r-- | library/cpp/containers/paged_vector/ut/ya.make | 24 |
4 files changed, 731 insertions, 731 deletions
diff --git a/library/cpp/containers/paged_vector/paged_vector.cpp b/library/cpp/containers/paged_vector/paged_vector.cpp index e354caf09d..52f91880bf 100644 --- a/library/cpp/containers/paged_vector/paged_vector.cpp +++ b/library/cpp/containers/paged_vector/paged_vector.cpp @@ -1 +1 @@ -#include "paged_vector.h" +#include "paged_vector.h" diff --git a/library/cpp/containers/paged_vector/paged_vector.h b/library/cpp/containers/paged_vector/paged_vector.h index 6a3657d3ea..dbd1486a71 100644 --- a/library/cpp/containers/paged_vector/paged_vector.h +++ b/library/cpp/containers/paged_vector/paged_vector.h @@ -4,429 +4,429 @@ #include <util/generic/vector.h> #include <util/generic/yexception.h> -#include <iterator> - +#include <iterator> + namespace NPagedVector { - template <class T, ui32 PageSize = 1u << 20, class A = std::allocator<T>> - class TPagedVector; - - namespace NPrivate { - template <class T, class TT, ui32 PageSize, class A> - struct TPagedVectorIterator { - private: - friend class TPagedVector<TT, PageSize, A>; - typedef TPagedVector<TT, PageSize, A> TVec; - typedef TPagedVectorIterator<T, TT, PageSize, A> TSelf; - size_t Offset; - TVec* Vector; - - template <class T1, class TT1, ui32 PageSize1, class A1> - friend struct TPagedVectorIterator; - - public: - TPagedVectorIterator() - : Offset() - , Vector() - { - } - - TPagedVectorIterator(TVec* vector, size_t offset) - : Offset(offset) - , Vector(vector) - { - } - - template <class T1, class TT1, ui32 PageSize1, class A1> - TPagedVectorIterator(const TPagedVectorIterator<T1, TT1, PageSize1, A1>& it) - : Offset(it.Offset) - , Vector(it.Vector) - { - } - - T& operator*() const { - return (*Vector)[Offset]; - } - - T* operator->() const { - return &(**this); - } - - template <class T1, class TT1, ui32 PageSize1, class A1> - bool operator==(const TPagedVectorIterator<T1, TT1, PageSize1, A1>& it) const { - return Offset == it.Offset; - } - - template <class T1, class TT1, ui32 PageSize1, class A1> - bool operator!=(const TPagedVectorIterator<T1, TT1, PageSize1, A1>& it) const { - return !(*this == it); - } - - template <class T1, class TT1, ui32 PageSize1, class A1> - bool operator<(const TPagedVectorIterator<T1, TT1, PageSize1, A1>& it) const { - return Offset < it.Offset; - } - - template <class T1, class TT1, ui32 PageSize1, class A1> - bool operator<=(const TPagedVectorIterator<T1, TT1, PageSize1, A1>& it) const { - return Offset <= it.Offset; - } - - template <class T1, class TT1, ui32 PageSize1, class A1> - bool operator>(const TPagedVectorIterator<T1, TT1, PageSize1, A1>& it) const { - return !(*this <= it); - } - - template <class T1, class TT1, ui32 PageSize1, class A1> - bool operator>=(const TPagedVectorIterator<T1, TT1, PageSize1, A1>& it) const { - return !(*this < it); - } - - template <class T1, class TT1, ui32 PageSize1, class A1> - ptrdiff_t operator-(const TPagedVectorIterator<T1, TT1, PageSize1, A1>& it) const { - return Offset - it.Offset; - } - - TSelf& operator+=(ptrdiff_t off) { - Offset += off; - return *this; - } - - TSelf& operator-=(ptrdiff_t off) { - return this->operator+=(-off); - } - - TSelf& operator++() { - return this->operator+=(1); - } - - TSelf& operator--() { - return this->operator+=(-1); - } - - TSelf operator++(int) { - TSelf it = *this; - this->operator+=(1); - return it; - } - - TSelf operator--(int) { - TSelf it = *this; - this->operator+=(-1); - return it; - } - - TSelf operator+(ptrdiff_t off) { - TSelf res = *this; - res += off; - return res; - } - - TSelf operator-(ptrdiff_t off) { - return this->operator+(-off); - } - - size_t GetOffset() { - return Offset; - } - }; + template <class T, ui32 PageSize = 1u << 20, class A = std::allocator<T>> + class TPagedVector; + + namespace NPrivate { + template <class T, class TT, ui32 PageSize, class A> + struct TPagedVectorIterator { + private: + friend class TPagedVector<TT, PageSize, A>; + typedef TPagedVector<TT, PageSize, A> TVec; + typedef TPagedVectorIterator<T, TT, PageSize, A> TSelf; + size_t Offset; + TVec* Vector; + + template <class T1, class TT1, ui32 PageSize1, class A1> + friend struct TPagedVectorIterator; + + public: + TPagedVectorIterator() + : Offset() + , Vector() + { + } + + TPagedVectorIterator(TVec* vector, size_t offset) + : Offset(offset) + , Vector(vector) + { + } + + template <class T1, class TT1, ui32 PageSize1, class A1> + TPagedVectorIterator(const TPagedVectorIterator<T1, TT1, PageSize1, A1>& it) + : Offset(it.Offset) + , Vector(it.Vector) + { + } + + T& operator*() const { + return (*Vector)[Offset]; + } + + T* operator->() const { + return &(**this); + } + + template <class T1, class TT1, ui32 PageSize1, class A1> + bool operator==(const TPagedVectorIterator<T1, TT1, PageSize1, A1>& it) const { + return Offset == it.Offset; + } + + template <class T1, class TT1, ui32 PageSize1, class A1> + bool operator!=(const TPagedVectorIterator<T1, TT1, PageSize1, A1>& it) const { + return !(*this == it); + } + + template <class T1, class TT1, ui32 PageSize1, class A1> + bool operator<(const TPagedVectorIterator<T1, TT1, PageSize1, A1>& it) const { + return Offset < it.Offset; + } + + template <class T1, class TT1, ui32 PageSize1, class A1> + bool operator<=(const TPagedVectorIterator<T1, TT1, PageSize1, A1>& it) const { + return Offset <= it.Offset; + } + + template <class T1, class TT1, ui32 PageSize1, class A1> + bool operator>(const TPagedVectorIterator<T1, TT1, PageSize1, A1>& it) const { + return !(*this <= it); + } + + template <class T1, class TT1, ui32 PageSize1, class A1> + bool operator>=(const TPagedVectorIterator<T1, TT1, PageSize1, A1>& it) const { + return !(*this < it); + } + + template <class T1, class TT1, ui32 PageSize1, class A1> + ptrdiff_t operator-(const TPagedVectorIterator<T1, TT1, PageSize1, A1>& it) const { + return Offset - it.Offset; + } + + TSelf& operator+=(ptrdiff_t off) { + Offset += off; + return *this; + } + + TSelf& operator-=(ptrdiff_t off) { + return this->operator+=(-off); + } + + TSelf& operator++() { + return this->operator+=(1); + } + + TSelf& operator--() { + return this->operator+=(-1); + } + + TSelf operator++(int) { + TSelf it = *this; + this->operator+=(1); + return it; + } + + TSelf operator--(int) { + TSelf it = *this; + this->operator+=(-1); + return it; + } + + TSelf operator+(ptrdiff_t off) { + TSelf res = *this; + res += off; + return res; + } + + TSelf operator-(ptrdiff_t off) { + return this->operator+(-off); + } + + size_t GetOffset() { + return Offset; + } + }; } } -namespace std { - template <class T, class TT, ui32 PageSize, class A> - struct iterator_traits<NPagedVector::NPrivate::TPagedVectorIterator<T, TT, PageSize, A>> { - typedef ptrdiff_t difference_type; - typedef T value_type; - typedef T* pointer; - typedef T& reference; - typedef random_access_iterator_tag iterator_category; - }; +namespace std { + template <class T, class TT, ui32 PageSize, class A> + struct iterator_traits<NPagedVector::NPrivate::TPagedVectorIterator<T, TT, PageSize, A>> { + typedef ptrdiff_t difference_type; + typedef T value_type; + typedef T* pointer; + typedef T& reference; + typedef random_access_iterator_tag iterator_category; + }; } namespace NPagedVector { - //2-level radix tree - template <class T, ui32 PageSize, class A> - class TPagedVector: private TVector<TSimpleSharedPtr<TVector<T, A>>, A> { - static_assert(PageSize, "expect PageSize"); - - typedef TVector<T, A> TPage; - typedef TVector<TSimpleSharedPtr<TPage>, A> TPages; - typedef TPagedVector<T, PageSize, A> TSelf; - - public: - typedef NPrivate::TPagedVectorIterator<T, T, PageSize, A> iterator; - typedef NPrivate::TPagedVectorIterator<const T, T, PageSize, A> const_iterator; - typedef std::reverse_iterator<iterator> reverse_iterator; - typedef std::reverse_iterator<const_iterator> const_reverse_iterator; - typedef T value_type; - typedef value_type& reference; - typedef const value_type& const_reference; - - TPagedVector() = default; - - template <typename TIter> - TPagedVector(TIter b, TIter e) { - append(b, e); - } - - iterator begin() { - return iterator(this, 0); - } - - const_iterator begin() const { - return const_iterator((TSelf*)this, 0); - } - - iterator end() { - return iterator(this, size()); - } - - const_iterator end() const { - return const_iterator((TSelf*)this, size()); - } - - reverse_iterator rbegin() { - return reverse_iterator(end()); - } - - const_reverse_iterator rbegin() const { - return const_reverse_iterator(end()); - } - - reverse_iterator rend() { - return reverse_iterator(begin()); - } - - const_reverse_iterator rend() const { - return const_reverse_iterator(begin()); - } - - void swap(TSelf& v) { - TPages::swap((TPages&)v); - } - - private: - static size_t PageNumber(size_t idx) { - return idx / PageSize; - } - - static size_t InPageIndex(size_t idx) { - return idx % PageSize; - } - - static size_t Index(size_t pnum, size_t poff) { - return pnum * PageSize + poff; - } - - TPage& PageAt(size_t pnum) const { - return *TPages::at(pnum); - } - - TPage& CurrentPage() const { - return *TPages::back(); - } - - size_t CurrentPageSize() const { - return TPages::empty() ? 0 : CurrentPage().size(); - } - - size_t NPages() const { - return TPages::size(); - } - - void AllocateNewPage() { - TPages::push_back(new TPage()); - CurrentPage().reserve(PageSize); - } - - void MakeNewPage() { + //2-level radix tree + template <class T, ui32 PageSize, class A> + class TPagedVector: private TVector<TSimpleSharedPtr<TVector<T, A>>, A> { + static_assert(PageSize, "expect PageSize"); + + typedef TVector<T, A> TPage; + typedef TVector<TSimpleSharedPtr<TPage>, A> TPages; + typedef TPagedVector<T, PageSize, A> TSelf; + + public: + typedef NPrivate::TPagedVectorIterator<T, T, PageSize, A> iterator; + typedef NPrivate::TPagedVectorIterator<const T, T, PageSize, A> const_iterator; + typedef std::reverse_iterator<iterator> reverse_iterator; + typedef std::reverse_iterator<const_iterator> const_reverse_iterator; + typedef T value_type; + typedef value_type& reference; + typedef const value_type& const_reference; + + TPagedVector() = default; + + template <typename TIter> + TPagedVector(TIter b, TIter e) { + append(b, e); + } + + iterator begin() { + return iterator(this, 0); + } + + const_iterator begin() const { + return const_iterator((TSelf*)this, 0); + } + + iterator end() { + return iterator(this, size()); + } + + const_iterator end() const { + return const_iterator((TSelf*)this, size()); + } + + reverse_iterator rbegin() { + return reverse_iterator(end()); + } + + const_reverse_iterator rbegin() const { + return const_reverse_iterator(end()); + } + + reverse_iterator rend() { + return reverse_iterator(begin()); + } + + const_reverse_iterator rend() const { + return const_reverse_iterator(begin()); + } + + void swap(TSelf& v) { + TPages::swap((TPages&)v); + } + + private: + static size_t PageNumber(size_t idx) { + return idx / PageSize; + } + + static size_t InPageIndex(size_t idx) { + return idx % PageSize; + } + + static size_t Index(size_t pnum, size_t poff) { + return pnum * PageSize + poff; + } + + TPage& PageAt(size_t pnum) const { + return *TPages::at(pnum); + } + + TPage& CurrentPage() const { + return *TPages::back(); + } + + size_t CurrentPageSize() const { + return TPages::empty() ? 0 : CurrentPage().size(); + } + + size_t NPages() const { + return TPages::size(); + } + + void AllocateNewPage() { + TPages::push_back(new TPage()); + CurrentPage().reserve(PageSize); + } + + void MakeNewPage() { AllocateNewPage(); - CurrentPage().resize(PageSize); - } - - void PrepareAppend() { - if (TPages::empty() || CurrentPage().size() + 1 > PageSize) - AllocateNewPage(); - } - - public: - size_t size() const { - return empty() ? 0 : (NPages() - 1) * PageSize + CurrentPage().size(); - } - - bool empty() const { - return TPages::empty() || 1 == NPages() && CurrentPage().empty(); - } - - explicit operator bool() const noexcept { - return !empty(); - } - - void emplace_back() { - PrepareAppend(); - CurrentPage().emplace_back(); - } - - void push_back(const_reference t) { - PrepareAppend(); - CurrentPage().push_back(t); - } - - void pop_back() { - if (CurrentPage().empty()) - TPages::pop_back(); - CurrentPage().pop_back(); - } - - template <typename TIter> - void append(TIter b, TIter e) { - size_t sz = e - b; - size_t sz1 = Min<size_t>(sz, PageSize - CurrentPageSize()); - size_t sz2 = (sz - sz1) / PageSize; - size_t sz3 = (sz - sz1) % PageSize; - - if (sz1) { - PrepareAppend(); - TPage& p = CurrentPage(); - p.insert(p.end(), b, b + sz1); - } - - for (size_t i = 0; i < sz2; ++i) { - AllocateNewPage(); - TPage& p = CurrentPage(); - p.insert(p.end(), b + sz1 + i * PageSize, b + sz1 + (i + 1) * PageSize); - } - - if (sz3) { - AllocateNewPage(); - TPage& p = CurrentPage(); - p.insert(p.end(), b + sz1 + sz2 * PageSize, e); - } - } - - iterator erase(iterator it) { - size_t pnum = PageNumber(it.Offset); - size_t pidx = InPageIndex(it.Offset); - - if (CurrentPage().empty()) - TPages::pop_back(); - - for (size_t p = NPages() - 1; p > pnum; --p) { - PageAt(p - 1).push_back(PageAt(p).front()); - PageAt(p).erase(PageAt(p).begin()); - } - - PageAt(pnum).erase(PageAt(pnum).begin() + pidx); - return it; - } - - iterator erase(iterator b, iterator e) { - // todo : suboptimal! - while (b != e) { - b = erase(b); - --e; - } - - return b; - } - - iterator insert(iterator it, const value_type& v) { - size_t pnum = PageNumber(it.Offset); - size_t pidx = InPageIndex(it.Offset); - + CurrentPage().resize(PageSize); + } + + void PrepareAppend() { + if (TPages::empty() || CurrentPage().size() + 1 > PageSize) + AllocateNewPage(); + } + + public: + size_t size() const { + return empty() ? 0 : (NPages() - 1) * PageSize + CurrentPage().size(); + } + + bool empty() const { + return TPages::empty() || 1 == NPages() && CurrentPage().empty(); + } + + explicit operator bool() const noexcept { + return !empty(); + } + + void emplace_back() { + PrepareAppend(); + CurrentPage().emplace_back(); + } + + void push_back(const_reference t) { PrepareAppend(); + CurrentPage().push_back(t); + } + + void pop_back() { + if (CurrentPage().empty()) + TPages::pop_back(); + CurrentPage().pop_back(); + } + + template <typename TIter> + void append(TIter b, TIter e) { + size_t sz = e - b; + size_t sz1 = Min<size_t>(sz, PageSize - CurrentPageSize()); + size_t sz2 = (sz - sz1) / PageSize; + size_t sz3 = (sz - sz1) % PageSize; + + if (sz1) { + PrepareAppend(); + TPage& p = CurrentPage(); + p.insert(p.end(), b, b + sz1); + } + + for (size_t i = 0; i < sz2; ++i) { + AllocateNewPage(); + TPage& p = CurrentPage(); + p.insert(p.end(), b + sz1 + i * PageSize, b + sz1 + (i + 1) * PageSize); + } + + if (sz3) { + AllocateNewPage(); + TPage& p = CurrentPage(); + p.insert(p.end(), b + sz1 + sz2 * PageSize, e); + } + } + + iterator erase(iterator it) { + size_t pnum = PageNumber(it.Offset); + size_t pidx = InPageIndex(it.Offset); + + if (CurrentPage().empty()) + TPages::pop_back(); + + for (size_t p = NPages() - 1; p > pnum; --p) { + PageAt(p - 1).push_back(PageAt(p).front()); + PageAt(p).erase(PageAt(p).begin()); + } + + PageAt(pnum).erase(PageAt(pnum).begin() + pidx); + return it; + } + + iterator erase(iterator b, iterator e) { + // todo : suboptimal! + while (b != e) { + b = erase(b); + --e; + } + + return b; + } + + iterator insert(iterator it, const value_type& v) { + size_t pnum = PageNumber(it.Offset); + size_t pidx = InPageIndex(it.Offset); + + PrepareAppend(); + + for (size_t p = NPages() - 1; p > pnum; --p) { + PageAt(p).insert(PageAt(p).begin(), PageAt(p - 1).back()); + PageAt(p - 1).pop_back(); + } + + PageAt(pnum).insert(PageAt(pnum).begin() + pidx, v); + return it; + } + + template <typename TIter> + void insert(iterator it, TIter b, TIter e) { + // todo : suboptimal! + for (; b != e; ++b, ++it) + it = insert(it, *b); + } + + reference front() { + return TPages::front()->front(); + } + + const_reference front() const { + return TPages::front()->front(); + } + + reference back() { + return CurrentPage().back(); + } + + const_reference back() const { + return CurrentPage().back(); + } + + void clear() { + TPages::clear(); + } + + void resize(size_t sz) { + if (sz == size()) + return; + + const size_t npages = NPages(); + const size_t newwholepages = sz / PageSize; + const size_t pagepart = sz % PageSize; + const size_t newpages = newwholepages + bool(pagepart); + + if (npages && newwholepages >= npages) + CurrentPage().resize(PageSize); + + if (newpages < npages) + TPages::resize(newpages); + else + for (size_t i = npages; i < newpages; ++i) + MakeNewPage(); + + if (pagepart) + CurrentPage().resize(pagepart); + + Y_VERIFY(sz == size(), "%" PRIu64 " %" PRIu64, (ui64)sz, (ui64)size()); + } - for (size_t p = NPages() - 1; p > pnum; --p) { - PageAt(p).insert(PageAt(p).begin(), PageAt(p - 1).back()); - PageAt(p - 1).pop_back(); - } + reference at(size_t idx) { + return TPages::at(PageNumber(idx))->at(InPageIndex(idx)); + } - PageAt(pnum).insert(PageAt(pnum).begin() + pidx, v); - return it; - } + const_reference at(size_t idx) const { + return TPages::at(PageNumber(idx))->at(InPageIndex(idx)); + } - template <typename TIter> - void insert(iterator it, TIter b, TIter e) { - // todo : suboptimal! - for (; b != e; ++b, ++it) - it = insert(it, *b); - } + reference operator[](size_t idx) { + return TPages::operator[](PageNumber(idx))->operator[](InPageIndex(idx)); + } - reference front() { - return TPages::front()->front(); - } + const_reference operator[](size_t idx) const { + return TPages::operator[](PageNumber(idx))->operator[](InPageIndex(idx)); + } - const_reference front() const { - return TPages::front()->front(); - } + friend bool operator==(const TSelf& a, const TSelf& b) { + return a.size() == b.size() && std::equal(a.begin(), a.end(), b.begin()); + } - reference back() { - return CurrentPage().back(); - } - - const_reference back() const { - return CurrentPage().back(); - } - - void clear() { - TPages::clear(); - } - - void resize(size_t sz) { - if (sz == size()) - return; - - const size_t npages = NPages(); - const size_t newwholepages = sz / PageSize; - const size_t pagepart = sz % PageSize; - const size_t newpages = newwholepages + bool(pagepart); - - if (npages && newwholepages >= npages) - CurrentPage().resize(PageSize); - - if (newpages < npages) - TPages::resize(newpages); - else - for (size_t i = npages; i < newpages; ++i) - MakeNewPage(); - - if (pagepart) - CurrentPage().resize(pagepart); - - Y_VERIFY(sz == size(), "%" PRIu64 " %" PRIu64, (ui64)sz, (ui64)size()); - } - - reference at(size_t idx) { - return TPages::at(PageNumber(idx))->at(InPageIndex(idx)); - } - - const_reference at(size_t idx) const { - return TPages::at(PageNumber(idx))->at(InPageIndex(idx)); - } - - reference operator[](size_t idx) { - return TPages::operator[](PageNumber(idx))->operator[](InPageIndex(idx)); - } - - const_reference operator[](size_t idx) const { - return TPages::operator[](PageNumber(idx))->operator[](InPageIndex(idx)); - } - - friend bool operator==(const TSelf& a, const TSelf& b) { - return a.size() == b.size() && std::equal(a.begin(), a.end(), b.begin()); - } - - friend bool operator<(const TSelf& a, const TSelf& b) { - return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end()); - } - }; + friend bool operator<(const TSelf& a, const TSelf& b) { + return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end()); + } + }; - namespace NPrivate { - typedef std::is_same<std::random_access_iterator_tag, std::iterator_traits< - TPagedVector<ui32>::iterator>::iterator_category> - TIteratorCheck; - static_assert(TIteratorCheck::value, "expect TIteratorCheck::Result"); + namespace NPrivate { + typedef std::is_same<std::random_access_iterator_tag, std::iterator_traits< + TPagedVector<ui32>::iterator>::iterator_category> + TIteratorCheck; + static_assert(TIteratorCheck::value, "expect TIteratorCheck::Result"); } } diff --git a/library/cpp/containers/paged_vector/ut/paged_vector_ut.cpp b/library/cpp/containers/paged_vector/ut/paged_vector_ut.cpp index e867808ee4..2904a1d05e 100644 --- a/library/cpp/containers/paged_vector/ut/paged_vector_ut.cpp +++ b/library/cpp/containers/paged_vector/ut/paged_vector_ut.cpp @@ -1,378 +1,378 @@ #include <library/cpp/containers/paged_vector/paged_vector.h> #include <library/cpp/testing/unittest/registar.h> - -#include <stdexcept> + +#include <stdexcept> class TPagedVectorTest: public TTestBase { - UNIT_TEST_SUITE(TPagedVectorTest); - UNIT_TEST(Test0) - UNIT_TEST(Test1) - UNIT_TEST(Test2) - UNIT_TEST(Test3) - UNIT_TEST(Test4) - UNIT_TEST(Test5) - UNIT_TEST(Test6) - UNIT_TEST(Test7) - UNIT_TEST(TestAt) - UNIT_TEST(TestAutoRef) - UNIT_TEST(TestIterators) - //UNIT_TEST(TestEbo) - UNIT_TEST_SUITE_END(); - -private: - // Copy-paste of STLPort tests - void Test0() { - using NPagedVector::TPagedVector; - TPagedVector<int, 16> v1; // Empty vector of integers. - - UNIT_ASSERT(v1.empty() == true); - UNIT_ASSERT(v1.size() == 0); - - for (size_t i = 0; i < 256; ++i) { - v1.resize(i + 1); - UNIT_ASSERT_VALUES_EQUAL(v1.size(), i + 1); - } - - for (size_t i = 256; i-- > 0;) { - v1.resize(i); - UNIT_ASSERT_VALUES_EQUAL(v1.size(), i); + UNIT_TEST_SUITE(TPagedVectorTest); + UNIT_TEST(Test0) + UNIT_TEST(Test1) + UNIT_TEST(Test2) + UNIT_TEST(Test3) + UNIT_TEST(Test4) + UNIT_TEST(Test5) + UNIT_TEST(Test6) + UNIT_TEST(Test7) + UNIT_TEST(TestAt) + UNIT_TEST(TestAutoRef) + UNIT_TEST(TestIterators) + //UNIT_TEST(TestEbo) + UNIT_TEST_SUITE_END(); + +private: + // Copy-paste of STLPort tests + void Test0() { + using NPagedVector::TPagedVector; + TPagedVector<int, 16> v1; // Empty vector of integers. + + UNIT_ASSERT(v1.empty() == true); + UNIT_ASSERT(v1.size() == 0); + + for (size_t i = 0; i < 256; ++i) { + v1.resize(i + 1); + UNIT_ASSERT_VALUES_EQUAL(v1.size(), i + 1); + } + + for (size_t i = 256; i-- > 0;) { + v1.resize(i); + UNIT_ASSERT_VALUES_EQUAL(v1.size(), i); } - } + } - void Test1() { - using NPagedVector::TPagedVector; - TPagedVector<int, 3> v1; // Empty vector of integers. + void Test1() { + using NPagedVector::TPagedVector; + TPagedVector<int, 3> v1; // Empty vector of integers. - UNIT_ASSERT(v1.empty() == true); - UNIT_ASSERT(v1.size() == 0); + UNIT_ASSERT(v1.empty() == true); + UNIT_ASSERT(v1.size() == 0); - // UNIT_ASSERT(v1.max_size() == INT_MAX / sizeof(int)); - // cout << "max_size = " << v1.max_size() << endl; - v1.push_back(42); // Add an integer to the vector. + // UNIT_ASSERT(v1.max_size() == INT_MAX / sizeof(int)); + // cout << "max_size = " << v1.max_size() << endl; + v1.push_back(42); // Add an integer to the vector. - UNIT_ASSERT(v1.size() == 1); + UNIT_ASSERT(v1.size() == 1); - UNIT_ASSERT(v1[0] == 42); + UNIT_ASSERT(v1[0] == 42); - { - TPagedVector<TPagedVector<int, 3>, 3> vect; - vect.resize(10); - UNIT_ASSERT(vect.size() == 10); - TPagedVector<TPagedVector<int, 3>, 3>::iterator it(vect.begin()), end(vect.end()); - for (; it != end; ++it) { - UNIT_ASSERT((*it).empty()); - UNIT_ASSERT((*it).size() == 0); - UNIT_ASSERT((*it).begin() == (*it).end()); + { + TPagedVector<TPagedVector<int, 3>, 3> vect; + vect.resize(10); + UNIT_ASSERT(vect.size() == 10); + TPagedVector<TPagedVector<int, 3>, 3>::iterator it(vect.begin()), end(vect.end()); + for (; it != end; ++it) { + UNIT_ASSERT((*it).empty()); + UNIT_ASSERT((*it).size() == 0); + UNIT_ASSERT((*it).begin() == (*it).end()); } } - } + } - void Test2() { - using NPagedVector::TPagedVector; - TPagedVector<double, 3> v1; // Empty vector of doubles. - v1.push_back(32.1); - v1.push_back(40.5); - v1.push_back(45.5); - v1.push_back(33.4); - TPagedVector<double, 3> v2; // Another empty vector of doubles. - v2.push_back(3.56); + void Test2() { + using NPagedVector::TPagedVector; + TPagedVector<double, 3> v1; // Empty vector of doubles. + v1.push_back(32.1); + v1.push_back(40.5); + v1.push_back(45.5); + v1.push_back(33.4); + TPagedVector<double, 3> v2; // Another empty vector of doubles. + v2.push_back(3.56); - UNIT_ASSERT(v1.size() == 4); - UNIT_ASSERT(v1[0] == 32.1); - UNIT_ASSERT(v1[1] == 40.5); - UNIT_ASSERT(v1[2] == 45.5); - UNIT_ASSERT(v1[3] == 33.4); + UNIT_ASSERT(v1.size() == 4); + UNIT_ASSERT(v1[0] == 32.1); + UNIT_ASSERT(v1[1] == 40.5); + UNIT_ASSERT(v1[2] == 45.5); + UNIT_ASSERT(v1[3] == 33.4); - UNIT_ASSERT(v2.size() == 1); - UNIT_ASSERT(v2[0] == 3.56); - v1.swap(v2); // Swap the vector's contents. + UNIT_ASSERT(v2.size() == 1); + UNIT_ASSERT(v2[0] == 3.56); + v1.swap(v2); // Swap the vector's contents. - UNIT_ASSERT(v1.size() == 1); - UNIT_ASSERT(v1[0] == 3.56); + UNIT_ASSERT(v1.size() == 1); + UNIT_ASSERT(v1[0] == 3.56); - UNIT_ASSERT(v2.size() == 4); - UNIT_ASSERT(v2[0] == 32.1); - UNIT_ASSERT(v2[1] == 40.5); - UNIT_ASSERT(v2[2] == 45.5); - UNIT_ASSERT(v2[3] == 33.4); + UNIT_ASSERT(v2.size() == 4); + UNIT_ASSERT(v2[0] == 32.1); + UNIT_ASSERT(v2[1] == 40.5); + UNIT_ASSERT(v2[2] == 45.5); + UNIT_ASSERT(v2[3] == 33.4); - v2 = v1; // Assign one vector to another. + v2 = v1; // Assign one vector to another. - UNIT_ASSERT(v2.size() == 1); - UNIT_ASSERT(v2[0] == 3.56); + UNIT_ASSERT(v2.size() == 1); + UNIT_ASSERT(v2[0] == 3.56); - v2.pop_back(); - UNIT_ASSERT(v2.size() == 0); - UNIT_ASSERT(v2.empty()); - } + v2.pop_back(); + UNIT_ASSERT(v2.size() == 0); + UNIT_ASSERT(v2.empty()); + } - void Test3() { - using NPagedVector::TPagedVector; - TPagedVector<char, 1> v1; + void Test3() { + using NPagedVector::TPagedVector; + TPagedVector<char, 1> v1; - v1.push_back('h'); - v1.push_back('i'); + v1.push_back('h'); + v1.push_back('i'); - UNIT_ASSERT(v1.size() == 2); - UNIT_ASSERT(v1[0] == 'h'); - UNIT_ASSERT(v1[1] == 'i'); + UNIT_ASSERT(v1.size() == 2); + UNIT_ASSERT(v1[0] == 'h'); + UNIT_ASSERT(v1[1] == 'i'); - TPagedVector<char, 1> v2; - v2.resize(v1.size()); + TPagedVector<char, 1> v2; + v2.resize(v1.size()); - for (size_t i = 0; i < v1.size(); ++i) - v2[i] = v1[i]; + for (size_t i = 0; i < v1.size(); ++i) + v2[i] = v1[i]; - v2[1] = 'o'; // Replace second character. + v2[1] = 'o'; // Replace second character. - UNIT_ASSERT(v2.size() == 2); - UNIT_ASSERT(v2[0] == 'h'); - UNIT_ASSERT(v2[1] == 'o'); + UNIT_ASSERT(v2.size() == 2); + UNIT_ASSERT(v2[0] == 'h'); + UNIT_ASSERT(v2[1] == 'o'); - UNIT_ASSERT((v1 == v2) == false); + UNIT_ASSERT((v1 == v2) == false); - UNIT_ASSERT((v1 < v2) == true); - } + UNIT_ASSERT((v1 < v2) == true); + } - void Test4() { - using NPagedVector::TPagedVector; - TPagedVector<int, 3> v; - v.resize(4); + void Test4() { + using NPagedVector::TPagedVector; + TPagedVector<int, 3> v; + v.resize(4); - v[0] = 1; - v[1] = 4; - v[2] = 9; - v[3] = 16; + v[0] = 1; + v[1] = 4; + v[2] = 9; + v[3] = 16; - UNIT_ASSERT(v.front() == 1); - UNIT_ASSERT(v.back() == 16); + UNIT_ASSERT(v.front() == 1); + UNIT_ASSERT(v.back() == 16); - v.push_back(25); + v.push_back(25); - UNIT_ASSERT(v.back() == 25); - UNIT_ASSERT(v.size() == 5); + UNIT_ASSERT(v.back() == 25); + UNIT_ASSERT(v.size() == 5); - v.pop_back(); + v.pop_back(); - UNIT_ASSERT(v.back() == 16); - UNIT_ASSERT(v.size() == 4); - } + UNIT_ASSERT(v.back() == 16); + UNIT_ASSERT(v.size() == 4); + } - void Test5() { - int array[] = {1, 4, 9, 16}; + void Test5() { + int array[] = {1, 4, 9, 16}; - typedef NPagedVector::TPagedVector<int, 3> TVectorType; - TVectorType v(array, array + 4); + typedef NPagedVector::TPagedVector<int, 3> TVectorType; + TVectorType v(array, array + 4); - UNIT_ASSERT(v.size() == 4); - - UNIT_ASSERT(v[0] == 1); - UNIT_ASSERT(v[1] == 4); - UNIT_ASSERT(v[2] == 9); - UNIT_ASSERT(v[3] == 16); - } - - void Test6() { - int array[] = {1, 4, 9, 16, 25, 36}; + UNIT_ASSERT(v.size() == 4); + + UNIT_ASSERT(v[0] == 1); + UNIT_ASSERT(v[1] == 4); + UNIT_ASSERT(v[2] == 9); + UNIT_ASSERT(v[3] == 16); + } + + void Test6() { + int array[] = {1, 4, 9, 16, 25, 36}; - typedef NPagedVector::TPagedVector<int, 3> TVectorType; - TVectorType v(array, array + 6); - TVectorType::iterator vit; + typedef NPagedVector::TPagedVector<int, 3> TVectorType; + TVectorType v(array, array + 6); + TVectorType::iterator vit; - UNIT_ASSERT_VALUES_EQUAL(v.size(), 6u); - UNIT_ASSERT(v[0] == 1); - UNIT_ASSERT(v[1] == 4); - UNIT_ASSERT(v[2] == 9); - UNIT_ASSERT(v[3] == 16); - UNIT_ASSERT(v[4] == 25); - UNIT_ASSERT(v[5] == 36); + UNIT_ASSERT_VALUES_EQUAL(v.size(), 6u); + UNIT_ASSERT(v[0] == 1); + UNIT_ASSERT(v[1] == 4); + UNIT_ASSERT(v[2] == 9); + UNIT_ASSERT(v[3] == 16); + UNIT_ASSERT(v[4] == 25); + UNIT_ASSERT(v[5] == 36); - vit = v.erase(v.begin()); // Erase first element. - UNIT_ASSERT(*vit == 4); + vit = v.erase(v.begin()); // Erase first element. + UNIT_ASSERT(*vit == 4); - UNIT_ASSERT(v.size() == 5); - UNIT_ASSERT(v[0] == 4); - UNIT_ASSERT(v[1] == 9); - UNIT_ASSERT(v[2] == 16); - UNIT_ASSERT(v[3] == 25); - UNIT_ASSERT(v[4] == 36); + UNIT_ASSERT(v.size() == 5); + UNIT_ASSERT(v[0] == 4); + UNIT_ASSERT(v[1] == 9); + UNIT_ASSERT(v[2] == 16); + UNIT_ASSERT(v[3] == 25); + UNIT_ASSERT(v[4] == 36); - vit = v.erase(v.end() - 1); // Erase last element. - UNIT_ASSERT(vit == v.end()); + vit = v.erase(v.end() - 1); // Erase last element. + UNIT_ASSERT(vit == v.end()); - UNIT_ASSERT(v.size() == 4); - UNIT_ASSERT(v[0] == 4); - UNIT_ASSERT(v[1] == 9); - UNIT_ASSERT(v[2] == 16); - UNIT_ASSERT(v[3] == 25); + UNIT_ASSERT(v.size() == 4); + UNIT_ASSERT(v[0] == 4); + UNIT_ASSERT(v[1] == 9); + UNIT_ASSERT(v[2] == 16); + UNIT_ASSERT(v[3] == 25); - v.erase(v.begin() + 1, v.end() - 1); // Erase all but first and last. + v.erase(v.begin() + 1, v.end() - 1); // Erase all but first and last. - UNIT_ASSERT(v.size() == 2); - UNIT_ASSERT(v[0] == 4); - UNIT_ASSERT(v[1] == 25); - } + UNIT_ASSERT(v.size() == 2); + UNIT_ASSERT(v[0] == 4); + UNIT_ASSERT(v[1] == 25); + } - void Test7() { - int array1[] = {1, 4, 25}; - int array2[] = {9, 16}; + void Test7() { + int array1[] = {1, 4, 25}; + int array2[] = {9, 16}; - typedef NPagedVector::TPagedVector<int, 3> TVectorType; + typedef NPagedVector::TPagedVector<int, 3> TVectorType; - TVectorType v(array1, array1 + 3); - TVectorType::iterator vit; - vit = v.insert(v.begin(), 0); // Insert before first element. - UNIT_ASSERT_VALUES_EQUAL(*vit, 0); - - vit = v.insert(v.end(), 36); // Insert after last element. - UNIT_ASSERT(*vit == 36); - - UNIT_ASSERT(v.size() == 5); - UNIT_ASSERT(v[0] == 0); - UNIT_ASSERT(v[1] == 1); - UNIT_ASSERT(v[2] == 4); - UNIT_ASSERT(v[3] == 25); - UNIT_ASSERT(v[4] == 36); - - // Insert contents of array2 before fourth element. - v.insert(v.begin() + 3, array2, array2 + 2); - - UNIT_ASSERT(v.size() == 7); - - UNIT_ASSERT(v[0] == 0); - UNIT_ASSERT(v[1] == 1); - UNIT_ASSERT(v[2] == 4); - UNIT_ASSERT(v[3] == 9); - UNIT_ASSERT(v[4] == 16); - UNIT_ASSERT(v[5] == 25); - UNIT_ASSERT(v[6] == 36); - - v.clear(); - UNIT_ASSERT(v.empty()); - } - - void TestAt() { - using NPagedVector::TPagedVector; - TPagedVector<int, 3> v; - TPagedVector<int, 3> const& cv = v; - - v.push_back(10); - UNIT_ASSERT(v.at(0) == 10); - v.at(0) = 20; - UNIT_ASSERT(cv.at(0) == 20); - - for (;;) { - try { - v.at(1) = 20; - UNIT_ASSERT(false); - } catch (std::out_of_range const&) { - return; - } catch (...) { - UNIT_ASSERT(false); + TVectorType v(array1, array1 + 3); + TVectorType::iterator vit; + vit = v.insert(v.begin(), 0); // Insert before first element. + UNIT_ASSERT_VALUES_EQUAL(*vit, 0); + + vit = v.insert(v.end(), 36); // Insert after last element. + UNIT_ASSERT(*vit == 36); + + UNIT_ASSERT(v.size() == 5); + UNIT_ASSERT(v[0] == 0); + UNIT_ASSERT(v[1] == 1); + UNIT_ASSERT(v[2] == 4); + UNIT_ASSERT(v[3] == 25); + UNIT_ASSERT(v[4] == 36); + + // Insert contents of array2 before fourth element. + v.insert(v.begin() + 3, array2, array2 + 2); + + UNIT_ASSERT(v.size() == 7); + + UNIT_ASSERT(v[0] == 0); + UNIT_ASSERT(v[1] == 1); + UNIT_ASSERT(v[2] == 4); + UNIT_ASSERT(v[3] == 9); + UNIT_ASSERT(v[4] == 16); + UNIT_ASSERT(v[5] == 25); + UNIT_ASSERT(v[6] == 36); + + v.clear(); + UNIT_ASSERT(v.empty()); + } + + void TestAt() { + using NPagedVector::TPagedVector; + TPagedVector<int, 3> v; + TPagedVector<int, 3> const& cv = v; + + v.push_back(10); + UNIT_ASSERT(v.at(0) == 10); + v.at(0) = 20; + UNIT_ASSERT(cv.at(0) == 20); + + for (;;) { + try { + v.at(1) = 20; + UNIT_ASSERT(false); + } catch (std::out_of_range const&) { + return; + } catch (...) { + UNIT_ASSERT(false); } } - } - - void TestAutoRef() { - using NPagedVector::TPagedVector; - typedef TPagedVector<int, 3> TVec; - TVec ref; - for (int i = 0; i < 5; ++i) { - ref.push_back(i); - } - - TPagedVector<TVec, 3> v_v_int; - v_v_int.push_back(ref); - v_v_int.push_back(v_v_int[0]); - v_v_int.push_back(ref); - v_v_int.push_back(v_v_int[0]); - v_v_int.push_back(v_v_int[0]); - v_v_int.push_back(ref); - - TPagedVector<TVec, 3>::iterator vvit(v_v_int.begin()), vvitEnd(v_v_int.end()); - for (; vvit != vvitEnd; ++vvit) { - UNIT_ASSERT(*vvit == ref); - } - } - - struct Point { - int x, y; - }; - - struct PointEx: public Point { - PointEx() - : builtFromBase(false) - { + } + + void TestAutoRef() { + using NPagedVector::TPagedVector; + typedef TPagedVector<int, 3> TVec; + TVec ref; + for (int i = 0; i < 5; ++i) { + ref.push_back(i); + } + + TPagedVector<TVec, 3> v_v_int; + v_v_int.push_back(ref); + v_v_int.push_back(v_v_int[0]); + v_v_int.push_back(ref); + v_v_int.push_back(v_v_int[0]); + v_v_int.push_back(v_v_int[0]); + v_v_int.push_back(ref); + + TPagedVector<TVec, 3>::iterator vvit(v_v_int.begin()), vvitEnd(v_v_int.end()); + for (; vvit != vvitEnd; ++vvit) { + UNIT_ASSERT(*vvit == ref); } - PointEx(const Point&) - : builtFromBase(true) - { - } - - bool builtFromBase; - }; - - void TestIterators() { - using NPagedVector::TPagedVector; - TPagedVector<int, 3> vint; - vint.resize(10); - TPagedVector<int, 3> const& crvint = vint; - - UNIT_ASSERT(vint.begin() == vint.begin()); - UNIT_ASSERT(crvint.begin() == vint.begin()); - UNIT_ASSERT(vint.begin() == crvint.begin()); - UNIT_ASSERT(crvint.begin() == crvint.begin()); - - UNIT_ASSERT(vint.begin() != vint.end()); - UNIT_ASSERT(crvint.begin() != vint.end()); - UNIT_ASSERT(vint.begin() != crvint.end()); - UNIT_ASSERT(crvint.begin() != crvint.end()); - - UNIT_ASSERT(vint.rbegin() == vint.rbegin()); - // Not Standard: - //UNIT_ASSERT(vint.rbegin() == crvint.rbegin()); - //UNIT_ASSERT(crvint.rbegin() == vint.rbegin()); - UNIT_ASSERT(crvint.rbegin() == crvint.rbegin()); - - UNIT_ASSERT(vint.rbegin() != vint.rend()); - // Not Standard: - //UNIT_ASSERT(vint.rbegin() != crvint.rend()); - //UNIT_ASSERT(crvint.rbegin() != vint.rend()); - UNIT_ASSERT(crvint.rbegin() != crvint.rend()); - } - - /* This test check a potential issue with empty base class + } + + struct Point { + int x, y; + }; + + struct PointEx: public Point { + PointEx() + : builtFromBase(false) + { + } + PointEx(const Point&) + : builtFromBase(true) + { + } + + bool builtFromBase; + }; + + void TestIterators() { + using NPagedVector::TPagedVector; + TPagedVector<int, 3> vint; + vint.resize(10); + TPagedVector<int, 3> const& crvint = vint; + + UNIT_ASSERT(vint.begin() == vint.begin()); + UNIT_ASSERT(crvint.begin() == vint.begin()); + UNIT_ASSERT(vint.begin() == crvint.begin()); + UNIT_ASSERT(crvint.begin() == crvint.begin()); + + UNIT_ASSERT(vint.begin() != vint.end()); + UNIT_ASSERT(crvint.begin() != vint.end()); + UNIT_ASSERT(vint.begin() != crvint.end()); + UNIT_ASSERT(crvint.begin() != crvint.end()); + + UNIT_ASSERT(vint.rbegin() == vint.rbegin()); + // Not Standard: + //UNIT_ASSERT(vint.rbegin() == crvint.rbegin()); + //UNIT_ASSERT(crvint.rbegin() == vint.rbegin()); + UNIT_ASSERT(crvint.rbegin() == crvint.rbegin()); + + UNIT_ASSERT(vint.rbegin() != vint.rend()); + // Not Standard: + //UNIT_ASSERT(vint.rbegin() != crvint.rend()); + //UNIT_ASSERT(crvint.rbegin() != vint.rend()); + UNIT_ASSERT(crvint.rbegin() != crvint.rend()); + } + + /* This test check a potential issue with empty base class * optimization. Some compilers (VC6) do not implement it * correctly resulting ina wrong behavior. */ - void TestEbo() { - using NPagedVector::TPagedVector; - // We use heap memory as test failure can corrupt vector internal - // representation making executable crash on vector destructor invocation. - // We prefer a simple memory leak, internal corruption should be reveal - // by size or capacity checks. - typedef TPagedVector<int, 3> V; - V* pv1 = new V; + void TestEbo() { + using NPagedVector::TPagedVector; + // We use heap memory as test failure can corrupt vector internal + // representation making executable crash on vector destructor invocation. + // We prefer a simple memory leak, internal corruption should be reveal + // by size or capacity checks. + typedef TPagedVector<int, 3> V; + V* pv1 = new V; - pv1->resize(1); - pv1->at(0) = 1; + pv1->resize(1); + pv1->at(0) = 1; - V* pv2 = new V; + V* pv2 = new V; - pv2->resize(10); - for (int i = 0; i < 10; ++i) - pv2->at(i) = 2; + pv2->resize(10); + for (int i = 0; i < 10; ++i) + pv2->at(i) = 2; - pv1->swap(*pv2); + pv1->swap(*pv2); - UNIT_ASSERT(pv1->size() == 10); - UNIT_ASSERT((*pv1)[5] == 2); + UNIT_ASSERT(pv1->size() == 10); + UNIT_ASSERT((*pv1)[5] == 2); - UNIT_ASSERT(pv2->size() == 1); - UNIT_ASSERT((*pv2)[0] == 1); + UNIT_ASSERT(pv2->size() == 1); + UNIT_ASSERT((*pv2)[0] == 1); - delete pv2; - delete pv1; - } + delete pv2; + delete pv1; + } }; UNIT_TEST_SUITE_REGISTRATION(TPagedVectorTest); diff --git a/library/cpp/containers/paged_vector/ut/ya.make b/library/cpp/containers/paged_vector/ut/ya.make index 74cfe5fb4a..69054531b1 100644 --- a/library/cpp/containers/paged_vector/ut/ya.make +++ b/library/cpp/containers/paged_vector/ut/ya.make @@ -1,13 +1,13 @@ -UNITTEST() - -OWNER(velavokr) - -PEERDIR( +UNITTEST() + +OWNER(velavokr) + +PEERDIR( library/cpp/containers/paged_vector -) - -SRCS( - paged_vector_ut.cpp -) - -END() +) + +SRCS( + paged_vector_ut.cpp +) + +END() |