Abseil在linux上编译的静态库(c++17)

// Copyright 2018 The Abseil Authors. // // Licensed under the Apache License, Version 2.0 (the "License"); // you may not use this file except in compliance with the License. // You may obtain a copy of the License at // // https://www.apache.org/licenses/LICENSE-2.0 // // Unless required by applicable law or agreed to in writing, software // distributed under the License is distributed on an "AS IS" BASIS, // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. // See the License for the specific language governing permissions and // limitations under the License. // A btree implementation of the STL set and map interfaces. A btree is smaller // and generally also faster than STL set/map (refer to the benchmarks below). // The red-black tree implementation of STL set/map has an overhead of 3 // pointers (left, right and parent) plus the node color information for each // stored value. So a set<int32_t> consumes 40 bytes for each value stored in // 64-bit mode. This btree implementation stores multiple values on fixed // size nodes (usually 256 bytes) and doesn't store child pointers for leaf // nodes. The result is that a btree_set<int32_t> may use much less memory per // stored value. For the random insertion benchmark in btree_bench.cc, a // btree_set<int32_t> with node-size of 256 uses 5.1 bytes per stored value. // // The packing of multiple values on to each node of a btree has another effect // besides better space utilization: better cache locality due to fewer cache // lines being accessed. Better cache locality translates into faster // operations. // // CAVEATS // // Insertions and deletions on a btree can cause splitting, merging or // rebalancing of btree nodes. And even without these operations, insertions // and deletions on a btree will move values around within a node. In both // cases, the result is that insertions and deletions can invalidate iterators // pointing to values other than the one being inserted/deleted. Therefore, this // container does not provide pointer stability. This is notably different from // STL set/map which takes care to not invalidate iterators on insert/erase // except, of course, for iterators pointing to the value being erased. A // partial workaround when erasing is available: erase() returns an iterator // pointing to the item just after the one that was erased (or end() if none // exists). #ifndef ABSL_CONTAINER_INTERNAL_BTREE_H_ #define ABSL_CONTAINER_INTERNAL_BTREE_H_ #include <algorithm> #include <cassert> #include <cstddef> #include <cstdint> #include <cstring> #include <functional> #include <iterator> #include <limits> #include <new> #include <string> #include <type_traits> #include <utility> #include "absl/base/internal/raw_logging.h" #include "absl/base/macros.h" #include "absl/container/internal/common.h" #include "absl/container/internal/compressed_tuple.h" #include "absl/container/internal/container_memory.h" #include "absl/container/internal/layout.h" #include "absl/memory/memory.h" #include "absl/meta/type_traits.h" #include "absl/strings/cord.h" #include "absl/strings/string_view.h" #include "absl/types/compare.h" #include "absl/utility/utility.h" namespace absl { ABSL_NAMESPACE_BEGIN namespace container_internal { #ifdef ABSL_BTREE_ENABLE_GENERATIONS #error ABSL_BTREE_ENABLE_GENERATIONS cannot be directly set #elif defined(ABSL_HAVE_ADDRESS_SANITIZER) || \ defined(ABSL_HAVE_MEMORY_SANITIZER) // When compiled in sanitizer mode, we add generation integers to the nodes and // iterators. When iterators are used, we validate that the container has not // been mutated since the iterator was constructed. #define ABSL_BTREE_ENABLE_GENERATIONS #endif template <typename Compare, typename T, typename U> using compare_result_t = absl::result_of_t<const Compare(const T &, const U &)>; // A helper class that indicates if the Compare parameter is a key-compare-to // comparator. template <typename Compare, typename T> using btree_is_key_compare_to = std::is_convertible<compare_result_t<Compare, T, T>, absl::weak_ordering>; struct StringBtreeDefaultLess { using is_transparent = void; StringBtreeDefaultLess() = default; // Compatibility constructor. StringBtreeDefaultLess(std::less<std::string>) {} // NOLINT StringBtreeDefaultLess(std::less<absl::string_view>) {} // NOLINT // Allow converting to std::less for use in key_comp()/value_comp(). explicit operator std::less<std::string>() const { return {}; } explicit operator std::less<absl::string_view>() const { return {}; } explicit operator std::less<absl::Cord>() const { return {}; } absl::weak_ordering operator()(absl::string_view lhs, absl::string_view rhs) const { return compare_internal::compare_result_as_ordering(lhs.compare(rhs)); } StringBtreeDefaultLess(std::less<absl::Cord>) {} // NOLINT absl::weak_ordering operator()(const absl::Cord &lhs, const absl::Cord &rhs) const { return compare_internal::compare_result_as_ordering(lhs.Compare(rhs)); } absl::weak_ordering operator()(const absl::Cord &lhs, absl::string_view rhs) const { return compare_internal::compare_result_as_ordering(lhs.Compare(rhs)); } absl::weak_ordering operator()(absl::string_view lhs, const absl::Cord &rhs) const { return compare_internal::compare_result_as_ordering(-rhs.Compare(lhs)); } }; struct StringBtreeDefaultGreater { using is_transparent = void; StringBtreeDefaultGreater() = default; StringBtreeDefaultGreater(std::greater<std::string>) {} // NOLINT StringBtreeDefaultGreater(std::greater<absl::string_view>) {} // NOLINT // Allow converting to std::greater for use in key_comp()/value_comp(). explicit operator std::greater<std::string>() const { return {}; } explicit operator std::greater<absl::string_view>() const { return {}; } explicit operator std::greater<absl::Cord>() const { return {}; } absl::weak_ordering operator()(absl::string_view lhs, absl::string_view rhs) const { return compare_internal::compare_result_as_ordering(rhs.compare(lhs)); } StringBtreeDefaultGreater(std::greater<absl::Cord>) {} // NOLINT absl::weak_ordering operator()(const absl::Cord &lhs, const absl::Cord &rhs) const { return compare_internal::compare_result_as_ordering(rhs.Compare(lhs)); } absl::weak_ordering operator()(const absl::Cord &lhs, absl::string_view rhs) const { return compare_internal::compare_result_as_ordering(-lhs.Compare(rhs)); } absl::weak_ordering operator()(absl::string_view lhs, const absl::Cord &rhs) const { return compare_internal::compare_result_as_ordering(rhs.Compare(lhs)); } }; // See below comments for checked_compare. template <typename Compare, bool is_class = std::is_class<Compare>::value> struct checked_compare_base : Compare { using Compare::Compare; explicit checked_compare_base(Compare c) : Compare(std::move(c)) {} const Compare &comp() const { return *this; } }; template <typename Compare> struct checked_compare_base<Compare, false> { explicit checked_compare_base(Compare c) : compare(std::move(c)) {} const Compare &comp() const { return compare; } Compare compare; }; // A mechanism for opting out of checked_compare for use only in btree_test.cc. struct BtreeTestOnlyCheckedCompareOptOutBase {}; // A helper class to adapt the specified comparator for two use cases: // (1) When using common Abseil string types with common comparison functors, // convert a boolean comparison into a three-way comparison that returns an // `absl::weak_ordering`. This helper class is specialized for // less<std::string>, greater<std::string>, less<string_view>, // greater<string_view>, less<absl::Cord>, and greater<absl::Cord>. // (2) Adapt the comparat