高级场景

默认情况下，fbl:: 中侵入式容器的大多数行为都旨在在编译时提供尽可能高的安全性，通常是禁止使用容易在编译时导致错误的使用模式。

不过，在某些高级场景中，用户可能会选择绕过这些编译时安全机制，以便故意允许某些行为。无论您何时选择使用上述某个选项，请务必仔细考虑关闭安全功能的影响，并确保以安全的方式使用该功能。

本指南的这一部分将介绍如何执行以下操作：

1. 使用 fbl::NodeOptions 选择启用高级行为
2. 控制位于容器中时对象的复制/移动性。
3. 允许 unique_ptr 跟踪的对象包含在多种容器类型中
4. 在 O(1) 时间内清除原始指针容器
5. 从容器中移除未引用容器的对象

使用 fbl::NodeOptions 控制高级选项

为了在编译时控制某些高级选项，节点状态对象（及其关联的混合输入）可以采用位标志样式常量，该常量可用于更改特定行为。您可以使用 | 运算符来组合选项。默认情况下，选项是 NodeState 或 Listable/Containable 类型的第二个模板参数，以及 TaggedListable/TaggedContainable 混音的第三个模板参数。这些选项始终默认为 fbl::NodeOptions::None。语法如下所示：

class SimpleObject :
  public fbl::DoublyLinkedListable<SimpleObject*, fbl::NodeOption::OptionFoo> { /* ... */ };

class MoreComplexObject :
  public fbl::ContainableBaseClasses<
    fbl::TaggedSinglyLinkedListable<MoreComplex*, Tag1, fbl::NodeOption::OptionBar>,
    fbl::TaggedWAVLTreeContainable <MoreComplex*, Tag2,
                                    fbl::NodeOption::OptionA | fbl::NodeOption::OptionB>> {
  // ...
};

class ExplicitNodesObject {
 public:
  // ...

 private:
  // ...
  static constexpr fbl::NodeOptions kOptions = fbl::NodeOption::OptionX |
                                               fbl::NodeOption::OptionY |
                                               fbl::NodeOption::OptionZ;
  fbl::WAVLTreeNodeState<ExplicitNodesObject*, kOptions> wavl_node_state_;
};

当对象位于容器中时，控制其复制/移动行为

不允许对对象位于容器中的节点状态进行复制或移动。请注意以下几点：

fbl::DoublyLinkedList<Obj*> the_list;
ASSERT(!the_list.is_empty());

Obj the_obj;
the_list.insert_after(the_list.begin());

Obj another_obj{the_obj};

Obj yet_another_object;
the_obj = yet_another_object;

列表中第一个节点之后存在 the_obj。如果允许通过默认复制构造函数将节点状态复制到 another_obj 中，则会出现两个对象，其中包含两个簿记副本。another_obj 会错误地认为它位于容器中，并且现在会在销毁时尝试断言。

更糟糕的是，如果您尝试通过调用 the_list.erase(another_object) 移除对象，则会尝试从处于不连贯状态的容器中清除对象。在本例中，另一个对象的上一个和下一个指针指向列表中的第一个对象，在示例开始时曾经位于 begin() 之后的对象，但 *begin() 的下一个指针指向 the_obj，同样地指向序列中下一个对象的上一个指针。虽然具体行为因容器类型和清空的具体实现而异，但会出现的行为是未定义的行为，无法顺利结束。

最后，当示例代码将新构造的 yet_another_object 分配给 the_obj 时，如果要从 yet_another_object 复制节点状态数据，the_obj 会突然认为它不在列表中，即使其两侧的对象持有指向它的指针。

无论您以何种方式查看，允许复制节点状态数据都会损坏容器的结构，并且无法阻止容器结构发生，大多数移动操作的定义也是如此。

为防止出现此类错误，fbl:: 节点状态对象的默认行为是禁止复制构造/分配以及移动构造/分配。任何尝试调用复制/移动构造函数/赋值运算符都会导致 static_assert 和编译失败。

对象不在容器中时该怎么办？那就不允许复制/移动吗？答案是肯定的，但为了安全起见，只有当代码作者已选择接受这种行为时，我们才会认为允许这么做。如需选择启用，您可以使用以下 NodeOptions 及其混合或节点存储类型。

