diff options
-rw-r--r-- | libxsde/xsde/cxx/stack.cxx | 65 | ||||
-rw-r--r-- | libxsde/xsde/cxx/stack.hxx | 28 | ||||
-rw-r--r-- | libxsde/xsde/cxx/stack.ixx | 75 | ||||
-rw-r--r-- | tests/cxx/parser/recursive/driver.cxx | 88 | ||||
-rw-r--r-- | tests/cxx/parser/recursive/makefile | 13 | ||||
-rw-r--r-- | tests/cxx/parser/recursive/test-001.std | 123 | ||||
-rw-r--r-- | tests/cxx/parser/recursive/test-001.xml | 50 | ||||
-rw-r--r-- | tests/cxx/parser/recursive/test.xsd | 29 |
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> |