summaryrefslogtreecommitdiff
path: root/absl/container/internal
Commit message (Collapse)AuthorAge
* raw_hash_set_test: Expect tsan to catch heap-use-after-free on iterators ↵Gravatar Dino Radakovic2023-08-01
| | | | | | | invalidated by rehashing PiperOrigin-RevId: 552901078 Change-Id: I137d01fe87b1bbf591b400305f6f7919982fc1c9
* InlinedVector: Disable CFI checking on the const GetInlinedData() pathGravatar Derek Mauro2023-08-01
| | | | | | | | | | as well. Some empty cases can trigger this. See also: https://clang.llvm.org/docs/ControlFlowIntegrity.html#bad-cast-checking. PiperOrigin-RevId: 552846765 Change-Id: I6adb3c0c73efec841ffe8fdac4342f641c68ddbe
* raw_hash_set_test: Match lowercase "invalid iterator" in death testsGravatar Dino Radakovic2023-07-31
| | | | | PiperOrigin-RevId: 552520562 Change-Id: I5d311871afbc2906894c3b754a503a6abace8ceb
* Refactor raw_hash_set deallocation to pass CommonFields instead of passing ↵Gravatar Evan Brown2023-07-27
| | | | | | | | the results of a bunch of accessors of CommonFields. Motivation: this makes it easier to refactor CommonFields to be smaller. PiperOrigin-RevId: 551616928 Change-Id: I3710443fb156537d716944584bea02f945559e99
* Change the API constraints of erase(const_iterator, const_iterator) so that ↵Gravatar Evan Brown2023-07-26
| | | | | | | calling erase(begin(), end()) resets reserved growth. PiperOrigin-RevId: 551248712 Change-Id: I34755c63e3ee40da4ba7047e0d24eec567d28173
* InlinedVector: Disable CFI checking on GetInlinedData()Gravatar Derek Mauro2023-07-26
| | | | | | | | | | | | GetInlinedDataUninitialized() is removed. Just use GetInlinedData() in all cases instead. GetInlinedData() is sometimes used to return uninitialized memory. In these cases it is immediately constructed. This is a followup to 511ad64. See also: https://clang.llvm.org/docs/ControlFlowIntegrity.html#bad-cast-checking. PiperOrigin-RevId: 551205766 Change-Id: I4ddb45e29a723ccf6fc7dc203e762f4ad559fc83
* InlinedVector: Fix control-flow-inregrity warning when using a classGravatar Derek Mauro2023-07-25
| | | | | | | | | | | | | | | | with a vtable The code is getting the pointer, then constructing it on the next line. Using reinterpret_cast on this pointer is legal according to https://clang.llvm.org/docs/ControlFlowIntegrity.html#bad-cast-checking, but it flags it anyway. The docs say it might be necessary for `allocate()`-type APIs, and recommends adding them to an ignorelist. Also note that std::addressof is removed. It is unnecessary since inlined_data is a char-array. PiperOrigin-RevId: 550972834 Change-Id: Ib224cec330bb6bcb770296de6c91881f404ef531
* Add a special case for erase(begin(), end()) to reset the control bytes. The ↵Gravatar Evan Brown2023-07-20
| | | | | | | | motivation is to avoid potentially expanding the table unnecessarily later. Note: I prefer doing this as a special case in erase(iterator, iterator) rather than special casing erase(iterator) for size==1 because IIUC that changes the time complexity of erase(iterator) from O(1) to O(N) and in pathological cases, it could change loops from O(N) to O(N^2). PiperOrigin-RevId: 549661855 Change-Id: I8603324260f51a98809db32f840ff09f25cf2481
* Rename CommonFields::slots_ptr to slot_array to match the name of the ↵Gravatar Evan Brown2023-07-19
| | | | | | | corresponding function in raw_hash_set. PiperOrigin-RevId: 549379884 Change-Id: I305745dbea2c15821b2092441c9b4546fc7aabbe
* Move growth_left to the backing array.Gravatar Evan Brown2023-07-17
| | | | | PiperOrigin-RevId: 548794485 Change-Id: Ie82d5f8ad752518ef05b38144ca1e32b21c9def8
* Clarify that lazy_emplace returns an iterator to the new element when lookup ↵Gravatar Abseil Team2023-07-05
| | | | | | | fails. PiperOrigin-RevId: 545683736 Change-Id: Ic0abec5037e160898e2f24de1b1489caff7d06fd
* roll forward: Make data members of CommonFields be private so that it's ↵Gravatar Evan Brown2023-06-30
| | | | | | | easier to change how we store this information internally. PiperOrigin-RevId: 544732832 Change-Id: I0c9a30f18edc71b3c7fffe94e2002ff6c52050f8
* rollback: Make data members of CommonFields be private so that it's easier ↵Gravatar Evan Brown2023-06-30
| | | | | | | to change how we store this information internally. PiperOrigin-RevId: 544718317 Change-Id: I0ff3e4df7e810be9f7c5db4328995e172eb704a5
* Make data members of CommonFields be private so that it's easier to change ↵Gravatar Evan Brown2023-06-30
| | | | | | | how we store this information internally. PiperOrigin-RevId: 544667586 Change-Id: I9b1943ca71ea1c1f8699832422cd7bc095ac8b2d
* Fix typoGravatar Abseil Team2023-06-29
| | | | | PiperOrigin-RevId: 544401753 Change-Id: Ie5bb48bb46c8c1bf41ef902242cefefd739e7c37
* Use std::is_final instead of a non-portable implementationGravatar Derek Mauro2023-06-16
| | | | | PiperOrigin-RevId: 540928490 Change-Id: Idf022b28ce101a948be4efd5336888a66f5eacf9
* Convert `raw_hash_set` comments from imperative to indicative mood.Gravatar Bradley C. Kuszmaul2023-05-31
| | | | https://google.github.io/styleguide/cppguide.html#Function_Comments
* Merge pull request #1462 from kuszmaul:fix-typoGravatar Copybara-Service2023-05-31
|\ | | | | | | | | PiperOrigin-RevId: 536785792 Change-Id: I2963dea81a75b01b7275d784f6a2908816d0c7bf
| * Typo gardeningGravatar Bradley C. Kuszmaul2023-05-30
| |
* | Migrate most RAW_LOGs and RAW_CHECKs in tests to regular LOG and CHECK.Gravatar Andy Getzendanner2023-05-23
|/ | | | | | | | | | | The non-RAW_ versions provide better output but weren't available when most of these tests were written. There are just a couple spots where RAW_ is actually needed, e.g. signal handlers and malloc hooks. Also fix a couple warnings in layout_test.cc newly surfaced because the optimizer understands CHECK_XX differently than INTERNAL_CHECK. PiperOrigin-RevId: 534584435 Change-Id: I8d36fa809ffdaae5a3813064bd602cb8611c1613
* Add tests for btrees in which slot_type is overaligned and slot_type is ↵Gravatar Evan Brown2023-05-04
| | | | | | | | | equal to field_type. Also do some minor refactoring in btree.h. PiperOrigin-RevId: 529460378 Change-Id: I278833ada93bbb7652e149fceed08ce3485e4312
* Add lifetimebound attribute to more Abseil container methods and remove them ↵Gravatar Abseil Team2023-05-04
| | | | | | | from internal ones. PiperOrigin-RevId: 529423722 Change-Id: Ib1cc427299100956c0f2ae6cb5214467ef5a3790
* Add lifetimebound attribute to some Abseil containersGravatar Abseil Team2023-05-03
| | | | | PiperOrigin-RevId: 529119690 Change-Id: If585274c409e2a344c8d60759da6f8f990023d29
* Add pointer-stability validation in btree.Gravatar Evan Brown2023-05-02
| | | | | | | When we insert a new element, when ASan is enabled, we replace the node that the new element is on in order to try to detect cases of code depending on pointer/reference-stability. PiperOrigin-RevId: 528826645 Change-Id: Ie5c15c13016a8aa831a0d1edc3ad33c1f5ca4d65
* Merge pull request #1434 from Vertexwahn:fix-spellingGravatar Copybara-Service2023-04-25
|\ | | | | | | | | PiperOrigin-RevId: 527066823 Change-Id: Ifa1e9a43c7490b34f9f4dbfa12d3acbed6b49777
| * Fix some spelling mistakesGravatar Vertexwahn2023-04-24
|/
* Minor optimization in btree: avoid redundant stores to node->position when ↵Gravatar Evan Brown2023-04-20
| | | | | | | constructing nodes. PiperOrigin-RevId: 525792213 Change-Id: I4386385e6e05d74a4ccc18cea505530e919f0e28
* In debug mode, detect cases of btree comparators that violate transitivity, ↵Gravatar Evan Brown2023-04-12
| | | | | | | | | i.e. comp(A,B) && comp(B,C) -> comp(A,C). When inserting a new element, we verify that the key is ordered correctly with respect to all the other values on the node, which can be done in constant time. PiperOrigin-RevId: 523729309 Change-Id: Idb5a5912a9aa5411d086cb9fa76791523046778a
* Replace absl::type_traits_internal::is_trivially_copyable withGravatar Derek Mauro2023-04-12
| | | | | | | std::is_trivially_copyable PiperOrigin-RevId: 523724345 Change-Id: Id68c79c3bbb253d892bdef4659ac8a926e023d12
* inlined_vector: fix incorrect restrictions on the copy constructor fast path.Gravatar Aaron Jacobs2023-04-11
| | | | | | | This has nothing to do with copy assignment or with destruction. PiperOrigin-RevId: 523576913 Change-Id: Iddb6ab73bcfd8b01a29880cdf4db4bc2b5aead8a
* inlined_vector: fix incorrect restrictions on the swap fast path.Gravatar Aaron Jacobs2023-04-11
| | | | | | | This has nothing to do with copy construction or copy assignment. PiperOrigin-RevId: 523571907 Change-Id: I338b5a40616594406ca8c80b747540c8935798e9
* inlined_vector: fix incorrect restrictions on the move-assignment fast path.Gravatar Aaron Jacobs2023-04-11
| | | | | | | This has nothing to do with copy construction or copy assignment. PiperOrigin-RevId: 523557887 Change-Id: I332d6ceaf738305157605f1271cb577a83d198c5
* inlined_vector: relax the requirements on the move-construction fast path.Gravatar Aaron Jacobs2023-04-11
| | | | | | | | | Don't require a trivial move constructor and trivial destructor. This excludes types that have declared themselves trivially relocatable by another means, like std::unique_ptr. Instead use "is trivially relocatable" directly, which includes all previous types as well as those that have opted in. PiperOrigin-RevId: 523557136 Change-Id: Icea2dbb8f36f99623308155f2e5b1edd8e5bd36b
* Add heterogeneous lookup support for wstring/u16string/u32string.Gravatar Abseil Team2023-04-03
| | | | | PiperOrigin-RevId: 521556211 Change-Id: I1e1812eb11bfc5772abbf38ce348580c3afa5612
* inlined_vector: fix incorrect conditions for move constructor fast paths.Gravatar Aaron Jacobs2023-03-29
| | | | | | | | | These have nothing to do with copy construction or copy assignment, and using "is trivially copy constructible" can in theory even give the wrong result if the copy constructor is trivial but the move constructor is not. PiperOrigin-RevId: 520488816 Change-Id: I6da4d57f3ce23b03044e0bf9aa70a14b51651fa3
* inlined_vector: destroy all types with trivial destructors efficiently.Gravatar Aaron Jacobs2023-03-27
| | | | | | | | | There's no reason to require the type to be trivially copy-constructible/assignable in order to avoid running destructors—those traits have nothing to do with destruction. PiperOrigin-RevId: 519822201 Change-Id: I2ed7bbb53f0c1a512017115ff29fb27a24c6b11a
* inlined_vector: get rid of IsMemcpyOk.Gravatar Abseil Team2023-03-24
| | | | | | | | | | | | | | This type trait had no precise definition, and indeed not even any documentation at all. Giving the ill-defined concept a name was harmful, because it obscured several places where the concept was used too conservatively, or even flat-out incorrectly. This CL has no behavior change: it simply expands IsMemcpyOk to the same conditions it previously had. It leaves TODOs for each place where this was too conservative or incorrect. PiperOrigin-RevId: 519278325 Change-Id: I25bc89f299f6e40b5c3bce7370ed90f33a95612f
* Use multiple empty generations so that we can detect when iterators from ↵Gravatar Evan Brown2023-03-02
| | | | | | | different empty hashtables are compared. PiperOrigin-RevId: 513568915 Change-Id: I3f387d0bae0e86749dff540e4fdd5037304ac975
* Optimize ConvertSpecialToEmptyAndFullToDeleted on ArmGravatar Connal de Souza2023-02-23
| | | | | | | BM_DropDeletes 73.4µs ± 0% 68.9µs ± 1% -6.22% (p=0.008 n=5+5) PiperOrigin-RevId: 511813266 Change-Id: Id28cece454d583e2dfe060e27cfc4720f987f009
* Merge pull request #1402 from AtariDreams:workaroundGravatar Copybara-Service2023-02-22
|\ | | | | | | | | PiperOrigin-RevId: 511695308 Change-Id: I502cdc75e993582eaca5cd91ed068238936a9640
* | Refactor swisstable iterator debug messages code. The motivations are (a) ↵Gravatar Evan Brown2023-02-21
| | | | | | | | | | | | | | distinguish between the "likely erased" and "could have rehashed" cases when generations are enabled, (b) suggest running under ASan when generations aren't enabled and doing so would narrow down the possible error cases, and (c) make ABSL_INTERNAL_ASSERT_IS_FULL not be a macro. PiperOrigin-RevId: 511255275 Change-Id: I5a44a813cd310837d0bd0209d2187b100be201e7
| * Remove workaround for gcc 5.1Gravatar Rose2023-02-21
|/ | | | We support GCC 7 and up, so we can remove this.
* Make default-constructed swisstable iterators use EmptyGroup() for ctrl_ so ↵Gravatar Evan Brown2023-02-14
| | | | | | | that we can distinguish between end() iterators and default-constructed iterators in debug mode. PiperOrigin-RevId: 509606271 Change-Id: I77b68590b3904a4cf7809b75d814d74cb89603b6
* Workaround MSan false positive.Gravatar Abseil Team2023-02-10
| | | | | | | | | On Linux Kernels >= 5.4 MSan reports a false positive when accessing thread local storage data from loaded libraries. This was reported on Chromium (which on some build configurations uses absl as a dynamic library). More info here: crbug.com/1414573. PiperOrigin-RevId: 508645053 Change-Id: I5d5a97e1ee7230cc23f3934a4ec5594b883918b4
* In sanitizer mode, detect when end iterators from different swisstables are ↵Gravatar Evan Brown2023-02-09
| | | | | | | | | compared. We change AssertSameContainer to be after AssertIsValidForComparison calls so that we can have more specific failure messages. PiperOrigin-RevId: 508472485 Change-Id: Iff2f7512086948a4aca7fd403596e8d4fde53b2a
* Fix missing includes/dependenciesGravatar Derek Mauro2023-02-02
| | | | | PiperOrigin-RevId: 506622658 Change-Id: I17ae2d97a6cadb7bdd8ebd0ec0dd3976568cb7e1
* Rollforward: in sanitizer mode, detect when references become invalidated by ↵Gravatar Evan Brown2023-02-01
| | | | | | | | | randomly rehashing on insertions when there is no reserved growth. Rollforward of ed59f62f8bbc5f05bcba2f89ee16f107e03813f2 PiperOrigin-RevId: 506314970 Change-Id: I7a654aef36bb169da9ea5c618789ee771f05fe28
* Rollback in sanitizer mode, detect when references become invalidated by ↵Gravatar Abseil Team2023-01-31
| | | | | | | | | randomly rehashing on insertions when there is no reserved growth. Rollback of ed59f62f8bbc5f05bcba2f89ee16f107e03813f2 PiperOrigin-RevId: 506003574 Change-Id: I1766321f279a3226e2821e0390387d5639d28964
* In sanitizer mode, detect when references become invalidated by randomly ↵Gravatar Evan Brown2023-01-30
| | | | | | | rehashing on insertions when there is no reserved growth. PiperOrigin-RevId: 505807487 Change-Id: I9051a04f6a75e579d16e9ae8defd404bcc377fba
* Replace absl::base_internal::Prefetch* calls with absl::Prefetch* callsGravatar Martijn Vels2023-01-27
| | | | | PiperOrigin-RevId: 505184961 Change-Id: I64482558a76abda6896bec4b2d323833b6cd7edf