]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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) | |
13 | # pragma once | |
14 | # pragma warning(push) | |
15 | # pragma warning(disable : 4127) // conditional expression constant | |
16 | #endif | |
17 | ||
20effc67 | 18 | #include <cstddef> |
7c673cae FG |
19 | #include <algorithm> |
20 | #include <functional> | |
21 | ||
22 | namespace boost { namespace xpressive { namespace detail | |
23 | { | |
24 | ||
25 | struct fill_t {} const fill = {}; | |
26 | ||
27 | ////////////////////////////////////////////////////////////////////////// | |
28 | // sequence_stack | |
29 | // | |
30 | // For storing a stack of sequences of type T, where each sequence | |
31 | // is guaranteed to be stored in contiguous memory. | |
32 | template<typename T> | |
33 | struct sequence_stack | |
34 | { | |
35 | struct allocate_guard_t; | |
36 | friend struct allocate_guard_t; | |
37 | struct allocate_guard_t | |
38 | { | |
39 | std::size_t i; | |
40 | T *p; | |
41 | bool dismissed; | |
42 | ~allocate_guard_t() | |
43 | { | |
44 | if(!this->dismissed) | |
45 | sequence_stack::deallocate(this->p, this->i); | |
46 | } | |
47 | }; | |
48 | private: | |
49 | static T *allocate(std::size_t size, T const &t) | |
50 | { | |
51 | allocate_guard_t guard = {0, (T *)::operator new(size * sizeof(T)), false}; | |
52 | ||
53 | for(; guard.i < size; ++guard.i) | |
54 | ::new((void *)(guard.p + guard.i)) T(t); | |
55 | guard.dismissed = true; | |
56 | ||
57 | return guard.p; | |
58 | } | |
59 | ||
60 | static void deallocate(T *p, std::size_t i) | |
61 | { | |
62 | while(i-- > 0) | |
63 | (p+i)->~T(); | |
64 | ::operator delete(p); | |
65 | } | |
66 | ||
67 | struct chunk | |
68 | { | |
69 | chunk(std::size_t size, T const &t, std::size_t count, chunk *back, chunk *next) | |
70 | : begin_(allocate(size, t)) | |
71 | , curr_(begin_ + count) | |
72 | , end_(begin_ + size) | |
73 | , back_(back) | |
74 | , next_(next) | |
75 | { | |
76 | if(this->back_) | |
77 | this->back_->next_ = this; | |
78 | if(this->next_) | |
79 | this->next_->back_ = this; | |
80 | } | |
81 | ||
82 | ~chunk() | |
83 | { | |
84 | deallocate(this->begin_, this->size()); | |
85 | } | |
86 | ||
87 | std::size_t size() const | |
88 | { | |
89 | return static_cast<std::size_t>(this->end_ - this->begin_); | |
90 | } | |
91 | ||
92 | T *const begin_, *curr_, *const end_; | |
93 | chunk *back_, *next_; | |
94 | ||
95 | private: | |
96 | chunk &operator =(chunk const &); | |
97 | }; | |
98 | ||
99 | chunk *current_chunk_; | |
100 | ||
101 | // Cache these for faster access | |
102 | T *begin_; | |
103 | T *curr_; | |
104 | T *end_; | |
105 | ||
106 | T *grow_(std::size_t count, T const &t) | |
107 | { | |
108 | if(this->current_chunk_) | |
109 | { | |
110 | // write the cached value of current into the expr. | |
111 | // OK to do this even if later statements throw. | |
112 | this->current_chunk_->curr_ = this->curr_; | |
113 | ||
114 | // Do we have a expr with enough available memory already? | |
115 | if(this->current_chunk_->next_ && count <= this->current_chunk_->next_->size()) | |
116 | { | |
117 | this->current_chunk_ = this->current_chunk_->next_; | |
118 | this->curr_ = this->current_chunk_->curr_ = this->current_chunk_->begin_ + count; | |
119 | this->end_ = this->current_chunk_->end_; | |
120 | this->begin_ = this->current_chunk_->begin_; | |
121 | std::fill_n(this->begin_, count, t); | |
122 | return this->begin_; | |
123 | } | |
124 | ||
125 | // grow exponentially | |
126 | std::size_t new_size = (std::max)( | |
127 | count | |
128 | , static_cast<std::size_t>(static_cast<double>(this->current_chunk_->size()) * 1.5) | |
129 | ); | |
130 | ||
131 | // Create a new expr and insert it into the list | |
132 | this->current_chunk_ = new chunk(new_size, t, count, this->current_chunk_, this->current_chunk_->next_); | |
133 | } | |
134 | else | |
135 | { | |
136 | // first chunk is 256 | |
137 | std::size_t new_size = (std::max)(count, static_cast<std::size_t>(256U)); | |
138 | ||
139 | // Create a new expr and insert it into the list | |
140 | this->current_chunk_ = new chunk(new_size, t, count, 0, 0); | |
141 | } | |
142 | ||
143 | this->begin_ = this->current_chunk_->begin_; | |
144 | this->curr_ = this->current_chunk_->curr_; | |
145 | this->end_ = this->current_chunk_->end_; | |
146 | return this->begin_; | |
147 | } | |
148 | ||
149 | void unwind_chunk_() | |
150 | { | |
151 | // write the cached value of curr_ into current_chunk_ | |
152 | this->current_chunk_->curr_ = this->begin_; | |
153 | // make the previous chunk the current | |
154 | this->current_chunk_ = this->current_chunk_->back_; | |
155 | ||
156 | // update the cache | |
157 | this->begin_ = this->current_chunk_->begin_; | |
158 | this->curr_ = this->current_chunk_->curr_; | |
159 | this->end_ = this->current_chunk_->end_; | |
160 | } | |
161 | ||
162 | bool in_current_chunk(T *ptr) const | |
163 | { | |
164 | return !std::less<void*>()(ptr, this->begin_) && std::less<void*>()(ptr, this->end_); | |
165 | } | |
166 | ||
167 | public: | |
168 | sequence_stack() | |
169 | : current_chunk_(0) | |
170 | , begin_(0) | |
171 | , curr_(0) | |
172 | , end_(0) | |
173 | { | |
174 | } | |
175 | ||
176 | ~sequence_stack() | |
177 | { | |
178 | this->clear(); | |
179 | } | |
180 | ||
181 | // walk to the front of the linked list | |
182 | void unwind() | |
183 | { | |
184 | if(this->current_chunk_) | |
185 | { | |
186 | while(this->current_chunk_->back_) | |
187 | { | |
188 | this->current_chunk_->curr_ = this->current_chunk_->begin_; | |
189 | this->current_chunk_ = this->current_chunk_->back_; | |
190 | } | |
191 | ||
192 | this->begin_ = this->curr_ = this->current_chunk_->curr_ = this->current_chunk_->begin_; | |
193 | this->end_ = this->current_chunk_->end_; | |
194 | } | |
195 | } | |
196 | ||
197 | void clear() | |
198 | { | |
199 | // walk to the front of the list | |
200 | this->unwind(); | |
201 | ||
202 | // delete the list | |
203 | for(chunk *next; this->current_chunk_; this->current_chunk_ = next) | |
204 | { | |
205 | next = this->current_chunk_->next_; | |
206 | delete this->current_chunk_; | |
207 | } | |
208 | ||
209 | this->begin_ = this->curr_ = this->end_ = 0; | |
210 | } | |
211 | ||
212 | T *push_sequence(std::size_t count, T const &t) | |
213 | { | |
7c673cae | 214 | // Check to see if we have overflowed this buffer |
20effc67 TL |
215 | std::size_t size_left = static_cast< std::size_t >(this->end_ - this->curr_); |
216 | if (size_left < count) | |
7c673cae | 217 | { |
7c673cae FG |
218 | // allocate a new block and return a ptr to the new memory |
219 | return this->grow_(count, t); | |
220 | } | |
221 | ||
20effc67 TL |
222 | // This is the ptr to return |
223 | T *ptr = this->curr_; | |
224 | ||
225 | // Advance the high-water mark | |
226 | this->curr_ += count; | |
227 | ||
7c673cae FG |
228 | return ptr; |
229 | } | |
230 | ||
231 | T *push_sequence(std::size_t count, T const &t, fill_t) | |
232 | { | |
233 | T *ptr = this->push_sequence(count, t); | |
234 | std::fill_n(ptr, count, t); | |
235 | return ptr; | |
236 | } | |
237 | ||
238 | void unwind_to(T *ptr) | |
239 | { | |
240 | while(!this->in_current_chunk(ptr)) | |
241 | { | |
242 | // completely unwind the current chunk, move to the previous chunk | |
243 | this->unwind_chunk_(); | |
244 | } | |
245 | this->current_chunk_->curr_ = this->curr_ = ptr; | |
246 | } | |
247 | ||
248 | // shrink-to-fit: remove any unused nodes in the chain | |
249 | void conserve() | |
250 | { | |
251 | if(this->current_chunk_) | |
252 | { | |
253 | for(chunk *next; this->current_chunk_->next_; this->current_chunk_->next_ = next) | |
254 | { | |
255 | next = this->current_chunk_->next_->next_; | |
256 | delete this->current_chunk_->next_; | |
257 | } | |
258 | } | |
259 | } | |
260 | }; | |
261 | ||
262 | }}} // namespace boost::xpressive::detail | |
263 | ||
264 | #if defined(_MSC_VER) | |
265 | # pragma warning(pop) | |
266 | #endif | |
267 | ||
268 | #endif |