/elec/propeller-clock

To get this branch, use:
bzr branch http://bzr.ed.am/elec/propeller-clock

« back to all changes in this revision

Viewing changes to src/utility/vector

  • Committer: edam
  • Date: 2011-11-04 13:48:15 UTC
  • Revision ID: edam@waxworlds.org-20111104134815-kj7qdhqfbxaj1tng
finished writing up electronics notes

Show diffs side-by-side

added added

removed removed

Lines of Context:
1
 
/*      Copyright (C) 2004 Garrett A. Kajmowicz
2
 
 
3
 
        This file is part of the uClibc++ Library.
4
 
 
5
 
        This library is free software; you can redistribute it and/or
6
 
        modify it under the terms of the GNU Lesser General Public
7
 
        License as published by the Free Software Foundation; either
8
 
        version 2.1 of the License, or (at your option) any later version.
9
 
 
10
 
        This library is distributed in the hope that it will be useful,
11
 
        but WITHOUT ANY WARRANTY; without even the implied warranty of
12
 
        MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13
 
        Lesser General Public License for more details.
14
 
 
15
 
        You should have received a copy of the GNU Lesser General Public
16
 
        License along with this library; if not, write to the Free Software
17
 
        Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
18
 
 
19
 
*/
20
 
 
21
 
#include <basic_definitions>
22
 
#include <memory>
23
 
#include <iterator>
24
 
#include <func_exception>
25
 
#include <algorithm>
26
 
#include <type_traits>
27
 
 
28
 
 
29
 
#ifndef __STD_HEADER_VECTOR
30
 
#define __STD_HEADER_VECTOR
31
 
 
32
 
#pragma GCC visibility push(default)
33
 
 
34
 
namespace std{
35
 
 
36
 
        template <class T, class Allocator = allocator<T> > class vector;
37
 
