Smart Pointers, Ch7, Modern C++ Design

Smart pointer 對 C++ 來說，是很常用的東西。使用 smart pointer 主要的目的，是 "resource allocation is initialization (RAII)"，這樣有能在 resource 不需要用的時候，藉由 smart pointer 自動 delete，省去一些管理 pointer 的困難。

這章提到的 SmartPtr 設計細節很多，主要是使用上的需要支援許多功能，卻又需要考慮效能和維持易用的語法，所以有些地方需要取捨。這些地方，都是設計 library 的時候常常碰到的問題，是很好的範例。

Smart Pointers 101

Smart Pointer 主要的用法，就是除了宣告以外，其他地方要用起來跟 raw pointer 一樣，因此需要實作下面的 member function：

1. explicit SmartPtr(T* pointee)
2. SmartPtr& operator=(const SmartPtr& other)
3. ~SmartPtr()
4. T& operator*() const
5. T* operator->() const

除了 operator*() 和 operator->()，還有其他 operator 是 raw pointer 支援的，但是 SmartPtr 考量使用情況不支援的：

1. T** operator&(): 可以提供更多的 raw pointer 相容性，方便直接以 SmartPtr 替換 raw pointer。但是這會曝露裡面的指標，而且會讓 STL container 等 template 用來取址的時候出錯。
2. Implicit Conversion Operator (operator T*()): 可以提供更多相容性，但是很容易被誤用，像是 delete spFoo 就可以自動轉型。這對於 raw pointer 直接把宣告換成 SmartPtr 的 code 非常容易出錯。
3. Array operator[](): 應該盡量使用 std::vector，所以不支援 array。實際上可以用修改 StoragePolicy 的方式，在 destructor 呼叫對應的 delete[] 達成指向 array 的目的。要使用 operator[] 或者指標加減，需要額外取得實際的指標。
4. 指標的 ordering comparisons，SmartPtr 預設也沒有提供。SmartPtr 指到的位址通常是分別配置的，比較大小沒有意義。Effective C++ 也有提到，避免直接使用指標運算加減，同一個陣列應該用 pArray[index] 的寫法。

另外，operator==, operator!=, operator! 的部份，raw pointer 很常用，必需要支援。直接用 operator bool() 自動轉型有很多問題，像是兩個不同型的指標可以都自動轉成 bool 去比較，或者自動轉成 bool 跟其他整數型別比較。總之，C++ 自動轉型很容易出問題，像是 std::string 也是額外提供 c_str() 而不是自動轉型。因為沒有自動轉型，所以這些 operator 必須一個一個定義出來，包括 SmartPtr 跟 raw pointer 的排列組合。

SmartPtr Member Functions

除了 operator overload 為了讓 SmartPtr 用起來跟一般指標相容，SmartPtr 不提供 member function，因為容易跟 pointee 的 member function 搞渾。像是下面的 release，改成 global 比較明顯。

struct Foo{ void release(); };
SmartPtr<foo> spFoo;
spFoo->release();
spFoo.release(); // 跟上面搞混了
release(spFoo); // 明顯不是呼叫 Foo

Multithreaded Reference Linking

因為使用環狀的 double-linked list，恰好兩個 SmartPtr 物件的情況，prev_ == next_ 對兩個物件都成立。下面這節處理 linked-list 的 code 需要改進，才能處理兩個物件的情況。修改以後，恰好兩個物件的時候，走 else 的分支，也會形成正確的 circular double-linked list.

//7.13.2.2 Multithreaded Reference Linking, p. 164
~SmartPtr()
{
    if ((prev_ == next_) && (prev_ == this))
    {
        delete pointee_;
    }
    else
    {
        prev_->next_ = next_;
        next_->prev_ = prev_;
    }
}

