Reimplement state stack not to move elements

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

8 files changed, 405 insertions, 66 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::
diff --git a/tests/cxx/parser/recursive/driver.cxx b/tests/cxx/parser/recursive/driver.cxx
index f961d76..bcbbd2e 100644
--- a/tests/cxx/parser/recursive/driver.cxx
+++ b/tests/cxx/parser/recursive/driver.cxx
@@ -91,6 +91,78 @@ struct indir_pimpl: indir_type_pskel
   }
 };
 
+struct a_pimpl: a_pskel
+{
+  virtual void
+  pre ()
+  {
+    cout << "a::pre" << endl;
+  }
+
+  virtual void
+  a ()
+  {
+    cout << "a::a" << endl;
+  }
+
+  virtual void
+  b ()
+  {
+    cout << "a::b" << endl;
+  }
+
+#ifdef XSDE_STL
+  virtual void
+  name (string const& n)
+  {
+    cout << "a::name: " << n << endl;
+  }
+#else
+  virtual void
+  name (char* n)
+  {
+    cout << "a::name: " << n << endl;
+    delete[] n;
+  }
+#endif
+
+  virtual void
+  post_a ()
+  {
+    cout << "a::post" << endl;
+  }
+};
+
+struct b_pimpl: b_pskel
+{
+  virtual void
+  pre ()
+  {
+    cout << "b::pre" << endl;
+  }
+
+#ifdef XSDE_STL
+  virtual void
+  name (string const& n)
+  {
+    cout << "b::name: " << n << endl;
+  }
+#else
+  virtual void
+  name (char* n)
+  {
+    cout << "b::name: " << n << endl;
+    delete[] n;
+  }
+#endif
+
+  virtual void
+  post_b ()
+  {
+    cout << "b::post" << endl;
+  }
+};
+
 struct test_pimpl: test_type_pskel
 {
   virtual void
@@ -105,6 +177,12 @@ struct test_pimpl: test_type_pskel
     cout << "test::sub" << endl;
   }
 
+  virtual void
+  a ()
+  {
+    cout << "test::a" << endl;
+  }
+
 #ifdef XSDE_STL
   virtual void
   name (string const& n)
@@ -143,11 +221,19 @@ main (int argc, char* argv[])
 
     sub_pimpl sub_p;
     indir_pimpl indir_p;
+
+    a_pimpl a_p;
+    b_pimpl b_p;
+
     test_pimpl test_p;
 
     sub_p.parsers (string_p, sub_p, indir_p, sub_p);
     indir_p.parsers (string_p, sub_p);
-    test_p.parsers (string_p, sub_p);
+
+    a_p.parsers (string_p, a_p, b_p);
+    b_p.parsers (string_p);
+
+    test_p.parsers (string_p, sub_p, a_p);
 
     xml_schema::document_pimpl doc_p (test_p, "test");
 
diff --git a/tests/cxx/parser/recursive/makefile b/tests/cxx/parser/recursive/makefile
index 7b9d36f..79307b7 100644
--- a/tests/cxx/parser/recursive/makefile
+++ b/tests/cxx/parser/recursive/makefile
@@ -8,6 +8,8 @@ include $(dir $(lastword $(MAKEFILE_LIST)))../../../../build/bootstrap.make
 xsd := test.xsd
 cxx := driver.cxx
 
+tests := 000 001
+
 obj := $(addprefix $(out_base)/,$(cxx:.cxx=.o) $(xsd:.xsd=-pskel.o))
 dep := $(obj:.o=.o.d)
 
@@ -43,9 +45,14 @@ $(out_base)/: $(driver)
 
 # Test.
 #
-$(test): driver := $(driver)
-$(test): $(driver) $(src_base)/test-000.xml $(src_base)/test-000.std
-	$(call message,test $$1,$$1 $(src_base)/test-000.xml | diff -u $(src_base)/test-000.std -,$(driver))
+test_targets := $(addprefix $(out_base)/.test-,$(tests))
+
+$(test): $(test_targets)
+$(test_targets): driver := $(driver)
+
+.PHONY: $(out_base)/.test-%
+$(out_base)/.test-%: $(driver) $(src_base)/test.xsd $(src_base)/test-%.xml $(src_base)/test-%.std
+	$(call message,test $(out_base)/$*,$(driver) $(src_base)/test-$*.xml | diff -u $(src_base)/test-$*.std -)
 
 
 # Dist.