        template <class T, class Allocator> bool operator==(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
38
 
        template <class T, class Allocator> bool operator< (const vector<T,Allocator>& x, const vector<T,Allocator>& y);
39
 
        template <class T, class Allocator> bool operator!=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
40
 
        template <class T, class Allocator> bool operator> (const vector<T,Allocator>& x, const vector<T,Allocator>& y);
41
 
        template <class T, class Allocator> bool operator>=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
42
 
        template <class T, class Allocator> bool operator<=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
43
 
        template <class T, class Allocator> void swap(vector<T,Allocator>& x, vector<T,Allocator>& y);
44
 
 
45
 
        template <class T, class Allocator> class _UCXXEXPORT vector {
46
 
        public:
47
 
 
48
 
                typedef typename Allocator::reference reference;
49
 
                typedef typename Allocator::const_reference const_reference;
50
 
                typedef typename Allocator::size_type size_type;
51
 
                typedef typename Allocator::difference_type difference_type;
52
 
                typedef typename Allocator::pointer pointer;
53
 
                typedef typename Allocator::const_pointer const_pointer;
54
 
 
55
 
                typedef T* iterator;
56
 
                typedef const T* const_iterator;
57
 
                typedef T value_type;
58
 
                typedef Allocator allocator_type;
59
 
                typedef std::reverse_iterator<iterator> reverse_iterator;
60
 
                typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
61
 
 
62
 
                explicit _UCXXEXPORT vector(const Allocator& al= Allocator()): data(0), //defaultValue(T()), 
63
 
                        data_size(__UCLIBCXX_STL_BUFFER_SIZE__), elements(0), a(al)
64
 
                {
65
 
                        data = a.allocate(data_size);
66
 
                }
67
 
 
68
 
                explicit _UCXXEXPORT vector(size_type n, const T& value = T(), const Allocator& al= Allocator()) : 
69
 
                        data(0), data_size(0), elements(0), a(al)
70
 
                {
71
 
                        data_size = n + __UCLIBCXX_STL_BUFFER_SIZE__;
72
 
                        data = a.allocate(data_size);
73
 
 
74
 
                        resize(n, value);
75
 
                }
76
 
 
77
 
                template <class InputIterator> _UCXXEXPORT 
78
 
                        vector(InputIterator first, InputIterator last, const Allocator& al = Allocator()):
79
 
                        data(0), data_size(__UCLIBCXX_STL_BUFFER_SIZE__), elements(0), a(al)
80
 
                {
81
 
                        data = a.allocate(data_size);
82
 
                        assign(first, last);
83
 
                }
84
 
 
85
 
                _UCXXEXPORT vector(const vector<T,Allocator>& x){
86
 
                        a = x.a;
87
 
 
88
 
                        elements  = x.elements;
89
 
                        data_size = elements + __UCLIBCXX_STL_BUFFER_SIZE__;
90
 
                        data = a.allocate(data_size);
91
 
 
92
 
                        for(size_type i = 0; i < elements; i++){
93
 
                                a.construct(data+i, x.data[i]);
94
 
                        }       
95
 
                }
96
 
 
97
 
                _UCXXEXPORT ~vector();  //Below
98
 
 
99
 
                _UCXXEXPORT vector<T,Allocator>& operator=(const vector<T,Allocator>& x){
100
 
                        if(&x == this){
101
 
                                return *this;
102
 
                        }
103
 
 
104
 
                        reserve(x.elements);    //Make sure that we have enough actual memory
105
 
 
106
 
 
107
 
                        //Copy as many elements as possible
108
 
 
109
 
                        size_t minElements = elements;
110
 
                        if(minElements > x.elements){
111
 
                                minElements = x.elements;
112
 
                        }
113
 
                        for(size_t i = 0; i < minElements; ++i){
114
 
                                data[i] = x.data[i];
115
 
                        }
116
 
 
117
 
                        //If we need to add new elements
118
 
                        if(elements < x.elements){
119
 
                                for(size_t i = elements; i< x.elements; ++i){
120
 
                                        a.construct(data+i, x.data[i]);
121
 
                                        ++elements;
122
 
                                }
123
 
                        }
124
 
 
125
 
                        if(elements > x.elements){
126
 
                                downsize(x.elements);
127
 
                        }
128
 
 
129
 
                        return *this;
130
 
                }
131
 
 
132
 
                template <class InputIterator> _UCXXEXPORT void assign(InputIterator first, InputIterator last){
133
 
                        clear();
134
 
                        insert(begin(), first, last);
135
 
                }
136
 
 
137
 
                template <class Size, class U> _UCXXEXPORT void assign(Size n, const U& u = U()){
138
 
                        clear();
139
 
                        resize(n, u);
140
 
                }
141
 
 
142
 
                inline allocator_type get_allocator() const{
143
 
                        return a;
144
 
                }
145
 
 
146
 
                inline iterator begin(){
147
 
                        return data;
148
 
                }
149
 
 
150
 
                inline const_iterator begin() const{
151
 
                        return data;
152
 
                }
153
 
 
154
 
                inline iterator end(){
155
 
                        return (data + elements);
156
 
                }
157
 
 
158
 
                inline const_iterator end() const{
159
 
                        return (data + elements);
160
 
                }
161
 
 
162
 
                inline reverse_iterator rbegin(){
163
 
                        return reverse_iterator(end());
164
 
                }
165
 
 
166
 
                inline const_reverse_iterator rbegin() const{
167
 
                        return const_reverse_iterator(end());
168
 
                }
169
 
 
170
 
                inline reverse_iterator rend(){
171
 
                        return reverse_iterator(begin());
172
 
                }
173
 
 
174
 
                inline const_reverse_iterator rend() const{
175
 
                        return const_reverse_iterator(begin());
176
 
                }
177
 
 
178
 
                inline size_type size() const{
179
 
                        return elements;
180
 
                }
181
 
 
182
 
                _UCXXEXPORT size_type max_size() const{
183
 
                        return ((size_type)(-1)) / sizeof(T);
184
 
                }
185
 
 
186
 
                void downsize(size_type sz);
187
 
                void resize(size_type sz, const T & c = T());
188
 
 
189
 
                inline size_type capacity() const{
190
 
                        return data_size;
191
 
                }
192
 
 
193
 
                inline bool empty() const{
194
 
                        return (size() == 0);
195
 
                }
196
 
 
197
 
                void reserve(size_type n);
198
 
 
199
 
                inline reference operator[](size_type n){
200
 
                        return data[n];
201
 
                }
202
 
 
203
 
                inline const_reference operator[](size_type n) const{
204
 
                        return data[n];
205
 
                }
206
 
 
207
 
                _UCXXEXPORT const_reference at(size_type n) const{
208
 
                        if(n >= elements){
209
 
                                __throw_out_of_range("Invalid subscript");
210
 
                        }
211
 
                        return data[n];
212
 
                }
213
 
 
214
 
                _UCXXEXPORT reference at(size_type n){
215
 
                        if(n >= elements){
216
 
                                __throw_out_of_range("Invalid subscript");
217
 
                        }
218
 
                        return data[n];
219
 
                }
220
 
 
221
 
                inline reference front(){
222
 
                        return data[0];
223
 
                }
224
 
 
225
 
                inline const_reference front() const{
226
 
                        return data[0];
227
 
                }
228
 
 
229
 
                inline reference back(){
230
 
                        return data[ size() - 1];
231
 
                }
232
 
 
233
 
                inline const_reference back() const{
234
 
                        return data[ size() - 1 ];
235
 
                }
236
 
 
237
 
                inline void push_back(const T& x){
238
 
                        resize( size() + 1, x);
239
 
                }
240
 
 
241
 
                inline void pop_back(){
242
 
                        downsize(size() - 1);
243
 
                }
244
 
 
245
 
                _UCXXEXPORT iterator insert(iterator position, const T& x = T()){
246
 
                        size_type index = position - data;
247
 
                        resize(size() + 1, x);
248
 
                        for(size_type i = elements - 1; i > index; --i){
249
 
                                data[i] = data[i-1];
250
 
                        }
251
 
                        data[index] = x;
252
 
                        return (data + index);
253
 
                }
254
 
 
255
 
                _UCXXEXPORT void _insert_fill(iterator position, size_type n, const T & x){
256
 
                        size_type index = position - data;
257
 
                        resize(size() + n, x);
258
 
 
259
 
                        for(size_type i = elements -1; (i > (index+n-1)); --i){
260
 
                                data[i] = data[i-n];
261
 
                        }
262
 
                        for(size_type i = 0; i < n; i++){
263
 
                                data[i + index]  = x;
264
 
                        }
265
 
                }
266
 
 
267
 
                template <class InputIterator> _UCXXEXPORT 
268
 
                        void _insert_from_iterator(iterator position, InputIterator first, InputIterator last)
269
 
                {
270
 
                        T temp;
271
 
                        while(first !=last){
272
 
                                temp = *first;
273
 
                                position = insert(position, temp);
274
 
                                ++position;
275
 
                                ++first;
276
 
                        }
277
 
                }
278
 
 
279
 
                template <class InputIterator>
280
 
                        inline void _dispatch_insert(iterator position, InputIterator first, InputIterator last, __true_type)
281
 
                {
282
 
                        _insert_fill(position, first, last);
283
 
                }
284
 
 
285
 
                template <class InputIterator>
286
 
                        inline void _dispatch_insert(iterator position, InputIterator first, InputIterator last, __false_type)
287
 
                {
288
 
                                _insert_from_iterator(position, first, last);
289
 
                }
290
 
 
291
 
                inline void insert(iterator position, size_type n, const T& x ){
292
 
                        _insert_fill(position, n, x);
293
 
                }
294
 
 
295
 
                template <class InputIterator> inline void insert(iterator position, InputIterator first, InputIterator last){
296
 
                        typedef typename __is_integer<InputIterator>::value __some_type;
297
 
                        _dispatch_insert(position, first, last, __some_type());
298
 
                }
299
 
 
300
 
                _UCXXEXPORT iterator erase(iterator position){
301
 
                        size_type index = position - data;
302
 
                        for(size_type i = index; i < (elements - 1); ++i){
303
 
                                data[i] = data[i+1];
304
 
                        }
305
 
                        downsize(size() - 1);
306
 
                        return (data + index);
307
 
                }
308
 
 
309
 
                _UCXXEXPORT iterator erase(iterator first, iterator last){
310
 
                        size_type index = first - data;
311
 
                        size_type width = last - first;
312
 
                        for(size_type i = index; i < (elements - width) ;++i){
313
 
                                data[i] = data[i+width];
314
 
                        }
315
 
                        downsize(size() - width);
316
 
                        return (data + index);
317
 
                }
318
 
 
319
 
                _UCXXEXPORT void swap(vector<T,Allocator>& v){
320
 
                        if(this == &v){         //Avoid dv.swap(v)
321
 
                                return;
322
 
                        }
323
 
                        T* ptr;
324
 
                        size_type temp;
325
 
 
326
 
                        //Swap pointers first
327
 
                        ptr = data;
328
 
                        data = v.data;
329
 
                        v.data  = ptr;
330
 
 
331
 
                        //Swap element counts
332
 
                        temp = elements;
333
 
                        elements = v.elements;
334
 
                        v.elements = temp;
335
 
 
336
 
                        //Swap data size
337
 
                        temp = data_size;
338
 
                        data_size = v.data_size;
339
 
                        v.data_size = temp;
340
 
                }
341
 
 
342
 
                _UCXXEXPORT void clear(){
343
 
                        downsize(0);
344
 
                }
345
 
 
346
 
        protected:
347
 
                T* data;
348
 
                size_type data_size;
349
 
                size_type elements;
350
 
                Allocator a;
351
 
        };
352
 
 
353
 
 
354
 
 
355
 
        //Here go template instantiations
356
 
 
357
 
        template<class T, class Allocator> _UCXXEXPORT vector<T, Allocator>::~vector(){
358
 
                for(size_t i = 0; i < elements; ++i){
359
 
                        a.destroy(data + i);
360
 
                }
361
 
                a.deallocate(data, data_size);
362
 
        }
363
 
 
364
 
 
365
 
        template<class T, class Allocator> _UCXXEXPORT void vector<T, Allocator>::reserve(size_type n){
366
 
                if(n > data_size){              //We never shrink...
367
 
                        T * temp_ptr = data;
368
 
                        size_type temp_size = data_size;
369
 
 
370
 
                        data_size = n;
371
 
                        data = a.allocate(data_size);
372
 
 
373
 
                        for(size_type i = 0; i<elements; ++i){
374
 
                                a.construct(data+i, temp_ptr[i]);
375
 
                                a.destroy(temp_ptr+i);
376
 
                        }
377
 
                        a.deallocate(temp_ptr, temp_size);
378
 
                }
379
 
        }
380
 
 
381
 
        template<class T, class Allocator> _UCXXEXPORT void vector<T, Allocator>::resize(size_type sz, const T & c){
382
 
                if(sz > elements){      //Need to actually call constructor
383
 
                        if(sz > data_size){
384
 
                                reserve(sz + __UCLIBCXX_STL_BUFFER_SIZE__);
385
 
                        }
386
 
 
387
 
                        for(size_type i = elements; i<sz ; ++i){
388
 
                                a.construct(data+i, c);
389
 
                        }
390
 
                        elements = sz;
391
 
                }else{
392
 
                        downsize(sz);
393
 
                }
394
 
        }
395
 
 
396
 
        template<class T, class Allocator> _UCXXEXPORT void vector<T, Allocator>::downsize(size_type sz){
397
 
                if(sz < elements){      //Actually are downsizing
398
 
                        for(size_t i = sz; i< elements; ++i){
399
 
                                a.destroy(data+i);
400
 
                        }
401
 
                        elements = sz;
402
 
                }
403
 
        }
404
 
 
405
 
 
406
 
#ifndef __UCLIBCXX_COMPILE_VECTOR__
407
 
#ifdef __UCLIBCXX_EXPAND_VECTOR_BASIC__
408
 
 
409
 
 
410
 
#ifdef __UCLIBCXX_EXPAND_CONSTRUCTORS_DESTRUCTORS__
411
 
        template<> _UCXXEXPORT vector<char, allocator<char> >::vector(const allocator<char>& al);
412
 
        template<> _UCXXEXPORT vector<char, allocator<char> >::vector(size_type n, const char & value, const allocator<char> & al);
413
 
 
414
 
        template<> _UCXXEXPORT vector<char, allocator<char> >::~vector();
415
 
        template<> _UCXXEXPORT vector<unsigned char, allocator<unsigned char> >::~vector();
416
 
 
417
 
#endif //__UCLIBCXX_EXPAND_CONSTRUCTORS_DESTRUCTORS__
418
 
 
419
 
        template<> _UCXXEXPORT void vector<char, allocator<char> >::reserve(size_type n);
420
 
        template<> _UCXXEXPORT void vector<unsigned char, allocator<unsigned char> >::reserve(size_type n);
421
 
        template<> _UCXXEXPORT void vector<short int, allocator<short int> >::reserve(size_type n);
422
 
        template<> _UCXXEXPORT void vector<unsigned short int, allocator<unsigned short int> >::reserve(size_type n);
423
 
        template<> _UCXXEXPORT void vector<int, allocator<int> >::reserve(size_type n);
424
 
        template<> _UCXXEXPORT void vector<unsigned int, allocator<unsigned int> >::reserve(size_type n);
425
 
        template<> _UCXXEXPORT void vector<long int, allocator<long int> >::reserve(size_type n);
426
 
        template<> _UCXXEXPORT void vector<unsigned long int, allocator<unsigned long int> >::reserve(size_type n);
427
 
        template<> _UCXXEXPORT void vector<float, allocator<float> >::reserve(size_type n);
428
 
        template<> _UCXXEXPORT void vector<double, allocator<double> >::reserve(size_type n);
429
 
        template<> _UCXXEXPORT void vector<bool, allocator<bool> >::reserve(size_type n);
430
 
 
431
 
        template<> _UCXXEXPORT void vector<char, allocator<char> >::resize(size_type sz, const char & c);
432
 
        template<> _UCXXEXPORT void
433
 
                vector<unsigned char, allocator<unsigned char> >::resize(size_type sz, const unsigned char & c);
434
 
        template<> _UCXXEXPORT void vector<short int, allocator<short int> >::resize(size_type sz, const short & c);
435
 
        template<> _UCXXEXPORT void
436
 
                vector<unsigned short int, allocator<unsigned short int> >::resize(size_type sz, const unsigned short int & c);
437
 
        template<> _UCXXEXPORT void vector<int, allocator<int> >::resize(size_type sz, const int & c);
438
 
        template<> _UCXXEXPORT void vector<unsigned int, allocator<unsigned int> >::resize(size_type sz, const unsigned int & c);
439
 
        template<> _UCXXEXPORT void vector<long int, allocator<long int> >::resize(size_type sz, const long int & c);
440
 
        template<> _UCXXEXPORT void
441
 
                vector<unsigned long int, allocator<unsigned long int> >::resize(size_type sz, const unsigned long int & c);
442
 
        template<> _UCXXEXPORT void vector<float, allocator<float> >::resize(size_type sz, const float & c);
443
 
        template<> _UCXXEXPORT void vector<double, allocator<double> >::resize(size_type sz, const double & c);
444
 
        template<> _UCXXEXPORT void vector<bool, allocator<bool> >::resize(size_type sz, const bool & c);
445
 
 
446
 
#elif defined __UCLIBCXX_EXPAND_STRING_CHAR__
447
 
 
448
 
#ifdef __UCLIBCXX_EXPAND_CONSTRUCTORS_DESTRUCTORS__
449
 
 
450
 
        template<> _UCXXEXPORT vector<char, allocator<char> >::vector(const allocator<char>& al);
451
 
        template<> _UCXXEXPORT vector<char, allocator<char> >::vector(size_type n, const char & value, const allocator<char> & al);
452
 
        template<> _UCXXEXPORT vector<char, allocator<char> >::~vector();
453
 
 
454
 
#endif
455
 
 
456
 
        template<> _UCXXEXPORT void vector<char, allocator<char> >::reserve(size_type n);
457
 
        template<> _UCXXEXPORT void vector<char, allocator<char> >::resize(size_type sz, const char & c);
458
 
 
459
 
#endif
460
 
#endif
461
 
 
462
 
 
463
 
 
464
 
        template <class T, class Allocator> _UCXXEXPORT bool
465
 
                operator==(const vector<T,Allocator>& x, const vector<T,Allocator>& y)
466
 
        {
467
 
                if(x.size() !=y.size() ){
468
 
                        return false;
469
 
                }
470
 
                for(size_t i = 0; i < x.size(); ++i){
471
 
                        if(x[i] != y[i]){
472
 
                                return false;
473
 
                        }
474
 
                }
475
 
                return true;
476
 
        }
477
 
 
478
 
        template <class T, class Allocator> _UCXXEXPORT bool
479
 
                operator< (const vector<T,Allocator>& x, const vector<T,Allocator>& y)
480
 
        {
481
 
                less<typename iterator_traits<typename vector<T,Allocator>::iterator >::value_type> c;
482
 
                return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end(), c);
483
 
        }
484
 
