summaryrefslogtreecommitdiff
path: root/absl/container/internal/btree.h
Commit message (Collapse)AuthorAge
* Export of internal Abseil changesGravatar Abseil Team2021-05-18
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | -- 30af50146f07d7afdb196abf235f44ec44ea6409 by Derek Mauro <dmauro@google.com>: Update Abseil dependency versions PiperOrigin-RevId: 374415690 -- 6a241e9ea8ee201789bb66aadf9e1ca9cc23c5dc by Derek Mauro <dmauro@google.com>: Fix the install test project, which is doing a mixed-mode build. This manifests in failure with GCC 11, which defaults to C++17 Also explicitly reference python3 in the test script. python2 is being removed by some Linux distros. PiperOrigin-RevId: 374278107 -- 42f85122407e799183880e0b2e2a71f6d35ee003 by Evan Brown <ezb@google.com>: Use `capacity + Group::kWidth` control bytes instead of `capacity + Group::kWidth + 1`. We don't use the extra byte - we only need the first `capacity` ones that are valid, the one sentinel byte and then `Group::kWidth - 1` cloned control bytes. For example, in `EmptyGroup()`, where capacity is 0, we use `Group::kWidth` control bytes. We need to update set_ctrl() to only mirror `Group::kWidth - 1` bytes instead of `Group::kWidth` bytes. Note: this doesn't actually save memory unless `alignof(value_type)` is one. Also add/update related comments. PiperOrigin-RevId: 374198589 -- 5dcd09b2221bf23add583541769b476dac54e112 by Evan Brown <ezb@google.com>: Improve b-tree value_comp() support. - Don't expose internal adapted comparator functionality. - Support value_comp() for maps using function pointer comparators. - For maps, make value_compare's constructor and the member comparator be protected - [reference](https://en.cppreference.com/w/cpp/container/map/value_compare). PiperOrigin-RevId: 373832649 -- d75819786ff5a06e1ed0c5c1e80b3b95ac49c83b by Evan Brown <ezb@google.com>: Don't export adapted comparator functionality in key_comp(). PiperOrigin-RevId: 373651039 GitOrigin-RevId: 30af50146f07d7afdb196abf235f44ec44ea6409 Change-Id: I260480b0923cefeba81c543e2b7c34cacaa7d7c7
* Export of internal Abseil changesGravatar Abseil Team2021-04-05
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | -- 51798d2ac9c95ee8955955c5d8d78b4c9592ecf7 by Derek Mauro <dmauro@google.com>: Correctly install pkgconfig files under CMAKE_INSTALL_LIBDIR Fixes #931 PiperOrigin-RevId: 366816645 -- fbaad678b54dae70e4cd9f4442b4fef9efb71b30 by Abseil Team <absl-team@google.com>: Add a kDefaultStatusToStringMode representing the default StatusToStringMode. PiperOrigin-RevId: 366478305 -- 25b4be6a591e8b25338a00be1273cd6cae6b0165 by Evan Brown <ezb@google.com>: Fix a typo in a comment. PiperOrigin-RevId: 366464483 -- 6add48ed8f633c219f02c6ef8af876f8dbaa9955 by Abseil Team <absl-team@google.com>: Update comment to mention absl::container_literal::Layout which is what is used instead of gtl::Layout. PiperOrigin-RevId: 366452345 GitOrigin-RevId: 51798d2ac9c95ee8955955c5d8d78b4c9592ecf7 Change-Id: I8e68bc55d81445b2f6f707943fed9075cd402844
* Export of internal Abseil changesGravatar Abseil Team2021-03-18
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | -- 8e75347c10d85112296811be6ef35761744ad9bc by Derek Mauro <dmauro@google.com>: Big update to LTS release process * Add create_lts.py script to to the LTS modification This is simpler than copybara since very few changes are needed * Use the default installation paths instead of a versioned path. If a versioned path is needed, this is easy to change on the commandline. * Make the integration test use the LTS transformed version * Test both static and dynamic linking (fixes pkg-config dynamic linking) PiperOrigin-RevId: 363566934 -- e00e971a2de3138861f5e1900201c9cc7788f714 by Laramie Leavitt <lar@google.com>: Add a non-compile test to absl::BitGenRef for temporaries. PiperOrigin-RevId: 363437284 -- 3685644ec115d99789de32aceb76c32a00756fea by Derek Mauro <dmauro@google.com>: Make OSS code consistent with internal code by using the forward declaration of absl::Status that contains ABSL_MUST_USE_RESULT. PiperOrigin-RevId: 363426906 -- b85fec142c3aa3f632fa985f9f8f73a253819723 by Evan Brown <ezb@google.com>: Move raw_hash_set::infoz_ into raw_hash_set::settings_. This reduces the size of raw_hash_sets by alignof(size_t) bytes when hashtablez is disabled. PiperOrigin-RevId: 363034264 -- c6fde3b17e5845191eb8b2bfc1760c8bfb9573ff by Mark Barolak <mbar@google.com>: Internal change PiperOrigin-RevId: 362990378 -- 81713cf964905b43d1cbe32ce5fed97539029625 by Abseil Team <absl-team@google.com>: Fix typo in comment (execeptions -> exceptions). PiperOrigin-RevId: 362946191 -- 3ee92ca470feca44da417b03ee45a915c6eb5155 by Abseil Team <absl-team@google.com>: Add absl::FindAndReportLeaks and routes it to the corresponding __lsan_do_recoverable_leak_check. PiperOrigin-RevId: 362622199 -- b95b7194b20e02c20d72289fbc79a0d35b82e256 by Abseil Team <absl-team@google.com>: Add `kWithEverything` to StatusToStringMode PiperOrigin-RevId: 362595218 -- 0a960d96a0014eab7e1c55b479269450ed8e98d7 by Abseil Team <absl-team@google.com>: Accept e.g. ".__uniq" as a valid clone name. Further, bring the implementation on par with libiberty's demangler grammar. Clang introduced option -funique-internal-linkage-names that adds the suffix ".__uniq.[0-9]+" to internal linkage functions to give them a globally unique identifier. The suffix was designed to work with existing demanglers which do recognize a "_" along with the alphanumeric string. This change enhances the demangler to allow "_" with the alphanumeric string. Please refer to libiberty's cp-demangle.c where function d_clone_suffix implements the demangling of clone suffixes : 1. '_' is accepted as a valid character with the alphanumeric sequence. 2. The alphanumberic sequence is optional. 3. The digit sequence is optional. PiperOrigin-RevId: 362557420 -- 2ac5ea212c150afd2f58025a5cab8c45d16949c6 by Abseil Team <absl-team@google.com>: Change variable name 'slots' to 'slot_count' to avoid name-clash with Qt builds. PiperOrigin-RevId: 362556289 -- 934f0f409c9c548716a46363d6e243406fad4028 by Mark Barolak <mbar@google.com>: Clarify the comment on ABSL_CACHELINE_SIZE to indicate that the macro definition itself shouldn't change, but rather that call sites should change when possible. This addresses the request for improved documentation in https://github.com/abseil/abseil-cpp/pull/842. PiperOrigin-RevId: 362354288 GitOrigin-RevId: 8e75347c10d85112296811be6ef35761744ad9bc Change-Id: I33ec8561d8d645c3353e9d2dd447501d0e1825a7
* Export of internal Abseil changesGravatar Abseil Team2021-03-10
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | -- 5ed5dc9e17c66c298ee31cefc941a46348d8ad34 by Abseil Team <absl-team@google.com>: Fix typo. PiperOrigin-RevId: 362040582 -- ac704b53a49becc42f77e4529d3952f8e7d18ce4 by Abseil Team <absl-team@google.com>: Fix a typo in a comment. PiperOrigin-RevId: 361576641 -- d20ccb27b7e9b53481e9192c1aae5202c06bfcb1 by Derek Mauro <dmauro@google.com>: Remove the inline keyword from functions that aren't defined in the header. This may fix #910. PiperOrigin-RevId: 361551300 -- aed9ae1dffa7b228dcb6ffbeb2fe06a13970c72b by Laramie Leavitt <lar@google.com>: Propagate nice/strict/naggy state on absl::MockingBitGen. Allowing NiceMocks reduces the log spam for un-mocked calls, and it enables nicer setup with ON_CALL, so it is desirable to support it in absl::MockingBitGen. Internally, gmock tracks object "strictness" levels using an internal API; in order to achieve the same results we detect when the MockingBitGen is wrapped in a Nice/Naggy/Strict and wrap the internal implementation MockFunction in the same type. This is achieved by providing overloads to the Call() function, and passing the mock object type down into it's own RegisterMock call, where a compile-time check verifies the state and creates the appropriate mock function. PiperOrigin-RevId: 361233484 -- 96186023fabd13d01d32d60d9c7ac4ead1aeb989 by Abseil Team <absl-team@google.com>: Ensure that trivial types are passed by value rather than reference PiperOrigin-RevId: 361217450 -- e1135944835d27f77e8119b8166d8fb6aa25f906 by Evan Brown <ezb@google.com>: Internal change. PiperOrigin-RevId: 361215882 -- 583fe6c94c1c2ef757ef6e78292a15fbe4030e35 by Evan Brown <ezb@google.com>: Increase the minimum number of slots per node from 3 to 4. We also rename kNodeValues (and related names) to kNodeSlots to make it clear that they are about the number of slots per node rather than the number of values per node - kMinNodeValues keeps the same name because it's actually about the number of values rather than the number of slots. Motivation: I think the expected number of values per node, assuming random insertion order, is the average of the maximum and minimum numbers of values per node (kNodeSlots and kMinNodeValues). For large and/or even kNodeSlots, this is ~75% of kNodeSlots, but for kNodeSlots=3, this is ~67% of kNodeSlots. kMinNodeValues (which corresponds to worst-case occupancy) is ~33% of kNodeSlots, when kNodeSlots=3, compared to 50% for even kNodeSlots. This results in higher memory overhead per value, and since this case (kNodeSlots=3) is used when values are large, it seems worth fixing. PiperOrigin-RevId: 361171495 GitOrigin-RevId: 5ed5dc9e17c66c298ee31cefc941a46348d8ad34 Change-Id: I8e33b5df1f987a77112093821085c410185ab51a
* Export of internal Abseil changesGravatar Abseil Team2020-12-24
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | -- 7c15492a46380679651a4291bb284980901d04b1 by Andy Getzendanner <durandal@google.com>: Add some internal hooks for ABSL_RAW_LOG and do a bit of tidying up. PiperOrigin-RevId: 348836291 -- 9a438cdcf2bd8d2b7ab27f4955432abf0d087672 by Evan Brown <ezb@google.com>: Fix a bug affecting b-tree extract() when there are multiple keys in the container that are equivalent to the lookup key. In that case, we are supposed to extract the first such key in the container - [reference](https://en.cppreference.com/w/cpp/container/multiset/extract), but we were extracting the first one we found (which was not necessarily the first in the container). Also, optimize internal_lower_bound to not keep searching all the way to the leaf if it finds an equivalent key on an internal node and we can't have multiple equivalent keys for the lookup key. PiperOrigin-RevId: 348822858 -- b5e34c3af3f52815dbca3c6858c26fa8f385a408 by Abseil Team <absl-team@google.com>: Fix misleading comment. Ignored object can be either deallocated or leaked. PiperOrigin-RevId: 348705960 -- 64fd9e8c0684bfe86f50161b0e0e9077bb96e05c by Christian Blichmann <cblichmann@google.com>: Minor cleanups: - Sorting using declarations - Changing the format of a NOLINT statement PiperOrigin-RevId: 348641845 GitOrigin-RevId: 7c15492a46380679651a4291bb284980901d04b1 Change-Id: Ia1ccd844586bd3dced2466651f1175d40caf3d7a
* Export of internal Abseil changesGravatar Abseil Team2020-12-10
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | -- 6e9f93888bbe6718997ed90bbd049f1f3572b066 by Abseil Team <absl-team@google.com>: Fix status to be safe for self move assignment. PiperOrigin-RevId: 346815392 -- 35cae74a977f258e81dfbe925fb5a34cb6632036 by Gennadiy Rozental <rogeeff@google.com>: Eliminate unnecessary access to the global vars. PiperOrigin-RevId: 346777168 -- e7e786c243069060f5d6c1c945decb4b0b83f95b by Andy Getzendanner <durandal@google.com>: Internal change. PiperOrigin-RevId: 346685656 -- 4ccd41c48f1a83cfa20b3ea534f743dd7d788376 by Abseil Team <absl-team@google.com>: Move CordRep Ref() and Unref() logic into cord_internal.h This change moves Ref() and Unref() logic out of cord.cc into cord_internal. The main purpose is to make upcoming ring buffer changes easier to isolate from existing cord.cc code. Notice that this removes the nullptr check from Unref() and now requires it to be non null (which held true most times). We may need to rethink if the 'unref unlikely one' is the common case: are cordreps most likely shared? This may be something between 'root' and non root nodes, i.e., is it more likely for leaf / flat nodes in large cords to be shared than top level cordreps being shared? Vice versa? Benchmarks say that we mostly shouldn't care, the caveat being that atomic ops seem more expensive on upcoming archs (arcadia) so we should error on the side of an extra IsOne() branch saving us single owned atomic ops. PiperOrigin-RevId: 346676121 -- f0babab103b9e60d61ba09482d468985e43eceb3 by Samuel Benzaquen <sbenza@google.com>: Fix iterator based constructor and `.insert` members to only require EmplaceConstructible as the standard specifies. PiperOrigin-RevId: 346616707 -- 8f48eedda02277f9c96a88ed7726e34b557cce20 by Evan Brown <ezb@google.com>: Fix a bug in binary_search_impl when there's a transparent, three-way comparator that has different equivalence classes for different lookup types. Add a new can_have_multiple_equivalent_keys method to share the common logic for these cases. PiperOrigin-RevId: 346605948 -- 649183cb3cc9383431de9c81fb1c0f885d4001ae by Abseil Team <absl-team@google.com>: Add benchmark for accessing a Duration flag. PiperOrigin-RevId: 346594843 -- fefdb046520871af63ce2229e2f7cccfc0483dea by Abseil Team <absl-team@google.com>: Restructure CordReader for upcoming ring buffer changes. PiperOrigin-RevId: 346410642 -- 8b2f50e7da0ebab06ead5f94e366e984ca23cb6a by Abseil Team <absl-team@google.com>: Wire in an internal-only flag to toggle upcoming ring buffer changes on/off for experimentation. PiperOrigin-RevId: 346199111 GitOrigin-RevId: 6e9f93888bbe6718997ed90bbd049f1f3572b066 Change-Id: I8f34866b25a79209cb5448bbb28dd3044111d2e9
* Export of internal Abseil changesGravatar Abseil Team2020-12-03
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | -- 8ebcdcac49f299156a8fd4a77501a258050960e8 by Evan Brown <ezb@google.com>: In btree_iterator, refactor a bit and update a couple of comments. PiperOrigin-RevId: 345491436 -- 421d3b9b5cf484811b9514436ce83f797e109145 by CJ Johnson <johnsoncj@google.com>: Updates the implementation of InlinedVector to accurately express the value-initialization semantics of the default constructor PiperOrigin-RevId: 345479151 -- 88f36a132b2038cb276ed1ad4d9764adb1fc78e6 by CJ Johnson <johnsoncj@google.com>: Updates the implementation of InlinedVector to accurately express the value-initialization semantics of the default constructor PiperOrigin-RevId: 345433064 -- e55c9b4e7c578c1c4f2df65b1991041c283a97d9 by Chris Kennelly <ckennelly@google.com>: Internal change PiperOrigin-RevId: 345388181 -- e2284c4e77ff1ebc3009e5bf520524c552226d8a by Chris Kennelly <ckennelly@google.com>: Internal change PiperOrigin-RevId: 345357514 -- 1c496a2ae07ce98578614155d63ef2ea4de5e518 by Chris Kennelly <ckennelly@google.com>: Mark string lookup functions noexcept. PiperOrigin-RevId: 345275012 GitOrigin-RevId: 8ebcdcac49f299156a8fd4a77501a258050960e8 Change-Id: I0ccb57d210b543270769e1378de38bf0922f8745
* Export of internal Abseil changesGravatar Abseil Team2020-10-27
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | -- e5b45b15c19e85aaa33430ac2bd45fcc2e52dad5 by Greg Falcon <gfalcon@google.com>: Add extra tests exercising ShiftLeft() at boundary conditions, to guard against logic errors in our memory bounds checking. PiperOrigin-RevId: 339326030 -- cdfde78815ca016a57f90f53d08c3335bd355f30 by Evan Brown <ezb@google.com>: Fix a bug in b-tree erase() and count() in which we weren't accounting for cases where the comparator is heterogeneous and has different equivalence classes for different lookup types. Optimize equal_range to avoid comparisons when possible. PiperOrigin-RevId: 339270230 -- b4aa337c156fa91f74f25c676c679ae146311968 by Derek Mauro <dmauro@google.com>: Fix execution of the cmake build scripts when not on Kokoro PiperOrigin-RevId: 339131253 -- fa3d1f602f711be72fde6b5f29d6341b9b5f8a2c by Derek Mauro <dmauro@google.com>: Update Docker container used for Alpine Linux testing PiperOrigin-RevId: 339074246 GitOrigin-RevId: e5b45b15c19e85aaa33430ac2bd45fcc2e52dad5 Change-Id: I2cc3adc4de3493203c8a944aedee40efa54af0c0
* Export of internal Abseil changesGravatar Abseil Team2020-10-26
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | -- 730bb88bee556aa11fa19aa33e1434cb6fa78985 by Evan Brown <ezb@google.com>: Support missing allocator-related constructors in b-tree. See [reference](https://en.cppreference.com/w/cpp/container/set/set). Also use allocator_traits::select_on_container_copy_construction() to get allocator for copy construction. PiperOrigin-RevId: 339058322 -- b6cc121689ae3e452d1db2d66122cb198d25142b by Derek Mauro <dmauro@google.com>: Fix more sign-compare warnings PiperOrigin-RevId: 339057920 -- 0e2c62da1dcaf6529abab952bdcc96c6de2d9506 by Abseil Team <absl-team@google.com>: Add missing <limits> include PiperOrigin-RevId: 339054753 -- d5a9ec2d1e40fe6359e720942e4955009ee415ec by Derek Mauro <dmauro@google.com>: Stop disabling sign-compare warnings for non-test targets. Our users complain about these. This does not catch issues in header-only libraries (like btree.h) but we may work on those in the future PiperOrigin-RevId: 338967089 -- 0c062c542a4c61ea0f65d25811827c0858e3adde by Abseil Team <absl-team@google.com>: Improve cache-locality for ThreadIdentity and PerThreadSynch. This is a change based on an observation in RPC benchmarks that shows significant cycles being spent in waking up a thread, 99.8% of which was on cache misses. Investigating this a bit more, it turns out to be due to sharing the cache line with the waiter state. To fix this issue, the following changes are introduced: - Reorder fields in PerThreadSync so that it fits in a single cache line The size of this structure was 80 bytes before this change. Note: Manually inspected all booleans to make sure they are not modified by multiple threads concurrently. PiperOrigin-RevId: 338852058 -- a90d6f2b2346385017e32dd8ae1b5ca691a5863f by Derek Mauro <dmauro@google.com>: Delete GCC 4.9 test script. It is no longer supported PiperOrigin-RevId: 338779452 -- 7274008d4757e88869110be9db39d03d911ae2b5 by Abseil Team <absl-team@google.com>: Fix the usage example in which SetFlag should take a pointer. PiperOrigin-RevId: 338744529 GitOrigin-RevId: 730bb88bee556aa11fa19aa33e1434cb6fa78985 Change-Id: Iff99594c4022e60e482a392d334b376c7ae8883e
* Export of internal Abseil changesGravatar Abseil Team2020-10-23
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | -- 017c3924d21132085bc20c9be0ae469bfbf2c56c by Gennadiy Rozental <rogeeff@google.com>: Import of CCTZ from GitHub. PiperOrigin-RevId: 338723934 -- 8b08c23d7b05232e283b1388cee3eb5bebc2d9c4 by Derek Mauro <dmauro@google.com>: Add script to test GCC floor (the minimum version of GCC we support, currently the GCC 5 series) PiperOrigin-RevId: 338708581 -- afa440ac7c843126b4f99b89ebc071dda1d85a4d by Abseil Team <absl-team@google.com>: Fix typo in documentation of StatusOr::value_or() ('of' -> 'if'). PiperOrigin-RevId: 338690089 -- 97d5008865327fc36b942b96de0d0cacfb909df5 by Derek Mauro <dmauro@google.com>: Import of CCTZ from GitHub. PiperOrigin-RevId: 338568224 -- da5e09a7fedb3217329465d9206b7cbc6677176b by Abseil Team <absl-team@google.com>: Add `absl_btree_prefer_linear_node_search` Allow keys of `btree_set`, `btree_map`, `btree_multiset`, and `btree_multimap` to opt-in to linear search (instead of binary search). Linear search was used previously for arithmetic types with `key_compare` of `std::greater` or `std::less`. For example, this would be useful for key types that wrap an integer and define their own cheap `operator<()`. ``` class K { public: using absl_btree_prefer_linear_node_search = std::true_type; ... private: friend bool operator<(K a, K b) { return a.k_ < b.k_; } int k_; }; absl::btree_map<K, V> m; // Uses linear search assert((absl::btree_map<K, V>::testonly_uses_linear_node_search())); ``` PiperOrigin-RevId: 338476553 -- c56ead7ce6b0a5ad32e3a42904c686448a69451e by Gennadiy Rozental <rogeeff@google.com>: Import of CCTZ from GitHub. PiperOrigin-RevId: 338419417 GitOrigin-RevId: 017c3924d21132085bc20c9be0ae469bfbf2c56c Change-Id: I1199f3ae917280a3ef20ccc6038abbe34d96ec0b
* Export of internal Abseil changesGravatar Abseil Team2020-10-22
| | | | | | | | | | | | | | | | | | | | | | | | | | -- d09230db053c544c2dc7fd7d95d1ebe4302071e9 by Abseil Team <absl-team@google.com>: Move testonly_uses_linear_node_search to BtreeNodePeer PiperOrigin-RevId: 338210523 -- 7b11c945dbba7a354103c194877eba240f7f0cbc by Derek Mauro <dmauro@google.com>: Allow pinning to a GoogleTest commit to make the build reproducible Allow using a cached copy of the commit to avoid depending on GitHub PiperOrigin-RevId: 338115715 -- 8414f496c570a6398744da8324e158b39a2e3d92 by Andy Getzendanner <durandal@google.com>: Generate a pkg-config file per absl_cc_library. PiperOrigin-RevId: 337986219 GitOrigin-RevId: d09230db053c544c2dc7fd7d95d1ebe4302071e9 Change-Id: Iae398ab8ad5c0c6833abd01aa5198315f5b6fa99
* btree: fix sign-compare warnings (#800)Gravatar Dominic Chen2020-09-30
|
* Export of internal Abseil changesGravatar Abseil Team2020-09-29
| | | | | | | | | | | | | | | | | | | | | | | | | | | | -- dad7313f7e8c36c35fc213ce5110100595f90990 by Andy Getzendanner <durandal@google.com>: Fix log_severity.h header guard to match path. PiperOrigin-RevId: 334439123 -- 8a58aa0f4171219d38fb49a2e008e249f86de4cb by Abseil Team <absl-team@google.com>: Minor comment cleanup PiperOrigin-RevId: 334409054 -- a1bc324e53c358b874f99b3f5624658fff99453e by Evan Brown <ezb@google.com>: Cleanup in btree.h: - Combine internal_locate_impls and update comments. - Avoid use of auto with SearchResult. - Change one iterator reference to be stored by value (copy is cheap). PiperOrigin-RevId: 334396951 GitOrigin-RevId: dad7313f7e8c36c35fc213ce5110100595f90990 Change-Id: I79862795abd3169587f5bafe0e5369bdde90c1e1
* Export of internal Abseil changesGravatar Abseil Team2020-09-10
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | -- cfb567ed02096320663d882d2c0c2fb7db7af1e4 by Derek Mauro <dmauro@google.com>: Upgrade to GCC 10.2.0, Bazel 3.5.0, and CMake 3.18.2 PiperOrigin-RevId: 330847323 -- 5dcb9ce14d92315163079366a91c43cbd5184ea4 by Evan Brown <ezb@google.com>: Optimize equal_range() by avoiding the call to upper_bound() when possible. We need to support heterogeneous comparators that have different behavior when comparing key_type to non-key_type. See the new test. Also update the comment for `key_compare_to_adapter`. PiperOrigin-RevId: 330794444 -- 744405dbda5513527d74094a5c3b9db1e0927693 by Gennadiy Rozental <rogeeff@google.com>: Introduce trampoline for friend access to avoid friending routines and classes from different namespace. PiperOrigin-RevId: 330773156 -- a195d1226576f8a7bb5671f3e42d1021b827fad9 by Abseil Team <absl-team@google.com>: Fix an incorrect version number test for std::variant availability in tvOs. PiperOrigin-RevId: 330759480 -- 58b02eb9159a577953676d9928cb26b30068b847 by Derek Mauro <dmauro@google.com>: Use c++20 instead of c++2a now that it is supported by GCC PiperOrigin-RevId: 330559797 GitOrigin-RevId: cfb567ed02096320663d882d2c0c2fb7db7af1e4 Change-Id: I0e0d68409c95da42f5609920155ba5694ade8df0
* Export of internal Abseil changesGravatar Abseil Team2020-08-27
| | | | | | | | | | | | | -- ec39082e792ef7bb17e8432b6e10d1cb96dbad24 by Derek Mauro <dmauro@google.com>: Fix a sign-compare warning in btree.h Fixes #771 PiperOrigin-RevId: 328653403 GitOrigin-RevId: ec39082e792ef7bb17e8432b6e10d1cb96dbad24 Change-Id: I6b681dcda4fd8933257b06d0428d40b1d01f6ad1
* Export of internal Abseil changesGravatar Abseil Team2020-08-14
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | -- 0c8282d75798c77733eee6167870bcc6acc0bfc1 by Evan Brown <ezb@google.com>: Provide mutable access to the key in node handles using std::launder when compiled with C++17 or later. Also, document why we can't provide mutable access to the key without C++17. Note: we use Policy::mutable_key() because btree already uses Policy::key() internally to get const key access, and we want to avoid calling std::launder unless we need mutable access to the key. PiperOrigin-RevId: 326519000 -- 8018d0c3044400f0a731b0d2d00b606742c98818 by Xiaoyi Zhang <zhangxy@google.com>: Move `Status` internal symbols from the public header into an internal header file. PiperOrigin-RevId: 326471847 -- 87a7644864ba7c003b0611898aaba1b71c840376 by Abseil Team <absl-team@google.com>: Avoid a costly divide (the division accounts for 10% of the time spent in the function). When the division is signed, the compiler has to generate a div. When it is unsigned, it can generate a shift: https://godbolt.org/z/vGfTv4. As per the test above the div, we know that the value is unsigned. PiperOrigin-RevId: 326453275 GitOrigin-RevId: 0c8282d75798c77733eee6167870bcc6acc0bfc1 Change-Id: I0a953558358055ab3dc6a533d8930698509b1195
* Export of internal Abseil changesGravatar Abseil Team2020-08-05
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | -- c12db0cff0f0cb0c10731cdf4bf1663e99ecb82e by Samuel Benzaquen <sbenza@google.com>: Fix incompatibility of retired flags and AddressSanitizer. PiperOrigin-RevId: 325028944 -- 20119dce82503c6ac22f3ec479d0eaea6acc7ba0 by Abseil Team <absl-team@google.com>: Internal change PiperOrigin-RevId: 324939694 -- bb1ab1a4e1a551469ad110bdfce3210aeb9bf4b8 by Abseil Team <absl-team@google.com>: Teach Abseil stack consumption utilities about AArch64. PiperOrigin-RevId: 324935395 -- 987043ffc960f38457478b01c04b47dfaf7ae006 by Evan Brown <ezb@google.com>: Cleanup: simplify the slot transfer methods a bit. PiperOrigin-RevId: 324834817 -- ed7081130d3ab93a2c3c916e30fe4367d8e96954 by Abseil Team <absl-team@google.com>: Pass __FILE__ as const char* instead of as array of chars to internal_log_function to allow deterministic symbols for AtomicHook wrapper of the InternalLogFunction PiperOrigin-RevId: 324800499 GitOrigin-RevId: c12db0cff0f0cb0c10731cdf4bf1663e99ecb82e Change-Id: Ibb92b1cab465e45abc86281f0fba894c82a662df
* Export of internal Abseil changesGravatar Abseil Team2020-07-24
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | -- 873b52b0a691e759413c5db27dafc541a5da5263 by Andy Getzendanner <durandal@google.com>: Introduce an internal-only thread-local caching wrapper around GetTID. PiperOrigin-RevId: 323055682 -- 091a4537f1ef6e158acbf4261cfae1af7a3bdb7f by Abseil Team <absl-team@google.com>: Internal change PiperOrigin-RevId: 322864497 -- c80ccfff2a825819f31826a30f48cca3297699f8 by Evan Brown <ezb@google.com>: Roll forward b-tree changes simplifying deletion and getting rid of recursion in clear_and_delete(). We also change clear_and_delete() to avoid some unnecessary comparisons by restructuring the loops. PiperOrigin-RevId: 322658938 -- 81464c0fb9c8c6268dca2e530aba99e75e1e59ae by Gennadiy Rozental <rogeeff@google.com>: Eliminate definition of RunningOnValgrind inside the library. Fixes #674 Fixes #657 PiperOrigin-RevId: 322508440 GitOrigin-RevId: 873b52b0a691e759413c5db27dafc541a5da5263 Change-Id: I20b40c9e8fc62edcf981caab467cca33cf6fd2ba
* Export of internal Abseil changesGravatar Abseil Team2020-07-21
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | -- dcd4d95f6201dc5781a3a374be8eb10c812fd98a by Derek Mauro <dmauro@google.com>: Add -Wundef to GCC warnings PiperOrigin-RevId: 322388155 -- b030746368262aff6bc487f5525bcd9b32d18ebb by Abseil Team <absl-team@google.com>: Google internal clean-up. PiperOrigin-RevId: 322381901 -- 18e4cfcd50730c493cfc0cf1e127e57c186ce90b by Evan Brown <ezb@google.com>: Rollback b-tree erase simplification change. PiperOrigin-RevId: 322368252 -- d15431c52fa7ccb25ffbd967fd11f8f58246d48a by Abseil Team <absl-team@google.com>: Update MOCK_METHOD (new format) in memory/memory_test.cc PiperOrigin-RevId: 322208282 GitOrigin-RevId: dcd4d95f6201dc5781a3a374be8eb10c812fd98a Change-Id: I3a900b4993f86bdd1c9597819c7a0e6e1759eda3
* Export of internal Abseil changesGravatar Abseil Team2020-07-20
| | | | | | | | | | | | | | | | | | | | | | | | | | | | -- 763b4755cc65db94fb1d6c09655f77deee685698 by Evan Brown <ezb@google.com>: Rollback change getting rid of recursion in clear_and_delete(). PiperOrigin-RevId: 322156175 -- e430ae6970ae2e76357876449878033e3c72e734 by Greg Falcon <gfalcon@google.com>: fix build on P9 Import of https://github.com/abseil/abseil-cpp/pull/739 PiperOrigin-RevId: 321855200 -- 3076c5bf811a950e7f7914023434d4aa9c0fbbb0 by Derek Mauro <dmauro@google.com>: Check for the existence of CMake policies before using them Fixes #742 PiperOrigin-RevId: 321798698 GitOrigin-RevId: 763b4755cc65db94fb1d6c09655f77deee685698 Change-Id: I641e42f8bebe236b75f1bf1116a129c2ad9b2571
* Export of internal Abseil changesGravatar Abseil Team2020-07-17
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | -- d2b7a83bafb90d35b2b7d8eb4177e9d712e8d62c by Gennadiy Rozental <rogeeff@google.com>: Introduce ABSL specific macros for detecting the usage of sanitizers. PiperOrigin-RevId: 321687443 -- a41342cc04b1088087dda12d7272aa3835f8e36a by Evan Brown <ezb@google.com>: Get rid of recursion in clear_and_delete(). PiperOrigin-RevId: 321583786 -- 99c6d300b17f186c28867b08cc79f1e55077e88a by Evan Brown <ezb@google.com>: Code simplification: consolidate methods to erase values/nodes. Motivation: this will make floating storage work simpler. - Delete erase_same_node/erase_from_leaf_node/remove_value/remove_values_ignore_children. - Move node deletion methods inside btree_node. - Delete three-argument move() and use transfer_n() instead. - Note: there's still one usage of move (in btree::erase(iterator)) that could use transfer, but I think doing so would add more complexity than it's worth. PiperOrigin-RevId: 321407673 -- c3efed6c1763190c6b3bccbede9b2989ab21b258 by Evan Brown <ezb@google.com>: Support heterogeneous insert_or_assign, try_emplace, operator[] for btree_map. Also do a bit of cleanup: - Add _impl methods for insert_or_assign/try_emplace. - Rename some hint iterator params from `position` to `hint`. PiperOrigin-RevId: 321399557 GitOrigin-RevId: d2b7a83bafb90d35b2b7d8eb4177e9d712e8d62c Change-Id: Ie2d0c7c3ed197c2b53d475248941392cbad20e59
* Export of internal Abseil changesGravatar Abseil Team2020-06-18
| | | | | | | | | | | | | | | | | | | | | | | -- 34c0d521b11ed4191ea3e071a864a84e5e5941b7 by Matthew Brown <matthewbr@google.com>: Release absl::StrFormat custom type extensions - Allows StrFormat methods to be extended to accept types which implement AbslFormatConvert() - NOLINTNEXTLINE(readability-redundant-declaration) used, declarations are required in some compilers. PiperOrigin-RevId: 316963065 -- 4d475b5ad02d41057447d722ad35573fc4f48d1f by Evan Brown <ezb@google.com>: Small fix to previous change: the first overload of insert_iterator_unique wasn't actually being selected. Fix that issue and add tests to verify that it actually works. Note: couldn't use TestInstanceTracker here because that counts instances (and decrements in destructor) rather than counting all constructor calls. PiperOrigin-RevId: 316927690 GitOrigin-RevId: 34c0d521b11ed4191ea3e071a864a84e5e5941b7 Change-Id: If8bbb8317b93af4084ac4cc55b752b99b1581b58
* Export of internal Abseil changesGravatar Abseil Team2020-06-17
| | | | | | | | | | | | | | | | | | | | | | | | | | | | -- 1f80d4f1cb8847545627a2d0b18f697c4a763292 by Samuel Benzaquen <sbenza@google.com>: Add a hint message to the assertions for easier debugging. Also, move it out of the template to avoid printing the whole template instantiation as part of the assertion. It is not relevant and can significantly bloat the error message and hide the important bits. PiperOrigin-RevId: 316736140 -- 223e97a90150de5b7206be2e45c62a9b70ac02df by Tom Manshreck <shreck@google.com>: Update Span description to remove "view" terminology, in light of recent clarification of the differences between a view and a span type. PiperOrigin-RevId: 316734382 -- 361b87d55b1809a5da3f72a996686f27b3d630c2 by Evan Brown <ezb@google.com>: Allow for explicit conversion of values in btree range constructor/insert. PiperOrigin-RevId: 316725951 GitOrigin-RevId: 1f80d4f1cb8847545627a2d0b18f697c4a763292 Change-Id: I74e2b095bc24710b27ed63ed94a50ef8f0fc897f
* Export of internal Abseil changesGravatar Abseil Team2020-06-03
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | -- 9e8b4a286d70df9487bff080816bd07ae38af5f8 by Evan Brown <ezb@google.com>: Add btree_node::transfer_n/transfer_n_backward and replace usage of uninitialized_move_n and value_destroy_n. PiperOrigin-RevId: 314600027 -- 6c452aa1ee7e46ab941ba7d1fa636da8ea3d7370 by Laramie Leavitt <lar@google.com>: Remove the MockingBitGenBase base class in favor of type-erasure in BitGenRef. In Abseil random, mocking was split across two different classes, MockingBitGenBase and MockingBitGen. This split existed because Google Mock is a test-only library that we don't link into production, so MockingBitGenBase provided a low-overhead scaffold used to lookup mocks when in test code, but which is unused in production code. That has been replaced by type-erasure which looks for a method named CallImpl with the correct signature. Weaken the coupling between MockingBitGen, DistributionCaller, and MockOverloadSet. Rename CallImpl to InvokeMock() Previously, the implementation of DistributionCaller was also split across different files using explicit instantiation of the DistributionCaller struct and some details in the Mocking classes. Now Distribution caller uses the presence of the InvokeMock() method to choose whether to use the mockable call path or the default call path. PiperOrigin-RevId: 314584095 -- 07853c47dc98698d67d65a3b9b662a65ab9def0a by Abseil Team <absl-team@google.com>: Add PC / backtrace / symbolization support for Apple platforms. Full backtrace support requires iOS 9+ PiperOrigin-RevId: 314415072 -- 43889f17a132b31f6558c6482721cbbc776128fd by Gennadiy Rozental <rogeeff@google.com>: Consolidate all reflection interface in the new module 'reflection' and expose interface to locate reflection handle by name. PiperOrigin-RevId: 314390358 GitOrigin-RevId: 9e8b4a286d70df9487bff080816bd07ae38af5f8 Change-Id: I8e0910437740cf9ea9da5000adddfcef127e1158
* Export of internal Abseil changesGravatar Abseil Team2020-04-16
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | -- 0e867881e4b9f388a13d6fa8ed715192460130ab by Abseil Team <absl-team@google.com>: Minor wording change to header comment for Mutex::AwaitWithDeadline(). No functional changes. PiperOrigin-RevId: 306729491 -- fc64361fb831003fa5e6fbb84a9a89338fd2838c by Derek Mauro <dmauro@google.com>: Uses C++20 compatible allocator traits in Abseil types This merges both instances of CountingAllocator in the Abseil codebase. Makes the presubmits test C++20 mode. Fixes #651 PiperOrigin-RevId: 306728102 -- d759e5681b9dd6b7339fc019ed58fb5fdececdc3 by Derek Mauro <dmauro@google.com>: Makes btree's iterator comparisons C++20 compatible See https://stackoverflow.com/questions/60386792/c20-comparison-warning-about-ambiguous-reversed-operator PiperOrigin-RevId: 306702048 -- e9da5f409bc5ddb1bad308f9d8c41213c67a1d1e by Derek Mauro <dmauro@google.com>: Switch a few uses of at() that should have been data() in the implementation of InlinedVector. Use ABSL_HARDENING_ASSERT in resize(). PiperOrigin-RevId: 306670992 GitOrigin-RevId: 0e867881e4b9f388a13d6fa8ed715192460130ab Change-Id: If431f3e5d77097e9901654773552dcc01dface87
* Export of internal Abseil changesGravatar Abseil Team2020-03-26
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | -- 990253454819ce26ff1dda9ab4bbc145b61d01e4 by Xiaoyi Zhang <zhangxy@google.com>: Import github PR https://github.com/abseil/abseil-cpp/pull/645 PiperOrigin-RevId: 303119797 -- 5ac845cb7929b7d1eaf59a309afd811db5001175 by Abseil Team <absl-team@google.com>: Fix internal exception spec compatibility error PiperOrigin-RevId: 303104081 -- 3290595dd866eecab3c7044e2e3ca0adb74f1bf5 by Gennadiy Rozental <rogeeff@google.com>: Use FlagValue<T> to represent the value of a flag. Place it directly after FlagImpl and use a computed offset refer to it. The offset is computed based on the assumption that the `value_` data member is placed directly after the impl_ data member in Flag<T>. This change will allow us to migrate to `T`-specific storage in the generic case. This change decreases the overhead for int flags by 32 bytes. PiperOrigin-RevId: 303038099 -- f2b37722cd7a6d3a60ef9713f0d2bbff56f3ddbf by Derek Mauro <dmauro@google.com>: Minor correctness fix for an ABSL_HAVE_BUILTIN conditional PiperOrigin-RevId: 302980666 -- 39c079a6141ae1c5728af8bf33a39c8aff9deb9f by Abseil Team <absl-team@google.com>: Use ABSL_HARDENING_ASSERT in b-tree and SwissTable iterators. PiperOrigin-RevId: 302970075 -- 9668a044e080c789df32bcaa1ffb5100831cd9fa by Benjamin Barenblat <bbaren@google.com>: Correct `add_subdirectory` line in CMake googletest support Commit bcefbdcdf6ad85046ccacee0aeffba5404d3e528 added support for building with CMake against a local googletest checkout, but I missed a line when constructing the diff. Change the `add_subdirectory` line to reference the correct directories. PiperOrigin-RevId: 302947488 -- 0a3c10fabf80a43ca69ab8b1570030e55f2be741 by Andy Soffer <asoffer@google.com>: Remove unused distribution format traits. PiperOrigin-RevId: 302896176 -- 0478f2f6270e5ed64c0e28ec09556ca90b2d46a9 by Samuel Benzaquen <sbenza@google.com>: Fix for CWG:2310. PiperOrigin-RevId: 302734089 -- 3cb978dda5cae5905affdc0914dcc2d27671ed11 by Samuel Benzaquen <sbenza@google.com>: Fix the Allocate/Deallocate functions to use the same underlying allocator type. PiperOrigin-RevId: 302721804 -- ae38d3984fb68b4e3ddc165fa8d5c24d5936be52 by Matthew Brown <matthewbr@google.com>: Internal Change PiperOrigin-RevId: 302717314 -- 7357cf7abd03cc60b6e82b5f28a8e34935c3b4dc by Andy Getzendanner <durandal@google.com>: Fix typo: s/ABSL_HARDENED_ASSERT/ABSL_HARDENING_ASSERT/ PiperOrigin-RevId: 302532164 GitOrigin-RevId: 990253454819ce26ff1dda9ab4bbc145b61d01e4 Change-Id: Ie595a221c16e1e7e1255ad42e029b646c5f3e11d
* Export of internal Abseil changesGravatar Abseil Team2020-03-16
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | -- 91ca367a7548270155721bdda74611aeea2a2153 by Abseil Team <absl-team@google.com>: Replace the only usage of btree_node::swap with simpler logic using transfers and delete btree_node::swap. Add a benchmark for constructing small containers. PiperOrigin-RevId: 301169874 -- ff9d73a7125b7f8ab5733cda877204dfbfac138e by Derek Mauro <dmauro@google.com>: Ensure ABSL_CXX_STANDARD is set. Fixes #640 PiperOrigin-RevId: 301160106 -- 14ca0beee8c109e532134e7e9da7b072da1bf911 by Abseil Team <absl-team@google.com>: Rollback the change to make Cord iterators a fixed size. That change increased the iterator size, which can cause a deep recursion call to hit the stack memory limit, in turn causing a signal 11 failure. PiperOrigin-RevId: 301084915 -- 619e3cd9e56408bdb8b3b5a1e08dda1e95242264 by Matthew Brown <matthewbr@google.com>: Internal Change PiperOrigin-RevId: 300832828 -- 64f8d62ab4c4c78077dbe85a9595a8eeb6d16608 by Gennadiy Rozental <rogeeff@google.com>: Fix for empty braces support. We will call proper aggregate construction in case when {} is used as default value. In other words instead of "new T", we'll call "new T{}". PiperOrigin-RevId: 300715686 -- db3f65594d6db8b104b01262f884dff465b696ef by Abseil Team <absl-team@google.com>: Emscripten supports thread-local storage nowadays. PiperOrigin-RevId: 300675185 GitOrigin-RevId: 91ca367a7548270155721bdda74611aeea2a2153 Change-Id: I3344f745f9c3fc78775532b1808442fabd98e34a
* Export of internal Abseil changesGravatar Abseil Team2020-03-10
| | | | | | | | | | | -- ea0cfebeb69b25bec343652bbe1a203f5476c51a by Mark Barolak <mbar@google.com>: Change "std::string" to "string" in places where a "std::" qualification was incorrectly inserted by automation. PiperOrigin-RevId: 300108520 GitOrigin-RevId: ea0cfebeb69b25bec343652bbe1a203f5476c51a Change-Id: Ie3621e63a6ebad67b9fe56a3ebe33e1d50dac602
* Export of internal Abseil changesGravatar Abseil Team2020-03-09
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | -- 2c5c118f0615ba90e48ee2f18eccc9f511740f6d by Samuel Benzaquen <sbenza@google.com>: Rename internal macros to follow the convention in absl. PiperOrigin-RevId: 299906738 -- 92d84a707c7ebc4ec19bdd92d5765d1b6d218c1e by Derek Mauro <dmauro@google.com>: Import GitHub #629: Skip the .exe suffix in the helpshort filter on Windows PiperOrigin-RevId: 299892396 -- 2a6910d4be6c67a8376628764121b528ff53504d by Abseil Team <absl-team@google.com>: Use unsigned int128 intrinsic when available. It generates better branchless code. PiperOrigin-RevId: 299848585 -- 110c16cf0a739e1df5028fb6fbd03ef5dde1d278 by Derek Mauro <dmauro@google.com>: Import GitHub #594: Avoid reading the registry for Windows UWP apps PiperOrigin-RevId: 299821671 -- d8397d367e88163e5e8a47f379c716352dc91d03 by Greg Falcon <gfalcon@google.com>: Add absl::Hash support for Cord. The hash function is heterogeneous with other string types: a Cord and a string with the same byte sequence will hash to the same value. SwissTable types know about Cord, and will allow heterogeneous lookup (e.g., you can pass a Cord to flat_hash_map<string, T>::find(), and vice versa.) Add a missing dependency to the cmake Cord target. PiperOrigin-RevId: 299443713 GitOrigin-RevId: 2c5c118f0615ba90e48ee2f18eccc9f511740f6d Change-Id: I7b087c7984b0cb52c4b337d49266c467b98ebdf9
* Export of internal Abseil changesGravatar Abseil Team2020-03-03
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | -- a3e58c1870a9626039f4d178d2d599319bd9f8a8 by Matt Kulukundis <kfm@google.com>: Allow MakeCordFromExternal to take a zero arg releaser. PiperOrigin-RevId: 298650274 -- 01897c4a9bb99f3dc329a794019498ad345ddebd by Samuel Benzaquen <sbenza@google.com>: Reduce library bloat for absl::Flag by moving the definition of base virtual functions to a .cc file. This removes the duplicate symbols in user translation units and has the side effect of moving the vtable definition too (re key function) PiperOrigin-RevId: 298617920 -- 190f0d3782c63aed01046886d7fbc1be5bca2de9 by Derek Mauro <dmauro@google.com>: Import GitHub #596: Unbreak stacktrace code for UWP apps PiperOrigin-RevId: 298600834 -- cd5cf6f8c87b35b85a9584e94da2a99057345b73 by Gennadiy Rozental <rogeeff@google.com>: Use union of heap allocated pointer, one word atomic and two word atomic to represent flags value. Any type T, which is trivially copy-able and with with sizeof(T) <= 8, will be stored in atomic int64_t. Any type T, which is trivially copy-able and with with 8 < sizeof(T) <= 16, will be stored in atomic AlignedTwoWords. We also introducing value storage type to distinguish these cases. PiperOrigin-RevId: 298497200 -- f8fe7bd53bfed601f002f521e34ab4bc083fc28b by Matthew Brown <matthewbr@google.com>: Ensure a deep copy and proper equality on absl::Status::ErasePayload PiperOrigin-RevId: 298482742 -- a5c9ccddf4b04f444e3f7e27dbc14faf1fcb5373 by Gennadiy Rozental <rogeeff@google.com>: Change ChunkIterator implementation to use fixed capacity collection of CordRep*. We can now assume that depth never exceeds 91. That makes comparison operator exception safe. I've tested that with this CL we do not observe an overhead of chunk_end. Compiler optimized this iterator completely. PiperOrigin-RevId: 298458472 -- 327ea5e8910bc388b03389c730763f9823abfce5 by Abseil Team <absl-team@google.com>: Minor cleanups in b-tree code: - Rename some variables: fix issues of different param names between definition/declaration, move away from `x` as a default meaningless variable name. - Make init_leaf/init_internal be non-static methods (they already take the node as the first parameter). - In internal_emplace/try_shrink, update root/rightmost the same way as in insert_unique/insert_multi. - Replace a TODO with a comment. PiperOrigin-RevId: 298432836 -- 8020ce9ec8558ee712d9733ae3d660ac1d3ffe1a by Abseil Team <absl-team@google.com>: Guard against unnecessary copy in case the buffer is empty. This is important in cases were the user is explicitly tuning their chunks to match PiecewiseChunkSize(). PiperOrigin-RevId: 298366044 -- 89324441d1c0c697c90ba7d8fc63639805fcaa9d by Abseil Team <absl-team@google.com>: Internal change PiperOrigin-RevId: 298219363 GitOrigin-RevId: a3e58c1870a9626039f4d178d2d599319bd9f8a8 Change-Id: I28dffc684b6fd0292b94807b88ec6664d5d0e183
* Export of internal Abseil changesGravatar Abseil Team2020-02-11
| | | | | | | | | | | | | | | | | | | | | | | | | | | | -- daa829a331a2316713681b5fe7630d1951e0fdec by Gennadiy Rozental <rogeeff@google.com>: Eliminate Flag's destroy method. The Abseil Flags are never destroyed. The only place where Destroy method was invoked was in some obscure place during flag registration, where we faces with duplicate retired flag registration. Regired Flag destruction is empty anyway. so we can just delete the duplicate object. The FLagImpl::Destroy is never invoked. PiperOrigin-RevId: 294472413 -- 3c159499ccde8ccdd6907b3a1ddb26be7d3f016f by Abseil Team <absl-team@google.com>: Internal change. PiperOrigin-RevId: 294401573 -- 25910db425c50d9b9a8f8275af5a67c2935934fd by Shahriar Rouf <nafi@google.com>: Optimize absl::string_view::compare. Motivation: https://godbolt.org/z/Uz8DWV PiperOrigin-RevId: 294286196 GitOrigin-RevId: daa829a331a2316713681b5fe7630d1951e0fdec Change-Id: I818dad27ac5eb61bb7632e01224953cd882803bf
* Export of internal Abseil changesGravatar Abseil Team2020-02-04
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | -- 1bc4d36e13fb9175ea8cdaa00213aa9d4417c669 by Andy Getzendanner <durandal@google.com>: Fix pointer format specifier in documentation Import of https://github.com/abseil/abseil-cpp/pull/614 PiperOrigin-RevId: 293227540 -- c7b43b30493c4fb5f2ec3264672b08bfe1ea3709 by Abseil Team <absl-team@google.com>: Internal change. PiperOrigin-RevId: 293160245 -- 64439365e2b4a0b5e51ae0a7dafdb15912402dfd by Shahriar Rouf <nafi@google.com>: Add benchmarks for string_view: BM_CompareFirstOneLess and BM_CompareSecondOneLess. PiperOrigin-RevId: 293031676 -- b273b420cab24a6e3f487430987e09f4eb1caec4 by Greg Falcon <gfalcon@google.com>: Remove an unreachable line from charconv.cc. Fixes github issue #613. PiperOrigin-RevId: 292980167 -- 70babb5f7a3d9fdd00a2b3085c3c2b9fe0265c79 by Gennadiy Rozental <rogeeff@google.com>: Move GetFlag implementation into FlagImpl. This change will allow us to hide details of GetFlag overloads inside implementation detais. Eventually we'll migrate to a different implementation. No semantic changes in this CL. PiperOrigin-RevId: 292930847 -- 94bee7b7cc31e0167ee4b953281c1e78c96a574a by Abseil Team <absl-team@google.com>: Clarification in absl::Exponential documentation. PiperOrigin-RevId: 292912672 -- d6916d30c5c1d3ee9ae46d69ec0a166a760c99c7 by Derek Mauro <dmauro@google.com>: Make AtomicHook constant-initializable on Clang for Windows. Only mark AtomicHook as constant-initializable on platforms where it is actually constant-initializable. PiperOrigin-RevId: 292655939 GitOrigin-RevId: 1bc4d36e13fb9175ea8cdaa00213aa9d4417c669 Change-Id: I090b231a0ca0d92868e494ab5b3fa86c902889d5
* Export of internal Abseil changesGravatar Abseil Team2020-01-31
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | -- 0b924fe4e9871200792617329d32beb8356daa9b by Derek Mauro <dmauro@google.com>: Use less threads in the GetTID() test to avoid test timeouts PiperOrigin-RevId: 292566826 -- 0b519c4fd48d61b7c4ea94ed6a6be6e981b9c51a by Abseil Team <absl-team@google.com>: Internal change. PiperOrigin-RevId: 292563778 -- 3204f6e07bcc2b5e9098d45f1a20998f25ab808e by Abseil Team <absl-team@google.com>: Internal change. PiperOrigin-RevId: 292550551 -- 09fbbe73833478d3f26f3e33c8291b991fd3be51 by Derek Mauro <dmauro@google.com>: Add a debug bounds-check to absl::string_view::operator[] string_view accesses that are out-of-bounds are undefined behavior: https://en.cppreference.com/w/cpp/string/basic_string_view/operator_at This change causes code to abort in debug mode, indicating a bug and possibly a security issue like a buffer overflow. Code broken by this change should be investigated. PiperOrigin-RevId: 292544735 -- bf2c19cb45682628f963d4067c0cd6deed7e656d by Derek Mauro <dmauro@google.com>: Add debug assertions to absl::string_view::front and absl::string_view::back Calling front() or back() on an empty string_view is undefined behavior. This assertion is to help catch broken code. https://en.cppreference.com/w/cpp/string/basic_string_view/front https://en.cppreference.com/w/cpp/string/basic_string_view/back PiperOrigin-RevId: 292453255 -- 47f573679b322f8c0fd2cb037cc87e7bc822ac6b by Xiaoyi Zhang <zhangxy@google.com>: Release functional/CMakeList.txt. PiperOrigin-RevId: 292417025 GitOrigin-RevId: 0b924fe4e9871200792617329d32beb8356daa9b Change-Id: Ie6980fb1ac351d72a2ce4468f25bd31db396f88a
* Export of internal Abseil changesGravatar Abseil Team2019-12-12
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | -- c99f979ad34f155fbeeea69b88bdc7458d89a21c by Derek Mauro <dmauro@google.com>: Remove a floating point division by zero test. This isn't testing behavior related to the library, and MSVC warns about it in opt mode. PiperOrigin-RevId: 285220804 -- 68b015491f0dbf1ab547994673281abd1f34cd4b by Gennadiy Rozental <rogeeff@google.com>: This CL introduces following changes to the class FlagImpl: * We eliminate the CommandLineFlagLocks struct. Instead callback guard and callback function are combined into a single CallbackData struct, while primary data lock is stored separately. * CallbackData member of class FlagImpl is initially set to be nullptr and is only allocated and initialized when a flag's callback is being set. For most flags we do not pay for the extra space and extra absl::Mutex now. * Primary data guard is stored in data_guard_ data member. This is a properly aligned character buffer of necessary size. During initialization of the flag we construct absl::Mutex in this space using placement new call. * We now avoid extra value copy after successful attempt to parse value out of string. Instead we swap flag's current value with tentative value we just produced. PiperOrigin-RevId: 285132636 -- ed45d118fb818969eb13094cf7827c885dfc562c by Tom Manshreck <shreck@google.com>: Change null-term* (and nul-term*) to NUL-term* in comments PiperOrigin-RevId: 285036610 -- 729619017944db895ce8d6d29c1995aa2e5628a5 by Derek Mauro <dmauro@google.com>: Use the Posix implementation of thread identity on MinGW. Some versions of MinGW suffer from thread_local bugs. PiperOrigin-RevId: 285022920 -- 39a25493503c76885bc3254c28f66a251c5b5bb0 by Greg Falcon <gfalcon@google.com>: Implementation detail change. Add further ABSL_NAMESPACE_BEGIN and _END annotation macros to files in Abseil. PiperOrigin-RevId: 285012012 GitOrigin-RevId: c99f979ad34f155fbeeea69b88bdc7458d89a21c Change-Id: I4c85d3704e45d11a9ac50d562f39640a6adbedc1
* Export of internal Abseil changesGravatar Abseil Team2019-11-26
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | -- 2ba0e41a21fbdab36b2f4f3b0dd4b112bd788604 by Derek Mauro <dmauro@google.com>: Remove the include of <intsafe.h>, which is missing on some versions of MinGW. DWORD is easily replaced by uint32_t. PiperOrigin-RevId: 282576177 -- 238fd41114b3e83fcb91d2afe1e6dcce7cfd53b0 by Samuel Benzaquen <sbenza@google.com>: Remove assertion in erase(iterator) that tries to use the comparator. Add missing this-> qualifier. Fix bug where node elements are not being destroyed properly. PiperOrigin-RevId: 282427096 -- 6b9446e3b38ed97451c010933e86a572ab659ab2 by Derek Mauro <dmauro@google.com>: Improves/fixes feature detection in thread_identity Only use ABSL_PER_THREAD_TLS_KEYWORD when it is supported (previously on some platforms it evaluated to nothing, which completely breaks everything), but prefer it to thread_local since benchmarks indicate it is slightly faster in this critical code path. Disable the calls to pthread_sigmask on MinGW where it is not supported. PiperOrigin-RevId: 282425291 GitOrigin-RevId: 2ba0e41a21fbdab36b2f4f3b0dd4b112bd788604 Change-Id: I34073ecbb4a43ad71f54161c136d88fc728888f1
* Export of internal Abseil changesGravatar Abseil Team2019-09-25
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | -- 8e04df6fcbd062e5eaf179a6ec9b0a26f8aa8a39 by Abseil Team <absl-team@google.com>: Use a floating point type for the example usage of absl::uniform_real_distribution. PiperOrigin-RevId: 271167776 -- 5f8f1dfea50bc16a9d9af3e50c4636500a938b29 by Abseil Team <absl-team@google.com>: the llvm wasm backend does not support this data symbol in text section, so remove it from the test. PiperOrigin-RevId: 271138100 -- 2874542cb212962ac3093fd78fd5e1eb85c126c0 by Xiaoyi Zhang <zhangxy@google.com>: Work around MSVC 2019 compiler bug related to constexpr in optional_test. The change in optional_test is necessary to avoid another bug on MSVC complaining about accessing invalid member of union, and also makes the test more reasonale by checking the value of a non-static member. Filed a bug against MSVC https://developercommunity.visualstudio.com/content/problem/743998/internal-compiler-error-related-to-constexpr-and-u.html. PiperOrigin-RevId: 271129805 -- 3a5d56f0c3362aabf68938fb95c4e2d3eca59538 by Abseil Team <absl-team@google.com>: Improve precision of absl::GetCurrentTimeNanos() by adjusting cycle time sooner. PiperOrigin-RevId: 271007945 -- 1e044a6dec7c0ca150fff1aee52dbdb16aa43ed7 by Abseil Team <absl-team@google.com>: Internal change. PiperOrigin-RevId: 270962690 GitOrigin-RevId: 8e04df6fcbd062e5eaf179a6ec9b0a26f8aa8a39 Change-Id: Icb05423a7e93ebdae16baadd59a60b75b5cfa249
* Export of internal Abseil changesGravatar Abseil Team2019-08-19
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | -- 62058c9c008e23c787f35c1a5fe05851046a71f1 by Abseil Team <absl-team@google.com>: Fix some strange usage of INSTANTIATE_TEST_SUITE_P PiperOrigin-RevId: 264185105 -- 4400d84027d86415a2f9b81996ff22e7fd7aa30f by Derek Mauro <dmauro@google.com>: Disable testing std::string_view from nullptr on GCC >= GCC9. PiperOrigin-RevId: 264150587 -- 656d5a742ba48d025589709fad33ddae4b02c620 by Matt Calabrese <calabrese@google.com>: Fix `absl::any_cast` such that it properly works with qualifications. PiperOrigin-RevId: 263843429 -- 6ec89214a4ef2170bf069623a56ffd22863b748d by Abseil Team <absl-team@google.com>: Use macros to enable inline constexpr variables in compare.h when the compiler supports the feature. PiperOrigin-RevId: 263790677 -- a5171e0897195a0367fc08abce9504f813d027ff by Derek Mauro <dmauro@google.com>: Add the Apache License to files that are missing it. PiperOrigin-RevId: 263774164 -- 19e09a7ce8a0aac0a7d534e1799e4d73b63a1bb5 by Abseil Team <absl-team@google.com>: Update iter.position when moving up the tree in rebalance_after_delete. This field isn't read after the first iteration in rebalance_after_delete, and I think it's not a correctness issue, but it is read in try_merge_or_rebalance and potentially affects rebalancing decisions so it can affect performance. There's also an extremely unlikely potential for undefined behavior due to signed integer overflow since this field is only ever incremented in try_merge_or_rebalance (and position is an int). Basically though, I just don't think it makes sense to have this invalid iterator floating around here. PiperOrigin-RevId: 263770305 GitOrigin-RevId: 62058c9c008e23c787f35c1a5fe05851046a71f1 Change-Id: I1e2fb7cbfac7507dddedd181414ee35a5778f8f5
* Export of internal Abseil changesGravatar Abseil Team2019-08-09
-- 3dbb096e4662311f81df1017a8e0975e903936cf by Derek Mauro <dmauro@google.com>: Document and workaround a known MSVC bug doing constexpr pointer arithmetic PiperOrigin-RevId: 262604652 -- b5fa7f1a0c776f6ba20d52772a1679ec42ad21fd by Derek Mauro <dmauro@google.com>: Fix typo in macos_xcode_bazel.sh PiperOrigin-RevId: 262591285 -- 89dd77ab5bb44d76b6cb6b2f288e21536e16a85a by Derek Mauro <dmauro@google.com>: Internal change PiperOrigin-RevId: 262582747 -- 32295ed9a0c6c8ab143a912194040eede05d3ea3 by Abseil Team <absl-team@google.com>: Internal change PiperOrigin-RevId: 262569140 -- 7f0f5b94197369228024529022d727439d2c894f by Abseil Team <absl-team@google.com>: Internal change PiperOrigin-RevId: 262563554 -- 314aed043639abbd221074125c57b7c68616de7e by Derek Mauro <dmauro@google.com>: Release absl::btree PiperOrigin-RevId: 262553526 -- 72b44056c6ce9000c4a6cd9aec58b82067c82a13 by CJ Johnson <johnsoncj@google.com>: Internal change PiperOrigin-RevId: 262421185 -- 4e2c12151edf534f929e8e810f1334073f90489a by Abseil Team <absl-team@google.com>: Update documentation to make it less likely for users to write `Hours(24)` without considering using civil dates instead. PiperOrigin-RevId: 262420758 -- 92b85b9573e800bd96b019408eefbc5ce4f68780 by Derek Mauro <dmauro@google.com>: Add the ability to override the bazel version in the macos_xcode_bazel.sh test script. PiperOrigin-RevId: 262412063 GitOrigin-RevId: 3dbb096e4662311f81df1017a8e0975e903936cf Change-Id: I423b2b829dc0c5f814e37bec4d68c7470f43f041
generated by cgit v1.2.3 (git 2.39.1) at 2025-01-07 13:32:15 +0000