Previously, ~raw_hash_set() would change *this to have the same
representation as an empty hash table. This is unnecessary since
nobody should be touching a destroyed hash table, and prevents future
optimizations/changes that might not be able to preserve this
behavior.
PiperOrigin-RevId: 487899950
Change-Id: I2d4470677bdd411c2e48ef511187e39f4e7fc2f4
- Add assertions that the iterators are either (a) from the same container or (b) both default constructed. Standard says: "The domain of == for forward iterators is that of iterators over the same underlying sequence. However, value-initialized iterators may be compared and shall compare equal to other value-initialized iterators of the same type." - [reference](https://eel.is/c++draft/forward.iterators#2).
- Also optimize IsEndIterator a bit.
PiperOrigin-RevId: 487617518
Change-Id: Iefba5c3bc8caa93954671793e6929e22f419c298
We check for comparisons of swisstable iterators from different heap allocations, which can indicate either iterators from different containers or that there was a rehash between when the iterators were initialized.
PiperOrigin-RevId: 487304602
Change-Id: I5c596c5ea07948d66e048f99937f9032a630344f
Note that multi{set,map}::emplace doesn't specify in which order the new element is inserted if there are equivalent keys in the table, whereas emplace_hint specifies that the new element must be before the hint if possible.
https://en.cppreference.com/w/cpp/container/multiset/emplacehttps://en.cppreference.com/w/cpp/container/multiset/emplace_hint
Also refactor to rely on IsAssertEnabled instead of checking for NDEBUG.
PiperOrigin-RevId: 486733450
Change-Id: Ie90d33c584a6caccd8301ad6fc0396234dbbfac4
- Separate the failure cases into different assertions: end/default constructed vs rehashed or erased.
- Update the assertion error for AssertIsValid to not mention the end iterator case because end iterators are considered valid by AssertIsValid.
- Also fix an out-of-date comment for skip_empty_or_deleted.
PiperOrigin-RevId: 485402559
Change-Id: I593056abdc6c3565d0396fb885923fef643bf4e4
- Check for invalid generation before checking for other types of invalid iterators.
- Check specifically for dereferencing end() iterators.
PiperOrigin-RevId: 483725646
Change-Id: Ibca19c48b1b242384683580145be8fb9ae707bc8
Note: btree_iterator::operator- is still O(N) because in the worst case (end()-begin()), we will have at least one operation per node in the tree, and there are at least N/M nodes, where M (a constant) is the maximum number of values per node.
PiperOrigin-RevId: 481716874
Change-Id: Ic0225b7509208ed96b75a2dc626d2aa4a24f4946
Class `Allocation` is not initialized and I will get a compile error like this.
```
error: ‘worklist.absl::lts_20220623::InlinedVector<absl::lts_20220623::cord_internal::CordRep*, 2, std::allocator<absl::lts_20220623::cord_internal::CordRep*> >::storage_.absl::lts_20220623::inlined_vector_internal::Storage<absl::lts_20220623::cord_internal::CordRep*, 2, std::allocator<absl::lts_20220623::cord_internal::CordRep*> >::data_.absl::lts_20220623::inlined_vector_internal::Storage<absl::lts_20220623::cord_internal::CordRep*, 2, std::allocator<absl::lts_20220623::cord_internal::CordRep*> >::Data::allocated.absl::lts_20220623::inlined_vector_internal::Storage<absl::lts_20220623::cord_internal::CordRep*, 2, std::allocator<absl::lts_20220623::cord_internal::CordRep*> >::Allocated::allocated_capacity’ may be used uninitialized [-Werror=maybe-uninitialized]
```
Also remove the transfer implementations from btree_set.h and flat_hash_set.h, which are equivalent to the default implementations.
Motivation: this will simplify upcoming changes related to trivial relocation.
PiperOrigin-RevId: 477493403
Change-Id: I75babef4c93dec3a8105f86c58af54199bb1ec9c
Certain core libraries in Chrome build with these warnings [1];
btree_map and btree_set cannot be used in those libraries until these
warnings are fixed.
[1] https://crbug.com/1292951
PiperOrigin-RevId: 476908396
Change-Id: I32e9ea1eec911e329d6ff00f04fa2e9cfde8660a
The btree data structure poisons regions of memory it's not using. It leaves
these regions poisoned when it frees memory. This means that a custom memory
allocator that tries to reuse freed memory will trigger an ASAN
use-after-poison error.
The fix is to unpoison each memory region right before freeing it.
PiperOrigin-RevId: 475309671
Change-Id: I29d55c298d3d89a83e1f960deb6e93118891ff83
Addresses failures with the following, in some files:
-Wshorten-64-to-32
-Wimplicit-int-conversion
-Wsign-compare
-Wsign-conversion
-Wtautological-unsigned-zero-compare
(This specific CL focuses on .cc files in */internal/.)
Bug: chromium:1292951
PiperOrigin-RevId: 473868797
Change-Id: Ibe0b76e33f9e001d59862beaac54fb47bacd39b2
Addresses failures with the following, in some files:
-Wshorten-64-to-32
-Wimplicit-int-conversion
-Wsign-compare
-Wsign-conversion
-Wtautological-unsigned-zero-compare
(This specific CL focuses on tests.)
Bug: chromium:1292951
PiperOrigin-RevId: 473055916
Change-Id: I40cdd6c87ba9d0a5fb2db5746cff04f14ee829c2
Addresses failures with the following, in some files:
-Wshorten-64-to-32
-Wimplicit-int-conversion
-Wsign-compare
-Wsign-conversion
-Wtautological-unsigned-zero-compare
(This specific CL focuses on miscellaneous non-test source files.)
Bug: chromium:1292951
PiperOrigin-RevId: 473054605
Change-Id: Ifd7b24966613ca915511a3a607095508068200b8
In some cases we can do a bit better by using
std::min(std::numeric_limits<size_type>::max() / 2, allocator<T>::max_size())
They may help in some cases, particularly on 32-bit platforms.
PiperOrigin-RevId: 471846886
Change-Id: I5bd63de5dd8aec3de6530a33d8904dd6e9bd015e
The problem is that the underlying storage adds redzone after the actual data so from compiler's perspective it looks like a valid memory. In the outlined version the memory is returned in call.i.i with unknown size so the access check can't be removed. The workaround is to always outline the call to InitializeData for ASAN builds.
Outlined version:
%call.i.i = call noundef i32* @absl::FixedArray<int, 4ul, std::__u::allocator<int> >::Storage::InitializeData()(...), !dbg !28
store i32* %call.i.i, i32** %data_.i.i, align 8, !dbg !27
%arrayidx = getelementptr inbounds i32, i32* %call.i.i, i64 5, !dbg !29
%24 = bitcast i32* %arrayidx to i8*, !dbg !29
call void @llvm.asan.check.memaccess(i8* %24, i32 36), !dbg !29
store i32 0, i32* %arrayidx, align 4, !dbg !29
Inlined version:
%arrayidx = getelementptr inbounds %"class.absl::FixedArray", %"class.absl::FixedArray"* %7, i64 0, i32 0, i32 0, i32 1, i64 20, !dbg !40
%27 = bitcast i8* %arrayidx to i32*, !dbg !40
>>>>>>>>>>>>>>> call to @llvm.asan.check.memaccess removed <<<<<<<<<<<<<<
store i32 0, i32* %27, align 4, !dbg !40
Workaround for ASAN stack safety analysis problem with FixedArray container annotations.
PiperOrigin-RevId: 471583635
Change-Id: I0d74eed5782a1cbd340ca4aca1bce71b63b06d43
Addresses failures with the following, in some files:
-Wshorten-64-to-32
-Wimplicit-int-conversion
-Wsign-compare
-Wsign-conversion
-Wtautological-unsigned-zero-compare
(This specific CL focuses on .cc files in */internal/.)
Bug: chromium:1292951
PiperOrigin-RevId: 471561809
Change-Id: I7abd6d83706f5ca135f1ce3458192a498a6280b9
Addresses failures with the following, in some files:
-Wshorten-64-to-32
-Wimplicit-int-conversion
-Wsign-compare
-Wsign-conversion
-Wtautological-unsigned-zero-compare
(This specific CL focuses on .cc files in */internal/.)
Bug: chromium:1292951
PiperOrigin-RevId: 471549854
Change-Id: Id685d0e4666212926f4e001b8ef4930b6a33a4cc
Corrects the computation of max_size(), so that it accounts for the
size of the objects.
PiperOrigin-RevId: 471343778
Change-Id: I68e222cefaa0295b8d8c38d00308a29df4165e81
Addresses failures with the following, in some files:
-Wshorten-64-to-32
-Wimplicit-int-conversion
-Wsign-compare
-Wsign-conversion
-Wtautological-unsigned-zero-compare
(This specific CL focuses on .h and win32 .inc files.)
Bug: chromium:1292951
PiperOrigin-RevId: 463835431
Change-Id: If8e5f7f651d5cd96035e23e4623bdb08a7fedabe
This ensures that emmintrin.h is included with clang-cl. Otherwise, errors like
this occur:
.../absl/container/internal/raw_hash_set.h(536,8): error: unknown type name '__m128i'
inline __m128i _mm_cmpgt_epi8_fixed(__m128i a, __m128i b) {
This aligns the include ifdef guards and the guards that use the provided APIs.
The includes are also reordered, so they appear after the config header which
provides the internal macro values.
PiperOrigin-RevId: 456530271
Change-Id: I86dfd0022fd06fe7aa132138ec4d1bd14a86ba84
This change introduces the symbol
ABSL_INTERNAL_NEED_REDUNDANT_CONSTEXPR_DECL
to guard redundant declarations of static constexpr data
members that are needed prior to C++17.
This change also introduces the symbol
ABSL_INTERNAL_CPLUSPLUS_LANG, which is supposed to be set
to the same value as __cplusplus, except it uses _MSVC_LANG
on MSVC so that the value is correct on MSVC.
Neither of these new symbols should be used outside of Abseil.
Fixes#1191
PiperOrigin-RevId: 453923908
Change-Id: I1316c52c19fa0c168b93cced0c817e4cb7c9c862
Avoid using value move/swap and delete those functions from slot_policy types. There was only one use of params_type::move in `erase`.
PiperOrigin-RevId: 453237739
Change-Id: Ie81c6dba6c4db34e97a067d2c0defcded8044a5a
https://pastebin.com/CmnzwUFN
The key idea is to avoid using 16 byte NEON and use 8 byte NEON which has lower latency for BitMask::Match. Even though 16 byte NEON achieves higher throughput, in SwissMap it's very important to catch these Matches with low latency as probing on average happens at most once.
I also introduced NonIterableMask as ARM has really great cbnz instructions and additional AND on scalar mask had 1 extra latency cycle
PiperOrigin-RevId: 453216147
Change-Id: I842c50d323954f8383ae156491232ced55aacb78
Abseil Team
Evan Brown
Gennadiy Rozental
GOGOYAO
Derek Mauro
Tom Rybka