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
Line 
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
13#ifndef NV_CORE_ARRAY_HH
14#define NV_CORE_ARRAY_HH
15
16#include <nv/core/common.hh>
17#include <nv/stl/memory.hh>
18#include <nv/stl/iterator.hh>
19#include <nv/stl/utility.hh>
20#include <vector>
21#include <algorithm>
22#include <array>
23
24namespace nv
25{
26
27        struct default_init
28        {
29
30        };
31
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
170        template< typename T, size_t N >
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 > > >;
595       
596        template< typename T >
597        using dynamic_array = array_base_t < sized_container_allocator< resizable_dynamic_storage< T > > >;
598
599        template< typename T >
600        using vector = array_base_t < growing_container_allocator< growable_dynamic_storage< T > > >;
601
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;
615//
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;
635//
636//              static_vector() : m_size(0) {}
637//
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//      };
654
655}
656
657#endif // NV_CORE_ARRAY_HH
Note: See TracBrowser for help on using the repository browser.