Line data Source code
1 : //
2 : // Author: Vladimir Migashko <migashko@gmail.com>, (C) 2012
3 : //
4 : // Copyright: See COPYING file that comes with this distribution
5 : //
6 :
7 : #ifndef VSET_MEMORY_FSB_CHAIN_HPP
8 : #define VSET_MEMORY_FSB_CHAIN_HPP
9 :
10 : #include <fas/system/nullptr.hpp>
11 :
12 : namespace vset { namespace memory{ namespace fsb{
13 :
14 : template<typename T, template<typename> class Chunk >
15 : struct chain
16 : {
17 : typedef chain<T, Chunk> self;
18 : typedef Chunk<T> chunk_type;
19 :
20 : size_t size;
21 : mutable size_t first_free;
22 :
23 26 : chain()
24 : : size(0)
25 26 : , first_free(0)
26 26 : {}
27 :
28 : static size_t head_size()
29 : {
30 : return sizeof(self);
31 : }
32 :
33 38 : void acquire(size_t c)
34 : {
35 38 : size += c;
36 38 : }
37 :
38 62559 : chunk_type* first_chunk()
39 : {
40 62559 : return reinterpret_cast<chunk_type*>(this+1);
41 : }
42 :
43 345979 : const chunk_type* first_chunk() const
44 : {
45 345979 : return reinterpret_cast<const chunk_type*>(this+1);
46 : }
47 :
48 : chunk_type* last_chunk()
49 : {
50 : chunk_type* cnk = reinterpret_cast<chunk_type*>(this + 1);
51 : return size > 0 ? cnk + size - 1 : cnk;
52 : }
53 :
54 4 : const chunk_type* last_chunk() const
55 : {
56 4 : const chunk_type* cnk = reinterpret_cast<const chunk_type*>(this + 1);
57 4 : return size > 0 ? cnk + size - 1 : cnk;
58 : }
59 :
60 :
61 : static size_t chunk_size()
62 : {
63 : return sizeof(chunk_type);
64 : }
65 :
66 30229 : const T* first_value() const
67 : {
68 30229 : if ( const chunk_type* beg = first_occuped() )
69 : {
70 30228 : return beg->first_value();
71 : }
72 1 : return fas_nullptr;
73 : }
74 :
75 30229 : T* first_value()
76 : {
77 30229 : return const_cast<T*>( const_cast<const self*>(this)->first_value() );
78 : }
79 :
80 4 : const T* last_value() const
81 : {
82 4 : if ( const chunk_type* beg = last_occuped() )
83 : {
84 4 : return beg->last_value();
85 : }
86 0 : return fas_nullptr;
87 : }
88 :
89 4 : T* last_value()
90 : {
91 4 : return const_cast<T*>( const_cast<const self*>(this)->last_value() );
92 : }
93 :
94 124227 : const T* next_value(const T* value) const
95 : {
96 : size_t offset = static_cast<size_t>(
97 124227 : reinterpret_cast<const char*>( value ) -
98 : reinterpret_cast<const char*>( this->first_chunk() )
99 248454 : );
100 124227 : const chunk_type* chk = first_chunk() + offset/sizeof(chunk_type);
101 :
102 124227 : if ( const T* result = chk->next_value(value) )
103 : {
104 103962 : return result;
105 : }
106 :
107 20265 : for ( ++chk; chk->empty(); ++chk)
108 : {
109 20217 : if ( static_cast<size_t>(chk - this->first_chunk()) == size )
110 : {
111 20217 : return fas_nullptr;
112 : }
113 : }
114 :
115 48 : return chk->first_value();
116 : }
117 :
118 124227 : T* next_value(T* value)
119 : {
120 124227 : return const_cast<T*>( const_cast<const self*>(this)->next_value(value) );
121 : }
122 :
123 22343 : const T* pred_value(const T* value) const
124 : {
125 : size_t offset = static_cast<size_t>(
126 22343 : reinterpret_cast<const char*>(value) -
127 : reinterpret_cast<const char*>(this->first_chunk())
128 44686 : );
129 22343 : const chunk_type* chk = first_chunk() + offset/sizeof(chunk_type);
130 :
131 22343 : if ( const T* result = chk->pred_value(value) )
132 : {
133 20366 : return result;
134 : }
135 :
136 1977 : if ( chk == this->first_chunk() )
137 : {
138 1941 : return fas_nullptr;
139 : }
140 :
141 36 : for ( --chk; chk->empty(); --chk)
142 : {
143 0 : if ( chk == this->first_chunk() )
144 : {
145 0 : return fas_nullptr;
146 : }
147 : }
148 36 : return chk->last_value();
149 : }
150 :
151 22343 : T* pred_value(T* value)
152 : {
153 22343 : return const_cast<T*>( const_cast<const self*>(this)->pred_value(value) );
154 : }
155 :
156 30229 : const chunk_type* first_occuped() const
157 : {
158 30229 : const chunk_type* beg = first_chunk();
159 30229 : const chunk_type* end = beg + size;
160 :
161 30230 : for ( ;beg!=end; ++beg)
162 : {
163 30229 : if ( !beg->empty() )
164 : {
165 30228 : return beg;
166 : }
167 : }
168 1 : return fas_nullptr;
169 : }
170 :
171 : chunk_type* first_occuped()
172 : {
173 : return const_cast<chunk_type*>( const_cast<const self*>(this)->first_occuped() );
174 : }
175 :
176 4 : const chunk_type* last_occuped() const
177 : {
178 4 : const chunk_type* beg = last_chunk();
179 4 : const chunk_type* end = first_chunk() - 1;
180 :
181 4 : for ( ;beg!=end; --beg)
182 : {
183 4 : if ( !beg->empty() )
184 : {
185 4 : return beg;
186 : }
187 : }
188 0 : return fas_nullptr;
189 : }
190 :
191 : chunk_type* last_occuped()
192 : {
193 : return const_cast<chunk_type*>( const_cast<const self*>(this)->last_occuped() );
194 : }
195 :
196 10845 : chunk_type* find_free()
197 : {
198 10845 : chunk_type* beg = first_chunk() + first_free;
199 10845 : chunk_type* end = first_chunk() + size;
200 :
201 10857 : for ( ;beg!=end; ++beg)
202 : {
203 10845 : if ( !beg->filled() )
204 : {
205 10833 : first_free = static_cast<size_t>( beg - first_chunk() );
206 10833 : return beg;
207 : }
208 : }
209 :
210 12 : first_free = static_cast<size_t>( beg - first_chunk() );
211 12 : return fas_nullptr;
212 : }
213 :
214 : const chunk_type* find_free() const
215 : {
216 : const chunk_type* beg = first_chunk() + first_free ;
217 : const chunk_type* end = first_chunk() + size;
218 :
219 : for ( ;beg!=end; ++beg)
220 : {
221 : if ( !beg->filled() )
222 : {
223 : first_free = beg - first_chunk();
224 : return beg;
225 : }
226 : }
227 : first_free = beg - first_chunk();
228 : return fas_nullptr;
229 : }
230 :
231 10845 : T* mark()
232 : {
233 10845 : if ( chunk_type* chk = find_free() )
234 : {
235 10833 : return chk->mark();
236 : }
237 12 : return fas_nullptr;
238 : }
239 :
240 10008 : void free(T* value)
241 : {
242 : size_t offset = static_cast<size_t>(
243 10008 : reinterpret_cast<char*>(value) -
244 : reinterpret_cast<char*>(this->first_chunk())
245 20016 : );
246 :
247 10008 : chunk_type* chk = this->first_chunk() + offset/sizeof(chunk_type);
248 10008 : chk->free(value);
249 :
250 10008 : offset = static_cast<size_t>(chk - this->first_chunk() );
251 10008 : if ( offset < first_free )
252 : {
253 0 : first_free = offset;
254 : }
255 10008 : }
256 :
257 206 : size_t count() const
258 : {
259 206 : size_t cnt=0;
260 206 : const chunk_type* beg = first_chunk();
261 206 : const chunk_type* end = first_chunk() + size;
262 448 : for (; beg != end; ++beg)
263 : {
264 242 : cnt+=beg->count();
265 : }
266 206 : return cnt;
267 : }
268 :
269 3 : size_t capacity() const
270 : {
271 3 : return size * chunk_type::max_count();
272 : }
273 : };
274 :
275 : }}}
276 :
277 : #endif
|
