summaryrefslogtreecommitdiff
path: root/absl/container
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
* InlinedVector: Disable CFI checking during the reinterpret_cast on theGravatar Derek Mauro2023-07-27
| | | | | | | | | | heap allocation path. The cast occurs before the memory is initialized. See also: https://clang.llvm.org/docs/ControlFlowIntegrity.html#bad-cast-checking. PiperOrigin-RevId: 551542366 Change-Id: Id5834892c36a5cb8ec095bcfee3e9e31f20c48ae
* 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
| |
* | Add support for stateful allocators to absl::FixedArray.Gravatar Abseil Team2023-05-26
| | | | | | | | | | PiperOrigin-RevId: 535534819 Change-Id: Iccf8da3e0b084131e4c0dba205f3e190d3a66f4e
* | 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
* Merge pull request #1441 from Vertexwahn:fix-spelling3Gravatar Copybara-Service2023-05-03
|\ | | | | | | | | PiperOrigin-RevId: 529086715 Change-Id: Id5462322d5707a1b4475438520fcb70ee7b15450
| * Fix spelling mistakesGravatar Vertexwahn2023-05-02
|/
* 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: optimize the move-assignment fast path.Gravatar Aaron Jacobs2023-03-31
| | | | | | | | We know that the elements are trivially destructible if this path is used, so there is no need to call their destructors one by one. PiperOrigin-RevId: 521088624 Change-Id: I3edff97a073770f99031eefa7a34968fad5d7880
* inlined_vector: stop sharing the memcpy-based move-assignment path.Gravatar Aaron Jacobs2023-03-31
| | | | | | | | | The fact that this is called from paths where the element type may not have a trivial destructor is preventing an optimization (see the TODO). Stop calling from those paths so that the optimization can be made in an upcoming CL. PiperOrigin-RevId: 521087730 Change-Id: Id2b66d8f36bb0d294784d0793fdd8f07e315739f
* inlined_vector: remove excess restrictions on copy constructor fast path.Gravatar Aaron Jacobs2023-03-31
| | | | | | | | The copy constructor isn't doing or simulating copy assignment; nor is it destroying anything. We don't need to require that those operations be trivial. PiperOrigin-RevId: 521020499 Change-Id: I0f36a720384b333ea15e6c8275872fd4fd9a738f
* 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
* inlined_vector_test: add coverage of moving vectors of unique pointers.Gravatar Abseil Team2023-03-24
| | | | | | | | std::unique_ptr is trivially relocatable, but not trivially destructible. This will be important coverage to ensure correctness of upcoming commit(s) that expand the use of memcpy to more trivially relocatable types. PiperOrigin-RevId: 519270234 Change-Id: I8e584a405633dac89bf1f67eab8145971d2ddab2
* 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
* | Resolve TODO: remove C++11 workaroundsGravatar Rose2023-02-22
| | | | | | | | We no longer support C++11 as per the Google C++ support documentation: we support C++14 and up, so we can remove these workarounds.
* | 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
generated by cgit v1.2.3 (git 2.39.1) at 2024-05-17 22:25:30 +0000