| Commit message (Collapse) | Author | Age |
|
|
|
|
|
|
|
| |
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
|
|
|
|
|
|
|
| |
the element being extracted).
PiperOrigin-RevId: 485120182
Change-Id: Ic54d538721678bed0a748dacbf33c319e62b93b8
|
|
|
|
|
|
|
|
| |
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
|
|
|
|
|
|
|
|
|
|
| |
between raw_hash_set and btree.
Also remove the transfer implementations from btree_set.h and flat_hash_set.h, which are equivalent to the default implementations.
Motivation: this will simplify upcoming changes related to trivial relocation.
PiperOrigin-RevId: 477493403
Change-Id: I75babef4c93dec3a8105f86c58af54199bb1ec9c
|
|
|
|
|
|
|
| |
Avoid using value move/swap and delete those functions from slot_policy types. There was only one use of params_type::move in `erase`.
PiperOrigin-RevId: 453237739
Change-Id: Ie81c6dba6c4db34e97a067d2c0defcded8044a5a
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
the allocator (ignoring copy/move constructors).
We were using `init_type`s for temp values that we would move into slots, but in this case, we need to have actual slots. We use node handles for managing slots outside of nodes.
Also, in btree::copy_or_move_values_in_order, pass the slots from the iterators rather than references to values. This allows for moving from map keys instead of copying for standard layout types.
In the test, fix a couple of ClangTidy warnings from missing includes and calling `new` instead of `make_unique`.
PiperOrigin-RevId: 452062967
Change-Id: I870e89ae1aa5b3cfa62ae6e75b73ffc3d52e731c
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
--
91d76b3ac9edff91f206d9eee60423c39eeeaf93 by Derek Mauro <dmauro@google.com>:
Internal change
PiperOrigin-RevId: 430442277
--
9f8a87bcc5cc5b0fd8b7f0318f37d152fd8bea06 by Evan Brown <ezb@google.com>:
Small refactoring to work towards allowing for node_btree_* containers.
- Change common_params::transfer to rely on slot_policy transfer instead of manually doing construct/destruct. Transfer is not construct/destruct for node containers.
- Move maps' value_compare into btree.h from btree_map.h so it can be reused for node_btree_map.h.
- Also add a test for maps' value_compare protected members.
PiperOrigin-RevId: 430245542
--
0126e0b6295342317d9c9f0a66e2d7009b858426 by Martijn Vels <mvels@google.com>:
Add CordRepSubString::Create function with hard checks on IsFlat() | IsExternal()
This hardens internal invariants, IsFlat() || IsExternal() is a cheap, single predicted branch, and removes boilerplate code from cord.cc
PiperOrigin-RevId: 429676041
--
ed98a92af49d9e238d9f1d1b69fb4eddcd1ccbc7 by Abseil Team <absl-team@google.com>:
tweaks to status.h documentation to reflect general-purpose communication
PiperOrigin-RevId: 429584104
GitOrigin-RevId: 91d76b3ac9edff91f206d9eee60423c39eeeaf93
Change-Id: I54d6d116a564f86a842b983ca76559bf9b388f72
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
--
e7f53dfbf809812e84770217777f81b6308a3084 by Abseil Team <absl-team@google.com>:
Add a parameter pack to absl profile to allow profiles to separate
dynamic data from static data that is available at constructor-time.
Background: `inline_element_size` is effectively constant, but there
is a data race between its initialization and its access. We had fixed that race by making
inline_element_size atomic. This CL changes `inline_element_size`
back to a non-atomic integer, and provides a way for all profiles to
provide Register()-time values.
PiperOrigin-RevId: 413960559
--
70234c5943f8e37e17c1d9c54d8ed61d39880abf by Chris Kennelly <ckennelly@google.com>:
Document that absl::FunctionRef does not allocate.
PiperOrigin-RevId: 413946831
--
3308ae571412c4be3cc32d088c6edac98ff2d1ed by Samuel Benzaquen <sbenza@google.com>:
Internal change
PiperOrigin-RevId: 413933619
--
1617093a730d055edcf7bc04fdd6509783f5f75d by Martijn Vels <mvels@google.com>:
Internal Change
PiperOrigin-RevId: 413778735
--
03ad683f059c806a6c8b04f5b79b2662c3df8c73 by Evan Brown <ezb@google.com>:
Unify btree erase_if definitions and optimize them so that we only do rebalancing once per leaf node.
PiperOrigin-RevId: 413757280
--
5ba402f70801938178e486617063f01c7862525d by Martijn Vels <mvels@google.com>:
Cleanup up cord sampling internals
PiperOrigin-RevId: 413755011
--
522da8f9d3e0f11630d89fb41952004742bc335a by Evan Brown <ezb@google.com>:
Add b-tree benchmark for erase_if.
Since this benchmark doesn't work for std:: containers before C++20, disable it for them.
PiperOrigin-RevId: 413740844
--
a690ea42de8ed4a761d00235d8b2fb7548ba9732 by Andy Getzendanner <durandal@google.com>:
Import of CCTZ from GitHub.
PiperOrigin-RevId: 413735737
GitOrigin-RevId: e7f53dfbf809812e84770217777f81b6308a3084
Change-Id: I4f9f9039ba92831bc48971964aa063244c9fed72
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
--
e2a571b818faaec4185426a8cf71fd2970674423 by Matt Kulukundis <kfm@google.com>:
Fix missed use of old RTTI macro
PiperOrigin-RevId: 413239579
--
e3c15a3fe0a4e44d6e08d69ad912b2245a403bd6 by Derek Mauro <dmauro@google.com>:
Makes erase_if return the number of erased elements for compatibility
with C++20
https://en.cppreference.com/w/cpp/container/unordered_map/erase_if
This may technically be an API break, but no actual breaks were found
in Google code. Fixes to open source code should be trivial.
Closes #1065
PiperOrigin-RevId: 413204392
--
c1fb1ddbc2def3f3d177e5b80b9934bdbb7b16fc by Matt Kulukundis <kfm@google.com>:
Consolidate to a single HAS_RTTI macro
PiperOrigin-RevId: 413169336
GitOrigin-RevId: e2a571b818faaec4185426a8cf71fd2970674423
Change-Id: I74b78ebd5fc172e3f5fcbd13a58cf53f7b250ae9
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
--
355b8f7b0070b005d53d94ee4180e95559ba2c88 by Derek Mauro <dmauro@google.com>:
Documentation: don't define absl::Status::ok() in terms of itself
Fixes #1058
PiperOrigin-RevId: 410035651
--
31c512c834b3a8979297adc5006c3727a3c6554b by Evan Brown <ezb@google.com>:
Cleanup: move set_params/set_slot_policy into btree_set.h and move map_params into btree_map.h.
Also change some `sizeof(value_type)`s to `sizeof(slot_type)`s and update some comments/variable names referring to values to refer to slots as appropriate in btree.h.
Motivation: preliminary cleanup towards node_btree_*.
PiperOrigin-RevId: 409991342
--
3129ca320d61a82f1c9ee8c02a23d25024eea4ab by Abseil Team <absl-team@google.com>:
Use simpler implementation for AddressIsReadable.
In particular, current solution doesn't work on systems configured with large
pid_t space.
PiperOrigin-RevId: 409397716
--
f71067f7494b19ce4a2e1df730b934dc931c51b2 by Martijn Vels <mvels@google.com>:
Add Span dependency
PiperOrigin-RevId: 409198889
GitOrigin-RevId: 355b8f7b0070b005d53d94ee4180e95559ba2c88
Change-Id: I7f4df3ec7739fdfde61d8ba983f07a08f6f1c7d7
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
--
4324716dc5384f03dcd7e36e8cca0e944e4dac74 by Evan Brown <ezb@google.com>:
Clarify comments about API differences from std::{set,map} in btree headers.
We note that the most important API differences are mentioned in the next paragraph and that other API differences are minor. An example of another minor API difference is the note about std::launder in the comment for `extract`.
Motivation: readers shouldn't feel like they need to read the entire header file to understand why b-tree containers are not "drop-in replacements" for STL containers.
PiperOrigin-RevId: 408703780
--
7e8da4f14afd25d11713eee6b743ba31605332bf by Derek Mauro <dmauro@google.com>:
Remove the test for absl::base_internal::NominalCPUFrequency() from OSS code
This is an internal-only function that should never by called by OSS code.
By its nature fails on unsupported platforms.
Google code has tests for this function on supported internal platforms.
Fixes #1053
PiperOrigin-RevId: 408692861
--
37bad2e003b17e3f82d6fd5d90ae183553c018b0 by Abseil Team <absl-team@google.com>:
To avoid triggering -Wmissing-variable-declarations warnings, ABSL_FLAG now
declares the Flag before defining it.
PiperOrigin-RevId: 408673990
GitOrigin-RevId: 4324716dc5384f03dcd7e36e8cca0e944e4dac74
Change-Id: I8c8ea73c4a4e38729c5bfdfa3fefb5d593e0536c
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
--
336f161ad8cb2cc3e1a6bbcbbb8c5b692ee59789 by Derek Mauro <dmauro@google.com>:
Internal change
PiperOrigin-RevId: 398308807
--
80d512823d17561a45feca81f37713a91a175349 by Abseil Team <absl-team@google.com>:
Internal change.
PiperOrigin-RevId: 398257218
--
f1f9792000355eb1d0c11b17800048491662a218 by Abseil Team <absl-team@google.com>:
Fix documentation for btree_multi{map,set}::merge to match behavior for elements with equivalent keys.
PiperOrigin-RevId: 398071060
--
8a9a302aebf2419e83f0c7dc5a63c33d26b807a3 by James Y Knight <jyknight@google.com>:
Silence -Wunused-value warning newly emitted by ToT Clang.
The value is being intentionally ignored, as the purpose of the call is only to eliminate this overload via SFINAE when `GenT{}` is not constant evaluable.
PiperOrigin-RevId: 397861294
GitOrigin-RevId: 336f161ad8cb2cc3e1a6bbcbbb8c5b692ee59789
Change-Id: I946e1d22619f92ce6a424c8c13a20a50b39ed463
|
|
|
|
|
|
|
|
|
|
|
| |
--
4fd27d1c0fda72a8772f2779714c327b18ae657b by Derek Mauro <dmauro@google.com>:
Adds missing documentation for btree's lower_bound and upper_bound methods
PiperOrigin-RevId: 395777262
GitOrigin-RevId: 4fd27d1c0fda72a8772f2779714c327b18ae657b
Change-Id: Ife2f9149bcf30523be93ee9d8919c7085a9d3a29
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
--
14d42e9d0b8aed0c0f00900cd6fd790908930de5 by Gennadiy Rozental <rogeeff@google.com>:
Fix gcc ci build command for LTS
PiperOrigin-RevId: 331543198
--
f1655ec91a4ad656dd1100cf2e134d08941278ca by Abseil Team <absl-team@google.com>:
Consistently document size_type return value of all map/set types.
PiperOrigin-RevId: 331528359
GitOrigin-RevId: 14d42e9d0b8aed0c0f00900cd6fd790908930de5
Change-Id: I33ebba4acb3e5918e4e112f03c81aba529dcd0b4
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
--
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
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
--
a7e789be4687681b98060fddbf8bd1c64a8f5908 by Abseil Team <absl-team@google.com>:
Support C++20 erase_if API in btree.
See the reference here: https://en.cppreference.com/w/cpp/container/set/erase_if.
PiperOrigin-RevId: 286235196
--
952dd2fdd8435dd293e2186c97e14ef3f29a1aa6 by Derek Mauro <dmauro@google.com>:
Avoids accessing an out-of-bounds value during flag parsing
PiperOrigin-RevId: 286206167
--
ba24591ade579fc4446a09bb3f23bf3602908c04 by Abseil Team <absl-team@google.com>:
Change null term* (and nul term*) to NUL-term* in comments.
PiperOrigin-RevId: 286066376
--
d770baecf36f3d7a8214ca2033d90696ba353d00 by Andy Soffer <asoffer@google.com>:
cmake: Fix x86_64 check on Windows for random copts
Import of https://github.com/abseil/abseil-cpp/pull/518
PiperOrigin-RevId: 286056395
--
9ed007e284ecf6ec79547437dbed9ce3023204b9 by Greg Falcon <gfalcon@google.com>:
Manual re-import of CCTZ from GitHub. filegroup() moved as a side effect of an internal change.
PiperOrigin-RevId: 286015866
--
25441cc5cb7ee906177f8dac0dcd524df0e6e305 by Derek Mauro <dmauro@google.com>:
Fix implicit cycle in debugging build rules due to .inc files
PiperOrigin-RevId: 285873346
GitOrigin-RevId: a7e789be4687681b98060fddbf8bd1c64a8f5908
Change-Id: Idef8cce4e723fccae6bdd749e94e11e655908214
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
--
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
|
|
--
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
|