• fbl::NodeOptions::AllowCopy
• fbl::NodeOptions::AllowMove
• fbl::NodeOptions::AllowCopyAndMove

设置 AllowCopy 将允许进行复制（l 值）构造和赋值，而设置 AllowMove 将允许移动（r 值）构造和赋值。AllowCopyAndMove 是将这两者结合到一起的简写形式。

在操作期间，节点状态对象将 ZX_DEBUG_ASSERT，表示源对象不在用于构造的容器中，并且在分配期间，源对象和目标对象在容器中均不存在。无论是否启用了 ZX_DEBUG_ASERT，源对象和目标对象的状态都永远不会修改。

例如：

struct Point : fbl::DoublyLinkedListable<std::unique_ptr<Point>,
                                         fbl::NodeOptions::AllowCopy> {
  float x, y;
};

fbl::DoublyLinkedList<std::unique_ptr<Point>> all_points;

void AddCopy(const Point& pt) {
  // If pt is in a list, this will assert. If asserts are off, pt will remain
  // where it is and new_pt will not start life in a container.
  auto new_pt = std::make_unique<Point>(pt);
  all_points.push_back(std::move(new_pt));
}

那么，如果您要允许复制或移动某个对象（即使它位于容器中），该怎么办？例如，如果您想使用复制构造函数克隆点列表，该怎么办？用户也可以通过传递以下各种适当的组合项来选择此行为：

• fbl::NodeOptions::AllowCopyFromContainer
• fbl::NodeOptions::AllowMoveFromContainer
• fbl::NodeOptions::AllowCopyAndMoveFromContainer

上述行为保持不变；节点状态永远不会更改。新对象将从任何容器外部开始，并且源对象将保留在任何位置。此选项的 FromContainer 版本与非 FromContainer 版本的唯一区别在于 FromContainer 版本绝不会断言。因此，您可以使用以下命令克隆点列表。

struct Point : fbl::DoublyLinkedListable<std::unique_ptr<Point>,
                                         fbl::NodeOptions::AllowCopyFromContainer> {
  float x, y;
};

using PointList = fbl::DoublyLinkedList<std::unique_ptr<Point>>;

PointList CloneList(const PointList& list) {
  PointList ret;
  for (const auto& point : list) {
    ret.push_back(std::make_unique<Point>(point));
  }
  return ret;
}

允许 unique_ptr 跟踪的对象存在于多个容器中

通常，如果定义可同时存在于多个容器中的对象，同时使用 unique_ptr 语义跟踪容器中这些对象，则是错误的。从理论上讲，两个不同的容器应该不可能同时跟踪同一对象，每个容器使用 unique_ptr 之类的元素，因为这样会违反指针的唯一性。

为了防止出现任何错误，ContainableBaseClasses 不允许对任何指定的混入项使用 std::unique_ptr 指针类型，除非可包含基类的列表的长度正好为 1。

struct Tag1 {};
struct Tag2 {};

// This is legal
class Obj : public fbl::ContainableBaseClasses<
  fbl::TaggedSinglyLinkedListable<std::unique_ptr<Obj>, Tag1>> { /* ... */ };

// This is not
class Obj : public fbl::ContainableBaseClasses<
  fbl::TaggedSinglyLinkedListable<std::unique_ptr<Obj>, Tag1>,
  fbl::TaggedSinglyLinkedListable<std::unique_ptr<Obj>, Tag2>> { /* ... */ };

// Neither is this
class Obj : public fbl::ContainableBaseClasses<
  fbl::TaggedSinglyLinkedListable<std::unique_ptr<Obj>, Tag1>,
  fbl::TaggedSinglyLinkedListable<Obj*, Tag2>> { /* ... */ };

不过，可以存在于多个容器中的类型有合法用途，这些容器使用 std::unique_ptr 进行管理。

首先，您可能会遇到这样一种情况：一个对象可以存在于两种不同类型的数据结构中（可能是列表和一种树），但它们始终无法同时存在于同一数据结构中。如果结构的使用完全不相交，您可能需要放宽默认限制。

