| Original file line number | Diff line number | Diff line change |
|---|---|---|
| @@ -1,49 +1,145 @@ | ||
| #ifndef PARLAY_INTERNAL_DEBUG_UNINITIALIZED_H_ | ||
| #define PARLAY_INTERNAL_DEBUG_UNINITIALIZED_H_ | ||
|
|
||
| #include <type_traits> | ||
|
|
||
| namespace parlay { | ||
| namespace internal { | ||
|
|
||
| // A simple type to help look for uninitialized memory bugs. | ||
| // UninitializedTracker is essentially an integer type, but | ||
| // also tracks whether it is currently in an initialized | ||
| // or uninitialized state. | ||
| // | ||
| // Attempting to assign to an uninitialized state will | ||
| // trigger an assertion failure. Attempting to copy or | ||
| // move an uninitialized object will also cause failure. | ||
| // | ||
| // This code will technically invoke undefined behaviour | ||
| // at some point, since we set the initialized flag to | ||
| // false in the destructor for the sole purpose of | ||
| // checking whether it is indeed false the next time | ||
| // someone comes along and wants to do an uninitialized | ||
| // in place construction at that memory location. | ||
| // | ||
| // Some compilers or debugging tools might therefore not | ||
| // work correctly with this class. Defining the initialized | ||
| // flag as volatile seems to prevent compilers from optimizing | ||
| // it out, and therefore leaves its value in memory after | ||
| // the object is destroyed, but this can not be guaranteed. | ||
| // | ||
| // For correctness, this type should only ever be used | ||
| // if its memory is allocated inside a parlay::sequence | ||
| // or parlay::uninitialized_sequence since they know how | ||
| // to set the initialized/uninitialized flag | ||
| struct UninitializedTracker { | ||
|
|
||
| UninitializedTracker() : x(0), initialized(true) {} | ||
|
|
||
| // cppcheck-suppress noExplicitConstructor | ||
| /* implicit */ UninitializedTracker(int _x) : x(_x), initialized(true) {} | ||
|
|
||
| UninitializedTracker(const UninitializedTracker &other) { | ||
| assert(other.initialized && "Attempting to copy an uninitialized object!"); | ||
| x = other.x; | ||
| initialized = true; | ||
| } | ||
|
|
||
| UninitializedTracker &operator=(const UninitializedTracker &other) { | ||
| assert(initialized && "Attempting to assign to an uninitialized object!"); | ||
| assert(other.initialized && "Copy assigning an uninitialized object!"); | ||
| x = other.x; | ||
| return *this; | ||
| } | ||
|
|
||
| ~UninitializedTracker() { | ||
| assert(initialized && "Destructor called on uninitialized object!"); | ||
| initialized = false; | ||
| } | ||
|
|
||
| bool operator==(const UninitializedTracker& other) const { | ||
| assert(initialized && "Trying to compare an uninitialized object!"); | ||
| assert(other.initialized && "Trying to compare against an uninitialized object!"); | ||
| return x == other.x; | ||
| } | ||
|
|
||
| bool operator<(const UninitializedTracker& other) const { | ||
| assert(initialized && "Trying to compare an uninitialized object!"); | ||
| assert(other.initialized && "Trying to compare against an uninitialized object!"); | ||
| return x < other.x; | ||
| } | ||
|
|
||
| void swap(UninitializedTracker& other) { | ||
| assert(initialized && "Trying to swap uninitialized object!"); | ||
| assert(other.initialized && "Trying to swap with uninitialize object!"); | ||
| std::swap(x, other.x); | ||
| } | ||
|
|
||
| int x; | ||
| volatile bool initialized; // Volatile required to prevent optimizing out the store in the destructor | ||
| }; | ||
|
|
||
| } // namespace internal | ||
| } // namespace parlay | ||
|
|
||
| namespace std { | ||
| // Specialize the swap function for UninitializedTracker | ||
| inline void swap(parlay::internal::UninitializedTracker& a, parlay::internal::UninitializedTracker& b) { | ||
| a.swap(b); | ||
| } | ||
| } | ||
|
|
||
| // Macros for testing initialized/uninitializedness | ||
|
|
||
| #ifdef PARLAY_DEBUG_UNINITIALIZED | ||
|
|
||
| // Checks that the given UninitializedTracker object is uninitialized | ||
| // | ||
| // Usage: | ||
| // PARLAY_ASSERT_UNINITIALIZED(x) | ||
| // Result: | ||
| // Terminates the program if the expression (x) refers to an object of | ||
| // type UninitializedTracker such that (x).initialized is true, i.e. | ||
| // the object is in an initialized state | ||
| // | ||
| // Note: This macro should only ever be used on memory that was allocated | ||
| // by a parlay::sequence or a parlay::uninitialized_sequence, since they | ||
| // are required to appropriately flag all newly allocated memory as being | ||
| // uninitialized. False positives will occur if this macro is invoked on | ||
| // memory that is not managed by one of these containers. | ||
| #define PARLAY_ASSERT_UNINITIALIZED(x) \ | ||
| do { \ | ||
| using PARLAY_AU_T = std::remove_cv_t<std::remove_reference_t<decltype(x)>>; \ | ||
| if constexpr (std::is_same_v<PARLAY_AU_T, ::parlay::internal::UninitializedTracker>) { \ | ||
| assert(!((x).initialized) && "Memory required to be uninitialized is initialized!"); \ | ||
| } \ | ||
| } while (0) | ||
|
|
||
| // Checks that the given UninitializedTracker object is initialized | ||
| // | ||
| // Usage: | ||
| // PARLAY_ASSERT_INITIALIZED(x) | ||
| // Result: | ||
| // Terminates the program if the expression (x) refers to an object of | ||
| // type UninitializedTracker such that (x).initialized is false, i.e. | ||
| // the object is in an uninitialized state | ||
| // | ||
| // Note: This macro should only ever be used on memory that was allocated | ||
| // by a parlay::sequence or a parlay::uninitialized_sequence, since they | ||
| // are required to appropriately flag all newly allocated memory as being | ||
| // uninitialized. False positives will occur if this macro is invoked on | ||
| // memory that is not managed by one of these containers. | ||
| #define PARLAY_ASSERT_INITIALIZED(x) \ | ||
| do { \ | ||
| using PARLAY_AI_T = std::remove_cv_t<std::remove_reference_t<decltype(x)>>; \ | ||
| if constexpr (std::is_same_v<PARLAY_AI_T, ::parlay::internal::UninitializedTracker>) { \ | ||
| assert((x).initialized && "Memory required to be initialized is uninitialized!"); \ | ||
| } \ | ||
| } while (0) | ||
|
|
||
| #else | ||
| #define PARLAY_ASSERT_UNINITIALIZED(x) | ||
| #define PARLAY_ASSERT_INITIALIZED(x) | ||
| #endif // PARLAY_DEBUG_UNINITIALIZED | ||
|
|
||
| #endif // PARLAY_INTERNAL_DEBUG_UNINITIALIZED_H_ |
| Original file line number | Diff line number | Diff line change |
|---|---|---|
| @@ -0,0 +1,154 @@ | ||
|
|
||
| #ifndef PARLAY_INTERNAL_UNINITIALIZED_SEQUENCE_H_ | ||
| #define PARLAY_INTERNAL_UNINITIALIZED_SEQUENCE_H_ | ||
|
|
||
| #include <iterator> | ||
| #include <memory> | ||
|
|
||
| #include "../alloc.h" | ||
|
|
||
| #include "debug_uninitialized.h" | ||
|
|
||
| namespace parlay { | ||
| namespace internal { | ||
|
|
||
| #ifndef PARLAY_USE_STD_ALLOC | ||
| template<typename T> | ||
| using _uninitialized_sequence_default_allocator = parlay::allocator<T>; | ||
| #else | ||
| template<typename T> | ||
| using _uninitialized_sequence_default_allocator = std::allocator<T>; | ||
| #endif | ||
|
|
||
| // An uninitialized fixed-size sequence container. | ||
| // | ||
| // By uninitialized, we mean two things: | ||
| // - The constructor uninitialized_sequence<T>(n) does not initialize its elements | ||
| // - The destructor ~uninitialized_sequence() also DOES NOT destroy its elements | ||
| // | ||
| // In other words, the elements of the sequence are uninitialized upon construction, | ||
| // and are also required to be uninitialized when the sequence is destroyed. | ||
| // | ||
| // Q: What on earth is the purpose of such a container?? | ||
| // A: Its purpose is to be used as temporary storage for out of place algorithms | ||
| // that use uninitialized_relocate. Since the container begins in an uninitialized | ||
| // state, it is valid to uninitialized_relocate objects into it, and then | ||
| // uninitialized_relocate them back out. This leaves the elements uninitialized, | ||
| // so that no destructors will accidentally be triggered for moved-out-of objects. | ||
| // | ||
| template<typename T, typename Alloc = _uninitialized_sequence_default_allocator<T>> | ||
| class uninitialized_sequence { | ||
| public: | ||
| using value_type = T; | ||
| using reference = T&; | ||
| using const_reference = const T&; | ||
| using difference_type = std::ptrdiff_t; | ||
| using size_type = size_t; | ||
| using pointer = T*; | ||
| using const_pointer = const T*; | ||
|
|
||
| using iterator = T*; | ||
| using const_iterator = const T*; | ||
| using reverse_iterator = std::reverse_iterator<iterator>; | ||
| using const_reverse_iterator = std::reverse_iterator<const_iterator>; | ||
|
|
||
| using allocator_type = Alloc; | ||
|
|
||
| private: | ||
| struct uninitialized_sequence_impl : public allocator_type { | ||
| size_t n; | ||
| value_type* data; | ||
| explicit uninitialized_sequence_impl(size_t _n, const allocator_type& alloc) | ||
| : allocator_type(alloc), | ||
| n(_n), | ||
| data(std::allocator_traits<allocator_type>::allocate(*this, n)) { } | ||
| ~uninitialized_sequence_impl() { | ||
| std::allocator_traits<allocator_type>::deallocate(*this, data, n); | ||
| } | ||
| } impl; | ||
|
|
||
| public: | ||
| explicit uninitialized_sequence(size_t n, const allocator_type& alloc = {}) | ||
| : impl(n, alloc) { | ||
| #ifdef PARLAY_DEBUG_UNINITIALIZED | ||
| // If uninitialized memory debugging is turned on, make sure that | ||
| // each object of type UninitializedTracker is appropriately set | ||
| // to its uninitialized state. | ||
| if constexpr (std::is_same_v<value_type, UninitializedTracker>) { | ||
| auto buffer = impl.data; | ||
| parallel_for(0, n, [&](size_t i) { | ||
| buffer[i].initialized = false; | ||
| }); | ||
| } | ||
| #endif | ||
| } | ||
|
|
||
| #ifdef PARLAY_DEBUG_UNINITIALIZED | ||
| // If uninitialized memory debugging is turned on, make sure that | ||
| // each object of type UninitializedTracker is destroyed or still | ||
| // uninitialized by the time this sequence is destroyed | ||
| ~uninitialized_sequence() { | ||
| auto buffer = impl.data; | ||
| parallel_for(0, impl.n, [&](size_t i) { | ||
| PARLAY_ASSERT_UNINITIALIZED(buffer[i]); | ||
| }); | ||
| } | ||
| #endif | ||
|
|
||
| iterator begin() { return impl.data; } | ||
| iterator end() { return impl.data + impl.n; } | ||
|
|
||
| const_iterator begin() const { return impl.data; } | ||
| const_iterator end() const { return impl.data + impl.n; } | ||
|
|
||
| const_iterator cbegin() const { return impl.data; } | ||
| const_iterator cend() const { return impl.data + impl.n; } | ||
|
|
||
| reverse_iterator rbegin() { return std::make_reverse_iterator(end()); } | ||
| reverse_iterator rend() { return std::make_reverse_iterator(begin()); } | ||
|
|
||
| const_reverse_iterator rbegin() const { return std::make_reverse_iterator(end()); } | ||
| const_reverse_iterator rend() const { return std::make_reverse_iterator(begin()); } | ||
|
|
||
| const_reverse_iterator crbegin() const { return std::make_reverse_iterator(cend()); } | ||
| const_reverse_iterator crend() const { return std::make_reverse_iterator(cbegin()); } | ||
|
|
||
| void swap(uninitialized_sequence<T, Alloc>& other) { | ||
| std::swap(impl.n, other.impl.n); | ||
| std::swap(impl.data, other.impl.data); | ||
| } | ||
|
|
||
| size_type size() const { return impl.n; } | ||
|
|
||
| value_type* data() { return impl.data; } | ||
|
|
||
| const value_type* data() const { return impl.data; } | ||
|
|
||
| value_type& operator[](size_t i) { return impl.data[i]; } | ||
| const value_type& operator[](size_t i) const { return impl.data[i]; } | ||
|
|
||
| value_type& at(size_t i) { | ||
| if (i >= size()) { | ||
| throw std::out_of_range("uninitialized_sequence access out of bounds: length = " + | ||
| std::to_string(size()) + ", index = " + std::to_string(i)); | ||
| } | ||
| else { | ||
| return impl.data[i]; | ||
| } | ||
| } | ||
|
|
||
| const value_type& at(size_t i) const { | ||
| if (i >= size()) { | ||
| throw std::out_of_range("uninitialized_sequence access out of bounds: length = " + | ||
| std::to_string(size()) + ", index = " + std::to_string(i)); | ||
| } | ||
| else { | ||
| return impl.data[i]; | ||
| } | ||
| } | ||
| }; | ||
|
|
||
| } // namespace internal | ||
| } // namespace parlay | ||
|
|
||
| #endif // PARLAY_INTERNAL_UNINITIALIZED_SEQUENCE_H_ |
| Original file line number | Diff line number | Diff line change |
|---|---|---|
| @@ -0,0 +1,53 @@ | ||
|
|
||
| #ifndef PARLAY_INTERNAL_UNINITIALIZED_STORAGE_H_ | ||
| #define PARLAY_INTERNAL_UNINITIALIZED_STORAGE_H_ | ||
|
|
||
| #include <memory> | ||
| #include <new> | ||
|
|
||
| #include "debug_uninitialized.h" | ||
|
|
||
| namespace parlay { | ||
| namespace internal { | ||
|
|
||
| // Contains uninitialized correctly aligned storage large enough to | ||
| // hold a single object of type T. The object is not initialized | ||
| // and its destructor is not ran when the storage goes out of | ||
| // scope. The purpose of such an object is to act as temp space | ||
| // when using uninitialized_relocate | ||
| template<typename T> | ||
| class uninitialized_storage { | ||
| using value_type = T; | ||
| typename std::aligned_storage<sizeof(T), alignof(T)>::type storage; | ||
|
|
||
| public: | ||
| uninitialized_storage() { | ||
| #ifdef PARLAY_DEBUG_UNINITIALIZED | ||
| // If uninitialized memory debugging is turned on, make sure that | ||
| // each object of type UninitializedTracker is appropriately set | ||
| // to its uninitialized state. | ||
| if constexpr (std::is_same_v<value_type, UninitializedTracker>) { | ||
| get()->initialized = false; | ||
| } | ||
| #endif | ||
| } | ||
|
|
||
| #ifdef PARLAY_DEBUG_UNINITIALIZED | ||
| ~uninitialized_storage() { | ||
| PARLAY_ASSERT_UNINITIALIZED(*get()); | ||
| } | ||
| #endif | ||
|
|
||
| value_type* get() { | ||
| return std::launder(reinterpret_cast<value_type*>(std::addressof(storage))); | ||
| } | ||
|
|
||
| const value_type* get() const { | ||
| return std::launder(reinterpret_cast<value_type*>(std::addressof(storage))); | ||
| } | ||
| }; | ||
|
|
||
| } // namespace internal | ||
| } // namespace parlay | ||
|
|
||
| #endif // PARLAY_INTERNAL_UNINITIALIZED_STORAGE_H_ |
| Original file line number | Diff line number | Diff line change |
|---|---|---|
| @@ -0,0 +1,175 @@ | ||
| // Useful type traits used mostly internally by Parlay | ||
| // | ||
| // Many inspired by this video, and the following standards | ||
| // proposals: | ||
| // - https://www.youtube.com/watch?v=MWBfmmg8-Yo | ||
| // - http://open-std.org/JTC1/SC22/WG21/docs/papers/2014/n4034.pdf | ||
| // - https://quuxplusone.github.io/blog/code/object-relocation-in-terms-of-move-plus-destroy-draft-7.html | ||
| // | ||
| // Includes: | ||
| // - priority_tag | ||
| // - is_contiguous_iterator / is_random_access_iterator | ||
| // - is_trivial_allocator | ||
| // - is_trivially_relocatable / is_nothrow_relocatable | ||
| // | ||
|
|
||
| #ifndef PARLAY_TYPE_TRAITS_H | ||
| #define PARLAY_TYPE_TRAITS_H | ||
|
|
||
| #include <cstddef> | ||
|
|
||
| #include <iterator> | ||
| #include <memory> | ||
| #include <type_traits> | ||
|
|
||
| namespace parlay { | ||
|
|
||
| /* --------------------- Priority tags. ------------------------- | ||
| Priority tags are an easy way to force template resolution to | ||
| pick the "best" option in the presence of multiple valid | ||
| choices. It works because of the facts that priority_tag<K> | ||
| is a subtype of priority_tag<K-1>, and template resolution | ||
| will always pick the most specialised option when faced with | ||
| a choice, so it will prefer priority_tag<K> over | ||
| priority_tag<K-1> | ||
| */ | ||
|
|
||
| template<size_t K> | ||
| struct priority_tag : priority_tag<K-1> {}; | ||
|
|
||
| template<> | ||
| struct priority_tag<0> {}; | ||
|
|
||
| /* --------------------- Contiguous iterators ----------------------- | ||
| An iterator is a contiguous iterator if it points to memory that | ||
| is contiguous. More specifically, it means that given an iterator | ||
| a, and an index n such that a+n is a valid, dereferencable iterator, | ||
| then *(a + n) is equivalent to *(std::addressof(*a) + n). | ||
| C++20 will introduce a concept for detecting contiguous iterators. | ||
| Until then, we just do the conservative thing and deduce that any | ||
| iterators represented as pointers are contiguous. | ||
| We also supply a convenient trait for checking whether an iterator | ||
| is a random access iterator. This can be done using current C++, | ||
| but is too verbose to type frequently, so we shorten it here. | ||
| */ | ||
|
|
||
| template<typename It> | ||
| struct is_contiguous_iterator : std::is_pointer<It> {}; | ||
|
|
||
| template<typename It> | ||
| inline constexpr bool is_contiguous_iterator_v = is_contiguous_iterator<It>::value; | ||
|
|
||
| template<typename It> | ||
| struct is_random_access_iterator : std::bool_constant< | ||
| std::is_base_of_v<std::random_access_iterator_tag, typename std::iterator_traits<It>::iterator_category>> {}; | ||
|
|
||
| template<typename It> | ||
| inline constexpr bool is_random_access_iterator_v = is_random_access_iterator<It>::value; | ||
|
|
||
| /* ----------------- Trivial allocators. --------------------- | ||
| Allocator-aware containers and algorithms need to know whether | ||
| they can construct/destruct objects directly inside memory given | ||
| to them by an allocator, or whether the allocator has custom | ||
| behaviour. Since some optimizations require us to circumvent | ||
| custom allocator behaviour, we need to detect when an allocator | ||
| does not do this. | ||
| Specifically, an allocator-aware algorithm must construct objects | ||
| inside memory returned by an allocator by writing | ||
| std::allocator_traits<allocator_type>::construct(allocator, p, args); | ||
| if the allocator type defines a method .construct, then this results | ||
| in forwarding the construction to that method. Otherwise, this just | ||
| results in a call to | ||
| new (p) T(std::forward<Args>(args)...) | ||
| If we wish to circumvent calling the constructor, for example, | ||
| for a trivially relocatable type in which we would prefer to | ||
| copy directly via memcpy, we must ensure that the allocator | ||
| does not have a custom .construct method. Otherwise, we can | ||
| not optimize, and must continue to use the allocator's own | ||
| construct method. | ||
| The same discussion is true for destruction as well. | ||
| See https://www.youtube.com/watch?v=MWBfmmg8-Yo for more info. | ||
| */ | ||
|
|
||
| namespace internal { | ||
|
|
||
| // Detect the existence of the .destroy method of the type Alloc | ||
| template<typename Alloc, typename T> | ||
| auto trivial_allocator(Alloc& a, T *p, priority_tag<2>) | ||
| -> decltype(void(a.destroy(p)), std::false_type()); | ||
|
|
||
| // Detect the existence of the .construct method of the type Alloc | ||
| template<typename Alloc, typename T> | ||
| auto trivial_allocator(Alloc& a, T *p, priority_tag<1>) | ||
| -> decltype(void(a.construct(p, std::declval<T&&>())), std::false_type()); | ||
|
|
||
| // By default, if no .construct or .destroy methods are found, assume | ||
| // that the allocator is trivial | ||
| template<typename Alloc, typename T> | ||
| auto trivial_allocator(Alloc& a, T* p, priority_tag<0>) | ||
| -> std::true_type; | ||
|
|
||
| } // namespace internal | ||
|
|
||
| template<typename Alloc, typename T> | ||
| struct is_trivial_allocator | ||
| : decltype(internal::trivial_allocator<Alloc, T>(std::declval<Alloc&>(), nullptr, priority_tag<2>())) {}; | ||
|
|
||
| template<typename Alloc, typename T> | ||
| inline constexpr bool is_trivial_allocator_v = is_trivial_allocator<Alloc, T>::value; | ||
|
|
||
| // Manually specialize std::allocator since it is trivial, but | ||
| // some (maybe all?) implementations still provide a .construct | ||
| // and .destroy method anyway. | ||
| template<typename T> | ||
| struct is_trivial_allocator<std::allocator<T>, T> : std::true_type {}; | ||
|
|
||
| /* ----------------- Trivially relocatable. --------------------- | ||
| A type T is called trivially relocatable if, given a pointer | ||
| p to an object of type T, and a pointer q to unintialized | ||
| memory large enough for an object of type T, then | ||
| new (q) T(std::move(*p)); | ||
| p->~T(); | ||
| is equivalent to | ||
| std::memcpy(p, q, sizeof(T)); | ||
| Any type that is trivially move constructible and trivially | ||
| destructible is therefore trivially relocatable. User-defined | ||
| types that are not obviously trivially relocatable can be | ||
| annotated as such by specializing the is_trivially_relocatable | ||
| type. | ||
| See proposal D1144R0 for copious details: | ||
| https://quuxplusone.github.io/blog/code/object-relocation-in-terms-of-move-plus-destroy-draft-7.html | ||
| */ | ||
|
|
||
| template <typename T> | ||
| struct is_trivially_relocatable : | ||
| std::bool_constant<std::is_trivially_move_constructible<T>::value && | ||
| std::is_trivially_destructible<T>::value> { }; | ||
|
|
||
| template <typename T> struct is_nothrow_relocatable : | ||
| std::bool_constant<is_trivially_relocatable<T>::value || | ||
| (std::is_nothrow_move_constructible<T>::value && | ||
| std::is_nothrow_destructible<T>::value)> { }; | ||
|
|
||
| template<typename T> | ||
| inline constexpr bool is_trivially_relocatable_v = is_trivially_relocatable<T>::value; | ||
|
|
||
| template<typename T> | ||
| inline constexpr bool is_nothrow_relocatable_v = is_nothrow_relocatable<T>::value; | ||
|
|
||
| } // namespace parlay | ||
|
|
||
| #endif //PARLAY_TYPE_TRAITS_H |
| Original file line number | Diff line number | Diff line change |
|---|---|---|
| @@ -0,0 +1,124 @@ | ||
| #include "gtest/gtest.h" | ||
|
|
||
| #include <algorithm> | ||
| #include <deque> | ||
| #include <numeric> | ||
|
|
||
| #include <parlay/primitives.h> | ||
| #include <parlay/sequence.h> | ||
| #include <parlay/type_traits.h> | ||
| #include <parlay/utilities.h> | ||
|
|
||
| #include <parlay/internal/counting_sort.h> | ||
|
|
||
| #include "sorting_utils.h" | ||
|
|
||
| constexpr size_t num_buckets = 1 << 16; | ||
|
|
||
| TEST(TestCountingSort, TestCountingSort) { | ||
| auto s = parlay::tabulate(100000, [](unsigned long long i) -> unsigned long long { | ||
| return (50021 * i + 61) % num_buckets; | ||
| }); | ||
| auto [sorted, offsets] = parlay::internal::count_sort(parlay::make_slice(s), [](auto x) { return x; }, num_buckets); | ||
| ASSERT_EQ(s.size(), sorted.size()); | ||
| std::sort(std::begin(s), std::end(s)); | ||
| ASSERT_EQ(s, sorted); | ||
| ASSERT_TRUE(std::is_sorted(std::begin(sorted), std::end(sorted))); | ||
| } | ||
|
|
||
| TEST(TestCountingSort, TestCountingSortUnstable) { | ||
| auto s = parlay::tabulate(100000, [](long long i) -> UnstablePair { | ||
| UnstablePair x; | ||
| x.x = (53 * i + 61) % num_buckets; | ||
| x.y = 0; | ||
| return x; | ||
| }); | ||
| auto [sorted, offsets] = parlay::internal::count_sort(parlay::make_slice(s), [](const auto& x) -> unsigned long long { | ||
| return x.x; | ||
| }, num_buckets); | ||
| ASSERT_EQ(s.size(), sorted.size()); | ||
| std::stable_sort(std::begin(s), std::end(s)); | ||
| ASSERT_EQ(s, sorted); | ||
| ASSERT_TRUE(std::is_sorted(std::begin(sorted), std::end(sorted))); | ||
| } | ||
|
|
||
| TEST(TestCountingSort, TestCountingSortInplaceCustomKey) { | ||
| auto s = parlay::tabulate(100000, [](long long i) -> UnstablePair { | ||
| UnstablePair x; | ||
| x.x = (53 * i + 61) % (1 << 10); | ||
| x.y = 0; | ||
| return x; | ||
| }); | ||
| auto s2 = s; | ||
| ASSERT_EQ(s, s2); | ||
| parlay::internal::count_sort_inplace(parlay::make_slice(s), [](const auto& x) -> unsigned long long { | ||
| return x.x; | ||
| }, num_buckets); | ||
| std::stable_sort(std::begin(s2), std::end(s2)); | ||
| ASSERT_EQ(s, s2); | ||
| ASSERT_TRUE(std::is_sorted(std::begin(s), std::end(s))); | ||
| } | ||
|
|
||
| TEST(TestCountingSort, TestCountingSortInplaceUncopyable) { | ||
| auto s = parlay::tabulate(100000, [](int i) -> UncopyableThing { | ||
| return UncopyableThing((100000-i) % num_buckets); | ||
| }); | ||
| auto s2 = parlay::tabulate(100000, [](int i) -> UncopyableThing { | ||
| return UncopyableThing((100000-i) % num_buckets); | ||
| }); | ||
| ASSERT_EQ(s, s2); | ||
| parlay::internal::count_sort_inplace(parlay::make_slice(s), [](const auto& a) { return a.x; }, num_buckets); | ||
| std::sort(std::begin(s2), std::end(s2)); | ||
| ASSERT_EQ(s, s2); | ||
| ASSERT_TRUE(std::is_sorted(std::begin(s), std::end(s))); | ||
| } | ||
|
|
||
| TEST(TestCountingSort, TestCountingSortInplaceNonContiguous) { | ||
| auto ss = parlay::tabulate(100000, [](long long i) -> long long { | ||
| return (50021 * i + 61) % num_buckets; | ||
| }); | ||
| auto s = std::deque<long long>(ss.begin(), ss.end()); | ||
| auto s2 = s; | ||
| ASSERT_EQ(s, s2); | ||
| parlay::internal::count_sort_inplace(parlay::make_slice(s), [](auto x) { return x; }, num_buckets); | ||
| std::sort(std::begin(s2), std::end(s2)); | ||
| ASSERT_EQ(s, s2); | ||
| ASSERT_TRUE(std::is_sorted(std::begin(s), std::end(s))); | ||
| } | ||
|
|
||
| namespace parlay { | ||
| // Specialize std::unique_ptr to be considered trivially relocatable | ||
| template<typename T> | ||
| struct is_trivially_relocatable<std::unique_ptr<T>> : public std::true_type { }; | ||
| } | ||
|
|
||
| TEST(TestCountingSort, TestCountingSortInplaceUniquePtr) { | ||
| auto s = parlay::tabulate(100000, [](size_t i) { | ||
| return std::make_unique<int>((50021 * i + 61) % num_buckets); | ||
| }); | ||
| auto sorted = parlay::tabulate(100000, [](size_t i) { | ||
| return std::make_unique<int>((50021 * i + 61) % num_buckets); | ||
| }); | ||
| std::sort(std::begin(sorted), std::end(sorted), [](const auto& p1, const auto& p2) { | ||
| return *p1 < *p2; | ||
| }); | ||
| parlay::internal::count_sort_inplace(parlay::make_slice(s), [](const auto& p) { return *p; }, num_buckets); | ||
| ASSERT_EQ(s.size(), sorted.size()); | ||
| for (size_t i = 0; i < 100000; i++) { | ||
| ASSERT_EQ(*s[i], *sorted[i]); | ||
| } | ||
| } | ||
|
|
||
| TEST(TestCountingSort, TestCountingSortInplaceSelfReferential) { | ||
| auto s = parlay::tabulate(100000, [](int i) -> SelfReferentialThing { | ||
| return SelfReferentialThing(i % num_buckets); | ||
| }); | ||
| auto s2 = parlay::tabulate(100000, [](int i) -> SelfReferentialThing { | ||
| return SelfReferentialThing(i % num_buckets); | ||
| }); | ||
| ASSERT_EQ(s, s2); | ||
| parlay::internal::count_sort_inplace(parlay::make_slice(s), [](const auto& p) { return p.x; }, num_buckets); | ||
| std::stable_sort(std::begin(s2), std::end(s2)); | ||
| ASSERT_EQ(s, s2); | ||
| ASSERT_TRUE(std::is_sorted(std::begin(s), std::end(s))); | ||
| } |
| Original file line number | Diff line number | Diff line change |
|---|---|---|
| @@ -1,10 +1,182 @@ | ||
| #include "gtest/gtest.h" | ||
|
|
||
| #include <algorithm> | ||
| #include <numeric> | ||
| #include <vector> | ||
|
|
||
| #include <parlay/delayed_sequence.h> | ||
|
|
||
| TEST(TestDelayedSequence, TestConstruction) { | ||
| auto s = parlay::delayed_seq<int>(100000, [](size_t i) -> int { return i; }); | ||
| ASSERT_EQ(s.size(), 100000); | ||
| } | ||
|
|
||
| struct MyFunctor { | ||
| std::unique_ptr<int> f; | ||
| MyFunctor(int _f) : f(std::make_unique<int>(_f)) { } | ||
| MyFunctor(const MyFunctor& other) : f(std::make_unique<int>(*(other.f))) {} | ||
| MyFunctor& operator=(const MyFunctor& other) { | ||
| f = std::make_unique<int>(*(other.f)); | ||
| return *this; | ||
| } | ||
| MyFunctor(MyFunctor&& other) : f(std::move(other.f)) { } | ||
| MyFunctor& operator=(MyFunctor&& other) { | ||
| f = std::move(other.f); | ||
| return *this; | ||
| } | ||
| int operator()(int i) const { return *f*i; } | ||
| }; | ||
|
|
||
| TEST(TestDelayedSequence, TestCopyConstruct) { | ||
| auto s = parlay::delayed_seq<int>(100000, MyFunctor(1)); | ||
| auto s2 = s; | ||
| ASSERT_EQ(s2.size(), s.size()); | ||
| ASSERT_TRUE(std::equal(std::begin(s), std::end(s), std::begin(s2))); | ||
| } | ||
|
|
||
| TEST(TestDelayedSequence, TestMoveConstruct) { | ||
| auto s = parlay::delayed_seq<int>(100000, MyFunctor(1)); | ||
| auto s2 = std::move(s); | ||
| ASSERT_EQ(s2.size(), 100000); | ||
| for (size_t i = 0; i < 100000; i++) { | ||
| ASSERT_EQ(s2[i], i); | ||
| } | ||
| } | ||
|
|
||
| TEST(TestDelayedSequence, TestCopyAssign) { | ||
| auto s = parlay::delayed_seq<int>(100000, MyFunctor(1)); | ||
| ASSERT_EQ(s.size(), 100000); | ||
| for (size_t i = 0; i < 10000; i++) { | ||
| ASSERT_EQ(s[i], i); | ||
| } | ||
| s = parlay::delayed_seq<int>(200000, MyFunctor(2)); | ||
| ASSERT_EQ(s.size(), 200000); | ||
| for (size_t i = 0; i < 20000; i++) { | ||
| ASSERT_EQ(s[i], i*2); | ||
| } | ||
| } | ||
|
|
||
| TEST(TestDelayedSequence, TestMoveAssign) { | ||
| auto s = parlay::delayed_seq<int>(100000, MyFunctor(1)); | ||
| for (size_t i = 0; i < 10000; i++) { | ||
| ASSERT_EQ(s[i], i); | ||
| } | ||
| auto s2 = parlay::delayed_seq<int>(200000, MyFunctor(2)); | ||
| s = std::move(s2); | ||
| ASSERT_EQ(s.size(), 200000); | ||
| for (size_t i = 0; i < 20000; i++) { | ||
| ASSERT_EQ(s[i], i*2); | ||
| } | ||
| } | ||
|
|
||
| // I don't know why you would ever want to do this but | ||
| // hey, its possible | ||
| TEST(TestDelayedSequence, TestLambdaCapture) { | ||
| auto v = std::vector<int>(100000); | ||
| std::iota(std::begin(v), std::end(v), 0); | ||
| auto s = parlay::delayed_seq<int>(100000, [v = std::move(v)](size_t i) { | ||
| return v[i]; | ||
| }); | ||
| ASSERT_EQ(s.size(), 100000); | ||
| for (size_t i = 0; i < 10000; i++) { | ||
| ASSERT_EQ(s[i], i); | ||
| } | ||
| } | ||
|
|
||
| TEST(TestDelayedSequence, TestAsInputIterator) { | ||
| auto s = parlay::delayed_seq<int>(100000, [](size_t i) -> int { return i; }); | ||
| std::vector<int> v; | ||
| std::copy(std::begin(s), std::end(s), std::back_inserter(v)); | ||
| ASSERT_TRUE(std::equal(std::begin(s), std::end(s), std::begin(v))); | ||
| } | ||
|
|
||
| TEST(TestDelayedSequence, TestForwardIterator) { | ||
| auto s = parlay::delayed_seq<int>(100000, [](size_t i) -> int { return i; }); | ||
| size_t i = 0; | ||
| for (auto it = s.begin(); it != s.end(); it++) { | ||
| ASSERT_EQ(*it, i++); | ||
| } | ||
| ASSERT_EQ(i, 100000); | ||
| } | ||
|
|
||
| TEST(TestDelayedSequence, TestBackwardIterator) { | ||
| auto s = parlay::delayed_seq<int>(100000, [](size_t i) -> int { return i; }); | ||
| size_t i = 100000; | ||
| for (auto it = s.end(); it != s.begin(); it--) { | ||
| ASSERT_EQ(*(it-1), --i); | ||
| } | ||
| ASSERT_EQ(i, 0); | ||
| } | ||
|
|
||
| TEST(TestDelayedSequence, TestAsReverseIterator) { | ||
| auto s = parlay::delayed_seq<int>(100000, [](size_t i) -> int { return i; }); | ||
| std::vector<int> v; | ||
| std::copy(std::rbegin(s), std::rend(s), std::back_inserter(v)); | ||
| ASSERT_TRUE(std::equal(std::begin(s), std::end(s), std::rbegin(v))); | ||
| } | ||
|
|
||
| TEST(TestDelayedSequence, TestAsRandomAccess) { | ||
| auto s = parlay::delayed_seq<int>(100000, [](size_t i) -> int { return i; }); | ||
| auto found = std::binary_search(std::begin(s), std::end(s), 49998); | ||
| ASSERT_TRUE(found); | ||
| auto it = std::lower_bound(std::begin(s), std::end(s), 49998); | ||
| ASSERT_NE(it, std::end(s)); | ||
| ASSERT_EQ(*it, 49998); | ||
| } | ||
|
|
||
| TEST(TestDelayedSequence, TestSubscript) { | ||
| auto s = parlay::delayed_seq<int>(100000, [](size_t i) -> int { return i; }); | ||
| for (size_t i = 0; i < 100000; i++) { | ||
| ASSERT_EQ(i, s[i]); | ||
| } | ||
| } | ||
|
|
||
| TEST(TestDelayedSequence, TestAt) { | ||
| auto s = parlay::delayed_seq<int>(100000, [](size_t i) -> int { return i; }); | ||
| for (size_t i = 0; i < 100000; i++) { | ||
| ASSERT_EQ(i, s.at(i)); | ||
| } | ||
| } | ||
|
|
||
| TEST(TestDelayedSequence, TestFront) { | ||
| auto s = parlay::delayed_seq<int>(100000, [](size_t i) -> int { return i; }); | ||
| ASSERT_EQ(s.front(), 0); | ||
| } | ||
|
|
||
| TEST(TestDelayedSequence, TestBack) { | ||
| auto s = parlay::delayed_seq<int>(100000, [](size_t i) -> int { return i; }); | ||
| ASSERT_EQ(s.back(), 99999); | ||
| } | ||
|
|
||
| // Delayed sequences can be used to return references, so that | ||
| // they will not make copies of the things they refer to. | ||
| TEST(TestDelayedSequence, TestDelayedSequenceOfReferences) { | ||
| std::vector<std::unique_ptr<int>> v; | ||
| for (size_t i = 0; i < 100000; i++) { | ||
| v.emplace_back(std::make_unique<int>(i)); | ||
| } | ||
| auto s = parlay::delayed_seq<const std::unique_ptr<int>&>(100000, [&](size_t i) -> const std::unique_ptr<int>& { | ||
| return v[i]; | ||
| }); | ||
| for (size_t i = 0; i < 100000; i++) { | ||
| const auto& si = s[i]; | ||
| ASSERT_EQ(*v[i], *si); | ||
| } | ||
| } | ||
|
|
||
| // Delayed sequences can be used to return references, and | ||
| // they can even be mutable references, so we can modify | ||
| // the underlying source! | ||
| TEST(TestDelayedSequence, TestDelayedSequenceOfMutableReferences) { | ||
| std::vector<std::unique_ptr<int>> v; | ||
| for (size_t i = 0; i < 100000; i++) { | ||
| v.emplace_back(std::make_unique<int>(i)); | ||
| } | ||
| auto s = parlay::delayed_seq<int&>(100000, [&](size_t i) -> int& { | ||
| return *v[i]; | ||
| }); | ||
| for (size_t i = 0; i < 100000; i++) { | ||
| s[i]++; | ||
| ASSERT_EQ(*v[i], i+1); | ||
| } | ||
| } |