1 /*
2    Copyright 2017 Skytechnology sp. z o.o.
3 
4    This file is part of LizardFS.
5 
6    LizardFS is free software: you can redistribute it and/or modify
7    it under the terms of the GNU General Public License as published by
8    the Free Software Foundation, version 3.
9 
10    LizardFS is distributed in the hope that it will be useful,
11    but WITHOUT ANY WARRANTY; without even the implied warranty of
12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13    GNU General Public License for more details.
14 
15    You should have received a copy of the GNU General Public License
16    along with LizardFS. If not, see <http://www.gnu.org/licenses/>.
17  */
18 
19 #pragma once
20 
21 #include "common/platform.h"
22 
23 #include <algorithm>
24 #include <array>
25 #include <cassert>
26 #include <cstddef>
27 #include <memory>
28 #include <type_traits>
29 #include <vector>
30 
31 namespace detail {
32 
33 /*! \brief Allocator with local buffer for small requests.
34  *
35  * This allocator class has local buffer that is used
36  * to fulfill small allocation requests (<= N).
37  *
38  * Local buffer can be used only for one request at a time.
39  * It is up to the caller to make sure this condition is met.
40  *
41  * The class is designed to be used in small_vector.
42  */
43 template <class T, std::size_t N>
44 class static_preallocator : public std::allocator<T> {
45 	typedef std::allocator<T> base;
46 
47 public:
48 	typedef typename base::value_type value_type;
49 	typedef typename base::pointer pointer;
50 	typedef typename base::const_pointer const_pointer;
51 	typedef typename base::reference reference;
52 	typedef typename base::const_reference const_reference;
53 	typedef typename base::size_type size_type;
54 	typedef typename base::difference_type difference_type;
55 
56 	template <typename U>
57 	struct rebind {
58 		typedef static_preallocator<U, N> other;
59 	};
60 
61 public:
static_preallocator()62 	static_preallocator() noexcept(std::is_nothrow_constructible<base>::value) : base() {
63 	}
64 
noexcept(std::is_nothrow_constructible<base,const base &>::value)65 	static_preallocator(const static_preallocator &other) noexcept(
66 	    std::is_nothrow_constructible<base, const base &>::value)
67 	    : base(other.as_base()) {
68 	}
69 
noexcept(std::is_nothrow_constructible<base,base &&>::value)70 	static_preallocator(static_preallocator &&other) noexcept(
71 	    std::is_nothrow_constructible<base, base &&>::value)
72 	    : base(std::move(other.as_base())) {
73 	}
74 
75 	static_preallocator &operator=(const static_preallocator &other) {
76 		base::operator=(other.as_base());
77 		return *this;
78 	}
79 	static_preallocator &operator=(static_preallocator &&other) {
80 		base::operator=(std::move(other.as_base()));
81 		return *this;
82 	}
83 
84 	template <class U>
static_preallocator(const static_preallocator<U,N> & other)85 	static_preallocator(const static_preallocator<U, N> &other)
86 	    : base(other.as_base()) {
87 	}
88 
~static_preallocator()89 	~static_preallocator() {
90 	}
91 
92 	pointer allocate(size_type n, const_pointer *hint = nullptr) {
93 		if (n == 0) {
94 			return nullptr;
95 		}
96 
97 		if (n <= N) {
98 			return reinterpret_cast<pointer>(data_.data());
99 		}
100 
101 		return base::allocate(n, hint);
102 	}
103 
deallocate(pointer p,size_type n)104 	void deallocate(pointer p, size_type n) {
105 		if (n > N) {
106 			base::deallocate(p, n);
107 		}
108 	}
109 
110 	using base::address;
111 	using base::construct;
112 	using base::destroy;
113 	using base::max_size;
114 
115 protected:
as_base()116 	const base &as_base() const {
117 		return static_cast<const base &>(*this);
118 	}
119 
as_base()120 	base &as_base() {
121 		return static_cast<base &>(*this);
122 	}
123 
124 	std::array<uint8_t, N * sizeof(T)> data_;
125 };
126 
127 template <class T1, std::size_t N1, class T2, std::size_t N2>
128 bool operator==(const static_preallocator<T1, N1> &a, const static_preallocator<T2, N2> &b) {
129 	return static_cast<const std::allocator<T1>&>(a) == static_cast<const std::allocator<T2>&>(b);
130 }
131 
132 template <class T1, std::size_t N1, class T2, std::size_t N2>
133 bool operator!=(const static_preallocator<T1, N1> &a, const static_preallocator<T2, N2> &b) {
134 	return static_cast<const std::allocator<T1>&>(a) != static_cast<const std::allocator<T2>&>(b);
135 }
136 
137 }  // detail
138 
139 /*! \brief Class providing std::vector interface for use with small number of elements.
140  *
141  * small_vector contains some preallocated elements in-place,
142  * which can avoid the use of dynamic storage allocation when
143  * the actual number of elements is below that preallocated threshold.
144  */
145 template <class T, std::size_t N>
146 class small_vector : public std::vector<T, detail::static_preallocator<T, N>> {
147 	typedef std::vector<T, detail::static_preallocator<T, N>> base;
148 
149 public:
150 	typedef typename base::value_type value_type;
151 	typedef typename base::pointer pointer;
152 	typedef typename base::const_pointer const_pointer;
153 	typedef typename base::reference reference;
154 	typedef typename base::const_reference const_reference;
155 	typedef typename base::iterator iterator;
156 	typedef typename base::const_iterator const_iterator;
157 	typedef typename base::const_reverse_iterator const_reverse_iterator;
158 	typedef typename base::reverse_iterator reverse_iterator;
159 	typedef typename base::size_type size_type;
160 	typedef typename base::difference_type difference_type;
161 	typedef typename base::allocator_type allocator_type;
162 
163 public:
small_vector()164 	small_vector() noexcept(std::is_nothrow_constructible<base>::value) : base() {
165 		reserve(N);
166 	}
167 
small_vector(const small_vector & other)168 	small_vector(const small_vector &other) : base() {
169 		reserve(N);
170 		operator=(other);
171 	}
172 
noexcept(std::is_nothrow_constructible<base>::value && std::is_nothrow_constructible<base,base &&>::value && std::is_nothrow_constructible<T,T &&>::value)173 	small_vector(small_vector &&other) noexcept(
174 			std::is_nothrow_constructible<base>::value &&
175 			std::is_nothrow_constructible<base, base &&>::value &&
176 			std::is_nothrow_constructible<T, T &&>::value)
177 	    : base() {
178 		reserve(N);
179 		operator=(std::move(other));
180 	}
181 
small_vector(std::initializer_list<T> il)182 	small_vector(std::initializer_list<T> il) {
183 		reserve(std::max(N, il.size()));
184 		insert(end(), il);
185 	}
186 
base()187 	small_vector(size_type count, const value_type &value = value_type()) : base() {
188 		reserve(N);
189 		insert(end(), count, value);
190 	}
191 
192 	template <typename InputIterator, typename =
193 	          typename std::enable_if<std::is_convertible<
194 	          typename std::iterator_traits<InputIterator>::iterator_category,
195 	          std::input_iterator_tag>::value>::type>
small_vector(InputIterator first,InputIterator last)196 	small_vector(InputIterator first, InputIterator last) : base() {
197 		reserve(std::max<size_type>(N, std::distance(first, last)));
198 		insert(end(), first, last);
199 	}
200 
201 	small_vector &operator=(const small_vector &other) {
202 		base::operator=(other);
203 		return *this;
204 	}
205 
206 	small_vector &operator=(small_vector &&other) {
207 		clear();
208 
209 		if (other.capacity() > N) {
210 			base::operator=(std::move(other));
211 
212 			// With std c++ library implementation in gcc
213 			// there is no need for two next lines. Move assignment
214 			// makes 'other' equal to empty vector.
215 			other.clear();
216 			other.base::shrink_to_fit();
217 			assert(other.capacity() == 0);
218 
219 			other.reserve(N);
220 			return *this;
221 		}
222 
223 		insert(end(), std::make_move_iterator(other.begin()), std::make_move_iterator(other.end()));
224 		other.clear();
225 		return *this;
226 	}
227 
shrink_to_fit()228 	void shrink_to_fit() {
229 		// The assumption in small_vector class
230 		// is that if std::vector uses local storage
231 		// then we have reserved exactly N elements.
232 		// Calling shrink_to_fit if the size() < N
233 		// breaks this requirement.
234 		if (size() >= N) {
235 			base::shrink_to_fit();
236 		}
237 	}
238 
swap(small_vector & x)239 	void swap(small_vector &x) {
240 		if (capacity() > N && x.capacity() > N) {
241 			return base::swap(x);
242 		}
243 
244 		if (capacity() <= N && x.capacity() <= N) {
245 			size_type m = std::min(size(), x.size());
246 
247 			std::swap_ranges(begin(), begin() + m, x.begin());
248 			if (size() < x.size()) {
249 				insert(end(), std::make_move_iterator(x.begin() + m),
250 				       std::make_move_iterator(x.end()));
251 				x.erase(x.begin() + m, x.end());
252 			} else if (x.size() < size()) {
253 				x.insert(x.end(), std::make_move_iterator(begin() + m),
254 				         std::make_move_iterator(end()));
255 				erase(begin() + m, end());
256 			}
257 			return;
258 		}
259 
260 		if (capacity() > N) {
261 			small_vector<T, N> tmp(std::move(*this));
262 
263 			*this = std::move(x);
264 			x = std::move(tmp);
265 		} else {
266 			small_vector<T, N> tmp(std::move(x));
267 
268 			x = std::move(*this);
269 			*this = std::move(tmp);
270 		}
271 	}
272 
273 	using base::at;
274 	using base::assign;
275 	using base::back;
276 	using base::begin;
277 	using base::capacity;
278 	using base::cbegin;
279 	using base::cend;
280 	using base::clear;
281 	using base::crbegin;
282 	using base::crend;
283 	using base::data;
284 	using base::emplace;
285 	using base::emplace_back;
286 	using base::empty;
287 	using base::end;
288 	using base::erase;
289 	using base::front;
290 	using base::get_allocator;
291 	using base::insert;
292 	using base::max_size;
293 	using base::operator[];
294 	using base::pop_back;
295 	using base::push_back;
296 	using base::rbegin;
297 	using base::reserve;
298 	using base::resize;
299 	using base::size;
300 };
301