這裡還有另外一個觀察，SmartPtr 維護 book-keeping data 的 thread safe 的重要性。Book-keeping 只有在 construct, assign, destruct 這三個地方發生，相對於 dereference 算是很少的。個人經驗上，通常是某 thread 頻繁使用某變數，而其他任何一個 thread 偶爾用到同一個變數，這種情況比較容易發生 race-condition。如果 SmartPtr 沒有頻繁複製的話，應該不太需要擔心 thread safety。這也可以解釋 reference-linking 不處理 thread 問題，因為要額外處理 mutex lock 太花成本。相比之下，reference-counting 只要 atomic increment 就達成 thread safe，相對來說快很多。

Storage Policy Revisited

讀到 7.14.1 The Storage Policy 的時候，突然想到 C code 常有下面這樣的 API 設計：

file_id fid = file_open("aaa.txt");
file_read(fid);
…
file_close(fid);

像是 file_id 這樣的 handle，作用跟指標類似，也需要資源管理。這樣的 handle 可以用 SmartPtr 來操作嗎？測試以後確定，只要適當的使用 StoragePolicy，定義好 StoredType 就可以用 SmartPtr 來管理這種 handle，但是只能管理 ownership，不能用 operator->() 或者 operator*()，因為無法對應相關的 global function。如此使用上需要 GetImp(ptrHandle)，這是先天的限制，因為 handle 或 id 常常就是為了不直接使用 pointer 的刻意設計。

心得：實用案例

假設有某個 Task 需要二個不同 resource 才能運作，

struct Task
{
    SmartPtr<R1> pR1;
    SmartPtr<R2> pR2;
};

在 StartTask() 的時候，需要取得每一個 resource，每個都取得才會成功。

bool StartTask()
{
    Task task;
    if(NULL == (task.pR1 = getResource1()))
    {
        return false;
    }
    if(NULL == (task.pR2 = getResource2()))
    {
        return false; // 自動釋放 task.pR1
    }
    m_runningTask = task; // 成功了，保存這個 Task 的狀態
    return true;
}

如此這段邏輯就很清楚，萬一中間多插了一個 return，或是發生 exception，也可以正確釋放資源。這個例子裡面，SmartPtr 使用 ownership transfer 就夠用了。如果其他地方有用到，reference counting 就比較適合。

Functor, Ch5, Modern C++ Design

從這章開始，這本書使用 template 等技巧實作了 Loki library 的主要元件，也就是 design pattern 的功能。這章 Functor 的設計，是要讓 library 使用者快速套用 Command Pattern。

Command Pattern

這是 Command Pattern 的架構，其實在很多跟 UI 有關的 Framework 都使用了這樣的設計。
使用的時候，client 自訂 ConcreteCommand 要呼叫的 Receiver::Action 和參數，然後把這個物件傳給 Invoker，這樣就能在需要的時間點，讓 Invoker 執行該做的事。

因為通常是 Receiver 真正做事， Command & ConcreteCommand 只存參數等狀態，所以 Command & ConcreteCommand 常常只是 forwarding，於是這章打算把 forwarding command 包裝起來，不用每次都重複寫。包裝起來需要做到下面的功能：

1. Create 的時候，要能設定 Receiver, action, 還有 action 的參數。
1. Command::Execute() 可能有不同的 return type, parameter type，每一組 prototype 都是一個 class，所以要用 class template 來做。
2. Create 的時候，可以給已知的參數，這樣 prototype 就會改變。
3. 可以產生 MacroCommand，可以一次執行多的 ConcreteCommand.
2. 可以被 Invoker 執行，並且呼叫正確的 action.
3. C++ 的 callable entity 都要能使用。
1. Function pointer
2. Functor (class with operator())
3. Pointer to member function
4. 因為 Command + Execute() 本身就跟 functor 結構一樣，而且這邊設計的萬能 Command 需要同時能夠呼叫 functor 和其他 Command，就統一使用 operator() 代替 Execute，並且把 class 命名為 Functor。（要自動判斷呼叫 operator() 還是 Execute()，應該很難設計）

