tools

various tools
git clone git://deadbeef.fr/tools.git
Log | Files | Refs | README | LICENSE

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