        template <class T, class Allocator> _UCXXEXPORT bool
485
 
                operator!=(const vector<T,Allocator>& x, const vector<T,Allocator>& y)
486
 
        {
487
 
                return !(x == y);
488
 
        }
489
 
        template <class T, class Allocator> _UCXXEXPORT bool
490
 
                operator> (const vector<T,Allocator>& x, const vector<T,Allocator>& y)
491
 
        {
492
 
                greater<typename iterator_traits<typename vector<T,Allocator>::iterator >::value_type> c;
493
 
                return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end(), c);
494
 
        }
495
 
        template <class T, class Allocator> _UCXXEXPORT bool
496
 
                operator>=(const vector<T,Allocator>& x, const vector<T,Allocator>& y)
497
 
        {
498
 
                greater_equal<typename iterator_traits<typename vector<T,Allocator>::iterator >::value_type> c;
499
 
                return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end(), c);
500
 
        }
501
 
        template <class T, class Allocator> _UCXXEXPORT bool
502
 
                operator<=(const vector<T,Allocator>& x, const vector<T,Allocator>& y)
503
 
        {
504
 
                less_equal<typename iterator_traits<typename vector<T,Allocator>::iterator >::value_type> c;
505
 
                return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end(), c);
506
 
        }
507
 
 
508
 
        template <class T, class Allocator> _UCXXEXPORT void swap(vector<T,Allocator>& x, vector<T,Allocator>& y){
509
 
                x.swap(y);
510
 
        }
511
 
 
512
 
}
513
 
 
514
 
#pragma GCC visibility pop
515
 
 
516
 
#endif
517