Functor

整理一下上面的需求，可以得到下面的功能列表。

1. Functor 的 prototype (return type + parameter type) 是 template 分類的方式。
2. 因為 parameter type 長度不固定，用 Typelist 來處理。
3. Constructor 有三種，分別負責記住 function pointer, functor, pointer to member function.
4. Overload operator() 來執行 constructor 給的參數。
5. 內部處理不同 constructor 的資料，因為資料不一樣大，執行方式也不同，用 private class 繼承。

假設 Functor 最多吃兩個參數，一開始寫出來的 code 大概像這樣，可以滿足幾個重點。第一，只要 prototype 固定， Functor 就是個完整的 type，這對 library 設計有很有用。第二，Typelist 可以處理不同長度的 prototype。第三，function pointer 和 functor 都能用，只要 constructor 給參數。第四，operator() 有不同長度的版本，利用 template 沒用到就沒實體化的特性。第五，因為 functor 等資料大小不同，用 private class 動態產生不同大小或型別的容器來存。

template<typename RType, class TL>
class Functor
{
    typedef typename IndexOf<TL, 0>::Result P1;
    typedef typename IndexOf<TL, 1>::Result P2;
public:
    template<typename Ftor>
    Functor(Ftor ftor)
    {
        m_pImpl = new FunctorImpl<RType, TL, Ftor>(ftor);
    }
    RType operator()()
    {
        return (*m_pImpl)();
    }
    RType operator()(P1 p1)
    {
        return (*m_pImpl)(p1);
    }
    RType operator()(P1 p1, P2 p2)
    {
        return (*m_pImpl)(p1, p2);
    }

private:
    template<typename RType2, class TL2>
    class BaseImpl
    {
        …
    };

    template<typename RType2, class TL2, typename Ftor>
    class FunctorImpl : public BaseImpl<RType2, TL2>
    {
        ...
    };

    BaseImpl<RType, TL>* m_pImpl;
};

在實作 BaseImpl 的時候，會想跟 Functor 本身一樣提供不同長度的 operator()，並且給子類別 virtual 實作，但是這樣不行。BaseImpl::operator() 如果是 virtual，就一定要在 template 裡面實體化，因為 virtual 沒辦法事先判斷有沒有用到。如果又同時 overload，就會讓所有版本實體化，造成參數數量錯誤的 compile error。

所以實作的方式，是用 template specialization 根據參數長度，讓每個長度的 operator() 都放在分別的 BaseImpl 裡面，這樣就可以宣告為 virtual。然後實作的 FunctorImpl 再 overload 所有長度的 operator()，符合長度的那個是繼承的 virtual 一定會實體化。其他的長度不是 virtual，不會實體化可以 compile，如果傳錯參數長度，實體化的時候也會 compile error。

template<typename RType2, class TL2> class BaseImpl;
template<typename R>
class BaseImpl<R, TYPELIST_0()>
{
public:
    virtual R operator()() = 0;
    virtual ~BaseImpl() {}
};
template<typename R, typename P1>
class BaseImpl<R, TYPELIST_1(P1)>
{
public:
    virtual R operator()(P1 p1) = 0;
    virtual ~BaseImpl() {}
};
template<typename R, typename P1, typename P2>
class BaseImpl<R, TYPELIST_2(P1, P2)>
{
public:
    virtual R operator()(P1 p1, P2 p2) = 0;
    virtual ~BaseImpl() {}
};

template<typename RType2, class TL2, typename Ftor>
class FunctorImpl : public BaseImpl<RType2, TL2>
{
public:
    FunctorImpl(Ftor ftor) : m_ftor(ftor) {}
    RType2 operator()()
    {
        return m_ftor();
    }
    RType2 operator()(P1 p1)
    {
        return m_ftor(p1);
    }
    RType2 operator()(P1 p1, P2 p2)
    {
        return m_ftor(p1, p2);
    }

private:
    Ftor m_ftor;
};

