Chris@16: ///////////////////////////////////////////////////////////////////////////////
Chris@16: // sequence_stack.hpp
Chris@16: //
Chris@16: //  Copyright 2008 Eric Niebler. Distributed under the Boost
Chris@16: //  Software License, Version 1.0. (See accompanying file
Chris@16: //  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #ifndef BOOST_XPRESSIVE_DETAIL_SEQUENCE_STACK_HPP_EAN_10_04_2005
Chris@16: #define BOOST_XPRESSIVE_DETAIL_SEQUENCE_STACK_HPP_EAN_10_04_2005
Chris@16: 
Chris@16: // MS compatible compilers support #pragma once
Chris@101: #if defined(_MSC_VER)
Chris@16: # pragma once
Chris@16: # pragma warning(push)
Chris@16: # pragma warning(disable : 4127) // conditional expression constant
Chris@16: #endif
Chris@16: 
Chris@16: #include <algorithm>
Chris@16: #include <functional>
Chris@16: 
Chris@16: namespace boost { namespace xpressive { namespace detail
Chris@16: {
Chris@16: 
Chris@16: struct fill_t {} const fill = {};
Chris@16: 
Chris@16: //////////////////////////////////////////////////////////////////////////
Chris@16: // sequence_stack
Chris@16: //
Chris@16: //   For storing a stack of sequences of type T, where each sequence
Chris@16: //   is guaranteed to be stored in contiguous memory.
Chris@16: template<typename T>
Chris@16: struct sequence_stack
Chris@16: {
Chris@16:     struct allocate_guard_t;
Chris@16:     friend struct allocate_guard_t;
Chris@16:     struct allocate_guard_t
Chris@16:     {
Chris@16:         std::size_t i;
Chris@16:         T *p;
Chris@16:         bool dismissed;
Chris@16:         ~allocate_guard_t()
Chris@16:         {
Chris@16:             if(!this->dismissed)
Chris@16:                 sequence_stack::deallocate(this->p, this->i);
Chris@16:         }
Chris@16:     };
Chris@16: private:
Chris@16:     static T *allocate(std::size_t size, T const &t)
Chris@16:     {
Chris@16:         allocate_guard_t guard = {0, (T *)::operator new(size * sizeof(T)), false};
Chris@16: 
Chris@16:         for(; guard.i < size; ++guard.i)
Chris@16:             ::new((void *)(guard.p + guard.i)) T(t);
Chris@16:         guard.dismissed = true;
Chris@16: 
Chris@16:         return guard.p;
Chris@16:     }
Chris@16: 
Chris@16:     static void deallocate(T *p, std::size_t i)
Chris@16:     {
Chris@16:         while(i-- > 0)
Chris@16:             (p+i)->~T();
Chris@16:         ::operator delete(p);
Chris@16:     }
Chris@16: 
Chris@16:     struct chunk
Chris@16:     {
Chris@16:         chunk(std::size_t size, T const &t, std::size_t count, chunk *back, chunk *next)
Chris@16:           : begin_(allocate(size, t))
Chris@16:           , curr_(begin_ + count)
Chris@16:           , end_(begin_ + size)
Chris@16:           , back_(back)
Chris@16:           , next_(next)
Chris@16:         {
Chris@16:             if(this->back_)
Chris@16:                 this->back_->next_ = this;
Chris@16:             if(this->next_)
Chris@16:                 this->next_->back_ = this;
Chris@16:         }
Chris@16: 
Chris@16:         ~chunk()
Chris@16:         {
Chris@16:             deallocate(this->begin_, this->size());
Chris@16:         }
Chris@16: 
Chris@16:         std::size_t size() const
Chris@16:         {
Chris@16:             return static_cast<std::size_t>(this->end_ - this->begin_);
Chris@16:         }
Chris@16: 
Chris@16:         T *const begin_, *curr_, *const end_;
Chris@16:         chunk *back_, *next_;
Chris@16: 
Chris@16:     private:
Chris@16:         chunk &operator =(chunk const &);
Chris@16:     };
Chris@16: 
Chris@16:     chunk *current_chunk_;
Chris@16: 
Chris@16:     // Cache these for faster access
Chris@16:     T *begin_;
Chris@16:     T *curr_;
Chris@16:     T *end_;
Chris@16: 
Chris@16:     T *grow_(std::size_t count, T const &t)
Chris@16:     {
Chris@16:         if(this->current_chunk_)
Chris@16:         {
Chris@16:             // write the cached value of current into the expr.
Chris@16:             // OK to do this even if later statements throw.
Chris@16:             this->current_chunk_->curr_ = this->curr_;
Chris@16: 
Chris@16:             // Do we have a expr with enough available memory already?
Chris@16:             if(this->current_chunk_->next_ && count <= this->current_chunk_->next_->size())
Chris@16:             {
Chris@16:                 this->current_chunk_ = this->current_chunk_->next_;
Chris@16:                 this->curr_ = this->current_chunk_->curr_ = this->current_chunk_->begin_ + count;
Chris@16:                 this->end_ = this->current_chunk_->end_;
Chris@16:                 this->begin_ = this->current_chunk_->begin_;
Chris@16:                 std::fill_n(this->begin_, count, t);
Chris@16:                 return this->begin_;
Chris@16:             }
Chris@16: 
Chris@16:             // grow exponentially
Chris@16:             std::size_t new_size = (std::max)(
Chris@16:                 count
Chris@16:               , static_cast<std::size_t>(static_cast<double>(this->current_chunk_->size()) * 1.5)
Chris@16:             );
Chris@16: 
Chris@16:             // Create a new expr and insert it into the list
Chris@16:             this->current_chunk_ = new chunk(new_size, t, count, this->current_chunk_, this->current_chunk_->next_);
Chris@16:         }
Chris@16:         else
Chris@16:         {
Chris@16:             // first chunk is 256
Chris@16:             std::size_t new_size = (std::max)(count, static_cast<std::size_t>(256U));
Chris@16: 
Chris@16:             // Create a new expr and insert it into the list
Chris@16:             this->current_chunk_ = new chunk(new_size, t, count, 0, 0);
Chris@16:         }
Chris@16: 
Chris@16:         this->begin_ = this->current_chunk_->begin_;
Chris@16:         this->curr_ = this->current_chunk_->curr_;
Chris@16:         this->end_ = this->current_chunk_->end_;
Chris@16:         return this->begin_;
Chris@16:     }
Chris@16: 
Chris@16:     void unwind_chunk_()
Chris@16:     {
Chris@16:         // write the cached value of curr_ into current_chunk_
Chris@16:         this->current_chunk_->curr_ = this->begin_;
Chris@16:         // make the previous chunk the current
Chris@16:         this->current_chunk_ = this->current_chunk_->back_;
Chris@16: 
Chris@16:         // update the cache
Chris@16:         this->begin_ = this->current_chunk_->begin_;
Chris@16:         this->curr_ = this->current_chunk_->curr_;
Chris@16:         this->end_ = this->current_chunk_->end_;
Chris@16:     }
Chris@16: 
Chris@16:     bool in_current_chunk(T *ptr) const
Chris@16:     {
Chris@16:         return !std::less<void*>()(ptr, this->begin_) && std::less<void*>()(ptr, this->end_);
Chris@16:     }
Chris@16: 
Chris@16: public:
Chris@16:     sequence_stack()
Chris@16:       : current_chunk_(0)
Chris@16:       , begin_(0)
Chris@16:       , curr_(0)
Chris@16:       , end_(0)
Chris@16:     {
Chris@16:     }
Chris@16: 
Chris@16:     ~sequence_stack()
Chris@16:     {
Chris@16:         this->clear();
Chris@16:     }
Chris@16: 
Chris@16:     // walk to the front of the linked list
Chris@16:     void unwind()
Chris@16:     {
Chris@16:         if(this->current_chunk_)
Chris@16:         {
Chris@16:             while(this->current_chunk_->back_)
Chris@16:             {
Chris@16:                 this->current_chunk_->curr_ = this->current_chunk_->begin_;
Chris@16:                 this->current_chunk_ = this->current_chunk_->back_;
Chris@16:             }
Chris@16: 
Chris@16:             this->begin_ = this->curr_ = this->current_chunk_->curr_ = this->current_chunk_->begin_;
Chris@16:             this->end_ = this->current_chunk_->end_;
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     void clear()
Chris@16:     {
Chris@16:         // walk to the front of the list
Chris@16:         this->unwind();
Chris@16: 
Chris@16:         // delete the list
Chris@16:         for(chunk *next; this->current_chunk_; this->current_chunk_ = next)
Chris@16:         {
Chris@16:             next = this->current_chunk_->next_;
Chris@16:             delete this->current_chunk_;
Chris@16:         }
Chris@16: 
Chris@16:         this->begin_ = this->curr_ = this->end_ = 0;
Chris@16:     }
Chris@16: 
Chris@16:     T *push_sequence(std::size_t count, T const &t)
Chris@16:     {
Chris@16:         // This is the ptr to return
Chris@16:         T *ptr = this->curr_;
Chris@16: 
Chris@16:         // Advance the high-water mark
Chris@16:         this->curr_ += count;
Chris@16: 
Chris@16:         // Check to see if we have overflowed this buffer
Chris@16:         if(std::less<void*>()(this->end_, this->curr_))
Chris@16:         {
Chris@16:             // oops, back this out.
Chris@16:             this->curr_ = ptr;
Chris@16: 
Chris@16:             // allocate a new block and return a ptr to the new memory
Chris@16:             return this->grow_(count, t);
Chris@16:         }
Chris@16: 
Chris@16:         return ptr;
Chris@16:     }
Chris@16: 
Chris@16:     T *push_sequence(std::size_t count, T const &t, fill_t)
Chris@16:     {
Chris@16:         T *ptr = this->push_sequence(count, t);
Chris@16:         std::fill_n(ptr, count, t);
Chris@16:         return ptr;
Chris@16:     }
Chris@16: 
Chris@16:     void unwind_to(T *ptr)
Chris@16:     {
Chris@16:         while(!this->in_current_chunk(ptr))
Chris@16:         {
Chris@16:             // completely unwind the current chunk, move to the previous chunk
Chris@16:             this->unwind_chunk_();
Chris@16:         }
Chris@16:         this->current_chunk_->curr_ = this->curr_ = ptr;
Chris@16:     }
Chris@16: 
Chris@16:     // shrink-to-fit: remove any unused nodes in the chain
Chris@16:     void conserve()
Chris@16:     {
Chris@16:         if(this->current_chunk_)
Chris@16:         {
Chris@16:             for(chunk *next; this->current_chunk_->next_; this->current_chunk_->next_ = next)
Chris@16:             {
Chris@16:                 next = this->current_chunk_->next_->next_;
Chris@16:                 delete this->current_chunk_->next_;
Chris@16:             }
Chris@16:         }
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: }}} // namespace boost::xpressive::detail
Chris@16: 
Chris@101: #if defined(_MSC_VER)
Chris@16: # pragma warning(pop)
Chris@16: #endif
Chris@16: 
Chris@16: #endif