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_CHUNK_HPP
8 : #define VSET_MEMORY_FSB_CHUNK_HPP
9 :
10 : #include <fas/system/nullptr.hpp>
11 : #include <stdexcept>
12 :
13 : namespace vset { namespace memory{ namespace fsb{
14 :
15 : template<typename T>
16 : struct chunk
17 : {
18 : typedef chunk<T> self;
19 : typedef T value_type;
20 :
21 : size_t bits;
22 : T data[sizeof(size_t)*8];
23 :
24 38 : chunk()
25 : : bits(0)
26 38 : , data()
27 38 : {}
28 :
29 11087 : bool filled() const
30 : {
31 11087 : return bits == static_cast<size_t>(-1);
32 : }
33 :
34 50776 : bool empty() const
35 : {
36 50776 : return bits == 0;
37 : }
38 :
39 22694 : static size_t max_count()
40 : {
41 22694 : return sizeof(size_t)*8;
42 : }
43 :
44 : static size_t head_size()
45 : {
46 : return sizeof(size_t);
47 : }
48 :
49 242 : size_t count() const
50 : {
51 242 : if ( this->empty() )
52 : {
53 0 : return 0;
54 : }
55 242 : else if ( this->filled() )
56 : {
57 36 : return this->max_count();
58 : }
59 :
60 206 : size_t cnt = 0;
61 13390 : for ( size_t i = 0; i < sizeof(size_t)*8; ++i )
62 : {
63 13184 : cnt += ( 0 != (bits & ( static_cast<size_t>(1) << i)) );
64 : }
65 206 : return cnt;
66 : }
67 :
68 : static size_t size()
69 : {
70 : return sizeof(self);
71 : }
72 :
73 : void clear()
74 : {
75 : bits = 0;
76 : }
77 :
78 30276 : const T* first_value() const
79 : {
80 30276 : size_t index = next_occuped(0);
81 30276 : if ( index == static_cast<size_t>(-1) )
82 : {
83 0 : return fas_nullptr;
84 : }
85 30276 : return data + index;
86 : }
87 :
88 : T* first_value()
89 : {
90 : return const_cast<T*>( const_cast<const self*>(this)->first_value() );
91 : }
92 :
93 40 : const T* last_value() const
94 : {
95 40 : size_t index = pred_occuped( max_count() - 1 );
96 40 : if ( index == static_cast<size_t>(-1) )
97 : {
98 0 : return fas_nullptr;
99 : }
100 40 : return data + index;
101 : }
102 :
103 : T* last_value()
104 : {
105 : return const_cast<T*>( const_cast<const self*>(this)->last_value() );
106 : }
107 :
108 124227 : const T* next_value(const T* current) const
109 : {
110 124227 : size_t index = this->next_occuped( static_cast<size_t>(current - data + 1) );
111 124227 : if ( index == static_cast<size_t>(-1) )
112 : {
113 20265 : return fas_nullptr;
114 : }
115 103962 : return data + index;
116 : }
117 :
118 : T* next_value(T* current)
119 : {
120 : return const_cast<T*>( const_cast<const self*>(this)->next_value(current) );
121 : }
122 :
123 22343 : const T* pred_value(const T* current) const
124 : {
125 22343 : size_t index = this->pred_occuped( static_cast<size_t>(current - data - 1) );
126 22343 : if ( index == static_cast<size_t>(-1) )
127 : {
128 1977 : return fas_nullptr;
129 : }
130 20366 : return data + index;
131 : }
132 :
133 : T* pred_value(T* current)
134 : {
135 : return const_cast<T*>( const_cast<const self*>(this)->pred_value(current) );
136 : }
137 :
138 154503 : size_t next_occuped(size_t pos = 0) const
139 : {
140 1357422 : for ( size_t i = pos; i < sizeof(size_t)*8; ++i )
141 : {
142 1337157 : if ( bits & ( static_cast<size_t>(1) << i) )
143 : {
144 134238 : return i;
145 : }
146 : }
147 20265 : return static_cast<size_t>(-1);
148 : }
149 :
150 22383 : size_t pred_occuped(size_t pos = max_count() - 1) const
151 : {
152 22615 : for ( size_t i = pos ; i < max_count(); --i )
153 : {
154 20638 : if ( bits & ( static_cast<size_t>(1) << i) )
155 : {
156 20406 : return i;
157 : }
158 : }
159 1977 : return static_cast<size_t>(-1);
160 : }
161 :
162 10833 : size_t first_free() const
163 : {
164 55318 : for ( size_t i = 0; i < sizeof(size_t)*8; ++i )
165 : {
166 55318 : if ( ! ( bits & ( static_cast<size_t>(1) << i) ) )
167 : {
168 10833 : return i;
169 : }
170 : }
171 0 : return static_cast<size_t>(-1);
172 : }
173 :
174 10833 : T* mark()
175 : {
176 10833 : size_t index = first_free();
177 10833 : if ( index == static_cast<size_t>(-1) )
178 : {
179 0 : return fas_nullptr;
180 : }
181 10833 : return mark(index);
182 : }
183 :
184 10833 : T* mark(size_t index)
185 : {
186 10833 : bits |= ( static_cast<size_t>(1) << index );
187 10833 : return data + index;
188 : }
189 :
190 10008 : void free(T* addr)
191 : {
192 10008 : size_t index = static_cast<size_t>(addr - data);
193 10008 : if ( index < 64 )
194 : {
195 10008 : bits &= ~( static_cast<size_t>(1)<<index);
196 : }
197 : else
198 : {
199 0 : throw std::invalid_argument("chunk<T>::free");
200 : }
201 10008 : }
202 : };
203 :
204 : }}}
205 :
206 : #endif
|