這段是很巧妙的設計，靠著 template specialization 可以讓 virtual function 選擇性的實體化。

Pointers to Member Function

上面的實作，可以同時支援 pointer to function & functor。根據上面的實作，寫出 pointer to member function 是很容易的，只要在 constructor 提供兩個參數，pointer to object & pointer to member function 就可以了。

public:
    template<class ObjPtr, class MemberPtr>
    Functor(ObjPtr objPtr, MemberPtr memberPtr)
    {
        m_pImpl = new PointerToMemberImpl<RType, TL, ObjPtr, MemberPtr>(objPtr, memberPtr);
    }
…
private:
    template<typename RType2, class TL2, typename ObjPtr, typename MemberPtr>
    class PointerToMemberImpl : public BaseImpl<RType2, TL2>
    {
    public:
        PointerToMemberImpl(ObjPtr objPtr, MemberPtr memberPtr) :
            m_objPtr(objPtr),
            m_memberPtr(memberPtr)
        {}
        RType2 operator()()
        {
            return (m_objPtr->*m_memberPtr)();
        }
        RType2 operator()(P1 p1)
        {
            return (m_objPtr->*m_memberPtr)(p1);
        }
        RType2 operator()(P1 p1, P2 p2)
        {
            return (m_objPtr->*m_memberPtr)(p1, p2);
        }

    private:
        ObjPtr m_objPtr;
        MemberPtr m_memberPtr;
    };

注意 Functor constructor 的第一個參數是 pointer to object，語意可以明確表示，建構 Functor 的時候和執行的時候，都是用同一個 object。雖然 pointer to member function 比較晚介紹，但是可能是最常用的，因為 C++ 通常 member function 佔多數。

Binding and Chaining Requests

Functor （也就是 command pattern）有兩個常見的特殊應用，第一個是 binding，create 的同時給部份參數特定的值，但是剩餘的參數執行時才給。如此一來，執行時的 prototype 會改變。最常見的特例，就是 command pattern 建立 command 的同時，寫好幾個 setXXX() 把所有參數指定，使得執行變成 void execute(void)。

Chaining 則是把好幾個 Functor 串成一個，也就是 command pattern 的 macro command。要注意 chaining 通常是同樣的 prototype 才能組合，這樣參數才能一致，return 也就可以選擇某一個。最常見的 chaining 通常也是 void execute(void) 這組 prototype，沒有參數和 return 的模糊。

這兩個實作都很直接使用 template。

Small-Object Allocation, Ch4, Modern C++ Design

這章算是開始介紹 library 的設計，為後面其他工具鋪路，要設計一個有效率的 allocator。個人對於 memory 的配置不特別感興趣，因為這是 C++ 很基本的功能，也有很多 library 針對不同需求實作這個東西，直接找來用是很簡單的。但是除了 memory，其他地方也是有類似的資源分配需求，這章有些技巧可以學。



上面的圖表示了四層的設計。SmallObject 是對外的界面，只要繼承他就可以快速 new-delete。SmallObjAllocator 則是負責 allocate 不同大小的 memory。FixedAllocator 只負責處理固定大小的 allocation。Chunk 則是把小塊 memory 拼成大塊，轉交給底層 ::operator new 一次處理一大塊。

Chunks

這是 Chunk 的定義，用 Init() 來真的呼叫 ::operator new 取得一塊大塊 memory，用 pData_ 記下來。書裡沒列出的 Deinit() 應該要呼叫 ::operator delete。

struct Chunk
{
    void Init(std::size_t blockSize, unsigned char blocks);
    void Deinit();
    void* Allocate(std::size_t blockSize);
    void Deallocate(void* p, std::size_t blockSize);
    unsigned char* pData_;
    unsigned char firstAvailableBlock_;
    unsigned char blocksAvailable_;
};

