Index: /trunk/nv/stl/array.hh =================================================================== --- /trunk/nv/stl/array.hh (revision 390) +++ /trunk/nv/stl/array.hh (revision 391) @@ -11,372 +11,15 @@ */ -#ifndef NV_CORE_ARRAY_HH -#define NV_CORE_ARRAY_HH +#ifndef NV_STL_ARRAY_HH +#define NV_STL_ARRAY_HH #include -#include -#include -#include -#include -#include -#include +#include +#include +#include +#include namespace nv { - - struct default_init - { - - }; - - template< typename SizeType > - struct default_next_capacity - { - static SizeType get( SizeType requested, SizeType capacity, SizeType max_size ) - { - SizeType minimum = nv::min( capacity, 4 ); - SizeType remaining = max_size - capacity; - if ( remaining < requested ) return 0; - SizeType additional = nv::max( requested, capacity ); - return nv::max( minimum, remaining < additional ? max_size : capacity + additional ); - } - }; - - struct policy_initialize_always - { - template < typename ForwardIterator > - inline static void initialize( ForwardIterator first, ForwardIterator last ) - { - uninitialized_construct( first, last ); - } - template < typename InputIterator, typename ForwardIterator > - inline static ForwardIterator copy( InputIterator first, InputIterator last, ForwardIterator out ) - { - return uninitialized_copy( first, last, out ); - } - template < typename ForwardIterator > - inline static void destroy( ForwardIterator first, ForwardIterator last ) - { - uninitialized_destroy( first, last ); - } - template < typename ForwardIterator > - inline static void destroy( ForwardIterator first ) - { - destroy_object( first ); - } - }; - - struct policy_initialize_never - { - template < typename ForwardIterator > - inline static void initialize( ForwardIterator, ForwardIterator ) - { - } - template < typename InputIterator, typename ForwardIterator > - inline static ForwardIterator copy( InputIterator first, InputIterator last, ForwardIterator out ) - { - return detail::uninitialized_copy( first, last, out, true_type ); - } - template < typename ForwardIterator > - inline static void destroy( ForwardIterator, ForwardIterator ) - { - } - template < typename ForwardIterator > - inline static void destroy( ForwardIterator ) - { - } - }; - - struct policy_initialize_standard - { - template < typename ForwardIterator > - inline static void initialize( ForwardIterator first, ForwardIterator last ) - { - typedef typename iterator_traits< ForwardIterator >::value_type value_type; - if ( !has_trivial_constructor() ) - detail::uninitialized_construct_impl( first, last, false_type() ); - } - template < typename InputIterator, typename ForwardIterator > - inline static ForwardIterator copy( InputIterator first, InputIterator last, ForwardIterator out ) - { - return uninitialized_copy( first, last, out ); - } - template < typename ForwardIterator > - inline static void destroy( ForwardIterator first, ForwardIterator last ) - { - typedef typename iterator_traits< ForwardIterator >::value_type value_type; - if ( !has_trivial_destructor() ) - detail::uninitialized_destroy_impl( first, last, false_type() ); - } - template < typename ForwardIterator > - inline static void destroy( ForwardIterator first ) - { - typedef typename iterator_traits< ForwardIterator >::value_type value_type; - if ( !has_trivial_destructor() ) - destroy_object( first ); - } - }; - - template< typename T > - class dynamic_storage - { - public: - typedef T value_type; - - static constexpr bool is_static = false; - static constexpr bool is_const = false; - - constexpr const value_type* data() const { return reinterpret_cast( m_data ); } - inline value_type* data() { return reinterpret_cast( m_data ); } - constexpr const char* raw_data() const { return reinterpret_cast( m_data ); } - inline char* raw_data() { return reinterpret_cast( m_data ); } - - protected: - constexpr dynamic_storage() : m_data( nullptr ) {} - // prevent copying - dynamic_storage( const dynamic_storage& ) = delete; - dynamic_storage& operator=( const dynamic_storage& ) = delete; - // allow move - inline dynamic_storage( dynamic_storage&& other ) - : m_data( other.m_data ) - { - other.m_data = nullptr; - } - inline dynamic_storage& operator=( dynamic_storage&& other ) - { - if ( this != &other ) - { - reallocate( 0, false ); - m_data = other.m_data; - } - return *this; - } - ~dynamic_storage() = default; - - bool reallocate( size_t new_size, bool copy_needed ) - { - if ( copy_needed ) - m_data = (uint8*)nvrealloc( m_data, new_size * sizeof( value_type ) ); - else - { - nvfree( m_data ); - m_data = ( new_size > 0 ? (uint8*)nvmalloc( new_size * sizeof( value_type ) ) : nullptr ); - } - return true; // TODO : alloc check? - } - protected: - uint8* m_data; - }; - - template< typename T, size_t N > - class static_storage - { - public: - typedef T value_type; - - static constexpr bool is_static = true; - static constexpr bool is_const = false; - - constexpr const value_type* data() const { return reinterpret_cast( m_data ); } - inline value_type* data() { return reinterpret_cast( m_data ); } - constexpr const char* raw_data() const { return reinterpret_cast( m_data ); } - inline char* raw_data() { return reinterpret_cast( m_data ); } - - protected: - static constexpr bool reallocate( size_t new_size, bool /*copy_needed*/ ) { return new_size <= N; } - - static_storage() = default; - - // prevent copying - static_storage( const static_storage& ) = delete; - static_storage& operator=( const static_storage& ) = delete; - // allow move - static_storage( static_storage&& other ) = default; - static_storage& operator=( static_storage&& other ) = default; - - ~static_storage() = default; - protected: - typedef aligned_array_t storage_type; - storage_type m_data; - }; - - template< typename Storage, size_t N > - class fixed_storage : public Storage - { - public: - typedef size_t size_type; - typedef typename Storage::value_type value_type; - - static constexpr bool is_fixed = true; - - fixed_storage() - { - Storage::reallocate( N, false ); - } - ~fixed_storage() - { - Storage::reallocate( 0, false ); - } - static constexpr size_type max_size() { return N; } - static constexpr size_type capacity() { return N; } - static constexpr size_type size() { return N; } - static constexpr bool empty() { return N == 0; } - static constexpr size_type raw_size() { return sizeof( value_type ) * N; } - - operator array_ref< value_type >() { return array_ref< value_type >( Storage::data(), size() ); } - operator const_array_ref< value_type >() const { return const_array_ref< value_type >( Storage::data(), size() ); } - - // allow move - fixed_storage( fixed_storage&& ) = default; - fixed_storage& operator=( fixed_storage&& ) = default; - }; - - template< typename Storage > - class resizable_storage : public Storage - { - public: - typedef size_t size_type; - typedef typename Storage::value_type value_type; - - static constexpr bool is_fixed = false; - - ~resizable_storage() - { - if ( m_size > 0 ) reallocate( 0, false ); - } - static constexpr size_type max_size() { return size_type( 0x80000000 ); } - constexpr size_t capacity() { return m_size; } - constexpr size_t size() const { return m_size; } - constexpr bool empty() const { return m_size == 0; } - constexpr size_t raw_size() const { return sizeof( value_type ) * m_size; } - - operator array_ref< value_type >() { return array_ref< value_type >( Storage::data(), size() ); } - operator const_array_ref< value_type >() const { return const_array_ref< value_type >( Storage::data(), size() ); } - protected: - constexpr resizable_storage() : m_size( 0 ) {} - - // allow move - inline resizable_storage( resizable_storage&& other ) - : Storage( nv::move( other ) ), m_size( other.m_size ) - { - other.m_size = 0; - } - inline resizable_storage& operator=( resizable_storage&& other ) - { - m_size = other.m_size; - Storage::operator=( nv::move( o ) ); - other.m_size = 0; - return *this; - } - - // TODO: return type error checking - bool try_resize( size_t new_size, bool copy_needed ) - { - if ( new_size != m_size ) - { - if ( reallocate( new_size, copy_needed ) ) - { - m_size = new_size; - return true; - } - return false; - } - return true; - } - protected: - size_type m_size; - }; - - template< typename Storage, typename NextCapacity = default_next_capacity< size_t > > - class growable_storage : public Storage - { - public: - typedef size_t size_type; - typedef typename Storage::value_type value_type; - - static constexpr bool is_fixed = false; - - ~growable_storage() - { - if ( m_capacity > 0 ) reallocate( 0, false ); - } - static constexpr size_type max_size() { return size_type( 0x80000000 ); } - constexpr size_t capacity() { return m_capacity; } - constexpr size_t size() const { return m_size; } - constexpr bool empty() const { return m_size == 0; } - constexpr size_t raw_size() const { return sizeof( value_type ) * m_size; } - - operator array_ref< value_type >() { return array_ref< value_type >( Storage::data(), size() ); } - operator const_array_ref< value_type >() const { return const_array_ref< value_type >( Storage::data(), size() ); } - protected: - constexpr growable_storage() : m_size( 0 ), m_capacity( 0 ) {} - - // allow move - inline growable_storage( growable_storage&& other ) - : Storage( nv::move( other ) ), m_size( other.m_size ), m_capacity( other.m_capacity ) - { - other.m_size = 0; - other.m_capacity = 0; - } - inline growable_storage& operator=( growable_storage&& other ) - { - m_size = other.m_size; - m_capacity = other.m_capacity; - Storage::operator=( nv::move( other ) ); - other.m_size = 0; - other.m_capacity = 0; - return *this; - } - - // TODO: return type error checking - bool try_grow( size_t amount ) - { - size_type new_size = amount + m_size; - if ( new_size > m_capacity ) - { - size_type new_capacity = NextCapacity::get( new_size - m_capacity, m_capacity, max_size() ); - if ( new_capacity > 0 && reallocate( new_capacity, true ) ) - { - m_capacity = new_capacity; - m_size = new_size; - } - else return false; - } - m_size = new_size; - return true; - } - // TODO: return type error checking - bool try_reserve( size_t new_capacity, bool copy_needed ) - { - if ( new_capacity > m_capacity ) - { - if ( reallocate( new_capacity, copy_needed ) ) - { - m_capacity = new_capacity; - } - else return false; - } - return true; - } - // TODO: return type error checking - bool try_resize( size_t new_size, bool copy_needed ) - { - if ( new_size > m_size ) - { - if ( try_reserve( new_size, copy_needed ) ) - { - m_size = new_size; - return true; - } - return false; - } - m_size = new_size; - return true; - } - protected: - size_type m_size; - size_type m_capacity; - }; - template< typename T, size_t N > @@ -392,214 +35,17 @@ using resizable_static_storage = resizable_storage< static_storage< T, N > >; + template< typename T, size_t N > + using array = + detail::add_random_access < + detail::add_iterators < + fixed_container_handler< fixed_static_storage< T, N > > > >; + template< typename T > - using growable_dynamic_storage = growable_storage< dynamic_storage< T > >; - - template< typename T, size_t N > - using growable_static_storage = growable_storage< static_storage< T, N > >; - - template < - typename Storage, - typename InitializePolicy = policy_initialize_standard - > - class fixed_container_allocator : public Storage - { - public: - typedef typename Storage::value_type value_type; - typedef typename Storage::size_type size_type; - - fixed_container_allocator() - { - InitializePolicy::initialize( data(), data() + Storage::capacity() ); - } - - explicit fixed_container_allocator( default_init ) - { - uninitialized_construct( data(), data() + Storage::capacity() ); - } - - explicit fixed_container_allocator( const value_type& v ) - { - uninitialized_fill( data(), data() + Storage::capacity(), v ); - } - - ~fixed_container_allocator() - { - InitializePolicy::destroy( data(), data() + Storage::capacity() ); - } - - // prevent copying - fixed_container_allocator( const fixed_container_allocator& ) = delete; - fixed_container_allocator& operator=( const fixed_container_allocator& ) = delete; - // allow move - fixed_container_allocator( fixed_container_allocator&& ) = default; - fixed_container_allocator& operator=( fixed_container_allocator&& ) = default; - }; - - template < - typename Storage, - typename InitializePolicy = policy_initialize_standard - > - class sized_container_allocator : public Storage - { - public: - typedef typename Storage::value_type value_type; - typedef typename Storage::size_type size_type; - - inline sized_container_allocator() {} - inline explicit sized_container_allocator( size_type new_size ) { resize( new_size ); } - inline explicit sized_container_allocator( default_init ) { resize( default_init() ); } - inline sized_container_allocator( size_type new_size, const value_type& v ) { resize( new_size, v ); } - - // prevent copying - sized_container_allocator( const sized_container_allocator& ) = delete; - sized_container_allocator& operator=( const sized_container_allocator& ) = delete; - // allow move - sized_container_allocator( sized_container_allocator&& ) = default; - sized_container_allocator& operator=( sized_container_allocator&& ) = default; - - - inline void resize( size_type new_size ) - { - size_type old_size = Storage::size(); - resize_impl( new_size ); - initialize_range( old_size, Storage::size() ); - } - - inline void resize( size_type new_size, default_init ) - { - size_type old_size = Storage::size(); - resize_impl( new_size ); - initialize_range( old_size, Storage::size(), default_init() ); - } - - inline void resize( size_type new_size, const value_type& value ) - { - size_type old_size = Storage::size(); - resize_impl( new_size ); - initialize_range( old_size, Storage::size(), value ); - } - - inline void assign( const value_type* ptr, size_type sz ) - { - if ( Storage::size() > 0 ) InitializePolicy::destroy( Storage::data(), Storage::data() + Storage::size() ); - if ( ptr != nullptr && sz > 0 ) - { - if ( sz != Storage::size() && Storage::try_resize( sz, false ) ) - InitializePolicy::copy( ptr, ptr + sz, Storage::data() ); - } - else Storage::try_resize( 0, false ); - } - - template< typename InputIterator > - inline void assign( InputIterator first, InputIterator last ) - { - size_type d = distance( first, last ); - if ( d != Storage::size() && Storage::try_resize( sz, false ) ) - InitializePolicy::copy( first, last, Storage::data() ); - } - - // explicit copy - inline void assign( const sized_container_allocator& other ) - { - assign( other.data(), other.size() ); - } - - inline void clear() - { - if ( Storage::size() > 0 ) - { - InitializePolicy::destroy( Storage::data(), Storage::data() + Storage::size() ); - Storage::try_resize( 0, false ); - } - } - - ~sized_container_allocator() - { - if ( Storage::size() > 0 ) clear(); - } - - protected: - - inline void initialize_range( size_type old_size, size_type new_size ) - { - if ( new_size > old_size ) InitializePolicy::initialize( Storage::data() + old_size, Storage::data() + new_size ); - } - inline void initialize_range( size_type old_size, size_type new_size, default_init ) - { - if ( new_size > old_size ) uninitialized_construct( Storage::data() + old_size, Storage::data() + new_size ); - } - inline void initialize_range( size_type old_size, size_type new_size, const value_type& value ) - { - if ( new_size > old_size ) uninitialized_fill( Storage::data() + old_size, Storage::data() + new_size, value ); - } - inline void resize_impl( size_type new_size ) - { - size_type old_size = Storage::size(); - if ( new_size != old_size ) - { - if ( new_size < old_size ) - { - InitializePolicy::destroy( Storage::data() + new_size, Storage::data() + old_size ); - } - if ( Storage::try_resize( new_size, true ) ) - { - // TODO: error checking - } - } - } - - }; - - template < - typename Storage, - typename InitializePolicy = policy_initialize_standard - > - class growing_container_allocator : public sized_container_allocator< Storage, InitializePolicy > - { - typedef sized_container_allocator< Storage, InitializePolicy > inherited; - public: - typedef typename Storage::value_type value_type; - typedef typename Storage::size_type size_type; - - using sized_container_allocator< Storage, InitializePolicy >::sized_container_allocator; - - void reserve( size_type new_capacity ) - { - Storage::try_reserve( new_capacity, true ); - } - void push_back( const value_type& e ) - { - if ( Storage::try_grow( 1 ) ) copy_construct_object( data() + size() - 1, e ); - } - void push_back( value_type&& e ) - { - if ( Storage::try_grow( 1 ) ) move_construct_object( data() + size() - 1, forward( e ) ); - } - template < typename... Args > - void emplace_back( Args&&... args ) - { - if ( Storage::try_grow( 1 ) ) construct_object( data() + size() - 1, forward( args )... ); - } - void pop_back() - { - try_resize( size() - 1, true ); - } - - }; - - - template < typename ContainerAllocator > - using array_base_t = detail::add_random_access< detail::add_iterators < ContainerAllocator > >; - - template< typename T, size_t N > - using array = array_base_t < fixed_container_allocator < fixed_static_storage< T, N > > >; - - template< typename T > - using dynamic_array = array_base_t < sized_container_allocator< resizable_dynamic_storage< T > > >; - - template< typename T > - using vector = array_base_t < growing_container_allocator< growable_dynamic_storage< T > > >; + using dynamic_array = + detail::add_random_access < + detail::add_iterators < + sized_container_handler< resizable_dynamic_storage< T > > > >; } -#endif // NV_CORE_ARRAY_HH +#endif // NV_STL_ARRAY_HH Index: /trunk/nv/stl/container/contiguous.hh =================================================================== --- /trunk/nv/stl/container/contiguous.hh (revision 391) +++ /trunk/nv/stl/container/contiguous.hh (revision 391) @@ -0,0 +1,32 @@ +// Copyright (C) 2015 ChaosForge Ltd +// http://chaosforge.org/ +// +// This file is part of NV Libraries. +// For conditions of distribution and use, see copyright notice in nv.hh + +/** +* @file contiguous.hh +* @author Kornel Kisielewicz epyon@chaosforge.org +* @brief exception free contiguous base classes +*/ + +#ifndef NV_STL_CONTAINER_CONTIGUOUS +#define NV_STL_CONTAINER_CONTIGUOUS + +#include +#include +#include +#include +#include +#include +#include + +namespace nv +{ + + template < typename ContainerAllocator > + using array_base_t = detail::add_random_access< detail::add_iterators < ContainerAllocator > >; + +} + +#endif // NV_STL_CONTAINER_CONTIGUOUS Index: /trunk/nv/stl/container/contiguous_storage.hh =================================================================== --- /trunk/nv/stl/container/contiguous_storage.hh (revision 391) +++ /trunk/nv/stl/container/contiguous_storage.hh (revision 391) @@ -0,0 +1,109 @@ +// Copyright (C) 2014 ChaosForge Ltd +// http://chaosforge.org/ +// +// This file is part of NV Libraries. +// For conditions of distribution and use, see copyright notice in nv.hh + +/** +* @file contiguous_storage.hh +* @author Kornel Kisielewicz epyon@chaosforge.org +* @brief contiguous_storage classes +*/ + +#ifndef NV_STL_CONTAINER_CONTIGUOUS_STORAGE_HH +#define NV_STL_CONTAINER_CONTIGUOUS_STORAGE_HH + +#include +#include +#include + +namespace nv +{ + + template< typename T, size_t N > + class static_storage + { + public: + typedef T value_type; + + static constexpr bool is_static = true; + static constexpr bool is_const = false; + + constexpr const value_type* data() const { return reinterpret_cast( m_data ); } + inline value_type* data() { return reinterpret_cast( m_data ); } + constexpr const char* raw_data() const { return reinterpret_cast( m_data ); } + inline char* raw_data() { return reinterpret_cast( m_data ); } + + protected: + static constexpr bool reallocate( size_t new_size, bool /*copy_needed*/ ) { return new_size <= N; } + + static_storage() = default; + + // prevent copying + static_storage( const static_storage& ) = delete; + static_storage& operator=( const static_storage& ) = delete; + // allow move + static_storage( static_storage&& other ) = default; + static_storage& operator=( static_storage&& other ) = default; + + ~static_storage() = default; + protected: + typedef aligned_array_t storage_type; + storage_type m_data; + }; + + template< typename T > + class dynamic_storage + { + public: + typedef T value_type; + + static constexpr bool is_static = false; + static constexpr bool is_const = false; + + constexpr const value_type* data() const { return reinterpret_cast( m_data ); } + inline value_type* data() { return reinterpret_cast( m_data ); } + constexpr const char* raw_data() const { return reinterpret_cast( m_data ); } + inline char* raw_data() { return reinterpret_cast( m_data ); } + + protected: + constexpr dynamic_storage() : m_data( nullptr ) {} + // prevent copying + dynamic_storage( const dynamic_storage& ) = delete; + dynamic_storage& operator=( const dynamic_storage& ) = delete; + // allow move + inline dynamic_storage( dynamic_storage&& other ) + : m_data( other.m_data ) + { + other.m_data = nullptr; + } + inline dynamic_storage& operator=( dynamic_storage&& other ) + { + if ( this != &other ) + { + reallocate( 0, false ); + m_data = other.m_data; + } + return *this; + } + ~dynamic_storage() = default; + + bool reallocate( size_t new_size, bool copy_needed ) + { + if ( copy_needed ) + m_data = (uint8*)nvrealloc( m_data, new_size * sizeof( value_type ) ); + else + { + nvfree( m_data ); + m_data = ( new_size > 0 ? (uint8*)nvmalloc( new_size * sizeof( value_type ) ) : nullptr ); + } + return true; // TODO : alloc check? + } + protected: + uint8* m_data; + }; + +} + +#endif // NV_STL_CONTIGUOUS_STORAGE_HH + Index: /trunk/nv/stl/container/contiguous_storage_policy.hh =================================================================== --- /trunk/nv/stl/container/contiguous_storage_policy.hh (revision 391) +++ /trunk/nv/stl/container/contiguous_storage_policy.hh (revision 391) @@ -0,0 +1,216 @@ +// Copyright (C) 2015 ChaosForge Ltd +// http://chaosforge.org/ +// +// This file is part of NV Libraries. +// For conditions of distribution and use, see copyright notice in nv.hh + +/** +* @file contiguous_storage_policy.hh +* @author Kornel Kisielewicz epyon@chaosforge.org +* @brief contiguous storage policy classes +*/ + +#ifndef NV_STL_CONTAINER_CONTIGUOUS_STORAGE_POLICY +#define NV_STL_CONTAINER_CONTIGUOUS_STORAGE_POLICY + +#include +#include +#include + +namespace nv +{ + + template< typename Storage, size_t N > + class fixed_storage : public Storage + { + public: + typedef size_t size_type; + typedef typename Storage::value_type value_type; + + static constexpr bool is_fixed = true; + + fixed_storage() + { + Storage::reallocate( N, false ); + } + ~fixed_storage() + { + Storage::reallocate( 0, false ); + } + static constexpr size_type max_size() { return N; } + static constexpr size_type capacity() { return N; } + static constexpr size_type size() { return N; } + static constexpr bool empty() { return N == 0; } + static constexpr size_type raw_size() { return sizeof( value_type ) * N; } + + operator array_ref< value_type >() { return array_ref< value_type >( Storage::data(), size() ); } + operator const_array_ref< value_type >() const { return const_array_ref< value_type >( Storage::data(), size() ); } + + // allow move + fixed_storage( fixed_storage&& ) = default; + fixed_storage& operator=( fixed_storage&& ) = default; + }; + + template< typename Storage > + class resizable_storage : public Storage + { + public: + typedef size_t size_type; + typedef typename Storage::value_type value_type; + + static constexpr bool is_fixed = false; + + ~resizable_storage() + { + if ( m_size > 0 ) reallocate( 0, false ); + } + static constexpr size_type max_size() { return size_type( 0x80000000 ); } + constexpr size_t capacity() { return m_size; } + constexpr size_t size() const { return m_size; } + constexpr bool empty() const { return m_size == 0; } + constexpr size_t raw_size() const { return sizeof( value_type ) * m_size; } + + operator array_ref< value_type >() { return array_ref< value_type >( Storage::data(), size() ); } + operator const_array_ref< value_type >() const { return const_array_ref< value_type >( Storage::data(), size() ); } + protected: + constexpr resizable_storage() : m_size( 0 ) {} + + // allow move + inline resizable_storage( resizable_storage&& other ) + : Storage( nv::move( other ) ), m_size( other.m_size ) + { + other.m_size = 0; + } + inline resizable_storage& operator=( resizable_storage&& other ) + { + m_size = other.m_size; + Storage::operator=( nv::move( o ) ); + other.m_size = 0; + return *this; + } + + // TODO: return type error checking + bool try_resize( size_t new_size, bool copy_needed ) + { + if ( new_size != m_size ) + { + if ( reallocate( new_size, copy_needed ) ) + { + m_size = new_size; + return true; + } + return false; + } + return true; + } + protected: + size_type m_size; + }; + + template< typename SizeType > + struct default_next_capacity + { + static SizeType get( SizeType requested, SizeType capacity, SizeType max_size ) + { + SizeType minimum = nv::min( capacity, 4 ); + SizeType remaining = max_size - capacity; + if ( remaining < requested ) return 0; + SizeType additional = nv::max( requested, capacity ); + return nv::max( minimum, remaining < additional ? max_size : capacity + additional ); + } + }; + + template< typename Storage, typename NextCapacity = default_next_capacity< size_t > > + class growable_storage : public Storage + { + public: + typedef size_t size_type; + typedef typename Storage::value_type value_type; + + static constexpr bool is_fixed = false; + + ~growable_storage() + { + if ( m_capacity > 0 ) reallocate( 0, false ); + } + static constexpr size_type max_size() { return size_type( 0x80000000 ); } + constexpr size_t capacity() { return m_capacity; } + constexpr size_t size() const { return m_size; } + constexpr bool empty() const { return m_size == 0; } + constexpr size_t raw_size() const { return sizeof( value_type ) * m_size; } + + operator array_ref< value_type >() { return array_ref< value_type >( Storage::data(), size() ); } + operator const_array_ref< value_type >() const { return const_array_ref< value_type >( Storage::data(), size() ); } + protected: + constexpr growable_storage() : m_size( 0 ), m_capacity( 0 ) {} + + // allow move + inline growable_storage( growable_storage&& other ) + : Storage( nv::move( other ) ), m_size( other.m_size ), m_capacity( other.m_capacity ) + { + other.m_size = 0; + other.m_capacity = 0; + } + inline growable_storage& operator=( growable_storage&& other ) + { + m_size = other.m_size; + m_capacity = other.m_capacity; + Storage::operator=( nv::move( other ) ); + other.m_size = 0; + other.m_capacity = 0; + return *this; + } + + // TODO: return type error checking + bool try_grow( size_t amount ) + { + size_type new_size = amount + m_size; + if ( new_size > m_capacity ) + { + size_type new_capacity = NextCapacity::get( new_size - m_capacity, m_capacity, max_size() ); + if ( new_capacity > 0 && reallocate( new_capacity, true ) ) + { + m_capacity = new_capacity; + m_size = new_size; + } + else return false; + } + m_size = new_size; + return true; + } + // TODO: return type error checking + bool try_reserve( size_t new_capacity, bool copy_needed ) + { + if ( new_capacity > m_capacity ) + { + if ( reallocate( new_capacity, copy_needed ) ) + { + m_capacity = new_capacity; + } + else return false; + } + return true; + } + // TODO: return type error checking + bool try_resize( size_t new_size, bool copy_needed ) + { + if ( new_size > m_size ) + { + if ( try_reserve( new_size, copy_needed ) ) + { + m_size = new_size; + return true; + } + return false; + } + m_size = new_size; + return true; + } + protected: + size_type m_size; + size_type m_capacity; + }; + +} + +#endif // NV_STL_CONTAINER_CONTIGUOUS_STORAGE_POLICY Index: /trunk/nv/stl/container/fixed_container_handler.hh =================================================================== --- /trunk/nv/stl/container/fixed_container_handler.hh (revision 391) +++ /trunk/nv/stl/container/fixed_container_handler.hh (revision 391) @@ -0,0 +1,62 @@ +// Copyright (C) 2015 ChaosForge Ltd +// http://chaosforge.org/ +// +// This file is part of NV Libraries. +// For conditions of distribution and use, see copyright notice in nv.hh + +/** +* @file fixed_container_handler.hh +* @author Kornel Kisielewicz epyon@chaosforge.org +* @brief fixed contiguous container handler +*/ + +#ifndef NV_STL_CONTAINER_FIXED_CONTAINER_HANDLER_HH +#define NV_STL_CONTAINER_FIXED_CONTAINER_HANDLER_HH + +#include +#include + +namespace nv +{ + + template < + typename Storage, + typename InitializePolicy = policy_initialize_standard + > + class fixed_container_handler : public Storage + { + public: + typedef typename Storage::value_type value_type; + typedef typename Storage::size_type size_type; + + fixed_container_handler() + { + InitializePolicy::initialize( data(), data() + Storage::capacity() ); + } + + explicit fixed_container_handler( default_init ) + { + uninitialized_construct( data(), data() + Storage::capacity() ); + } + + explicit fixed_container_handler( const value_type& v ) + { + uninitialized_fill( data(), data() + Storage::capacity(), v ); + } + + ~fixed_container_handler() + { + InitializePolicy::destroy( data(), data() + Storage::capacity() ); + } + + // prevent copying + fixed_container_handler( const fixed_container_handler& ) = delete; + fixed_container_handler& operator=( const fixed_container_handler& ) = delete; + // allow move + fixed_container_handler( fixed_container_handler&& ) = default; + fixed_container_handler& operator=( fixed_container_handler&& ) = default; + }; + +} + +#endif // NV_STL_CONTAINER_FIXED_CONTAINER_HANDLER_HH Index: /trunk/nv/stl/container/growing_container_handler.hh =================================================================== --- /trunk/nv/stl/container/growing_container_handler.hh (revision 391) +++ /trunk/nv/stl/container/growing_container_handler.hh (revision 391) @@ -0,0 +1,63 @@ +// Copyright (C) 2015 ChaosForge Ltd +// http://chaosforge.org/ +// +// This file is part of NV Libraries. +// For conditions of distribution and use, see copyright notice in nv.hh + +/** +* @file growing_container_handler.hh +* @author Kornel Kisielewicz epyon@chaosforge.org +* @brief growing contiguous container handler +*/ + +#ifndef NV_STL_CONTAINER_GROWING_CONTAINER_HANDLER_HH +#define NV_STL_CONTAINER_GROWING_CONTAINER_HANDLER_HH + +#include +#include +#include + +namespace nv +{ + + template < + typename Storage, + typename InitializePolicy = policy_initialize_standard + > + class growing_container_handler : public sized_container_handler< Storage, InitializePolicy > + { + typedef sized_container_handler< Storage, InitializePolicy > inherited; + public: + typedef typename Storage::value_type value_type; + typedef typename Storage::size_type size_type; + + using sized_container_handler< Storage, InitializePolicy >::sized_container_handler; + + void reserve( size_type new_capacity ) + { + Storage::try_reserve( new_capacity, true ); + } + void push_back( const value_type& e ) + { + if ( Storage::try_grow( 1 ) ) copy_construct_object( data() + size() - 1, e ); + } + void push_back( value_type&& e ) + { + if ( Storage::try_grow( 1 ) ) move_construct_object( data() + size() - 1, forward( e ) ); + } + template < typename... Args > + void emplace_back( Args&&... args ) + { + if ( Storage::try_grow( 1 ) ) construct_object( data() + size() - 1, forward( args )... ); + } + void pop_back() + { + try_resize( size() - 1, true ); + } + + }; + +} + +#endif // #define NV_STL_CONTAINER_GROWING_CONTAINER_HANDLER_HH + Index: /trunk/nv/stl/container/hash_table.hh =================================================================== --- /trunk/nv/stl/container/hash_table.hh (revision 390) +++ /trunk/nv/stl/container/hash_table.hh (revision 391) @@ -201,5 +201,5 @@ } - void clear( size_type new_count ) + void clear() { free_nodes( m_buckets, m_bucket_count ); @@ -256,5 +256,5 @@ { node_type* node = alloc_node(); - base_type::entry_construct( node, forward( args )... ); + base_type::entry_construct( node, nv::forward( args )... ); node->next = m_buckets[index]; m_buckets[index] = node; @@ -263,5 +263,5 @@ } - size_type get_bucket_index( hash_type hash_code ) + size_type get_bucket_index( hash_type hash_code ) const { return bucket_index( hash_code, m_bucket_count ); @@ -336,5 +336,5 @@ } - size_type bucket_index( hash_type hash_code, size_t b_count ) + size_type bucket_index( hash_type hash_code, size_t b_count ) const { return RangeHashPolicy::get( hash_code, b_count ); @@ -508,6 +508,6 @@ } - template < typename QueryType > - iterator do_find_node( size_type index, const QueryType& query, hash_type h ) const + template < typename ComparableType > + iterator do_find_node( size_type index, const ComparableType& query, hash_type h ) const { const_local_iterator first = this->cbegin( index ); Index: /trunk/nv/stl/container/initialize_policy.hh =================================================================== --- /trunk/nv/stl/container/initialize_policy.hh (revision 391) +++ /trunk/nv/stl/container/initialize_policy.hh (revision 391) @@ -0,0 +1,104 @@ +// Copyright (C) 2014 ChaosForge Ltd +// http://chaosforge.org/ +// +// This file is part of NV Libraries. +// For conditions of distribution and use, see copyright notice in nv.hh + +/** +* @file initialize_policy.hh +* @author Kornel Kisielewicz epyon@chaosforge.org +* @brief initialize policies +*/ + +#ifndef NV_STL_INITIALIZE_POLICY_HH +#define NV_STL_INITIALIZE_POLICY_HH + +#include +#include + +namespace nv +{ + + struct default_init + { + + }; + + struct policy_initialize_always + { + template < typename ForwardIterator > + inline static void initialize( ForwardIterator first, ForwardIterator last ) + { + uninitialized_construct( first, last ); + } + template < typename InputIterator, typename ForwardIterator > + inline static ForwardIterator copy( InputIterator first, InputIterator last, ForwardIterator out ) + { + return uninitialized_copy( first, last, out ); + } + template < typename ForwardIterator > + inline static void destroy( ForwardIterator first, ForwardIterator last ) + { + uninitialized_destroy( first, last ); + } + template < typename ForwardIterator > + inline static void destroy( ForwardIterator first ) + { + destroy_object( first ); + } + }; + + struct policy_initialize_never + { + template < typename ForwardIterator > + inline static void initialize( ForwardIterator, ForwardIterator ) + { + } + template < typename InputIterator, typename ForwardIterator > + inline static ForwardIterator copy( InputIterator first, InputIterator last, ForwardIterator out ) + { + return detail::uninitialized_copy( first, last, out, true_type ); + } + template < typename ForwardIterator > + inline static void destroy( ForwardIterator, ForwardIterator ) + { + } + template < typename ForwardIterator > + inline static void destroy( ForwardIterator ) + { + } + }; + + struct policy_initialize_standard + { + template < typename ForwardIterator > + inline static void initialize( ForwardIterator first, ForwardIterator last ) + { + typedef typename iterator_traits< ForwardIterator >::value_type value_type; + if ( !has_trivial_constructor() ) + detail::uninitialized_construct_impl( first, last, false_type() ); + } + template < typename InputIterator, typename ForwardIterator > + inline static ForwardIterator copy( InputIterator first, InputIterator last, ForwardIterator out ) + { + return uninitialized_copy( first, last, out ); + } + template < typename ForwardIterator > + inline static void destroy( ForwardIterator first, ForwardIterator last ) + { + typedef typename iterator_traits< ForwardIterator >::value_type value_type; + if ( !has_trivial_destructor() ) + detail::uninitialized_destroy_impl( first, last, false_type() ); + } + template < typename ForwardIterator > + inline static void destroy( ForwardIterator first ) + { + typedef typename iterator_traits< ForwardIterator >::value_type value_type; + if ( !has_trivial_destructor() ) + destroy_object( first ); + } + }; + +} + +#endif // NV_STL_INITIALIZE_POLICY_HH Index: /trunk/nv/stl/container/sized_container_handler.hh =================================================================== --- /trunk/nv/stl/container/sized_container_handler.hh (revision 391) +++ /trunk/nv/stl/container/sized_container_handler.hh (revision 391) @@ -0,0 +1,139 @@ +// Copyright (C) 2015 ChaosForge Ltd +// http://chaosforge.org/ +// +// This file is part of NV Libraries. +// For conditions of distribution and use, see copyright notice in nv.hh + +/** +* @file sized_container_handler.hh +* @author Kornel Kisielewicz epyon@chaosforge.org +* @brief sized contiguous container handler +*/ + +#ifndef NV_STL_CONTAINER_SIZED_CONTAINER_HANDLER_HH +#define NV_STL_CONTAINER_SIZED_CONTAINER_HANDLER_HH + +#include +#include + +namespace nv +{ + + template < + typename Storage, + typename InitializePolicy = policy_initialize_standard + > + class sized_container_handler : public Storage + { + public: + typedef typename Storage::value_type value_type; + typedef typename Storage::size_type size_type; + + inline sized_container_handler() {} + inline explicit sized_container_handler( size_type new_size ) { resize( new_size ); } + inline explicit sized_container_handler( default_init ) { resize( default_init() ); } + inline sized_container_handler( size_type new_size, const value_type& v ) { resize( new_size, v ); } + + // prevent copying + sized_container_handler( const sized_container_handler& ) = delete; + sized_container_handler& operator=( const sized_container_handler& ) = delete; + // allow move + sized_container_handler( sized_container_handler&& ) = default; + sized_container_handler& operator=( sized_container_handler&& ) = default; + + + inline void resize( size_type new_size ) + { + size_type old_size = Storage::size(); + resize_impl( new_size ); + initialize_range( old_size, Storage::size() ); + } + + inline void resize( size_type new_size, default_init ) + { + size_type old_size = Storage::size(); + resize_impl( new_size ); + initialize_range( old_size, Storage::size(), default_init() ); + } + + inline void resize( size_type new_size, const value_type& value ) + { + size_type old_size = Storage::size(); + resize_impl( new_size ); + initialize_range( old_size, Storage::size(), value ); + } + + inline void assign( const value_type* ptr, size_type sz ) + { + if ( Storage::size() > 0 ) InitializePolicy::destroy( Storage::data(), Storage::data() + Storage::size() ); + if ( ptr != nullptr && sz > 0 ) + { + if ( sz != Storage::size() && Storage::try_resize( sz, false ) ) + InitializePolicy::copy( ptr, ptr + sz, Storage::data() ); + } + else Storage::try_resize( 0, false ); + } + + template< typename InputIterator > + inline void assign( InputIterator first, InputIterator last ) + { + size_type d = distance( first, last ); + if ( d != Storage::size() && Storage::try_resize( sz, false ) ) + InitializePolicy::copy( first, last, Storage::data() ); + } + + // explicit copy + inline void assign( const sized_container_handler& other ) + { + assign( other.data(), other.size() ); + } + + inline void clear() + { + if ( Storage::size() > 0 ) + { + InitializePolicy::destroy( Storage::data(), Storage::data() + Storage::size() ); + Storage::try_resize( 0, false ); + } + } + + ~sized_container_handler() + { + if ( Storage::size() > 0 ) clear(); + } + + protected: + + inline void initialize_range( size_type old_size, size_type new_size ) + { + if ( new_size > old_size ) InitializePolicy::initialize( Storage::data() + old_size, Storage::data() + new_size ); + } + inline void initialize_range( size_type old_size, size_type new_size, default_init ) + { + if ( new_size > old_size ) uninitialized_construct( Storage::data() + old_size, Storage::data() + new_size ); + } + inline void initialize_range( size_type old_size, size_type new_size, const value_type& value ) + { + if ( new_size > old_size ) uninitialized_fill( Storage::data() + old_size, Storage::data() + new_size, value ); + } + inline void resize_impl( size_type new_size ) + { + size_type old_size = Storage::size(); + if ( new_size != old_size ) + { + if ( new_size < old_size ) + { + InitializePolicy::destroy( Storage::data() + new_size, Storage::data() + old_size ); + } + if ( Storage::try_resize( new_size, true ) ) + { + // TODO: error checking + } + } + } + + }; + +} + +#endif // NV_STL_CONTAINER_SIZED_CONTAINER_HANDLER_HH Index: /trunk/nv/stl/functional/hash.hh =================================================================== --- /trunk/nv/stl/functional/hash.hh (revision 390) +++ /trunk/nv/stl/functional/hash.hh (revision 391) @@ -59,9 +59,9 @@ } protected: - constexpr H str_hash_impl( char c, const char* remain, H value ) + static constexpr H str_hash_impl( char c, const char* remain, H value ) { return c == 0 ? value : str_hash_impl( remain[0], remain + 1, (H)(H)( value ^ (H)c ) * hash_prime ); } - constexpr H hash_impl( const char* current, size_t remain, H value ) + static constexpr H hash_impl( const char* current, size_t remain, H value ) { return remain == 0 ? value : hash_impl( current + 1, remain - 1, (H)(H)( value ^ (H)(current[0]) ) * hash_prime ); @@ -120,5 +120,5 @@ return value == 0.0f ? detail::fnv_hash( &value, 1 ) : 0; }; - inline H operator()( float value ) const { return hash( value ); } + inline H operator()( float value ) const { return get( value ); } }; @@ -131,5 +131,5 @@ return value == 0.0f ? detail::fnv_hash( &value, 1 ) : 0; }; - inline H operator()( float value ) const { return hash( value ); } + inline H operator()( float value ) const { return get( value ); } }; Index: /trunk/nv/stl/memory.hh =================================================================== --- /trunk/nv/stl/memory.hh (revision 390) +++ /trunk/nv/stl/memory.hh (revision 391) @@ -22,4 +22,5 @@ #include #include +#include namespace nv @@ -138,5 +139,5 @@ } - template < typename T > + template< typename T > inline void copy_construct_object( T* object, const T& original ) { Index: /trunk/nv/stl/vector.hh =================================================================== --- /trunk/nv/stl/vector.hh (revision 391) +++ /trunk/nv/stl/vector.hh (revision 391) @@ -0,0 +1,38 @@ +// Copyright (C) 2014 ChaosForge Ltd +// http://chaosforge.org/ +// +// This file is part of NV Libraries. +// For conditions of distribution and use, see copyright notice in nv.hh + +/** +* @file vector.hh +* @author Kornel Kisielewicz epyon@chaosforge.org +* @brief exception free vector class +*/ + +#ifndef NV_STL_VECTOR_HH +#define NV_STL_VECTOR_HH + +#include +#include +#include +#include + +namespace nv +{ + + template< typename T > + using growable_dynamic_storage = growable_storage< dynamic_storage< T > >; + + template< typename T, size_t N > + using growable_static_storage = growable_storage< static_storage< T, N > >; + + template< typename T > + using vector = + detail::add_random_access < + detail::add_iterators < + growing_container_handler< growable_dynamic_storage< T > > > >; + +} + +#endif // NV_CORE_VECTOR_HH Index: /trunk/src/stl/hash_table.cc =================================================================== --- /trunk/src/stl/hash_table.cc (revision 391) +++ /trunk/src/stl/hash_table.cc (revision 391) @@ -0,0 +1,63 @@ +// Copyright (C) 2015 ChaosForge Ltd +// http://chaosforge.org/ +// +// This file is part of NV Libraries. +// For conditions of distribution and use, see copyright notice in nv.hh + +#include "nv/stl/container/hash_table.hh" +#include "nv/stl/container/hash_table_policy.hh" + +using namespace nv; + +static const uint32 s_primes[] = +{ + 2U, 3U, 5U, 7U, 11U, 13U, 17U, 19U, + 23U, 29U, 31U, 37U, 41U, 43U, 47U, 53U, + 59U, 61U, 67U, 71U, 73U, 79U, 83U, 89U, + 97U, 103U, 109U, 113U, 127U, 137U, 139U, 149U, + 157U, 167U, 179U, 193U, 199U, 211U, 227U, 241U, + 257U, 277U, 293U, 313U, 337U, 359U, 383U, 409U, + 439U, 467U, 503U, 541U, 577U, 619U, 661U, 709U, + 761U, 823U, 887U, 953U, 1031U, 1109U, 1193U, 1289U, + 1381U, 1493U, 1613U, 1741U, 1879U, 2029U, 2179U, 2357U, + 2549U, 2753U, 2971U, 3209U, 3469U, 3739U, 4027U, 4349U, + 4703U, 5087U, 5503U, 5953U, 6427U, 6949U, 7517U, 8123U, + 8783U, 9497U, 10273U, 11113U, 12011U, 12983U, 14033U, 15173U, + 16411U, 17749U, 19183U, 20753U, 22447U, 24281U, 26267U, 28411U, + 30727U, 33223U, 35933U, 38873U, 42043U, 45481U, 49201U, 53201U, + 57557U, 62233U, 67307U, 72817U, 78779U, 85229U, 92203U, 99733U, + 107897U, 116731U, 126271U, 136607U, 147793U, 159871U, 172933U, 187091U, + 202409U, 218971U, 236897U, 256279U, 277261U, 299951U, 324503U, 351061U, + 379787U, 410857U, 444487U, 480881U, 520241U, 562841U, 608903U, 658753U, + 712697U, 771049U, 834181U, 902483U, 976369U, 1056323U, 1142821U, 1236397U, + 1337629U, 1447153U, 1565659U, 1693859U, 1832561U, 1982627U, 2144977U, 2320627U, + 2510653U, 2716249U, 2938679U, 3179303U, 3439651U, 3721303U, 4026031U, 4355707U, + 4712381U, 5098259U, 5515729U, 5967347U, 6456007U, 6984629U, 7556579U, 8175383U, + 8844859U, 9569143U, 10352717U, 11200489U, 12117689U, 13109983U, 14183539U, 15345007U, + 16601593U, 17961079U, 19431899U, 21023161U, 22744717U, 24607243U, 26622317U, 28802401U, + 31160981U, 33712729U, 36473443U, 39460231U, 42691603U, 46187573U, 49969847U, 54061849U, + 58488943U, 63278561U, 68460391U, 74066549U, 80131819U, 86693767U, 93793069U, 101473717U, + 109783337U, 118773397U, 128499677U, 139022417U, 150406843U, 162723577U, 176048909U, 190465427U, + 206062531U, 222936881U, 241193053U, 260944219U, 282312799U, 305431229U, 330442829U, 357502601U, + 386778277U, 418451333U, 452718089U, 489790921U, 529899637U, 573292817U, 620239453U, 671030513U, + 725980837U, 785430967U, 849749479U, 919334987U, 994618837U, 1076067617U, 1164186217U, 1259520799U, + 1362662261U, 1474249943U, 1594975441U, 1725587117U, 1866894511U, 2019773507U, 2185171673U, 2364114217U, + 2557710269U, 2767159799U, 2993761039U, 3238918481U, 3504151727U, 3791104843U, 4101556399U, 4294967291U, + 4294967291U // sentinel +}; + +static const nv::uint32 s_primes_size = ( sizeof( s_primes ) / sizeof( *s_primes ) ); + +namespace nv +{ + void* g_hash_table_empty[2] = { nullptr, (void*)uintptr_t( ~0 ) }; +} + +nv::uint32 nv::get_prime_larger_or_equal_to( nv::uint32 value ) +{ + NV_ASSERT( value < 4294967291, "value too large!" ); + if ( value < 3 ) return 2; + uint32 i = 0; + while ( s_primes[i] < value ) ++i; + return s_primes[i]; +}