Line data Source code
1 :
2 : /* Copyright (c) 2011-2014, EPFL/Blue Brain Project
3 : * Stefan Eilemann <stefan.eilemann@epfl.ch>
4 : *
5 : * This file is part of Lunchbox <https://github.com/Eyescale/Lunchbox>
6 : *
7 : * This library is free software; you can redistribute it and/or modify it under
8 : * the terms of the GNU Lesser General Public License version 3.0 as published
9 : * by the Free Software Foundation.
10 : *
11 : * This library is distributed in the hope that it will be useful, but WITHOUT
12 : * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
13 : * FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
14 : * details.
15 : *
16 : * You should have received a copy of the GNU Lesser General Public License
17 : * along with this library; if not, write to the Free Software Foundation, Inc.,
18 : * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
19 : */
20 :
21 : #ifndef LUNCHBOX_LFVECTOR_H
22 : #define LUNCHBOX_LFVECTOR_H
23 :
24 : #include <lunchbox/bitOperation.h> // used inline
25 : #include <lunchbox/debug.h> // used inline
26 : #include <lunchbox/os.h> // bzero()
27 : #include <lunchbox/scopedMutex.h> // member
28 : #include <lunchbox/serializable.h>
29 : #include <lunchbox/spinLock.h> // member
30 : #include <algorithm> // used inline
31 : #include <stdexcept>
32 :
33 : namespace lunchbox
34 : {
35 : /**
36 : * STL-like vector implementation providing certain thread-safety guarantees.
37 : *
38 : * All operations not modifying the vector size are lock-free and wait-free. All
39 : * operations modifying the vector size are serialized using a spin lock. The
40 : * interaction of operations is documented in the corresponding modify
41 : * operation.
42 : *
43 : * Undocumented methods behave like the STL implementation. The number of slots
44 : * (default 32) sets the maximum elements the vector may hold to
45 : * 2^nSlots-1. Each slot needs one pointer additional storage. Naturally it
46 : * should never be set higher than 64.
47 : *
48 : * Not all std::vector methods are implemented. Serializable using
49 : * boost.serialization.
50 : *
51 : * Example: @include tests/lfVector.cpp
52 : */
53 : template< class T, int32_t nSlots = 32 > class LFVector
54 : {
55 : public:
56 : typedef ScopedFastWrite ScopedWrite;
57 : typedef T value_type;
58 :
59 : /** @version 1.3.2 */
60 : LFVector();
61 :
62 : /** @version 1.3.2 */
63 : explicit LFVector( const size_t n );
64 :
65 : /** @version 1.3.2 */
66 : LFVector( const size_t n, const T& t );
67 :
68 : /** @version 1.3.2 */
69 : explicit LFVector( const LFVector& from );
70 :
71 : /** @version 1.3.2 */
72 : template< int32_t fromSlots >
73 : explicit LFVector( const LFVector< T, fromSlots >& from );
74 :
75 : /** @version 1.3.2 */
76 : ~LFVector();
77 :
78 : /** @version 1.3.2 */
79 : LFVector& operator = ( const LFVector& from );
80 :
81 : /** @version 1.3.2 */
82 : bool operator == ( const LFVector& rhs ) const;
83 :
84 : /** @version 1.3.2 */
85 : bool operator != ( const LFVector& rhs ) const { return !(*this == rhs); }
86 :
87 9200001 : bool empty() const { return size_ == 0; } //!< @version 1.3.2
88 51911031 : size_t size() const { return size_; } //!< @version 1.3.2
89 :
90 : /** @version 1.3.2 */
91 : T& operator[]( size_t i );
92 :
93 : /** @version 1.3.2 */
94 : const T& operator[]( size_t i ) const;
95 :
96 : /** @version 1.3.2 */
97 : T& front();
98 :
99 : /** @version 1.3.2 */
100 : T& back();
101 :
102 : /** Iterator over the vector elements. @version 1.3.2 */
103 : typedef LFVectorIterator< LFVector< T, nSlots >, T > iterator;
104 :
105 : /** Iterator over the const vector elements. @version 1.3.2 */
106 : typedef LFVectorIterator<const LFVector<T, nSlots>, const T> const_iterator;
107 :
108 : const_iterator begin() const; //!< @version 1.3.2
109 : const_iterator end() const; //!< @version 1.3.2
110 : iterator begin(); //!< @version 1.3.2
111 : iterator end(); //!< @version 1.3.2
112 :
113 : /**
114 : * Resize the vector to at least the given size.
115 : *
116 : * In contrast to resize(), expand() only increases the size of the vector,
117 : * allowing concurrent resize operations on the same vector. Completely
118 : * thread-save with read operations. Existing end() iterators will keep
119 : * pointing to the old end of the vector. The size is updated after all
120 : * elements have been inserted, so size() followed by a read is
121 : * thread-safe. In contrast to <code>while( vector.size() < newSize )
122 : * vector.insert( item );</code> this method's operation is atomic with
123 : * other writes.
124 : *
125 : * @param newSize the minimum new size.
126 : * @param item the element to insert.
127 : * @throw std::runtime_error if the vector is full
128 : * @version 1.3.2
129 : */
130 : void expand( const size_t newSize, const T& item = T( ));
131 :
132 : /**
133 : * Add an element to the vector.
134 : *
135 : * Completely thread-save with read operations. Existing end() iterators
136 : * will keep pointing to the old end of the vector. The size is updated
137 : * after the element is inserted, so size() followed by a read is
138 : * thread-safe.
139 : *
140 : * @param item the element to insert.
141 : * @param lock true for internal lock, false if locked with getWriteLock()
142 : * @throw std::runtime_error if the vector is full
143 : * @version 1.3.2
144 : */
145 : void push_back( const T& item, bool lock = true );
146 :
147 : /**
148 : * Remove the last element (STL version).
149 : *
150 : * A concurrent read on the removed item produces undefined results, in
151 : * particular end() and back().
152 : *
153 : * @version 1.3.2
154 : */
155 : void pop_back();
156 :
157 : /**
158 : * Remove the last element (atomic version).
159 : *
160 : * A concurrent read on the removed item produces undefined results, in
161 : * particular end() and back(). The last element is assigned to the given
162 : * output element if the vector is not empty. If the vector is empty,
163 : * element is not touched and false is returned. The whole operation is
164 : * atomic with other operations changing the size of the vector.
165 : *
166 : * @param element the item receiving the value which was stored at the end.
167 : * @return true if the vector was not empty, false if no item was popped.
168 : * @version 1.3.2
169 : */
170 : bool pop_back( T& element );
171 :
172 : /**
173 : * Remove an element.
174 : *
175 : * A concurrent read on the item or any following item is not thread
176 : * save. The vector's size is decremented first. Returns end() if the
177 : * element can't be removed, i.e., the iterator is past end() or not for
178 : * this vector.
179 : *
180 : * @param pos the element to remove
181 : * @return an iterator pointing to the element after the removed element, or
182 : * end() if nothing was erased.
183 : * @version 1.3.2
184 : */
185 : iterator erase( typename LFVector< T, nSlots >::iterator pos );
186 :
187 : /**
188 : * Remove the last occurence of the given element.
189 : *
190 : * A concurrent read on the item or any following item is not thread
191 : * save. The vector's size is decremented first. Returns end() if the
192 : * element can't be removed, i.e., the vector does not contain the element.
193 : *
194 : * @param element the element to remove
195 : * @return an iterator pointing to the element after the removed element, or
196 : * end() if nothing was erased.
197 : * @version 1.3.2
198 : */
199 : iterator erase( const T& element );
200 :
201 : /**
202 : * Resize the vector.
203 : *
204 : * Thread-safe with other write operations. Shrinking is not thread-safe
205 : * with concurrent reads on the removed elements and produces undefined
206 : * results.
207 : *
208 : * @throw std::runtime_error if the vector is full
209 : * @version 1.7.2
210 : */
211 : void resize( const size_t size, const T& value = T( ));
212 :
213 : /**
214 : * Clear the vector and all storage.
215 : *
216 : * Thread-safe with other write operations. By nature not thread-safe with
217 : * read operations.
218 : *
219 : * @version 1.3.2
220 : */
221 : void clear();
222 :
223 : /** @return the locked mutex for unlocked write operations. @version 1.5 */
224 : ScopedWrite getWriteLock();
225 :
226 : private:
227 : LB_SERIALIZABLE
228 :
229 : T* slots_[ nSlots ];
230 : size_t size_;
231 : mutable SpinLock lock_;
232 :
233 : template< int32_t fromSlots >
234 : void assign_( const LFVector< T, fromSlots >& from );
235 :
236 : void push_back_unlocked_( const T& item );
237 :
238 : void trim_();
239 : };
240 :
241 : /** Output the vector and up to 256 items to the ostream. @version 0.1 */
242 : template< class T >
243 : std::ostream& operator << ( std::ostream& os, const LFVector< T >& v );
244 :
245 : }
246 :
247 : #include "lfVector.ipp" // template implementation
248 :
249 : #endif // LUNCHBOX_LFVECTOR_H
|