您可能想要允许这种情况的第二个原因是，您有一个对象的生命周期由容器使用 std::unique_ptr 跟踪，但您希望允许对象临时存在于容器中，以便更轻松地实现某种算法。可能需要将一组对象过滤到临时列表中，然后传递给将对过滤后的集合执行操作的函数。或者，可能需要将它们放入具有自定义排序/键的临时 WAVLTree 中，以检查重复项。

无论是什么原因，您都可以通过将 AllowMultiContainerUptr 选项传递给您使用的节点状态类型来允许此行为。以下示例展示了不相交的容器用例：

struct FreeObjTag {};
struct ActiveObjTag {};
class Obj : public fbl::ContainableBaseClasses<
  fbl::TaggedSinglyLinkedListable<std::unique_ptr<Obj>, FreeObjTag,
                                  fbl::NodeOptions::AllowMultiContainerUptr>,
  fbl::TaggedWAVLTreeContainable<std::unique_ptr<Obj>, ActiveObjTag,
                                 fbl::NodeOptions::AllowMultiContainerUptr>> {
 public:
  using FreeStack = fbl::TaggedSinglyLinkedList<std::unique_ptr<Obj>, FreeObjTag>;
  using ActiveSet = fbl::TaggedWAVLTree<UniqueId, std::unique_ptr<Obj>, ActiveObjTag>;

  // ...
  UniqueId GetKey() const { return unique_id_; }
  void AssignId(UniqueId id) {
    ZX_DEBUG_ASSERT(!fbl::InContainer<ActiveObjTag>(*this));
    unique_id_ = id;
  }
  // ...

 private:
  // ...
};

fbl::Mutex obj_lock_;
Obj::FreeStack free_objects_ TA_GUARDED(obj_lock_);
Obj::ActiveSet active_objects_ TA_GUARDED(obj_lock_);

zx_status_t ActivateObject(UniqueId id) {
  fbl::AutoLock lock(&obj_lock_);

  if (free_objects_.is_empty()) {
    return ZX_ERR_NO_MEMORY;
  }

  auto ptr = free_objects_.pop_front();
  ptr.AssignId(id);
  active_objects_.insert(std::move(ptr));
  return ZX_OK;
}

允许使用 clear_unsafe() 执行 O(1) 清除容器操作

如生命周期检查部分中所述，非受管指针容器可能不会销毁仍包含其中的对象，并且对象在认为自己仍在容器中时无法销毁。这两种行为都会被视为错误，并且会在调试 build 中触发断言。

如果您遇到这样的情况，您并不在意对象在销毁时仍然以为它们位于容器中，该怎么办？也许您分配了一块连续的内存，并将其划分为对象，然后添加到空闲列表上。如果您想释放大块内存，并且知道所有对象都已返回可用列表，那么为什么要遍历该列表将所有链接的列表记录归零？这样只会白费功夫。

您可以对对象使用 AllowClearUnsafe NodeOption，以绕过这些检查，并跳过强制性的 O(N) 取消关联列表。使用时，系统会跳过节点状态对象中存在的断言，并且容器中名为 clear_unsafe() 的方法可供使用。clear_unsafe() 只会将容器重置为其原始空状态，而无需清理对象的节点状态。这是一个简单的 O(1) 操作。尝试对使用不带此标志的节点状态对象的容器调用 clear_unsafe() 将触发 static_assert。下面是一个简单的示例：

class SlabObject :
  public fbl::SinglyLinkedListable<SlabObject*,
                                   fbl::NodeOptions::AllowClearUnsafe> { /* ... */ };

static fbl::Mutex slab_lock;
static SlabObject* slab_memory TA_GUARDED(slab_lock) = nullptr;
static fbl::SizedSinglyLinkedList<SlabObject*> TA_GUARDED(slab_lock) free_objects;

static constexpr size_t kSlabSize = (1 << 20);   // One MB of objects
static constexpr size_t kSlabCount = kSlabSize / sizeof(SlabObject);

zx_status_t InitSlab() {
  fbl::AutoLock lock(&slab_lock);
  if ((slab_memory != nullptr) || !free_objects.is_empty()) {
    return ZX_ERR_BAD_STATE;
  }

  fbl::AllocChecker ac;
  slab_memory = new (&ac) SlabObject[kSlabCount];
  if (!ac.check()) {
    return ZX_ERR_NO_MEMORY;
  }

  for (size_t i = 0; i < kSlabCount; ++i) {
    free_objects.push_front(slab_memory + i);
  }

  return ZX_OK;
}

