Reimplement state stack not to move elements

Add another recursive parsing test that forces second allocation
in the stack.

3 files changed, 108 insertions, 60 deletions

diff --git a/libxsde/xsde/cxx/stack.cxx b/libxsde/xsde/cxx/stack.cxx
index 775c88f..bf5b276 100644
--- a/libxsde/xsde/cxx/stack.cxx
+++ b/libxsde/xsde/cxx/stack.cxx
@@ -3,49 +3,76 @@
 // copyright : Copyright (c) 2005-2010 Code Synthesis Tools CC
 // license   : GNU GPL v2 + exceptions; see accompanying LICENSE file
 
-#include <string.h> // memcpy
-
 #include <xsde/cxx/stack.hxx>
 
 namespace xsde
 {
   namespace cxx
   {
+    stack::
+    ~stack ()
+    {
+      for (block* n = next_; n != 0;)
+      {
+        block* t = n;
+        n = n->next;
+
+#ifndef XSDE_CUSTOM_ALLOCATOR
+        operator delete (t);
+#else
+        cxx::free (t);
+#endif
+      }
+    }
+
 #ifdef XSDE_EXCEPTIONS
     void stack::
 #else
     stack::error stack::
 #endif
-    grow ()
+    push_impl ()
     {
-      size_t c = capacity_ ? capacity_ * 2 : 8;
+      bool first = (cap_ == 1);
+      block*& n = first ? next_ : cur_->next;
+      size_t c = first ? 8 : cap_ * 2;
 
+      if (n == 0)
+      {
 #ifndef XSDE_CUSTOM_ALLOCATOR
-      char* d = static_cast<char*> (operator new (c * el_size_));
+        n = static_cast<block*> (operator new (sizeof (block) + c * el_size_));
 #else
-      char* d = static_cast<char*> (alloc (c * el_size_));
+        n = static_cast<block*> (alloc (sizeof (block) + c * el_size_));
 #endif
 
 #ifndef XSDE_EXCEPTIONS
-      if (d == 0)
-        return error_no_memory;
-#endif
-
-      if (size_ > 1)
-        memcpy (d, data_, (size_ - 1) * el_size_);
-
-#ifndef XSDE_CUSTOM_ALLOCATOR
-      operator delete (data_);
-#else
-      cxx::free (data_);
+        if (n == 0)
+          return error_no_memory;
 #endif
+        n->next = 0;
+        n->prev = cur_;
+      }
 
-      data_ = d;
-      capacity_ = c;
+      cur_ = n;
+      cap_ = c;
+      num_ = 1;
 
 #ifndef XSDE_EXCEPTIONS
       return error_none;
 #endif
     }
+
+    size_t stack::
+    size () const
+    {
+      size_t r = num_;
+
+      for (size_t c = cap_; c != 1;)
+      {
+        c = c == 8 ? 1 : c / 2;
+        r += c;
+      }
+
+      return r;
+    }
   }
 }
diff --git a/libxsde/xsde/cxx/stack.hxx b/libxsde/xsde/cxx/stack.hxx
index 5270a10..a8f26f2 100644
--- a/libxsde/xsde/cxx/stack.hxx
+++ b/libxsde/xsde/cxx/stack.hxx
@@ -54,6 +54,8 @@ namespace xsde
       bool
       empty () const;
 
+      // Note: expensive, non-inline function.
+      //
       size_t
       size () const;
 
@@ -66,14 +68,28 @@ namespace xsde
 #else
       error
 #endif
-      grow ();
+      push_impl ();
 
     private:
-      size_t el_size_;
-      void* first_;
-      char* data_;
-      size_t size_;
-      size_t capacity_;
+      // The stack is implemented as a doubly-linked list of memory
+      // regions. The first region is special since it is the single,
+      // pre-allocated element. It also doesn't have the embedded
+      // 'next' and 'prev' fields. Instead, the next_ member is used
+      // for this purpose. The memory blocks have fixed sizes: 1, 8,
+      // 16, ... elements.
+      //
+      struct block
+      {
+        block* prev;
+        block* next;
+        char data[0]; // Sufficiently padded (2 * sizeof(void*)).
+      };
+
+      size_t el_size_; // Element size in bytes.
+      block* cur_;     // Current block (the first element if cap_ == 1).
+      block* next_;    // Next block of the special first block.
+      size_t cap_;     // Capacity of the current block in elements.
+      size_t num_;     // Number of elements in the current block.
     };
   }
 }
diff --git a/libxsde/xsde/cxx/stack.ixx b/libxsde/xsde/cxx/stack.ixx
index bef310e..1f947df 100644
--- a/libxsde/xsde/cxx/stack.ixx
+++ b/libxsde/xsde/cxx/stack.ixx
@@ -14,30 +14,33 @@ namespace xsde
   namespace cxx
   {
     inline stack::
-    ~stack ()
-    {
-      if (data_)
-#ifndef XSDE_CUSTOM_ALLOCATOR
-        operator delete (data_);
-#else
-        cxx::free (data_);
-#endif
-    }
-
-    inline stack::
     stack (size_t el_size, void* first_el)
         : el_size_ (el_size),
-          first_ (first_el),
-          data_ (0),
-          size_ (0),
-          capacity_ (0)
+          cur_ (static_cast<block*> (first_el)),
+          next_ (0),
+          cap_ (1),
+          num_ (0)
     {
     }
 
     inline void stack::
     pop ()
     {
-      --size_;
+      if (cap_ == 1)
+        --num_;
+      else
+      {
+        if (num_ > 1)
+          --num_;
+        else
+        {
+          // Move to the previous block.
+          //
+          cap_ = cur_ == next_ ? 1 : cap_ / 2;
+          cur_ = cur_->prev;
+          num_ = cap_;
+        }
+      }
     }
 
 #ifdef XSDE_EXCEPTIONS
@@ -47,45 +50,47 @@ namespace xsde
 #endif
     push ()
     {
-      if (size_ > capacity_)
+      if (num_ < cap_)
+      {
+        num_++;
+#ifndef XSDE_EXCEPTIONS
+        return error_none;
+#endif
+      }
+      else
       {
 #ifdef XSDE_EXCEPTIONS
-        grow ();
+        push_impl ();
 #else
-        if (error e = grow ())
-          return e;
+        return push_impl ();
 #endif
       }
-
-      ++size_;
-
-#ifndef XSDE_EXCEPTIONS
-      return error_none;
-#endif
     }
 
     inline void* stack::
     top ()
     {
-      return size_ == 1 ? first_ : data_ + (size_ - 2) * el_size_;
+      return cap_ == 1
+        ? static_cast<void*> (cur_)
+        : static_cast<void*> (cur_->data + (num_ - 1) * el_size_);
     }
 
     inline void stack::
     clear ()
     {
-      size_ = 0;
+      cap_ = 1;
+      num_ = 0;
+
+      // Reset cur_ to the first block.
+      //
+      if (next_)
+        cur_ = next_->prev;
     }
 
     inline bool stack::
     empty () const
     {
-      return size_ == 0;
-    }
-
-    inline size_t stack::
-    size () const
-    {
-      return size_;
+      return num_ == 0;
     }
 
     inline size_t stack::