From 1ae9b71c474628d60eb251a3f62967fe64151bb2 Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Tue, 20 Apr 2021 07:17:48 -0700 Subject: Export of internal Abseil changes MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit -- ac1df60490c9583e475e22de7adfc40023196fbf by Martijn Vels : Change Cord constructor(string_view) to explicit make_tree and Cordz tracking This CL changes the ctor to use an easier to maintain model where Cord code explicitly invokes Cordz update or new / tree logic, which avoids the ambiguity of the 'branched' InlineRep::set_tree code. This removes the need to equip InlineRep with 'MethodIdentifier' or other necessary call info, and also is a cleaner model: InlineRep is carrying too much code now that should plainly sit in Cord, especially with all internal abstractions having moved to InlineData. See child CL(s) for desired state PiperOrigin-RevId: 369433619 -- b665af7f586e6c679a8b27d4f78d5a1d2b596058 by Abseil Team : Rename the 'Compare' template type to 'LessThan', as the passed-in function is expected to act like operator<. It is worth avoiding confusion with std::compare, which returns an int (-1/0/1), as due to implicit casting this can lead to hard-to-spot bugs. PiperOrigin-RevId: 369391118 -- c3c775269cad0f4982ec63f3616dd78bb9e52dca by Martijn Vels : Integrate CordzUpdateTracker into CordzInfo PiperOrigin-RevId: 369348824 -- 771d81ed357496c117179e1daec76eba5155932d by Martijn Vels : Replace mutex() with Lock() / Unlock() function Mini design future tracking of CordzInfo sampled cords: CordzInfo holds a CordRep* reference without a reference count. Cord is responsible for synchronizing updates for sampled cords such that the CordRep* contained in CordzInfo is at all times valid. This is done by scoping Lock() and Unlock() calls around the code modifying the code of a sampled cord. For example (using the future CL CordzUpdateScope()): CordzInfo* cordz_info = get_cordz_info(); CordzUpdateScope scope(cordz_info, CordzUpdateTracker::kRemovePrefix); CordRep* rep = RemovePrefixImpl(root); set_tree(rep); if (cordz_info) { cordz_info->SetCordRep(rep); } On CordzInfo::Unlock(), if the internal rep is null, the cord is no longer sampled, and CordzInfo will be deleted. Thus any update resulting in the Cord being inlined will automatically no longer be sampled. PiperOrigin-RevId: 369338802 -- 5563c12df04a1e965a03b50bdd032739c55c0706 by Martijn Vels : Add UpdateTracker to CordzStatistics PiperOrigin-RevId: 369318178 -- 6b4d8463722a3e55a3e8f6cb3741a41055e7f83e by Martijn Vels : Add kClear, kConstructor* and kUnknown values and fix typo PiperOrigin-RevId: 369297163 -- 041adcbc929789d6d53371a8236840fc350e1eeb by Derek Mauro : Switch from malloc to operator new in pool_urbg.cc so it can only fail by throwing/aborting PiperOrigin-RevId: 369274087 -- 5d97a5f43e3f2d02d0a5bbe586d93b5751812981 by Benjamin Barenblat : Correct Thumb function bound computation in the symbolizer On 32-bit ARM, all functions are aligned to multiples of two bytes, and the lowest-order bit in a function’s address is ignored by the CPU when computing branch targets. That bit is still present in instructions and ELF symbol tables, though; it’s repurposed to indicate whether the function contains ARM or Thumb code. If the symbolizer doesn’t ignore that bit, it will believe Thumb functions have boundaries that are off by one byte, so instruct the symbolizer to null out the lowest-order bit after retrieving it from the symbol table. PiperOrigin-RevId: 369254082 -- 462bb307c6cc332c1e2c3adb5f0cad51804bf937 by Derek Mauro : Add a check for malloc failure in pool_urbg.cc GitHub #940 PiperOrigin-RevId: 369238100 GitOrigin-RevId: ac1df60490c9583e475e22de7adfc40023196fbf Change-Id: Ic6ec91c62cd3a0031f6a75a43a83da959ece2d25 --- absl/algorithm/container.h | 180 ++++++++++++++++++++++----------------------- 1 file changed, 90 insertions(+), 90 deletions(-) (limited to 'absl/algorithm/container.h') diff --git a/absl/algorithm/container.h b/absl/algorithm/container.h index 6398438f..1652e7b0 100644 --- a/absl/algorithm/container.h +++ b/absl/algorithm/container.h @@ -905,11 +905,11 @@ void c_sort(C& c) { // Overload of c_sort() for performing a `comp` comparison other than the // default `operator<`. -template -void c_sort(C& c, Compare&& comp) { +template +void c_sort(C& c, LessThan&& comp) { std::sort(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c), - std::forward(comp)); + std::forward(comp)); } // c_stable_sort() @@ -925,11 +925,11 @@ void c_stable_sort(C& c) { // Overload of c_stable_sort() for performing a `comp` comparison other than the // default `operator<`. -template -void c_stable_sort(C& c, Compare&& comp) { +template +void c_stable_sort(C& c, LessThan&& comp) { std::stable_sort(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c), - std::forward(comp)); + std::forward(comp)); } // c_is_sorted() @@ -944,11 +944,11 @@ bool c_is_sorted(const C& c) { // c_is_sorted() overload for performing a `comp` comparison other than the // default `operator<`. -template -bool c_is_sorted(const C& c, Compare&& comp) { +template +bool c_is_sorted(const C& c, LessThan&& comp) { return std::is_sorted(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c), - std::forward(comp)); + std::forward(comp)); } // c_partial_sort() @@ -966,14 +966,14 @@ void c_partial_sort( // Overload of c_partial_sort() for performing a `comp` comparison other than // the default `operator<`. -template +template void c_partial_sort( RandomAccessContainer& sequence, container_algorithm_internal::ContainerIter middle, - Compare&& comp) { + LessThan&& comp) { std::partial_sort(container_algorithm_internal::c_begin(sequence), middle, container_algorithm_internal::c_end(sequence), - std::forward(comp)); + std::forward(comp)); } // c_partial_sort_copy() @@ -994,15 +994,15 @@ c_partial_sort_copy(const C& sequence, RandomAccessContainer& result) { // Overload of c_partial_sort_copy() for performing a `comp` comparison other // than the default `operator<`. -template +template container_algorithm_internal::ContainerIter c_partial_sort_copy(const C& sequence, RandomAccessContainer& result, - Compare&& comp) { + LessThan&& comp) { return std::partial_sort_copy(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), container_algorithm_internal::c_begin(result), container_algorithm_internal::c_end(result), - std::forward(comp)); + std::forward(comp)); } // c_is_sorted_until() @@ -1018,12 +1018,12 @@ container_algorithm_internal::ContainerIter c_is_sorted_until(C& c) { // Overload of c_is_sorted_until() for performing a `comp` comparison other than // the default `operator<`. -template +template container_algorithm_internal::ContainerIter c_is_sorted_until( - C& c, Compare&& comp) { + C& c, LessThan&& comp) { return std::is_sorted_until(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c), - std::forward(comp)); + std::forward(comp)); } // c_nth_element() @@ -1043,14 +1043,14 @@ void c_nth_element( // Overload of c_nth_element() for performing a `comp` comparison other than // the default `operator<`. -template +template void c_nth_element( RandomAccessContainer& sequence, container_algorithm_internal::ContainerIter nth, - Compare&& comp) { + LessThan&& comp) { std::nth_element(container_algorithm_internal::c_begin(sequence), nth, container_algorithm_internal::c_end(sequence), - std::forward(comp)); + std::forward(comp)); } //------------------------------------------------------------------------------ @@ -1072,12 +1072,12 @@ container_algorithm_internal::ContainerIter c_lower_bound( // Overload of c_lower_bound() for performing a `comp` comparison other than // the default `operator<`. -template +template container_algorithm_internal::ContainerIter c_lower_bound( - Sequence& sequence, T&& value, Compare&& comp) { + Sequence& sequence, T&& value, LessThan&& comp) { return std::lower_bound(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), - std::forward(value), std::forward(comp)); + std::forward(value), std::forward(comp)); } // c_upper_bound() @@ -1095,12 +1095,12 @@ container_algorithm_internal::ContainerIter c_upper_bound( // Overload of c_upper_bound() for performing a `comp` comparison other than // the default `operator<`. -template +template container_algorithm_internal::ContainerIter c_upper_bound( - Sequence& sequence, T&& value, Compare&& comp) { + Sequence& sequence, T&& value, LessThan&& comp) { return std::upper_bound(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), - std::forward(value), std::forward(comp)); + std::forward(value), std::forward(comp)); } // c_equal_range() @@ -1118,12 +1118,12 @@ c_equal_range(Sequence& sequence, T&& value) { // Overload of c_equal_range() for performing a `comp` comparison other than // the default `operator<`. -template +template container_algorithm_internal::ContainerIterPairType -c_equal_range(Sequence& sequence, T&& value, Compare&& comp) { +c_equal_range(Sequence& sequence, T&& value, LessThan&& comp) { return std::equal_range(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), - std::forward(value), std::forward(comp)); + std::forward(value), std::forward(comp)); } // c_binary_search() @@ -1140,12 +1140,12 @@ bool c_binary_search(Sequence&& sequence, T&& value) { // Overload of c_binary_search() for performing a `comp` comparison other than // the default `operator<`. -template -bool c_binary_search(Sequence&& sequence, T&& value, Compare&& comp) { +template +bool c_binary_search(Sequence&& sequence, T&& value, LessThan&& comp) { return std::binary_search(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), std::forward(value), - std::forward(comp)); + std::forward(comp)); } //------------------------------------------------------------------------------ @@ -1166,14 +1166,14 @@ OutputIterator c_merge(const C1& c1, const C2& c2, OutputIterator result) { // Overload of c_merge() for performing a `comp` comparison other than // the default `operator<`. -template +template OutputIterator c_merge(const C1& c1, const C2& c2, OutputIterator result, - Compare&& comp) { + LessThan&& comp) { return std::merge(container_algorithm_internal::c_begin(c1), container_algorithm_internal::c_end(c1), container_algorithm_internal::c_begin(c2), container_algorithm_internal::c_end(c2), result, - std::forward(comp)); + std::forward(comp)); } // c_inplace_merge() @@ -1189,13 +1189,13 @@ void c_inplace_merge(C& c, // Overload of c_inplace_merge() for performing a merge using a `comp` other // than `operator<`. -template +template void c_inplace_merge(C& c, container_algorithm_internal::ContainerIter middle, - Compare&& comp) { + LessThan&& comp) { std::inplace_merge(container_algorithm_internal::c_begin(c), middle, container_algorithm_internal::c_end(c), - std::forward(comp)); + std::forward(comp)); } // c_includes() @@ -1213,13 +1213,13 @@ bool c_includes(const C1& c1, const C2& c2) { // Overload of c_includes() for performing a merge using a `comp` other than // `operator<`. -template -bool c_includes(const C1& c1, const C2& c2, Compare&& comp) { +template +bool c_includes(const C1& c1, const C2& c2, LessThan&& comp) { return std::includes(container_algorithm_internal::c_begin(c1), container_algorithm_internal::c_end(c1), container_algorithm_internal::c_begin(c2), container_algorithm_internal::c_end(c2), - std::forward(comp)); + std::forward(comp)); } // c_set_union() @@ -1243,7 +1243,7 @@ OutputIterator c_set_union(const C1& c1, const C2& c2, OutputIterator output) { // Overload of c_set_union() for performing a merge using a `comp` other than // `operator<`. -template ::value, void>::type, @@ -1251,12 +1251,12 @@ template ::value, void>::type> OutputIterator c_set_union(const C1& c1, const C2& c2, OutputIterator output, - Compare&& comp) { + LessThan&& comp) { return std::set_union(container_algorithm_internal::c_begin(c1), container_algorithm_internal::c_end(c1), container_algorithm_internal::c_begin(c2), container_algorithm_internal::c_end(c2), output, - std::forward(comp)); + std::forward(comp)); } // c_set_intersection() @@ -1280,7 +1280,7 @@ OutputIterator c_set_intersection(const C1& c1, const C2& c2, // Overload of c_set_intersection() for performing a merge using a `comp` other // than `operator<`. -template ::value, void>::type, @@ -1288,12 +1288,12 @@ template ::value, void>::type> OutputIterator c_set_intersection(const C1& c1, const C2& c2, - OutputIterator output, Compare&& comp) { + OutputIterator output, LessThan&& comp) { return std::set_intersection(container_algorithm_internal::c_begin(c1), container_algorithm_internal::c_end(c1), container_algorithm_internal::c_begin(c2), container_algorithm_internal::c_end(c2), output, - std::forward(comp)); + std::forward(comp)); } // c_set_difference() @@ -1318,7 +1318,7 @@ OutputIterator c_set_difference(const C1& c1, const C2& c2, // Overload of c_set_difference() for performing a merge using a `comp` other // than `operator<`. -template ::value, void>::type, @@ -1326,12 +1326,12 @@ template ::value, void>::type> OutputIterator c_set_difference(const C1& c1, const C2& c2, - OutputIterator output, Compare&& comp) { + OutputIterator output, LessThan&& comp) { return std::set_difference(container_algorithm_internal::c_begin(c1), container_algorithm_internal::c_end(c1), container_algorithm_internal::c_begin(c2), container_algorithm_internal::c_end(c2), output, - std::forward(comp)); + std::forward(comp)); } // c_set_symmetric_difference() @@ -1357,7 +1357,7 @@ OutputIterator c_set_symmetric_difference(const C1& c1, const C2& c2, // Overload of c_set_symmetric_difference() for performing a merge using a // `comp` other than `operator<`. -template ::value, void>::type, @@ -1366,13 +1366,13 @@ template ::type> OutputIterator c_set_symmetric_difference(const C1& c1, const C2& c2, OutputIterator output, - Compare&& comp) { + LessThan&& comp) { return std::set_symmetric_difference( container_algorithm_internal::c_begin(c1), container_algorithm_internal::c_end(c1), container_algorithm_internal::c_begin(c2), container_algorithm_internal::c_end(c2), output, - std::forward(comp)); + std::forward(comp)); } //------------------------------------------------------------------------------ @@ -1391,11 +1391,11 @@ void c_push_heap(RandomAccessContainer& sequence) { // Overload of c_push_heap() for performing a push operation on a heap using a // `comp` other than `operator<`. -template -void c_push_heap(RandomAccessContainer& sequence, Compare&& comp) { +template +void c_push_heap(RandomAccessContainer& sequence, LessThan&& comp) { std::push_heap(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), - std::forward(comp)); + std::forward(comp)); } // c_pop_heap() @@ -1410,11 +1410,11 @@ void c_pop_heap(RandomAccessContainer& sequence) { // Overload of c_pop_heap() for performing a pop operation on a heap using a // `comp` other than `operator<`. -template -void c_pop_heap(RandomAccessContainer& sequence, Compare&& comp) { +template +void c_pop_heap(RandomAccessContainer& sequence, LessThan&& comp) { std::pop_heap(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), - std::forward(comp)); + std::forward(comp)); } // c_make_heap() @@ -1429,11 +1429,11 @@ void c_make_heap(RandomAccessContainer& sequence) { // Overload of c_make_heap() for performing heap comparisons using a // `comp` other than `operator<` -template -void c_make_heap(RandomAccessContainer& sequence, Compare&& comp) { +template +void c_make_heap(RandomAccessContainer& sequence, LessThan&& comp) { std::make_heap(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), - std::forward(comp)); + std::forward(comp)); } // c_sort_heap() @@ -1448,11 +1448,11 @@ void c_sort_heap(RandomAccessContainer& sequence) { // Overload of c_sort_heap() for performing heap comparisons using a // `comp` other than `operator<` -template -void c_sort_heap(RandomAccessContainer& sequence, Compare&& comp) { +template +void c_sort_heap(RandomAccessContainer& sequence, LessThan&& comp) { std::sort_heap(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), - std::forward(comp)); + std::forward(comp)); } // c_is_heap() @@ -1467,11 +1467,11 @@ bool c_is_heap(const RandomAccessContainer& sequence) { // Overload of c_is_heap() for performing heap comparisons using a // `comp` other than `operator<` -template -bool c_is_heap(const RandomAccessContainer& sequence, Compare&& comp) { +template +bool c_is_heap(const RandomAccessContainer& sequence, LessThan&& comp) { return std::is_heap(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), - std::forward(comp)); + std::forward(comp)); } // c_is_heap_until() @@ -1487,12 +1487,12 @@ c_is_heap_until(RandomAccessContainer& sequence) { // Overload of c_is_heap_until() for performing heap comparisons using a // `comp` other than `operator<` -template +template container_algorithm_internal::ContainerIter -c_is_heap_until(RandomAccessContainer& sequence, Compare&& comp) { +c_is_heap_until(RandomAccessContainer& sequence, LessThan&& comp) { return std::is_heap_until(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), - std::forward(comp)); + std::forward(comp)); } //------------------------------------------------------------------------------ @@ -1513,12 +1513,12 @@ container_algorithm_internal::ContainerIter c_min_element( // Overload of c_min_element() for performing a `comp` comparison other than // `operator<`. -template +template container_algorithm_internal::ContainerIter c_min_element( - Sequence& sequence, Compare&& comp) { + Sequence& sequence, LessThan&& comp) { return std::min_element(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), - std::forward(comp)); + std::forward(comp)); } // c_max_element() @@ -1535,12 +1535,12 @@ container_algorithm_internal::ContainerIter c_max_element( // Overload of c_max_element() for performing a `comp` comparison other than // `operator<`. -template +template container_algorithm_internal::ContainerIter c_max_element( - Sequence& sequence, Compare&& comp) { + Sequence& sequence, LessThan&& comp) { return std::max_element(container_algorithm_internal::c_begin(sequence), container_algorithm_internal::c_end(sequence), - std::forward(comp)); + std::forward(comp)); } // c_minmax_element() @@ -1558,12 +1558,12 @@ c_minmax_element(C& c) { // Overload of c_minmax_element() for performing `comp` comparisons other than // `operator<`. -template +template container_algorithm_internal::ContainerIterPairType -c_minmax_element(C& c, Compare&& comp) { +c_minmax_element(C& c, LessThan&& comp) { return std::minmax_element(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c), - std::forward(comp)); + std::forward(comp)); } //------------------------------------------------------------------------------ @@ -1588,15 +1588,15 @@ bool c_lexicographical_compare(Sequence1&& sequence1, Sequence2&& sequence2) { // Overload of c_lexicographical_compare() for performing a lexicographical // comparison using a `comp` operator instead of `operator<`. -template +template bool c_lexicographical_compare(Sequence1&& sequence1, Sequence2&& sequence2, - Compare&& comp) { + LessThan&& comp) { return std::lexicographical_compare( container_algorithm_internal::c_begin(sequence1), container_algorithm_internal::c_end(sequence1), container_algorithm_internal::c_begin(sequence2), container_algorithm_internal::c_end(sequence2), - std::forward(comp)); + std::forward(comp)); } // c_next_permutation() @@ -1612,11 +1612,11 @@ bool c_next_permutation(C& c) { // Overload of c_next_permutation() for performing a lexicographical // comparison using a `comp` operator instead of `operator<`. -template -bool c_next_permutation(C& c, Compare&& comp) { +template +bool c_next_permutation(C& c, LessThan&& comp) { return std::next_permutation(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c), - std::forward(comp)); + std::forward(comp)); } // c_prev_permutation() @@ -1632,11 +1632,11 @@ bool c_prev_permutation(C& c) { // Overload of c_prev_permutation() for performing a lexicographical // comparison using a `comp` operator instead of `operator<`. -template -bool c_prev_permutation(C& c, Compare&& comp) { +template +bool c_prev_permutation(C& c, LessThan&& comp) { return std::prev_permutation(container_algorithm_internal::c_begin(c), container_algorithm_internal::c_end(c), - std::forward(comp)); + std::forward(comp)); } //------------------------------------------------------------------------------ -- cgit v1.2.3 From 89c531c1e0d7372e2e7029f072a35495c5447d61 Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Thu, 29 Jul 2021 08:04:56 -0700 Subject: Export of internal Abseil changes -- e1a0989213908927f05002ab7697955ad7dc5632 by Martijn Vels : Introduce CordRepBtreeReader CordRepBtreeReader provides forward navigation on cord btrees with absolute positional (offset) context, iterating over btree data in absl::string_view chunks. PiperOrigin-RevId: 387585161 -- 206d298e2bccb998731995cb05717b31fa9d90ec by Abseil Team : Internal change PiperOrigin-RevId: 387577465 -- f07fafe8a400a4f5dfef186d1a3b61fb7f709fe5 by Abseil Team : This change adds debug-build enforcement that the inputs to absl::c_set_intersection are sorted, which is a prerequisite of std::set_intersection and required for correct operation of the algorithm. PiperOrigin-RevId: 387446657 -- 2ca15c6361bb758be7fb88cae82bf8489b4d3364 by Abseil Team : Change BadStatusOrAccess::what() to contain status_.ToString() This ensures that on uncaught exception propagation that would cause program termination, the message contains information on the error which caused the failure. Lazy initialization of what_ is a value judgement: if most callers are expected to call status() not what(), lazy initialization is correct. If most callers are expected to call what(), it should be initialized on construction to avoid atomic operation overhead. PiperOrigin-RevId: 387402243 -- 3e855084e104dc972a0c4385395e6d8e8465127f by Gennadiy Rozental : LSC: Standardize access to GoogleTest flags on GTEST_FLAG_GET/GTEST_FLAG_SET This change is necessary to move Googletest flags out of the testing:: namespace without breaking code. These new macros will continue to be required for code that needs to work both inside Google's monorepo and outside in OSS, but can be used anywhere inside the monorepo. PiperOrigin-RevId: 387396025 -- 1ccf5895a15059ef689af5c4817d7b84f73190be by Gennadiy Rozental : Import of CCTZ from GitHub. PiperOrigin-RevId: 387388496 GitOrigin-RevId: e1a0989213908927f05002ab7697955ad7dc5632 Change-Id: I3606d9ce29d909a3555e662e9df564202cf5068d --- CMake/AbseilDll.cmake | 2 + absl/algorithm/container.h | 12 +- absl/container/btree_test.cc | 4 +- absl/status/BUILD.bazel | 2 + absl/status/CMakeLists.txt | 1 + absl/status/statusor.cc | 36 ++- absl/status/statusor.h | 28 +- absl/status/statusor_test.cc | 70 +++-- absl/strings/BUILD.bazel | 19 ++ absl/strings/CMakeLists.txt | 20 ++ absl/strings/cord_ring_test.cc | 2 +- absl/strings/cord_test.cc | 18 +- absl/strings/internal/cord_rep_btree_reader.cc | 68 +++++ absl/strings/internal/cord_rep_btree_reader.h | 219 ++++++++++++++++ .../strings/internal/cord_rep_btree_reader_test.cc | 285 +++++++++++++++++++++ absl/time/internal/cctz/src/time_zone_info.cc | 39 ++- 16 files changed, 763 insertions(+), 62 deletions(-) create mode 100644 absl/strings/internal/cord_rep_btree_reader.cc create mode 100644 absl/strings/internal/cord_rep_btree_reader.h create mode 100644 absl/strings/internal/cord_rep_btree_reader_test.cc (limited to 'absl/algorithm/container.h') diff --git a/CMake/AbseilDll.cmake b/CMake/AbseilDll.cmake index 66c9e395..8bdf5a50 100644 --- a/CMake/AbseilDll.cmake +++ b/CMake/AbseilDll.cmake @@ -209,6 +209,8 @@ set(ABSL_INTERNAL_DLL_FILES "strings/internal/cord_rep_btree.h" "strings/internal/cord_rep_btree_navigator.cc" "strings/internal/cord_rep_btree_navigator.h" + "strings/internal/cord_rep_btree_reader.cc" + "strings/internal/cord_rep_btree_reader.h" "strings/internal/cord_rep_flat.h" "strings/internal/cord_rep_ring.cc" "strings/internal/cord_rep_ring.h" diff --git a/absl/algorithm/container.h b/absl/algorithm/container.h index 1652e7b0..c38a4a63 100644 --- a/absl/algorithm/container.h +++ b/absl/algorithm/container.h @@ -1262,7 +1262,7 @@ OutputIterator c_set_union(const C1& c1, const C2& c2, OutputIterator output, // c_set_intersection() // // Container-based version of the `std::set_intersection()` function -// to return an iterator containing the intersection of two containers. +// to return an iterator containing the intersection of two sorted containers. template ::value, @@ -1272,6 +1272,11 @@ template ::type> OutputIterator c_set_intersection(const C1& c1, const C2& c2, OutputIterator output) { + // In debug builds, ensure that both containers are sorted with respect to the + // default comparator. std::set_intersection requires the containers be sorted + // using operator<. + assert(absl::c_is_sorted(c1)); + assert(absl::c_is_sorted(c2)); return std::set_intersection(container_algorithm_internal::c_begin(c1), container_algorithm_internal::c_end(c1), container_algorithm_internal::c_begin(c2), @@ -1289,6 +1294,11 @@ template ::type> OutputIterator c_set_intersection(const C1& c1, const C2& c2, OutputIterator output, LessThan&& comp) { + // In debug builds, ensure that both containers are sorted with respect to the + // default comparator. std::set_intersection requires the containers be sorted + // using the same comparator. + assert(absl::c_is_sorted(c1, comp)); + assert(absl::c_is_sorted(c2, comp)); return std::set_intersection(container_algorithm_internal::c_begin(c1), container_algorithm_internal::c_end(c1), container_algorithm_internal::c_begin(c2), diff --git a/absl/container/btree_test.cc b/absl/container/btree_test.cc index d5d79151..d27cf271 100644 --- a/absl/container/btree_test.cc +++ b/absl/container/btree_test.cc @@ -595,7 +595,7 @@ void BtreeTest() { using V = typename remove_pair_const::type; const std::vector random_values = GenerateValuesWithSeed( absl::GetFlag(FLAGS_test_values), 4 * absl::GetFlag(FLAGS_test_values), - testing::GTEST_FLAG(random_seed)); + GTEST_FLAG_GET(random_seed)); unique_checker container; @@ -619,7 +619,7 @@ void BtreeMultiTest() { using V = typename remove_pair_const::type; const std::vector random_values = GenerateValuesWithSeed( absl::GetFlag(FLAGS_test_values), 4 * absl::GetFlag(FLAGS_test_values), - testing::GTEST_FLAG(random_seed)); + GTEST_FLAG_GET(random_seed)); multi_checker container; diff --git a/absl/status/BUILD.bazel b/absl/status/BUILD.bazel index 189bd73d..30df22ae 100644 --- a/absl/status/BUILD.bazel +++ b/absl/status/BUILD.bazel @@ -78,6 +78,7 @@ cc_library( copts = ABSL_DEFAULT_COPTS, deps = [ ":status", + "//absl/base", "//absl/base:core_headers", "//absl/base:raw_logging_internal", "//absl/meta:type_traits", @@ -96,6 +97,7 @@ cc_test( ":statusor", "//absl/base", "//absl/memory", + "//absl/strings", "//absl/types:any", "//absl/utility", "@com_google_googletest//:gtest_main", diff --git a/absl/status/CMakeLists.txt b/absl/status/CMakeLists.txt index 1248dff0..43898564 100644 --- a/absl/status/CMakeLists.txt +++ b/absl/status/CMakeLists.txt @@ -64,6 +64,7 @@ absl_cc_library( COPTS ${ABSL_DEFAULT_COPTS} DEPS + absl::base absl::status absl::core_headers absl::raw_logging_internal diff --git a/absl/status/statusor.cc b/absl/status/statusor.cc index b954b45e..96642b34 100644 --- a/absl/status/statusor.cc +++ b/absl/status/statusor.cc @@ -16,6 +16,7 @@ #include #include +#include "absl/base/call_once.h" #include "absl/base/internal/raw_logging.h" #include "absl/status/status.h" #include "absl/strings/str_cat.h" @@ -26,13 +27,44 @@ ABSL_NAMESPACE_BEGIN BadStatusOrAccess::BadStatusOrAccess(absl::Status status) : status_(std::move(status)) {} -BadStatusOrAccess::~BadStatusOrAccess() = default; +BadStatusOrAccess::BadStatusOrAccess(const BadStatusOrAccess& other) + : status_(other.status_) {} + +BadStatusOrAccess& BadStatusOrAccess::operator=( + const BadStatusOrAccess& other) { + // Ensure assignment is correct regardless of whether this->InitWhat() has + // already been called. + other.InitWhat(); + status_ = other.status_; + what_ = other.what_; + return *this; +} + +BadStatusOrAccess& BadStatusOrAccess::operator=(BadStatusOrAccess&& other) { + // Ensure assignment is correct regardless of whether this->InitWhat() has + // already been called. + other.InitWhat(); + status_ = std::move(other.status_); + what_ = std::move(other.what_); + return *this; +} + +BadStatusOrAccess::BadStatusOrAccess(BadStatusOrAccess&& other) + : status_(std::move(other.status_)) {} + const char* BadStatusOrAccess::what() const noexcept { - return "Bad StatusOr access"; + InitWhat(); + return what_.c_str(); } const absl::Status& BadStatusOrAccess::status() const { return status_; } +void BadStatusOrAccess::InitWhat() const { + absl::call_once(init_what_, [this] { + what_ = absl::StrCat("Bad StatusOr access: ", status_.ToString()); + }); +} + namespace internal_statusor { void Helper::HandleInvalidStatusCtorArg(absl::Status* status) { diff --git a/absl/status/statusor.h b/absl/status/statusor.h index b7c55cc8..235a3433 100644 --- a/absl/status/statusor.h +++ b/absl/status/statusor.h @@ -44,6 +44,7 @@ #include #include "absl/base/attributes.h" +#include "absl/base/call_once.h" #include "absl/meta/type_traits.h" #include "absl/status/internal/statusor_internal.h" #include "absl/status/status.h" @@ -72,13 +73,18 @@ ABSL_NAMESPACE_BEGIN class BadStatusOrAccess : public std::exception { public: explicit BadStatusOrAccess(absl::Status status); - ~BadStatusOrAccess() override; + ~BadStatusOrAccess() override = default; + + BadStatusOrAccess(const BadStatusOrAccess& other); + BadStatusOrAccess& operator=(const BadStatusOrAccess& other); + BadStatusOrAccess(BadStatusOrAccess&& other); + BadStatusOrAccess& operator=(BadStatusOrAccess&& other); // BadStatusOrAccess::what() // // Returns the associated explanatory string of the `absl::StatusOr` - // object's error code. This function only returns the string literal "Bad - // StatusOr Access" for cases when evaluating general exceptions. + // object's error code. This function contains information about the failing + // status, but its exact formatting may change and should not be depended on. // // The pointer of this string is guaranteed to be valid until any non-const // function is invoked on the exception object. @@ -91,7 +97,11 @@ class BadStatusOrAccess : public std::exception { const absl::Status& status() const; private: + void InitWhat() const; + absl::Status status_; + mutable absl::once_flag init_what_; + mutable std::string what_; }; // Returned StatusOr objects may not be ignored. @@ -437,8 +447,7 @@ class StatusOr : private internal_statusor::StatusOrData, T, U&&>>>>>::value, int> = 0> StatusOr(U&& u) // NOLINT - : StatusOr(absl::in_place, std::forward(u)) { - } + : StatusOr(absl::in_place, std::forward(u)) {} template < typename U = T, @@ -457,8 +466,7 @@ class StatusOr : private internal_statusor::StatusOrData, absl::negation>>::value, int> = 0> explicit StatusOr(U&& u) // NOLINT - : StatusOr(absl::in_place, std::forward(u)) { - } + : StatusOr(absl::in_place, std::forward(u)) {} // StatusOr::ok() // @@ -481,7 +489,7 @@ class StatusOr : private internal_statusor::StatusOrData, // Returns a reference to the current `absl::Status` contained within the // `absl::StatusOr`. If `absl::StatusOr` contains a `T`, then this // function returns `absl::OkStatus()`. - const Status& status() const &; + const Status& status() const&; Status status() &&; // StatusOr::value() @@ -661,7 +669,9 @@ StatusOr::StatusOr(absl::in_place_t, std::initializer_list ilist, : Base(absl::in_place, ilist, std::forward(args)...) {} template -const Status& StatusOr::status() const & { return this->status_; } +const Status& StatusOr::status() const& { + return this->status_; +} template Status StatusOr::status() && { return ok() ? OkStatus() : std::move(this->status_); diff --git a/absl/status/statusor_test.cc b/absl/status/statusor_test.cc index c2e8fb7e..7cae90e1 100644 --- a/absl/status/statusor_test.cc +++ b/absl/status/statusor_test.cc @@ -17,6 +17,7 @@ #include #include #include +#include #include #include @@ -25,6 +26,7 @@ #include "absl/base/casts.h" #include "absl/memory/memory.h" #include "absl/status/status.h" +#include "absl/strings/string_view.h" #include "absl/types/any.h" #include "absl/utility/utility.h" @@ -34,6 +36,7 @@ using ::testing::AllOf; using ::testing::AnyWith; using ::testing::ElementsAre; using ::testing::Field; +using ::testing::HasSubstr; using ::testing::Ne; using ::testing::Not; using ::testing::Pointee; @@ -257,9 +260,9 @@ TEST(StatusOr, TestMoveOnlyInitializationFromTemporaryByValueOrDie) { TEST(StatusOr, TestValueOrDieOverloadForConstTemporary) { static_assert( - std::is_same&&>().value())>(), + std::is_same< + const int&&, + decltype(std::declval&&>().value())>(), "value() for const temporaries should return const T&&"); } @@ -303,20 +306,57 @@ TEST(StatusOr, StatusCtorForwards) { EXPECT_NE(status.message(), "Some error"); } +TEST(BadStatusOrAccessTest, CopyConstructionWhatOk) { + absl::Status error = + absl::InternalError("some arbitrary message too big for the sso buffer"); + absl::BadStatusOrAccess e1{error}; + absl::BadStatusOrAccess e2{e1}; + EXPECT_THAT(e1.what(), HasSubstr(error.ToString())); + EXPECT_THAT(e2.what(), HasSubstr(error.ToString())); +} + +TEST(BadStatusOrAccessTest, CopyAssignmentWhatOk) { + absl::Status error = + absl::InternalError("some arbitrary message too big for the sso buffer"); + absl::BadStatusOrAccess e1{error}; + absl::BadStatusOrAccess e2{absl::InternalError("other")}; + e2 = e1; + EXPECT_THAT(e1.what(), HasSubstr(error.ToString())); + EXPECT_THAT(e2.what(), HasSubstr(error.ToString())); +} + +TEST(BadStatusOrAccessTest, MoveConstructionWhatOk) { + absl::Status error = + absl::InternalError("some arbitrary message too big for the sso buffer"); + absl::BadStatusOrAccess e1{error}; + absl::BadStatusOrAccess e2{std::move(e1)}; + EXPECT_THAT(e2.what(), HasSubstr(error.ToString())); +} + +TEST(BadStatusOrAccessTest, MoveAssignmentWhatOk) { + absl::Status error = + absl::InternalError("some arbitrary message too big for the sso buffer"); + absl::BadStatusOrAccess e1{error}; + absl::BadStatusOrAccess e2{absl::InternalError("other")}; + e2 = std::move(e1); + EXPECT_THAT(e2.what(), HasSubstr(error.ToString())); +} + // Define `EXPECT_DEATH_OR_THROW` to test the behavior of `StatusOr::value`, // which either throws `BadStatusOrAccess` or `LOG(FATAL)` based on whether // exceptions are enabled. #ifdef ABSL_HAVE_EXCEPTIONS -#define EXPECT_DEATH_OR_THROW(statement, status_) \ - EXPECT_THROW( \ - { \ - try { \ - statement; \ - } catch (const absl::BadStatusOrAccess& e) { \ - EXPECT_EQ(e.status(), status_); \ - throw; \ - } \ - }, \ +#define EXPECT_DEATH_OR_THROW(statement, status_) \ + EXPECT_THROW( \ + { \ + try { \ + statement; \ + } catch (const absl::BadStatusOrAccess& e) { \ + EXPECT_EQ(e.status(), status_); \ + EXPECT_THAT(e.what(), HasSubstr(e.status().ToString())); \ + throw; \ + } \ + }, \ absl::BadStatusOrAccess); #else // ABSL_HAVE_EXCEPTIONS #define EXPECT_DEATH_OR_THROW(statement, status) \ @@ -412,8 +452,6 @@ TEST(StatusOr, TestStatusCtor) { EXPECT_EQ(thing.status().code(), absl::StatusCode::kCancelled); } - - TEST(StatusOr, TestValueCtor) { const int kI = 4; const absl::StatusOr thing(kI); @@ -1300,8 +1338,6 @@ TEST(StatusOr, TestPointerDefaultCtor) { EXPECT_EQ(thing.status().code(), absl::StatusCode::kUnknown); } - - TEST(StatusOr, TestPointerStatusCtor) { absl::StatusOr thing(absl::CancelledError()); EXPECT_FALSE(thing.ok()); diff --git a/absl/strings/BUILD.bazel b/absl/strings/BUILD.bazel index 7e0245a3..9720b683 100644 --- a/absl/strings/BUILD.bazel +++ b/absl/strings/BUILD.bazel @@ -271,6 +271,7 @@ cc_library( "internal/cord_internal.cc", "internal/cord_rep_btree.cc", "internal/cord_rep_btree_navigator.cc", + "internal/cord_rep_btree_reader.cc", "internal/cord_rep_consume.cc", "internal/cord_rep_ring.cc", ], @@ -278,6 +279,7 @@ cc_library( "internal/cord_internal.h", "internal/cord_rep_btree.h", "internal/cord_rep_btree_navigator.h", + "internal/cord_rep_btree_reader.h", "internal/cord_rep_consume.h", "internal/cord_rep_flat.h", "internal/cord_rep_ring.h", @@ -336,6 +338,23 @@ cc_test( ], ) +cc_test( + name = "cord_rep_btree_reader_test", + size = "medium", + srcs = ["internal/cord_rep_btree_reader_test.cc"], + copts = ABSL_TEST_COPTS, + visibility = ["//visibility:private"], + deps = [ + ":cord", + ":cord_internal", + ":cord_rep_test_util", + ":strings", + "//absl/base:config", + "//absl/base:raw_logging_internal", + "@com_google_googletest//:gtest_main", + ], +) + cc_library( name = "cordz_update_tracker", hdrs = ["internal/cordz_update_tracker.h"], diff --git a/absl/strings/CMakeLists.txt b/absl/strings/CMakeLists.txt index e55c035d..88f076a8 100644 --- a/absl/strings/CMakeLists.txt +++ b/absl/strings/CMakeLists.txt @@ -557,6 +557,7 @@ absl_cc_library( "internal/cord_internal.h" "internal/cord_rep_btree.h" "internal/cord_rep_btree_navigator.h" + "internal/cord_rep_btree_reader.h" "internal/cord_rep_consume.h" "internal/cord_rep_flat.h" "internal/cord_rep_ring.h" @@ -565,6 +566,7 @@ absl_cc_library( "internal/cord_internal.cc" "internal/cord_rep_btree.cc" "internal/cord_rep_btree_navigator.cc" + "internal/cord_rep_btree_reader.cc" "internal/cord_rep_consume.cc" "internal/cord_rep_ring.cc" COPTS @@ -977,6 +979,24 @@ absl_cc_test( GTest::gmock_main ) +absl_cc_test( + NAME + cord_rep_btree_reader_test + SRCS + "internal/cord_rep_btree_reader_test.cc" + COPTS + ${ABSL_TEST_COPTS} + DEPS + absl::base + absl::config + absl::cord_internal + absl::cord_rep_test_util + absl::core_headers + absl::raw_logging_internal + absl::strings + GTest::gmock_main +) + absl_cc_test( NAME cord_ring_test diff --git a/absl/strings/cord_ring_test.cc b/absl/strings/cord_ring_test.cc index b1787edf..f1318595 100644 --- a/absl/strings/cord_ring_test.cc +++ b/absl/strings/cord_ring_test.cc @@ -275,7 +275,7 @@ CordRepConcat* MakeConcat(CordRep* left, CordRep* right, int depth = 0) { enum Composition { kMix, kAppend, kPrepend }; Composition RandomComposition() { - RandomEngine rng(testing::GTEST_FLAG(random_seed)); + RandomEngine rng(GTEST_FLAG_GET(random_seed)); return (rng() & 1) ? kMix : ((rng() & 1) ? kAppend : kPrepend); } diff --git a/absl/strings/cord_test.cc b/absl/strings/cord_test.cc index 14eca155..597378cc 100644 --- a/absl/strings/cord_test.cc +++ b/absl/strings/cord_test.cc @@ -361,7 +361,7 @@ TEST(Cord, StartsEndsWith) { } TEST(Cord, Subcord) { - RandomEngine rng(testing::GTEST_FLAG(random_seed)); + RandomEngine rng(GTEST_FLAG_GET(random_seed)); const std::string s = RandomLowercaseString(&rng, 1024); absl::Cord a; @@ -570,7 +570,7 @@ TEST(Cord, Flatten) { VerifyFlatten(absl::MakeFragmentedCord({"small ", "fragmented ", "cord"})); // Test with a cord that is longer than the largest flat buffer - RandomEngine rng(testing::GTEST_FLAG(random_seed)); + RandomEngine rng(GTEST_FLAG_GET(random_seed)); VerifyFlatten(absl::Cord(RandomLowercaseString(&rng, 8192))); } @@ -937,7 +937,7 @@ static void TestCompare(const absl::Cord& c, const absl::Cord& d, } TEST(Compare, ComparisonIsUnsigned) { - RandomEngine rng(testing::GTEST_FLAG(random_seed)); + RandomEngine rng(GTEST_FLAG_GET(random_seed)); std::uniform_int_distribution uniform_uint8(0, 255); char x = static_cast(uniform_uint8(rng)); TestCompare( @@ -947,7 +947,7 @@ TEST(Compare, ComparisonIsUnsigned) { TEST(Compare, RandomComparisons) { const int kIters = 5000; - RandomEngine rng(testing::GTEST_FLAG(random_seed)); + RandomEngine rng(GTEST_FLAG_GET(random_seed)); int n = GetUniformRandomUpTo(&rng, 5000); absl::Cord a[] = {MakeExternalCord(n), @@ -1082,7 +1082,7 @@ TEST(ConstructFromExternal, ReleaserInvoked) { } TEST(ConstructFromExternal, CompareContents) { - RandomEngine rng(testing::GTEST_FLAG(random_seed)); + RandomEngine rng(GTEST_FLAG_GET(random_seed)); for (int length = 1; length <= 2048; length *= 2) { std::string data = RandomLowercaseString(&rng, length); @@ -1098,7 +1098,7 @@ TEST(ConstructFromExternal, CompareContents) { } TEST(ConstructFromExternal, LargeReleaser) { - RandomEngine rng(testing::GTEST_FLAG(random_seed)); + RandomEngine rng(GTEST_FLAG_GET(random_seed)); constexpr size_t kLength = 256; std::string data = RandomLowercaseString(&rng, kLength); std::array data_array; @@ -1323,7 +1323,7 @@ TEST(Cord, DiabolicalGrowth) { // resulting cord. // TODO(b/183983616): Apply some minimum compaction when copying a shared // source cord into a mutable copy for updates in CordRepRing. - RandomEngine rng(testing::GTEST_FLAG(random_seed)); + RandomEngine rng(GTEST_FLAG_GET(random_seed)); const std::string expected = RandomLowercaseString(&rng, 5000); absl::Cord cord; for (char c : expected) { @@ -1483,7 +1483,7 @@ TEST(CordChunkIterator, Operations) { VerifyChunkIterator(reused_nodes_cord, expected_chunks); } - RandomEngine rng(testing::GTEST_FLAG(random_seed)); + RandomEngine rng(GTEST_FLAG_GET(random_seed)); absl::Cord flat_cord(RandomLowercaseString(&rng, 256)); absl::Cord subcords; for (int i = 0; i < 128; ++i) subcords.Prepend(flat_cord.Subcord(i, 128)); @@ -1621,7 +1621,7 @@ TEST(CordCharIterator, Operations) { VerifyCharIterator(reused_nodes_cord); } - RandomEngine rng(testing::GTEST_FLAG(random_seed)); + RandomEngine rng(GTEST_FLAG_GET(random_seed)); absl::Cord flat_cord(RandomLowercaseString(&rng, 256)); absl::Cord subcords; for (int i = 0; i < 4; ++i) subcords.Prepend(flat_cord.Subcord(16 * i, 128)); diff --git a/absl/strings/internal/cord_rep_btree_reader.cc b/absl/strings/internal/cord_rep_btree_reader.cc new file mode 100644 index 00000000..3ba43144 --- /dev/null +++ b/absl/strings/internal/cord_rep_btree_reader.cc @@ -0,0 +1,68 @@ +// Copyright 2021 The Abseil Authors +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#include "absl/strings/internal/cord_rep_btree_reader.h" + +#include + +#include "absl/base/config.h" +#include "absl/strings/internal/cord_internal.h" +#include "absl/strings/internal/cord_rep_btree.h" +#include "absl/strings/internal/cord_rep_btree_navigator.h" +#include "absl/strings/internal/cord_rep_flat.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace cord_internal { + +absl::string_view CordRepBtreeReader::Read(size_t n, size_t chunk_size, + CordRep*& tree) { + assert(chunk_size <= navigator_.Current()->length); + + // If chunk_size is non-zero, we need to start inside last returned edge. + // Else we start reading at the next data edge of the tree. + CordRep* edge = chunk_size ? navigator_.Current() : navigator_.Next(); + const size_t offset = chunk_size ? edge->length - chunk_size : 0; + + // Read the sub tree and verify we got what we wanted. + ReadResult result = navigator_.Read(offset, n); + tree = result.tree; + + // If the data returned in `tree` was covered entirely by `chunk_size`, i.e., + // read from the 'previous' edge, we did not consume any additional data, and + // can directly return the substring into the current data edge as the next + // chunk. We can easily establish from the above code that `navigator_.Next()` + // has not been called as that requires `chunk_size` to be zero. + if (n < chunk_size) return CordRepBtree::EdgeData(edge).substr(result.n); + + // The amount of data taken from the last edge is `chunk_size` and `result.n` + // contains the offset into the current edge trailing the read data (which can + // be 0). As the call to `navigator_.Read()` could have consumed all remaining + // data, calling `navigator_.Current()` is not safe before checking if we + // already consumed all remaining data. + const size_t consumed_by_read = n - chunk_size - result.n; + if (consumed_ + consumed_by_read >= length()) { + consumed_ = length(); + return {}; + } + + // We did not read all data, return remaining data from current edge. + edge = navigator_.Current(); + consumed_ += consumed_by_read + edge->length; + return CordRepBtree::EdgeData(edge).substr(result.n); +} + +} // namespace cord_internal +ABSL_NAMESPACE_END +} // namespace absl diff --git a/absl/strings/internal/cord_rep_btree_reader.h b/absl/strings/internal/cord_rep_btree_reader.h new file mode 100644 index 00000000..c19fa43d --- /dev/null +++ b/absl/strings/internal/cord_rep_btree_reader.h @@ -0,0 +1,219 @@ +// Copyright 2021 The Abseil Authors +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#ifndef ABSL_STRINGS_INTERNAL_CORD_REP_BTREE_READER_H_ +#define ABSL_STRINGS_INTERNAL_CORD_REP_BTREE_READER_H_ + +#include + +#include "absl/base/config.h" +#include "absl/strings/internal/cord_internal.h" +#include "absl/strings/internal/cord_rep_btree.h" +#include "absl/strings/internal/cord_rep_btree_navigator.h" +#include "absl/strings/internal/cord_rep_flat.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace cord_internal { + +// CordRepBtreeReader implements logic to iterate over cord btrees. +// References to the underlying data are returned as absl::string_view values. +// The most typical use case is a forward only iteration over tree data. +// The class also provides `Skip()`, `Seek()` and `Read()` methods similar to +// CordRepBtreeNavigator that allow more advanced navigation. The class provides +// a `consumed` property which contains the end offset of the chunk last +// returned to the user which is useful in cord iteration logic. +// +// Example: iterate over all data inside a cord btree: +// +// CordRepBtreeReader reader; +// for (string_view sv = reader.Init(tree); !sv.Empty(); sv = sv.Next()) { +// DoSomethingWithDataIn(sv); +// } +// +// All navigation methods always return the next 'chunk' of data. The class +// assumes that all data is directly 'consumed' by the caller. For example: +// invoking `Skip()` will skip the desired number of bytes, and directly +// read and return the next chunk of data directly after the skipped bytes. +// +// Example: iterate over all data inside a btree skipping the first 100 bytes: +// +// CordRepBtreeReader reader; +// absl::string_view sv = reader.Init(tree); +// if (sv.length() > 100) { +// sv.RemovePrefix(100); +// } else { +// sv = reader.Skip(100 - sv.length()); +// } +// while (!sv.empty()) { +// DoSomethingWithDataIn(sv); +// absl::string_view sv = reader.Next(); +// } +// +// It is important to notice that `consumed` represents the end position of the +// last data edge returned to the caller, not the cumulative data returned to +// the caller which can be less in cases of skipping or seeking over data. +// +// For example, consider a cord btree with five data edges: "abc", "def", "ghi", +// "jkl" and "mno": +// +// absl::string_view sv; +// CordRepBtreeReader reader; +// +// sv = reader.Init(tree); // sv = "abc", reader.consumed() = 3 +// sv = reader.Skip(4); // sv = "hi", reader.consumed() = 9 +// sv = reader.Skip(2); // sv = "l", reader.consumed() = 12 +// sv = reader.Next(); // sv = "mno", reader.consumed() = 15 +// +// In the above example, `reader.consumed()` reflects the data edges iterated +// over or skipped by the reader, not the amount of data 'consumed' by the +// caller. +class CordRepBtreeReader { + public: + using ReadResult = CordRepBtreeNavigator::ReadResult; + using Position = CordRepBtreeNavigator::Position; + + // Returns true if this instance is not empty. + explicit operator bool() const { return navigator_.btree() != nullptr; } + + // Returns the tree referenced by this instance or nullptr if empty. + CordRepBtree* btree() const { return navigator_.btree(); } + + // Returns the current data edge inside the referenced btree. + // Requires that the current instance is not empty. + CordRep* node() const { return navigator_.Current(); } + + // Returns the length of the referenced tree. + // Requires that the current instance is not empty. + size_t length() const; + + // Returns the end offset of the last navigated to chunk, which represents the + // total bytes 'consumed' relative to the start of the tree. The returned + // value is never zero. For example, initializing a reader with a tree with a + // first data edge of 19 bytes will return `consumed() = 19`. See also the + // class comments on the meaning of `consumed`. + // Requires that the current instance is not empty. + size_t consumed() const; + + // Resets this instance to an empty value. + void Reset() { navigator_.Reset(); } + + // Initializes this instance with `tree`. `tree` must not be null. + // Returns a reference to the first data edge of the provided tree. + absl::string_view Init(CordRepBtree* tree); + + // Navigates to and returns the next data edge of the referenced tree. + // Returns an empty string_view if an attempt is made to read beyond the end + // of the tree, i.e.: if `remaining()` is zero indicating an EOF condition. + // Requires that the current instance is not empty. + absl::string_view Next(); + + // Skips the provided amount of bytes and returns a reference to the data + // directly following the skipped bytes. + absl::string_view Skip(size_t skip); + + // Reads `n` bytes into `tree`. + // If `chunk_size` is zero, starts reading at the next data edge. If + // `chunk_size` is non zero, the read starts at the last `chunk_size` bytes of + // the last returned data edge. Effectively, this means that the read starts + // at offset `consumed() - chunk_size`. + // Requires that `chunk_size` is less than or equal to the length of the + // last returned data edge. The purpose of `chunk_size` is to simplify code + // partially consuming a returned chunk and wanting to include the remaining + // bytes in the Read call. For example, the below code will read 1000 bytes of + // data into a cord tree if the first chunk starts with "big:": + // + // CordRepBtreeReader reader; + // absl::string_view sv = reader.Init(tree); + // if (absl::StartsWith(sv, "big:")) { + // CordRepBtree tree; + // sv = reader.Read(1000, sv.size() - 4 /* "big:" */, &tree); + // } + // + // This method will return an empty string view if all remaining data was + // read. If `n` exceeded the amount of remaining data this function will + // return an empty string view and `tree` will be set to nullptr. + // In both cases, `consumed` will be set to `length`. + absl::string_view Read(size_t n, size_t chunk_size, CordRep*& tree); + + // Navigates to the chunk at offset `offset`. + // Returns a reference into the navigated to chunk, adjusted for the relative + // position of `offset` into that chunk. For example, calling `Seek(13)` on a + // cord tree containing 2 chunks of 10 and 20 bytes respectively will return + // a string view into the second chunk starting at offset 3 with a size of 17. + // Returns an empty string view if `offset` is equal to or greater than the + // length of the referenced tree. + absl::string_view Seek(size_t offset); + + private: + size_t consumed_; + CordRepBtreeNavigator navigator_; +}; + +inline size_t CordRepBtreeReader::length() const { + assert(btree() != nullptr); + return btree()->length; +} + +inline size_t CordRepBtreeReader::consumed() const { + assert(btree() != nullptr); + return consumed_; +} + +inline absl::string_view CordRepBtreeReader::Init(CordRepBtree* tree) { + assert(tree != nullptr); + const CordRep* edge = navigator_.InitFirst(tree); + consumed_ = edge->length; + return CordRepBtree::EdgeData(edge); +} + +inline absl::string_view CordRepBtreeReader::Next() { + assert(consumed() < length()); + const CordRep* edge = navigator_.Next(); + assert(edge != nullptr); + consumed_ += edge->length; + return CordRepBtree::EdgeData(edge); +} + +inline absl::string_view CordRepBtreeReader::Skip(size_t skip) { + // As we are always positioned on the last 'consumed' edge, we + // need to skip the current edge as well as `skip`. + const size_t edge_length = navigator_.Current()->length; + CordRepBtreeNavigator::Position pos = navigator_.Skip(skip + edge_length); + if (ABSL_PREDICT_FALSE(pos.edge == nullptr)) { + consumed_ = length(); + return {}; + } + // The combined length of all edges skipped before `pos.edge` is `skip - + // pos.offset`, all of which are 'consumed', as well as the current edge. + consumed_ += skip - pos.offset + pos.edge->length; + return CordRepBtree::EdgeData(pos.edge).substr(pos.offset); +} + +inline absl::string_view CordRepBtreeReader::Seek(size_t offset) { + const CordRepBtreeNavigator::Position pos = navigator_.Seek(offset); + if (ABSL_PREDICT_FALSE(pos.edge == nullptr)) { + consumed_ = length(); + return {}; + } + absl::string_view chunk = CordRepBtree::EdgeData(pos.edge).substr(pos.offset); + consumed_ = offset + chunk.length(); + return chunk; +} + +} // namespace cord_internal +ABSL_NAMESPACE_END +} // namespace absl + +#endif // ABSL_STRINGS_INTERNAL_CORD_REP_BTREE_READER_H_ diff --git a/absl/strings/internal/cord_rep_btree_reader_test.cc b/absl/strings/internal/cord_rep_btree_reader_test.cc new file mode 100644 index 00000000..44d3365f --- /dev/null +++ b/absl/strings/internal/cord_rep_btree_reader_test.cc @@ -0,0 +1,285 @@ +// Copyright 2021 The Abseil Authors +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#include "absl/strings/internal/cord_rep_btree_reader.h" + +#include +#include +#include +#include + +#include "gmock/gmock.h" +#include "gtest/gtest.h" +#include "absl/base/config.h" +#include "absl/base/internal/raw_logging.h" +#include "absl/strings/cord.h" +#include "absl/strings/internal/cord_internal.h" +#include "absl/strings/internal/cord_rep_btree.h" +#include "absl/strings/internal/cord_rep_test_util.h" +#include "absl/strings/string_view.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace cord_internal { +namespace { + +using ::testing::Eq; +using ::testing::IsEmpty; +using ::testing::Ne; +using ::testing::Not; + +using ::absl::cordrep_testing::CordRepBtreeFromFlats; +using ::absl::cordrep_testing::MakeFlat; +using ::absl::cordrep_testing::CordToString; +using ::absl::cordrep_testing::CreateFlatsFromString; +using ::absl::cordrep_testing::CreateRandomString; + +using ReadResult = CordRepBtreeReader::ReadResult; + +TEST(CordRepBtreeReaderTest, Next) { + constexpr size_t kChars = 3; + const size_t cap = CordRepBtree::kMaxCapacity; + int counts[] = {1, 2, cap, cap * cap, cap * cap + 1, cap * cap * 2 + 17}; + + for (int count : counts) { + std::string data = CreateRandomString(count * kChars); + std::vector flats = CreateFlatsFromString(data, kChars); + CordRepBtree* node = CordRepBtreeFromFlats(flats); + + CordRepBtreeReader reader; + absl::string_view chunk = reader.Init(node); + EXPECT_THAT(chunk, Eq(data.substr(0, chunk.length()))); + + size_t consumed = chunk.length(); + EXPECT_THAT(reader.consumed(), Eq(consumed)); + + while (consumed < data.length()) { + chunk = reader.Next(); + EXPECT_THAT(chunk, Eq(data.substr(consumed, chunk.length()))); + + consumed += chunk.length(); + EXPECT_THAT(reader.consumed(), Eq(consumed)); + } + + EXPECT_THAT(consumed, Eq(data.length())); + EXPECT_THAT(reader.consumed(), Eq(data.length())); + + CordRep::Unref(node); + } +} + +TEST(CordRepBtreeReaderTest, Skip) { + constexpr size_t kChars = 3; + const size_t cap = CordRepBtree::kMaxCapacity; + int counts[] = {1, 2, cap, cap * cap, cap * cap + 1, cap * cap * 2 + 17}; + + for (int count : counts) { + std::string data = CreateRandomString(count * kChars); + std::vector flats = CreateFlatsFromString(data, kChars); + CordRepBtree* node = CordRepBtreeFromFlats(flats); + + for (size_t skip1 = 0; skip1 < data.length() - kChars; ++skip1) { + for (size_t skip2 = 0; skip2 < data.length() - kChars; ++skip2) { + CordRepBtreeReader reader; + absl::string_view chunk = reader.Init(node); + size_t consumed = chunk.length(); + + chunk = reader.Skip(skip1); + ASSERT_THAT(chunk, Eq(data.substr(consumed + skip1, chunk.length()))); + consumed += chunk.length() + skip1; + ASSERT_THAT(reader.consumed(), Eq(consumed)); + + if (consumed >= data.length()) continue; + + size_t skip = std::min(data.length() - consumed - 1, skip2); + chunk = reader.Skip(skip); + ASSERT_THAT(chunk, Eq(data.substr(consumed + skip, chunk.length()))); + } + } + + CordRep::Unref(node); + } +} + +TEST(CordRepBtreeReaderTest, SkipBeyondLength) { + CordRepBtree* tree = CordRepBtree::Create(MakeFlat("abc")); + tree = CordRepBtree::Append(tree, MakeFlat("def")); + CordRepBtreeReader reader; + reader.Init(tree); + EXPECT_THAT(reader.Skip(100), IsEmpty()); + EXPECT_THAT(reader.consumed(), Eq(6)); + CordRep::Unref(tree); +} + +TEST(CordRepBtreeReaderTest, Seek) { + constexpr size_t kChars = 3; + const size_t cap = CordRepBtree::kMaxCapacity; + int counts[] = {1, 2, cap, cap * cap, cap * cap + 1, cap * cap * 2 + 17}; + + for (int count : counts) { + std::string data = CreateRandomString(count * kChars); + std::vector flats = CreateFlatsFromString(data, kChars); + CordRepBtree* node = CordRepBtreeFromFlats(flats); + + for (size_t seek = 0; seek < data.length() - 1; ++seek) { + CordRepBtreeReader reader; + reader.Init(node); + absl::string_view chunk = reader.Seek(seek); + ASSERT_THAT(chunk, Not(IsEmpty())); + ASSERT_THAT(chunk, Eq(data.substr(seek, chunk.length()))); + ASSERT_THAT(reader.consumed(), Eq(seek + chunk.length())); + } + + CordRep::Unref(node); + } +} + +TEST(CordRepBtreeReaderTest, SeekBeyondLength) { + CordRepBtree* tree = CordRepBtree::Create(MakeFlat("abc")); + tree = CordRepBtree::Append(tree, MakeFlat("def")); + CordRepBtreeReader reader; + reader.Init(tree); + EXPECT_THAT(reader.Seek(6), IsEmpty()); + EXPECT_THAT(reader.consumed(), Eq(6)); + EXPECT_THAT(reader.Seek(100), IsEmpty()); + EXPECT_THAT(reader.consumed(), Eq(6)); + CordRep::Unref(tree); +} + +TEST(CordRepBtreeReaderTest, Read) { + std::string data = "abcdefghijklmno"; + std::vector flats = CreateFlatsFromString(data, 5); + CordRepBtree* node = CordRepBtreeFromFlats(flats); + + CordRep* tree; + CordRepBtreeReader reader; + absl::string_view chunk; + + // Read zero bytes + chunk = reader.Init(node); + chunk = reader.Read(0, chunk.length(), tree); + EXPECT_THAT(tree, Eq(nullptr)); + EXPECT_THAT(chunk, Eq("abcde")); + EXPECT_THAT(reader.consumed(), Eq(5)); + EXPECT_THAT(reader.Next(), Eq("fghij")); + + // Read in full + chunk = reader.Init(node); + chunk = reader.Read(15, chunk.length(), tree); + EXPECT_THAT(tree, Ne(nullptr)); + EXPECT_THAT(CordToString(tree), Eq("abcdefghijklmno")); + EXPECT_THAT(chunk, Eq("")); + EXPECT_THAT(reader.consumed(), Eq(15)); + CordRep::Unref(tree); + + // Read < chunk bytes + chunk = reader.Init(node); + chunk = reader.Read(3, chunk.length(), tree); + ASSERT_THAT(tree, Ne(nullptr)); + EXPECT_THAT(CordToString(tree), Eq("abc")); + EXPECT_THAT(chunk, Eq("de")); + EXPECT_THAT(reader.consumed(), Eq(5)); + EXPECT_THAT(reader.Next(), Eq("fghij")); + CordRep::Unref(tree); + + // Read < chunk bytes at offset + chunk = reader.Init(node); + chunk = reader.Read(2, chunk.length() - 2, tree); + ASSERT_THAT(tree, Ne(nullptr)); + EXPECT_THAT(CordToString(tree), Eq("cd")); + EXPECT_THAT(chunk, Eq("e")); + EXPECT_THAT(reader.consumed(), Eq(5)); + EXPECT_THAT(reader.Next(), Eq("fghij")); + CordRep::Unref(tree); + + // Read from consumed chunk + chunk = reader.Init(node); + chunk = reader.Read(3, 0, tree); + ASSERT_THAT(tree, Ne(nullptr)); + EXPECT_THAT(CordToString(tree), Eq("fgh")); + EXPECT_THAT(chunk, Eq("ij")); + EXPECT_THAT(reader.consumed(), Eq(10)); + EXPECT_THAT(reader.Next(), Eq("klmno")); + CordRep::Unref(tree); + + // Read across chunks + chunk = reader.Init(node); + chunk = reader.Read(12, chunk.length() - 2, tree); + ASSERT_THAT(tree, Ne(nullptr)); + EXPECT_THAT(CordToString(tree), Eq("cdefghijklmn")); + EXPECT_THAT(chunk, Eq("o")); + EXPECT_THAT(reader.consumed(), Eq(15)); + CordRep::Unref(tree); + + // Read across chunks landing on exact edge boundary + chunk = reader.Init(node); + chunk = reader.Read(10 - 2, chunk.length() - 2, tree); + ASSERT_THAT(tree, Ne(nullptr)); + EXPECT_THAT(CordToString(tree), Eq("cdefghij")); + EXPECT_THAT(chunk, Eq("klmno")); + EXPECT_THAT(reader.consumed(), Eq(15)); + CordRep::Unref(tree); + + CordRep::Unref(node); +} + +TEST(CordRepBtreeReaderTest, ReadExhaustive) { + constexpr size_t kChars = 3; + const size_t cap = CordRepBtree::kMaxCapacity; + int counts[] = {1, 2, cap, cap * cap + 1, cap * cap * cap * 2 + 17}; + + for (int count : counts) { + std::string data = CreateRandomString(count * kChars); + std::vector flats = CreateFlatsFromString(data, kChars); + CordRepBtree* node = CordRepBtreeFromFlats(flats); + + for (size_t read_size : {kChars - 1, kChars, kChars + 7, cap * cap}) { + CordRepBtreeReader reader; + absl::string_view chunk = reader.Init(node); + + // `consumed` tracks the end of last consumed chunk which is the start of + // the next chunk: we always read with `chunk_size = chunk.length()`. + size_t consumed = 0; + size_t remaining = data.length(); + while (remaining > 0) { + CordRep* tree; + size_t n = (std::min)(remaining, read_size); + chunk = reader.Read(n, chunk.length(), tree); + EXPECT_THAT(tree, Ne(nullptr)); + if (tree) { + EXPECT_THAT(CordToString(tree), Eq(data.substr(consumed, n))); + CordRep::Unref(tree); + } + + consumed += n; + remaining -= n; + EXPECT_THAT(reader.consumed(), Eq(consumed + chunk.length())); + + if (remaining > 0) { + ASSERT_FALSE(chunk.empty()); + ASSERT_THAT(chunk, Eq(data.substr(consumed, chunk.length()))); + } else { + ASSERT_TRUE(chunk.empty()) << chunk; + } + } + } + + CordRep::Unref(node); + } +} + +} // namespace +} // namespace cord_internal +ABSL_NAMESPACE_END +} // namespace absl diff --git a/absl/time/internal/cctz/src/time_zone_info.cc b/absl/time/internal/cctz/src/time_zone_info.cc index 8039353e..f2777d91 100644 --- a/absl/time/internal/cctz/src/time_zone_info.cc +++ b/absl/time/internal/cctz/src/time_zone_info.cc @@ -43,6 +43,7 @@ #include #include #include +#include #include "absl/base/config.h" #include "absl/time/internal/cctz/include/cctz/civil_time.h" @@ -576,14 +577,17 @@ bool TimeZoneInfo::Load(ZoneInfoSource* zip) { namespace { +using FilePtr = std::unique_ptr; + // fopen(3) adaptor. -inline FILE* FOpen(const char* path, const char* mode) { +inline FilePtr FOpen(const char* path, const char* mode) { #if defined(_MSC_VER) FILE* fp; if (fopen_s(&fp, path, mode) != 0) fp = nullptr; - return fp; + return FilePtr(fp, fclose); #else - return fopen(path, mode); // TODO: Enable the close-on-exec flag. + // TODO: Enable the close-on-exec flag. + return FilePtr(fopen(path, mode), fclose); #endif } @@ -611,11 +615,11 @@ class FileZoneInfoSource : public ZoneInfoSource { protected: explicit FileZoneInfoSource( - FILE* fp, std::size_t len = std::numeric_limits::max()) - : fp_(fp, fclose), len_(len) {} + FilePtr fp, std::size_t len = std::numeric_limits::max()) + : fp_(std::move(fp)), len_(len) {} private: - std::unique_ptr fp_; + FilePtr fp_; std::size_t len_; }; @@ -644,17 +648,9 @@ std::unique_ptr FileZoneInfoSource::Open( path.append(name, pos, std::string::npos); // Open the zoneinfo file. - FILE* fp = FOpen(path.c_str(), "rb"); - if (fp == nullptr) return nullptr; - std::size_t length = 0; - if (fseek(fp, 0, SEEK_END) == 0) { - long offset = ftell(fp); - if (offset >= 0) { - length = static_cast(offset); - } - rewind(fp); - } - return std::unique_ptr(new FileZoneInfoSource(fp, length)); + auto fp = FOpen(path.c_str(), "rb"); + if (fp.get() == nullptr) return nullptr; + return std::unique_ptr(new FileZoneInfoSource(std::move(fp))); } class AndroidZoneInfoSource : public FileZoneInfoSource { @@ -663,8 +659,9 @@ class AndroidZoneInfoSource : public FileZoneInfoSource { std::string Version() const override { return version_; } private: - explicit AndroidZoneInfoSource(FILE* fp, std::size_t len, const char* vers) - : FileZoneInfoSource(fp, len), version_(vers) {} + explicit AndroidZoneInfoSource(FilePtr fp, std::size_t len, + std::string version) + : FileZoneInfoSource(std::move(fp), len), version_(std::move(version)) {} std::string version_; }; @@ -676,7 +673,7 @@ std::unique_ptr AndroidZoneInfoSource::Open( // See Android's libc/tzcode/bionic.cpp for additional information. for (const char* tzdata : {"/data/misc/zoneinfo/current/tzdata", "/system/usr/share/zoneinfo/tzdata"}) { - std::unique_ptr fp(FOpen(tzdata, "rb"), fclose); + auto fp = FOpen(tzdata, "rb"); if (fp.get() == nullptr) continue; char hbuf[24]; // covers header.zonetab_offset too @@ -703,7 +700,7 @@ std::unique_ptr AndroidZoneInfoSource::Open( if (strcmp(name.c_str() + pos, ebuf) == 0) { if (fseek(fp.get(), static_cast(start), SEEK_SET) != 0) break; return std::unique_ptr(new AndroidZoneInfoSource( - fp.release(), static_cast(length), vers)); + std::move(fp), static_cast(length), vers)); } } } -- cgit v1.2.3 From 299f59cadda78dfaf71b2a35049b63911e8eff47 Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Wed, 17 Nov 2021 10:01:24 -0800 Subject: Export of internal Abseil changes -- 2130ba98c8359b08d97fb16d84dfd05687005dcf by Abseil Team : Tweaking the documentation of c_all_of to state the effect more directly. PiperOrigin-RevId: 410557900 -- 4732289bf4b56123fed113e36be4710b55c6a6c7 by Greg Falcon : Improve the quality of absl::Hash>. This previously dispatched to std::hash>, which suffers from trivial collisions on many platforms. (They often hash the internal words but no size info, so that, e.g., {1, 1} and {1, 1, 0} collide.) Also extended the unit test to exercise this. PiperOrigin-RevId: 410329943 -- 1c5f3934230a7669f74c96b305251786a265e235 by Greg Falcon : Add broader testing of absl hash contracts in the hash unit test. In particular, test that the hash erasure mechanism works. PiperOrigin-RevId: 410312738 -- 5e1923f527ed3d02f6752a5b38d5e1c17a4a146f by Derek Mauro : Internal change PiperOrigin-RevId: 410290663 -- 8c74bc962b3b98a5908017c345efc592393048ea by Martijn Vels : Add Cord::CreateFlat() function PiperOrigin-RevId: 410260776 -- bd0de4e94c85620d3b8dd60fae367b730fc4cb34 by Evan Brown : Rename node_hash_policy to node_slot_policy. Motivation: we can potentially reuse this code for node_btree_*. PiperOrigin-RevId: 410082271 GitOrigin-RevId: 2130ba98c8359b08d97fb16d84dfd05687005dcf Change-Id: Ie052084cf992dee250d8b2f388d39c4de0dcff40 --- CMake/AbseilDll.cmake | 4 +- absl/algorithm/container.h | 2 +- absl/container/BUILD.bazel | 14 +- absl/container/CMakeLists.txt | 14 +- absl/container/internal/node_hash_policy.h | 92 ----------- absl/container/internal/node_hash_policy_test.cc | 69 -------- absl/container/internal/node_slot_policy.h | 92 +++++++++++ absl/container/internal/node_slot_policy_test.cc | 69 ++++++++ absl/container/node_hash_map.h | 4 +- absl/container/node_hash_set.h | 4 +- absl/hash/hash_test.cc | 195 ++++++++++++++++++----- absl/hash/internal/hash.h | 19 ++- absl/strings/cord.h | 5 + absl/strings/internal/cord_rep_flat.h | 11 ++ 14 files changed, 368 insertions(+), 226 deletions(-) delete mode 100644 absl/container/internal/node_hash_policy.h delete mode 100644 absl/container/internal/node_hash_policy_test.cc create mode 100644 absl/container/internal/node_slot_policy.h create mode 100644 absl/container/internal/node_slot_policy_test.cc (limited to 'absl/algorithm/container.h') diff --git a/CMake/AbseilDll.cmake b/CMake/AbseilDll.cmake index 7c827251..07a4576e 100644 --- a/CMake/AbseilDll.cmake +++ b/CMake/AbseilDll.cmake @@ -81,7 +81,7 @@ set(ABSL_INTERNAL_DLL_FILES "container/internal/have_sse.h" "container/internal/inlined_vector.h" "container/internal/layout.h" - "container/internal/node_hash_policy.h" + "container/internal/node_slot_policy.h" "container/internal/raw_hash_map.h" "container/internal/raw_hash_set.cc" "container/internal/raw_hash_set.h" @@ -455,7 +455,7 @@ set(ABSL_INTERNAL_DLL_TARGETS "hashtable_debug" "hashtable_debug_hooks" "have_sse" - "node_hash_policy" + "node_slot_policy" "raw_hash_map" "container_common" "raw_hash_set" diff --git a/absl/algorithm/container.h b/absl/algorithm/container.h index c38a4a63..26b19529 100644 --- a/absl/algorithm/container.h +++ b/absl/algorithm/container.h @@ -166,7 +166,7 @@ container_algorithm_internal::ContainerDifferenceType c_distance( // c_all_of() // // Container-based version of the `std::all_of()` function to -// test a condition on all elements within a container. +// test if all elements within a container satisfy a condition. template bool c_all_of(const C& c, Pred&& pred) { return std::all_of(container_algorithm_internal::c_begin(c), diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel index ffaee19c..ea2c98b8 100644 --- a/absl/container/BUILD.bazel +++ b/absl/container/BUILD.bazel @@ -307,7 +307,7 @@ cc_library( deps = [ ":container_memory", ":hash_function_defaults", - ":node_hash_policy", + ":node_slot_policy", ":raw_hash_map", "//absl/algorithm:container", "//absl/memory", @@ -339,7 +339,7 @@ cc_library( linkopts = ABSL_DEFAULT_LINKOPTS, deps = [ ":hash_function_defaults", - ":node_hash_policy", + ":node_slot_policy", ":raw_hash_set", "//absl/algorithm:container", "//absl/memory", @@ -535,21 +535,21 @@ cc_test( ) cc_library( - name = "node_hash_policy", - hdrs = ["internal/node_hash_policy.h"], + name = "node_slot_policy", + hdrs = ["internal/node_slot_policy.h"], copts = ABSL_DEFAULT_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, deps = ["//absl/base:config"], ) cc_test( - name = "node_hash_policy_test", - srcs = ["internal/node_hash_policy_test.cc"], + name = "node_slot_policy_test", + srcs = ["internal/node_slot_policy_test.cc"], copts = ABSL_TEST_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, deps = [ ":hash_policy_traits", - ":node_hash_policy", + ":node_slot_policy", "@com_google_googletest//:gtest_main", ], ) diff --git a/absl/container/CMakeLists.txt b/absl/container/CMakeLists.txt index 78584d2c..bb718cf8 100644 --- a/absl/container/CMakeLists.txt +++ b/absl/container/CMakeLists.txt @@ -348,7 +348,7 @@ absl_cc_library( DEPS absl::container_memory absl::hash_function_defaults - absl::node_hash_policy + absl::node_slot_policy absl::raw_hash_map absl::algorithm_container absl::memory @@ -382,7 +382,7 @@ absl_cc_library( ${ABSL_DEFAULT_COPTS} DEPS absl::hash_function_defaults - absl::node_hash_policy + absl::node_slot_policy absl::raw_hash_set absl::algorithm_container absl::memory @@ -599,9 +599,9 @@ absl_cc_library( absl_cc_library( NAME - node_hash_policy + node_slot_policy HDRS - "internal/node_hash_policy.h" + "internal/node_slot_policy.h" COPTS ${ABSL_DEFAULT_COPTS} DEPS @@ -611,14 +611,14 @@ absl_cc_library( absl_cc_test( NAME - node_hash_policy_test + node_slot_policy_test SRCS - "internal/node_hash_policy_test.cc" + "internal/node_slot_policy_test.cc" COPTS ${ABSL_TEST_COPTS} DEPS absl::hash_policy_traits - absl::node_hash_policy + absl::node_slot_policy GTest::gmock_main ) diff --git a/absl/container/internal/node_hash_policy.h b/absl/container/internal/node_hash_policy.h deleted file mode 100644 index 4617162f..00000000 --- a/absl/container/internal/node_hash_policy.h +++ /dev/null @@ -1,92 +0,0 @@ -// Copyright 2018 The Abseil Authors. -// -// Licensed under the Apache License, Version 2.0 (the "License"); -// you may not use this file except in compliance with the License. -// You may obtain a copy of the License at -// -// https://www.apache.org/licenses/LICENSE-2.0 -// -// Unless required by applicable law or agreed to in writing, software -// distributed under the License is distributed on an "AS IS" BASIS, -// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -// See the License for the specific language governing permissions and -// limitations under the License. -// -// Adapts a policy for nodes. -// -// The node policy should model: -// -// struct Policy { -// // Returns a new node allocated and constructed using the allocator, using -// // the specified arguments. -// template -// value_type* new_element(Alloc* alloc, Args&&... args) const; -// -// // Destroys and deallocates node using the allocator. -// template -// void delete_element(Alloc* alloc, value_type* node) const; -// }; -// -// It may also optionally define `value()` and `apply()`. For documentation on -// these, see hash_policy_traits.h. - -#ifndef ABSL_CONTAINER_INTERNAL_NODE_HASH_POLICY_H_ -#define ABSL_CONTAINER_INTERNAL_NODE_HASH_POLICY_H_ - -#include -#include -#include -#include -#include - -#include "absl/base/config.h" - -namespace absl { -ABSL_NAMESPACE_BEGIN -namespace container_internal { - -template -struct node_hash_policy { - static_assert(std::is_lvalue_reference::value, ""); - - using slot_type = typename std::remove_cv< - typename std::remove_reference::type>::type*; - - template - static void construct(Alloc* alloc, slot_type* slot, Args&&... args) { - *slot = Policy::new_element(alloc, std::forward(args)...); - } - - template - static void destroy(Alloc* alloc, slot_type* slot) { - Policy::delete_element(alloc, *slot); - } - - template - static void transfer(Alloc*, slot_type* new_slot, slot_type* old_slot) { - *new_slot = *old_slot; - } - - static size_t space_used(const slot_type* slot) { - if (slot == nullptr) return Policy::element_space_used(nullptr); - return Policy::element_space_used(*slot); - } - - static Reference element(slot_type* slot) { return **slot; } - - template - static auto value(T* elem) -> decltype(P::value(elem)) { - return P::value(elem); - } - - template - static auto apply(Ts&&... ts) -> decltype(P::apply(std::forward(ts)...)) { - return P::apply(std::forward(ts)...); - } -}; - -} // namespace container_internal -ABSL_NAMESPACE_END -} // namespace absl - -#endif // ABSL_CONTAINER_INTERNAL_NODE_HASH_POLICY_H_ diff --git a/absl/container/internal/node_hash_policy_test.cc b/absl/container/internal/node_hash_policy_test.cc deleted file mode 100644 index 84aabba9..00000000 --- a/absl/container/internal/node_hash_policy_test.cc +++ /dev/null @@ -1,69 +0,0 @@ -// Copyright 2018 The Abseil Authors. -// -// Licensed under the Apache License, Version 2.0 (the "License"); -// you may not use this file except in compliance with the License. -// You may obtain a copy of the License at -// -// https://www.apache.org/licenses/LICENSE-2.0 -// -// Unless required by applicable law or agreed to in writing, software -// distributed under the License is distributed on an "AS IS" BASIS, -// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -// See the License for the specific language governing permissions and -// limitations under the License. - -#include "absl/container/internal/node_hash_policy.h" - -#include - -#include "gmock/gmock.h" -#include "gtest/gtest.h" -#include "absl/container/internal/hash_policy_traits.h" - -namespace absl { -ABSL_NAMESPACE_BEGIN -namespace container_internal { -namespace { - -using ::testing::Pointee; - -struct Policy : node_hash_policy { - using key_type = int; - using init_type = int; - - template - static int* new_element(Alloc* alloc, int value) { - return new int(value); - } - - template - static void delete_element(Alloc* alloc, int* elem) { - delete elem; - } -}; - -using NodePolicy = hash_policy_traits; - -struct NodeTest : ::testing::Test { - std::allocator alloc; - int n = 53; - int* a = &n; -}; - -TEST_F(NodeTest, ConstructDestroy) { - NodePolicy::construct(&alloc, &a, 42); - EXPECT_THAT(a, Pointee(42)); - NodePolicy::destroy(&alloc, &a); -} - -TEST_F(NodeTest, transfer) { - int s = 42; - int* b = &s; - NodePolicy::transfer(&alloc, &a, &b); - EXPECT_EQ(&s, a); -} - -} // namespace -} // namespace container_internal -ABSL_NAMESPACE_END -} // namespace absl diff --git a/absl/container/internal/node_slot_policy.h b/absl/container/internal/node_slot_policy.h new file mode 100644 index 00000000..baba5743 --- /dev/null +++ b/absl/container/internal/node_slot_policy.h @@ -0,0 +1,92 @@ +// Copyright 2018 The Abseil Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +// +// Adapts a policy for nodes. +// +// The node policy should model: +// +// struct Policy { +// // Returns a new node allocated and constructed using the allocator, using +// // the specified arguments. +// template +// value_type* new_element(Alloc* alloc, Args&&... args) const; +// +// // Destroys and deallocates node using the allocator. +// template +// void delete_element(Alloc* alloc, value_type* node) const; +// }; +// +// It may also optionally define `value()` and `apply()`. For documentation on +// these, see hash_policy_traits.h. + +#ifndef ABSL_CONTAINER_INTERNAL_NODE_SLOT_POLICY_H_ +#define ABSL_CONTAINER_INTERNAL_NODE_SLOT_POLICY_H_ + +#include +#include +#include +#include +#include + +#include "absl/base/config.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace container_internal { + +template +struct node_slot_policy { + static_assert(std::is_lvalue_reference::value, ""); + + using slot_type = typename std::remove_cv< + typename std::remove_reference::type>::type*; + + template + static void construct(Alloc* alloc, slot_type* slot, Args&&... args) { + *slot = Policy::new_element(alloc, std::forward(args)...); + } + + template + static void destroy(Alloc* alloc, slot_type* slot) { + Policy::delete_element(alloc, *slot); + } + + template + static void transfer(Alloc*, slot_type* new_slot, slot_type* old_slot) { + *new_slot = *old_slot; + } + + static size_t space_used(const slot_type* slot) { + if (slot == nullptr) return Policy::element_space_used(nullptr); + return Policy::element_space_used(*slot); + } + + static Reference element(slot_type* slot) { return **slot; } + + template + static auto value(T* elem) -> decltype(P::value(elem)) { + return P::value(elem); + } + + template + static auto apply(Ts&&... ts) -> decltype(P::apply(std::forward(ts)...)) { + return P::apply(std::forward(ts)...); + } +}; + +} // namespace container_internal +ABSL_NAMESPACE_END +} // namespace absl + +#endif // ABSL_CONTAINER_INTERNAL_NODE_SLOT_POLICY_H_ diff --git a/absl/container/internal/node_slot_policy_test.cc b/absl/container/internal/node_slot_policy_test.cc new file mode 100644 index 00000000..51b7467b --- /dev/null +++ b/absl/container/internal/node_slot_policy_test.cc @@ -0,0 +1,69 @@ +// Copyright 2018 The Abseil Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#include "absl/container/internal/node_slot_policy.h" + +#include + +#include "gmock/gmock.h" +#include "gtest/gtest.h" +#include "absl/container/internal/hash_policy_traits.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace container_internal { +namespace { + +using ::testing::Pointee; + +struct Policy : node_slot_policy { + using key_type = int; + using init_type = int; + + template + static int* new_element(Alloc* alloc, int value) { + return new int(value); + } + + template + static void delete_element(Alloc* alloc, int* elem) { + delete elem; + } +}; + +using NodePolicy = hash_policy_traits; + +struct NodeTest : ::testing::Test { + std::allocator alloc; + int n = 53; + int* a = &n; +}; + +TEST_F(NodeTest, ConstructDestroy) { + NodePolicy::construct(&alloc, &a, 42); + EXPECT_THAT(a, Pointee(42)); + NodePolicy::destroy(&alloc, &a); +} + +TEST_F(NodeTest, transfer) { + int s = 42; + int* b = &s; + NodePolicy::transfer(&alloc, &a, &b); + EXPECT_EQ(&s, a); +} + +} // namespace +} // namespace container_internal +ABSL_NAMESPACE_END +} // namespace absl diff --git a/absl/container/node_hash_map.h b/absl/container/node_hash_map.h index 7a39f628..302dafa2 100644 --- a/absl/container/node_hash_map.h +++ b/absl/container/node_hash_map.h @@ -43,7 +43,7 @@ #include "absl/algorithm/container.h" #include "absl/container/internal/container_memory.h" #include "absl/container/internal/hash_function_defaults.h" // IWYU pragma: export -#include "absl/container/internal/node_hash_policy.h" +#include "absl/container/internal/node_slot_policy.h" #include "absl/container/internal/raw_hash_map.h" // IWYU pragma: export #include "absl/memory/memory.h" @@ -535,7 +535,7 @@ namespace container_internal { template class NodeHashMapPolicy - : public absl::container_internal::node_hash_policy< + : public absl::container_internal::node_slot_policy< std::pair&, NodeHashMapPolicy> { using value_type = std::pair; diff --git a/absl/container/node_hash_set.h b/absl/container/node_hash_set.h index 93b15f46..4247288d 100644 --- a/absl/container/node_hash_set.h +++ b/absl/container/node_hash_set.h @@ -39,7 +39,7 @@ #include "absl/algorithm/container.h" #include "absl/container/internal/hash_function_defaults.h" // IWYU pragma: export -#include "absl/container/internal/node_hash_policy.h" +#include "absl/container/internal/node_slot_policy.h" #include "absl/container/internal/raw_hash_set.h" // IWYU pragma: export #include "absl/memory/memory.h" @@ -442,7 +442,7 @@ namespace container_internal { template struct NodeHashSetPolicy - : absl::container_internal::node_hash_policy> { + : absl::container_internal::node_slot_policy> { using key_type = T; using init_type = T; using constant_iterators = std::true_type; diff --git a/absl/hash/hash_test.cc b/absl/hash/hash_test.cc index b3ddebdd..dbfacb2d 100644 --- a/absl/hash/hash_test.cc +++ b/absl/hash/hash_test.cc @@ -14,12 +14,14 @@ #include "absl/hash/hash.h" +#include #include #include #include #include #include #include +#include #include #include #include @@ -46,6 +48,56 @@ namespace { +// Utility wrapper of T for the purposes of testing the `AbslHash` type erasure +// mechanism. `TypeErasedValue` can be constructed with a `T`, and can +// be compared and hashed. However, all hashing goes through the hashing +// type-erasure framework. +template +class TypeErasedValue { + public: + TypeErasedValue() = default; + TypeErasedValue(const TypeErasedValue&) = default; + TypeErasedValue(TypeErasedValue&&) = default; + explicit TypeErasedValue(const T& n) : n_(n) {} + + template + friend H AbslHashValue(H hash_state, const TypeErasedValue& v) { + v.HashValue(absl::HashState::Create(&hash_state)); + return hash_state; + } + + void HashValue(absl::HashState state) const { + absl::HashState::combine(std::move(state), n_); + } + + bool operator==(const TypeErasedValue& rhs) const { return n_ == rhs.n_; } + bool operator!=(const TypeErasedValue& rhs) const { return !(*this == rhs); } + + private: + T n_; +}; + +// A TypeErasedValue refinement, for containers. It exposes the wrapped +// `value_type` and is constructible from an initializer list. +template +class TypeErasedContainer : public TypeErasedValue { + public: + using value_type = typename T::value_type; + TypeErasedContainer() = default; + TypeErasedContainer(const TypeErasedContainer&) = default; + TypeErasedContainer(TypeErasedContainer&&) = default; + explicit TypeErasedContainer(const T& n) : TypeErasedValue(n) {} + TypeErasedContainer(std::initializer_list init_list) + : TypeErasedContainer(T(init_list.begin(), init_list.end())) {} + // one-argument constructor of value type T, to appease older toolchains that + // get confused by one-element initializer lists in some contexts + explicit TypeErasedContainer(const value_type& v) + : TypeErasedContainer(T(&v, &v + 1)) {} +}; + +template +using TypeErasedVector = TypeErasedContainer>; + using absl::Hash; using absl::hash_internal::SpyHashState; @@ -389,23 +441,60 @@ TYPED_TEST_SUITE_P(HashValueSequenceTest); TYPED_TEST_P(HashValueSequenceTest, BasicUsage) { EXPECT_TRUE((is_hashable::value)); - using ValueType = typename TypeParam::value_type; - auto a = static_cast(0); - auto b = static_cast(23); - auto c = static_cast(42); - - EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly( - std::make_tuple(TypeParam(), TypeParam{}, TypeParam{a, b, c}, - TypeParam{a, b}, TypeParam{b, c}))); + using IntType = typename TypeParam::value_type; + auto a = static_cast(0); + auto b = static_cast(23); + auto c = static_cast(42); + + std::vector exemplars = { + TypeParam(), TypeParam(), TypeParam{a, b, c}, + TypeParam{a, c, b}, TypeParam{c, a, b}, TypeParam{a}, + TypeParam{a, a}, TypeParam{a, a, a}, TypeParam{a, a, b}, + TypeParam{a, b, a}, TypeParam{b, a, a}, TypeParam{a, b}, + TypeParam{b, c}}; + EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(exemplars)); } REGISTER_TYPED_TEST_CASE_P(HashValueSequenceTest, BasicUsage); using IntSequenceTypes = testing::Types, std::forward_list, std::list, - std::vector, std::vector, std::set, - std::multiset>; + std::vector, std::vector, TypeErasedVector, + TypeErasedVector, std::set, std::multiset>; INSTANTIATE_TYPED_TEST_CASE_P(My, HashValueSequenceTest, IntSequenceTypes); +template +class HashValueNestedSequenceTest : public testing::Test {}; +TYPED_TEST_SUITE_P(HashValueNestedSequenceTest); + +TYPED_TEST_P(HashValueNestedSequenceTest, BasicUsage) { + using T = TypeParam; + using V = typename T::value_type; + std::vector exemplars = { + // empty case + T{}, + // sets of empty sets + T{V{}}, T{V{}, V{}}, T{V{}, V{}, V{}}, + // multisets of different values + T{V{1}}, T{V{1, 1}, V{1, 1}}, T{V{1, 1, 1}, V{1, 1, 1}, V{1, 1, 1}}, + // various orderings of same nested sets + T{V{}, V{1, 2}}, T{V{}, V{2, 1}}, T{V{1, 2}, V{}}, T{V{2, 1}, V{}}, + // various orderings of various nested sets, case 2 + T{V{1, 2}, V{3, 4}}, T{V{1, 2}, V{4, 3}}, T{V{1, 3}, V{2, 4}}, + T{V{1, 3}, V{4, 2}}, T{V{1, 4}, V{2, 3}}, T{V{1, 4}, V{3, 2}}, + T{V{2, 3}, V{1, 4}}, T{V{2, 3}, V{4, 1}}, T{V{2, 4}, V{1, 3}}, + T{V{2, 4}, V{3, 1}}, T{V{3, 4}, V{1, 2}}, T{V{3, 4}, V{2, 1}}}; + EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(exemplars)); +} + +REGISTER_TYPED_TEST_CASE_P(HashValueNestedSequenceTest, BasicUsage); +using NestedIntSequenceTypes = + testing::Types>, + std::vector>, + TypeErasedVector>, + TypeErasedVector>>; +INSTANTIATE_TYPED_TEST_CASE_P(My, HashValueNestedSequenceTest, + NestedIntSequenceTypes); + // Private type that only supports AbslHashValue to make sure our chosen hash // implementation is recursive within absl::Hash. // It uses std::abs() on the value to provide different bitwise representations @@ -564,23 +653,59 @@ TEST(HashValueTest, Variant) { #endif } -TEST(HashValueTest, Maps) { - EXPECT_TRUE((is_hashable>::value)); +template +class HashValueAssociativeMapTest : public testing::Test {}; +TYPED_TEST_SUITE_P(HashValueAssociativeMapTest); + +TYPED_TEST_P(HashValueAssociativeMapTest, BasicUsage) { + using M = TypeParam; + using V = typename M::value_type; + std::vector exemplars{M{}, + M{V{0, "foo"}}, + M{V{1, "foo"}}, + M{V{0, "bar"}}, + M{V{1, "bar"}}, + M{V{0, "foo"}, V{42, "bar"}}, + M{V{42, "bar"}, V{0, "foo"}}, + M{V{1, "foo"}, V{42, "bar"}}, + M{V{1, "foo"}, V{43, "bar"}}, + M{V{1, "foo"}, V{43, "baz"}}}; + EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(exemplars)); +} - using M = std::map; - EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple( - M{}, M{{0, "foo"}}, M{{1, "foo"}}, M{{0, "bar"}}, M{{1, "bar"}}, - M{{0, "foo"}, {42, "bar"}}, M{{1, "foo"}, {42, "bar"}}, - M{{1, "foo"}, {43, "bar"}}, M{{1, "foo"}, {43, "baz"}}))); +REGISTER_TYPED_TEST_CASE_P(HashValueAssociativeMapTest, BasicUsage); +using AssociativeMapTypes = testing::Types>; +INSTANTIATE_TYPED_TEST_CASE_P(My, HashValueAssociativeMapTest, + AssociativeMapTypes); - using MM = std::multimap; - EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(std::make_tuple( - MM{}, MM{{0, "foo"}}, MM{{1, "foo"}}, MM{{0, "bar"}}, MM{{1, "bar"}}, - MM{{0, "foo"}, {0, "bar"}}, MM{{0, "bar"}, {0, "foo"}}, - MM{{0, "foo"}, {42, "bar"}}, MM{{1, "foo"}, {42, "bar"}}, - MM{{1, "foo"}, {1, "foo"}, {43, "bar"}}, MM{{1, "foo"}, {43, "baz"}}))); +template +class HashValueAssociativeMultimapTest : public testing::Test {}; +TYPED_TEST_SUITE_P(HashValueAssociativeMultimapTest); + +TYPED_TEST_P(HashValueAssociativeMultimapTest, BasicUsage) { + using MM = TypeParam; + using V = typename MM::value_type; + std::vector exemplars{MM{}, + MM{V{0, "foo"}}, + MM{V{1, "foo"}}, + MM{V{0, "bar"}}, + MM{V{1, "bar"}}, + MM{V{0, "foo"}, V{0, "bar"}}, + MM{V{0, "bar"}, V{0, "foo"}}, + MM{V{0, "foo"}, V{42, "bar"}}, + MM{V{1, "foo"}, V{42, "bar"}}, + MM{V{1, "foo"}, V{1, "foo"}, V{43, "bar"}}, + MM{V{1, "foo"}, V{43, "bar"}, V{1, "foo"}}, + MM{V{1, "foo"}, V{43, "baz"}}}; + EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(exemplars)); } +REGISTER_TYPED_TEST_CASE_P(HashValueAssociativeMultimapTest, BasicUsage); +using AssociativeMultimapTypes = + testing::Types>; +INSTANTIATE_TYPED_TEST_CASE_P(My, HashValueAssociativeMultimapTest, + AssociativeMultimapTypes); + TEST(HashValueTest, ReferenceWrapper) { EXPECT_TRUE(is_hashable>::value); @@ -928,28 +1053,14 @@ TEST(HashTest, SmallValueOn64ByteBoundary) { Hash()(IntAndString{0, std::string(63, '0')}); } -struct TypeErased { - size_t n; - - template - friend H AbslHashValue(H hash_state, const TypeErased& v) { - v.HashValue(absl::HashState::Create(&hash_state)); - return hash_state; - } - - void HashValue(absl::HashState state) const { - absl::HashState::combine(std::move(state), n); - } -}; - TEST(HashTest, TypeErased) { - EXPECT_TRUE((is_hashable::value)); - EXPECT_TRUE((is_hashable>::value)); + EXPECT_TRUE((is_hashable>::value)); + EXPECT_TRUE((is_hashable, int>>::value)); - EXPECT_EQ(SpyHash(TypeErased{7}), SpyHash(size_t{7})); - EXPECT_NE(SpyHash(TypeErased{7}), SpyHash(size_t{13})); + EXPECT_EQ(SpyHash(TypeErasedValue(7)), SpyHash(size_t{7})); + EXPECT_NE(SpyHash(TypeErasedValue(7)), SpyHash(size_t{13})); - EXPECT_EQ(SpyHash(std::make_pair(TypeErased{7}, 17)), + EXPECT_EQ(SpyHash(std::make_pair(TypeErasedValue(7), 17)), SpyHash(std::make_pair(size_t{7}, 17))); } diff --git a/absl/hash/internal/hash.h b/absl/hash/internal/hash.h index b1e33caf..97b68bad 100644 --- a/absl/hash/internal/hash.h +++ b/absl/hash/internal/hash.h @@ -502,10 +502,9 @@ AbslHashValue(H hash_state, const std::vector& vector) { vector.size()); } +// AbslHashValue special cases for hashing std::vector #if defined(ABSL_IS_BIG_ENDIAN) && \ (defined(__GLIBCXX__) || defined(__GLIBCPP__)) -// AbslHashValue for hashing std::vector -// // std::hash in libstdc++ does not work correctly with vector on Big // Endian platforms therefore we need to implement a custom AbslHashValue for // it. More details on the bug: @@ -521,6 +520,22 @@ AbslHashValue(H hash_state, const std::vector& vector) { } return H::combine(combiner.finalize(std::move(hash_state)), vector.size()); } +#else +// When not working around the libstdc++ bug above, we still have to contend +// with the fact that std::hash> is often poor quality, hashing +// directly on the internal words and on no other state. On these platforms, +// vector{1, 1} and vector{1, 1, 0} hash to the same value. +// +// Mixing in the size (as we do in our other vector<> implementations) on top +// of the library-provided hash implementation avoids this QOI issue. +template +typename std::enable_if::value && std::is_same::value, + H>::type +AbslHashValue(H hash_state, const std::vector& vector) { + return H::combine(std::move(hash_state), + std::hash>{}(vector), + vector.size()); +} #endif // ----------------------------------------------------------------------------- diff --git a/absl/strings/cord.h b/absl/strings/cord.h index 3f0633bd..662e889a 100644 --- a/absl/strings/cord.h +++ b/absl/strings/cord.h @@ -855,6 +855,11 @@ class Cord { // Returns true if the Cord is being profiled by cordz. bool is_profiled() const { return data_.is_tree() && data_.is_profiled(); } + // Returns the available inlined capacity, or 0 if is_tree() == true. + size_t inline_capacity() const { + return data_.is_tree() ? 0 : kMaxInline - data_.inline_size(); + } + // Returns the profiled CordzInfo, or nullptr if not sampled. absl::cord_internal::CordzInfo* cordz_info() const { return data_.cordz_info(); diff --git a/absl/strings/internal/cord_rep_flat.h b/absl/strings/internal/cord_rep_flat.h index 62cf5840..8c254273 100644 --- a/absl/strings/internal/cord_rep_flat.h +++ b/absl/strings/internal/cord_rep_flat.h @@ -117,6 +117,17 @@ struct CordRepFlat : public CordRep { #endif } + // Create a CordRepFlat containing `data`, with an optional additional + // extra capacity of up to `extra` bytes. Requires that `data.size()` + // is less than kMaxFlatLength. + static CordRepFlat* Create(absl::string_view data, size_t extra = 0) { + assert(data.size() <= kMaxFlatLength); + CordRepFlat* flat = New(data.size() + (std::min)(extra, kMaxFlatLength)); + memcpy(flat->Data(), data.data(), data.size()); + flat->length = data.size(); + return flat; + } + // Returns a pointer to the data inside this flat rep. char* Data() { return reinterpret_cast(storage); } const char* Data() const { return reinterpret_cast(storage); } -- cgit v1.2.3