Line data Source code
1 :
2 : /* Copyright (c) 2011-2013, 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 :
32 : namespace lunchbox
33 : {
34 : /**
35 : * STL-like vector implementation providing certain thread-safety guarantees.
36 : *
37 : * All operations not modifying the vector size are lock-free and wait-free. All
38 : * operations modifying the vector size are serialized using a spin lock. The
39 : * interaction of operations is documented in the corresponding modify
40 : * operation.
41 : *
42 : * Undocumented methods behave like the STL implementation. The number of slots
43 : * (default 32) sets the maximum elements the vector may hold to
44 : * 2^nSlots-1. Each slot needs one pointer additional storage. Naturally it
45 : * should never be set higher than 64.
46 : *
47 : * Not all std::vector methods are implemented. Serializable using
48 : * boost.serialization.
49 : *
50 : * Example: @include tests/lfVector.cpp
51 : */
52 : template< class T, int32_t nSlots = 32 > class LFVector
53 : {
54 : public:
55 : typedef ScopedFastWrite ScopedWrite;
56 : typedef T value_type;
57 :
58 : /** @version 1.3.2 */
59 : LFVector();
60 :
61 : /** @version 1.3.2 */
62 : explicit LFVector( const size_t n );
63 :
64 : /** @version 1.3.2 */
65 : LFVector( const size_t n, const T& t );
66 :
67 : /** @version 1.3.2 */
68 : explicit LFVector( const LFVector& from );
69 :
70 : /** @version 1.3.2 */
71 : template< int32_t fromSlots >
72 : explicit LFVector( const LFVector< T, fromSlots >& from );
73 :
74 : /** @version 1.3.2 */
75 : ~LFVector();
76 :
77 : /** @version 1.3.2 */
78 : LFVector& operator = ( const LFVector& from );
79 :
80 : /** @version 1.3.2 */
81 : bool operator == ( const LFVector& rhs ) const;
82 :
83 : /** @version 1.3.2 */
84 : bool operator != ( const LFVector& rhs ) const { return !(*this == rhs); }
85 :
86 9200000 : bool empty() const { return size_ == 0; } //!< @version 1.3.2
87 107257850 : size_t size() const { return size_; } //!< @version 1.3.2
88 :
89 : /** @version 1.3.2 */
90 : T& operator[]( size_t i );
91 :
92 : /** @version 1.3.2 */
93 : const T& operator[]( size_t i ) const;
94 :
95 : /** @version 1.3.2 */
96 : T& front();
97 :
98 : /** @version 1.3.2 */
99 : T& back();
100 :
101 : /** Iterator over the vector elements. @version 1.3.2 */
102 : typedef LFVectorIterator< LFVector< T, nSlots >, T > iterator;
103 :
104 : /** Iterator over the const vector elements. @version 1.3.2 */
105 : typedef LFVectorIterator<const LFVector<T, nSlots>, const T> const_iterator;
106 :
107 : const_iterator begin() const; //!< @version 1.3.2
108 : const_iterator end() const; //!< @version 1.3.2
109 : iterator begin(); //!< @version 1.3.2
110 : iterator end(); //!< @version 1.3.2
111 :
112 : /**
113 : * Resize the vector to at least the given size.
114 : *
115 : * In contrast to resize(), expand() only increases the size of the vector,
116 : * allowing concurrent resize operations on the same vector. Completely
117 : * thread-save with read operations. Existing end() iterators will keep
118 : * pointing to the old end of the vector. The size is updated after all
119 : * elements have been inserted, so size() followed by a read is
120 : * thread-safe. In contrast to <code>while( vector.size() < newSize )
121 : * vector.insert( item );</code> this method's operation is atomic with
122 : * other writes.
123 : *
124 : * @param newSize the minimum new size.
125 : * @param item the element to insert.
126 : * @version 1.3.2
127 : */
128 : void expand( const size_t newSize, const T& item = T( ));
129 :
130 : /**
131 : * Add an element to the vector.
132 : *
133 : * Completely thread-save with read operations. Existing end() iterators
134 : * will keep pointing to the old end of the vector. The size is updated
135 : * after the element is inserted, so size() followed by a read is
136 : * thread-safe.
137 : *
138 : * @param item the element to insert.
139 : * @param lock true for internal lock, false if locked with getWriteLock()
140 : * @version 1.3.2
141 : */
142 : void push_back( const T& item, bool lock = true );
143 :
144 : /**
145 : * Remove the last element (STL version).
146 : *
147 : * A concurrent read on the removed item produces undefined results, in
148 : * particular end() and back().
149 : *
150 : * @version 1.3.2
151 : */
152 : void pop_back();
153 :
154 : /**
155 : * Remove the last element (atomic version).
156 : *
157 : * A concurrent read on the removed item produces undefined results, in
158 : * particular end() and back(). The last element is assigned to the given
159 : * output element if the vector is not empty. If the vector is empty,
160 : * element is not touched and false is returned. The whole operation is
161 : * atomic with other operations changing the size of the vector.
162 : *
163 : * @param element the item receiving the value which was stored at the end.
164 : * @return true if the vector was not empty, false if no item was popped.
165 : * @version 1.3.2
166 : */
167 : bool pop_back( T& element );
168 :
169 : /**
170 : * Remove an element.
171 : *
172 : * A concurrent read on the item or any following item is not thread
173 : * save. The vector's size is decremented first. Returns end() if the
174 : * element can't be removed, i.e., the iterator is past end() or not for
175 : * this vector.
176 : *
177 : * @param pos the element to remove
178 : * @return an iterator pointing to the element after the removed element, or
179 : * end() if nothing was erased.
180 : * @version 1.3.2
181 : */
182 : iterator erase( typename LFVector< T, nSlots >::iterator pos );
183 :
184 : /**
185 : * Remove the last occurence of the given element.
186 : *
187 : * A concurrent read on the item or any following item is not thread
188 : * save. The vector's size is decremented first. Returns end() if the
189 : * element can't be removed, i.e., the vector does not contain the element.
190 : *
191 : * @param element the element to remove
192 : * @return an iterator pointing to the element after the removed element, or
193 : * end() if nothing was erased.
194 : * @version 1.3.2
195 : */
196 : iterator erase( const T& element );
197 :
198 : /**
199 : * Resize the vector.
200 : *
201 : * Thread-safe with other write operations. Shrinking is not thread-safe
202 : * with concurrent reads on the removed elements and produces undefined
203 : * results.
204 : *
205 : * @version 1.7.2
206 : */
207 : void resize( const size_t size, const T& value = T( ));
208 :
209 : /**
210 : * Clear the vector and all storage.
211 : *
212 : * Thread-safe with other write operations. By nature not thread-safe with
213 : * read operations.
214 : *
215 : * @version 1.3.2
216 : */
217 : void clear();
218 :
219 : /** @return the locked mutex for unlocked write operations. @version 1.5 */
220 : ScopedWrite getWriteLock();
221 :
222 : private:
223 : LB_SERIALIZABLE
224 :
225 : T* slots_[ nSlots ];
226 : size_t size_;
227 : mutable SpinLock lock_;
228 :
229 : template< int32_t fromSlots >
230 : void assign_( const LFVector< T, fromSlots >& from );
231 :
232 : void push_back_unlocked_( const T& item );
233 :
234 : void trim_();
235 : };
236 :
237 : /** Output the vector and up to 256 items to the ostream. @version 0.1 */
238 : template< class T >
239 : std::ostream& operator << ( std::ostream& os, const LFVector< T >& v );
240 :
241 : }
242 :
243 : #include "lfVector.ipp" // template implementation
244 :
245 : #endif // LUNCHBOX_LFVECTOR_H
|
