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
- browse files at revision 57
- compare with another revision
- download diff
- download tarball
- view history from revision 57
- Committer: edam
- Date: 2012-02-25 01:31:43 UTC
- Revision ID: tim@ed.am-20120225013143-9fet2y2d3fjlrwez
added ulibc
- files added:
- src/utility
added
removed
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
Loggerhead is a web-based interface for Bazaar branches
Version: 1.18.2, Revision: 480