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:
- Demonstrate the simple case of an object that may exist in a single container.
- Show two ways to allow for membership in multiple containers simultaneously.
- Show how to take complete manual control of bookkeeping storage in your object in the case that advanced requirements need to be satisfied.
Single container membership using a mix-in.
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:
- A message is removed from the free list, or a new message is allocated if the free list is empty.
- The payload of the message is prepared.
- The message is placed into the pending queue.
- Finally, the worker thread is poked to tell it that it has messages waiting in the pending queue to process.
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.
Multiple container membership using a multiple mix-ins
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 FooObjs 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 FooObjs 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. FooObjs 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 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.
For raw pointers, this is a no-op. For unique_ptrs, this is illegal
and will fail to compile.
Multiple container membership using ContainableBaseClasses
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 FooObjs. 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
that 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.
Avoid mixing ContainableBaseClasses with default mix-ins
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 a 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>> { /* ... */ };
Container membership using explicit nodes and custom traits
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 that might justify the use of explicit nodes and custom traits in order to control container membership for your object.
- Your object must have a C++ standard layout and therefore cannot inherit from any of the mix-ins.
- You must have precise control of where in your object the node storage exists, and cannot have it end up in the storage allocated by the compiler for base classes.
- Your object is part of a complicated class hierarchy, where different levels of the hierarchy each need to be containable in different containers. Use of the mix-in helpers at the various levels would produce ambiguity and conflicts because of inheritance.
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 that hold the actual bookkeeping used by the container's data structure. In order to make use of them, you will need to:
- Add the appropriate instances of the node state types to your object.
- Define a trait class, which will be used by containers in order access the bookkeeping.
- Define a container type, specifying the appropriate trait class to link the container type to the bookkeeping in your class it is supposed to make use of.
Here is an example of an object that 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>;
};
Adding the node state bookkeeping
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 that can be used by lists to track their objects using raw
pointers, while bar_list_node_ is a node state object that can be used by
lists to track their objects using fbl::RefPtr<>s. It is best practice to
make these node state objects private members of your class.
Defining node state trait classes
These lines declare two "trait" classes 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;
Defining container type and specifying the node state storage they should use
Finally, you will need to define the container types that may be used with your object and make those types available to the users of your object. In this example, these are the lines that 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 that 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);