Context Navigation

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

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

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

Download in other formats: