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
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 minimum = nv::min<SizeType>( capacity, 4 );
38                        SizeType remaining = max_size - capacity;
39                        if ( remaining < requested ) return 0;
40                        SizeType additional = nv::max( requested, capacity );
41                        return nv::max( minimum, remaining < additional ? max_size : capacity + additional );
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
171        template< typename T, size_t N >
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 > > >;
596       
597        template< typename T >
598        using dynamic_array = array_base_t < sized_container_allocator< resizable_dynamic_storage< T > > >;
599
600        template< typename T >
601        using vector = array_base_t < growing_container_allocator< growable_dynamic_storage< T > > >;
602
603}
604
605#endif // NV_CORE_ARRAY_HH
Note: See TracBrowser for help on using the repository browser.