aboutsummaryrefslogtreecommitdiff
path: root/absl/container
Commit message (Collapse)AuthorAgeFilesLines
* inlined_vector: get rid of IsMemcpyOk.Abseil Team2023-03-242-60/+229
| | | | | | | | | | | | | | 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.Abseil Team2023-03-241-4/+46
| | | | | | | | 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 ↵Evan Brown2023-03-023-25/+68
| | | | | | | different empty hashtables are compared. PiperOrigin-RevId: 513568915 Change-Id: I3f387d0bae0e86749dff540e4fdd5037304ac975
* Optimize ConvertSpecialToEmptyAndFullToDeleted on ArmConnal de Souza2023-02-231-3/+4
| | | | | | | 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:workaroundCopybara-Service2023-02-221-8/+2
|\ | | | | | | | | PiperOrigin-RevId: 511695308 Change-Id: I502cdc75e993582eaca5cd91ed068238936a9640
| * Remove workaround for gcc 5.1Rose2023-02-211-8/+2
| | | | | | | | We support GCC 7 and up, so we can remove this.
* | Resolve TODO: remove C++11 workaroundsRose2023-02-222-2/+2
| | | | | | | | 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) ↵Evan Brown2023-02-212-56/+101
|/ | | | | | | 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
* Make default-constructed swisstable iterators use EmptyGroup() for ctrl_ so ↵Evan Brown2023-02-142-33/+41
| | | | | | | that we can distinguish between end() iterators and default-constructed iterators in debug mode. PiperOrigin-RevId: 509606271 Change-Id: I77b68590b3904a4cf7809b75d814d74cb89603b6
* Workaround MSan false positive.Abseil Team2023-02-103-0/+8
| | | | | | | | | 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 ↵Evan Brown2023-02-092-22/+77
| | | | | | | | | 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/dependenciesDerek Mauro2023-02-023-0/+6
| | | | | PiperOrigin-RevId: 506622658 Change-Id: I17ae2d97a6cadb7bdd8ebd0ec0dd3976568cb7e1
* Rollforward: in sanitizer mode, detect when references become invalidated by ↵Evan Brown2023-02-015-9/+72
| | | | | | | | | 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 ↵Abseil Team2023-01-315-72/+9
| | | | | | | | | 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 ↵Evan Brown2023-01-305-9/+72
| | | | | | | rehashing on insertions when there is no reserved growth. PiperOrigin-RevId: 505807487 Change-Id: I9051a04f6a75e579d16e9ae8defd404bcc377fba
* Replace absl::base_internal::Prefetch* calls with absl::Prefetch* callsMartijn Vels2023-01-272-10/+14
| | | | | PiperOrigin-RevId: 505184961 Change-Id: I64482558a76abda6896bec4b2d323833b6cd7edf
* Sort CMakeList deps for raw_hash_set and raw_hash_set_test.Evan Brown2023-01-231-5/+5
| | | | | PiperOrigin-RevId: 504045295 Change-Id: I110d4573087358e17a719def29e8037adfac6d15
* Add CodegenAbslRawHashSetStringFindNeEnd function, which is useful because ↵Evan Brown2023-01-201-0/+8
| | | | | | | the find isn't inlined but the iterator comparison is. PiperOrigin-RevId: 503473637 Change-Id: I02b8d95b7a1b738314c4f07a863c7606f822f079
* In sanitizer mode, detect when references become invalidated after reserved ↵Evan Brown2023-01-172-10/+43
| | | | | | | growth runs out. PiperOrigin-RevId: 502625638 Change-Id: I1c06b2162dbdaaa6a36cea503ac6d07cd157b2e2
* In sanitizer mode, detect when invalidated iterators are compared.Evan Brown2023-01-052-13/+25
| | | | | PiperOrigin-RevId: 499964205 Change-Id: I45a1d62a5e093921946e7c3c7ab31480252b330e
* Fix a bug in iterator validation code in which we don't update the table's ↵Evan Brown2022-12-222-1/+16
| | | | | | | reserved growth if the reservation wouldn't grow the table. PiperOrigin-RevId: 497246219 Change-Id: I9671236f56d10851c49de71c21899368be6c3a00
* Update `FixedArray` doc comments to match actual template param namesLawrence Wolf-Sonkin2022-12-221-5/+4
| | | | | | | | | | * The template parameter provided to `FixedArray` for the number of inline elements is named `N` * If left defaulted, which is recommended, `FixedArray` chooses the number of inline elements by itself * The `inline_elements` static class member contains the actual number of inlinable elements * Previously the docs referred to the template parameter as `inline_elements` instead of `N`. PiperOrigin-RevId: 497185546 Change-Id: I321092826d956704c0074062d2a7b924b28e36d0
* Restrict visibility of absl/container:hash_function_defaults.Chris Kennelly2022-12-191-0/+3
| | | | | PiperOrigin-RevId: 496514638 Change-Id: I45b8dfe01c83915c460711339d2d8c38604c8d81
* In sanitizer mode, add generations to swisstable iterators and backing ↵Evan Brown2022-12-195-63/+310
| | | | | | | arrays so that we can detect invalid iterator use. PiperOrigin-RevId: 496455788 Change-Id: I83df92828098a3ef1181b4e454f3ac5d3ac7a2f2
* Optimize raw_hash_set CountLeadingEmptyOrDeleted() on ArmConnal de Souza2022-12-191-6/+8
| | | | | | | | name old cpu/op new cpu/op delta BM_Group_CountLeadingEmptyOrDeleted 0.98ns ± 0% 0.78ns ± 0% -20.51% (p=0.000 n=10+10) PiperOrigin-RevId: 496397005 Change-Id: I1c6b325b14566da194f21d3387b6f4d838bf0b34
* Fix some ClangTidy warnings in raw_hash_set code.Evan Brown2022-12-083-27/+18
| | | | | PiperOrigin-RevId: 493993005 Change-Id: I0705be8678022a9e08a1af9972687b7955593994
* Change CommonFields from a private base class of raw_hash_set to be the ↵Evan Brown2022-12-082-48/+44
| | | | | | | | | | | first member of the settings_ CompressedTuple so that we can move growth_left into CommonFields. This allows for removing growth_left as a separate argument for a few functions. Also, move the infoz() accessor functions to be before the data members of CommonFields to comply with the style guide. PiperOrigin-RevId: 493918310 Change-Id: I58474e37d3b16a1513d2931af6b153dea1d809c2
* Add a compilation test for recursive hash map typesDerek Mauro2022-12-022-0/+16
| | | | | PiperOrigin-RevId: 492535520 Change-Id: I2e58b39bd4ab3064f675474c5e712c76fac02674
* Move the vtable into a function to delay instantiation until the function isSamuel Benzaquen2022-12-012-33/+56
| | | | | | | | | | | | | called. When the variable is a global the compiler is allowed to instantiate it more aggresively and it might happen before the types involved are complete. When it is inside a function the compiler can't instantiate it until after the functions are called. Remove an unused member from the vtable. Replace transfer_slot_fn with a generic function when relocation is available to reduce duplication. PiperOrigin-RevId: 492227302 Change-Id: I07499f63b91c59c0ae42402683387c7b84a6f0ee
* Reduce flat_hash_{set,map} generated code size.Abseil Team2022-11-286-349/+579
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This CL makes a bunch of changes (mostly to raw_hash_set which underlies flat_hash_set and flat_hash_map). Techniques used: * Extract code that does not depend on the specific hash table type into common (non-inlined) functions. * Place ABSL_ATTRIBUTE_NOINLINE directives judiciously. * Out-of-line some slow paths. Reduces sizes of some large binaries by ~0.5%. Has no significant performance impact on a few performance critical binaries. ## Speed of fleetbench micro-benchmarks Following is a histogram of %-age changes in [fleetbench](https://github.com/google/fleetbench) hot_swissmap_benchmark results. Negative numbers indicate a speedup caused by this change. Statistically insignificant changes are mapped to zero. XXX Also run and merge in cold_swissmap_benchmark Across all 351 benchmarks, the average speedup is 0.38%. The best speedup was -25%, worst slowdown was +6.81%. ``` Count: 351 Average: -0.382764 StdDev: 3.77807 Min: -25 Median: 0.435135 Max: 6.81 --------------------------------------------- [ -25, -10) 16 4.558% 4.558% # [ -9, -8) 2 0.570% 5.128% [ -8, -7) 1 0.285% 5.413% [ -7, -6) 1 0.285% 5.698% [ -6, -5) 2 0.570% 6.268% [ -5, -4) 5 1.425% 7.692% [ -4, -3) 13 3.704% 11.396% # [ -3, -2) 15 4.274% 15.670% # [ -2, -1) 26 7.407% 23.077% ## [ -1, 0) 14 3.989% 27.066% # [ 0, 1) 185 52.707% 79.772% ############ [ 1, 2) 14 3.989% 83.761% # [ 2, 3) 8 2.279% 86.040% # [ 3, 4) 7 1.994% 88.034% [ 4, 5) 32 9.117% 97.151% ## [ 5, 6) 6 1.709% 98.860% [ 6, 7) 4 1.140% 100.000% ``` We looked at the slowdowns and they do not seem worth worrying about. E.g., the worst one was: ``` BM_FindHit_Hot<::absl::node_hash_set,64>/set_size:4096/density:0 2.61ns ± 1% 2.79ns ± 1% +6.81% (p=0.008 n=5+5) ``` ## Detailed changes * Out-of-line slow paths in hash table sampler methods. * Explicitly unregister from sampler instead of from destructor. * Introduced a non-templated CommonFields struct that holds some of the hash table fields (infoz, ctrl, slots, size, capacity). This struct can be passed to new non-templated helpers. The struct is a private base class of raw_hash_set. * Made non-inlined InitializeSlots<> that is only templated on allocator and size/alignment of the slot type so that we can share instantiations across types that have the same size/alignment. * Moved some infrequently called code paths into non-inlined type-erased. functions. Pass a suite of type-specific function pointers to these routines for when they need to operate on slots. * Marked some methods as non-inlined. * Avoid unnecessary reinitialization in destructor. * Introduce UpdateSpine type-erased helper that is called from clear() and rehash(). PiperOrigin-RevId: 491413386 Change-Id: Ia5495c5a6ec73622a785a0d260e406ddb9085a7c
* Refactor btree iterator generation code into a base class rather than using ↵Evan Brown2022-11-221-49/+60
| | | | | | | ifdefs inside btree_iterator. PiperOrigin-RevId: 490317784 Change-Id: I4ffe2a1ad2e39890790e278d82eec7223b67908c
* Improve error messages when comparing btree iterators when generations are ↵Evan Brown2022-11-212-20/+35
| | | | | | | | | | enabled. - Add assertions that the iterators haven't been invalidated. - Also refactor some generation-related code to define the functions inside ABSL_BTREE_ENABLE_GENERATIONS ifdef/else branches. PiperOrigin-RevId: 489988637 Change-Id: I34d32ed2e27cf89f7f8bb5d9c1f6770bb40b8794
* Add a new API for `extract_and_get_next()` in b-tree that returns both the ↵Evan Brown2022-11-154-6/+153
| | | | | | | | extracted node and an iterator to the next element in the container. Motivation: it can be useful, when calling `extract` to maintain an iterator next to the location of the extracted element. `std::set`, et al. allow for this because they have iterator stability. `absl::{flat,node}_hash_{set,map}` allow for this because they are guaranteed not to rehash when elements are removed so they also have iterator stability across calls to `extract()`. But b-tree doesn't support this use case without this API because removing elements can cause rebalancing, which invalidates iterators. We can get the next iterator without this API using `lower_bound(node_handle.value())`, but that requires an extra lookup. PiperOrigin-RevId: 488721247 Change-Id: Id66f17311bf53678f536e4e4f070775f5ce0c542
* Stop unnecessary clearing of fields in ~raw_hash_set.Abseil Team2022-11-111-11/+13
| | | | | | | | | | | 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
* Improve error messages when comparing btree iterators.Evan Brown2022-11-102-8/+58
| | | | | | | | - 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
* Improve error messages when comparing swisstable iterators.Evan Brown2022-11-092-9/+58
| | | | | | | 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
* Auto increase inlined capacity whenever it does not affect class' size.Abseil Team2022-11-093-12/+68
| | | | | PiperOrigin-RevId: 487292771 Change-Id: I2454e28fe91017fb2954a4ad194712fcafe893d2
* Fix some invalid iterator bugs in btree_test.cc for multi{set,map} ↵Evan Brown2022-11-071-29/+39
| | | | | | | | | | | | | emplace{_hint} tests. 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/emplace https://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
* Merge pull request #1287 from GOGOYAO:patch-1Copybara-Service2022-11-031-2/+2
|\ | | | | | | | | PiperOrigin-RevId: 485886212 Change-Id: Ic7a710913f8376d07b9bdeb987d007ec04e48465
| * Initialize `Allocation` to eliminate compile errorGOGOYAO2022-10-041-2/+2
| | | | | | | | | | | | 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] ```
* | Improve error messages when dereferencing invalid swisstable iterators.Evan Brown2022-11-012-23/+64
| | | | | | | | | | | | | | | | | | - 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
* | Add a warning about extract invalidating iterators (not just the iterator of ↵Abseil Team2022-10-312-5/+7
| | | | | | | | | | | | | | the element being extracted). PiperOrigin-RevId: 485120182 Change-Id: Ic54d538721678bed0a748dacbf33c319e62b93b8
* | `absl::InlinedVector::swap` supports non-assignable types.Abseil Team2022-10-253-104/+254
| | | | | | | | | | PiperOrigin-RevId: 483752526 Change-Id: Ie6b63a4a3cc7593e5b8bf255ba571a77d609ce04
* | Improve b-tree error messages when dereferencing invalid iterators.Evan Brown2022-10-252-2/+22
| | | | | | | | | | | | | | | | - Check for invalid generation before checking for other types of invalid iterators. - Check specifically for dereferencing end() iterators. PiperOrigin-RevId: 483725646 Change-Id: Ibca19c48b1b242384683580145be8fb9ae707bc8
* | Use btree iterator subtraction instead of std::distance in erase_range() and ↵Evan Brown2022-10-182-2/+2
| | | | | | | | | | | | | | count(). PiperOrigin-RevId: 481979737 Change-Id: I69f53665b0463a7d8d80f2a3feedfdd95d32b012
* | Implement btree_iterator::operator-, which is faster than std::distance for ↵Evan Brown2022-10-177-0/+130
| | | | | | | | | | | | | | | | btree iterators. 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
* | `absl::InlinedVector` supports move assignment with non-assignable types.Abseil Team2022-10-125-12/+165
| | | | | | | | | | PiperOrigin-RevId: 480601268 Change-Id: I5a639da57b79ae600387c81e662d5c1542b2bf99
* | Add static_cast<void*> to the sources for trivial relocations to avoid ↵Evan Brown2022-10-072-4/+6
| | | | | | | | | | | | | | spurious -Wdynamic-class-memaccess errors in the presence of other compilation errors. PiperOrigin-RevId: 479625866 Change-Id: Ia10ad35a2f58ffb3f36f996d357d5e126b181e1c
* | Eliminate use of internal interfacesGennadiy Rozental2022-10-062-2/+2
| | | | | | | | | | PiperOrigin-RevId: 479325483 Change-Id: I9c4384173ce996818e0cf749c0fc465d6e9aaf8c
* | No changes in OSS.Gennadiy Rozental2022-10-043-7/+26
|/ | | | | PiperOrigin-RevId: 478869244 Change-Id: Id16eb1e5036e95a5e2a990a647f1f7090129a009
generated by cgit v1.2.3 (git 2.39.1) at 2025-05-05 00:53:27 +0000