如前文所述,如果物件存在於侵入式容器中,使用者必須明確地將容器記帳的儲存空間新增至物件本身。本節將詳細說明如何控制物件可存在的容器。本功能將執行以下作業:
- 示範可能在單一容器中存在的物件簡單情況。
- 說明同時使用多個容器加入成員資格的兩種方法。
- 示範如何在滿足進階需求時,完全手動控管物件中的簿記儲存空間。
單一容器成員資格。
一般而言,選擇使用容器的預設混合項目是最簡單且正確的選擇。您已看過本指南「開始使用」一節的雙連結清單看起來會像這樣。以下列舉所有預設混合項目的簡單範例。
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
佇列中新增該 Foo 的參照。
請注意,當物件出現在有效物件的集合中時,系統會檢查該物件是否「已經」在待處理佇列中,然後再嘗試將其附加到待處理佇列。FooObj
如果 ContainerTypeA
的執行個體「已經」位於 ContainerTypeA
的執行個體中 (無論是同一執行個體或不同的執行個體),嘗試將物件放入 ContainerTypeA
的執行個體中將觸發 ZX_DEBUG_ASSERT;如果斷言已啟用,則會觸發 ZX_DEBUG_ASSERT,否則會破壞程式狀態。確保不會發生這種情況,非常重要。經常,程式中的不變性可確保這種情況永遠不會發生,但如果您的程式缺少這種不變數,請記得檢查物件,確認物件是否已在容器中。
請參閱測試容器成員資格一節,瞭解各種具體做法。另請注意這個範例中會如何審慎測試成員資格。有一些更好的做法,我們會在下一節說明 ContainableBaseClasses
的使用方式中說明。
這個範例還有一個重點如果要將 FooObj
放入待處理佇列,則必須將新的 fbl::RefPtr
執行個體提供給 push_back
。您可以藉由呼叫疊代器的 CopyPointer
方法來取得這項結果,此方法會叫用基礎指標類型的複製建構函式,從而提供物件的新參照。對原始指標而言,這屬於免人工管理。若為 unique_ptr,此為非法行為且無法編譯。
使用 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
雖然在技術上嚴格來說 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<>
追蹤其物件的節點狀態物件。最佳做法是將這些節點狀態物件設為類別的私人成員。
定義節點狀態特徵類別
這些行會宣告兩個「特徵」類別,用來指示容器類型如何存取其相關聯的節點簿記。
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 類別設為不公開,不過由於節點執行個體的私人性質,您也必須將 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);