aboutsummaryrefslogtreecommitdiff
path: root/absl/container
Commit message (Collapse)AuthorAgeFilesLines
* Add template keyword to example comment for Layout::WithStaticSizes.Evan Brown2024-03-181-2/+2
| | | | | | | Without this keyword, we can sometimes get cryptic compilation failures such as "error: expected ';' after alias declaration". PiperOrigin-RevId: 616933517 Change-Id: I2209f3899a4ac03c031217cec67de25bd376d355
* Fix a typo in a comment.Evan Brown2024-03-181-2/+2
| | | | | PiperOrigin-RevId: 616895950 Change-Id: I9dc9099e779df4b692496aa5ee5573ef0e7fd826
* Add a feature to container_internal::Layout that lets you specify some array ↵Abseil Team2024-03-183-66/+753
| | | | | | | | | sizes at compile-time as template parameters. This can make offset and size calculations faster. In particular, it seems to always improve the performance of AllocSize(), and it sometimes improves the performance of other functions, e.g. when the Layout object outlives the function that created it. PiperOrigin-RevId: 616817169 Change-Id: Id1d318d7d2af68783f9f59090d89c642be6ae558
* `layout`: Mark parameter of Slices with ABSL_ATTRIBUTE_UNUSED, remove old ↵Dino Radakovic2024-03-151-4/+5
| | | | | | | | | | | | | | workaround The workaround was added for a bug in GCC < 6.1., which had since been fixed. Abseil only [supports](https://github.com/google/oss-policies-info/blob/9a9bfe8a4a12be20757497074fc2f0ecb77438ad/foundational-cxx-support-matrix.md) GCC > 7.3.1. However, removing the workaround still trips even more recent GCC, such as 13.1. When `SizeSeq` is empty, `p` is not actually used. Marking it as `ABSL_ATTRIBUTE_UNUSED` silences the GCC warning for that case too. We could disable `Slices` altogether when `SizeSeq` is empty, but that would be a breaking change (even though this API is internal), and possibly hurt generic programming use (they'd have to check if their parameter packs are empty). PiperOrigin-RevId: 616245873 Change-Id: I77f7b0b921dfd63fb01c5223851ad1d8a7da233b
* `layout`: Use auto return type for functions that explicitly instantiate ↵Dino Radakovic2024-03-151-6/+2
| | | | | | | | | | std::tuple in return statements This improves readability by avoiding spelling the same type twice, the first time with even more boilerplate (e.g. `typename`). Return type deduction is a C++14 feature, and Abseil [currently supports](https://github.com/google/oss-policies-info/blob/9a9bfe8a4a12be20757497074fc2f0ecb77438ad/foundational-cxx-support-matrix.md) C++ >= 14. PiperOrigin-RevId: 616218396 Change-Id: I82aeec878dd69001d2cf822db6512f5a62baec02
* Roll back extern template instatiations in swisstable due to binary size ↵Evan Brown2024-03-1311-341/+7
| | | | | | | increases in shared libraries. PiperOrigin-RevId: 615497725 Change-Id: Ic29db8923ea4ea7cd0b01b396896fa9fff8c74b0
* Test that rehash(0) reduces capacity to minimum.Vitaly Goldshteyn2024-03-131-1/+6
| | | | | PiperOrigin-RevId: 615380243 Change-Id: I5400b40a6bc5ac52ece5d4fa6da7df9e4ff50855
* Add extern templates for common swisstable types.Evan Brown2024-03-1211-7/+341
| | | | | | | | Motivation: mitigate linker input size increase from swisstable optimizations. Note: the changes in raw_hash_set.h are fixing build errors that happened when adding the explicit instantiations. The change in unchecked_deref is because set iterators have const reference access whereas map iterators have mutable reference access and the function is never actually called for sets (it's used in raw_hash_map) so it wasn't needed before. I'm not sure why the soo_slot/soo_iterator problems didn't cause compile errors earlier. PiperOrigin-RevId: 615174043 Change-Id: Iac5eb2332a76e9b70021156fbb2b8def47a5391d
* Make swisstable SOO support GDB pretty printing and still compile in OSS.Evan Brown2024-03-121-8/+3
| | | | | PiperOrigin-RevId: 615131303 Change-Id: I68fcbdd943594983c67f8e07810b05d5fa9a6f2e
* Move GCC uninitialized memory warning suppression into MaybeInitializedPtr.Evan Brown2024-03-111-16/+21
| | | | | PiperOrigin-RevId: 614701769 Change-Id: I7c2143dd467e376eb4936ef894f3413bba681419
* Replace usages of absl::move, absl::forward, and absl::exchange with theirDerek Mauro2024-03-114-15/+15
| | | | | | | std:: equivalents PiperOrigin-RevId: 614687225 Change-Id: I07421db08ee9c221e561f42e3bf8345fb5321401
* Avoid MSan: use-of-uninitialized-value error in find_non_soo.Evan Brown2024-03-071-2/+1
| | | | | PiperOrigin-RevId: 613590317 Change-Id: I69f095681102e5492916085ada0eed085a75765b
* Add ABSL_ATTRIBUTE_UNUSED to variables used in an ABSL_ASSUME.Evan Brown2024-03-061-2/+2
| | | | | PiperOrigin-RevId: 613305668 Change-Id: Ifc247f48ea476745eaaf0dd41dbdab8404a6cafb
* Implement small object optimization in swisstable - disabled for now.Evan Brown2024-03-066-371/+1091
| | | | | | | | | Details: - We use the space for control/slots pointers as the inline buffer. - We use a max inline capacity of 1 to make the implementation much simpler and to avoid having to randomize the iteration order for inline tables. - For iteration of inline tables, we introduce the kSooControl buffer which just has 1 full control byte followed by 1 sentinel control byte so that incrementing yields an end() iterator. We don't access kSooControl during lookups - only iteration. PiperOrigin-RevId: 613253492 Change-Id: Id98ff11842f8bef27ac7ed88138dc03b46ce4fa6
* Extract `InsertPosition` function to be able to reuse it.Vitaly Goldshteyn2024-03-042-13/+27
| | | | | PiperOrigin-RevId: 612560213 Change-Id: Id75dfd1222a0bed8ec72ce21e4a97b1d09fc9eaa
* PR #1632: inlined_vector: Use trivial relocation for `erase`Arthur O'Dwyer2024-03-033-8/+86
| | | | | | | | | | | | | | | Imported from GitHub PR https://github.com/abseil/abseil-cpp/pull/1632 Prior art for the `vector::erase` optimization: https://github.com/AmadeusITGroup/amc/blob/efcb7be/include/amc/vectorcommon.hpp#L176-L180 https://github.com/bloomberg/bde/blob/e15f05be6/groups/bsl/bslalg/bslalg_arrayprimitives.h#L3787-L3799 https://github.com/facebook/folly/blob/d24bf04/folly/FBVector.h#L1254-L1262 https://github.com/qt/qtbase/blob/fbfee2d/src/corelib/tools/qarraydataops.h#L856-L861 Merge 6ce011079ccf945ae95434ce45ea6c5e3a088af8 into 55d28d4b3b82f9a47b3fa9b811b675a032820621 Merging this change closes #1632 COPYBARA_INTEGRATE_REVIEW=https://github.com/abseil/abseil-cpp/pull/1632 from Quuxplusone:trivial-erase 6ce011079ccf945ae95434ce45ea6c5e3a088af8 PiperOrigin-RevId: 612278964 Change-Id: I327ace8a38292b4610c6be031cc334e77c76fd35
* Create `BM_GroupPortable_Match`.Vitaly Goldshteyn2024-03-031-0/+13
| | | | | PiperOrigin-RevId: 612201313 Change-Id: Ia9e7f146f5e1ecaffcb15de694049b716db38d02
* Rework casting in raw_hash_set's `IsFull()`.Paul Rigge2024-02-281-1/+3
| | | | | | | Instead of casting an int to the enum type where the int does not have an associated enum value, cast the enum to its underlying type. This should be no functional change but make some linters happier. PiperOrigin-RevId: 611172311 Change-Id: I9ae10f8fa2029014236f60a90ee2ab2273c66fa5
* Add braces for conditional statements in raw_hash_map functions.Evan Brown2024-02-231-3/+5
| | | | | | | The current version violates the Google C++ style guide - see https://google.github.io/styleguide/cppguide.html#Formatting_Looping_Branching. This code does not fit into the historical exception that "the curly braces for the controlled statement or the line breaks inside the curly braces may be omitted if as a result the entire statement appears on either a single line (in which case there is a space between the closing parenthesis and the controlled statement) or on two lines (in which case there is a line break after the closing parenthesis and there are no braces)." PiperOrigin-RevId: 609789188 Change-Id: Id7ae9596e454dac5581d19939564c07670077f92
* Optimize `prepare_insert`, when resize happens. It removes single ↵Vitaly Goldshteyn2024-02-221-11/+13
| | | | | | | unnecessary probing before resize that is beneficial for small tables the most. PiperOrigin-RevId: 609547787 Change-Id: If6584919b4c93945ea078b1c1a9f57b355dce924
* Change find_or_prepare_insert to return std::pair<iterator, bool> to match ↵Evan Brown2024-02-212-22/+21
| | | | | | | return type of insert. PiperOrigin-RevId: 609058024 Change-Id: I2f7cc2daf862e7e2d23acd6dd3fe85cb1945d5f0
* PR #1618: inlined_vector: Use trivial relocation for `SwapInlinedElements`Arthur O'Dwyer2024-02-212-17/+47
| | | | | | | | | | | | | | Imported from GitHub PR https://github.com/abseil/abseil-cpp/pull/1618 I noticed while working on #1615 that `inlined_vector` could use the trivial relocatability trait here, too. Here the memcpy codepath already exists; we just have to opt in to using it. Merge 567a1dd9b6b3352f649e900b24834b59e39cfa14 into a7012a5bfcf26a41b9dd32d4c429004773503dd6 Merging this change closes #1618 COPYBARA_INTEGRATE_REVIEW=https://github.com/abseil/abseil-cpp/pull/1618 from Quuxplusone:trivial-swap 567a1dd9b6b3352f649e900b24834b59e39cfa14 PiperOrigin-RevId: 609019296 Change-Id: I4055ab790245752179e405b490fcd479e7389726
* Improve raw_hash_set tests.Abseil Team2024-02-211-14/+29
| | | | | PiperOrigin-RevId: 608947694 Change-Id: Ie53a91c4d78dcb80c57227616b488ec64b23c588
* Use const_cast to avoid duplicating the implementation of ↵Evan Brown2024-02-201-2/+1
| | | | | | | | raw_hash_set::find(key). Motivation: the implementation becomes more complicated with small object optimization. PiperOrigin-RevId: 608742838 Change-Id: I55fc42321b1967f9c7bbee49817a2f2d4ee44b56
* Introduce `Group::MaskNonFull` without usage.Abseil Team2024-02-153-0/+68
| | | | | | | | It can be used instead of `MaskEmptyOrDeleted` in case of inserting to empty table. `MaskNonFull` requires less operations, in particular it eliminates `_mm_set1_epi8` and `_mm_cmpgt_epi8` operations. PiperOrigin-RevId: 607587394 Change-Id: Ia48f922d1ca6de38cc91e7ab0d608c45f8f2c446
* Make `begin()` to return `end()` on empty tables.Abseil Team2024-02-081-5/+6
| | | | | PiperOrigin-RevId: 605460827 Change-Id: I57007a7ad18829e7bfed27ba65871afbd227d012
* Switch rank structs to be consistent with written guidance in ↵Matt Kulukundis2024-02-071-9/+10
| | | | | | | go/ranked-overloads PiperOrigin-RevId: 605125821 Change-Id: I2ee260eaf283acafd80abfd2b7419a0e9f597a78
* Avoid hash computation and `Group::Match` in small tables copy and use ↵Abseil Team2024-02-072-22/+102
| | | | | | | `IterateOverFullSlots` for iterating for all tables. PiperOrigin-RevId: 605116090 Change-Id: Ia65c664421f7630225b00f1c45c636b4681121ce
* Add absl_container_hash-based HashEq specializationDennis Kormalev2024-02-078-6/+270
| | | | | | | | | | | | | | SwissTable provides support for heterogeneous lookup in associative containers through transparent Hash and Eq types. However, it is not possible for user types to provide additional specializations to allow their types to use this functionality. This CL brings ability for user types to specify their own transparent absl_container_hash and (optionally) absl_container_eq inner types to achieve the same functionality. PiperOrigin-RevId: 604994859 Change-Id: I302486d292c9a18b7d4c77033227008f5539e354
* Enable StringLikeTest in hash_function_defaults_testDennis Kormalev2024-02-051-6/+4
| | | | | PiperOrigin-RevId: 604369517 Change-Id: I6024a8828563c5a2487ba85ede91a88d7059f9c8
* Optimize raw_hash_set destructor.Abseil Team2024-02-012-18/+87
| | | | | | | | | | There are three optimizations here: 1. Early exit in case all slots were destroyed. especially useful for empty tables. 2. MatchFull is used in order to iterate over all full slots. 3. Portable group is used for `MatchFull` in the case of small table. PiperOrigin-RevId: 603434899 Change-Id: I40bc90d17331d579cfbb1b4e0693f0913e5c38e4
* Type erased hash_slot_fn that depends only on key types (and hash function).Abseil Team2024-01-3116-16/+214
| | | | | PiperOrigin-RevId: 603148301 Change-Id: Ie2e5702995c9e1ef4d5aaab23bc89a1eb5007a86
* Replace `testonly = 1` with `testonly = True` in abseil BUILD files.Shahriar Rouf2024-01-311-20/+20
| | | | | | | https://bazel.build/build/style-guide#other-conventions PiperOrigin-RevId: 603084345 Change-Id: Ibd7c9573d820f88059d12c46ff82d7d322d002ae
* Avoid extra `& msbs` on every iteration over the mask for GroupPortableImpl.Abseil Team2024-01-312-24/+79
| | | | | PiperOrigin-RevId: 602974812 Change-Id: Ic35b41e321b9456a8ddd83470ee2eb07c51e3180
* Early return from destroy_slots for trivially destructible types in ↵Abseil Team2024-01-3011-27/+122
| | | | | | | flat_hash_{*}. PiperOrigin-RevId: 602813933 Change-Id: I744fe438281755a141b2fd47e54ab9c6c0fad5a3
* Avoid export of testonly target absl::test_allocator in CMake buildsDerek Mauro2024-01-301-0/+1
| | | | | | | Closes #1536 PiperOrigin-RevId: 602764437 Change-Id: Ia5c20a3874262a2ddb8797f608af17d7e86dd6d6
* Introduce `RawHashSetLayout` helper class.Abseil Team2024-01-291-41/+63
| | | | | PiperOrigin-RevId: 602485199 Change-Id: I5cc10eb8dcfe5988cf939080a224522e02ad8607
* Use absl::NoDestructor for global HashtablezSampler.Abseil Team2024-01-243-1/+4
| | | | | PiperOrigin-RevId: 601156448 Change-Id: Id6d19bda7eb3acee11cfab3a95e611996d6ef4cc
* Remove code pieces for no longer supported GCC versions.Abseil Team2024-01-222-4/+1
| | | | | | | The minimum supported version today is GCC 7 (`__GNUC__ >= 7`). PiperOrigin-RevId: 600475215 Change-Id: I1aa46384f1e75f268649a48dbe2b42f3475bb07f
* Added benchmarks for smaller size copy constructors.Abseil Team2024-01-181-3/+4
| | | | | PiperOrigin-RevId: 599538858 Change-Id: I9e92f4c9cfef1bfe6f8f925efe0ede3f309b6bf4
* Speed up `raw_hash_map::[]` with ABSL hardening enabled by unchecking ↵Abseil Team2024-01-122-3/+16
| | | | | | | dereference of iterator returned by `try_emplace`. PiperOrigin-RevId: 597920257 Change-Id: I1b2e8f10a2f1efa763a6f0760294beafdb6fd9c0
* Enable ABSL_BTREE_ENABLE_GENERATIONS and ABSL_SWISSTABLE_ENABLE_GENERATIONS ↵Abseil Team2024-01-114-10/+14
| | | | | | | | | | | | | | with ABSL_HAVE_HWADDRESS_SANITIZER. It will detect bugs similar to Asan. Also updated related tests to pass with HWASAN. They are still flaky because of nature of HWASAN algorithm, but test can be update to avoid flakiness, which I will do in followup patches. PiperOrigin-RevId: 597613798 Change-Id: Ic8af36a268ca041c002eb561b946aa2d9b93996a
* Speed up `raw_hash_set::contains()` when ABSL hardening is enabled by ↵Abseil Team2024-01-031-1/+15
| | | | | | | removing the iterator invalidation check from the comparison that contains performs. PiperOrigin-RevId: 595460301 Change-Id: I9a5d6c81385e38184f4848c58209adc5d32bb7be
* Migrate static objects to NoDestructor in tests, testing libraries and ↵Abseil Team2023-12-265-13/+24
| | | | | | | benchmarks. PiperOrigin-RevId: 593918110 Change-Id: Ide100c69b10e28011af17c7f82bb10eea072cad4
* Unify btree EmptyNode allocation code across compilers.Abseil Team2023-12-201-23/+9
| | | | | | | | | We currently have a workaround for MSVC, which has constexpr pointer arithmetic bugs. The bug seems to still exist and the existing code for non-MSVC compilers doesn't build. This alternative constexpr constructor avoids pointer arithmetic and seems to be working for all, including MSVC. PiperOrigin-RevId: 592586957 Change-Id: Ic585693c3a7abaab5fbbc0954b8ee924994f8dbf
* Create and destroy tables outside of the timer and in batch in Reserve ↵Abseil Team2023-12-201-12/+26
| | | | | | | benchmarks. PiperOrigin-RevId: 592483250 Change-Id: I55fa9982c4dbc723b30957cb31da95251e368707
* Add a pragma to disable a maybe-uninitialized warning for GCC12+Abseil Team2023-12-193-1/+14
| | | | | PiperOrigin-RevId: 592301543 Change-Id: I97e4df805c7313896228430a50a7f991127f3e30
* Refactor `EraseMetaOnly` to speed up single group tables.Abseil Team2023-12-193-15/+42
| | | | | PiperOrigin-RevId: 592272653 Change-Id: I895c5786555227bdc88ab0a4cce8cf5ba65222a1
* Add the `BM_EraseEmplace` benchmark that constantly adds and removes the ↵Abseil Team2023-12-181-0/+18
| | | | | | | same element. PiperOrigin-RevId: 591987002 Change-Id: Ic1ed2063aeb95a6e814eefcbed024e1a5a1d8d2f
* Unit-tests to verify ABSL raw_hash_set does not double-hash in prodAbseil Team2023-12-123-0/+75
| | | | | PiperOrigin-RevId: 590337123 Change-Id: Ib98bbb5a5dadbce5e891567038e016f4da2efc0b
generated by cgit v1.2.3 (git 2.39.1) at 2025-04-16 07:31:52 +0000