diff --git a/tests/cxx/parser/recursive/test-001.std b/tests/cxx/parser/recursive/test-001.std
new file mode 100644
index 0000000..9acdc4c
--- /dev/null
+++ b/tests/cxx/parser/recursive/test-001.std
@@ -0,0 +1,123 @@
+test::pre
+test::name: testName
+a::pre
+a::name: 1
+b::pre
+b::name: b1
+b::post
+a::b
+a::pre
+a::name: 2
+b::pre
+b::name: b1
+b::post
+a::b
+a::pre
+a::name: 3
+b::pre
+b::name: b3
+b::post
+a::b
+a::pre
+a::name: 4
+b::pre
+b::name: b4
+b::post
+a::b
+a::pre
+a::name: 5
+b::pre
+b::name: b5
+b::post
+a::b
+a::pre
+a::name: 6
+b::pre
+b::name: b6
+b::post
+a::b
+a::pre
+a::name: 7
+b::pre
+b::name: b7
+b::post
+a::b
+a::pre
+a::name: 8
+b::pre
+b::name: b8
+b::post
+a::b
+a::pre
+a::name: 9
+b::pre
+b::name: b9
+b::post
+a::b
+a::pre
+a::name: 10
+b::pre
+b::name: b10
+b::post
+a::b
+a::pre
+a::name: 11
+b::pre
+b::name: b11
+b::post
+a::b
+a::pre
+a::name: 12
+b::pre
+b::name: b12
+b::post
+a::b
+a::pre
+a::name: 13
+b::pre
+b::name: b13
+b::post
+a::b
+a::pre
+a::name: 14
+b::pre
+b::name: b14
+b::post
+a::b
+a::pre
+a::name: 15
+b::pre
+b::name: b15
+b::post
+a::b
+a::post
+a::a
+a::post
+a::a
+a::post
+a::a
+a::post
+a::a
+a::post
+a::a
+a::post
+a::a
+a::post
+a::a
+a::post
+a::a
+a::post
+a::a
+a::post
+a::a
+a::post
+a::a
+a::post
+a::a
+a::post
+a::a
+a::post
+a::a
+a::post
+test::a
+test::post
diff --git a/tests/cxx/parser/recursive/test-001.xml b/tests/cxx/parser/recursive/test-001.xml
new file mode 100644
index 0000000..d90bf23
--- /dev/null
+++ b/tests/cxx/parser/recursive/test-001.xml
@@ -0,0 +1,50 @@
+<test xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
+      xsi:noNamespaceSchemaLocation="test.xsd"
+      name="testName">
+<a name="1">
+    <b name="b1"/>
+<a name="2">
+    <b name="b1"/>
+<a name="3">
+    <b name="b3"/>
+<a name="4">
+    <b name="b4"/>
+<a name="5">
+    <b name="b5"/>
+<a name="6">
+    <b name="b6"/>
+<a name="7">
+    <b name="b7"/>
+<a name="8">
+    <b name="b8"/>
+<a name="9">
+    <b name="b9"/>
+<a name="10">
+    <b name="b10"/>
+<a name="11">
+    <b name="b11"/>
+<a name="12">
+    <b name="b12"/>
+<a name="13">
+    <b name="b13"/>
+<a name="14">
+    <b name="b14"/>
+<a name="15">
+    <b name="b15"/>
+
+</a>
+</a>
+</a>
+</a>
+</a>
+</a>
+</a>
+</a>
+</a>
+</a>
+</a>
+</a>
+</a>
+</a>
+</a>
+</test>
diff --git a/tests/cxx/parser/recursive/test.xsd b/tests/cxx/parser/recursive/test.xsd
index 33e1d2d..0723ca2 100644
--- a/tests/cxx/parser/recursive/test.xsd
+++ b/tests/cxx/parser/recursive/test.xsd
@@ -1,5 +1,7 @@
 <xs:schema xmlns:xs="http://www.w3.org/2001/XMLSchema">
 
+  <!-- test 1 -->
+
   <xs:complexType name="sub_type">
     <xs:sequence>
       <xs:element name="sub" type="sub_type" minOccurs="0"/>
@@ -16,10 +18,33 @@
     <xs:attribute name="name" type="xs:string" />
   </xs:complexType>
 
+  <!-- test 2 -->
+
+  <xs:element name="a">
+    <xs:complexType>
+      <xs:sequence>
+        <xs:choice maxOccurs="unbounded">
+          <xs:element ref="a" />
+          <xs:element ref="b" />
+        </xs:choice>
+      </xs:sequence>
+      <xs:attribute name="name" type="xs:string" use="required"/>
+    </xs:complexType>
+  </xs:element>
+
+  <xs:element name="b">
+    <xs:complexType>
+      <xs:attribute name="name" type="xs:string"/>
+    </xs:complexType>
+  </xs:element>
+
+  <!-- root -->
+
   <xs:complexType name="test_type">
-    <xs:sequence>
+    <xs:choice>
       <xs:element name="sub" type="sub_type" />
-    </xs:sequence>
+      <xs:element ref="a"/>
+    </xs:choice>
     <xs:attribute name="name" type="xs:string" />
   </xs:complexType>