1 /////////////////////////////////////////////////////////////////////////////// 2 // sequence_stack.hpp 3 // 4 // Copyright 2008 Eric Niebler. Distributed under the Boost 5 // Software License, Version 1.0. (See accompanying file 6 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 7 8 #ifndef BOOST_XPRESSIVE_DETAIL_SEQUENCE_STACK_HPP_EAN_10_04_2005 9 #define BOOST_XPRESSIVE_DETAIL_SEQUENCE_STACK_HPP_EAN_10_04_2005 10 11 // MS compatible compilers support #pragma once 12 #if defined(_MSC_VER) && (_MSC_VER >= 1020) 13 # pragma once 14 # pragma warning(push) 15 # pragma warning(disable : 4127) // conditional expression constant 16 #endif 17 18 #include <algorithm> 19 #include <functional> 20 21 namespace boost { namespace xpressive { namespace detail 22 { 23 24 ////////////////////////////////////////////////////////////////////////// 25 // sequence_stack 26 // 27 // For storing a stack of sequences of type T, where each sequence 28 // is guaranteed to be stored in contiguous memory. 29 template<typename T> 30 struct sequence_stack 31 { 32 private: 33 34 struct chunk 35 { chunkboost::xpressive::detail::sequence_stack::chunk36 chunk(std::size_t size, std::size_t count, chunk *back, chunk *next) 37 : begin_(new T[ size ]) 38 , curr_(begin_ + count) 39 , end_(begin_ + size) 40 , back_(back) 41 , next_(next) 42 { 43 if(this->back_) 44 this->back_->next_ = this; 45 if(this->next_) 46 this->next_->back_ = this; 47 } 48 ~chunkboost::xpressive::detail::sequence_stack::chunk49 ~chunk() 50 { 51 delete[] this->begin_; 52 } 53 sizeboost::xpressive::detail::sequence_stack::chunk54 std::size_t size() const 55 { 56 return static_cast<std::size_t>(this->end_ - this->begin_); 57 } 58 59 T *const begin_, *curr_, *const end_; 60 chunk *back_, *next_; 61 62 private: 63 chunk &operator =(chunk const &); 64 }; 65 66 chunk *current_chunk_; 67 68 // Cache these for faster access 69 T *begin_; 70 T *curr_; 71 T *end_; 72 grow_boost::xpressive::detail::sequence_stack73 T *grow_(std::size_t count) 74 { 75 if(this->current_chunk_) 76 { 77 // write the cached value of current into the expr. 78 // OK to do this even if later statements throw. 79 this->current_chunk_->curr_ = this->curr_; 80 81 // Do we have a expr with enough available memory already? 82 if(this->current_chunk_->next_ && count <= this->current_chunk_->next_->size()) 83 { 84 this->current_chunk_ = this->current_chunk_->next_; 85 this->curr_ = this->current_chunk_->curr_ = this->current_chunk_->begin_ + count; 86 this->end_ = this->current_chunk_->end_; 87 this->begin_ = this->current_chunk_->begin_; 88 std::fill_n(this->begin_, count, T()); 89 return this->begin_; 90 } 91 92 // grow exponentially 93 std::size_t new_size = (std::max)(count, static_cast<std::size_t>(this->current_chunk_->size() * 1.5)); 94 95 // Create a new expr and insert it into the list 96 this->current_chunk_ = new chunk(new_size, count, this->current_chunk_, this->current_chunk_->next_); 97 } 98 else 99 { 100 // first chunk is 256 101 std::size_t new_size = (std::max)(count, static_cast<std::size_t>(256U)); 102 103 // Create a new expr and insert it into the list 104 this->current_chunk_ = new chunk(new_size, count, 0, 0); 105 } 106 107 this->begin_ = this->current_chunk_->begin_; 108 this->curr_ = this->current_chunk_->curr_; 109 this->end_ = this->current_chunk_->end_; 110 return this->begin_; 111 } 112 unwind_chunk_boost::xpressive::detail::sequence_stack113 void unwind_chunk_() 114 { 115 // write the cached value of curr_ into current_chunk_ 116 this->current_chunk_->curr_ = this->begin_; 117 // make the previous chunk the current 118 this->current_chunk_ = this->current_chunk_->back_; 119 120 // update the cache 121 this->begin_ = this->current_chunk_->begin_; 122 this->curr_ = this->current_chunk_->curr_; 123 this->end_ = this->current_chunk_->end_; 124 } 125 in_current_chunkboost::xpressive::detail::sequence_stack126 bool in_current_chunk(T *ptr) const 127 { 128 return !std::less<void*>()(ptr, this->begin_) && std::less<void*>()(ptr, this->end_); 129 } 130 131 public: sequence_stackboost::xpressive::detail::sequence_stack132 sequence_stack() 133 : current_chunk_(0) 134 , begin_(0) 135 , curr_(0) 136 , end_(0) 137 { 138 } 139 ~sequence_stackboost::xpressive::detail::sequence_stack140 ~sequence_stack() 141 { 142 this->clear(); 143 } 144 145 // walk to the front of the linked list unwindboost::xpressive::detail::sequence_stack146 void unwind() 147 { 148 if(this->current_chunk_) 149 { 150 while(this->current_chunk_->back_) 151 { 152 this->current_chunk_->curr_ = this->current_chunk_->begin_; 153 this->current_chunk_ = this->current_chunk_->back_; 154 } 155 156 this->begin_ = this->curr_ = this->current_chunk_->curr_ = this->current_chunk_->begin_; 157 this->end_ = this->current_chunk_->end_; 158 } 159 } 160 clearboost::xpressive::detail::sequence_stack161 void clear() 162 { 163 // walk to the front of the list 164 this->unwind(); 165 166 // delete the list 167 for(chunk *next; this->current_chunk_; this->current_chunk_ = next) 168 { 169 next = this->current_chunk_->next_; 170 delete this->current_chunk_; 171 } 172 173 this->begin_ = this->curr_ = this->end_ = 0; 174 } 175 176 template<bool Fill> push_sequenceboost::xpressive::detail::sequence_stack177 T *push_sequence(std::size_t count, mpl::bool_<Fill>) 178 { 179 // This is the ptr to return 180 T *ptr = this->curr_; 181 182 // Advance the high-water mark 183 this->curr_ += count; 184 185 // Check to see if we have overflowed this buffer 186 if(std::less<void*>()(this->end_, this->curr_)) 187 { 188 // oops, back this out. 189 this->curr_ = ptr; 190 191 // allocate a new block and return a ptr to the new memory 192 return this->grow_(count); 193 } 194 195 if(Fill) 196 { 197 std::fill_n(ptr, count, T()); 198 } 199 200 return ptr; 201 } 202 push_sequenceboost::xpressive::detail::sequence_stack203 T *push_sequence(std::size_t count) 204 { 205 return this->push_sequence(count, mpl::true_()); 206 } 207 unwind_toboost::xpressive::detail::sequence_stack208 void unwind_to(T *ptr) 209 { 210 while(!this->in_current_chunk(ptr)) 211 { 212 // completely unwind the current chunk, move to the previous chunk 213 this->unwind_chunk_(); 214 } 215 this->current_chunk_->curr_ = this->curr_ = ptr; 216 } 217 218 // shrink-to-fit: remove any unused nodes in the chain conserveboost::xpressive::detail::sequence_stack219 void conserve() 220 { 221 if(this->current_chunk_) 222 { 223 for(chunk *next; this->current_chunk_->next_; this->current_chunk_->next_ = next) 224 { 225 next = this->current_chunk_->next_->next_; 226 delete this->current_chunk_->next_; 227 } 228 } 229 } 230 }; 231 232 typedef mpl::false_ no_fill_t; 233 no_fill_t const no_fill = {}; 234 235 }}} // namespace boost::xpressive::detail 236 237 #if defined(_MSC_VER) && (_MSC_VER >= 1020) 238 # pragma warning(pop) 239 #endif 240 241 #endif 242