Allocate() 和 Deallocate() 是用來分配使用 pData_ 指到的 memory 空間 (memory chunk)，參數 blockSize 是要 allocate 的大小，對同一個 Chunk 永遠是固定的，為了節省空間所以存在上層。Memory chunk 分成多個相同 blockSize 的 block，每個 block 的第一個 byte 紀錄下個 available block 的 index，形成一個 linked list 來紀錄可用的 block。這是 memory management 常見的作法。因為只用一個 byte，所以一個 Chunk 最多有 256 個 block。

在 Chunk 裡面，Allocate() 和 Deallocate() 都只要處理 linked list 的頭，速度很快。額外用的空間也佔很少比例。但是要注意，因為用 linked list 紀錄 available block，所以 Deallocate() 沒辦法檢查 double free，double free 會造成 linked list 壞掉。如果要解決這個問題，就要每個 block 多用一個 bit 紀錄是否 available。

The Fixed-Size Allocator

針對同一個大小的 allocation，使用同一個 FixedAllocator 來分配，就是這一層要處理的。因為他要控制多個 Chunk，可能需要 linear search 會降低效率，所以加了幾個技巧。

1. 使用最簡單的 cache 機制，紀錄最後一個 allocated chunk, deallocated chunk。先找最後一個。
2. 如果最後一個 allocated chunk 沒有空間，那就從頭開始 linear search。
3. 如果最後一個 deallocated chunk 不是，那就從這個指標同時往上下找。這是為了改進兩種 memory 使用模式，一種是 delete 順序跟 new 相同，另一種 delete 順序跟 new 相反。
4. 等到 Deallocate 有兩個空的 Chunk，才真的刪掉一個。這是為了避免 new & delete 反覆跨過邊界條件浪費時間。

The SmallObjAllocator Class

這個 class 處理任意大小的 memory 分配。如果太大，直接用 ::operator new/delete。如果夠小，就呼叫適當的 FixedAllocator 來處理。所以他有一個 vector<FixedAllocator> pool_，並且按照allocation 大小排序。

跟 FixedAllocator 類似，SmallObjAllocator 也 cache 紀錄了最後一個用來 allocate & deallocate 的 FixedAllocator，為了讓連續相同大小的物件使用更有效率。

SmallObject

實作 static operator new & delete 來給其他 class 繼承。他的定義很簡單，但是他的 delete 有第二個參數 size，是比較特別的。一般 operator delete 只有一個參數，但是 C++ 也支援兩個參數的版本，對實作 SmallObjAllocator 比較有效率，可以省下很多搜尋的時間。而 compiler 實作的時候，可以透過 virtual destructor 或者 v-table 得到指標執行時候真正的 size，再把 size 傳給 operator delete。

class SmallObject
{
public:
    static void* operator new(std::size_t size);
    static void operator delete(void* p, std::size_t size);
    virtual ~SmallObject() {}
};

其實這個部份我有疑惑，因為繼承 SmallObject 都會一併繼承 virtual desctructor，很多 compiler 會需要多存一個 vptr，這多使用的空間，和整個 allocation 的設計目的違背。而且，如果這邊沒有 virtual destructor，還是能夠繼承使用相同的功能，因此這邊不必 virtual，如果繼承以後有需要再加就可以了。為了避免直接 delete (SmallObject*)pFoo 沒呼叫到實際的 destructor，要把 ~SmallObject() 改成 protected。實際用 gcc 測試，struct Foo{ int a; }; 本身只要 4 bytes，多一個 virtual 會變成 16 bytes。改成 non-virtual protected destructor 就沒有問題。

Singleton and Multithreading Issues

設計基礎的 memory 分配的時候，整個系統都呼叫同一個 operator new，所以只能有一個 SmallObjAllocator 實體，同時也只能有一個 thread 使用。這邊很優雅的用 policy template 處理 multi-thread mutex lock 的實作，加上適當的 default 就完全不影響原本的設計，是很精彩的設計範例。