/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: 2012-02-25 01:31:43 UTC
  • Revision ID: tim@ed.am-20120225013143-9fet2y2d3fjlrwez
added ulibc

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/utility/vector
 
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