diff options
author | Boris Kolpackov <boris@codesynthesis.com> | 2010-08-27 19:55:14 +0200 |
---|---|---|
committer | Boris Kolpackov <boris@codesynthesis.com> | 2010-08-27 19:55:14 +0200 |
commit | 14b909b25dec8e68f7bcb35e89ce503c5f12967c (patch) | |
tree | b6ed37a611d99eb5e3110a4a048e55b4ca447e47 /libxsde | |
parent | 686b15bcd3d9045fdb4679970b0f39466125abf8 (diff) |
Reimplement state stack not to move elements
Add another recursive parsing test that forces second allocation
in the stack.
Diffstat (limited to 'libxsde')
-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 |
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:: |