Usermode/Libraries/libc++.so_src/include_exp/vector

   1 /*
   2  * Acess2 C++ Library
   3  * - By John Hodge (thePowersGang)
   4  *
   5  * vector (header)
   6  * - C++'s vector (dynamic array) type
   7  */
   8 #ifndef _LIBCXX_VECTOR_
   9 #define _LIBCXX_VECTOR_
  10
  11 #include <allocator>
  12 #include <stdexcept>
  13
  14 extern "C" void _SysDebug(const char *, ...);
  15
  16 namespace std {
  17
  18 namespace _bits {
  19 template <class VectorType, class T>
  20 class vector_iterator//:
  21         //public random_acess_iterator_tag
  22 {
  23         friend VectorType;
  24
  25         typedef typename VectorType::size_type  size_type;
  26         typedef typename VectorType::difference_type    difference_type;
  27
  28         T*      m_array;
  29         size_type       m_pos;
  30         size_type       m_max;
  31 public:
  32         vector_iterator():
  33                 vector_iterator(0,0,0)
  34         {
  35         }
  36         vector_iterator(const vector_iterator& x):
  37                 vector_iterator()
  38         {
  39                 *this = x;
  40         }
  41         vector_iterator(T* array, size_type start, size_type max):
  42                 m_array(array),
  43                 m_pos(start),
  44                 m_max(max)
  45         {
  46         }
  47         vector_iterator& operator=(const vector_iterator& x)
  48         {
  49                 m_array = x.m_array;
  50                 m_pos = x.m_pos;
  51                 m_max = x.m_max;
  52                 return *this;
  53         }
  54         bool operator==(const vector_iterator& other) const {
  55                 return m_pos == other.m_pos;
  56         }
  57         bool operator!=(const vector_iterator& other) const {
  58                 return !(*this == other);
  59         }
  60         T& operator*() const {
  61                 return m_array[m_pos];
  62         }
  63         T& operator->() const {
  64                 return m_array[m_pos];
  65         }
  66         T& operator[](difference_type n) {
  67                 return *(*this + n);
  68         }
  69         vector_iterator& operator++() {
  70                 if(m_pos < m_max) {
  71                         m_pos ++;
  72                 }
  73                 return *this;
  74         }
  75         const vector_iterator operator++(int) {
  76                 vector_iterator ret(*this);
  77                 ++*this;
  78                 return ret;
  79         }
  80         vector_iterator& operator--() {
  81                 if(m_pos > 0) {
  82                         m_pos --;
  83                 }
  84                 return *this;
  85         }
  86         const vector_iterator operator--(int) {
  87                 vector_iterator ret(*this);
  88                 --*this;
  89                 return ret;
  90         }
  91         vector_iterator& operator+=(difference_type n) {
  92                 if( n < 0 )
  93                         return (*this -= -n);
  94                 if( n > 0 )
  95                         m_pos = (m_pos + n < m_max ? m_pos + n : m_max);
  96                 return *this;
  97         }
  98         vector_iterator& operator-=(difference_type n) {
  99                 if( n < 0 )
 100                         return (*this += -n);
 101                 if( n > 0 )
 102                         m_pos = (m_pos >= n ? m_pos - n : 0);
 103                 return *this;
 104         }
 105         const difference_type operator-(const vector_iterator& it2) const {
 106                 //_libcxx_assert(m_array == it2.m_array);
 107                 return m_pos - it2.m_pos;
 108         }
 109         bool operator<(const vector_iterator& o) const { return m_pos < o.m_pos; }
 110         bool operator>(const vector_iterator& o) const { return m_pos > o.m_pos; }
 111         bool operator<=(const vector_iterator& o) const { return m_pos <= o.m_pos; }
 112         bool operator>=(const vector_iterator& o) const { return m_pos >= o.m_pos; }
 113 };
 114 #define vector_iterator_tpl class VectorType, class T
 115 #define vector_iterator vector_iterator<VectorType, T>
 116 template <vector_iterator_tpl>
 117 const vector_iterator operator+(const vector_iterator& it, typename VectorType::difference_type n) {
 118         return vector_iterator(it) += n;
 119 }
 120 template <vector_iterator_tpl>
 121 const vector_iterator operator+(typename VectorType::difference_type n, const vector_iterator& it) {
 122         return vector_iterator(it) += n;
 123 }
 124 template <vector_iterator_tpl>
 125 const vector_iterator operator-(const vector_iterator& it, typename VectorType::difference_type n) {
 126         return vector_iterator(it) -= n;
 127 }
 128 #undef vector_iterator_tpl
 129 #undef vector_iterator
 130
 131 }
 132
 133 template <class T, class Alloc = allocator<T> >
 134 class vector
 135 {
 136 public:
 137         typedef T       value_type;
 138         typedef Alloc   allocator_type;
 139         typedef typename allocator_type::reference      reference;
 140         typedef typename allocator_type::const_reference        const_reference;
 141         typedef typename allocator_type::pointer        pointer;
 142         typedef typename allocator_type::const_pointer  const_pointer;
 143         typedef int     difference_type;
 144         typedef size_t  size_type;
 145         typedef ::std::_bits::vector_iterator<vector,T> iterator;
 146         typedef ::std::_bits::vector_iterator<vector,const T>   const_iterator;
 147
 148 private:
 149         allocator_type  m_alloc;
 150         size_type       m_size;
 151         size_type       m_capacity;
 152         value_type*     m_data;
 153
 154 public:
 155         vector(const allocator_type& alloc = allocator_type()):
 156                 m_alloc(alloc),
 157                 m_size(0),
 158                 m_capacity(0),
 159                 m_data(0)
 160         {
 161         }
 162         vector(size_type n, const value_type& val = value_type(), const allocator_type& alloc = allocator_type()):
 163                 vector(alloc)
 164         {
 165                 resize(n, val);
 166         }
 167         template <class InputIterator>
 168         vector(InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type()):
 169                 vector(alloc)
 170         {
 171                 insert(begin(), first, last);
 172         }
 173         vector(const vector& x):
 174                 vector(x.m_alloc)
 175         {
 176                 *this = x;
 177         }
 178         #if _CXX11_AVAIL
 179         vector(vector&& x):
 180                 m_alloc(x.m_alloc),
 181                 m_size(x.m_size),
 182                 m_capacity(x.m_capacity),
 183                 m_data(x.m_data)
 184         {
 185                 x.m_data = nullptr;
 186                 x.m_capacity = 0;
 187                 x.m_size = 0;
 188         }
 189         #endif
 190         vector& operator=(const vector& x)
 191         {
 192                 clear();
 193                 m_alloc.deallocate(m_data, m_capacity);
 194                 m_capacity = 0;
 195
 196                 reserve(x.size());
 197                 for( size_type i = 0; i < x.size(); i ++ )
 198                         push_back( x[i] );
 199
 200                 return *this;
 201         }
 202
 203         ~vector()
 204         {
 205                 clear();
 206                 m_alloc.deallocate(m_data, m_capacity);
 207                 m_capacity = 0;
 208         }
 209
 210         // Iterators
 211         iterator       begin()       { return iterator_to(0); }
 212         const_iterator begin() const { return iterator_to(0); }
 213         iterator       end()       { return iterator_to(m_size); }
 214         const_iterator end() const { return iterator_to(m_size); }
 215
 216         // Capacity
 217         size_type size() const {
 218                 return m_size;
 219         }
 220         size_type max_size() const {
 221                 return -1 / sizeof(value_type);
 222         }
 223         void resize(size_type new_cap, value_type val = value_type()) {
 224                 reserve(new_cap);
 225                 if( new_cap > m_size )
 226                 {
 227                         for( size_type i = m_size; i < new_cap; i ++ ) {
 228                                 m_alloc.construct( &m_data[i], val );
 229                         }
 230                 }
 231                 else
 232                 {
 233                         for( size_type i = new_cap; i < m_size; i ++ )
 234                                 m_alloc.destroy( &m_data[i] );
 235                 }
 236                 m_size = new_cap;
 237         }
 238         size_type capacity() const {
 239                 return m_capacity;
 240         }
 241         bool empty() const {
 242                 return m_size == 0;
 243         }
 244         void reserve(size_type n) {
 245                 if( n > max_size() )
 246                         throw ::std::length_error("::std::vector::reserve");
 247                 if( n > m_capacity )
 248                 {
 249                         size_type size = (n + 0x1F) & ~0x1F;
 250                         auto new_area = m_alloc.allocate(size);
 251                         for( size_type i = 0; i < m_size; i ++ )
 252                                 new_area[i] = m_data[i];
 253                         m_alloc.deallocate(m_data, m_capacity);
 254                         m_data = new_area;
 255                         m_capacity = size;
 256                         //::_SysDebug("::std::vector::resize - m_capacity=%i for n=%i", m_capacity, n);
 257                 }
 258         }
 259         void shrink_to_fit() {
 260         }
 261
 262         // Element access
 263         reference operator[] (size_type n) {
 264                 return m_data[n];
 265         }
 266         const_reference operator[] (size_type n) const {
 267                 return m_data[n];
 268         }
 269         reference at(size_type n) {
 270                 if(n > size())
 271                         _throw_out_of_range("::std::vector - at");
 272                 return m_data[n];
 273         }
 274         const_reference at(size_type n) const {
 275                 if(n > size())
 276                         _throw_out_of_range("::std::vector - at");
 277                 return m_data[n];
 278         }
 279         reference front() {
 280                 return m_data[0];
 281         }
 282         const_reference front() const {
 283                 return m_data[0];
 284         }
 285         reference back() {
 286                 return m_data[size()-1];
 287         }
 288         const_reference back() const {
 289                 return m_data[size()-1];
 290         }
 291         pointer data() noexcept {
 292                 return m_data;
 293         }
 294         const_pointer data() const noexcept {
 295                 return m_data;
 296         }
 297
 298         // Modifiers
 299         void assign(size_type n, const value_type& val) {
 300                 clear();
 301                 resize(n, val);
 302         }
 303         void push_back(const value_type& val) {
 304                 resize(size()+1, val);
 305         }
 306         void pop_back() {
 307                 if( !empty() ) {
 308                         resize(size()-1);
 309                 }
 310         }
 311         iterator insert(iterator position, const value_type& val) {
 312                 insert(position, 1, val);
 313                 return iterator_to(position.m_pos);
 314         }
 315         void insert(iterator position, size_type n, const value_type& val) {
 316                 reserve(m_size + n);
 317                 if( position != end() ) {
 318                         ::_sys::debug("TODO: vector::insert within vector (%i!=%i)",
 319                                 position-begin(), end()-begin());
 320                         ::_sys::abort();
 321                 }
 322                 size_type       pos = m_size;
 323                 while( n -- )
 324                 {
 325                         //::_sys::debug("vector::insert - %x at %i", val, pos);
 326                         m_alloc.construct( &m_data[pos], val );
 327                         pos ++;
 328                         m_size ++;
 329                 }
 330         }
 331         template <class InputIterator>
 332         void insert(iterator position, InputIterator first, InputIterator last) {
 333                 InputIterator   it = first;
 334                 size_type       len = 0;
 335                 while(it != last) {
 336                         ++ it;
 337                         len ++;
 338                 }
 339                 reserve(m_size + len);
 340
 341                 it = first;
 342                 while(it != last)
 343                 {
 344                         //::_sys::debug("vector::insert - to %i, from %p:%i",
 345                         //      position.m_pos, it.m_array, it.m_pos);
 346                         position = insert(position, *it) + 1;
 347                         ++it;
 348                 }
 349         }
 350         iterator erase(iterator position);
 351         iterator erase(iterator first, iterator last);
 352         //void swap(vector& x) {
 353         //      ::std::swap(m_size, x.m_size);
 354         //      ::std::swap(m_capacity, x.m_capacity);
 355         //      ::std::swap(m_data, x.m_data);
 356         //}
 357         void clear() {
 358                 for( size_type i = 0; i < m_size; i ++ ) {
 359                         m_alloc.destroy( &m_data[i] );
 360                 }
 361                 m_size = 0;
 362         }
 363 private:
 364         iterator iterator_to(size_type index) {
 365                 _libcxx_assert(index <= m_size);
 366                 return iterator(m_data, index, m_size);
 367         }
 368         const_iterator iterator_to(size_type index) const {
 369                 _libcxx_assert(index <= m_size);
 370                 return const_iterator(m_data, index, m_size);
 371         }
 372 };
 373
 374 };      // namespace std
 375
 376 #endif
 377 // vim: ft=cpp
 378