如简介中所述,对于侵入式容器中存在的对象,用户必须明确将用于容器簿记的存储空间添加到对象本身。本部分将详细介绍如何控制允许对象存在于哪些容器中。此功能将会:
- 演示对象可能存在于单个容器中的简单案例。
- 展示同时允许在多个容器中拥有成员资格的两种方法。
- 介绍如何在需要满足高级要求时完全手动控制对象中的簿记存储空间。
使用混入的单一容器成员资格。
通常,选择为容器使用默认混入是最简单且正确的选择。您已经在本指南的使用入门部分看到了双重链接列表的样子。以下是所有默认混音项的简单示例。
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*>>;
每个示例中都使用了指向 FooObj
的原始指针。如果您使用 std::unique_ptr
或 fbl::RefPtr
语义管理对象,则可以根据需要替换它们,前提是混合中的指针类型与容器的指针类型匹配。
这些对象中的每一个都可以存在于容器的单个类型中,但这不会将它们绑定到容器的单个实例。例如:
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
对象可以存在于由指向 Messages
的唯一指针的 DoublyLinkedList
的任何实例中,但一次只能存在于一个实例中。在此示例中,保留了一份消息列表。
发送消息时:
- 如果空闲列表为空,则系统会从中移除消息,或者分配新消息。
- 消息的载荷已准备就绪。
- 系统会将该邮件置于待处理队列中。
- 最后,系统会对工作器线程进行轮询,告知它有消息在待处理队列中等待处理。
当 worker 完成操作后,它会将 Message
对象移回空闲列表中,并在该列表中重复使用,但此处未显示该代码。
使用多个混合的多种容器成员资格
如果某个对象需要同时存在于多个容器中,该怎么办?如果容器类型本身不同,则可以直接使用多个默认混音。只需将混入项添加到对象的基类列表中即可。例如:
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;
}
在此示例中,我们正在维护系统中所有活跃 FooObj
的树。树中的对象按其 UniqueId
(在本例中只是一个大整数)编入索引。此外,还有一个等待处理的 FooObj
队列。ProcessFooWithId
函数会尝试查找具有指定 ID 的 Foo,并在 g_process_pending
队列中对其引用。
请注意,在活动对象集中发现某个对象时,系统会检查该对象,以确保它尚未在待处理队列中,然后才能尝试将其附加到待处理队列。FooObj
可以同时存在于待处理队列和活动集中,但不能在待处理队列中存在两次。如果对象已位于 ContainerTypeA
的实例(同一实例或不同实例)中,则尝试在 ContainerTypeA
的实例中放入该对象将触发 ZX_DEBUG_ASSERT(如果断言已启用),否则最终会破坏程序状态。确保不会发生这种情况非常重要。程序中的不变性通常可以确保这种情况永远不会发生,但如果您的程序没有这种不变性,请务必检查您的对象,查看其是否已在容器中。
如需了解执行此操作的各种方法,请参阅有关测试容器成员资格的部分。还要注意,此示例中的成员资格是多么糟糕。还有更好的方式可以做到这一点,下一部分将为您介绍 ContainableBaseClasses
的用法。
关于此示例,最后一点要强调一下。当需要将 FooObj
放入待处理队列时,需要向 push_back
提供对象实例的 fbl::RefPtr
新实例。这可以通过调用迭代器的 CopyPointer
方法来获得,该方法将调用底层指针类型的复制构造函数,为我们提供对象的新引用。对于原始指针,这是空操作。对于 unique_ptrs,此操作是非法的,并且无法编译。
使用 ContainableBaseClasses 实现多容器成员资格
如果您的对象需要同时存在于同一基本类型的多个容器中,该怎么办?最简单的方法是使用 fbl::ContainableBaseClasses
以及类型标记,这些标记可用于识别对象中可以存在的不同容器。下面是对上一个示例的重新实现,但这次添加了另一个可以存在对象的列表。
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;
}
}
该示例首先定义了 3 种不同的类型(“代码”),这些类型将用于标识要与 FooObj
同时使用的不同容器。这些类型实际上没有任何作用,它们只是空结构。您绝不能实例化其中任何文件。它们的用途只是成为一种唯一类型,编译器可以使用它来了解哪种列表类型与哪种节点状态配对。在本例中,TaggedDoublyLinkedListable
持有的具有 ProcessPendingTag
的节点状态是 g_process_pending_foos
列表使用的节点状态。
请注意,这样也可以使 InContainer
测试更易于阅读。利用标记,我们可以调用独立的 fbl::InContainer<>
函数,将 const&
传递给对象,并指定应使用标记测试对象所属的容器类型。
ContainableBaseClasses
可与可包含的混合内容的任意组合搭配使用,并允许对象存在于任意数量的容器类型中,但前提是每个容器类型都有一个唯一的类型用作其标记。
避免将 ContainableBaseClasses 与默认 mix-in 混用
虽然从技术层面来讲,ContainableBaseClasses
可以与默认混音结合使用,但这并非最佳实践,应避免这样做。
虽然显然,如果开始使用标记和 ContainableBaseClases
来管理对象的容器成员资格,需要执行一些额外的输入操作,但是一旦您开始执行这些操作,就可以轻松地扩展模式。始终将标记用于给定对象(与有时使用标记,有时不使用)的一致性有助于提高可读性和可维护性,尤其是在测试容器成员资格以及了解哪些容器类型定义使用对象中的节点存储空间时。
因此,请勿执行以下操作:
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>> { /* ... */ };
请改为执行如下操作:
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>> { /* ... */ };
使用显式节点和自定义特征的容器成员资格
最后,还有最后一个选项可用于控制对象的容器成员资格。此选项是最低级别的选项,编写、理解和维护方面的工作量也最大。应仅在特定技术要求强制您这样做的情况下使用。下面列出了使用显式节点和自定义特征来控制对象的容器成员资格的一些原因。
- 您的对象必须具有 C++ 标准布局,因此不能从任何混音对象继承。
- 您必须精确控制节点存储空间在对象中的位置,并且不能将其最终放入编译器为基类分配的存储空间中。
- 您的对象是复杂的类层次结构的一部分,层次结构的不同层级各自需要包含在不同的容器中。在不同级别使用混入帮助程序会产生歧义和冲突,因为继承关系。
每个基本容器类型都有一个与之关联的 NodeState
类型。不出意料的是,它们的名称是:
SinglyLinkedListNodeState<PtrType>
DoublyLinkedListNodeState<PtrType>
WAVLTreeNodeState<PtrType>
这些是存放容器数据结构实际使用账簿的结构。要使用它们,您需要:
以下示例展示的对象可以存在于两个使用显式节点和自定义特征的双重关联列表中:
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>;
};
添加节点状态簿记
这些行声明 Obj
同时存在于两个不同的双重链接列表中所需的存储空间。
fbl::DoublyLinkedListNodeState<Obj*> foo_list_node_;
fbl::DoublyLinkedListNodeState<fbl::RefPtr<Obj>> bar_list_node_;
需为节点指定用于跟踪的指针类型,且该类型必须与容器的类型一致。在此示例中,foo_list_node_
是一个节点状态对象,列表可以使用原始指针跟踪其对象,而 bar_list_node_
是一个节点状态对象,列表可以使用 fbl::RefPtr<>
跟踪其对象。最佳做法是将这些节点状态对象设为类的私有成员。
定义节点状态特征类
这行代码声明了两个“trait”类,用于告知容器类型如何访问其关联的节点簿记。
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_;
}
};
这些类没有成员变量或方法,只有一个名为 node_state
的静态方法,该方法接受对对象类型的可变引用,并返回对对象中相应节点状态簿记实例的可变引用。这些类绝不会实例化,而仅用于在编译时定义容器类型与要包含的对象中相应记账存储空间单位之间的关系。
请注意,根据最佳实践,我们的节点状态实例是 Obj
的私有成员。最好将这些特征类设为私有,但由于节点实例的私密性,您还需要将 trait 类声明为对象的好友。在此示例中,这些代码行负责处理该任务。
friend struct FooListTraits;
friend struct BarListTraits;
定义容器类型并指定应使用的节点状态存储空间
最后,您需要定义可用于您的对象的容器类型,并将这些类型提供给该对象的用户。在此示例中,这些是用于处理该任务的行。
public:
using FooList = fbl::DoublyLinkedListCustomTraits<Obj*, FooListTraits>;
using BarList = fbl::DoublyLinkedListCustomTraits<fbl::RefPtr<Obj>, BarListTraits>;
请注意,我们为 DoublyLinkedList
使用了其中一个专用 using
别名,特别是 DoublyLinkedListCustomTraits
。此别名会简单地重新排列模板参数的顺序,以便传递给列表类型的第二个参数定义将由列表用于查找相应节点状态簿记存储空间的特征类。
trait 类和节点状态存储空间都是 Obj
的私有成员,因此请务必有可供对象用户使用的容器类型的公共定义。这样他们就可以说出如下内容。
Obj obj_instance;
Obj::FooList list;
list.push_back(&obj_instance);