diff options
Diffstat (limited to 'test/libcxx/containers')
66 files changed, 5747 insertions, 48 deletions
diff --git a/test/libcxx/containers/associative/map/version.pass.cpp b/test/libcxx/containers/associative/map/version.pass.cpp new file mode 100644 index 0000000000000..b2e3fa43e7879 --- /dev/null +++ b/test/libcxx/containers/associative/map/version.pass.cpp @@ -0,0 +1,20 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <map> + +#include <map> + +#ifndef _LIBCPP_VERSION +#error _LIBCPP_VERSION not defined +#endif + +int main() +{ +} diff --git a/test/libcxx/containers/associative/set/version.pass.cpp b/test/libcxx/containers/associative/set/version.pass.cpp new file mode 100644 index 0000000000000..c3c4d926e5c33 --- /dev/null +++ b/test/libcxx/containers/associative/set/version.pass.cpp @@ -0,0 +1,20 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <set> + +#include <set> + +#ifndef _LIBCPP_VERSION +#error _LIBCPP_VERSION not defined +#endif + +int main() +{ +} diff --git a/test/libcxx/containers/associative/tree_balance_after_insert.pass.cpp b/test/libcxx/containers/associative/tree_balance_after_insert.pass.cpp new file mode 100644 index 0000000000000..300c1e9a49157 --- /dev/null +++ b/test/libcxx/containers/associative/tree_balance_after_insert.pass.cpp @@ -0,0 +1,1619 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// Not a portable test + +// Precondition: __root->__is_black_ == true +// template <class _NodePtr> +// void +// __tree_balance_after_insert(_NodePtr __root, _NodePtr __x) + +#include <__tree> +#include <cassert> + +struct Node +{ + Node* __left_; + Node* __right_; + Node* __parent_; + bool __is_black_; + + Node* __parent_unsafe() const { return __parent_; } + void __set_parent(Node* x) { __parent_ = x;} + + Node() : __left_(), __right_(), __parent_(), __is_black_() {} +}; + +void +test1() +{ + { + Node root; + Node a; + Node b; + Node c; + Node d; + + root.__left_ = &c; + + c.__parent_ = &root; + c.__left_ = &b; + c.__right_ = &d; + c.__is_black_ = true; + + b.__parent_ = &c; + b.__left_ = &a; + b.__right_ = 0; + b.__is_black_ = false; + + d.__parent_ = &c; + d.__left_ = 0; + d.__right_ = 0; + d.__is_black_ = false; + + a.__parent_ = &b; + a.__left_ = 0; + a.__right_ = 0; + a.__is_black_ = false; + + std::__tree_balance_after_insert(root.__left_, &a); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__left_ == &c); + + assert(c.__parent_ == &root); + assert(c.__left_ == &b); + assert(c.__right_ == &d); + assert(c.__is_black_ == true); + + assert(b.__parent_ == &c); + assert(b.__left_ == &a); + assert(b.__right_ == 0); + assert(b.__is_black_ == true); + + assert(d.__parent_ == &c); + assert(d.__left_ == 0); + assert(d.__right_ == 0); + assert(d.__is_black_ == true); + + assert(a.__parent_ == &b); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == false); + } + { + Node root; + Node a; + Node b; + Node c; + Node d; + + root.__left_ = &c; + + c.__parent_ = &root; + c.__left_ = &b; + c.__right_ = &d; + c.__is_black_ = true; + + b.__parent_ = &c; + b.__left_ = 0; + b.__right_ = &a; + b.__is_black_ = false; + + d.__parent_ = &c; + d.__left_ = 0; + d.__right_ = 0; + d.__is_black_ = false; + + a.__parent_ = &b; + a.__left_ = 0; + a.__right_ = 0; + a.__is_black_ = false; + + std::__tree_balance_after_insert(root.__left_, &a); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__left_ == &c); + + assert(c.__parent_ == &root); + assert(c.__left_ == &b); + assert(c.__right_ == &d); + assert(c.__is_black_ == true); + + assert(b.__parent_ == &c); + assert(b.__left_ == 0); + assert(b.__right_ == &a); + assert(b.__is_black_ == true); + + assert(d.__parent_ == &c); + assert(d.__left_ == 0); + assert(d.__right_ == 0); + assert(d.__is_black_ == true); + + assert(a.__parent_ == &b); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == false); + } + { + Node root; + Node a; + Node b; + Node c; + Node d; + + root.__left_ = &c; + + c.__parent_ = &root; + c.__left_ = &b; + c.__right_ = &d; + c.__is_black_ = true; + + b.__parent_ = &c; + b.__left_ = 0; + b.__right_ = 0; + b.__is_black_ = false; + + d.__parent_ = &c; + d.__left_ = &a; + d.__right_ = 0; + d.__is_black_ = false; + + a.__parent_ = &d; + a.__left_ = 0; + a.__right_ = 0; + a.__is_black_ = false; + + std::__tree_balance_after_insert(root.__left_, &a); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__left_ == &c); + + assert(c.__parent_ == &root); + assert(c.__left_ == &b); + assert(c.__right_ == &d); + assert(c.__is_black_ == true); + + assert(b.__parent_ == &c); + assert(b.__left_ == 0); + assert(b.__right_ == 0); + assert(b.__is_black_ == true); + + assert(d.__parent_ == &c); + assert(d.__left_ == &a); + assert(d.__right_ == 0); + assert(d.__is_black_ == true); + + assert(a.__parent_ == &d); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == false); + } + { + Node root; + Node a; + Node b; + Node c; + Node d; + + root.__left_ = &c; + + c.__parent_ = &root; + c.__left_ = &b; + c.__right_ = &d; + c.__is_black_ = true; + + b.__parent_ = &c; + b.__left_ = 0; + b.__right_ = 0; + b.__is_black_ = false; + + d.__parent_ = &c; + d.__left_ = 0; + d.__right_ = &a; + d.__is_black_ = false; + + a.__parent_ = &d; + a.__left_ = 0; + a.__right_ = 0; + a.__is_black_ = false; + + std::__tree_balance_after_insert(root.__left_, &a); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__left_ == &c); + + assert(c.__parent_ == &root); + assert(c.__left_ == &b); + assert(c.__right_ == &d); + assert(c.__is_black_ == true); + + assert(b.__parent_ == &c); + assert(b.__left_ == 0); + assert(b.__right_ == 0); + assert(b.__is_black_ == true); + + assert(d.__parent_ == &c); + assert(d.__left_ == 0); + assert(d.__right_ == &a); + assert(d.__is_black_ == true); + + assert(a.__parent_ == &d); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == false); + } + { + Node root; + Node a; + Node b; + Node c; + Node d; + Node e; + Node f; + Node g; + Node h; + Node i; + + root.__left_ = &c; + + c.__parent_ = &root; + c.__left_ = &b; + c.__right_ = &d; + c.__is_black_ = true; + + b.__parent_ = &c; + b.__left_ = &a; + b.__right_ = &g; + b.__is_black_ = false; + + d.__parent_ = &c; + d.__left_ = &h; + d.__right_ = &i; + d.__is_black_ = false; + + a.__parent_ = &b; + a.__left_ = &e; + a.__right_ = &f; + a.__is_black_ = false; + + e.__parent_ = &a; + e.__is_black_ = true; + + f.__parent_ = &a; + f.__is_black_ = true; + + g.__parent_ = &b; + g.__is_black_ = true; + + h.__parent_ = &d; + h.__is_black_ = true; + + i.__parent_ = &d; + i.__is_black_ = true; + + std::__tree_balance_after_insert(root.__left_, &a); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__left_ == &c); + + assert(c.__parent_ == &root); + assert(c.__left_ == &b); + assert(c.__right_ == &d); + assert(c.__is_black_ == true); + + assert(b.__parent_ == &c); + assert(b.__left_ == &a); + assert(b.__right_ == &g); + assert(b.__is_black_ == true); + + assert(d.__parent_ == &c); + assert(d.__left_ == &h); + assert(d.__right_ == &i); + assert(d.__is_black_ == true); + + assert(a.__parent_ == &b); + assert(a.__left_ == &e); + assert(a.__right_ == &f); + assert(a.__is_black_ == false); + } + { + Node root; + Node a; + Node b; + Node c; + Node d; + Node e; + Node f; + Node g; + Node h; + Node i; + + root.__left_ = &c; + + c.__parent_ = &root; + c.__left_ = &b; + c.__right_ = &d; + c.__is_black_ = true; + + b.__parent_ = &c; + b.__left_ = &g; + b.__right_ = &a; + b.__is_black_ = false; + + d.__parent_ = &c; + d.__left_ = &h; + d.__right_ = &i; + d.__is_black_ = false; + + a.__parent_ = &b; + a.__left_ = &e; + a.__right_ = &f; + a.__is_black_ = false; + + e.__parent_ = &a; + e.__is_black_ = true; + + f.__parent_ = &a; + f.__is_black_ = true; + + g.__parent_ = &b; + g.__is_black_ = true; + + h.__parent_ = &d; + h.__is_black_ = true; + + i.__parent_ = &d; + i.__is_black_ = true; + + std::__tree_balance_after_insert(root.__left_, &a); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__left_ == &c); + + assert(c.__parent_ == &root); + assert(c.__left_ == &b); + assert(c.__right_ == &d); + assert(c.__is_black_ == true); + + assert(b.__parent_ == &c); + assert(b.__left_ == &g); + assert(b.__right_ == &a); + assert(b.__is_black_ == true); + + assert(d.__parent_ == &c); + assert(d.__left_ == &h); + assert(d.__right_ == &i); + assert(d.__is_black_ == true); + + assert(a.__parent_ == &b); + assert(a.__left_ == &e); + assert(a.__right_ == &f); + assert(a.__is_black_ == false); + } + { + Node root; + Node a; + Node b; + Node c; + Node d; + Node e; + Node f; + Node g; + Node h; + Node i; + + root.__left_ = &c; + + c.__parent_ = &root; + c.__left_ = &b; + c.__right_ = &d; + c.__is_black_ = true; + + b.__parent_ = &c; + b.__left_ = &g; + b.__right_ = &h; + b.__is_black_ = false; + + d.__parent_ = &c; + d.__left_ = &a; + d.__right_ = &i; + d.__is_black_ = false; + + a.__parent_ = &d; + a.__left_ = &e; + a.__right_ = &f; + a.__is_black_ = false; + + e.__parent_ = &a; + e.__is_black_ = true; + + f.__parent_ = &a; + f.__is_black_ = true; + + g.__parent_ = &b; + g.__is_black_ = true; + + h.__parent_ = &b; + h.__is_black_ = true; + + i.__parent_ = &d; + i.__is_black_ = true; + + std::__tree_balance_after_insert(root.__left_, &a); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__left_ == &c); + + assert(c.__parent_ == &root); + assert(c.__left_ == &b); + assert(c.__right_ == &d); + assert(c.__is_black_ == true); + + assert(b.__parent_ == &c); + assert(b.__left_ == &g); + assert(b.__right_ == &h); + assert(b.__is_black_ == true); + + assert(d.__parent_ == &c); + assert(d.__left_ == &a); + assert(d.__right_ == &i); + assert(d.__is_black_ == true); + + assert(a.__parent_ == &d); + assert(a.__left_ == &e); + assert(a.__right_ == &f); + assert(a.__is_black_ == false); + } + { + Node root; + Node a; + Node b; + Node c; + Node d; + Node e; + Node f; + Node g; + Node h; + Node i; + + root.__left_ = &c; + + c.__parent_ = &root; + c.__left_ = &b; + c.__right_ = &d; + c.__is_black_ = true; + + b.__parent_ = &c; + b.__left_ = &g; + b.__right_ = &h; + b.__is_black_ = false; + + d.__parent_ = &c; + d.__left_ = &i; + d.__right_ = &a; + d.__is_black_ = false; + + a.__parent_ = &d; + a.__left_ = &e; + a.__right_ = &f; + a.__is_black_ = false; + + e.__parent_ = &a; + e.__is_black_ = true; + + f.__parent_ = &a; + f.__is_black_ = true; + + g.__parent_ = &b; + g.__is_black_ = true; + + h.__parent_ = &b; + h.__is_black_ = true; + + i.__parent_ = &d; + i.__is_black_ = true; + + std::__tree_balance_after_insert(root.__left_, &a); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__left_ == &c); + + assert(c.__parent_ == &root); + assert(c.__left_ == &b); + assert(c.__right_ == &d); + assert(c.__is_black_ == true); + + assert(b.__parent_ == &c); + assert(b.__left_ == &g); + assert(b.__right_ == &h); + assert(b.__is_black_ == true); + + assert(d.__parent_ == &c); + assert(d.__left_ == &i); + assert(d.__right_ == &a); + assert(d.__is_black_ == true); + + assert(a.__parent_ == &d); + assert(a.__left_ == &e); + assert(a.__right_ == &f); + assert(a.__is_black_ == false); + } +} + +void +test2() +{ + { + Node root; + Node a; + Node b; + Node c; + + root.__left_ = &c; + + c.__parent_ = &root; + c.__left_ = &a; + c.__right_ = 0; + c.__is_black_ = true; + + a.__parent_ = &c; + a.__left_ = 0; + a.__right_ = &b; + a.__is_black_ = false; + + b.__parent_ = &a; + b.__left_ = 0; + b.__right_ = 0; + b.__is_black_ = false; + + std::__tree_balance_after_insert(root.__left_, &b); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__left_ == &b); + + assert(c.__parent_ == &b); + assert(c.__left_ == 0); + assert(c.__right_ == 0); + assert(c.__is_black_ == false); + + assert(a.__parent_ == &b); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == false); + + assert(b.__parent_ == &root); + assert(b.__left_ == &a); + assert(b.__right_ == &c); + assert(b.__is_black_ == true); + } + { + Node root; + Node a; + Node b; + Node c; + + root.__left_ = &a; + + a.__parent_ = &root; + a.__left_ = 0; + a.__right_ = &c; + a.__is_black_ = true; + + c.__parent_ = &a; + c.__left_ = &b; + c.__right_ = 0; + c.__is_black_ = false; + + b.__parent_ = &c; + b.__left_ = 0; + b.__right_ = 0; + b.__is_black_ = false; + + std::__tree_balance_after_insert(root.__left_, &b); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__left_ == &b); + + assert(a.__parent_ == &b); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == false); + + assert(c.__parent_ == &b); + assert(c.__left_ == 0); + assert(c.__right_ == 0); + assert(c.__is_black_ == false); + + assert(b.__parent_ == &root); + assert(b.__left_ == &a); + assert(b.__right_ == &c); + assert(b.__is_black_ == true); + } + { + Node root; + Node a; + Node b; + Node c; + Node d; + Node e; + Node f; + Node g; + + root.__left_ = &c; + + c.__parent_ = &root; + c.__left_ = &a; + c.__right_ = &g; + c.__is_black_ = true; + + a.__parent_ = &c; + a.__left_ = &d; + a.__right_ = &b; + a.__is_black_ = false; + + b.__parent_ = &a; + b.__left_ = &e; + b.__right_ = &f; + b.__is_black_ = false; + + d.__parent_ = &a; + d.__is_black_ = true; + + e.__parent_ = &b; + e.__is_black_ = true; + + f.__parent_ = &b; + f.__is_black_ = true; + + g.__parent_ = &c; + g.__is_black_ = true; + + std::__tree_balance_after_insert(root.__left_, &b); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__left_ == &b); + + assert(c.__parent_ == &b); + assert(c.__left_ == &f); + assert(c.__right_ == &g); + assert(c.__is_black_ == false); + + assert(a.__parent_ == &b); + assert(a.__left_ == &d); + assert(a.__right_ == &e); + assert(a.__is_black_ == false); + + assert(b.__parent_ == &root); + assert(b.__left_ == &a); + assert(b.__right_ == &c); + assert(b.__is_black_ == true); + + assert(d.__parent_ == &a); + assert(d.__is_black_ == true); + + assert(e.__parent_ == &a); + assert(e.__is_black_ == true); + + assert(f.__parent_ == &c); + assert(f.__is_black_ == true); + + assert(g.__parent_ == &c); + assert(g.__is_black_ == true); + } + { + Node root; + Node a; + Node b; + Node c; + Node d; + Node e; + Node f; + Node g; + + root.__left_ = &a; + + a.__parent_ = &root; + a.__left_ = &d; + a.__right_ = &c; + a.__is_black_ = true; + + c.__parent_ = &a; + c.__left_ = &b; + c.__right_ = &g; + c.__is_black_ = false; + + b.__parent_ = &c; + b.__left_ = &e; + b.__right_ = &f; + b.__is_black_ = false; + + d.__parent_ = &a; + d.__is_black_ = true; + + e.__parent_ = &b; + e.__is_black_ = true; + + f.__parent_ = &b; + f.__is_black_ = true; + + g.__parent_ = &c; + g.__is_black_ = true; + + std::__tree_balance_after_insert(root.__left_, &b); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__left_ == &b); + + assert(c.__parent_ == &b); + assert(c.__left_ == &f); + assert(c.__right_ == &g); + assert(c.__is_black_ == false); + + assert(a.__parent_ == &b); + assert(a.__left_ == &d); + assert(a.__right_ == &e); + assert(a.__is_black_ == false); + + assert(b.__parent_ == &root); + assert(b.__left_ == &a); + assert(b.__right_ == &c); + assert(b.__is_black_ == true); + + assert(d.__parent_ == &a); + assert(d.__is_black_ == true); + + assert(e.__parent_ == &a); + assert(e.__is_black_ == true); + + assert(f.__parent_ == &c); + assert(f.__is_black_ == true); + + assert(g.__parent_ == &c); + assert(g.__is_black_ == true); + } +} + +void +test3() +{ + { + Node root; + Node a; + Node b; + Node c; + + root.__left_ = &c; + + c.__parent_ = &root; + c.__left_ = &b; + c.__right_ = 0; + c.__is_black_ = true; + + b.__parent_ = &c; + b.__left_ = &a; + b.__right_ = 0; + b.__is_black_ = false; + + a.__parent_ = &b; + a.__left_ = 0; + a.__right_ = 0; + a.__is_black_ = false; + + std::__tree_balance_after_insert(root.__left_, &a); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__left_ == &b); + + assert(c.__parent_ == &b); + assert(c.__left_ == 0); + assert(c.__right_ == 0); + assert(c.__is_black_ == false); + + assert(a.__parent_ == &b); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == false); + + assert(b.__parent_ == &root); + assert(b.__left_ == &a); + assert(b.__right_ == &c); + assert(b.__is_black_ == true); + } + { + Node root; + Node a; + Node b; + Node c; + + root.__left_ = &a; + + a.__parent_ = &root; + a.__left_ = 0; + a.__right_ = &b; + a.__is_black_ = true; + + b.__parent_ = &a; + b.__left_ = 0; + b.__right_ = &c; + b.__is_black_ = false; + + c.__parent_ = &b; + c.__left_ = 0; + c.__right_ = 0; + c.__is_black_ = false; + + std::__tree_balance_after_insert(root.__left_, &c); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__left_ == &b); + + assert(a.__parent_ == &b); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == false); + + assert(c.__parent_ == &b); + assert(c.__left_ == 0); + assert(c.__right_ == 0); + assert(c.__is_black_ == false); + + assert(b.__parent_ == &root); + assert(b.__left_ == &a); + assert(b.__right_ == &c); + assert(b.__is_black_ == true); + } + { + Node root; + Node a; + Node b; + Node c; + Node d; + Node e; + Node f; + Node g; + + root.__left_ = &c; + + c.__parent_ = &root; + c.__left_ = &b; + c.__right_ = &g; + c.__is_black_ = true; + + b.__parent_ = &c; + b.__left_ = &a; + b.__right_ = &f; + b.__is_black_ = false; + + a.__parent_ = &b; + a.__left_ = &d; + a.__right_ = &e; + a.__is_black_ = false; + + d.__parent_ = &a; + d.__is_black_ = true; + + e.__parent_ = &a; + e.__is_black_ = true; + + f.__parent_ = &b; + f.__is_black_ = true; + + g.__parent_ = &c; + g.__is_black_ = true; + + std::__tree_balance_after_insert(root.__left_, &a); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__left_ == &b); + + assert(c.__parent_ == &b); + assert(c.__left_ == &f); + assert(c.__right_ == &g); + assert(c.__is_black_ == false); + + assert(a.__parent_ == &b); + assert(a.__left_ == &d); + assert(a.__right_ == &e); + assert(a.__is_black_ == false); + + assert(b.__parent_ == &root); + assert(b.__left_ == &a); + assert(b.__right_ == &c); + assert(b.__is_black_ == true); + + assert(d.__parent_ == &a); + assert(d.__is_black_ == true); + + assert(e.__parent_ == &a); + assert(e.__is_black_ == true); + + assert(f.__parent_ == &c); + assert(f.__is_black_ == true); + + assert(g.__parent_ == &c); + assert(g.__is_black_ == true); + } + { + Node root; + Node a; + Node b; + Node c; + Node d; + Node e; + Node f; + Node g; + + root.__left_ = &a; + + a.__parent_ = &root; + a.__left_ = &d; + a.__right_ = &b; + a.__is_black_ = true; + + b.__parent_ = &a; + b.__left_ = &e; + b.__right_ = &c; + b.__is_black_ = false; + + c.__parent_ = &b; + c.__left_ = &f; + c.__right_ = &g; + c.__is_black_ = false; + + d.__parent_ = &a; + d.__is_black_ = true; + + e.__parent_ = &b; + e.__is_black_ = true; + + f.__parent_ = &c; + f.__is_black_ = true; + + g.__parent_ = &c; + g.__is_black_ = true; + + std::__tree_balance_after_insert(root.__left_, &c); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__left_ == &b); + + assert(c.__parent_ == &b); + assert(c.__left_ == &f); + assert(c.__right_ == &g); + assert(c.__is_black_ == false); + + assert(a.__parent_ == &b); + assert(a.__left_ == &d); + assert(a.__right_ == &e); + assert(a.__is_black_ == false); + + assert(b.__parent_ == &root); + assert(b.__left_ == &a); + assert(b.__right_ == &c); + assert(b.__is_black_ == true); + + assert(d.__parent_ == &a); + assert(d.__is_black_ == true); + + assert(e.__parent_ == &a); + assert(e.__is_black_ == true); + + assert(f.__parent_ == &c); + assert(f.__is_black_ == true); + + assert(g.__parent_ == &c); + assert(g.__is_black_ == true); + } +} + +void +test4() +{ + Node root; + Node a; + Node b; + Node c; + Node d; + Node e; + Node f; + Node g; + Node h; + + root.__left_ = &a; + a.__parent_ = &root; + + std::__tree_balance_after_insert(root.__left_, &a); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &a); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(a.__parent_ == &root); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == true); + + a.__right_ = &b; + b.__parent_ = &a; + + std::__tree_balance_after_insert(root.__left_, &b); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &a); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(a.__parent_ == &root); + assert(a.__left_ == 0); + assert(a.__right_ == &b); + assert(a.__is_black_ == true); + + assert(b.__parent_ == &a); + assert(b.__left_ == 0); + assert(b.__right_ == 0); + assert(b.__is_black_ == false); + + b.__right_ = &c; + c.__parent_ = &b; + + std::__tree_balance_after_insert(root.__left_, &c); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &b); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(a.__parent_ == &b); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == false); + + assert(b.__parent_ == &root); + assert(b.__left_ == &a); + assert(b.__right_ == &c); + assert(b.__is_black_ == true); + + assert(c.__parent_ == &b); + assert(c.__left_ == 0); + assert(c.__right_ == 0); + assert(c.__is_black_ == false); + + c.__right_ = &d; + d.__parent_ = &c; + + std::__tree_balance_after_insert(root.__left_, &d); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &b); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(a.__parent_ == &b); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == true); + + assert(b.__parent_ == &root); + assert(b.__left_ == &a); + assert(b.__right_ == &c); + assert(b.__is_black_ == true); + + assert(c.__parent_ == &b); + assert(c.__left_ == 0); + assert(c.__right_ == &d); + assert(c.__is_black_ == true); + + assert(d.__parent_ == &c); + assert(d.__left_ == 0); + assert(d.__right_ == 0); + assert(d.__is_black_ == false); + + d.__right_ = &e; + e.__parent_ = &d; + + std::__tree_balance_after_insert(root.__left_, &e); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &b); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(b.__parent_ == &root); + assert(b.__left_ == &a); + assert(b.__right_ == &d); + assert(b.__is_black_ == true); + + assert(a.__parent_ == &b); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == true); + + assert(d.__parent_ == &b); + assert(d.__left_ == &c); + assert(d.__right_ == &e); + assert(d.__is_black_ == true); + + assert(c.__parent_ == &d); + assert(c.__left_ == 0); + assert(c.__right_ == 0); + assert(c.__is_black_ == false); + + assert(e.__parent_ == &d); + assert(e.__left_ == 0); + assert(e.__right_ == 0); + assert(e.__is_black_ == false); + + e.__right_ = &f; + f.__parent_ = &e; + + std::__tree_balance_after_insert(root.__left_, &f); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &b); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(b.__parent_ == &root); + assert(b.__left_ == &a); + assert(b.__right_ == &d); + assert(b.__is_black_ == true); + + assert(a.__parent_ == &b); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == true); + + assert(d.__parent_ == &b); + assert(d.__left_ == &c); + assert(d.__right_ == &e); + assert(d.__is_black_ == false); + + assert(c.__parent_ == &d); + assert(c.__left_ == 0); + assert(c.__right_ == 0); + assert(c.__is_black_ == true); + + assert(e.__parent_ == &d); + assert(e.__left_ == 0); + assert(e.__right_ == &f); + assert(e.__is_black_ == true); + + assert(f.__parent_ == &e); + assert(f.__left_ == 0); + assert(f.__right_ == 0); + assert(f.__is_black_ == false); + + f.__right_ = &g; + g.__parent_ = &f; + + std::__tree_balance_after_insert(root.__left_, &g); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &b); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(b.__parent_ == &root); + assert(b.__left_ == &a); + assert(b.__right_ == &d); + assert(b.__is_black_ == true); + + assert(a.__parent_ == &b); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == true); + + assert(d.__parent_ == &b); + assert(d.__left_ == &c); + assert(d.__right_ == &f); + assert(d.__is_black_ == false); + + assert(c.__parent_ == &d); + assert(c.__left_ == 0); + assert(c.__right_ == 0); + assert(c.__is_black_ == true); + + assert(f.__parent_ == &d); + assert(f.__left_ == &e); + assert(f.__right_ == &g); + assert(f.__is_black_ == true); + + assert(e.__parent_ == &f); + assert(e.__left_ == 0); + assert(e.__right_ == 0); + assert(e.__is_black_ == false); + + assert(g.__parent_ == &f); + assert(g.__left_ == 0); + assert(g.__right_ == 0); + assert(g.__is_black_ == false); + + g.__right_ = &h; + h.__parent_ = &g; + + std::__tree_balance_after_insert(root.__left_, &h); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &d); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(d.__parent_ == &root); + assert(d.__left_ == &b); + assert(d.__right_ == &f); + assert(d.__is_black_ == true); + + assert(b.__parent_ == &d); + assert(b.__left_ == &a); + assert(b.__right_ == &c); + assert(b.__is_black_ == false); + + assert(a.__parent_ == &b); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == true); + + assert(c.__parent_ == &b); + assert(c.__left_ == 0); + assert(c.__right_ == 0); + assert(c.__is_black_ == true); + + assert(f.__parent_ == &d); + assert(f.__left_ == &e); + assert(f.__right_ == &g); + assert(f.__is_black_ == false); + + assert(e.__parent_ == &f); + assert(e.__left_ == 0); + assert(e.__right_ == 0); + assert(e.__is_black_ == true); + + assert(g.__parent_ == &f); + assert(g.__left_ == 0); + assert(g.__right_ == &h); + assert(g.__is_black_ == true); + + assert(h.__parent_ == &g); + assert(h.__left_ == 0); + assert(h.__right_ == 0); + assert(h.__is_black_ == false); +} + +void +test5() +{ + Node root; + Node a; + Node b; + Node c; + Node d; + Node e; + Node f; + Node g; + Node h; + + root.__left_ = &h; + h.__parent_ = &root; + + std::__tree_balance_after_insert(root.__left_, &h); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &h); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(h.__parent_ == &root); + assert(h.__left_ == 0); + assert(h.__right_ == 0); + assert(h.__is_black_ == true); + + h.__left_ = &g; + g.__parent_ = &h; + + std::__tree_balance_after_insert(root.__left_, &g); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &h); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(h.__parent_ == &root); + assert(h.__left_ == &g); + assert(h.__right_ == 0); + assert(h.__is_black_ == true); + + assert(g.__parent_ == &h); + assert(g.__left_ == 0); + assert(g.__right_ == 0); + assert(g.__is_black_ == false); + + g.__left_ = &f; + f.__parent_ = &g; + + std::__tree_balance_after_insert(root.__left_, &f); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &g); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(g.__parent_ == &root); + assert(g.__left_ == &f); + assert(g.__right_ == &h); + assert(g.__is_black_ == true); + + assert(f.__parent_ == &g); + assert(f.__left_ == 0); + assert(f.__right_ == 0); + assert(f.__is_black_ == false); + + assert(h.__parent_ == &g); + assert(h.__left_ == 0); + assert(h.__right_ == 0); + assert(h.__is_black_ == false); + + f.__left_ = &e; + e.__parent_ = &f; + + std::__tree_balance_after_insert(root.__left_, &e); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &g); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(g.__parent_ == &root); + assert(g.__left_ == &f); + assert(g.__right_ == &h); + assert(g.__is_black_ == true); + + assert(f.__parent_ == &g); + assert(f.__left_ == &e); + assert(f.__right_ == 0); + assert(f.__is_black_ == true); + + assert(e.__parent_ == &f); + assert(e.__left_ == 0); + assert(e.__right_ == 0); + assert(e.__is_black_ == false); + + assert(h.__parent_ == &g); + assert(h.__left_ == 0); + assert(h.__right_ == 0); + assert(h.__is_black_ == true); + + e.__left_ = &d; + d.__parent_ = &e; + + std::__tree_balance_after_insert(root.__left_, &d); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &g); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(g.__parent_ == &root); + assert(g.__left_ == &e); + assert(g.__right_ == &h); + assert(g.__is_black_ == true); + + assert(e.__parent_ == &g); + assert(e.__left_ == &d); + assert(e.__right_ == &f); + assert(e.__is_black_ == true); + + assert(d.__parent_ == &e); + assert(d.__left_ == 0); + assert(d.__right_ == 0); + assert(d.__is_black_ == false); + + assert(f.__parent_ == &e); + assert(f.__left_ == 0); + assert(f.__right_ == 0); + assert(f.__is_black_ == false); + + assert(h.__parent_ == &g); + assert(h.__left_ == 0); + assert(h.__right_ == 0); + assert(h.__is_black_ == true); + + d.__left_ = &c; + c.__parent_ = &d; + + std::__tree_balance_after_insert(root.__left_, &c); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &g); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(g.__parent_ == &root); + assert(g.__left_ == &e); + assert(g.__right_ == &h); + assert(g.__is_black_ == true); + + assert(e.__parent_ == &g); + assert(e.__left_ == &d); + assert(e.__right_ == &f); + assert(e.__is_black_ == false); + + assert(d.__parent_ == &e); + assert(d.__left_ == &c); + assert(d.__right_ == 0); + assert(d.__is_black_ == true); + + assert(c.__parent_ == &d); + assert(c.__left_ == 0); + assert(c.__right_ == 0); + assert(c.__is_black_ == false); + + assert(f.__parent_ == &e); + assert(f.__left_ == 0); + assert(f.__right_ == 0); + assert(f.__is_black_ == true); + + assert(h.__parent_ == &g); + assert(h.__left_ == 0); + assert(h.__right_ == 0); + assert(h.__is_black_ == true); + + c.__left_ = &b; + b.__parent_ = &c; + + std::__tree_balance_after_insert(root.__left_, &b); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &g); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(g.__parent_ == &root); + assert(g.__left_ == &e); + assert(g.__right_ == &h); + assert(g.__is_black_ == true); + + assert(e.__parent_ == &g); + assert(e.__left_ == &c); + assert(e.__right_ == &f); + assert(e.__is_black_ == false); + + assert(c.__parent_ == &e); + assert(c.__left_ == &b); + assert(c.__right_ == &d); + assert(c.__is_black_ == true); + + assert(b.__parent_ == &c); + assert(b.__left_ == 0); + assert(b.__right_ == 0); + assert(b.__is_black_ == false); + + assert(d.__parent_ == &c); + assert(d.__left_ == 0); + assert(d.__right_ == 0); + assert(d.__is_black_ == false); + + assert(f.__parent_ == &e); + assert(f.__left_ == 0); + assert(f.__right_ == 0); + assert(f.__is_black_ == true); + + assert(h.__parent_ == &g); + assert(h.__left_ == 0); + assert(h.__right_ == 0); + assert(h.__is_black_ == true); + + b.__left_ = &a; + a.__parent_ = &b; + + std::__tree_balance_after_insert(root.__left_, &a); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &e); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(e.__parent_ == &root); + assert(e.__left_ == &c); + assert(e.__right_ == &g); + assert(e.__is_black_ == true); + + assert(c.__parent_ == &e); + assert(c.__left_ == &b); + assert(c.__right_ == &d); + assert(c.__is_black_ == false); + + assert(b.__parent_ == &c); + assert(b.__left_ == &a); + assert(b.__right_ == 0); + assert(b.__is_black_ == true); + + assert(a.__parent_ == &b); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == false); + + assert(d.__parent_ == &c); + assert(d.__left_ == 0); + assert(d.__right_ == 0); + assert(d.__is_black_ == true); + + assert(g.__parent_ == &e); + assert(g.__left_ == &f); + assert(g.__right_ == &h); + assert(g.__is_black_ == false); + + assert(f.__parent_ == &g); + assert(f.__left_ == 0); + assert(f.__right_ == 0); + assert(f.__is_black_ == true); + + assert(h.__parent_ == &g); + assert(h.__left_ == 0); + assert(h.__right_ == 0); + assert(h.__is_black_ == true); +} + +int main() +{ + test1(); + test2(); + test3(); + test4(); + test5(); +} diff --git a/test/libcxx/containers/associative/tree_key_value_traits.pass.cpp b/test/libcxx/containers/associative/tree_key_value_traits.pass.cpp new file mode 100644 index 0000000000000..0befd749a50c0 --- /dev/null +++ b/test/libcxx/containers/associative/tree_key_value_traits.pass.cpp @@ -0,0 +1,59 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +#include <__tree> +#include <map> +#include <set> +#include <type_traits> + +#include "test_macros.h" +#include "min_allocator.h" + +void testKeyValueTrait() { + { + typedef int Tp; + typedef std::__tree_key_value_types<Tp> Traits; + static_assert((std::is_same<Traits::key_type, int>::value), ""); + static_assert((std::is_same<Traits::__node_value_type, Tp>::value), ""); + static_assert((std::is_same<Traits::__container_value_type, Tp>::value), ""); + static_assert(Traits::__is_map == false, ""); + } + { + typedef std::pair<int, int> Tp; + typedef std::__tree_key_value_types<Tp> Traits; + static_assert((std::is_same<Traits::key_type, Tp>::value), ""); + static_assert((std::is_same<Traits::__node_value_type, Tp>::value), ""); + static_assert((std::is_same<Traits::__container_value_type, Tp>::value), ""); + static_assert(Traits::__is_map == false, ""); + } + { + typedef std::pair<const int, int> Tp; + typedef std::__tree_key_value_types<Tp> Traits; + static_assert((std::is_same<Traits::key_type, Tp>::value), ""); + static_assert((std::is_same<Traits::__node_value_type, Tp>::value), ""); + static_assert((std::is_same<Traits::__container_value_type, Tp>::value), ""); + static_assert(Traits::__is_map == false, ""); + } + { + typedef std::__value_type<int, int> Tp; + typedef std::__tree_key_value_types<Tp> Traits; + static_assert((std::is_same<Traits::key_type, int>::value), ""); + static_assert((std::is_same<Traits::mapped_type, int>::value), ""); + static_assert((std::is_same<Traits::__node_value_type, Tp>::value), ""); + static_assert((std::is_same<Traits::__container_value_type, + std::pair<const int, int> >::value), ""); + static_assert((std::is_same<Traits::__map_value_type, + std::pair<const int, int> >::value), ""); + static_assert(Traits::__is_map == true, ""); + } +} + +int main() { + testKeyValueTrait(); +} diff --git a/test/libcxx/containers/associative/tree_left_rotate.pass.cpp b/test/libcxx/containers/associative/tree_left_rotate.pass.cpp new file mode 100644 index 0000000000000..2720b448bdd4e --- /dev/null +++ b/test/libcxx/containers/associative/tree_left_rotate.pass.cpp @@ -0,0 +1,101 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// Not a portable test + +// Precondition: __x->__right_ != nullptr +// template <class _NodePtr> +// void +// __tree_left_rotate(_NodePtr __x); + +#include <__tree> +#include <cassert> + +struct Node +{ + Node* __left_; + Node* __right_; + Node* __parent_; + + Node* __parent_unsafe() const { return __parent_; } + void __set_parent(Node* x) { __parent_ = x;} + + Node() : __left_(), __right_(), __parent_() {} +}; + +void +test1() +{ + Node root; + Node x; + Node y; + root.__left_ = &x; + x.__left_ = 0; + x.__right_ = &y; + x.__parent_ = &root; + y.__left_ = 0; + y.__right_ = 0; + y.__parent_ = &x; + std::__tree_left_rotate(&x); + assert(root.__parent_ == 0); + assert(root.__left_ == &y); + assert(root.__right_ == 0); + assert(y.__parent_ == &root); + assert(y.__left_ == &x); + assert(y.__right_ == 0); + assert(x.__parent_ == &y); + assert(x.__left_ == 0); + assert(x.__right_ == 0); +} + +void +test2() +{ + Node root; + Node x; + Node y; + Node a; + Node b; + Node c; + root.__left_ = &x; + x.__left_ = &a; + x.__right_ = &y; + x.__parent_ = &root; + y.__left_ = &b; + y.__right_ = &c; + y.__parent_ = &x; + a.__parent_ = &x; + b.__parent_ = &y; + c.__parent_ = &y; + std::__tree_left_rotate(&x); + assert(root.__parent_ == 0); + assert(root.__left_ == &y); + assert(root.__right_ == 0); + assert(y.__parent_ == &root); + assert(y.__left_ == &x); + assert(y.__right_ == &c); + assert(x.__parent_ == &y); + assert(x.__left_ == &a); + assert(x.__right_ == &b); + assert(a.__parent_ == &x); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(b.__parent_ == &x); + assert(b.__left_ == 0); + assert(b.__right_ == 0); + assert(c.__parent_ == &y); + assert(c.__left_ == 0); + assert(c.__right_ == 0); +} + +int main() +{ + test1(); + test2(); +} diff --git a/test/libcxx/containers/associative/tree_remove.pass.cpp b/test/libcxx/containers/associative/tree_remove.pass.cpp new file mode 100644 index 0000000000000..fa0b7d4a13117 --- /dev/null +++ b/test/libcxx/containers/associative/tree_remove.pass.cpp @@ -0,0 +1,1651 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// Not a portable test + +// Returns __tree_next(__z) +// template <class _NodePtr> +// void +// __tree_remove(_NodePtr __root, _NodePtr __z) + +#include <__tree> +#include <cassert> + +struct Node +{ + Node* __left_; + Node* __right_; + Node* __parent_; + bool __is_black_; + + Node* __parent_unsafe() const { return __parent_; } + void __set_parent(Node* x) { __parent_ = x;} + + Node() : __left_(), __right_(), __parent_(), __is_black_() {} +}; + +void +test1() +{ + { + // Left + // Case 1 -> Case 2 -> x is red turned to black + Node root; + Node b; + Node c; + Node d; + Node e; + Node y; + + root.__left_ = &b; + + b.__parent_ = &root; + b.__left_ = &y; + b.__right_ = &d; + b.__is_black_ = true; + + y.__parent_ = &b; + y.__left_ = 0; + y.__right_ = 0; + y.__is_black_ = true; + + d.__parent_ = &b; + d.__left_ = &c; + d.__right_ = &e; + d.__is_black_ = false; + + c.__parent_ = &d; + c.__left_ = 0; + c.__right_ = 0; + c.__is_black_ = true; + + e.__parent_ = &d; + e.__left_ = 0; + e.__right_ = 0; + e.__is_black_ = true; + + std::__tree_remove(root.__left_, &y); + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &d); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(d.__parent_ == &root); + assert(d.__left_ == &b); + assert(d.__right_ == &e); + assert(d.__is_black_ == true); + + assert(b.__parent_ == &d); + assert(b.__left_ == 0); + assert(b.__right_ == &c); + assert(b.__is_black_ == true); + + assert(c.__parent_ == &b); + assert(c.__left_ == 0); + assert(c.__right_ == 0); + assert(c.__is_black_ == false); + + assert(e.__parent_ == &d); + assert(e.__left_ == 0); + assert(e.__right_ == 0); + assert(e.__is_black_ == true); + } + { + // Right + // Case 1 -> Case 2 -> x is red turned to black + Node root; + Node b; + Node c; + Node d; + Node e; + Node y; + + root.__left_ = &b; + + b.__parent_ = &root; + b.__right_ = &y; + b.__left_ = &d; + b.__is_black_ = true; + + y.__parent_ = &b; + y.__right_ = 0; + y.__left_ = 0; + y.__is_black_ = true; + + d.__parent_ = &b; + d.__right_ = &c; + d.__left_ = &e; + d.__is_black_ = false; + + c.__parent_ = &d; + c.__right_ = 0; + c.__left_ = 0; + c.__is_black_ = true; + + e.__parent_ = &d; + e.__right_ = 0; + e.__left_ = 0; + e.__is_black_ = true; + + std::__tree_remove(root.__left_, &y); + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &d); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(d.__parent_ == &root); + assert(d.__right_ == &b); + assert(d.__left_ == &e); + assert(d.__is_black_ == true); + + assert(b.__parent_ == &d); + assert(b.__right_ == 0); + assert(b.__left_ == &c); + assert(b.__is_black_ == true); + + assert(c.__parent_ == &b); + assert(c.__right_ == 0); + assert(c.__left_ == 0); + assert(c.__is_black_ == false); + + assert(e.__parent_ == &d); + assert(e.__right_ == 0); + assert(e.__left_ == 0); + assert(e.__is_black_ == true); + } + { + // Left + // Case 1 -> Case 3 -> Case 4 + Node root; + Node b; + Node c; + Node d; + Node e; + Node f; + Node y; + + root.__left_ = &b; + + b.__parent_ = &root; + b.__left_ = &y; + b.__right_ = &d; + b.__is_black_ = true; + + y.__parent_ = &b; + y.__left_ = 0; + y.__right_ = 0; + y.__is_black_ = true; + + d.__parent_ = &b; + d.__left_ = &c; + d.__right_ = &e; + d.__is_black_ = false; + + c.__parent_ = &d; + c.__left_ = &f; + c.__right_ = 0; + c.__is_black_ = true; + + e.__parent_ = &d; + e.__left_ = 0; + e.__right_ = 0; + e.__is_black_ = true; + + f.__parent_ = &c; + f.__left_ = 0; + f.__right_ = 0; + f.__is_black_ = false; + + std::__tree_remove(root.__left_, &y); + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &d); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(d.__parent_ == &root); + assert(d.__left_ == &f); + assert(d.__right_ == &e); + assert(d.__is_black_ == true); + + assert(f.__parent_ == &d); + assert(f.__left_ == &b); + assert(f.__right_ == &c); + assert(f.__is_black_ == false); + + assert(b.__parent_ == &f); + assert(b.__left_ == 0); + assert(b.__right_ == 0); + assert(b.__is_black_ == true); + + assert(c.__parent_ == &f); + assert(c.__left_ == 0); + assert(c.__right_ == 0); + assert(c.__is_black_ == true); + + assert(e.__parent_ == &d); + assert(e.__left_ == 0); + assert(e.__right_ == 0); + assert(e.__is_black_ == true); + } + { + // Right + // Case 1 -> Case 3 -> Case 4 + Node root; + Node b; + Node c; + Node d; + Node e; + Node f; + Node y; + + root.__left_ = &b; + + b.__parent_ = &root; + b.__right_ = &y; + b.__left_ = &d; + b.__is_black_ = true; + + y.__parent_ = &b; + y.__right_ = 0; + y.__left_ = 0; + y.__is_black_ = true; + + d.__parent_ = &b; + d.__right_ = &c; + d.__left_ = &e; + d.__is_black_ = false; + + c.__parent_ = &d; + c.__right_ = &f; + c.__left_ = 0; + c.__is_black_ = true; + + e.__parent_ = &d; + e.__right_ = 0; + e.__left_ = 0; + e.__is_black_ = true; + + f.__parent_ = &c; + f.__right_ = 0; + f.__left_ = 0; + f.__is_black_ = false; + + std::__tree_remove(root.__left_, &y); + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &d); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(d.__parent_ == &root); + assert(d.__right_ == &f); + assert(d.__left_ == &e); + assert(d.__is_black_ == true); + + assert(f.__parent_ == &d); + assert(f.__right_ == &b); + assert(f.__left_ == &c); + assert(f.__is_black_ == false); + + assert(b.__parent_ == &f); + assert(b.__right_ == 0); + assert(b.__left_ == 0); + assert(b.__is_black_ == true); + + assert(c.__parent_ == &f); + assert(c.__right_ == 0); + assert(c.__left_ == 0); + assert(c.__is_black_ == true); + + assert(e.__parent_ == &d); + assert(e.__right_ == 0); + assert(e.__left_ == 0); + assert(e.__is_black_ == true); + } +} + +void +test2() +{ + { + Node root; + Node a; + Node b; + Node c; + + root.__left_ = &b; + + b.__parent_ = &root; + b.__left_ = &a; + b.__right_ = &c; + b.__is_black_ = true; + + a.__parent_ = &b; + a.__left_ = 0; + a.__right_ = 0; + a.__is_black_ = true; + + c.__parent_ = &b; + c.__left_ = 0; + c.__right_ = 0; + c.__is_black_ = true; + + std::__tree_remove(root.__left_, &a); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &b); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(b.__parent_ == &root); + assert(b.__left_ == 0); + assert(b.__right_ == &c); + assert(b.__is_black_ == true); + + assert(c.__parent_ == &b); + assert(c.__left_ == 0); + assert(c.__right_ == 0); + assert(c.__is_black_ == false); + + std::__tree_remove(root.__left_, &b); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &c); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(c.__parent_ == &root); + assert(c.__left_ == 0); + assert(c.__right_ == 0); + assert(c.__is_black_ == true); + + std::__tree_remove(root.__left_, &c); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == 0); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + } + { + Node root; + Node a; + Node b; + Node c; + + root.__left_ = &b; + + b.__parent_ = &root; + b.__left_ = &a; + b.__right_ = &c; + b.__is_black_ = true; + + a.__parent_ = &b; + a.__left_ = 0; + a.__right_ = 0; + a.__is_black_ = false; + + c.__parent_ = &b; + c.__left_ = 0; + c.__right_ = 0; + c.__is_black_ = false; + + std::__tree_remove(root.__left_, &a); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &b); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(b.__parent_ == &root); + assert(b.__left_ == 0); + assert(b.__right_ == &c); + assert(b.__is_black_ == true); + + assert(c.__parent_ == &b); + assert(c.__left_ == 0); + assert(c.__right_ == 0); + assert(c.__is_black_ == false); + + std::__tree_remove(root.__left_, &b); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &c); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(c.__parent_ == &root); + assert(c.__left_ == 0); + assert(c.__right_ == 0); + assert(c.__is_black_ == true); + + std::__tree_remove(root.__left_, &c); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == 0); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + } + { + Node root; + Node a; + Node b; + Node c; + + root.__left_ = &b; + + b.__parent_ = &root; + b.__left_ = &a; + b.__right_ = &c; + b.__is_black_ = true; + + a.__parent_ = &b; + a.__left_ = 0; + a.__right_ = 0; + a.__is_black_ = true; + + c.__parent_ = &b; + c.__left_ = 0; + c.__right_ = 0; + c.__is_black_ = true; + + std::__tree_remove(root.__left_, &a); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &b); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(b.__parent_ == &root); + assert(b.__left_ == 0); + assert(b.__right_ == &c); + assert(b.__is_black_ == true); + + assert(c.__parent_ == &b); + assert(c.__left_ == 0); + assert(c.__right_ == 0); + assert(c.__is_black_ == false); + + std::__tree_remove(root.__left_, &c); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &b); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(b.__parent_ == &root); + assert(b.__left_ == 0); + assert(b.__right_ == 0); + assert(b.__is_black_ == true); + + std::__tree_remove(root.__left_, &b); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == 0); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + } + { + Node root; + Node a; + Node b; + Node c; + + root.__left_ = &b; + + b.__parent_ = &root; + b.__left_ = &a; + b.__right_ = &c; + b.__is_black_ = true; + + a.__parent_ = &b; + a.__left_ = 0; + a.__right_ = 0; + a.__is_black_ = false; + + c.__parent_ = &b; + c.__left_ = 0; + c.__right_ = 0; + c.__is_black_ = false; + + std::__tree_remove(root.__left_, &a); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &b); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(b.__parent_ == &root); + assert(b.__left_ == 0); + assert(b.__right_ == &c); + assert(b.__is_black_ == true); + + assert(c.__parent_ == &b); + assert(c.__left_ == 0); + assert(c.__right_ == 0); + assert(c.__is_black_ == false); + + std::__tree_remove(root.__left_, &c); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &b); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(b.__parent_ == &root); + assert(b.__left_ == 0); + assert(b.__right_ == 0); + assert(b.__is_black_ == true); + + std::__tree_remove(root.__left_, &b); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == 0); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + } + { + Node root; + Node a; + Node b; + Node c; + + root.__left_ = &b; + + b.__parent_ = &root; + b.__left_ = &a; + b.__right_ = &c; + b.__is_black_ = true; + + a.__parent_ = &b; + a.__left_ = 0; + a.__right_ = 0; + a.__is_black_ = true; + + c.__parent_ = &b; + c.__left_ = 0; + c.__right_ = 0; + c.__is_black_ = true; + + std::__tree_remove(root.__left_, &b); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &c); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(a.__parent_ == &c); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == false); + + assert(c.__parent_ == &root); + assert(c.__left_ == &a); + assert(c.__right_ == 0); + assert(c.__is_black_ == true); + + std::__tree_remove(root.__left_, &a); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &c); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(c.__parent_ == &root); + assert(c.__left_ == 0); + assert(c.__right_ == 0); + assert(c.__is_black_ == true); + + std::__tree_remove(root.__left_, &c); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == 0); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + } + { + Node root; + Node a; + Node b; + Node c; + + root.__left_ = &b; + + b.__parent_ = &root; + b.__left_ = &a; + b.__right_ = &c; + b.__is_black_ = true; + + a.__parent_ = &b; + a.__left_ = 0; + a.__right_ = 0; + a.__is_black_ = false; + + c.__parent_ = &b; + c.__left_ = 0; + c.__right_ = 0; + c.__is_black_ = false; + + std::__tree_remove(root.__left_, &b); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &c); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(a.__parent_ == &c); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == false); + + assert(c.__parent_ == &root); + assert(c.__left_ == &a); + assert(c.__right_ == 0); + assert(c.__is_black_ == true); + + std::__tree_remove(root.__left_, &a); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &c); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(c.__parent_ == &root); + assert(c.__left_ == 0); + assert(c.__right_ == 0); + assert(c.__is_black_ == true); + + std::__tree_remove(root.__left_, &c); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == 0); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + } + { + Node root; + Node a; + Node b; + Node c; + + root.__left_ = &b; + + b.__parent_ = &root; + b.__left_ = &a; + b.__right_ = &c; + b.__is_black_ = true; + + a.__parent_ = &b; + a.__left_ = 0; + a.__right_ = 0; + a.__is_black_ = true; + + c.__parent_ = &b; + c.__left_ = 0; + c.__right_ = 0; + c.__is_black_ = true; + + std::__tree_remove(root.__left_, &b); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &c); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(a.__parent_ == &c); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == false); + + assert(c.__parent_ == &root); + assert(c.__left_ == &a); + assert(c.__right_ == 0); + assert(c.__is_black_ == true); + + std::__tree_remove(root.__left_, &c); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &a); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(a.__parent_ == &root); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == true); + + std::__tree_remove(root.__left_, &a); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == 0); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + } + { + Node root; + Node a; + Node b; + Node c; + + root.__left_ = &b; + + b.__parent_ = &root; + b.__left_ = &a; + b.__right_ = &c; + b.__is_black_ = true; + + a.__parent_ = &b; + a.__left_ = 0; + a.__right_ = 0; + a.__is_black_ = false; + + c.__parent_ = &b; + c.__left_ = 0; + c.__right_ = 0; + c.__is_black_ = false; + + std::__tree_remove(root.__left_, &b); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &c); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(a.__parent_ == &c); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == false); + + assert(c.__parent_ == &root); + assert(c.__left_ == &a); + assert(c.__right_ == 0); + assert(c.__is_black_ == true); + + std::__tree_remove(root.__left_, &c); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &a); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(a.__parent_ == &root); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == true); + + std::__tree_remove(root.__left_, &a); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == 0); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + } + { + Node root; + Node a; + Node b; + Node c; + + root.__left_ = &b; + + b.__parent_ = &root; + b.__left_ = &a; + b.__right_ = &c; + b.__is_black_ = true; + + a.__parent_ = &b; + a.__left_ = 0; + a.__right_ = 0; + a.__is_black_ = true; + + c.__parent_ = &b; + c.__left_ = 0; + c.__right_ = 0; + c.__is_black_ = true; + + std::__tree_remove(root.__left_, &c); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &b); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(a.__parent_ == &b); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == false); + + assert(b.__parent_ == &root); + assert(b.__left_ == &a); + assert(b.__right_ == 0); + assert(b.__is_black_ == true); + + std::__tree_remove(root.__left_, &b); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &a); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(a.__parent_ == &root); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == true); + + std::__tree_remove(root.__left_, &a); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == 0); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + } + { + Node root; + Node a; + Node b; + Node c; + + root.__left_ = &b; + + b.__parent_ = &root; + b.__left_ = &a; + b.__right_ = &c; + b.__is_black_ = true; + + a.__parent_ = &b; + a.__left_ = 0; + a.__right_ = 0; + a.__is_black_ = false; + + c.__parent_ = &b; + c.__left_ = 0; + c.__right_ = 0; + c.__is_black_ = false; + + std::__tree_remove(root.__left_, &c); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &b); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(a.__parent_ == &b); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == false); + + assert(b.__parent_ == &root); + assert(b.__left_ == &a); + assert(b.__right_ == 0); + assert(b.__is_black_ == true); + + std::__tree_remove(root.__left_, &b); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &a); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(a.__parent_ == &root); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == true); + + std::__tree_remove(root.__left_, &a); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == 0); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + } + { + Node root; + Node a; + Node b; + Node c; + + root.__left_ = &b; + + b.__parent_ = &root; + b.__left_ = &a; + b.__right_ = &c; + b.__is_black_ = true; + + a.__parent_ = &b; + a.__left_ = 0; + a.__right_ = 0; + a.__is_black_ = true; + + c.__parent_ = &b; + c.__left_ = 0; + c.__right_ = 0; + c.__is_black_ = true; + + std::__tree_remove(root.__left_, &c); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &b); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(a.__parent_ == &b); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == false); + + assert(b.__parent_ == &root); + assert(b.__left_ == &a); + assert(b.__right_ == 0); + assert(b.__is_black_ == true); + + std::__tree_remove(root.__left_, &a); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &b); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(b.__parent_ == &root); + assert(b.__left_ == 0); + assert(b.__right_ == 0); + assert(b.__is_black_ == true); + + std::__tree_remove(root.__left_, &b); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == 0); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + } + { + Node root; + Node a; + Node b; + Node c; + + root.__left_ = &b; + + b.__parent_ = &root; + b.__left_ = &a; + b.__right_ = &c; + b.__is_black_ = true; + + a.__parent_ = &b; + a.__left_ = 0; + a.__right_ = 0; + a.__is_black_ = false; + + c.__parent_ = &b; + c.__left_ = 0; + c.__right_ = 0; + c.__is_black_ = false; + + std::__tree_remove(root.__left_, &c); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &b); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(a.__parent_ == &b); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == false); + + assert(b.__parent_ == &root); + assert(b.__left_ == &a); + assert(b.__right_ == 0); + assert(b.__is_black_ == true); + + std::__tree_remove(root.__left_, &a); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &b); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(b.__parent_ == &root); + assert(b.__left_ == 0); + assert(b.__right_ == 0); + assert(b.__is_black_ == true); + + std::__tree_remove(root.__left_, &b); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == 0); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + } +} + +void +test3() +{ + Node root; + Node a; + Node b; + Node c; + Node d; + Node e; + Node f; + Node g; + Node h; + + root.__left_ = &e; + + e.__parent_ = &root; + e.__left_ = &c; + e.__right_ = &g; + e.__is_black_ = true; + + c.__parent_ = &e; + c.__left_ = &b; + c.__right_ = &d; + c.__is_black_ = false; + + g.__parent_ = &e; + g.__left_ = &f; + g.__right_ = &h; + g.__is_black_ = false; + + b.__parent_ = &c; + b.__left_ = &a; + b.__right_ = 0; + b.__is_black_ = true; + + d.__parent_ = &c; + d.__left_ = 0; + d.__right_ = 0; + d.__is_black_ = true; + + f.__parent_ = &g; + f.__left_ = 0; + f.__right_ = 0; + f.__is_black_ = true; + + h.__parent_ = &g; + h.__left_ = 0; + h.__right_ = 0; + h.__is_black_ = true; + + a.__parent_ = &b; + a.__left_ = 0; + a.__right_ = 0; + a.__is_black_ = false; + + assert(std::__tree_invariant(root.__left_)); + + std::__tree_remove(root.__left_, &h); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &e); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(e.__parent_ == &root); + assert(e.__left_ == &c); + assert(e.__right_ == &g); + assert(e.__is_black_ == true); + + assert(c.__parent_ == &e); + assert(c.__left_ == &b); + assert(c.__right_ == &d); + assert(c.__is_black_ == false); + + assert(g.__parent_ == &e); + assert(g.__left_ == &f); + assert(g.__right_ == 0); + assert(g.__is_black_ == true); + + assert(b.__parent_ == &c); + assert(b.__left_ == &a); + assert(b.__right_ == 0); + assert(b.__is_black_ == true); + + assert(a.__parent_ == &b); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == false); + + assert(d.__parent_ == &c); + assert(d.__left_ == 0); + assert(d.__right_ == 0); + assert(d.__is_black_ == true); + + assert(f.__parent_ == &g); + assert(f.__left_ == 0); + assert(f.__right_ == 0); + assert(f.__is_black_ == false); + + std::__tree_remove(root.__left_, &g); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &e); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(e.__parent_ == &root); + assert(e.__left_ == &c); + assert(e.__right_ == &f); + assert(e.__is_black_ == true); + + assert(c.__parent_ == &e); + assert(c.__left_ == &b); + assert(c.__right_ == &d); + assert(c.__is_black_ == false); + + assert(b.__parent_ == &c); + assert(b.__left_ == &a); + assert(b.__right_ == 0); + assert(b.__is_black_ == true); + + assert(a.__parent_ == &b); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == false); + + assert(d.__parent_ == &c); + assert(d.__left_ == 0); + assert(d.__right_ == 0); + assert(d.__is_black_ == true); + + assert(f.__parent_ == &e); + assert(f.__left_ == 0); + assert(f.__right_ == 0); + assert(f.__is_black_ == true); + + std::__tree_remove(root.__left_, &f); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &c); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(c.__parent_ == &root); + assert(c.__left_ == &b); + assert(c.__right_ == &e); + assert(c.__is_black_ == true); + + assert(b.__parent_ == &c); + assert(b.__left_ == &a); + assert(b.__right_ == 0); + assert(b.__is_black_ == true); + + assert(e.__parent_ == &c); + assert(e.__left_ == &d); + assert(e.__right_ == 0); + assert(e.__is_black_ == true); + + assert(a.__parent_ == &b); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == false); + + assert(d.__parent_ == &e); + assert(d.__left_ == 0); + assert(d.__right_ == 0); + assert(d.__is_black_ == false); + + std::__tree_remove(root.__left_, &e); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &c); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(c.__parent_ == &root); + assert(c.__left_ == &b); + assert(c.__right_ == &d); + assert(c.__is_black_ == true); + + assert(b.__parent_ == &c); + assert(b.__left_ == &a); + assert(b.__right_ == 0); + assert(b.__is_black_ == true); + + assert(a.__parent_ == &b); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == false); + + assert(d.__parent_ == &c); + assert(d.__left_ == 0); + assert(d.__right_ == 0); + assert(d.__is_black_ == true); + + std::__tree_remove(root.__left_, &d); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &b); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(b.__parent_ == &root); + assert(b.__left_ == &a); + assert(b.__right_ == &c); + assert(b.__is_black_ == true); + + assert(a.__parent_ == &b); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == true); + + assert(c.__parent_ == &b); + assert(c.__left_ == 0); + assert(c.__right_ == 0); + assert(c.__is_black_ == true); + + std::__tree_remove(root.__left_, &c); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &b); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(b.__parent_ == &root); + assert(b.__left_ == &a); + assert(b.__right_ == 0); + assert(b.__is_black_ == true); + + assert(a.__parent_ == &b); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == false); + + std::__tree_remove(root.__left_, &b); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &a); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(a.__parent_ == &root); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(a.__is_black_ == true); + + std::__tree_remove(root.__left_, &a); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == 0); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); +} + +void +test4() +{ + Node root; + Node a; + Node b; + Node c; + Node d; + Node e; + Node f; + Node g; + Node h; + + root.__left_ = &d; + + d.__parent_ = &root; + d.__left_ = &b; + d.__right_ = &f; + d.__is_black_ = true; + + b.__parent_ = &d; + b.__left_ = &a; + b.__right_ = &c; + b.__is_black_ = false; + + f.__parent_ = &d; + f.__left_ = &e; + f.__right_ = &g; + f.__is_black_ = false; + + a.__parent_ = &b; + a.__left_ = 0; + a.__right_ = 0; + a.__is_black_ = true; + + c.__parent_ = &b; + c.__left_ = 0; + c.__right_ = 0; + c.__is_black_ = true; + + e.__parent_ = &f; + e.__left_ = 0; + e.__right_ = 0; + e.__is_black_ = true; + + g.__parent_ = &f; + g.__left_ = 0; + g.__right_ = &h; + g.__is_black_ = true; + + h.__parent_ = &g; + h.__left_ = 0; + h.__right_ = 0; + h.__is_black_ = false; + + assert(std::__tree_invariant(root.__left_)); + + std::__tree_remove(root.__left_, &a); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &d); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(d.__parent_ == &root); + assert(d.__left_ == &b); + assert(d.__right_ == &f); + assert(d.__is_black_ == true); + + assert(b.__parent_ == &d); + assert(b.__left_ == 0); + assert(b.__right_ == &c); + assert(b.__is_black_ == true); + + assert(f.__parent_ == &d); + assert(f.__left_ == &e); + assert(f.__right_ == &g); + assert(f.__is_black_ == false); + + assert(c.__parent_ == &b); + assert(c.__left_ == 0); + assert(c.__right_ == 0); + assert(c.__is_black_ == false); + + assert(e.__parent_ == &f); + assert(e.__left_ == 0); + assert(e.__right_ == 0); + assert(e.__is_black_ == true); + + assert(g.__parent_ == &f); + assert(g.__left_ == 0); + assert(g.__right_ == &h); + assert(g.__is_black_ == true); + + assert(h.__parent_ == &g); + assert(h.__left_ == 0); + assert(h.__right_ == 0); + assert(h.__is_black_ == false); + + std::__tree_remove(root.__left_, &b); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &d); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(d.__parent_ == &root); + assert(d.__left_ == &c); + assert(d.__right_ == &f); + assert(d.__is_black_ == true); + + assert(c.__parent_ == &d); + assert(c.__left_ == 0); + assert(c.__right_ == 0); + assert(c.__is_black_ == true); + + assert(f.__parent_ == &d); + assert(f.__left_ == &e); + assert(f.__right_ == &g); + assert(f.__is_black_ == false); + + assert(e.__parent_ == &f); + assert(e.__left_ == 0); + assert(e.__right_ == 0); + assert(e.__is_black_ == true); + + assert(g.__parent_ == &f); + assert(g.__left_ == 0); + assert(g.__right_ == &h); + assert(g.__is_black_ == true); + + assert(h.__parent_ == &g); + assert(h.__left_ == 0); + assert(h.__right_ == 0); + assert(h.__is_black_ == false); + + std::__tree_remove(root.__left_, &c); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &f); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(f.__parent_ == &root); + assert(f.__left_ == &d); + assert(f.__right_ == &g); + assert(f.__is_black_ == true); + + assert(d.__parent_ == &f); + assert(d.__left_ == 0); + assert(d.__right_ == &e); + assert(d.__is_black_ == true); + + assert(g.__parent_ == &f); + assert(g.__left_ == 0); + assert(g.__right_ == &h); + assert(g.__is_black_ == true); + + assert(e.__parent_ == &d); + assert(e.__left_ == 0); + assert(e.__right_ == 0); + assert(e.__is_black_ == false); + + assert(h.__parent_ == &g); + assert(h.__left_ == 0); + assert(h.__right_ == 0); + assert(h.__is_black_ == false); + + std::__tree_remove(root.__left_, &d); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &f); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(f.__parent_ == &root); + assert(f.__left_ == &e); + assert(f.__right_ == &g); + assert(f.__is_black_ == true); + + assert(e.__parent_ == &f); + assert(e.__left_ == 0); + assert(e.__right_ == 0); + assert(e.__is_black_ == true); + + assert(g.__parent_ == &f); + assert(g.__left_ == 0); + assert(g.__right_ == &h); + assert(g.__is_black_ == true); + + assert(h.__parent_ == &g); + assert(h.__left_ == 0); + assert(h.__right_ == 0); + assert(h.__is_black_ == false); + + std::__tree_remove(root.__left_, &e); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &g); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(g.__parent_ == &root); + assert(g.__left_ == &f); + assert(g.__right_ == &h); + assert(g.__is_black_ == true); + + assert(f.__parent_ == &g); + assert(f.__left_ == 0); + assert(f.__right_ == 0); + assert(f.__is_black_ == true); + + assert(h.__parent_ == &g); + assert(h.__left_ == 0); + assert(h.__right_ == 0); + assert(h.__is_black_ == true); + + std::__tree_remove(root.__left_, &f); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &g); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(g.__parent_ == &root); + assert(g.__left_ == 0); + assert(g.__right_ == &h); + assert(g.__is_black_ == true); + + assert(h.__parent_ == &g); + assert(h.__left_ == 0); + assert(h.__right_ == 0); + assert(h.__is_black_ == false); + + std::__tree_remove(root.__left_, &g); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == &h); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); + + assert(h.__parent_ == &root); + assert(h.__left_ == 0); + assert(h.__right_ == 0); + assert(h.__is_black_ == true); + + std::__tree_remove(root.__left_, &h); + + assert(std::__tree_invariant(root.__left_)); + + assert(root.__parent_ == 0); + assert(root.__left_ == 0); + assert(root.__right_ == 0); + assert(root.__is_black_ == false); +} + +int main() +{ + test1(); + test2(); + test3(); + test4(); +} diff --git a/test/libcxx/containers/associative/tree_right_rotate.pass.cpp b/test/libcxx/containers/associative/tree_right_rotate.pass.cpp new file mode 100644 index 0000000000000..9355a46b4e2b7 --- /dev/null +++ b/test/libcxx/containers/associative/tree_right_rotate.pass.cpp @@ -0,0 +1,101 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// Not a portable test + +// Precondition: __x->__left_ != nullptr +// template <class _NodePtr> +// void +// __tree_right_rotate(_NodePtr __x); + +#include <__tree> +#include <cassert> + +struct Node +{ + Node* __left_; + Node* __right_; + Node* __parent_; + + Node* __parent_unsafe() const { return __parent_; } + void __set_parent(Node* x) { __parent_ = x;} + + Node() : __left_(), __right_(), __parent_() {} +}; + +void +test1() +{ + Node root; + Node x; + Node y; + root.__left_ = &x; + x.__left_ = &y; + x.__right_ = 0; + x.__parent_ = &root; + y.__left_ = 0; + y.__right_ = 0; + y.__parent_ = &x; + std::__tree_right_rotate(&x); + assert(root.__parent_ == 0); + assert(root.__left_ == &y); + assert(root.__right_ == 0); + assert(y.__parent_ == &root); + assert(y.__left_ == 0); + assert(y.__right_ == &x); + assert(x.__parent_ == &y); + assert(x.__left_ == 0); + assert(x.__right_ == 0); +} + +void +test2() +{ + Node root; + Node x; + Node y; + Node a; + Node b; + Node c; + root.__left_ = &x; + x.__left_ = &y; + x.__right_ = &c; + x.__parent_ = &root; + y.__left_ = &a; + y.__right_ = &b; + y.__parent_ = &x; + a.__parent_ = &y; + b.__parent_ = &y; + c.__parent_ = &x; + std::__tree_right_rotate(&x); + assert(root.__parent_ == 0); + assert(root.__left_ == &y); + assert(root.__right_ == 0); + assert(y.__parent_ == &root); + assert(y.__left_ == &a); + assert(y.__right_ == &x); + assert(x.__parent_ == &y); + assert(x.__left_ == &b); + assert(x.__right_ == &c); + assert(a.__parent_ == &y); + assert(a.__left_ == 0); + assert(a.__right_ == 0); + assert(b.__parent_ == &x); + assert(b.__left_ == 0); + assert(b.__right_ == 0); + assert(c.__parent_ == &x); + assert(c.__left_ == 0); + assert(c.__right_ == 0); +} + +int main() +{ + test1(); + test2(); +} diff --git a/test/libcxx/containers/container.adaptors/queue/version.pass.cpp b/test/libcxx/containers/container.adaptors/queue/version.pass.cpp new file mode 100644 index 0000000000000..35b94b33c517d --- /dev/null +++ b/test/libcxx/containers/container.adaptors/queue/version.pass.cpp @@ -0,0 +1,20 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <queue> + +#include <queue> + +#ifndef _LIBCPP_VERSION +#error _LIBCPP_VERSION not defined +#endif + +int main() +{ +} diff --git a/test/libcxx/containers/container.adaptors/stack/version.pass.cpp b/test/libcxx/containers/container.adaptors/stack/version.pass.cpp new file mode 100644 index 0000000000000..339d0f4dda8f7 --- /dev/null +++ b/test/libcxx/containers/container.adaptors/stack/version.pass.cpp @@ -0,0 +1,20 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <stack> + +#include <stack> + +#ifndef _LIBCPP_VERSION +#error _LIBCPP_VERSION not defined +#endif + +int main() +{ +} diff --git a/test/libcxx/containers/gnu_cxx/hash_map.pass.cpp b/test/libcxx/containers/gnu_cxx/hash_map.pass.cpp new file mode 100644 index 0000000000000..0d9115d0f6938 --- /dev/null +++ b/test/libcxx/containers/gnu_cxx/hash_map.pass.cpp @@ -0,0 +1,26 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// Prevent emission of the deprecated warning. +#ifdef __clang__ +#pragma clang diagnostic ignored "-W#warnings" +#endif + +#include <ext/hash_map> + +namespace __gnu_cxx { +template class hash_map<int, int>; +} + +int main() { + typedef __gnu_cxx::hash_map<int, int> Map; + Map m; + Map m2(m); + ((void)m2); +} diff --git a/test/libcxx/containers/gnu_cxx/hash_set.pass.cpp b/test/libcxx/containers/gnu_cxx/hash_set.pass.cpp new file mode 100644 index 0000000000000..5fd4bde66e0ac --- /dev/null +++ b/test/libcxx/containers/gnu_cxx/hash_set.pass.cpp @@ -0,0 +1,26 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// Prevent emission of the deprecated warning. +#ifdef __clang__ +#pragma clang diagnostic ignored "-W#warnings" +#endif + +#include <ext/hash_set> + +namespace __gnu_cxx { +template class hash_set<int>; +} + +int main() { + typedef __gnu_cxx::hash_set<int> Set; + Set s; + Set s2(s); + ((void)s2); +} diff --git a/test/libcxx/containers/sequences/array/version.pass.cpp b/test/libcxx/containers/sequences/array/version.pass.cpp new file mode 100644 index 0000000000000..b89a8dd8cca3b --- /dev/null +++ b/test/libcxx/containers/sequences/array/version.pass.cpp @@ -0,0 +1,20 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <array> + +#include <array> + +#ifndef _LIBCPP_VERSION +#error _LIBCPP_VERSION not defined +#endif + +int main() +{ +} diff --git a/test/libcxx/containers/sequences/deque/version.pass.cpp b/test/libcxx/containers/sequences/deque/version.pass.cpp new file mode 100644 index 0000000000000..22e663d9bc227 --- /dev/null +++ b/test/libcxx/containers/sequences/deque/version.pass.cpp @@ -0,0 +1,20 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <deque> + +#include <deque> + +#ifndef _LIBCPP_VERSION +#error _LIBCPP_VERSION not defined +#endif + +int main() +{ +} diff --git a/test/libcxx/containers/sequences/forwardlist/version.pass.cpp b/test/libcxx/containers/sequences/forwardlist/version.pass.cpp new file mode 100644 index 0000000000000..918c8dd5d73cd --- /dev/null +++ b/test/libcxx/containers/sequences/forwardlist/version.pass.cpp @@ -0,0 +1,20 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <forward_list> + +#include <forward_list> + +#ifndef _LIBCPP_VERSION +#error _LIBCPP_VERSION not defined +#endif + +int main() +{ +} diff --git a/test/libcxx/containers/sequences/list/db_back.pass.cpp b/test/libcxx/containers/sequences/list/db_back.pass.cpp new file mode 100644 index 0000000000000..96dfd2d8d2ecd --- /dev/null +++ b/test/libcxx/containers/sequences/list/db_back.pass.cpp @@ -0,0 +1,32 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <list> + +// Call back() on empty container. + +#define _LIBCPP_DEBUG 1 +#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0)) + +#include <list> +#include <cassert> +#include <iterator> +#include <exception> +#include <cstdlib> + +int main() +{ + typedef int T; + typedef std::list<T> C; + C c(1); + assert(c.back() == 0); + c.clear(); + assert(c.back() == 0); + assert(false); +} diff --git a/test/libcxx/containers/sequences/list/db_cback.pass.cpp b/test/libcxx/containers/sequences/list/db_cback.pass.cpp new file mode 100644 index 0000000000000..1e25307c4602b --- /dev/null +++ b/test/libcxx/containers/sequences/list/db_cback.pass.cpp @@ -0,0 +1,30 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <list> + +// Call back() on empty const container. + +#define _LIBCPP_DEBUG 1 +#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0)) + +#include <list> +#include <cassert> +#include <iterator> +#include <exception> +#include <cstdlib> + +int main() +{ + typedef int T; + typedef std::list<T> C; + const C c; + assert(c.back() == 0); + assert(false); +} diff --git a/test/libcxx/containers/sequences/list/db_cfront.pass.cpp b/test/libcxx/containers/sequences/list/db_cfront.pass.cpp new file mode 100644 index 0000000000000..9501ce1931382 --- /dev/null +++ b/test/libcxx/containers/sequences/list/db_cfront.pass.cpp @@ -0,0 +1,30 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <list> + +// Call front() on empty const container. + +#define _LIBCPP_DEBUG 1 +#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0)) + +#include <list> +#include <cassert> +#include <iterator> +#include <exception> +#include <cstdlib> + +int main() +{ + typedef int T; + typedef std::list<T> C; + const C c; + assert(c.front() == 0); + assert(false); +} diff --git a/test/libcxx/containers/sequences/list/db_front.pass.cpp b/test/libcxx/containers/sequences/list/db_front.pass.cpp new file mode 100644 index 0000000000000..fc02895a8912c --- /dev/null +++ b/test/libcxx/containers/sequences/list/db_front.pass.cpp @@ -0,0 +1,32 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <list> + +// Call front() on empty container. + +#define _LIBCPP_DEBUG 1 +#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0)) + +#include <list> +#include <cassert> +#include <iterator> +#include <exception> +#include <cstdlib> + +int main() +{ + typedef int T; + typedef std::list<T> C; + C c(1); + assert(c.front() == 0); + c.clear(); + assert(c.front() == 0); + assert(false); +} diff --git a/test/libcxx/containers/sequences/list/db_iterators_6.pass.cpp b/test/libcxx/containers/sequences/list/db_iterators_6.pass.cpp new file mode 100644 index 0000000000000..3f0fd015e9a4d --- /dev/null +++ b/test/libcxx/containers/sequences/list/db_iterators_6.pass.cpp @@ -0,0 +1,33 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <list> + +// Decrement iterator prior to begin. + +#define _LIBCPP_DEBUG 1 +#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0)) + +#include <list> +#include <cassert> +#include <iterator> +#include <exception> +#include <cstdlib> + +int main() +{ + typedef int T; + typedef std::list<T> C; + C c(1); + C::iterator i = c.end(); + --i; + assert(i == c.begin()); + --i; + assert(false); +} diff --git a/test/libcxx/containers/sequences/list/db_iterators_7.pass.cpp b/test/libcxx/containers/sequences/list/db_iterators_7.pass.cpp new file mode 100644 index 0000000000000..bc2b7f4e1da21 --- /dev/null +++ b/test/libcxx/containers/sequences/list/db_iterators_7.pass.cpp @@ -0,0 +1,33 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <list> + +// Increment iterator past end. + +#define _LIBCPP_DEBUG 1 +#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0)) + +#include <list> +#include <cassert> +#include <iterator> +#include <exception> +#include <cstdlib> + +int main() +{ + typedef int T; + typedef std::list<T> C; + C c(1); + C::iterator i = c.begin(); + ++i; + assert(i == c.end()); + ++i; + assert(false); +} diff --git a/test/libcxx/containers/sequences/list/db_iterators_8.pass.cpp b/test/libcxx/containers/sequences/list/db_iterators_8.pass.cpp new file mode 100644 index 0000000000000..08c10d34a01ee --- /dev/null +++ b/test/libcxx/containers/sequences/list/db_iterators_8.pass.cpp @@ -0,0 +1,31 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <list> + +// Dereference non-dereferenceable iterator. + +#define _LIBCPP_DEBUG 1 +#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0)) + +#include <list> +#include <cassert> +#include <iterator> +#include <exception> +#include <cstdlib> + +int main() +{ + typedef int T; + typedef std::list<T> C; + C c(1); + C::iterator i = c.end(); + T j = *i; + assert(false); +} diff --git a/test/libcxx/containers/sequences/list/db_iterators_9.pass.cpp b/test/libcxx/containers/sequences/list/db_iterators_9.pass.cpp new file mode 100644 index 0000000000000..e2b95d8b16647 --- /dev/null +++ b/test/libcxx/containers/sequences/list/db_iterators_9.pass.cpp @@ -0,0 +1,59 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++98, c++03 +// UNSUPPORTED: libcpp-no-exceptions + +// <list> + +// Operations on "NULL" iterators + +#define _LIBCPP_DEBUG 1 +#define _LIBCPP_ASSERT(x, m) do { if (!x) throw 1; } while(0) + +#include <list> +#include <cassert> +#include <iterator> +#include <exception> +#include <cstdlib> + +struct S { int val; }; + +int main() +{ + { + unsigned lib_asserts; + + typedef S T; + typedef std::list<T> C; + C::iterator i{}; + C::const_iterator ci{}; + + lib_asserts = 0; + try { ++i; } catch (int) { ++lib_asserts; } + try { i++; } catch (int) { ++lib_asserts; } + try { ++ci; } catch (int) { ++lib_asserts; } + try { ci++; } catch (int) { ++lib_asserts; } + assert(lib_asserts == 4); + + lib_asserts = 0; + try { --i; } catch (int) { ++lib_asserts; } + try { i--; } catch (int) { ++lib_asserts; } + try { --ci; } catch (int) { ++lib_asserts; } + try { ci--; } catch (int) { ++lib_asserts; } + assert(lib_asserts == 4); + + lib_asserts = 0; + try { *i; } catch (int) { ++lib_asserts; } + try { *ci; } catch (int) { ++lib_asserts; } + try { (void) i->val; } catch (int) { ++lib_asserts; } + try { (void) ci->val; } catch (int) { ++lib_asserts; } + assert(lib_asserts == 4); + } +} diff --git a/test/libcxx/containers/sequences/list/list.cons/db_copy.pass.cpp b/test/libcxx/containers/sequences/list/list.cons/db_copy.pass.cpp new file mode 100644 index 0000000000000..c84960f37686f --- /dev/null +++ b/test/libcxx/containers/sequences/list/list.cons/db_copy.pass.cpp @@ -0,0 +1,29 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <list> + +// list(list&& c); + +#define _LIBCPP_DEBUG 1 +#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0)) + +#include <list> +#include <cstdlib> +#include <cassert> + +int main() +{ + std::list<int> l1; + l1.push_back(1); l1.push_back(2); l1.push_back(3); + std::list<int>::iterator i = l1.begin(); + std::list<int> l2 = l1; + l2.erase(i); + assert(false); +} diff --git a/test/libcxx/containers/sequences/list/list.cons/db_move.pass.cpp b/test/libcxx/containers/sequences/list/list.cons/db_move.pass.cpp new file mode 100644 index 0000000000000..dd424e89e7568 --- /dev/null +++ b/test/libcxx/containers/sequences/list/list.cons/db_move.pass.cpp @@ -0,0 +1,32 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++98, c++03 + +// <list> + +// list(list&& c); + +#define _LIBCPP_DEBUG 1 +#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(1)) + +#include <list> +#include <cstdlib> +#include <cassert> +#include "MoveOnly.h" +#include "test_allocator.h" +#include "min_allocator.h" + +int main() +{ + std::list<int> l1 = {1, 2, 3}; + std::list<int>::iterator i = l1.begin(); + std::list<int> l2 = std::move(l1); + assert(*l2.erase(i) == 2); +} diff --git a/test/libcxx/containers/sequences/list/list.modifiers/emplace_db1.pass.cpp b/test/libcxx/containers/sequences/list/list.modifiers/emplace_db1.pass.cpp new file mode 100644 index 0000000000000..1d64f9bd9e275 --- /dev/null +++ b/test/libcxx/containers/sequences/list/list.modifiers/emplace_db1.pass.cpp @@ -0,0 +1,44 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++98, c++03 + +// <list> + +// template <class... Args> void emplace(const_iterator p, Args&&... args); + +#define _LIBCPP_DEBUG 1 +#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0)) + +#include <list> +#include <cstdlib> +#include <cassert> + +class A +{ + int i_; + double d_; + + A(const A&); + A& operator=(const A&); +public: + A(int i, double d) + : i_(i), d_(d) {} + + int geti() const {return i_;} + double getd() const {return d_;} +}; + +int main() +{ + std::list<A> c1; + std::list<A> c2; + std::list<A>::iterator i = c1.emplace(c2.cbegin(), 2, 3.5); + assert(false); +} diff --git a/test/libcxx/containers/sequences/list/list.modifiers/erase_iter_db1.pass.cpp b/test/libcxx/containers/sequences/list/list.modifiers/erase_iter_db1.pass.cpp new file mode 100644 index 0000000000000..ec5de0264cb47 --- /dev/null +++ b/test/libcxx/containers/sequences/list/list.modifiers/erase_iter_db1.pass.cpp @@ -0,0 +1,28 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <list> + +// Call erase(const_iterator position) with end() + +#define _LIBCPP_DEBUG 1 +#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0)) + +#include <list> +#include <cassert> +#include <cstdlib> + +int main() +{ + int a1[] = {1, 2, 3}; + std::list<int> l1(a1, a1+3); + std::list<int>::const_iterator i = l1.end(); + l1.erase(i); + assert(false); +} diff --git a/test/libcxx/containers/sequences/list/list.modifiers/erase_iter_db2.pass.cpp b/test/libcxx/containers/sequences/list/list.modifiers/erase_iter_db2.pass.cpp new file mode 100644 index 0000000000000..833e2b54dfaf1 --- /dev/null +++ b/test/libcxx/containers/sequences/list/list.modifiers/erase_iter_db2.pass.cpp @@ -0,0 +1,29 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <list> + +// Call erase(const_iterator position) with iterator from another container + +#define _LIBCPP_DEBUG 1 +#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0)) + +#include <list> +#include <cassert> +#include <cstdlib> + +int main() +{ + int a1[] = {1, 2, 3}; + std::list<int> l1(a1, a1+3); + std::list<int> l2(a1, a1+3); + std::list<int>::const_iterator i = l2.begin(); + l1.erase(i); + assert(false); +} diff --git a/test/libcxx/containers/sequences/list/list.modifiers/erase_iter_iter_db1.pass.cpp b/test/libcxx/containers/sequences/list/list.modifiers/erase_iter_iter_db1.pass.cpp new file mode 100644 index 0000000000000..eef7a98e739a9 --- /dev/null +++ b/test/libcxx/containers/sequences/list/list.modifiers/erase_iter_iter_db1.pass.cpp @@ -0,0 +1,29 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <list> + +// Call erase(const_iterator first, const_iterator last); with first iterator from another container + +#define _LIBCPP_DEBUG 1 +#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0)) + +#include <list> +#include <cassert> +#include <cstdlib> + +int main() +{ + int a1[] = {1, 2, 3}; + std::list<int> l1(a1, a1+3); + std::list<int> l2(a1, a1+3); + std::list<int>::iterator i = l1.erase(l2.cbegin(), next(l1.cbegin())); + assert(false); +} + diff --git a/test/libcxx/containers/sequences/list/list.modifiers/erase_iter_iter_db2.pass.cpp b/test/libcxx/containers/sequences/list/list.modifiers/erase_iter_iter_db2.pass.cpp new file mode 100644 index 0000000000000..0dd03dc50da1b --- /dev/null +++ b/test/libcxx/containers/sequences/list/list.modifiers/erase_iter_iter_db2.pass.cpp @@ -0,0 +1,28 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <list> + +// Call erase(const_iterator first, const_iterator last); with second iterator from another container + +#define _LIBCPP_DEBUG 1 +#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0)) + +#include <list> +#include <cassert> +#include <cstdlib> + +int main() +{ + int a1[] = {1, 2, 3}; + std::list<int> l1(a1, a1+3); + std::list<int> l2(a1, a1+3); + std::list<int>::iterator i = l1.erase(l1.cbegin(), next(l2.cbegin())); + assert(false); +} diff --git a/test/libcxx/containers/sequences/list/list.modifiers/erase_iter_iter_db3.pass.cpp b/test/libcxx/containers/sequences/list/list.modifiers/erase_iter_iter_db3.pass.cpp new file mode 100644 index 0000000000000..22273a89f1e55 --- /dev/null +++ b/test/libcxx/containers/sequences/list/list.modifiers/erase_iter_iter_db3.pass.cpp @@ -0,0 +1,28 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <list> + +// Call erase(const_iterator first, const_iterator last); with both iterators from another container + +#define _LIBCPP_DEBUG 1 +#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0)) + +#include <list> +#include <cassert> +#include <cstdlib> + +int main() +{ + int a1[] = {1, 2, 3}; + std::list<int> l1(a1, a1+3); + std::list<int> l2(a1, a1+3); + std::list<int>::iterator i = l1.erase(l2.cbegin(), next(l2.cbegin())); + assert(false); +} diff --git a/test/libcxx/containers/sequences/list/list.modifiers/erase_iter_iter_db4.pass.cpp b/test/libcxx/containers/sequences/list/list.modifiers/erase_iter_iter_db4.pass.cpp new file mode 100644 index 0000000000000..d1e03c8ac7109 --- /dev/null +++ b/test/libcxx/containers/sequences/list/list.modifiers/erase_iter_iter_db4.pass.cpp @@ -0,0 +1,27 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <list> + +// Call erase(const_iterator first, const_iterator last); with a bad range + +#define _LIBCPP_DEBUG 1 +#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0)) + +#include <list> +#include <cassert> +#include <cstdlib> + +int main() +{ + int a1[] = {1, 2, 3}; + std::list<int> l1(a1, a1+3); + std::list<int>::iterator i = l1.erase(next(l1.cbegin()), l1.cbegin()); + assert(false); +} diff --git a/test/libcxx/containers/sequences/list/list.modifiers/insert_iter_iter_iter_db1.pass.cpp b/test/libcxx/containers/sequences/list/list.modifiers/insert_iter_iter_iter_db1.pass.cpp new file mode 100644 index 0000000000000..7fadb14affdda --- /dev/null +++ b/test/libcxx/containers/sequences/list/list.modifiers/insert_iter_iter_iter_db1.pass.cpp @@ -0,0 +1,36 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <list> + +// template <InputIterator Iter> +// iterator insert(const_iterator position, Iter first, Iter last); + + +#define _LIBCPP_DEBUG 1 +#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0)) + +#include <list> +#include <cstdlib> +#include <cassert> +#include "test_iterators.h" + +int main() +{ + { + std::list<int> v(100); + std::list<int> v2(100); + int a[] = {1, 2, 3, 4, 5}; + const int N = sizeof(a)/sizeof(a[0]); + std::list<int>::iterator i = v.insert(next(v2.cbegin(), 10), + input_iterator<const int*>(a), + input_iterator<const int*>(a+N)); + assert(false); + } +} diff --git a/test/libcxx/containers/sequences/list/list.modifiers/insert_iter_rvalue_db1.pass.cpp b/test/libcxx/containers/sequences/list/list.modifiers/insert_iter_rvalue_db1.pass.cpp new file mode 100644 index 0000000000000..0d0fd100fc91b --- /dev/null +++ b/test/libcxx/containers/sequences/list/list.modifiers/insert_iter_rvalue_db1.pass.cpp @@ -0,0 +1,27 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <list> + +// iterator insert(const_iterator position, value_type&& x); + +#define _LIBCPP_DEBUG 1 +#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0)) + +#include <list> +#include <cstdlib> +#include <cassert> + +int main() +{ + std::list<int> v1(3); + std::list<int> v2(3); + v1.insert(v2.begin(), 4); + assert(false); +}
\ No newline at end of file diff --git a/test/libcxx/containers/sequences/list/list.modifiers/insert_iter_size_value_db1.pass.cpp b/test/libcxx/containers/sequences/list/list.modifiers/insert_iter_size_value_db1.pass.cpp new file mode 100644 index 0000000000000..4fdfbfa50cbbb --- /dev/null +++ b/test/libcxx/containers/sequences/list/list.modifiers/insert_iter_size_value_db1.pass.cpp @@ -0,0 +1,27 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <list> + +// iterator insert(const_iterator position, size_type n, const value_type& x); + +#define _LIBCPP_DEBUG 1 +#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0)) + +#include <list> +#include <cstdlib> +#include <cassert> + +int main() +{ + std::list<int> c1(100); + std::list<int> c2; + std::list<int>::iterator i = c1.insert(next(c2.cbegin(), 10), 5, 1); + assert(false); +} diff --git a/test/libcxx/containers/sequences/list/list.modifiers/insert_iter_value_db1.pass.cpp b/test/libcxx/containers/sequences/list/list.modifiers/insert_iter_value_db1.pass.cpp new file mode 100644 index 0000000000000..9a13520b98eb2 --- /dev/null +++ b/test/libcxx/containers/sequences/list/list.modifiers/insert_iter_value_db1.pass.cpp @@ -0,0 +1,29 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <list> + +// iterator insert(const_iterator position, const value_type& x); + +#define _LIBCPP_DEBUG 1 +#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0)) + +#include <list> +#include <cstdlib> +#include <cassert> + + +int main() +{ + std::list<int> v1(3); + std::list<int> v2(3); + int i = 4; + v1.insert(v2.begin(), i); + assert(false); +} diff --git a/test/libcxx/containers/sequences/list/list.modifiers/pop_back_db1.pass.cpp b/test/libcxx/containers/sequences/list/list.modifiers/pop_back_db1.pass.cpp new file mode 100644 index 0000000000000..795e66d9702a8 --- /dev/null +++ b/test/libcxx/containers/sequences/list/list.modifiers/pop_back_db1.pass.cpp @@ -0,0 +1,33 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <list> + +// void pop_back(); + +#define _LIBCPP_DEBUG 1 +#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0)) + +#include <list> +#include <cstdlib> +#include <cassert> + +int main() +{ + int a[] = {1, 2, 3}; + std::list<int> c(a, a+3); + c.pop_back(); + assert(c == std::list<int>(a, a+2)); + c.pop_back(); + assert(c == std::list<int>(a, a+1)); + c.pop_back(); + assert(c.empty()); + c.pop_back(); // operation under test + assert(false); +} diff --git a/test/libcxx/containers/sequences/list/list.ops/db_splice_pos_list.pass.cpp b/test/libcxx/containers/sequences/list/list.ops/db_splice_pos_list.pass.cpp new file mode 100644 index 0000000000000..7a1180a9b5857 --- /dev/null +++ b/test/libcxx/containers/sequences/list/list.ops/db_splice_pos_list.pass.cpp @@ -0,0 +1,29 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <list> + +// void splice(const_iterator position, list& x); + +#define _LIBCPP_DEBUG 1 +#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0)) + +#include <list> +#include <cstdlib> +#include <cassert> + +int main() +{ + { + std::list<int> v1(3); + std::list<int> v2(3); + v1.splice(v2.begin(), v2); + assert(false); + } +} diff --git a/test/libcxx/containers/sequences/list/list.ops/db_splice_pos_list_iter.pass.cpp b/test/libcxx/containers/sequences/list/list.ops/db_splice_pos_list_iter.pass.cpp new file mode 100644 index 0000000000000..fa5243e322bfd --- /dev/null +++ b/test/libcxx/containers/sequences/list/list.ops/db_splice_pos_list_iter.pass.cpp @@ -0,0 +1,29 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <list> + +// void splice(const_iterator position, list<T,Allocator>& x, iterator i); + +#define _LIBCPP_DEBUG 1 +#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0)) + +#include <list> +#include <cstdlib> +#include <cassert> + +int main() +{ + { + std::list<int> v1(3); + std::list<int> v2(3); + v1.splice(v1.begin(), v2, v1.begin()); + assert(false); + } +} diff --git a/test/libcxx/containers/sequences/list/list.ops/db_splice_pos_list_iter_iter.pass.cpp b/test/libcxx/containers/sequences/list/list.ops/db_splice_pos_list_iter_iter.pass.cpp new file mode 100644 index 0000000000000..a385b4cf7afa4 --- /dev/null +++ b/test/libcxx/containers/sequences/list/list.ops/db_splice_pos_list_iter_iter.pass.cpp @@ -0,0 +1,29 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <list> + +// void splice(const_iterator position, list& x, iterator first, iterator last); + +#define _LIBCPP_DEBUG 1 +#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0)) + +#include <list> +#include <cstdlib> +#include <cassert> + +int main() +{ + { + std::list<int> v1(3); + std::list<int> v2(3); + v1.splice(v1.begin(), v2, v2.begin(), v1.end()); + assert(false); + } +} diff --git a/test/libcxx/containers/sequences/list/list.special/db_swap_1.pass.cpp b/test/libcxx/containers/sequences/list/list.special/db_swap_1.pass.cpp new file mode 100644 index 0000000000000..900f338c29eb4 --- /dev/null +++ b/test/libcxx/containers/sequences/list/list.special/db_swap_1.pass.cpp @@ -0,0 +1,36 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <list> + +// template <class T, class Alloc> +// void swap(list<T,Alloc>& x, list<T,Alloc>& y); + +#define _LIBCPP_DEBUG 1 +#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0)) + +#include <list> +#include <cstdlib> +#include <cassert> + +int main() +{ + int a1[] = {1, 3, 7, 9, 10}; + int a2[] = {0, 2, 4, 5, 6, 8, 11}; + std::list<int> c1(a1, a1+sizeof(a1)/sizeof(a1[0])); + std::list<int> c2(a2, a2+sizeof(a2)/sizeof(a2[0])); + std::list<int>::iterator i1 = c1.begin(); + std::list<int>::iterator i2 = c2.begin(); + swap(c1, c2); + c1.erase(i2); + c2.erase(i1); + std::list<int>::iterator j = i1; + c1.erase(i1); // called with iterator not refering to list. + assert(false); +} diff --git a/test/libcxx/containers/sequences/list/list.special/db_swap_2.pass.cpp b/test/libcxx/containers/sequences/list/list.special/db_swap_2.pass.cpp new file mode 100644 index 0000000000000..ace9a713aae78 --- /dev/null +++ b/test/libcxx/containers/sequences/list/list.special/db_swap_2.pass.cpp @@ -0,0 +1,36 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <list> + +// template <class T, class Alloc> +// void swap(list<T,Alloc>& x, list<T,Alloc>& y); + + +#define _LIBCPP_DEBUG 1 +#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0)) + +#include <list> +#include <cassert> +#include "test_allocator.h" +#include "min_allocator.h" + +int main() +{ + // allocators do not compare equal + { + int a1[] = {1, 3, 7, 9, 10}; + int a2[] = {0, 2, 4, 5, 6, 8, 11}; + typedef test_allocator<int> A; + std::list<int, A> c1(a1, a1+sizeof(a1)/sizeof(a1[0]), A(1)); + std::list<int, A> c2(a2, a2+sizeof(a2)/sizeof(a2[0]), A(2)); + swap(c1, c2); + assert(false); + } +} diff --git a/test/libcxx/containers/sequences/list/version.pass.cpp b/test/libcxx/containers/sequences/list/version.pass.cpp new file mode 100644 index 0000000000000..097c013f52cb8 --- /dev/null +++ b/test/libcxx/containers/sequences/list/version.pass.cpp @@ -0,0 +1,20 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <list> + +#include <list> + +#ifndef _LIBCPP_VERSION +#error _LIBCPP_VERSION not defined +#endif + +int main() +{ +} diff --git a/test/libcxx/containers/sequences/vector/const_value_type.pass.cpp b/test/libcxx/containers/sequences/vector/const_value_type.pass.cpp new file mode 100644 index 0000000000000..2a150f7cce542 --- /dev/null +++ b/test/libcxx/containers/sequences/vector/const_value_type.pass.cpp @@ -0,0 +1,22 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++98, c++03 + +// <vector> + +// vector<const int> v; // an extension + +#include <vector> +#include <type_traits> + +int main() +{ + std::vector<const int> v = {1, 2, 3}; +} diff --git a/test/libcxx/containers/sequences/vector/db_back.pass.cpp b/test/libcxx/containers/sequences/vector/db_back.pass.cpp new file mode 100644 index 0000000000000..05f3d07712eb5 --- /dev/null +++ b/test/libcxx/containers/sequences/vector/db_back.pass.cpp @@ -0,0 +1,56 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <vector> + +// Call back() on empty container. + +#if _LIBCPP_DEBUG >= 1 + +#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0)) + +#include <vector> +#include <cassert> +#include <iterator> +#include <exception> +#include <cstdlib> + +#include "min_allocator.h" + +int main() +{ + { + typedef int T; + typedef std::vector<T> C; + C c(1); + assert(c.back() == 0); + c.clear(); + assert(c.back() == 0); + assert(false); + } +#if __cplusplus >= 201103L + { + typedef int T; + typedef std::vector<T, min_allocator<T>> C; + C c(1); + assert(c.back() == 0); + c.clear(); + assert(c.back() == 0); + assert(false); + } +#endif +} + +#else + +int main() +{ +} + +#endif diff --git a/test/libcxx/containers/sequences/vector/db_cback.pass.cpp b/test/libcxx/containers/sequences/vector/db_cback.pass.cpp new file mode 100644 index 0000000000000..5eb1a353e8b04 --- /dev/null +++ b/test/libcxx/containers/sequences/vector/db_cback.pass.cpp @@ -0,0 +1,52 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <vector> + +// Call back() on empty const container. + +#if _LIBCPP_DEBUG >= 1 + +#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0)) + +#include <vector> +#include <cassert> +#include <iterator> +#include <exception> +#include <cstdlib> + +#include "min_allocator.h" + +int main() +{ + { + typedef int T; + typedef std::vector<T> C; + const C c; + assert(c.back() == 0); + assert(false); + } +#if __cplusplus >= 201103L + { + typedef int T; + typedef std::vector<T, min_allocator<T>> C; + const C c; + assert(c.back() == 0); + assert(false); + } +#endif +} + +#else + +int main() +{ +} + +#endif diff --git a/test/libcxx/containers/sequences/vector/db_cfront.pass.cpp b/test/libcxx/containers/sequences/vector/db_cfront.pass.cpp new file mode 100644 index 0000000000000..5e54da1d444e9 --- /dev/null +++ b/test/libcxx/containers/sequences/vector/db_cfront.pass.cpp @@ -0,0 +1,52 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <vector> + +// Call front() on empty const container. + +#if _LIBCPP_DEBUG >= 1 + +#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0)) + +#include <vector> +#include <cassert> +#include <iterator> +#include <exception> +#include <cstdlib> + +#include "min_allocator.h" + +int main() +{ + { + typedef int T; + typedef std::vector<T> C; + const C c; + assert(c.front() == 0); + assert(false); + } +#if __cplusplus >= 201103L + { + typedef int T; + typedef std::vector<T, min_allocator<T>> C; + const C c; + assert(c.front() == 0); + assert(false); + } +#endif +} + +#else + +int main() +{ +} + +#endif diff --git a/test/libcxx/containers/sequences/vector/db_cindex.pass.cpp b/test/libcxx/containers/sequences/vector/db_cindex.pass.cpp new file mode 100644 index 0000000000000..133aa56528245 --- /dev/null +++ b/test/libcxx/containers/sequences/vector/db_cindex.pass.cpp @@ -0,0 +1,54 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <vector> + +// Index const vector out of bounds. + +#if _LIBCPP_DEBUG >= 1 + +#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0)) + +#include <vector> +#include <cassert> +#include <iterator> +#include <exception> +#include <cstdlib> + +#include "min_allocator.h" + +int main() +{ + { + typedef int T; + typedef std::vector<T> C; + const C c(1); + assert(c[0] == 0); + assert(c[1] == 0); + assert(false); + } +#if __cplusplus >= 201103L + { + typedef int T; + typedef std::vector<T, min_allocator<T>> C; + const C c(1); + assert(c[0] == 0); + assert(c[1] == 0); + assert(false); + } +#endif +} + +#else + +int main() +{ +} + +#endif diff --git a/test/libcxx/containers/sequences/vector/db_front.pass.cpp b/test/libcxx/containers/sequences/vector/db_front.pass.cpp new file mode 100644 index 0000000000000..388058fb31593 --- /dev/null +++ b/test/libcxx/containers/sequences/vector/db_front.pass.cpp @@ -0,0 +1,56 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <vector> + +// Call front() on empty container. + +#if _LIBCPP_DEBUG >= 1 + +#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0)) + +#include <vector> +#include <cassert> +#include <iterator> +#include <exception> +#include <cstdlib> + +#include "min_allocator.h" + +int main() +{ + { + typedef int T; + typedef std::vector<T> C; + C c(1); + assert(c.front() == 0); + c.clear(); + assert(c.front() == 0); + assert(false); + } +#if __cplusplus >= 201103L + { + typedef int T; + typedef std::vector<T, min_allocator<T>> C; + C c(1); + assert(c.front() == 0); + c.clear(); + assert(c.front() == 0); + assert(false); + } +#endif +} + +#else + +int main() +{ +} + +#endif diff --git a/test/libcxx/containers/sequences/vector/db_index.pass.cpp b/test/libcxx/containers/sequences/vector/db_index.pass.cpp new file mode 100644 index 0000000000000..1daf076da67c1 --- /dev/null +++ b/test/libcxx/containers/sequences/vector/db_index.pass.cpp @@ -0,0 +1,56 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <vector> + +// Index vector out of bounds. + +#if _LIBCPP_DEBUG >= 1 + +#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0)) + +#include <vector> +#include <cassert> +#include <iterator> +#include <exception> +#include <cstdlib> + +#include "min_allocator.h" + +int main() +{ + { + typedef int T; + typedef std::vector<T> C; + C c(1); + assert(c[0] == 0); + c.clear(); + assert(c[0] == 0); + assert(false); + } +#if __cplusplus >= 201103L + { + typedef int T; + typedef std::vector<T, min_allocator<T>> C; + C c(1); + assert(c[0] == 0); + c.clear(); + assert(c[0] == 0); + assert(false); + } +#endif +} + +#else + +int main() +{ +} + +#endif diff --git a/test/libcxx/containers/sequences/vector/db_iterators_2.pass.cpp b/test/libcxx/containers/sequences/vector/db_iterators_2.pass.cpp new file mode 100644 index 0000000000000..2d43843067b75 --- /dev/null +++ b/test/libcxx/containers/sequences/vector/db_iterators_2.pass.cpp @@ -0,0 +1,54 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <vector> + +// Compare iterators from different containers with <. + +#if _LIBCPP_DEBUG >= 1 + +#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0)) + +#include <vector> +#include <cassert> +#include <iterator> +#include <exception> +#include <cstdlib> + +#include "min_allocator.h" + +int main() +{ + { + typedef int T; + typedef std::vector<T> C; + C c1; + C c2; + bool b = c1.begin() < c2.begin(); + assert(false); + } +#if __cplusplus >= 201103L + { + typedef int T; + typedef std::vector<T, min_allocator<T>> C; + C c1; + C c2; + bool b = c1.begin() < c2.begin(); + assert(false); + } +#endif +} + +#else + +int main() +{ +} + +#endif diff --git a/test/libcxx/containers/sequences/vector/db_iterators_3.pass.cpp b/test/libcxx/containers/sequences/vector/db_iterators_3.pass.cpp new file mode 100644 index 0000000000000..051d66c33394d --- /dev/null +++ b/test/libcxx/containers/sequences/vector/db_iterators_3.pass.cpp @@ -0,0 +1,54 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <vector> + +// Subtract iterators from different containers. + +#if _LIBCPP_DEBUG >= 1 + +#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0)) + +#include <vector> +#include <cassert> +#include <iterator> +#include <exception> +#include <cstdlib> + +#include "min_allocator.h" + +int main() +{ + { + typedef int T; + typedef std::vector<T> C; + C c1; + C c2; + int i = c1.begin() - c2.begin(); + assert(false); + } +#if __cplusplus >= 201103L + { + typedef int T; + typedef std::vector<T, min_allocator<T>> C; + C c1; + C c2; + int i = c1.begin() - c2.begin(); + assert(false); + } +#endif +} + +#else + +int main() +{ +} + +#endif diff --git a/test/libcxx/containers/sequences/vector/db_iterators_4.pass.cpp b/test/libcxx/containers/sequences/vector/db_iterators_4.pass.cpp new file mode 100644 index 0000000000000..4c2aa628de143 --- /dev/null +++ b/test/libcxx/containers/sequences/vector/db_iterators_4.pass.cpp @@ -0,0 +1,56 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <vector> + +// Index iterator out of bounds. + +#if _LIBCPP_DEBUG >= 1 + +#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0)) + +#include <vector> +#include <cassert> +#include <iterator> +#include <exception> +#include <cstdlib> + +#include "min_allocator.h" + +int main() +{ + { + typedef int T; + typedef std::vector<T> C; + C c(1); + C::iterator i = c.begin(); + assert(i[0] == 0); + assert(i[1] == 0); + assert(false); + } +#if __cplusplus >= 201103L + { + typedef int T; + typedef std::vector<T, min_allocator<T>> C; + C c(1); + C::iterator i = c.begin(); + assert(i[0] == 0); + assert(i[1] == 0); + assert(false); + } +#endif +} + +#else + +int main() +{ +} + +#endif diff --git a/test/libcxx/containers/sequences/vector/db_iterators_5.pass.cpp b/test/libcxx/containers/sequences/vector/db_iterators_5.pass.cpp new file mode 100644 index 0000000000000..1b1090499c276 --- /dev/null +++ b/test/libcxx/containers/sequences/vector/db_iterators_5.pass.cpp @@ -0,0 +1,60 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <vector> + +// Add to iterator out of bounds. + +#if _LIBCPP_DEBUG >= 1 + +#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0)) + +#include <vector> +#include <cassert> +#include <iterator> +#include <exception> +#include <cstdlib> + +#include "min_allocator.h" + +int main() +{ + { + typedef int T; + typedef std::vector<T> C; + C c(1); + C::iterator i = c.begin(); + i += 1; + assert(i == c.end()); + i = c.begin(); + i += 2; + assert(false); + } +#if __cplusplus >= 201103L + { + typedef int T; + typedef std::vector<T, min_allocator<T>> C; + C c(1); + C::iterator i = c.begin(); + i += 1; + assert(i == c.end()); + i = c.begin(); + i += 2; + assert(false); + } +#endif +} + +#else + +int main() +{ +} + +#endif diff --git a/test/libcxx/containers/sequences/vector/db_iterators_6.pass.cpp b/test/libcxx/containers/sequences/vector/db_iterators_6.pass.cpp new file mode 100644 index 0000000000000..424bc939b1366 --- /dev/null +++ b/test/libcxx/containers/sequences/vector/db_iterators_6.pass.cpp @@ -0,0 +1,58 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <vector> + +// Decrement iterator prior to begin. + +#if _LIBCPP_DEBUG >= 1 + +#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0)) + +#include <vector> +#include <cassert> +#include <iterator> +#include <exception> +#include <cstdlib> + +#include "min_allocator.h" + +int main() +{ + { + typedef int T; + typedef std::vector<T> C; + C c(1); + C::iterator i = c.end(); + --i; + assert(i == c.begin()); + --i; + assert(false); + } +#if __cplusplus >= 201103L + { + typedef int T; + typedef std::vector<T, min_allocator<T>> C; + C c(1); + C::iterator i = c.end(); + --i; + assert(i == c.begin()); + --i; + assert(false); + } +#endif +} + +#else + +int main() +{ +} + +#endif diff --git a/test/libcxx/containers/sequences/vector/db_iterators_7.pass.cpp b/test/libcxx/containers/sequences/vector/db_iterators_7.pass.cpp new file mode 100644 index 0000000000000..72cdb10cbc855 --- /dev/null +++ b/test/libcxx/containers/sequences/vector/db_iterators_7.pass.cpp @@ -0,0 +1,58 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <vector> + +// Increment iterator past end. + +#if _LIBCPP_DEBUG >= 1 + +#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0)) + +#include <vector> +#include <cassert> +#include <iterator> +#include <exception> +#include <cstdlib> + +#include "min_allocator.h" + +int main() +{ + { + typedef int T; + typedef std::vector<T> C; + C c(1); + C::iterator i = c.begin(); + ++i; + assert(i == c.end()); + ++i; + assert(false); + } +#if __cplusplus >= 201103L + { + typedef int T; + typedef std::vector<T, min_allocator<T>> C; + C c(1); + C::iterator i = c.begin(); + ++i; + assert(i == c.end()); + ++i; + assert(false); + } +#endif +} + +#else + +int main() +{ +} + +#endif diff --git a/test/libcxx/containers/sequences/vector/db_iterators_8.pass.cpp b/test/libcxx/containers/sequences/vector/db_iterators_8.pass.cpp new file mode 100644 index 0000000000000..7b898533197c6 --- /dev/null +++ b/test/libcxx/containers/sequences/vector/db_iterators_8.pass.cpp @@ -0,0 +1,54 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <vector> + +// Dereference non-dereferenceable iterator. + +#if _LIBCPP_DEBUG >= 1 + +#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0)) + +#include <vector> +#include <cassert> +#include <iterator> +#include <exception> +#include <cstdlib> + +#include "min_allocator.h" + +int main() +{ + { + typedef int T; + typedef std::vector<T> C; + C c(1); + C::iterator i = c.end(); + T j = *i; + assert(false); + } +#if __cplusplus >= 201103L + { + typedef int T; + typedef std::vector<T, min_allocator<T>> C; + C c(1); + C::iterator i = c.end(); + T j = *i; + assert(false); + } +#endif +} + +#else + +int main() +{ +} + +#endif diff --git a/test/libcxx/containers/sequences/vector/version.pass.cpp b/test/libcxx/containers/sequences/vector/version.pass.cpp new file mode 100644 index 0000000000000..2c4fa1263de31 --- /dev/null +++ b/test/libcxx/containers/sequences/vector/version.pass.cpp @@ -0,0 +1,20 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <vector> + +#include <vector> + +#ifndef _LIBCPP_VERSION +#error _LIBCPP_VERSION not defined +#endif + +int main() +{ +} diff --git a/test/libcxx/containers/unord/key_value_traits.pass.cpp b/test/libcxx/containers/unord/key_value_traits.pass.cpp new file mode 100644 index 0000000000000..a6d1ea7a527cc --- /dev/null +++ b/test/libcxx/containers/unord/key_value_traits.pass.cpp @@ -0,0 +1,59 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +#include <__hash_table> +#include <unordered_map> +#include <unordered_set> +#include <type_traits> + +#include "test_macros.h" +#include "min_allocator.h" + +void testKeyValueTrait() { + { + typedef int Tp; + typedef std::__hash_key_value_types<Tp> Traits; + static_assert((std::is_same<Traits::key_type, int>::value), ""); + static_assert((std::is_same<Traits::__node_value_type, Tp>::value), ""); + static_assert((std::is_same<Traits::__container_value_type, Tp>::value), ""); + static_assert(Traits::__is_map == false, ""); + } + { + typedef std::pair<int, int> Tp; + typedef std::__hash_key_value_types<Tp> Traits; + static_assert((std::is_same<Traits::key_type, Tp>::value), ""); + static_assert((std::is_same<Traits::__node_value_type, Tp>::value), ""); + static_assert((std::is_same<Traits::__container_value_type, Tp>::value), ""); + static_assert(Traits::__is_map == false, ""); + } + { + typedef std::pair<const int, int> Tp; + typedef std::__hash_key_value_types<Tp> Traits; + static_assert((std::is_same<Traits::key_type, Tp>::value), ""); + static_assert((std::is_same<Traits::__node_value_type, Tp>::value), ""); + static_assert((std::is_same<Traits::__container_value_type, Tp>::value), ""); + static_assert(Traits::__is_map == false, ""); + } + { + typedef std::__hash_value_type<int, int> Tp; + typedef std::__hash_key_value_types<Tp> Traits; + static_assert((std::is_same<Traits::key_type, int>::value), ""); + static_assert((std::is_same<Traits::mapped_type, int>::value), ""); + static_assert((std::is_same<Traits::__node_value_type, Tp>::value), ""); + static_assert((std::is_same<Traits::__container_value_type, + std::pair<const int, int> >::value), ""); + static_assert((std::is_same<Traits::__map_value_type, + std::pair<const int, int> >::value), ""); + static_assert(Traits::__is_map == true, ""); + } +} + +int main() { + testKeyValueTrait(); +} diff --git a/test/libcxx/containers/unord/next_prime.pass.cpp b/test/libcxx/containers/unord/next_prime.pass.cpp new file mode 100644 index 0000000000000..266d7f1f9d1ea --- /dev/null +++ b/test/libcxx/containers/unord/next_prime.pass.cpp @@ -0,0 +1,51 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// +// +// REQUIRES: long_tests + +// Not a portable test + +// <__hash_table> + +// size_t __next_prime(size_t n); + +// If n == 0, return 0, else return the lowest prime greater than or equal to n + +#include <__hash_table> +#include <cassert> + +bool +is_prime(size_t n) +{ + switch (n) + { + case 0: + case 1: + return false; + } + for (size_t i = 2; i*i <= n; ++i) + { + if (n % i == 0) + return false; + } + return true; +} + +int main() +{ + assert(std::__next_prime(0) == 0); + for (std::size_t n = 1; n <= 100000; ++n) + { + std::size_t p = std::__next_prime(n); + assert(p >= n); + for (std::size_t i = n; i < p; ++i) + assert(!is_prime(i)); + assert(is_prime(p)); + } +} diff --git a/test/libcxx/containers/unord/unord.map/db_iterators_7.pass.cpp b/test/libcxx/containers/unord/unord.map/db_iterators_7.pass.cpp new file mode 100644 index 0000000000000..b8db0a35ffc3e --- /dev/null +++ b/test/libcxx/containers/unord/unord.map/db_iterators_7.pass.cpp @@ -0,0 +1,60 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <unordered_map> + +// Increment iterator past end. + +#if _LIBCPP_DEBUG >= 1 + +#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0)) + +#include <unordered_map> +#include <string> +#include <cassert> +#include <iterator> +#include <exception> +#include <cstdlib> + +#include "min_allocator.h" + +int main() +{ + { + typedef std::unordered_map<int, std::string> C; + C c; + c.insert(std::make_pair(1, "one")); + C::iterator i = c.begin(); + ++i; + assert(i == c.end()); + ++i; + assert(false); + } +#if __cplusplus >= 201103L + { + typedef std::unordered_map<int, std::string, std::hash<int>, std::equal_to<int>, + min_allocator<std::pair<const int, std::string>>> C; + C c; + c.insert(std::make_pair(1, "one")); + C::iterator i = c.begin(); + ++i; + assert(i == c.end()); + ++i; + assert(false); + } +#endif +} + +#else + +int main() +{ +} + +#endif diff --git a/test/libcxx/containers/unord/unord.map/db_iterators_8.pass.cpp b/test/libcxx/containers/unord/unord.map/db_iterators_8.pass.cpp new file mode 100644 index 0000000000000..c923dd77862e6 --- /dev/null +++ b/test/libcxx/containers/unord/unord.map/db_iterators_8.pass.cpp @@ -0,0 +1,56 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <unordered_map> + +// Dereference non-dereferenceable iterator. + +#if _LIBCPP_DEBUG >= 1 + +#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0)) + +#include <unordered_map> +#include <string> +#include <cassert> +#include <iterator> +#include <exception> +#include <cstdlib> + +#include "min_allocator.h" + +int main() +{ + { + typedef std::unordered_map<int, std::string> C; + C c; + c.insert(std::make_pair(1, "one")); + C::iterator i = c.end(); + C::value_type j = *i; + assert(false); + } +#if __cplusplus >= 201103L + { + typedef std::unordered_map<int, std::string, std::hash<int>, std::equal_to<int>, + min_allocator<std::pair<const int, std::string>>> C; + C c; + c.insert(std::make_pair(1, "one")); + C::iterator i = c.end(); + C::value_type j = *i; + assert(false); + } +#endif +} + +#else + +int main() +{ +} + +#endif diff --git a/test/libcxx/containers/unord/unord.map/db_local_iterators_7.pass.cpp b/test/libcxx/containers/unord/unord.map/db_local_iterators_7.pass.cpp new file mode 100644 index 0000000000000..fa1886bfff189 --- /dev/null +++ b/test/libcxx/containers/unord/unord.map/db_local_iterators_7.pass.cpp @@ -0,0 +1,57 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <unordered_map> + +// Increment local_iterator past end. + +#if _LIBCPP_DEBUG >= 1 + +#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0)) + +#include <unordered_map> +#include <string> +#include <cassert> +#include <iterator> +#include <exception> +#include <cstdlib> + +#include "min_allocator.h" + +int main() +{ + { + typedef std::unordered_map<int, std::string> C; + C c(1); + C::local_iterator i = c.begin(0); + ++i; + ++i; + assert(false); + } +#if __cplusplus >= 201103L + { + typedef std::unordered_map<int, std::string, std::hash<int>, std::equal_to<int>, + min_allocator<std::pair<const int, std::string>>> C; + C c(1); + C::local_iterator i = c.begin(0); + ++i; + ++i; + assert(false); + } +#endif + +} + +#else + +int main() +{ +} + +#endif diff --git a/test/libcxx/containers/unord/unord.map/db_local_iterators_8.pass.cpp b/test/libcxx/containers/unord/unord.map/db_local_iterators_8.pass.cpp new file mode 100644 index 0000000000000..4b071cad7b473 --- /dev/null +++ b/test/libcxx/containers/unord/unord.map/db_local_iterators_8.pass.cpp @@ -0,0 +1,54 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <unordered_map> + +// Dereference non-dereferenceable iterator. + +#if _LIBCPP_DEBUG >= 1 + +#define _LIBCPP_ASSERT(x, m) ((x) ? (void)0 : std::exit(0)) + +#include <unordered_map> +#include <string> +#include <cassert> +#include <iterator> +#include <exception> +#include <cstdlib> + +#include "min_allocator.h" + +int main() +{ + { + typedef std::unordered_map<int, std::string> C; + C c(1); + C::local_iterator i = c.end(0); + C::value_type j = *i; + assert(false); + } +#if __cplusplus >= 201103L + { + typedef std::unordered_map<int, std::string, std::hash<int>, std::equal_to<int>, + min_allocator<std::pair<const int, std::string>>> C; + C c(1); + C::local_iterator i = c.end(0); + C::value_type j = *i; + assert(false); + } +#endif +} + +#else + +int main() +{ +} + +#endif diff --git a/test/libcxx/containers/unord/unord.map/version.pass.cpp b/test/libcxx/containers/unord/unord.map/version.pass.cpp new file mode 100644 index 0000000000000..fc47a326c571e --- /dev/null +++ b/test/libcxx/containers/unord/unord.map/version.pass.cpp @@ -0,0 +1,20 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <unordered_map> + +#include <unordered_map> + +#ifndef _LIBCPP_VERSION +#error _LIBCPP_VERSION not defined +#endif + +int main() +{ +} diff --git a/test/libcxx/containers/unord/unord.set/insert_dup_alloc.pass.cpp b/test/libcxx/containers/unord/unord.set/insert_dup_alloc.pass.cpp deleted file mode 100644 index 76ceafed22088..0000000000000 --- a/test/libcxx/containers/unord/unord.set/insert_dup_alloc.pass.cpp +++ /dev/null @@ -1,48 +0,0 @@ -//===----------------------------------------------------------------------===// -// -// 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. -// -//===----------------------------------------------------------------------===// - -// Check that we don't allocate when trying to insert a duplicate value into a -// unordered_set. See PR12999 http://llvm.org/bugs/show_bug.cgi?id=12999 - -#include <cassert> -#include <unordered_set> -#include "count_new.hpp" -#include "MoveOnly.h" - -int main() -{ - { - std::unordered_set<int> s; - assert(globalMemCounter.checkNewCalledEq(0)); - - for(int i=0; i < 100; ++i) - s.insert(3); - - assert(s.size() == 1); - assert(s.count(3) == 1); - assert(globalMemCounter.checkNewCalledEq(2)); - } - assert(globalMemCounter.checkOutstandingNewEq(0)); - globalMemCounter.reset(); -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES - { - std::unordered_set<MoveOnly> s; - assert(globalMemCounter.checkNewCalledEq(0)); - - for(int i=0; i<100; i++) - s.insert(MoveOnly(3)); - - assert(s.size() == 1); - assert(s.count(MoveOnly(3)) == 1); - assert(globalMemCounter.checkNewCalledEq(2)); - } - assert(globalMemCounter.checkOutstandingNewEq(0)); - globalMemCounter.reset(); -#endif -} diff --git a/test/libcxx/containers/unord/unord.set/version.pass.cpp b/test/libcxx/containers/unord/unord.set/version.pass.cpp new file mode 100644 index 0000000000000..d651ebdfc456e --- /dev/null +++ b/test/libcxx/containers/unord/unord.set/version.pass.cpp @@ -0,0 +1,20 @@ +//===----------------------------------------------------------------------===// +// +// 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. +// +//===----------------------------------------------------------------------===// + +// <unordered_set> + +#include <unordered_set> + +#ifndef _LIBCPP_VERSION +#error _LIBCPP_VERSION not defined +#endif + +int main() +{ +} |