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