vector.hpp (10261B)
1 // Copyright (c) 2020 Morel Bérenger 2 // 3 // This software is provided 'as-is', without any express or implied 4 // warranty. In no event will the authors be held liable for any damages 5 // arising from the use of this software. 6 // 7 // Permission is granted to anyone to use this software for any purpose, 8 // including commercial applications, and to alter it and redistribute it 9 // freely, subject to the following restrictions: 10 // 11 // 1. The origin of this software must not be misrepresented; you must not 12 // claim that you wrote the original software. If you use this software 13 // in a product, an acknowledgment in the product documentation would be 14 // appreciated but is not required. 15 // 2. Altered source versions must be plainly marked as such, and must not be 16 // misrepresented as being the original software. 17 // 3. This notice may not be removed or altered from any source distribution. 18 19 // a partial vector implementation. 20 // Why use it? Because: 21 // * it does *not* rely on exceptions; 22 // * it does *not* requires special tooling for debugging; 23 // * it allows lot smaller final binaries (than STL); 24 // You can just include it, and not use it by defining the 25 // WITH_STL flag: handy when you want STL for production, 26 // but this one for debugging. 27 // 28 // NOTE: the API is *not* 100% compatible, since it does not 29 // uses exceptions, but return values to signal errors, and 30 // is incomplete. 31 // Also, methods which are *not* in std::vector will be 32 // exposed in the end, to help handling memory. 33 // 34 // Bonus: 35 // * vector::remains() returns the number of unused slots 36 // * standalone "append" functions, which returning same 37 // type as the underlying container's "push_back" method 38 // * standalone "real_size" function, returning amount of 39 // memory used by a container. Does *not* count dynamic 40 // memory allocated by contained objects. 41 42 #ifndef VECTOR_HPP 43 #define VECTOR_HPP 44 45 #ifndef WITH_STL 46 47 #ifndef NDEBUG 48 #include <stdio.h> 49 #endif 50 51 //this could *highly* probably be replaced with: 52 //void* new( void* p ) { return p; } 53 #include <new> 54 55 //methods return true on error 56 //public API should rely as much as possible on private API: 57 //no need to pile useless calls: this just makes debug harder 58 //code should never throw 59 //The class is marked final to avoid useless vtable. 60 template <typename T> 61 class vector final 62 { 63 T* m_data = nullptr; 64 size_t m_size = 0; 65 size_t m_alloc = 0; 66 67 bool allocate( size_t new_size ); 68 bool release( size_t new_size ); 69 bool construct( size_t new_size ); 70 public: 71 typedef T* iterator; 72 typedef T const* const_iterator; 73 typedef T value_type; 74 75 bool empty( void ) const; 76 size_t size( void ) const; 77 size_t capacity( void ) const; 78 T const& operator[]( size_t index ) const; 79 T& operator[]( size_t index ); 80 bool shrink_to_fit( void ); 81 bool reserve( size_t size ); 82 bool resize( size_t size ); 83 bool assign( const_iterator start, const_iterator end ); 84 85 //default 86 vector( void ) = default; 87 //copy 88 vector( vector<T> const& ); 89 vector<T>& operator=( vector<T> const& ); 90 //move 91 vector( vector<T> && ); 92 vector<T>& operator=( vector<T> && ); 93 //destructor 94 ~vector( void ); 95 96 T const* begin( void ) const; 97 T * begin( void ); 98 T const* end( void ) const; 99 T * end( void ); 100 101 T const* rbegin( void ) const; 102 T * rbegin( void ); 103 T const* rend( void ) const; 104 T * rend( void ); 105 106 T const* data( void ) const; 107 T * data( void ); 108 109 T const& front( void ) const; 110 T & front( void ); 111 112 T const& back( void ) const; 113 T & back( void ); 114 115 bool push_back( const T& value ); 116 bool push_back( T&& value ); 117 void pop_back( void ); 118 119 // non-standard methods 120 121 // how much objects can still be stored before realloc 122 size_t remains( void ) const; 123 }; 124 125 template <typename T> 126 bool vector<T>::allocate( size_t new_size ) 127 { 128 T* tmp = static_cast<T*>( realloc( m_data, new_size * sizeof( T ) ) ); 129 if( tmp ) 130 { 131 m_data = tmp; 132 m_alloc = new_size; 133 } 134 return !tmp; 135 } 136 137 template <typename T> 138 bool vector<T>::release( size_t new_size ) 139 { 140 if( new_size > m_size ) 141 { 142 return true; 143 } 144 T* start = m_data + new_size; 145 T* end = m_data + m_size; 146 for( ; start != end; ++start ) 147 { 148 start->T::~T(); 149 } 150 m_size = new_size; 151 return false; 152 } 153 154 template <typename T> 155 bool vector<T>::construct( size_t new_size ) 156 { 157 if( new_size < m_size ) 158 { 159 return true; 160 } 161 162 T* start = m_data + m_size; 163 T* end = m_data + new_size; 164 for( ; start != end; ++start ) 165 { 166 new ( start ) T(); 167 } 168 m_size = new_size; 169 return false; 170 } 171 172 template <typename T> 173 size_t vector<T>::capacity( void ) const 174 { 175 return m_alloc; 176 } 177 178 template <typename T> 179 bool vector<T>::empty( void ) const 180 { 181 return m_size == 0; 182 } 183 184 template <typename T> 185 size_t vector<T>::size( void ) const 186 { 187 return m_size; 188 } 189 190 template <typename T> 191 T const& vector<T>::operator[]( size_t index ) const 192 { 193 return m_data[index]; 194 } 195 196 template <typename T> 197 T& vector<T>::operator[]( size_t index ) 198 { 199 return m_data[index]; 200 } 201 202 template <typename T> 203 bool vector<T>::shrink_to_fit( void ) 204 { 205 return allocate( m_size ); 206 } 207 208 template <typename T> 209 bool vector<T>::reserve( size_t size ) 210 { 211 if( m_alloc < size ) 212 { 213 return allocate( size ); 214 } 215 return false; 216 } 217 218 template <typename T> 219 bool vector<T>::resize( size_t size ) 220 { 221 if( size < m_size ) 222 { 223 return release( size ); 224 } 225 226 if( allocate( size ) ) 227 { 228 return true; 229 } 230 return construct( size ); 231 } 232 233 template <typename T> 234 bool vector<T>::assign( const_iterator start, const_iterator end ) 235 { 236 if( end - start < 0 ) 237 { 238 return true; 239 } 240 size_t new_size = static_cast<size_t>( end - start ); 241 242 release( new_size ); 243 if( allocate( new_size ) ) 244 { 245 return true; 246 } 247 m_size = new_size; 248 249 T* dst = m_data; 250 for( ; start != end; ++dst, ++start ) 251 { 252 *dst = *start; 253 } 254 255 return false; 256 } 257 258 template <typename T> 259 vector<T>::vector( vector<T> const& other ) 260 { 261 #ifndef NDEBUG 262 fprintf( stderr, "vector copy ctor: from %p[%zu] to %p[%zu]\n", 263 static_cast<void*>( other.m_data ), other.m_size, 264 static_cast<void*>( m_data ), m_size 265 ); 266 #endif 267 assign( other.begin(), other.end() ); 268 } 269 270 template <typename T> 271 vector<T>& vector<T>::operator=( vector<T> const& other ) 272 { 273 #ifndef NDEBUG 274 fprintf( stderr, "vector copy assign: from %p[%zu] to %p[%zu]\n", 275 static_cast<void*>( other.m_data ), other.m_size, 276 static_cast<void*>( m_data ), m_size 277 ); 278 #endif 279 assign( other.begin(), other.end() ); 280 return *this; 281 } 282 283 template <typename T> 284 vector<T>::vector( vector<T> && other ) 285 { 286 std::swap( other.m_data , m_data ); 287 std::swap( other.m_size , m_size ); 288 std::swap( other.m_alloc, m_alloc ); 289 } 290 291 template <typename T> 292 vector<T>& vector<T>::operator=( vector<T> && other ) 293 { 294 std::swap( other.m_data , m_data ); 295 std::swap( other.m_size , m_size ); 296 std::swap( other.m_alloc, m_alloc ); 297 return *this; 298 } 299 300 template <typename T> 301 vector<T>::~vector( void ) 302 { 303 release( m_size ); 304 free( m_data ); 305 } 306 307 template <typename T> 308 T const* vector<T>::data( void ) const 309 { 310 return m_data; 311 } 312 313 template <typename T> 314 T * vector<T>::data( void ) 315 { 316 return m_data; 317 } 318 319 template <typename T> 320 T const* vector<T>::begin( void ) const 321 { 322 return m_data; 323 } 324 325 template <typename T> 326 T * vector<T>::begin( void ) 327 { 328 return m_data; 329 } 330 331 template <typename T> 332 T const* vector<T>::rbegin( void ) const 333 { 334 return end() - 1; 335 } 336 337 template <typename T> 338 T * vector<T>::rbegin( void ) 339 { 340 return end() - 1; 341 } 342 343 template <typename T> 344 T const* vector<T>::rend( void ) const 345 { 346 return begin() - 1; 347 } 348 349 template <typename T> 350 T * vector<T>::rend( void ) 351 { 352 return begin() - 1; 353 } 354 355 356 template <typename T> 357 T const& vector<T>::front( void ) const 358 { 359 return *m_data; 360 } 361 362 template <typename T> 363 T & vector<T>::front( void ) 364 { 365 return *m_data; 366 } 367 368 369 template <typename T> 370 T const* vector<T>::end( void ) const 371 { 372 return m_data + m_size; 373 } 374 375 template <typename T> 376 T * vector<T>::end( void ) 377 { 378 return m_data + m_size; 379 } 380 381 template <typename T> 382 T const& vector<T>::back( void ) const 383 { 384 return m_data[m_size - 1]; 385 } 386 387 template <typename T> 388 T & vector<T>::back( void ) 389 { 390 return m_data[m_size - 1]; 391 } 392 393 template <typename T> 394 bool vector<T>::push_back( const T& value ) 395 { 396 size_t new_size = m_size + 1; 397 if( new_size >= capacity() && allocate( new_size ) ) 398 { 399 return true; 400 } 401 m_data[m_size] = value; 402 ++m_size; 403 return false; 404 } 405 406 template <typename T> 407 bool vector<T>::push_back( T&& value ) 408 { 409 size_t new_size = m_size + 1; 410 if( new_size >= capacity() && allocate( new_size ) ) 411 { 412 return true; 413 } 414 new (m_data + m_size ) T( std::move( value ) ); 415 //m_data[m_size] = std::move( value ); 416 ++m_size; 417 return false; 418 } 419 420 template <typename T> 421 void vector<T>::pop_back( void ) 422 { 423 if( m_size ) 424 { 425 --m_size; 426 m_data[m_size].~T(); 427 } 428 } 429 430 // non-standard methods 431 432 // how much objects can still be stored before realloc 433 template <typename T> 434 size_t vector<T>::remains( void ) const 435 { 436 return capacity() - size(); 437 } 438 439 #else 440 #include <vector> 441 using std::vector; 442 #endif 443 444 // append a single element to dst 445 template<typename C, typename T> 446 auto append( C& dst, T && src ) -> decltype( std::declval<C>().push_back( T() ) ) 447 { 448 return dst.push_back( src ); 449 } 450 451 // append a single element to dst 452 template<typename C, typename T> 453 auto append( C& dst, T const& src ) -> decltype( std::declval<C>().push_back( T() ) ) 454 { 455 return dst.push_back( src ); 456 } 457 458 // append a set to dst 459 template<typename C> 460 auto append( C& dst, typename C::const_iterator src_start, typename C::const_iterator src_end ) 461 -> decltype( std::declval<C>().push_back( typename C::value_type() ) ) 462 { 463 assert( src_end >= src_start ); 464 if( dst.reserve( dst.size() + static_cast<size_t>( src_end - src_start ) ) ) 465 { 466 return true; 467 } 468 for( ; src_start != src_end; ++src_start ) 469 { 470 if( dst.push_back( *src_start ) ) 471 { 472 return true; 473 } 474 } 475 return false; 476 } 477 478 // append a set to dst 479 template<typename C> 480 auto append( C& dst, C const& src ) 481 -> decltype( std::declval<C>().push_back( typename C::value_type() ) ) 482 { 483 if( dst.reserve( dst.size() + src.size() ) ) 484 { 485 return true; 486 } 487 for( auto el : src ) 488 { 489 dst.push_back( el ); 490 } 491 return false; 492 } 493 494 // return the amount of memory used by current instance. 495 // Obviously, it does not takes into account memory 496 // allocated by contained objects. 497 template <typename T> 498 size_t real_size( vector<T> const& target ) 499 { 500 return sizeof( target ) + target.capacity() * sizeof( T ); 501 } 502 503 #endif