From b41e76bb0bc6aac90e1755477936b216857b05d6 Mon Sep 17 00:00:00 2001 From: Marshall Clow Date: Fri, 5 Jun 2015 22:34:19 +0000 Subject: [PATCH] Fix PR#23767. Add tests for iterator invalidation for deque::erase/pop_front/pop_back llvm-svn: 239196 --- libcxx/include/deque | 4 +- .../erase_iter.invalidation.pass.cpp | 70 +++++++++++++++++++ .../erase_iter_iter.invalidation.pass.cpp | 78 ++++++++++++++++++++++ .../deque.modifiers/pop_back.invalidation.pass.cpp | 49 ++++++++++++++ .../pop_front.invalidation.pass.cpp | 49 ++++++++++++++ 5 files changed, 248 insertions(+), 2 deletions(-) create mode 100644 libcxx/test/std/containers/sequences/deque/deque.modifiers/erase_iter.invalidation.pass.cpp create mode 100644 libcxx/test/std/containers/sequences/deque/deque.modifiers/erase_iter_iter.invalidation.pass.cpp create mode 100644 libcxx/test/std/containers/sequences/deque/deque.modifiers/pop_back.invalidation.pass.cpp create mode 100644 libcxx/test/std/containers/sequences/deque/deque.modifiers/pop_front.invalidation.pass.cpp diff --git a/libcxx/include/deque b/libcxx/include/deque index 78ef118..a372560 100644 --- a/libcxx/include/deque +++ b/libcxx/include/deque @@ -2699,7 +2699,7 @@ deque<_Tp, _Allocator>::erase(const_iterator __f) difference_type __pos = __f - __b; iterator __p = __b + __pos; allocator_type& __a = __base::__alloc(); - if (__pos < (__base::size() - 1) / 2) + if (__pos <= (__base::size() - 1) / 2) { // erase from front _VSTD::move_backward(__b, __p, _VSTD::next(__p)); __alloc_traits::destroy(__a, _VSTD::addressof(*__b)); @@ -2737,7 +2737,7 @@ deque<_Tp, _Allocator>::erase(const_iterator __f, const_iterator __l) if (__n > 0) { allocator_type& __a = __base::__alloc(); - if (__pos < (__base::size() - __n) / 2) + if (__pos <= (__base::size() - __n) / 2) { // erase from front iterator __i = _VSTD::move_backward(__b, __p, __p + __n); for (; __b != __i; ++__b) diff --git a/libcxx/test/std/containers/sequences/deque/deque.modifiers/erase_iter.invalidation.pass.cpp b/libcxx/test/std/containers/sequences/deque/deque.modifiers/erase_iter.invalidation.pass.cpp new file mode 100644 index 0000000..49465cd --- /dev/null +++ b/libcxx/test/std/containers/sequences/deque/deque.modifiers/erase_iter.invalidation.pass.cpp @@ -0,0 +1,70 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +// + +// iterator erase(const_iterator f) + +// Erasing items from the beginning or the end of a deque shall not invalidate iterators +// to items that were not erased. + +#include +#include + +template +void del_at_start(C c) +{ + typename C::iterator first = c.begin(); + typename C::iterator it1 = first + 1; + typename C::iterator it2 = c.end() - 1; + + c.erase (first); + + typename C::iterator it3 = c.begin(); + typename C::iterator it4 = c.end() - 1; + assert( it1 == it3); + assert( *it1 == *it3); + assert(&*it1 == &*it3); + assert( it2 == it4); + assert( *it2 == *it4); + assert(&*it2 == &*it4); +} + +template +void del_at_end(C c) +{ + typename C::iterator first = c.end() - 1; + typename C::iterator it1 = c.begin(); + typename C::iterator it2 = first - 1; + + c.erase (first); + + typename C::iterator it3 = c.begin(); + typename C::iterator it4 = c.end() - 1; + assert( it1 == it3); + assert( *it1 == *it3); + assert(&*it1 == &*it3); + assert( it2 == it4); + assert( *it2 == *it4); + assert(&*it2 == &*it4); +} + +int main() +{ + std::deque queue; + for (int i = 0; i < 20; ++i) + queue.push_back(i); + + while (queue.size() > 1) + { + del_at_start(queue); + del_at_end(queue); + queue.pop_back(); + } +} diff --git a/libcxx/test/std/containers/sequences/deque/deque.modifiers/erase_iter_iter.invalidation.pass.cpp b/libcxx/test/std/containers/sequences/deque/deque.modifiers/erase_iter_iter.invalidation.pass.cpp new file mode 100644 index 0000000..c785e26 --- /dev/null +++ b/libcxx/test/std/containers/sequences/deque/deque.modifiers/erase_iter_iter.invalidation.pass.cpp @@ -0,0 +1,78 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +// + +// iterator erase(const_iterator f, const_iterator l) + +// Erasing items from the beginning or the end of a deque shall not invalidate iterators +// to items that were not erased. + + +#include +#include +#include + +template +void del_at_start(C c, size_t num) +{ + typename C::iterator first = c.begin(); + typename C::iterator last = first + num; + typename C::iterator it1 = last; + typename C::iterator it2 = c.end() - 1; + + c.erase (first, last); + + typename C::iterator it3 = c.begin(); + typename C::iterator it4 = c.end() - 1; + assert( it1 == it3); + assert( *it1 == *it3); + assert(&*it1 == &*it3); + assert( it2 == it4); + assert( *it2 == *it4); + assert(&*it2 == &*it4); +} + +template +void del_at_end(C c, size_t num) +{ + typename C::iterator last = c.end(); + typename C::iterator first = last - num; + typename C::iterator it1 = c.begin(); + typename C::iterator it2 = first - 1; + + c.erase (first, last); + + typename C::iterator it3 = c.begin(); + typename C::iterator it4 = c.end() - 1; + assert( it1 == it3); + assert( *it1 == *it3); + assert(&*it1 == &*it3); + assert( it2 == it4); + assert( *it2 == *it4); + assert(&*it2 == &*it4); +} + + +int main() +{ + std::deque queue; + for (int i = 0; i < 20; ++i) + queue.push_back(i); + + while (queue.size() > 1) + { + for (size_t i = 1; i < queue.size(); ++i) + { + del_at_start(queue, i); + del_at_end (queue, i); + } + queue.pop_back(); + } +} diff --git a/libcxx/test/std/containers/sequences/deque/deque.modifiers/pop_back.invalidation.pass.cpp b/libcxx/test/std/containers/sequences/deque/deque.modifiers/pop_back.invalidation.pass.cpp new file mode 100644 index 0000000..1d84f73 --- /dev/null +++ b/libcxx/test/std/containers/sequences/deque/deque.modifiers/pop_back.invalidation.pass.cpp @@ -0,0 +1,49 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +// + +// void pop_back() + +// Erasing items from the beginning or the end of a deque shall not invalidate iterators +// to items that were not erased. + +#include +#include + +template +void test(C c) +{ + typename C::iterator it1 = c.begin(); + typename C::iterator it2 = c.end() - 2; + + c.pop_back(); + + typename C::iterator it3 = c.begin(); + typename C::iterator it4 = c.end() - 1; + assert( it1 == it3); + assert( *it1 == *it3); + assert(&*it1 == &*it3); + assert( it2 == it4); + assert( *it2 == *it4); + assert(&*it2 == &*it4); +} + +int main() +{ + std::deque queue; + for (int i = 0; i < 20; ++i) + queue.push_back(i); + + while (queue.size() > 1) + { + test(queue); + queue.pop_back(); + } +} diff --git a/libcxx/test/std/containers/sequences/deque/deque.modifiers/pop_front.invalidation.pass.cpp b/libcxx/test/std/containers/sequences/deque/deque.modifiers/pop_front.invalidation.pass.cpp new file mode 100644 index 0000000..78317f3 --- /dev/null +++ b/libcxx/test/std/containers/sequences/deque/deque.modifiers/pop_front.invalidation.pass.cpp @@ -0,0 +1,49 @@ +//===----------------------------------------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +// + +// void pop_front() + +// Erasing items from the beginning or the end of a deque shall not invalidate iterators +// to items that were not erased. + +#include +#include + +template +void test(C c) +{ + typename C::iterator it1 = c.begin() + 1; + typename C::iterator it2 = c.end() - 1; + + c.pop_front(); + + typename C::iterator it3 = c.begin(); + typename C::iterator it4 = c.end() - 1; + assert( it1 == it3); + assert( *it1 == *it3); + assert(&*it1 == &*it3); + assert( it2 == it4); + assert( *it2 == *it4); + assert(&*it2 == &*it4); +} + +int main() +{ + std::deque queue; + for (int i = 0; i < 20; ++i) + queue.push_back(i); + + while (queue.size() > 1) + { + test(queue); + queue.pop_back(); + } +} -- 2.7.4