SlabObject* GetFreeObj() {
  fbl::AutoLock lock(&slab_lock);
  return !free_objects.is_empty() ? free_objects.pop_front() : nullptr;
}

void ReturnObj(SlabObject* obj) {
  fbl::AutoLock lock(&slab_lock);
  ZX_DEBUG_ASSERT(obj != nullptr);
  free_objects.push_front(obj);
}

zx_status_t DeinitSlab() {
  fbl::AutoLock lock(&slab_lock);

  // If not all of our objects have returned, or if we don't have any slab
  // memory allocated, then we cannot de-init our slab.
  if ((slab_memory == nullptr) || (free_objects.size() != kSlabCount)) {
    return ZX_ERR_BAD_STATE;
  }

  // Great, reset the free list with clear unsafe. This basically just sets the
  // head pointer to nullptr.
  free_objects.clear_unsafe();

  // Now give our memory back. Since our objects are flagged with
  // AllowClearUnsafe, node state destructors do nothing. Provided that
  // SlabObject destructors do nothing, this delete should just return memory to
  // the heap and not need to call N destructors.
  delete[] free_objects;
  free_objects = nullptr;

  return ZX_OK;
}

直接从所在的任何容器实例中移除对象。

一般来说，如果设计代码需要直接从容器中移除对象，而无需引用容器本身，则这种做法不是最佳做法。作为一项设计原则，侵扰性容器的用户应始终知晓存在哪些容器类型和实例对象。尽管如此，有时直接移除可能是最简单、最好的方法。

如果在不了解容器实例的情况下从容器中移除节点，那么默认跟踪大小的容器可能需要对数据结构进行 O(n) 遍历，以查找用于更新簿记的容器。因此，这些容器不支持直接移除。其他容器类型（例如 SinglyLinkedList）无法执行此操作，因为它们缺少指向其上一个节点的反向指针。

但是，一个大小不等的双链接列表可以支持直接节点移除。如需启用此功能，请将 AllowRemoveFromContainer 添加到节点状态的 NodeOption 中。启用后，节点状态结构将提供 RemoveFromContainer() 方法。调用 RemoveFromContainer 与调用 InContainer 完全相同。它可以直接从对象调用（如果没有歧义）、在继承产生不明确时使用显式类型选择要移除的容器；或者在使用 ContainableBaseClasses 辅助程序时，使用顶级 fbl::RemoveFromContaier<Tag>(obj_ref) 调用。请参阅 InContainer()

请参考以下使用场景。您有大量作业需要通过流水线的几个阶段进行处理。每个流水线阶段都有一个待处理工作队列，线程从队列中获取和处理作业，然后排入流水线的下一阶段。

如果要取消正在执行的作业，如何轻松知道该作业处于哪个流水线阶段？一个答案可能就是，您不需要这样做，只要您可以直接从它当前所处的处理阶段将其移除即可。最终可能如下所示：

struct PipelineTag {};
struct ActiveTag {};

fbl::Mutex pipeline_lock;

class Job : public fbl::RefCounted<Job>,
            public fbl::ContainableBaseClasses<
              fbl::TaggedDoublyLinkedListable<fbl::RefPtr<Job>, PipelineTag,
                                              fbl::NodeOptions::AllowRemoveFromContainer>,
              fbl::TaggedWAVLTreeContainable<fbl::RefPtr<Job>, ActiveTag>> {
 public:
  // ...
  UniqueId GetKey() const { return unique_id_; }
  bool is_canceled() const TA_REQ(pipeline_lock) { return cancel_flag_; }
  void set_canceled() TA_REQ(pipeline_lock) { cancel_flag_ = true; }
  // ...
 private:
  bool cancel_flag_ TA_GUARDED(pipeline_lock) = false;
};

using PipelineQueue = fbl::TaggedDoublyLinkedList<fbl::RefPtr<Job>, PipelineTag>;
std::array<PipelineQueue, 10> pipeline_stages TA_GUARDED(pipeline_lock);
fbl::TaggedWAVLTree<fbl::RefPtr<Job>, ActiveTag> active_jobs TA_GUARDED(pipeline_lock);

