From fd5eeb5f4bb9ad55172e9454f726667e3c325000 Mon Sep 17 00:00:00 2001 From: Yedidya Feldblum Date: Thu, 11 Jan 2018 21:56:07 -0800 Subject: [PATCH] Unsafe pre-sorted construction for sorted-vector containers Summary: [Folly] Unsafe pre-sorted construction for sorted-vector containers. If the backing container type can be constructed directly in sorted order or can be determined in advance to be in sorted order, then a special constructor can help code take advantage of this condition by avoiding an extra invocation of `std::sort`. Reviewed By: spalamarchuk Differential Revision: D6708379 fbshipit-source-id: 25d886b0814dc9230c6046ed1e7f199fac47754e --- folly/Utility.h | 24 ++++++++++++++- folly/sorted_vector_types.h | 51 +++++++++++++++++++++++++++++-- folly/test/UtilityTest.cpp | 2 +- folly/test/sorted_vector_test.cpp | 2 +- 4 files changed, 73 insertions(+), 6 deletions(-) diff --git a/folly/Utility.h b/folly/Utility.h index 1969a964..94141c18 100644 --- a/folly/Utility.h +++ b/folly/Utility.h @@ -1,5 +1,5 @@ /* - * Copyright 2017 Facebook, Inc. + * Copyright 2016-present Facebook, Inc. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -262,6 +262,28 @@ inline in_place_index_tag in_place_index(in_place_index_tag = {}) { struct initlist_construct_t {}; constexpr initlist_construct_t initlist_construct{}; +/** + * A generic tag type to indicate that some constructor or method is in some way + * unsafe and should be used only with extreme care and with full test coverage, + * if ever. + * + * Example: + * + * void takes_numbers(std::vector alist) { + * std::sort(alist.begin(), alist.end()); + * takes_numbers_assume_sorted(folly::unsafe, alist); + * } + * + * void takes_numbers_assume_sorted(folly::unsafe_t, std::vector alist) { + * assert(std::is_sorted(alist.begin(), alist.end())); // debug mode only + * for (i : alist) { + * // some behavior which is defined and safe only when alist is sorted ... + * } + * } + */ +struct unsafe_t {}; +constexpr unsafe_t unsafe{}; + /** * A simple function object that passes its argument through unchanged. * diff --git a/folly/sorted_vector_types.h b/folly/sorted_vector_types.h index f7fbba24..06d238ff 100644 --- a/folly/sorted_vector_types.h +++ b/folly/sorted_vector_types.h @@ -1,5 +1,5 @@ /* - * Copyright 2017 Facebook, Inc. + * Copyright 2011-present Facebook, Inc. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -60,6 +60,7 @@ #pragma once #include +#include #include #include #include @@ -70,6 +71,7 @@ #include #include +#include #include namespace folly { @@ -193,6 +195,13 @@ void bulk_insert( cont.end()); } } + +template +Container&& as_sorted(Container&& container, Compare const& comp) { + using namespace std; + std::sort(begin(container), end(container), comp); + return static_cast(container); +} } // namespace detail ////////////////////////////////////////////////////////////////////// @@ -285,10 +294,28 @@ class sorted_vector_set // Note that `sorted_vector_set(const Container& container)` is not provided, // since the purpose of this constructor is to avoid an unnecessary copy. explicit sorted_vector_set( + Container&& container, + const Compare& comp = Compare()) + : sorted_vector_set( + unsafe, + detail::as_sorted(std::move(container), comp), + comp) {} + + // Construct a sorted_vector_set by stealing the storage of a prefilled + // container. The container must be sorted, as unsafe_t hints. This supports + // bulk construction of sorted_vector_set with zero allocations, not counting + // those performed by the caller. (The iterator range constructor performs at + // least one allocation). + // + // Note that `sorted_vector_set(unsafe_t, const Container& container)` is not + // provided, since the purpose of this constructor is to avoid an unnecessary + // copy. + sorted_vector_set( + unsafe_t, Container&& container, const Compare& comp = Compare()) : m_(comp, container.get_allocator()) { - std::sort(container.begin(), container.end(), value_comp()); + assert(std::is_sorted(container.begin(), container.end(), value_comp())); m_.cont_.swap(container); } @@ -596,10 +623,28 @@ class sorted_vector_map // Note that `sorted_vector_map(const Container& container)` is not provided, // since the purpose of this constructor is to avoid an unnecessary copy. explicit sorted_vector_map( + Container&& container, + const Compare& comp = Compare()) + : sorted_vector_map( + unsafe, + detail::as_sorted(std::move(container), value_compare(comp)), + comp) {} + + // Construct a sorted_vector_map by stealing the storage of a prefilled + // container. The container must be sorted, as unsafe_t hints. This supports + // bulk construction of sorted_vector_map with zero allocations, not counting + // those performed by the caller. (The iterator range constructor performs at + // least one allocation). + // + // Note that `sorted_vector_map(unsafe_t, const Container& container)` is not + // provided, since the purpose of this constructor is to avoid an unnecessary + // copy. + sorted_vector_map( + unsafe_t, Container&& container, const Compare& comp = Compare()) : m_(value_compare(comp), container.get_allocator()) { - std::sort(container.begin(), container.end(), value_comp()); + assert(std::is_sorted(container.begin(), container.end(), value_comp())); m_.cont_.swap(container); } diff --git a/folly/test/UtilityTest.cpp b/folly/test/UtilityTest.cpp index c6f269e8..d27f4675 100644 --- a/folly/test/UtilityTest.cpp +++ b/folly/test/UtilityTest.cpp @@ -1,5 +1,5 @@ /* - * Copyright 2017 Facebook, Inc. + * Copyright 2016-present Facebook, Inc. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. diff --git a/folly/test/sorted_vector_test.cpp b/folly/test/sorted_vector_test.cpp index 7efa4c8f..e0692559 100644 --- a/folly/test/sorted_vector_test.cpp +++ b/folly/test/sorted_vector_test.cpp @@ -1,5 +1,5 @@ /* - * Copyright 2017 Facebook, Inc. + * Copyright 2011-present Facebook, Inc. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. -- 2.34.1