From 4a2ddf8075937b8f5e020dff830a7c01d891c448 Mon Sep 17 00:00:00 2001
From: Milo Yip <miloyip@gmail.com>
Date: Sun, 17 Aug 2014 18:29:37 +0800
Subject: Add Stack::ShrinkToFit() and some refactoring.

Lazy allocation. (so Document not for parsing don't need to allocate
stack).
Remove redundant stackCapacity member variable.
---
 include/rapidjson/internal/stack.h | 75 +++++++++++++++++++++++---------------
 1 file changed, 46 insertions(+), 29 deletions(-)

(limited to 'include/rapidjson/internal/stack.h')

diff --git a/include/rapidjson/internal/stack.h b/include/rapidjson/internal/stack.h
index 4ab84b1a..294b51a0 100644
--- a/include/rapidjson/internal/stack.h
+++ b/include/rapidjson/internal/stack.h
@@ -33,67 +33,84 @@ namespace internal {
 template <typename Allocator>
 class Stack {
 public:
-    Stack(Allocator* allocator, size_t stack_capacity) : allocator_(allocator), own_allocator_(0), stack_(0), stack_top_(0), stack_end_(0), stack_capacity_(stack_capacity) {
-        RAPIDJSON_ASSERT(stack_capacity_ > 0);
+    // Optimization note: Do not allocate memory for stack_ in constructor.
+    // Do it lazily when first Push() -> Expand() -> Resize().
+    Stack(Allocator* allocator, size_t stackCapacity) : allocator_(allocator), ownAllocator(0), stack_(0), stackTop_(0), stackEnd_(0), initialCapacity_(stackCapacity) {
+        RAPIDJSON_ASSERT(stackCapacity > 0);
         if (!allocator_)
-            own_allocator_ = allocator_ = new Allocator();
-        stack_top_ = stack_ = (char*)allocator_->Malloc(stack_capacity_);
-        stack_end_ = stack_ + stack_capacity_;
+            ownAllocator = allocator_ = new Allocator();
     }
 
     ~Stack() {
         Allocator::Free(stack_);
-        delete own_allocator_; // Only delete if it is owned by the stack
+        delete ownAllocator; // Only delete if it is owned by the stack
     }
 
-    void Clear() { /*stack_top_ = 0;*/ stack_top_ = stack_; }
+    void Clear() { stackTop_ = stack_; }
+
+    void ShrinkToFit() { 
+        if (Empty()) {
+            // If the stack is empty, completely deallocate the memory.
+            Allocator::Free(stack_);
+            stack_ = 0;
+            stackTop_ = 0;
+            stackEnd_ = 0;
+        }
+        else
+            Resize(GetSize());
+    }
 
     // Optimization note: try to minimize the size of this function for force inline.
     // Expansion is run very infrequently, so it is moved to another (probably non-inline) function.
     template<typename T>
     RAPIDJSON_FORCEINLINE T* Push(size_t count = 1) {
          // Expand the stack if needed
-        if (stack_top_ + sizeof(T) * count >= stack_end_)
+        if (stackTop_ + sizeof(T) * count >= stackEnd_)
             Expand<T>(count);
 
-        T* ret = reinterpret_cast<T*>(stack_top_);
-        stack_top_ += sizeof(T) * count;
+        T* ret = reinterpret_cast<T*>(stackTop_);
+        stackTop_ += sizeof(T) * count;
         return ret;
     }
 
     template<typename T>
     T* Pop(size_t count) {
         RAPIDJSON_ASSERT(GetSize() >= count * sizeof(T));
-        stack_top_ -= count * sizeof(T);
-        return reinterpret_cast<T*>(stack_top_);
+        stackTop_ -= count * sizeof(T);
+        return reinterpret_cast<T*>(stackTop_);
     }
 
     template<typename T>
     T* Top() { 
         RAPIDJSON_ASSERT(GetSize() >= sizeof(T));
-        return reinterpret_cast<T*>(stack_top_ - sizeof(T));
+        return reinterpret_cast<T*>(stackTop_ - sizeof(T));
     }
 
     template<typename T>
     T* Bottom() { return (T*)stack_; }
 
     Allocator& GetAllocator() { return *allocator_; }
-    bool Empty() const { return stack_top_ == stack_; }
-    size_t GetSize() const { return static_cast<size_t>(stack_top_ - stack_); }
-    size_t GetCapacity() const { return stack_capacity_; }
+    bool Empty() const { return stackTop_ == stack_; }
+    size_t GetSize() const { return static_cast<size_t>(stackTop_ - stack_); }
+    size_t GetCapacity() const { return static_cast<size_t>(stackEnd_ - stack_); }
 
 private:
     template<typename T>
     void Expand(size_t count) {
-        size_t new_capacity = stack_capacity_ * 2;
-        size_t size = GetSize();
-        size_t new_size = GetSize() + sizeof(T) * count;
-        if (new_capacity < new_size)
-            new_capacity = new_size;
-        stack_ = (char*)allocator_->Realloc(stack_, stack_capacity_, new_capacity);
-        stack_capacity_ = new_capacity;
-        stack_top_ = stack_ + size;
-        stack_end_ = stack_ + stack_capacity_;
+        // Only expand the capacity if the current stack exists. Otherwise just create a stack with initial capacity.
+        size_t newCapacity = (stack_ == 0) ? initialCapacity_ : GetCapacity() * 2;
+        size_t newSize = GetSize() + sizeof(T) * count;
+        if (newCapacity < newSize)
+            newCapacity = newSize;
+
+        Resize(newCapacity);
+    }
+
+    void Resize(size_t newCapacity) {
+        const size_t size = GetSize();  // Backup the current size
+        stack_ = (char*)allocator_->Realloc(stack_, GetCapacity(), newCapacity);
+        stackTop_ = stack_ + size;
+        stackEnd_ = stack_ + newCapacity;
     }
 
     // Prohibit copy constructor & assignment operator.
@@ -101,11 +118,11 @@ private:
     Stack& operator=(const Stack&);
 
     Allocator* allocator_;
-    Allocator* own_allocator_;
+    Allocator* ownAllocator;
     char *stack_;
-    char *stack_top_;
-    char *stack_end_;
-    size_t stack_capacity_;
+    char *stackTop_;
+    char *stackEnd_;
+    size_t initialCapacity_;
 };
 
 } // namespace internal
-- 
cgit v1.2.3