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