Context Navigation

source: trunk/nv/stl/array.hh @ 383

Last change on this file since 383 was 383, checked in by epyon, 10 years ago
more work on stl fully working vectors! copy & copy_n removal of a lot of std code!
File size: 20.3 KB

Rev	Line
[260]	1	// Copyright (C) 2014 ChaosForge Ltd
	2	// http://chaosforge.org/
	3	//
	4	// This file is part of NV Libraries.
	5	// For conditions of distribution and use, see copyright notice in nv.hh
	6
	7	/**
	8	* @file array.hh
	9	* @author Kornel Kisielewicz epyon@chaosforge.org
	10	* @brief exception free array classes
	11	*/
	12
[319]	13	#ifndef NV_CORE_ARRAY_HH
	14	#define NV_CORE_ARRAY_HH
[260]	15
[319]	16	#include <nv/core/common.hh>
[368]	17	#include <nv/stl/memory.hh>
[374]	18	#include <nv/stl/iterator.hh>
	19	#include <nv/stl/utility.hh>
[260]	20	#include <vector>
[323]	21	#include <algorithm>
[260]	22	#include <array>
	23
	24	namespace nv
	25	{
	26
[383]	27	struct default_init
	28	{
[375]	29
[383]	30	};
[375]	31
[383]	32	template< typename SizeType >
	33	struct default_next_capacity
	34	{
	35	static SizeType get( SizeType requested, SizeType capacity, SizeType max_size )
	36	{
	37	SizeType remaining = max_size - capacity;
	38	if ( remaining < requested ) return 0;
	39	SizeType additional = nv::max( requested, capacity );
	40	return ( remaining < additional ? max_size : capacity + additional );
	41	}
	42	};
	43
	44	struct policy_initialize_always
	45	{
	46	template < typename ForwardIterator >
	47	inline static void initialize( ForwardIterator first, ForwardIterator last )
	48	{
	49	uninitialized_construct( first, last );
	50	}
	51	template < typename InputIterator, typename ForwardIterator >
	52	inline static ForwardIterator copy( InputIterator first, InputIterator last, ForwardIterator out )
	53	{
	54	return uninitialized_copy( first, last, out );
	55	}
	56	template < typename ForwardIterator >
	57	inline static void destroy( ForwardIterator first, ForwardIterator last )
	58	{
	59	uninitialized_destroy( first, last );
	60	}
	61	template < typename ForwardIterator >
	62	inline static void destroy( ForwardIterator first )
	63	{
	64	destroy_object( first );
	65	}
	66	};
	67
	68	struct policy_initialize_never
	69	{
	70	template < typename ForwardIterator >
	71	inline static void initialize( ForwardIterator, ForwardIterator )
	72	{
	73	}
	74	template < typename InputIterator, typename ForwardIterator >
	75	inline static ForwardIterator copy( InputIterator first, InputIterator last, ForwardIterator out )
	76	{
	77	return detail::uninitialized_copy( first, last, out, true_type );
	78	}
	79	template < typename ForwardIterator >
	80	inline static void destroy( ForwardIterator, ForwardIterator )
	81	{
	82	}
	83	template < typename ForwardIterator >
	84	inline static void destroy( ForwardIterator )
	85	{
	86	}
	87	};
	88
	89	struct policy_initialize_standard
	90	{
	91	template < typename ForwardIterator >
	92	inline static void initialize( ForwardIterator first, ForwardIterator last )
	93	{
	94	typedef typename iterator_traits< ForwardIterator >::value_type value_type;
	95	if ( !has_trivial_constructor<value_type>() )
	96	detail::uninitialized_construct_impl( first, last, false_type() );
	97	}
	98	template < typename InputIterator, typename ForwardIterator >
	99	inline static ForwardIterator copy( InputIterator first, InputIterator last, ForwardIterator out )
	100	{
	101	return uninitialized_copy( first, last, out );
	102	}
	103	template < typename ForwardIterator >
	104	inline static void destroy( ForwardIterator first, ForwardIterator last )
	105	{
	106	typedef typename iterator_traits< ForwardIterator >::value_type value_type;
	107	if ( !has_trivial_destructor<value_type>() )
	108	detail::uninitialized_destroy_impl( first, last, false_type() );
	109	}
	110	template < typename ForwardIterator >
	111	inline static void destroy( ForwardIterator first )
	112	{
	113	typedef typename iterator_traits< ForwardIterator >::value_type value_type;
	114	if ( !has_trivial_destructor<value_type>() )
	115	destroy_object( first );
	116	}
	117	};
	118
	119	template< typename T >
	120	class dynamic_storage
	121	{
	122	public:
	123	typedef T value_type;
	124
	125	static constexpr bool is_static = false;
	126	static constexpr bool is_const = false;
	127
	128	constexpr const value_type* data() const { return reinterpret_cast<const value_type*>( m_data ); }
	129	inline value_type* data() { return reinterpret_cast<T*>( m_data ); }
	130	constexpr const char* raw_data() const { return reinterpret_cast<const char*>( m_data ); }
	131	inline char* raw_data() { return reinterpret_cast<char*>( m_data ); }
	132
	133	protected:
	134	constexpr dynamic_storage() : m_data( nullptr ) {}
	135	// prevent copying
	136	dynamic_storage( const dynamic_storage& ) = delete;
	137	dynamic_storage& operator=( const dynamic_storage& ) = delete;
	138	// allow move
	139	inline dynamic_storage( dynamic_storage&& other )
	140	: m_data( other.m_data )
	141	{
	142	other.m_data = nullptr;
	143	}
	144	inline dynamic_storage& operator=( dynamic_storage&& other )
	145	{
	146	if ( this != &other )
	147	{
	148	reallocate( 0, false );
	149	m_data = other.m_data;
	150	}
	151	return *this;
	152	}
	153	~dynamic_storage() = default;
	154
	155	bool reallocate( size_t new_size, bool copy_needed )
	156	{
	157	if ( copy_needed )
	158	m_data = (uint8)nvrealloc( m_data, new_size sizeof( value_type ) );
	159	else
	160	{
	161	nvfree( m_data );
	162	m_data = ( new_size > 0 ? (uint8)nvmalloc( new_size sizeof( value_type ) ) : nullptr );
	163	}
	164	return true; // TODO : alloc check?
	165	}
	166	protected:
	167	uint8* m_data;
	168	};
	169
[374]	170	template< typename T, size_t N >
[383]	171	class static_storage
	172	{
	173	public:
	174	typedef T value_type;
	175
	176	static constexpr bool is_static = true;
	177	static constexpr bool is_const = false;
	178
	179	constexpr const value_type* data() const { return reinterpret_cast<const value_type*>( m_data ); }
	180	inline value_type* data() { return reinterpret_cast<T*>( m_data ); }
	181	constexpr const char* raw_data() const { return reinterpret_cast<const char*>( m_data ); }
	182	inline char* raw_data() { return reinterpret_cast<char*>( m_data ); }
	183
	184	protected:
	185	static constexpr bool reallocate( size_t new_size, bool /copy_needed/ ) { return new_size <= N; }
	186
	187	static_storage() = default;
	188
	189	// prevent copying
	190	static_storage( const static_storage& ) = delete;
	191	static_storage& operator=( const static_storage& ) = delete;
	192	// allow move
	193	static_storage( static_storage&& other ) = default;
	194	static_storage& operator=( static_storage&& other ) = default;
	195
	196	~static_storage() = default;
	197	protected:
	198	typedef aligned_array_t<T, N, alignof( T ) > storage_type;
	199	storage_type m_data;
	200	};
	201
	202	template< typename Storage, size_t N >
	203	class fixed_storage : public Storage
	204	{
	205	public:
	206	typedef size_t size_type;
	207	typedef typename Storage::value_type value_type;
	208
	209	static constexpr bool is_fixed = true;
	210
	211	fixed_storage()
	212	{
	213	Storage::reallocate( N, false );
	214	}
	215	~fixed_storage()
	216	{
	217	Storage::reallocate( 0, false );
	218	}
	219	static constexpr size_type max_size() { return N; }
	220	static constexpr size_type capacity() { return N; }
	221	static constexpr size_type size() { return N; }
	222	static constexpr bool empty() { return N == 0; }
	223	static constexpr size_type raw_size() { return sizeof( value_type ) * N; }
	224
	225	operator array_ref< value_type >() { return array_ref< value_type >( Storage::data(), size() ); }
	226	operator const_array_ref< value_type >() const { return const_array_ref< value_type >( Storage::data(), size() ); }
	227
	228	// allow move
	229	fixed_storage( fixed_storage&& ) = default;
	230	fixed_storage& operator=( fixed_storage&& ) = default;
	231	};
	232
	233	template< typename Storage >
	234	class resizable_storage : public Storage
	235	{
	236	public:
	237	typedef size_t size_type;
	238	typedef typename Storage::value_type value_type;
	239
	240	static constexpr bool is_fixed = false;
	241
	242	~resizable_storage()
	243	{
	244	if ( m_size > 0 ) reallocate( 0, false );
	245	}
	246	static constexpr size_type max_size() { return size_type( 0x80000000 ); }
	247	constexpr size_t capacity() { return m_size; }
	248	constexpr size_t size() const { return m_size; }
	249	constexpr bool empty() const { return m_size == 0; }
	250	constexpr size_t raw_size() const { return sizeof( value_type ) * m_size; }
	251
	252	operator array_ref< value_type >() { return array_ref< value_type >( Storage::data(), size() ); }
	253	operator const_array_ref< value_type >() const { return const_array_ref< value_type >( Storage::data(), size() ); }
	254	protected:
	255	constexpr resizable_storage() : m_size( 0 ) {}
	256
	257	// allow move
	258	inline resizable_storage( resizable_storage&& other )
	259	: Storage( nv::move( other ) ), m_size( other.m_size )
	260	{
	261	other.m_size = 0;
	262	}
	263	inline resizable_storage& operator=( resizable_storage&& other )
	264	{
	265	m_size = other.m_size;
	266	Storage::operator=( nv::move( o ) );
	267	other.m_size = 0;
	268	return *this;
	269	}
	270
	271	// TODO: return type error checking
	272	bool try_resize( size_t new_size, bool copy_needed )
	273	{
	274	if ( new_size != m_size )
	275	{
	276	if ( reallocate( new_size, copy_needed ) )
	277	{
	278	m_size = new_size;
	279	return true;
	280	}
	281	return false;
	282	}
	283	return true;
	284	}
	285	protected:
	286	size_type m_size;
	287	};
	288
	289	template< typename Storage, typename NextCapacity = default_next_capacity< size_t > >
	290	class growable_storage : public Storage
	291	{
	292	public:
	293	typedef size_t size_type;
	294	typedef typename Storage::value_type value_type;
	295
	296	static constexpr bool is_fixed = false;
	297
	298	~growable_storage()
	299	{
	300	if ( m_capacity > 0 ) reallocate( 0, false );
	301	}
	302	static constexpr size_type max_size() { return size_type( 0x80000000 ); }
	303	constexpr size_t capacity() { return m_capacity; }
	304	constexpr size_t size() const { return m_size; }
	305	constexpr bool empty() const { return m_size == 0; }
	306	constexpr size_t raw_size() const { return sizeof( value_type ) * m_size; }
	307
	308	operator array_ref< value_type >() { return array_ref< value_type >( Storage::data(), size() ); }
	309	operator const_array_ref< value_type >() const { return const_array_ref< value_type >( Storage::data(), size() ); }
	310	protected:
	311	constexpr growable_storage() : m_size( 0 ), m_capacity( 0 ) {}
	312
	313	// allow move
	314	inline growable_storage( growable_storage&& other )
	315	: Storage( nv::move( other ) ), m_size( other.m_size ), m_capacity( other.m_capacity )
	316	{
	317	other.m_size = 0;
	318	other.m_capacity = 0;
	319	}
	320	inline growable_storage& operator=( growable_storage&& other )
	321	{
	322	m_size = other.m_size;
	323	m_capacity = other.m_capacity;
	324	Storage::operator=( nv::move( other ) );
	325	other.m_size = 0;
	326	other.m_capacity = 0;
	327	return *this;
	328	}
	329
	330	// TODO: return type error checking
	331	bool try_grow( size_t amount )
	332	{
	333	size_type new_size = amount + m_size;
	334	if ( new_size > m_capacity )
	335	{
	336	size_type new_capacity = NextCapacity::get( new_size - m_capacity, m_capacity, max_size() );
	337	if ( new_capacity > 0 && reallocate( new_capacity, true ) )
	338	{
	339	m_capacity = new_capacity;
	340	m_size = new_size;
	341	}
	342	else return false;
	343	}
	344	m_size = new_size;
	345	return true;
	346	}
	347	// TODO: return type error checking
	348	bool try_reserve( size_t new_capacity, bool copy_needed )
	349	{
	350	if ( new_capacity > m_capacity )
	351	{
	352	if ( reallocate( new_capacity, copy_needed ) )
	353	{
	354	m_capacity = new_capacity;
	355	}
	356	else return false;
	357	}
	358	return true;
	359	}
	360	// TODO: return type error checking
	361	bool try_resize( size_t new_size, bool copy_needed )
	362	{
	363	if ( new_size > m_size )
	364	{
	365	if ( try_reserve( new_size, copy_needed ) )
	366	{
	367	m_size = new_size;
	368	return true;
	369	}
	370	return false;
	371	}
	372	m_size = new_size;
	373	return true;
	374	}
	375	protected:
	376	size_type m_size;
	377	size_type m_capacity;
	378	};
	379
	380
	381	template< typename T, size_t N >
	382	using fixed_static_storage = fixed_storage< static_storage< T, N >, N >;
	383
	384	template< typename T, size_t N >
	385	using fixed_dynamic_storage = fixed_storage< dynamic_storage< T >, N >;
	386
	387	template< typename T >
	388	using resizable_dynamic_storage = resizable_storage< dynamic_storage< T > >;
	389
	390	template< typename T, size_t N >
	391	using resizable_static_storage = resizable_storage< static_storage< T, N > >;
	392
	393	template< typename T >
	394	using growable_dynamic_storage = growable_storage< dynamic_storage< T > >;
	395
	396	template< typename T, size_t N >
	397	using growable_static_storage = growable_storage< static_storage< T, N > >;
	398
	399	template <
	400	typename Storage,
	401	typename InitializePolicy = policy_initialize_standard
	402	>
	403	class fixed_container_allocator : public Storage
	404	{
	405	public:
	406	typedef typename Storage::value_type value_type;
	407	typedef typename Storage::size_type size_type;
	408
	409	fixed_container_allocator()
	410	{
	411	InitializePolicy::initialize( data(), data() + Storage::capacity() );
	412	}
	413
	414	explicit fixed_container_allocator( default_init )
	415	{
	416	uninitialized_construct( data(), data() + Storage::capacity() );
	417	}
	418
	419	explicit fixed_container_allocator( const value_type& v )
	420	{
	421	uninitialized_fill( data(), data() + Storage::capacity(), v );
	422	}
	423
	424	~fixed_container_allocator()
	425	{
	426	InitializePolicy::destroy( data(), data() + Storage::capacity() );
	427	}
	428
	429	// prevent copying
	430	fixed_container_allocator( const fixed_container_allocator& ) = delete;
	431	fixed_container_allocator& operator=( const fixed_container_allocator& ) = delete;
	432	// allow move
	433	fixed_container_allocator( fixed_container_allocator&& ) = default;
	434	fixed_container_allocator& operator=( fixed_container_allocator&& ) = default;
	435	};
	436
	437	template <
	438	typename Storage,
	439	typename InitializePolicy = policy_initialize_standard
	440	>
	441	class sized_container_allocator : public Storage
	442	{
	443	public:
	444	typedef typename Storage::value_type value_type;
	445	typedef typename Storage::size_type size_type;
	446
	447	inline sized_container_allocator() {}
	448	inline explicit sized_container_allocator( size_type new_size ) { resize( new_size ); }
	449	inline explicit sized_container_allocator( default_init ) { resize( default_init() ); }
	450	inline sized_container_allocator( size_type new_size, const value_type& v ) { resize( new_size, v ); }
	451
	452	// prevent copying
	453	sized_container_allocator( const sized_container_allocator& ) = delete;
	454	sized_container_allocator& operator=( const sized_container_allocator& ) = delete;
	455	// allow move
	456	sized_container_allocator( sized_container_allocator&& ) = default;
	457	sized_container_allocator& operator=( sized_container_allocator&& ) = default;
	458
	459
	460	inline void resize( size_type new_size )
	461	{
	462	size_type old_size = Storage::size();
	463	resize_impl( new_size );
	464	initialize_range( old_size, Storage::size() );
	465	}
	466
	467	inline void resize( size_type new_size, default_init )
	468	{
	469	size_type old_size = Storage::size();
	470	resize_impl( new_size );
	471	initialize_range( old_size, Storage::size(), default_init() );
	472	}
	473
	474	inline void resize( size_type new_size, const value_type& value )
	475	{
	476	size_type old_size = Storage::size();
	477	resize_impl( new_size );
	478	initialize_range( old_size, Storage::size(), value );
	479	}
	480
	481	inline void assign( const value_type* ptr, size_type sz )
	482	{
	483	if ( Storage::size() > 0 ) InitializePolicy::destroy( Storage::data(), Storage::data() + Storage::size() );
	484	if ( ptr != nullptr && sz > 0 )
	485	{
	486	if ( sz != Storage::size() && Storage::try_resize( sz, false ) )
	487	InitializePolicy::copy( ptr, ptr + sz, Storage::data() );
	488	}
	489	else Storage::try_resize( 0, false );
	490	}
	491
	492	template< typename InputIterator >
	493	inline void assign( InputIterator first, InputIterator last )
	494	{
	495	size_type d = distance( first, last );
	496	if ( d != Storage::size() && Storage::try_resize( sz, false ) )
	497	InitializePolicy::copy( first, last, Storage::data() );
	498	}
	499
	500	// explicit copy
	501	inline void assign( const sized_container_allocator& other )
	502	{
	503	assign( other.data(), other.size() );
	504	}
	505
	506	inline void clear()
	507	{
	508	if ( Storage::size() > 0 )
	509	{
	510	InitializePolicy::destroy( Storage::data(), Storage::data() + Storage::size() );
	511	Storage::try_resize( 0, false );
	512	}
	513	}
	514
	515	~sized_container_allocator()
	516	{
	517	if ( Storage::size() > 0 ) clear();
	518	}
	519
	520	protected:
	521
	522	inline void initialize_range( size_type old_size, size_type new_size )
	523	{
	524	if ( new_size > old_size ) InitializePolicy::initialize( Storage::data() + old_size, Storage::data() + new_size );
	525	}
	526	inline void initialize_range( size_type old_size, size_type new_size, default_init )
	527	{
	528	if ( new_size > old_size ) uninitialized_construct( Storage::data() + old_size, Storage::data() + new_size );
	529	}
	530	inline void initialize_range( size_type old_size, size_type new_size, const value_type& value )
	531	{
	532	if ( new_size > old_size ) uninitialized_fill( Storage::data() + old_size, Storage::data() + new_size, value );
	533	}
	534	inline void resize_impl( size_type new_size )
	535	{
	536	size_type old_size = Storage::size();
	537	if ( new_size != old_size )
	538	{
	539	if ( new_size < old_size )
	540	{
	541	InitializePolicy::destroy( Storage::data() + new_size, Storage::data() + old_size );
	542	}
	543	if ( Storage::try_resize( new_size, true ) )
	544	{
	545	// TODO: error checking
	546	}
	547	}
	548	}
	549
	550	};
	551
	552	template <
	553	typename Storage,
	554	typename InitializePolicy = policy_initialize_standard
	555	>
	556	class growing_container_allocator : public sized_container_allocator< Storage, InitializePolicy >
	557	{
	558	typedef sized_container_allocator< Storage, InitializePolicy > inherited;
	559	public:
	560	typedef typename Storage::value_type value_type;
	561	typedef typename Storage::size_type size_type;
	562
	563	using sized_container_allocator< Storage, InitializePolicy >::sized_container_allocator;
	564
	565	void reserve( size_type new_capacity )
	566	{
	567	Storage::try_reserve( new_capacity, true );
	568	}
	569	void push_back( const value_type& e )
	570	{
	571	if ( Storage::try_grow( 1 ) ) copy_construct_object( data() + size() - 1, e );
	572	}
	573	void push_back( value_type&& e )
	574	{
	575	if ( Storage::try_grow( 1 ) ) move_construct_object( data() + size() - 1, forward<value_type>( e ) );
	576	}
	577	template < typename... Args >
	578	void emplace_back( Args&&... args )
	579	{
	580	if ( Storage::try_grow( 1 ) ) construct_object( data() + size() - 1, forward<Args>( args )... );
	581	}
	582	void pop_back()
	583	{
	584	try_resize( size() - 1, true );
	585	}
	586
	587	};
	588
	589
	590	template < typename ContainerAllocator >
	591	using array_base_t = detail::add_random_access< detail::add_iterators < ContainerAllocator > >;
	592
	593	template< typename T, size_t N >
	594	using array = array_base_t < fixed_container_allocator < fixed_static_storage< T, N > > >;
[376]	595
[382]	596	template< typename T >
[383]	597	using dynamic_array = array_base_t < sized_container_allocator< resizable_dynamic_storage< T > > >;
[375]	598
[383]	599	template< typename T >
	600	using vector = array_base_t < growing_container_allocator< growable_dynamic_storage< T > > >;
	601
[374]	602	// template < typename T, typename ContainerAllocator >
	603	// class vector_base
	604	// {
	605	// public:
	606	// typedef T value_type;
	607	// typedef size_t size_type;
	608	// typedef ptrdiff_t difference_type;
	609	// typedef T* pointer;
	610	// typedef const T* const_pointer;
	611	// typedef T* iterator;
	612	// typedef const T* const_iterator;
	613	// typedef T& reference;
	614	// typedef const T& const_reference;
[368]	615	//
[374]	616	// protected:
	617	// ContainerAllocator m_storage;
	618	// };
	619
	620	// template< typename T, size_t N >
	621	// class static_vector : public detail::pointer_iterators < static_vector< T, N >, T, false >
	622	// {
	623	// public:
	624	// typedef T value_type;
	625	// typedef size_t size_type;
	626	// typedef ptrdiff_t difference_type;
	627	// typedef T* pointer;
	628	// typedef const T* const_pointer;
	629	// typedef T* iterator;
	630	// typedef const T* const_iterator;
	631	// typedef T& reference;
	632	// typedef const T& const_reference;
	633	// typedef nv::reverse_iterator<iterator> reverse_iterator;
	634	// typedef nv::reverse_iterator<const_iterator> const_reverse_iterator;
[368]	635	//
[374]	636	// static_vector() : m_size(0) {}
[368]	637	//
[374]	638	// inline const_pointer data() const { return m_data; }
	639	// inline pointer data() { return m_data; }
	640	// inline size_type size() const { return m_size; }
	641	// inline bool empty() const { return !m_size; }
	642	// inline size_type raw_size() const { return N * sizeof( T ); }
	643	// inline const char* raw_data() const { return (const char*)m_data; }
	644	// inline char* raw_data() { return (char*)m_data; }
	645	//
	646	// inline reference front() { NV_ASSERT( !empty(), "front() called on empty data!" ); return m_data[0]; }
	647	// inline const_reference front() const { NV_ASSERT( !empty(), "front() called on empty data!" ); return m_data[0]; }
	648	// inline reference back() { NV_ASSERT( !empty(), "front() called on empty data!" ); return m_data[m_size - 1]; }
	649	// inline const_reference back() const { NV_ASSERT( !empty(), "front() called on empty data!" ); return m_data[m_size - 1]; }
	650	// protected:
	651	// value_type m_data[N];
	652	// size_type m_size;
	653	// };
[260]	654
	655	}
	656
[319]	657	#endif // NV_CORE_ARRAY_HH

Note: See TracBrowser for help on using the repository browser.

Download in other formats: