RapidJSON 代碼剖析（一）：混合任意類型的堆棧

01-31

大家好，這個專欄會分析 RapidJSON （中文使用手冊）中一些有趣的 C++ 代碼，希望對讀者有所裨益。

C++ 語法解說

我們先來看一行代碼（document.h）：

bool StartArray() {n new (stack_.template Push<ValueType>()) ValueType(kArrayType);n return true;n}n

或許你會問，這是什麼C++語法？

這裡其實用了兩個可能較少接觸的C++特性。第一個是 placement new，第二個是 template disambiguator。

Placement new

簡單來說，placement new 就是不分配內存，由使用者給予內存空間來構建對象。其形式是：

new (T*) T(...);n

第一個括弧中的是給定的指針，它指向足夠放下 T 類型的內存空間。而 T(...) 則是一個構造函數調用。那麼，上面 StartArary() 里的代碼，分開來寫就是：

bool StartArray() {n ValueType* v = stack_.template Push<ValueType>(); // (1)n new (v) ValueType(kArrayType); // (2)n return true;n}n

這麼分拆，(2)應該很容易理解吧。那麼(1)是什麼樣的語法？為什麼中間會有 template 這個關鍵字？

template disambiguator

(1)其實只是調用 Stack 類的模板成員函數 Push()。如果刪去這個 template，代碼就顯得正常一點：

ValueType* v = stack_.Push<ValueType>(); // (1)n

這裡 Push<ValueType> 是一個 dependent name，它依賴於 ValueType 的實際類型。這裡編譯器不能確認 < 為小於運算符，還是模板的 <。為了避免歧義，需要加入template 關鍵字。這是C++標準的規定，缺少這個 template 關鍵字 gcc 和 clang 都會報錯，而 vc 則會通過（C++標準也容許實現這樣的編譯器）。和這個語法相近的還有typename disambiguator。

理解這些語法之後，我們進入核心問題。

混合任意類型的堆棧

處理樹狀的數據結構時，我們經常需要用到堆棧（stack）這種數據結構。C++ 標準庫也提供了 std::stack 這個容器。然而，這個模板類容器的實例，只能存放一種類型的對象。在 RapidJSON 的解析過程中，我們希望它能同時存放已解析的 Value 對象，以及 Member 對象（key-value對）。或者我們從另一個角度去想，程序堆棧（program stack）本身就是可儲存各種類型數據的堆棧。在 RapidJSON 中的其它地方也有這種需求。

在 internal/stack.h 中的 Stack 類實現了這個構思，其聲明是這樣的：

class Stack {n Stack(Allocator* allocator, size_t stackCapacity);n ~Stack();nn void Clear();n void ShrinkToFit();n n template<typename T> T* Push(size_t count = 1);n template<typename T> T* Pop(size_t count);n template<typename T> T* Top();n template<typename T> T* Bottom();nn Allocator& GetAllocator();n bool Empty() const;n size_t GetSize();n size_t GetCapacity();n};n

這個類比較特殊的地方，就是堆棧操作使用模板成員函數，可以壓入或彈出不同類型的對象。另外，為了完全防止拷貝構造函數調用的可能性，這些函數都是返回指針。雖然引用也可以，但使用指針在一些應用情況下會更自然。

例如，要壓入4個 int，再每次彈出兩個：

Stack s;n*s.Push<int>() = 1;n*s.Push<int>() = 2;n*s.Push<int>() = 3;n*s.Push<int>() = 4;nfor (int i = 0; i < 2; i++) {n int* a = s.Pop<int>(2);n std::cout << a[0] << " " << a[1] << std::endl;n}n// 輸出：n// 3 4n// 1 2n

注意到，Pop() 返回彈出的最底端元素的指針，我們仍然可以通過這指針合法地訪問這些彈出的元素。

重要事項（坑出沒注意）

在 StartArray() 的例子里，我們看到使用 placement new 來構建對象。在普通的情況下，new 和 delete 應該是成雙成對的，但使用了 placement new，就通常不能使用delete，因為 delete 會調用析構函數並釋放內存。在這個例子里，stack_ 對象提供了內存空間，所以我們只需要調用 ValueType 的析構函數。例如，如果解析在中途終止了，我們要手動彈出已入棧的 ValueType 並調用其析構函數：

while (!stack_.Empty())n (stack_.template Pop<ValueType>(1))->~ValueType();n

另一個問題是，如果壓入不同的數據類型，可能會有內存對齊問題，例如：

Stack s;n*s.Push<char>() = f;n*s.Push<char>() = o;n*s.Push<char>() = o;n*s.Push<int >() = 123; // 對齊問題n

123寫入的地址不是4的倍數，在一些CPU下可能造成崩潰。如果真的要做緊湊的packing，可以用 std::memcpy：

int i = 123;nstd::memcpy(s.Push<int>(), &i, sizeof(i));nnint j;nstd::memcpy(&j, s.Pop<int>(1), sizeof(j));n

代碼復用

由於 RapidJSON 不依賴於 STL，在實現一些功能時缺少一些容器的幫忙。後來想到，一些地方其實可以把 Stack 當作可動態縮放的緩衝區來使用。例如，我們想從DOM生成JSON的字元串，就實現了 GenericStringBuffer：

template <typename Encoding, typename Allocator = CrtAllocator>nclass GenericStringBuffer {npublic:n typedef typename Encoding::Ch Ch;n n // ... nn void Put(Ch c) { *stack_.template Push<Ch>() = c; }nn const Ch* GetString() const {n // Push and pop a null terminator. This is safe.n *stack_.template Push<Ch>() = 0;n stack_.template Pop<Ch>(1);nn return stack_.template Bottom<Ch>();n }nn size_t GetSize() const { return stack_.GetSize(); }nn // ...nn mutable internal::Stack<Allocator> stack_;n};n

想在緩衝器末端加入字元，就使用 Stack::Push<Ch>()，想把整個緩衝取出來，就簡單地回傳底端的指針。不過這裡有個特別的地方，因為需要空字元作結尾，在 GetString()時，會壓入並立即彈出一個空字元。如前所述，彈出後、壓入其他東西前，剛彈出的內容仍然是合法的。而由於我們希望GetString() 是 const 函數，所以這裡讓 stack_ 加上mutable 修飾詞。

結語

RapidJSON 為了一些內存及性能上的優化，萌生了一個混合任意類型的堆棧類 rapidjson::internal::Stack。但使用這個類要比 STL 提供的容器危險，必須清楚每個操作的具體情況、內存對齊等問題。而帶來的好處是更自由的容器內容類型，可以達到高緩存一致性（用多個 std::stack 不利此因素），並且避免不必要內存分配、釋放、對象拷貝構造等。從另一個角度看，這個類更像一種特殊的內存分配器。