Add Stack::ShrinkToFit() and some refactoring.

Lazy allocation. (so Document not for parsing don't need to allocate
stack).
Remove redundant stackCapacity member variable.

1 files changed, 46 insertions, 29 deletions

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