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