| // Copyright 2016 The Fuchsia Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #ifndef FBL_INTRUSIVE_CONTAINER_UTILS_H_ |
| #define FBL_INTRUSIVE_CONTAINER_UTILS_H_ |
| |
| #include <type_traits> |
| #include <utility> |
| |
| #include <fbl/intrusive_pointer_traits.h> |
| #include <fbl/macros.h> |
| |
| namespace fbl { |
| |
| // DefaultKeyedObjectTraits defines a default implementation of traits used to |
| // manage objects stored in associative containers such as hash-tables and |
| // trees. |
| // |
| // At a minimum, a class or a struct which is to be used to define the |
| // traits of a keyed object must define the following public members. |
| // |
| // GetKey : A static method which takes a constant reference to an object (the |
| // type of which is infered from PtrType) and returns a KeyType |
| // instance corresponding to the key for an object. |
| // LessThan : A static method which takes two keys (key1 and key2) and returns |
| // true if-and-only-if key1 is considered to be less than key2 for |
| // sorting purposes. |
| // EqualTo : A static method which takes two keys (key1 and key2) and returns |
| // true if-and-only-if key1 is considered to be equal to key2. |
| // |
| // Rules for keys: |
| // ++ The type of key returned by GetKey must be compatible with the key which |
| // was specified for the container. |
| // ++ The key for an object must remain constant for as long as the object is |
| // contained within a container. |
| // ++ When comparing keys, comparisons must obey basic transative and |
| // commutative properties. That is to say... |
| // LessThan(A, B) and LessThan(B, C) implies LessThan(A, C) |
| // EqualTo(A, B) and EqualTo(B, C) implies EqualTo(A, C) |
| // EqualTo(A, B) if-and-only-if EqualTo(B, A) |
| // LessThan(A, B) if-and-only-if EqualTo(B, A) or (not LessThan(B, A)) |
| // |
| // DefaultKeyedObjectTraits is a helper class which allows an object to be |
| // treated as a keyed-object by implementing a const GetKey method which returns |
| // a key of the appropriate type. The key type must be compatible with the |
| // container key type, and must have definitions of the < and == operators for |
| // the purpose of generating implementation of LessThan and EqualTo. |
| template <typename KeyType, typename ObjType> |
| struct DefaultKeyedObjectTraits { |
| static KeyType GetKey(const ObjType& obj) { return obj.GetKey(); } |
| static bool LessThan(const KeyType& key1, const KeyType& key2) { return key1 < key2; } |
| static bool EqualTo(const KeyType& key1, const KeyType& key2) { return key1 == key2; } |
| }; |
| |
| // A set of flag-style options which can be applied to container nodes in order |
| // to control and sanity check their behavior and compatibility at compile time. |
| // |
| // To control node options, users pass a set of options to either the |
| // containable mix-in class (SinglyLinkedLisable, DoublyLinkedListable, or |
| // WAVLTreeContainable), or directly to the node instance in the case that the |
| // user is specifying custom container traits. |
| enum class NodeOptions : uint64_t { |
| None = 0, |
| |
| // By default, nodes will not allow either copy construction or copy |
| // assignment. Directly copying the contents of node storage for a structure |
| // which is currently in a container cannot be allowed. The result would be |
| // to have two objects, one of which is actually in a container, and the other |
| // of which is only sort-of in the container. |
| // |
| // Because of this, if code attempts to expand either the copy constructor or |
| // assignment operator, by default it will trigger a static assert. |
| // |
| // It may be the case, however, that a user wishes to allow copying of their |
| // structure while the source and destination structure are _not_ in any |
| // containers. In this case, pass the NodeOptions::AllowCopy flag. Nodes |
| // will permit copying, but will runtime ZX_DEBUG_ASSERT if either the source |
| // or destination exist within a container at the time of the copy. In builds |
| // with ZX_DEBUG_ASSERTs disabled, neither the source nor the destination's |
| // internal node contents will be modified. So, in the case of the following |
| // code: |
| // |
| // MyStructure& A = *(container.begin()); |
| // MyStructure B = A; |
| // MyStructure& C = get_a_structure_reference_from_somewhere(); |
| // C = A; |
| // |
| // ++ A will remain in the container unmodified. |
| // ++ B will be in no container (as it was just constructed). |
| // ++ C either will either remain in its container if it had been in one, or |
| // will remain in no container if not. |
| // |
| // Finally, it is possible that a user actually _does_ wish to copy the |
| // contents of a structure out of a container using either copy construction |
| // or using copy assignment. If this is the case, pass the |
| // NodeOptions::AllowCopyFromContainer flag. In addition to allowing the copy |
| // constructor and assignment operators, the debug asserts will be disabled in |
| // this situation. Users may copy the contents of their node, but not mutate |
| // any container membership state as part of the process. |
| // |
| AllowCopy = (1 << 0), |
| AllowCopyFromContainer = (1 << 1), |
| |
| // See the AllowCopy and AllowCopyFromConainer flags for details. AllowMove |
| // and AllowMoveFromContainer are the same, simply applied to the rvalue |
| // constructor and assignment operators of the node. |
| AllowMove = (1 << 2), |
| AllowMoveFromContainer = (1 << 3), |
| |
| // Convenience definitions |
| AllowCopyMove = static_cast<uint64_t>(AllowCopy) | static_cast<uint64_t>(AllowMove), |
| AllowCopyMoveFromContainer = |
| static_cast<uint64_t>(AllowCopyFromContainer) | static_cast<uint64_t>(AllowMoveFromContainer), |
| |
| // Allow an object to exist in multiple containers at once, even if one or |
| // more of those containers tracks the object using a unique_ptr (or any other |
| // non-copyable pointer type). |
| // |
| // Generally, it would be a mistake to define an object which can exist in |
| // multiple containers concurrently, and track those objects in their |
| // containers using unique_ptr semantics. In theory, it should be impossible |
| // for two different containers to track the same object at the same time, |
| // each using something like a unique_ptr. This would violate the uniqueness of |
| // the pointer. |
| // |
| // Because of this, the ContainableBaseClasses helper (see below) will, by |
| // default, complain and refuse to build if someone attempts to use it in |
| // conjunction with a Containable mix-in which tracks objects using |
| // unique_ptr-style pointers. |
| // |
| // There are special cases, however, where a user might want this behavior to |
| // be permitted. Consider an object whose lifecycle is managed by a central |
| // list of unique_ptrs, but which can also exist on a temporary list which |
| // tracks the objects using raw pointers for strictly algorithmic purposes. |
| // Provided that the user carefully ensures that the object does not disappear |
| // from the central list while it exists on the temporary list, this should be |
| // completely fine. More concretely, the following should be allowed provided |
| // that the user opts in. |
| // |
| // using MainList = fbl::TaggedDoublyLinkedList<std::unique_ptr<Obj>, MainListTag>; |
| // using TmpList = fbl::TaggedSinglyLinkedList<Obj*, TmpListTag>; |
| // |
| // fbl::Mutex all_objects_lock; |
| // MainList all_objects TA_GUARDED(all_objects_lock); |
| // |
| // void do_interesting_things() TA_EXCL(all_objects_lock) { |
| // fbl::AutoLock lock(&all_objects_lock); |
| // TmpList interesting_objects; |
| // |
| // for (auto& obj : all_objects) { |
| // if (object_is_interesting(obj)) { |
| // interesting_objects.push(obj); |
| // } |
| // } |
| // |
| // do_interesting_things_to_interesting_objects(std::move(interesting_objects)); |
| // } |
| // |
| // Users who have carefully considered the lifecycle management of their |
| // objects and wish to allow this behavior should pass the |
| // AllowMultiContainerUptr option to their Containable mix-in. |
| AllowMultiContainerUptr = (1 << 4), |
| |
| // Reserved bits reserved for testing purposes and should always be ignored by |
| // node implementations. |
| ReservedBits = 0xF000000000000000, |
| }; |
| |
| // Helper functions which make it a bit easier to use the enum class NodeOptions |
| // in a flag style fashion. |
| // |
| // The | operator will take two options and or them together to produce their |
| // composition without needing to do all sorts of nasty casting. In other |
| // words: |
| // |
| // fbl::NodeOptions::AllowX | fbl::NodeOptions::AllowY |
| // |
| // is legal. |
| // |
| // The & operator is overloaded to perform the bitwise and of the |
| // underlying flags and test against zero returning a bool. This allows us to |
| // say things like: |
| // |
| // if constexpr (SomeOptions | fbl::NodeOptions::AllowX) { ... } |
| // |
| constexpr fbl::NodeOptions operator|(fbl::NodeOptions A, fbl::NodeOptions B) { |
| return static_cast<fbl::NodeOptions>( |
| static_cast<std::underlying_type<fbl::NodeOptions>::type>(A) | |
| static_cast<std::underlying_type<fbl::NodeOptions>::type>(B)); |
| } |
| |
| constexpr bool operator&(fbl::NodeOptions A, fbl::NodeOptions B) { |
| return (static_cast<std::underlying_type<fbl::NodeOptions>::type>(A) & |
| static_cast<std::underlying_type<fbl::NodeOptions>::type>(B)) != 0; |
| } |
| |
| struct DefaultObjectTag {}; |
| |
| // ContainableBaseClasses<> makes it easy to define types that live in multiple |
| // intrusive containers at once. |
| // |
| // If you didn't use this helper template, you would have to define multiple |
| // traits classes, each with their own node_state function, and then have |
| // multiple NodeState members in your class. This is noisy boilerplate, so |
| // instead you can just do something like the following: |
| // |
| // struct MyTag1 {}; |
| // struct MyTag2 {}; |
| // struct MyTag3 {}; |
| // |
| // class MyClass |
| // : public fbl::RefCounted<MyClass>, |
| // public fbl::ContainableBaseClasses< |
| // fbl::WAVLTreeContainable<fbl::RefPtr<MyClass>, MyTag1>, |
| // fbl::WAVLTreeContainable<fbl::RefPtr<MyClass>, MyTag2>, |
| // fbl::SinglyLinkedListable<MyClass*, MyTag3>, |
| // [...]> { <your class definition> }; |
| // |
| // Then when you create your container, you use the same tag type: |
| // |
| // fbl::TaggedWAVLTree<uint32_t, fbl::RefPtr<MyClass>, MyTag1> my_tree; |
| // |
| // The tag types themselves can be basically anything but I recommend you define |
| // your own empty structs to keep it simple and make it a type that you own. |
| // |
| // (Note for the curious: the tag types are necessary to solve the diamond |
| // problem, since your class ends up with multiple node_state_ members from the |
| // non-virtual multiple inheritance and the compiler needs to know which one you |
| // want.) |
| // |
| // When you inherit from this template, your class will also end up with a |
| // TagTypes member, which is just a std::tuple of your tag types, so that |
| // you can query these for metaprogramming purposes. |
| // |
| // You should also get relatively readable error messages for common error cases |
| // because of a few static_asserts; notably, you cannot: |
| // ++ Use any variation of unique_ptr as the PtrType here since that would defeat |
| // its purpose. |
| // ++ Explicitly use the DefaultObjectTag that is used as the tag type when |
| // the user does not specify one. |
| // ++ Pass the same tag type twice. |
| // |
| namespace internal { |
| |
| template <typename... BaseClasses> |
| struct ContainableBaseClassEnumerator; |
| |
| template <> |
| struct ContainableBaseClassEnumerator<> { |
| using ContainableTypes = std::tuple<>; |
| using TagTypes = std::tuple<>; |
| }; |
| |
| template <template <typename, NodeOptions, typename> class Containable, typename PtrType, |
| NodeOptions Options, typename TagType, typename... Rest> |
| struct ContainableBaseClassEnumerator<Containable<PtrType, Options, TagType>, Rest...> |
| : public Containable<PtrType, Options, TagType>, |
| public ContainableBaseClassEnumerator<Rest...> { |
| static_assert(internal::ContainerPtrTraits<PtrType>::CanCopy || |
| (Options & NodeOptions::AllowMultiContainerUptr), |
| "You can't have a unique_ptr in multiple containers at once without specifying the " |
| "AllowMultiContainerUptr flag in your node options."); |
| static_assert(!std::is_same_v<TagType, DefaultObjectTag>, |
| "Do not use fbl::DefaultObjectTag when inheriting from " |
| "fbl::ContainableBaseClasses; define your own instead."); |
| static_assert((!std::is_same_v<TagType, typename Rest::TagType> && ...), |
| "All tag types used with fbl::ContainableBaseClassEnumerator must be unique."); |
| |
| using ContainableTypes = decltype(std::tuple_cat( |
| std::declval<std::tuple<Containable<PtrType, Options, TagType>>>(), |
| std::declval<typename ContainableBaseClassEnumerator<Rest...>::ContainableTypes>())); |
| using TagTypes = decltype( |
| std::tuple_cat(std::declval<std::tuple<TagType>>(), |
| std::declval<typename ContainableBaseClassEnumerator<Rest...>::TagTypes>())); |
| }; |
| |
| } // namespace internal |
| |
| template <typename... BaseClasses> |
| struct ContainableBaseClasses { |
| using Enumerator = internal::ContainableBaseClassEnumerator<BaseClasses...>; |
| using ContainableTypes = typename Enumerator::ContainableTypes; |
| using TagTypes = typename Enumerator::TagTypes; |
| |
| template <typename Tag, size_t N = 0> |
| static constexpr size_t TagIndex() { |
| static_assert(N < std::tuple_size<ContainableTypes>(), "Tag not found!"); |
| using ContainableType = typename std::tuple_element<N, ContainableTypes>::type; |
| if constexpr (std::is_same_v<Tag, typename ContainableType::TagType>) { |
| return N; |
| } else { |
| return TagIndex<Tag, N + 1>(); |
| } |
| } |
| |
| template <typename Tag> |
| auto& GetContainableByTag() { |
| constexpr size_t Index = TagIndex<Tag>(); |
| return std::get<Index>(contained_nodes_); |
| } |
| |
| template <typename Tag> |
| const auto& GetContainableByTag() const { |
| constexpr size_t Index = TagIndex<Tag>(); |
| return std::get<Index>(contained_nodes_); |
| } |
| |
| ContainableTypes contained_nodes_; |
| }; |
| |
| namespace internal { |
| DECLARE_HAS_MEMBER_TYPE(has_tag_types, TagTypes); |
| } |
| |
| // This is a free function because making it a member function presents complicated lookup issues |
| // since the specific Containable classes exist as members of the ContainableBaseClasses<...>, and |
| // you'd need to say obj.template GetContainableByTag<TagType>().InContainer, which is super ugly. |
| template <typename TagType = DefaultObjectTag, typename Containable> |
| bool InContainer(const Containable& c) { |
| if constexpr (std::is_same_v<TagType, DefaultObjectTag>) { |
| return c.InContainer(); |
| } else { |
| return c.template GetContainableByTag<TagType>().InContainer(); |
| } |
| } |
| |
| // An enumeration which can be used as a template argument on list types to |
| // control the order of operation needed to compute the size of the list. When |
| // set to SizeOrder::N, the list's size will not be maintained and there will be |
| // no valid size() method to call. The only way to fetch the size of a list |
| // would be via |size_slow()|. Alternatively, a user may specify |
| // SizeOrder::Constant. In this case, the storage size of the list itself will |
| // grow by a size_t, and the size of the list will be maintained as elements are |
| // added and removed. |
| enum class SizeOrder { N, Constant }; |
| |
| } // namespace fbl |
| |
| namespace fbl::internal { |
| |
| // DirectEraseUtils |
| // |
| // A utility class used by HashTable to implement an O(n) or O(k) direct erase |
| // operation depending on whether or not the HashTable's bucket type supports |
| // O(k) erase. |
| template <typename ContainerType, typename Enable = void> |
| struct DirectEraseUtils; |
| |
| template <typename ContainerType> |
| struct DirectEraseUtils< |
| ContainerType, std::enable_if_t<ContainerType::SupportsConstantOrderErase == false, void>> { |
| using PtrTraits = typename ContainerType::PtrTraits; |
| using PtrType = typename PtrTraits::PtrType; |
| using ValueType = typename PtrTraits::ValueType; |
| |
| static PtrType erase(ContainerType& container, ValueType& obj) { |
| return container.erase_if([&obj](const ValueType& other) -> bool { return &obj == &other; }); |
| } |
| }; |
| |
| template <typename ContainerType> |
| struct DirectEraseUtils<ContainerType, |
| std::enable_if_t<ContainerType::SupportsConstantOrderErase == true, void>> { |
| using PtrTraits = typename ContainerType::PtrTraits; |
| using PtrType = typename PtrTraits::PtrType; |
| using ValueType = typename PtrTraits::ValueType; |
| |
| static PtrType erase(ContainerType& container, ValueType& obj) { return container.erase(obj); } |
| }; |
| |
| // KeyEraseUtils |
| // |
| // A utility class used by HashTable to implement an O(n) or O(k) erase-by-key |
| // operation depending on whether or not the HashTable's bucket type is |
| // associative or not. |
| template <typename ContainerType, typename KeyTraits, typename Enable = void> |
| struct KeyEraseUtils; |
| |
| template <typename ContainerType, typename KeyTraits> |
| struct KeyEraseUtils<ContainerType, KeyTraits, |
| std::enable_if_t<ContainerType::IsAssociative == false, void>> { |
| using PtrTraits = typename ContainerType::PtrTraits; |
| using PtrType = typename PtrTraits::PtrType; |
| using ValueType = typename PtrTraits::ValueType; |
| |
| template <typename KeyType> |
| static PtrType erase(ContainerType& container, const KeyType& key) { |
| return container.erase_if([key](const ValueType& other) -> bool { |
| return KeyTraits::EqualTo(key, KeyTraits::GetKey(other)); |
| }); |
| } |
| }; |
| |
| template <typename ContainerType, typename KeyTraits> |
| struct KeyEraseUtils<ContainerType, KeyTraits, |
| std::enable_if_t<ContainerType::IsAssociative == true, void>> { |
| using PtrTraits = typename ContainerType::PtrTraits; |
| using PtrType = typename PtrTraits::PtrType; |
| |
| template <typename KeyType> |
| static PtrType erase(ContainerType& container, const KeyType& key) { |
| return container.erase(key); |
| } |
| }; |
| |
| // Swaps two plain old data types with size no greater than 64 bits. |
| template <typename T, typename = std::enable_if_t<std::is_pod_v<T> && (sizeof(T) <= 8)>> |
| inline void Swap(T& a, T& b) noexcept { |
| T tmp = a; |
| a = b; |
| b = tmp; |
| } |
| |
| // Notes on container sentinels: |
| // |
| // Intrusive container implementations employ a slightly tricky pattern where |
| // sentinel values are used in place of nullptr in various places in the |
| // internal data structure in order to make some operations a bit easier. |
| // Generally speaking, a sentinel pointer is a pointer to a container with the |
| // sentinel bit set. It is cast and stored in the container's data structure as |
| // a pointer to an element which the container contains, even though it is |
| // actually a slightly damaged pointer to the container itself. |
| // |
| // An example of where this is used is in the doubly linked list implementation. |
| // The final element in the list holds the container's sentinel value instead of |
| // nullptr or a pointer to the head of the list. When an iterator hits the end |
| // of the list, it knows that it is at the end (because the sentinel bit is set) |
| // but can still get back to the list itself (by clearing the sentinel bit in |
| // the pointer) without needing to store an explicit pointer to the list itself. |
| // |
| // Care must be taken when using sentinel values. They are *not* valid pointers |
| // and must never be dereferenced, recovered into an managed representation, or |
| // returned to a user. In addition, it is essential that a legitimate pointer |
| // to a container never need to set the sentinel bit. Currently, bit 0 is being |
| // used because it should never be possible to have a proper container instance |
| // which is odd-aligned. |
| constexpr uintptr_t kContainerSentinelBit = 1U; |
| |
| // Create a sentinel pointer from a raw pointer, converting it to the specified |
| // type in the process. |
| template <typename T, typename U, typename = std::enable_if_t<std::is_pointer_v<T>>> |
| constexpr T make_sentinel(U* ptr) { |
| return reinterpret_cast<T>(reinterpret_cast<uintptr_t>(ptr) | kContainerSentinelBit); |
| } |
| |
| template <typename T, typename = std::enable_if_t<std::is_pointer_v<T>>> |
| constexpr T make_sentinel(decltype(nullptr)) { |
| return reinterpret_cast<T>(kContainerSentinelBit); |
| } |
| |
| // Turn a sentinel pointer back into a normal pointer, automatically |
| // re-interpreting its type in the process. |
| template <typename T, typename U, typename = std::enable_if_t<std::is_pointer_v<T>>> |
| constexpr T unmake_sentinel(U* sentinel) { |
| return reinterpret_cast<T>(reinterpret_cast<uintptr_t>(sentinel) & ~kContainerSentinelBit); |
| } |
| |
| // Test to see if a pointer is a sentinel pointer. |
| template <typename T> |
| constexpr bool is_sentinel_ptr(const T* ptr) { |
| return (reinterpret_cast<uintptr_t>(ptr) & kContainerSentinelBit) != 0; |
| } |
| |
| // Test to see if a pointer (which may be a sentinel) is valid. Valid in this |
| // context means that the pointer is not null, and is not a sentinel. |
| template <typename T> |
| constexpr bool valid_sentinel_ptr(const T* ptr) { |
| return ptr && !is_sentinel_ptr(ptr); |
| } |
| |
| DECLARE_HAS_MEMBER_FN(has_node_state, node_state); |
| |
| // SizeTracker is a partially specialized internal class used to track (or |
| // explicitly to not track) the size of Lists in the fbl:: containers. Its |
| // behavior and size depends on the SizeOrder template parameter passed to it. |
| // |
| // Please note that to use this class, containers must (sadly) derive from it, they |
| // cannot simply encapsulate it. The SizeOrder::N version of the tracker is |
| // nominally of 0 size, however 0 sized members of a struct/class are not allowed |
| // in C++. Attempting to put a 0 sized member into a class results in at least |
| // 1 byte of size impact, which changes the size of the entire object. |
| // |
| // 0 sized base classes, however, are totally fine. So, if we encapsulate a |
| // SizeTracker<SizeOrder::N>, then our container gets bigger for no reason, but |
| // if we derive from one, then our container stays the size that we expect it |
| // to. |
| // |
| // static_assert tests for this exist in the non-sized doubly and singly linked |
| // list tests. |
| template <SizeOrder> |
| class SizeTracker; |
| |
| template <> |
| class SizeTracker<SizeOrder::N> { |
| protected: |
| constexpr SizeTracker() = default; |
| ~SizeTracker() = default; |
| |
| // No copy, no move. |
| SizeTracker(const SizeTracker&) = delete; |
| SizeTracker& operator=(const SizeTracker&) = delete; |
| SizeTracker(SizeTracker&& other) = delete; |
| SizeTracker& operator=(SizeTracker&& other) = delete; |
| |
| // Inc, Dec, Reset, and swap operations are no-ops. There is no count |
| // accessor. Anyone who attempts to access count has made a mistake. |
| void IncSizeTracker(size_t) {} |
| void DecSizeTracker(size_t) {} |
| void ResetSizeTracker() {} |
| void SwapSizeTracker(SizeTracker&) {} |
| }; |
| |
| template <> |
| class SizeTracker<SizeOrder::Constant> { |
| protected: |
| constexpr SizeTracker() = default; |
| ~SizeTracker() = default; |
| |
| // No copy, no move. |
| SizeTracker(const SizeTracker&) = delete; |
| SizeTracker& operator=(const SizeTracker&) = delete; |
| SizeTracker(SizeTracker&& other) = delete; |
| SizeTracker& operator=(SizeTracker&& other) = delete; |
| |
| // Basic operations for manipulating the count storage. |
| void IncSizeTracker(size_t amt) { size_tracker_count_ += amt; } |
| void DecSizeTracker(size_t amt) { size_tracker_count_ -= amt; } |
| void ResetSizeTracker() { size_tracker_count_ = 0; } |
| void SwapSizeTracker(SizeTracker& other) { |
| std::swap(size_tracker_count_, other.size_tracker_count_); |
| } |
| size_t SizeTrackerCount() const { return size_tracker_count_; } |
| |
| private: |
| size_t size_tracker_count_ = 0; |
| }; |
| |
| } // namespace fbl::internal |
| |
| #endif // FBL_INTRUSIVE_CONTAINER_UTILS_H_ |