As noted in the introduction, for objects to exist in an intrusive container, users must explicitly add storage for the container bookkeeping to the object itself. This section will show you the details of how you can control which container(s) your object are allowed to exist in. It will:
Typically, choosing to use the default mix-in for a container is the easiest and proper choice. You have already seen what this looks like for the doubly linked list in the Getting Started section of this guide. Here are simple examples of all the default mix-ins.
class FooObj : public fbl::SinglyLinkedListable<FooObj*> { /* ... */ }; using StackOfFoos = fbl::SinglyLinkedList<FooObj*>; class FooObj : public fbl::DoublyLinkedListable<FooObj*> { /* ... */ }; using QueueOfFoos = fbl::DoublyLinkedList<FooObj*>; class FooObj : public fbl::WAVLTreeContainable<FooObj*> { /* ... */ }; using MapOfIntToFoos = fbl::WAVLTree<int, FooObj*>; // Hash tables default to singly linked list buckets class FooObj : public fbl::SinglyLinkedListable<FooObj*> { /* ... */ }; using SLLHashOfIntToFoos = fbl::HashTable<int, FooObj*>; // But you can use a doubly linked list as well. class FooObj : public fbl::DoublyLinkedListable<FooObj*> { /* ... */ }; using DLLHashOfIntToFoos = fbl::HashTable<int, FooObj*, fbl::DoublyLinkedList<FooObj*>>;
In each of these examples, a raw pointer to a FooObj
was used. If you manage your object using either std::unique_ptr
or fbl::RefPtr
semantics, they may be substituted as needed provided that the pointer type in the mix in matches the pointer type of the container.
Each of these objects can exist in a single type of a container, but this does not bind them to a single instance of a container. For example:
class Message : public fbl::DoublyLinkedListable<std::unique_ptr<Message>> { /* ... */ }; class TransmitQueue { public: // ... void SendMessage(Payload payload) { // Get a free message to send, or allocate if there are no free messages. std::unique_ptr<Message> tx; if (fbl::AutoLock lock(&lock_); free_messages_.is_empty()) { tx = std::make_unique<Message>(); } else { tx = free_messages_.pop_front(); } tx.PrepareMessage(std::move(payload)); { fbl::AutoLock lock(&lock_); tx_pending_messages_.push_back(std::move(tx)); } SignalTxThread(); } // ... private: fbl::Mutex lock_; fbl::DoublyLinkedList<std::unique_ptr<Message>> free_messages_ TA_GUARDED(lock_); fbl::DoublyLinkedList<std::unique_ptr<Message>> tx_pending_messages_ TA_GUARDED(lock_); };
Message
objects in this example can exist in any instance of a DoublyLinkedList
of unique pointers to Messages
, but only in one of the instances at a time. In this example, a free-list of messages is maintained. When the time comes to send a message:
When the worker is finished, it will move the Message
object back to the free list where it may be re-used, however that code has not been shown here.
What if an object needs to exist in multiple containers at the same time? If the container types themselves are different, then it is possible to simply use multiple default mix-ins. Simply add the mix-ins to the list of base classes for your object. For example:
class FooObj : public fbl::RefCounted<FooObj>, public fbl::DoublyLinkedListable<fbl::RefPtr<FooObj>>, public fbl::WAVLTreeContainable<fbl::RefPtr<FooObj>> { /* ... */ }; using UniqueId = uint64_t; static fbl::WAVLTree<UniqueId, fbl::RefPtr<FooObj>> g_active_foos; static fbl::DoublyLinkedList<fbl::RefPtr<FooObj>> g_process_pending; zx_status_t ProcessFooWithId(UniqueId id) { if (auto iter = g_active_foos.find(unique_id); iter.IsValid()) { if ((*iter).DoublyLinkedListable<fbl::RefPtr<FooObj>>::InContainer()) { return ZX_ERR_BAD_STATE; } g_process_pending.push_back(iter.CopyPointer()); PokeWorkerThread(); } else { return ZX_ERR_NOT_FOUND; } return ZX_OK; }
In this example, a tree of all the active FooObj
s in the system is being maintained. The objects in the tree are indexed by their UniqueId
(which is just a big integer in this case). There is also a queue of FooObj
s waiting to be processed. The ProcessFooWithId
function attempts to find the Foo with the specified ID and put a reference to it in the g_process_pending
queue.
Note that when an object is found in the set of active objects, it is checked to make sure it is not already in the pending queue before attempting to append it to the pending queue. FooObj
s can exist in both the pending queue and the active set at the same time, but they cannot exist in the pending queue twice. Attempting to put an object which into an instance of ContainerTypeA
when the object is already in an instance of ContainerTypeA
(either the same instance or a different one) will trigger a ZX_DEBUG_ASSERT if asserts are enabled, or end up corrupting the program state otherwise. It is very important to make sure that this does not happen. Frequently, invariants in a program ensure that this can never happen, but if your program lacks such invariants, remember to check your object to see if it is in a container already or not.
See the section on testing for container membership for various ways this can be done. Also note how ugly testing for membership is in this example. There are nicer ways to do this as you will see in the next sub-section describing the use of ContainableBaseClasses
.
One last thing to point out about this example. When it is time to put a FooObj
into the pending queue, a new instance of a fbl::RefPtr
to the object instance needs to be provided to push_back
. This can be obtained by calling the CopyPointer
method of the iterator, which will invoke the copy constructor of the underlying pointer type giving us a new reference to the object which can be used. For raw pointers, this is a no-op. For unique_ptrs, this is illegal and will fail to compile.
What should you do if your object needs to exist in multiple containers of the same fundamental type at the same time? The easiest thing that can be done is to make use of fbl::ContainableBaseClasses
, along with type tags which can be used to identify the different containers your object can exist in. Here is a re-implementation of the previous example, but this time with the addition of another list that the objects can exist in.
struct ActiveTag {}; struct ProcessPendingTag {}; struct OtherListTag {}; class FooObj : public fbl::RefCounted<FooObj>, public fbl::ContainableBaseClasses< fbl::TaggedDoublyLinkedListable<fbl::RefPtr<FooObj>, ProcessPendingTag>, fbl::TaggedDoublyLinkedListable<fbl::RefPtr<FooObj>, OtherListTag>, fbl::TaggedWAVLTreeContainable<fbl::RefPtr<FooObj>, ActiveTag>> { /* ... */ }; using UniqueId = uint64_t; static fbl::TaggedWAVLTree<UniqueId, fbl::RefPtr<FooObj>, ActiveTag> g_active_foos; static fbl::TaggedDoublyLinkedList<fbl::RefPtr<FooObj>, OtherListTag> g_process_pending_foos; zx_status_t ProcessFooWithId(UniqueId id) { if (auto iter = g_active_foos.find(unique_id); iter.IsValid()) { if (fbl::InContainer<ProcessPendingTag>(*iter)) { return ZX_ERR_BAD_STATE; } iter->SetPriority(fbl::InContainer<OtherTag>(*iter) ? 20 : 10); g_process_pending_foos.push_back(iter.CopyPointer()); } else { return ZX_ERR_NOT_FOUND; } }
The example starts by defining 3 different types (“tags”) that will be used to identify the different containers to be used concurrently with FooObj
s. These types don't actually do anything, they are simply empty structures. You will never instantiate any of them. Their purpose is only to be a unique type which the compiler can use to understand which list type is paired with which node state. In this example, the node state held by the TaggedDoublyLinkedListable
with the ProcessPendingTag
is the node state used by the g_process_pending_foos
list.
Note that this can make the InContainer
test easier to read as well. Using tags allows us to invoke the stand-alone fbl::InContainer<>
function, passing a const&
to an object, and specifying which type of container the object should be tested for membership in using the tag.
ContainableBaseClasses
works with any combination of containable mix-ins and allows objects to exist in an arbitrary number of container types, provided that each container type has a unique type to serve as its tag.
While technically ContainableBaseClasses
can be used in combination with the default mix-ins, doing so is not considered best practice and should be avoided.
While there is clearly some extra typing involved in starting to use tags and ContainableBaseClases
to manage your object's container membership, once you have started to do so it is easy to extend the pattern. The consistency of always using tags with an given object (vs. sometimes using them and sometimes not) will help with both readability and maintainability, particularly when it comes to testing for container membership, and when understanding which container type definitions use which piece of node storage in an object.
So, don't do this:
namespace FooTags { struct SortByBase {}; struct SortBySize {}; } class Foo : public DoublyLinkedListable<Foo*>, // For the pending processing queue public fbl::ContainableBaseClasses< public TaggedWAVLTreeContainable<Foo*, FooTags::SortByBase>, public TaggedWAVLTreeContainable<Foo*, FooTags::SortBySize>> { /* ... */ };
Instead do something more like this:
namespace FooTags { struct PendingProcessing {}; struct SortByBase {}; struct SortBySize {}; } class Foo : public fbl::ContainableBaseClasses< public TaggedDoublyLinkedListable<Foo*, FooTags::PendingProcessing>, public TaggedWAVLTreeContainable<Foo*, FooTags::SortByBase>, public TaggedWAVLTreeContainable<Foo*, FooTags::SortBySize>> { /* ... */ };
Finally, there is one last option for controlling container membership for objects. This option is the lowest level option, and the most work to write, understand, and maintain. It only should be used in situations where specific technical requirements force you to do so. Here are some of the reasons which might justify the use of explicit nodes and custom traits in order to control container membership for your object.
Every basic container type has a NodeState
type associated with it. Not surprisingly, their names are:
SinglyLinkedListNodeState<PtrType>
DoublyLinkedListNodeState<PtrType>
WAVLTreeNodeState<PtrType>
These are the structures which hold the actual bookkeeping used by the container's data structure. In order to make use of them, you will need to:
Here is an example of an object which can exist in two doubly linked lists using explicit nodes and custom traits:
class Obj { public: // Obj impl here private: struct FooListTraits { static auto& node_state(Obj& obj) { return obj.foo_list_node_; } }; struct BarListTraits { static auto& node_state(Obj& obj) { return obj.bar_list_node_; } }; friend struct FooListTraits; friend struct BarListTraits; fbl::DoublyLinkedListNodeState<Obj*> foo_list_node_; fbl::DoublyLinkedListNodeState<fbl::RefPtr<Obj>> bar_list_node_; public: using FooList = fbl::DoublyLinkedListCustomTraits<Obj*, FooListTraits>; using BarList = fbl::DoublyLinkedListCustomTraits<fbl::RefPtr<Obj>, BarListTraits>; };
These lines declare the storage required for Obj
to exist in two different doubly linked lists at the same time.
fbl::DoublyLinkedListNodeState<Obj*> foo_list_node_; fbl::DoublyLinkedListNodeState<fbl::RefPtr<Obj>> bar_list_node_;
The pointer type used for tracking needs to be specified for the node and needs to match that of the container. In this example, foo_list_node_
is a node state object which can be used by lists which track their objects using raw pointers, while bar_list_node_
is a node state object which can be used by lists which track their objects using fbl::RefPtr<>
s. It is best practice to make these node state objects private members of your class.
These lines declare two “trait” classes which are used to tell a container type how to access their associated node bookkeeping.
struct FooListTraits { static auto& node_state(Obj& obj) { return obj.foo_list_node_; } }; struct BarListTraits { static auto& node_state(Obj& obj) { return obj.bar_list_node_; } };
These classes have no member variable or methods, merely a single static method named node_state
which takes a mutable reference to your object type, and returns a mutable reference to the proper node state bookkeeping instance in your object. These classes will never be instantiated, they only are used to define, at compile time, the relationship of a type of a container to the proper unit of bookkeeping storage in the object to be contained.
Note that, in keeping with best practice, our node state instances are private members of Obj
. It is also best practice to make these trait classes private, but because of the private nature of the node instances, you will need to also declare the trait classes as friends of your object. In this example, these lines take care of that task.
friend struct FooListTraits; friend struct BarListTraits;
Finally, you will need to define the container types which may be used with your object and make those types available to the users of your object. In this example, these are the lines which take care of that task.
public: using FooList = fbl::DoublyLinkedListCustomTraits<Obj*, FooListTraits>; using BarList = fbl::DoublyLinkedListCustomTraits<fbl::RefPtr<Obj>, BarListTraits>;
Note that we have used one of the specialized using
aliases for DoublyLinkedList
, specifically DoublyLinkedListCustomTraits
. This alias simple re-arranges the ordering of template parameters so that the second parameter passed to the list type defines the trait class which will be used by the list to find the appropriate node state bookkeeping storage.
Both the trait classes and the node state storage are private members of Obj
, so it is important that there be a public definition of the container types available to the user of the object. This will allow them to say things like the following.
Obj obj_instance; Obj::FooList list; list.push_back(&obj_instance);