zx_status_t QueueJob(fbl::RefPtr<Job> job) {
  ZX_DEBUG_ASSERT(job != nullptr);
  {
    fbl::AutoLock lock(&pipeline_lock);

    // Can't queue a job for processing if it is already being processed.
    if (fbl::InContainer<ActiveTag>(*job)) {
      return ZX_ERR_BAD_STATE;
    }

    // If we are not in the active set, then we had better not be in any of the
    // pipeline stages.
    ZX_DEBUG_ASSERT(!fbl::InContainer<PipelineTag>(*job));

    // Put the job into the active set and into the first pipeline stage.
    active_jobs.insert(job);
    pipeline_stages[0].push_back(std::move(job));
  }

  SignalPipelineStage(0);
}

void WorkThread(size_t pipeline_stage) {
  ZX_DEBUG_ASSERT(pipeline_stage < pipeline_stages.size());
  PipelineQueue& our_stage = pipeline_stages[pipeline_stage];
  PipelineQueue* next_stage = ((pipeline_stage + 1) < pipeline_stages.size())
                            ? (pipeline_stages + pipeline_stage + 1)
                            : nullptr;

  while (!QuitTime()) {
    fbl::RefPtr<Job> job;
    {
      // If there is work in our stage, take it out and get to work.
      fbl::AutoLock lock(&pipeline_lock);
      if (!our_stage.is_empty()) {
        job = our_stage.pop_front();
      }
    }

    // Did we not find a job? Just wait for something to do then.
    if (job == nullptr) {
      WaitForPipelineStageWorkOrQuit(pipeline_stage);
      continue;
    }

    // Do the job.
    ProcessJob(job, pipeline_stage);

    // If the job was canceled or reached the end of the pipeline, we will call
    // a handler to take care of it once we are out of the lock.
    void(*handler)(fbl::RefPtr<Job>) = nullptr;
    {
      fbl::AutoLock lock(&pipeline_lock);

      if (job->is_canceled()) {
        // Handle job cancellation if it was flagged for cancel while we were
        // working. No need to take it out of the active set, the cancel
        // operation should have already done that for us.
        ZX_DEBUG_ASSERT(!fbl::InContainer<ActiveTag>(*job));
        handler = HandleCanceledJob;
      } else if (next_stage != nullptr) {
        // Queue to the next stage if there is one.
        next_stage->push_back(std::move(job));
        signal_next_stage = true;
      } else {
        // End of pipeline. This job is finished, remember to take it out of
        // the active set.
        ZX_DEBUG_ASSERT(fbl::InContainer<ActiveTag>(*job));
        active_jobs.erase(*job);
        handler = HandleFinishedJob;
      }
    }

    // Now that we are out of the lock, either signal the next stage so that it
    // knows that it might have some work, or call the chosen handler on the job.
    if (handler) {
      ZX_DEBUG_ASERT(job != nullptr);
      handler(std::move(job));
    } else {
      SignalPipelineStage(pipeline_stage + 1);
    }
  }
}

zx_status_t CancelJob(UniqueId id) {
  fbl::RefPtr<Job> canceled_job;
  {
    fbl::AutoLock lock(&pipeline_lock);

    // Is there an active job with the provided ID?
    auto iter = active_jobs.find(id);
    if (!iter.IsValid()) {
      return ZX_ERR_NOT_FOUND;
    }

    // No matter what, the job is no longer active. Take its reference back from
    // the active job set.
    fbl::RefPtr<Job> job = active_jobs.erase(iter);

    // Flag the job as canceled.
    job->set_canceled();

    // If the job is in a pipeline stage, then no thread is currently working on
    // it. We can just pull it out of whatever stage we are in and we are done.
    if (fbl::InContainer<PipelineTag>(*job)) {
      canceled_job = fbl::RemoveFromContainer<PipelineTag>(*job);
    }
  }

  // Now that we are out of the lock, if we were the ones to pull the job out of
  // the pipeline, we should hand it over to the cancel handler.
  HandleCanceledJob(std::move(canceled_job));
  return ZX_OK;
}