本部分将展示一个正在使用的入侵式容器的简单示例,并花一点时间讨论一些基本操作的细节。虽然本指南的后续部分将详细介绍这些概念以及其他许多概念,但本部分将对以下内容进行基本演示:
- 指针类型,以及如何使用它们来控制对象的生命周期。
- 可包含的“mix-ins”以及如何使用它们来允许对象存在于容器中。
- 如何迭代
fbl::
干扰性容器中的元素。 - 如何从
fbl::
侵扰性容器中移除元素。 - 从
fbl::
入侵性容器设置 build 依赖项。
简单示例
我们先来看一个简单的示例。在此示例中,系统会定义一个对象,该对象可存在于双重关联列表中,并使用 std::unique_ptr<>
进行跟踪。这些对象的列表如下:
- 已填充
- 进行迭代以输出对象的子集
- 进行迭代以移除一部分对象
- 已明确清理
#include <stdint.h>
#include <fbl/intrusive_double_list.h>
// An object that holds an immutable int and can exist on a doubly linked list
// managed using a std::unique_ptr
class MyObject : public fbl::DoublyLinkedListable<std::unique_ptr<MyObject>> {
public:
explicit MyObject(int val) : val_(val) {}
int val() const { return val_; }
private:
const int val_;
};
extern void TakeThisObjectFromMe(std::unique_ptr<MyObject>);
void DoThings() {
fbl::DoublyLinkedList<std::unique_ptr<MyObject>> list;
// Add 100 random integers to our list.
for (uint32_t i = 0; i < 100; ++i) {
list.push_back(std::make_unique<MyObject>(rand()));
}
// print out any members of the list that are even
for (const auto& obj : list) {
if (!(obj.val() % 2)) {
printf("Even Object %d\n", obj.val());
}
}
// Remove any objects that are divisible by 7 and give them to someone else.
for (auto iter = list.begin(); iter != list.end(); ) {
auto consider = iter++;
if (!(consider->val() % 7)) {
TakeThisObjectFromMe(list.erase(consider));
}
}
// Destroy the rest of the object by forcing the list to release its unique
// references to the objects. We could also simply let the list leave the
// scope of the function, which would do the same.
list.clear();
}
指针类型
此处首先要注意的一点是,std::
容器与 fbl::
容器之间的一个重要区别是,fbl::
容器始终使用指针跟踪对象。具体而言,它们是使用一组明确支持的指针类型进行跟踪。如果定义了 fbl::
列表的类型,它就会被定义为指向某个对象类型的特定指针类型的列表。在此示例中,选择了 std::unique_ptr<>
,这意味着对象的唯一引用可以存储在本地,也可以由列表保留,但不能同时由这两个引用保留。fbl::
容器目前支持 3 种不同的指针类型:
T*
:一种没有托管 RAII 语义的原始指针类型。std::unique_ptr<T, Deleter>
:标准的唯一指针类型,使用自定义删除器或默认删除器。fbl::RefPtr<T>
:fbl::
干扰性引用指针。从根本上来讲,是fbl::
的干扰性std::shared_ptr<T>
版本。
必须通过容器类型的第一个模板参数告知所有容器它们存储的对象类型以及使用哪种指针管理生命周期。使用代管式指针类型时,容器在将对象添加到容器中时,始终拥有引用的所有权,并在对象从容器中移除时返还该引用的所有权。此规则的例外情况是 clear()
,它会丢弃所有引用。
“原始”指针没有特殊的所有权语义,这意味着,完全由用户负责确保对象在容器中保持活动状态,以及在从容器中移除或清除时正确地清理对象。
可列表/可包含的 Mix-in 类
如果对象必须在某处存储下一个/上一个指针,那么此节点状态位于何处?列表如何找到它?实际上,控制此行为有多种方法,但此示例演示了最简单的方法。这派生自 DoublyLinkedList
的 Listable
混入帮助程序。与列表本身一样,您需要通过第一个模板参数告知混入对象类型和指针类型。这些类型需要与为列表定义本身指定的类型匹配。默认情况下,列表将查找该对象派生的 Listable
混合实例,以查找用于簿记的节点状态。所有这些都是在编译时完成的,在对象中查找节点状态不会产生任何运行时开销。
迭代
fbl::
容器支持基于范围的 for 循环迭代,以及更经典的 begin()/end() 迭代方式。与 std::
容器一样,使用基于范围的 进行枚举时,系统将返回对对象的 l 值引用。请务必注意,在 for 循环中应使用 auto&
或 const auto&
(甚至是 MyObject&
),而不只是 auto
,否则您可能会意外触发对象的复制构造函数。
fbl::
容器迭代器还支持 ++
运算符的标准前缀和后缀形式,您可以看到,在迭代时,您可以使用这些运算符选择性地从列表中移除元素。此示例中使用了修复后形式,因此 consider
将成为可以选择要移除的元素,而 iter
则变为指向列表中需要考虑的下一个元素的指针。
当元素位于列表中时,迭代器充当指向这些元素的非托管指针。可以通过所有标准方式访问底层对象,即使用 ->
运算符或使用 (*iter).val()
样式。甚至可以通过说 &(*iter)
将原始指针提取到该对象。应谨慎使用迭代器,因为它们在功能上是指向对象的原始指针。不建议您将它们存储任何时间,尤其是在使用新式代管指针来控制对象的生命周期时。
移除元素
在此示例中,移除元素后,系统将使用基于迭代器的擦除操作将其移除。擦除操作的结果将是对列表所用指针类型的 r 值引用。引用可能已被收回并保留在本地指针实例中,但在这种情况下,它直接移至某个外部函数的调用中,将对象的唯一所有权从列表中转移到进程中的外部函数。
clear()
是从容器中移除元素的另一种方式,但它会丢弃所有元素引用,可能会销毁它们在进程中指向的对象。
设置 build 依赖项
为了使用 fbl::
容器,用户必须确保为其要使用的容器添加适当的头文件,并在项目的 BUILD.gn
文件中包含 fbl
库的依赖项。
每种容器类型必需的包含文件包括:
容器类型 | 包含语句 |
---|---|
fbl::SinglyLinkedList<> |
#include <fbl/intrusive_single_list.h> |
fbl::DoublyLinkedList<> |
#include <fbl/intrusive_double_list.h> |
fbl::WAVLTree<> |
#include <fbl/intrusive_wavl_tree.h> |
fbl::HashTable<> |
#include <fbl/intrusive_hash_table.h> |
用户还必须将库 //zircon/system/ulib/fbl
添加到其项目的 BUILD.gn
文件的 deps
或 public_deps
部分。如果用户正在编写可执行文件,或者仅在库的私有部分使用 fbl
,则该引用属于 deps
部分。如果 fbl
是在用户库的公开头文件中的任何位置使用,则应改用 public_deps
。