summaryrefslogtreecommitdiff
path: root/absl/container/internal
Commit message (Collapse)AuthorAge
* Make raw_hash_set::destroy_slots no longer public. It was never meant to be ↵Gravatar Evan Brown2023-08-29
| | | | | | | a public member of the API. PiperOrigin-RevId: 561061460 Change-Id: Ib804d3d3cf427ebfc9e622db9915287eb8045e26
* Remove the has_element function and use FindElement instead.Gravatar Evan Brown2023-08-17
| | | | | PiperOrigin-RevId: 557920808 Change-Id: I1eb0ca1ea9e9de542321fbc23d82218c5d449fbf
* Update an old comment that refers to obsolete types.Gravatar Evan Brown2023-08-15
| | | | | PiperOrigin-RevId: 557187112 Change-Id: I7c3e4be0ab5a7451173da7a0ded53a3d227bb093
* Add missing includes in raw_hash_set.h.Gravatar Evan Brown2023-08-11
| | | | | PiperOrigin-RevId: 556065631 Change-Id: I7e69b1495946c42fab185a1bc23e9564bfbd5e41
* Include what you spellGravatar Dmitri Gribenko2023-08-11
| | | | | PiperOrigin-RevId: 555894810 Change-Id: I349c94e7c6e7ba1dbd817aa8e4340c1dada84654
* Store infoz on the heap instead of inline and store it only when we are ↵Gravatar Evan Brown2023-08-04
| | | | | | | sampling the current allocation. PiperOrigin-RevId: 553847957 Change-Id: Idd131d0362bf36bd22d9bd20df54bd9ae50f0e28
* Optimize Swissmap Match on Arm.Gravatar Connal de Souza2023-08-04
| | | | | | | | | | | | | | | | | Currently we require only a single bit to be set in each abstract bit for iterable bitmasks. However, in most cases, where we have a single match, or no matches in a group, iteration is not needed. We move the masking to the iteration function instead of having it as a requirement for iterable Bitmask construction. This is 4-8% faster for Find and Insert operations. This can hurt performance if we need to iterate many times (there are many matches in the same Group), however this is unlikely, even if we assume the table is completely full. If there are 0 or 1 matches in a group, or the first match is the correct item we are looking for, we save 1 instruction/cycle (most cases) If there are 2 matches in a group, and the first is a false positive, this is neutral (< 3%) If there are more than 2 matches in a group and the first two are false positives, this can be slower by 1 cycle/instruction per additional iteration (< 0.1%) No change to x86. PiperOrigin-RevId: 553831814 Change-Id: I08620899847eaf0086da989d829a1029ea24173a
* Update the comment for capacity_ to mention recent experiments to compress ↵Gravatar Evan Brown2023-08-03
| | | | | | | the field and store it together with size_. PiperOrigin-RevId: 553499768 Change-Id: Ia6eec6d580475a2b76a2415bfb35bcc08131ae34
* 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.
generated by cgit v1.2.3 (git 2.39.1) at 2025-01-20 02:37:24 +0000