aboutsummaryrefslogtreecommitdiff
path: root/absl/container
Commit message (Collapse)AuthorAgeFilesLines
...
* 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
* Add `MaskFull` to `Group`.Abseil Team2023-12-122-12/+59
| | | | | | | | | It is not used at the moment. Usage is planned to be submitted separately. Useful for faster iterating over all slots in the internal functions. PiperOrigin-RevId: 590300049 Change-Id: I081f33113268761db868771d29796d94c24e4e7a
* Small table growth optimization.Abseil Team2023-12-073-101/+532
| | | | | | | | | Details: - In case the table entirely fits into a single group size (`capacity <= Group::kWidth`), the order of elements is not important. - For growing upto Group::kWidth we rotate control bytes and slots deterministically (using memcpy). - We also avoid second find_first_non_full right after resize for small growing. PiperOrigin-RevId: 588825966 Change-Id: I09bd7fd489e3868dcf56c36b436805d08dae7ab5
* `btree_map`: avoid a copy in `map_params::key`.Abseil Team2023-11-281-1/+3
| | | | | PiperOrigin-RevId: 585892739 Change-Id: I30490dac5826bff2a33d9872f71154d360f9cc0d
* Make `FlatHashMapPolicy` return `std::true_type` for relocatable objects.Abseil Team2023-11-206-16/+84
| | | | | | | This reduces produced binary size and can trigger even more optimizations in the future. PiperOrigin-RevId: 584136517 Change-Id: I3854833799f88f28b755ec53132925f0c3d468ab
* Partial roll forward of reentrant validation with the validation itself ↵Evan Brown2023-11-132-22/+27
| | | | | | | disabled. This will make it easier to roll back and forwards in the future (if needed) without causing merge conflicts in unrelated code. PiperOrigin-RevId: 582059046 Change-Id: I66dc6527e7a0b351367b7a391c2d653fe793143f
* Roll back due to leak sanitizer reports.Aaron Jacobs2023-11-085-113/+22
| | | | | PiperOrigin-RevId: 580726428 Change-Id: I12b0f22c2084aef90bcca67536220a6bb550b57e
* Add control()/slot() functions to iterator/const_iterator.Evan Brown2023-11-071-15/+19
| | | | | | | | | This allows for avoiding e.g. it.inner_.slot_ on const iterators. Also, refactor HashtableDebugAccess::AllocatedByteSize to use regular iteration instead of looking directly at control/slot_array of the table in order to support small object optimization. PiperOrigin-RevId: 580194253 Change-Id: I64cd69287834ee5c7a8daf867c532258806bfb7b
* Update comments to make it explicit that moving a flat_hash_{set,map} can ↵Evan Brown2023-11-022-2/+2
| | | | | | | cause pointers to elements to be invalidated. PiperOrigin-RevId: 578920671 Change-Id: Ica40db48d5565b606e5e5f501c1305612b193d4d
* Add sanitizer mode validation for use of references to swisstables elements ↵Evan Brown2023-11-014-39/+74
| | | | | | | that may have been invalidated by a container move. PiperOrigin-RevId: 578649798 Change-Id: Icfee98d3a0399b545ec6ec59c5b52ae5e006218b
* Roll forward: Add sanitizer mode checks that element ↵Evan Brown2023-10-305-22/+113
| | | | | | | constructors/destructors don't make reentrant calls to raw_hash_set member functions. PiperOrigin-RevId: 577877803 Change-Id: I254c589b00cadec6ff95dfd60a8a38ab303c1af5
* Rollback: Add sanitizer mode checks that element constructors/destructors ↵Evan Brown2023-10-175-113/+22
| | | | | | | don't make reentrant calls to raw_hash_set member functions. PiperOrigin-RevId: 574232718 Change-Id: I8ef25fec00b76ee5fb9424e7614ca55edd6ba81b
* Add sanitizer mode checks that element constructors/destructors don't make ↵Evan Brown2023-10-165-22/+113
| | | | | | | reentrant calls to raw_hash_set member functions. PiperOrigin-RevId: 573897598 Change-Id: If40c23ac3cd9fff315ee18774e27c480cbca3a81
* Add iterator invalidation checking for when the hashtable is moved.Evan Brown2023-10-163-15/+45
| | | | | | Motivation: once we enable small object optimization in swisstable, iterators can be invalidated when the table is moved. PiperOrigin-RevId: 573884505 Change-Id: I4278129829143d3747dfd0ef0ff92f321c2633dc
generated by cgit v1.2.3 (git 2.39.1) at 2025-04-14 08:55:28 +0000