進階情境

根據預設，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;
}

允許 O(1) 使用 clear_unsafe() 清除容器

如生命週期檢查一節所述，非代管指標的容器可能不會隨著物件而銷毀，而且物件認為這些指標仍在容器中，因此無法銷毀。這兩種行為都視為錯誤，並在偵錯版本中觸發斷言。

如果在某個情況下，您沒擔心物件在刪除時仍位於容器中，該怎麼辦？也許您分配了連續的記憶體研究室，然後整理成物件，然後您再加入免費清單。如果您希望釋放記憶體空間，且您知道所有物件都已返回免費清單，那麼為何要這麼做，為何要把清單全部排除，如此所有的連結清單簿記中呢？這可是件很繁瑣的工作。

您可以在物件中使用 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 的相同。如果沒有模稜兩可，系統可能會直接從物件呼叫此方法，在繼承產生不明確時，使用明確類型選取要移除的容器，或使用頂層 fbl::RemoveFromContaier<Tag>(obj_ref) 呼叫。ContainableBaseClasses查看 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;
}