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

   1 /*
   2  * Acess2 C++ Library
   3  * - By John Hodge (thePowersGang)
   4  *
   5  * map (header)
   6  * - C++'s map type
   7  */
   8 #ifndef _LIBCXX_MAP_
   9 #define _LIBCXX_MAP_
  10
  11 #include "_libcxx_helpers.h"
  12 #include <allocator>
  13 #include <stdexcept>
  14 #include <iterator>
  15 #include <utility>
  16 #include <functional>   // less
  17
  18 namespace std {
  19
  20 namespace _bits {
  21
  22 template <class Val, class Map>
  23 class map_iterator:
  24         public ::std::iterator< ::std::bidirectional_iterator_tag, Val >
  25 {
  26         friend Map;
  27         typedef Val     value_type;
  28         Map     *m_map;
  29         size_t  m_index;
  30 public:
  31         map_iterator():
  32                 m_map(0), m_index(0)
  33         {
  34         }
  35         map_iterator(Map *map, typename Map::size_type ofs):
  36                 m_map(map), m_index(ofs)
  37         {
  38         }
  39         map_iterator(const map_iterator& x) {
  40                 *this = x;
  41         }
  42         map_iterator& operator=(const map_iterator& x) {
  43                 m_map = x.m_map;
  44                 m_index = x.m_index;
  45                 return *this;
  46         }
  47
  48         map_iterator& operator++() {
  49                 m_index ++;
  50         }
  51         map_iterator& operator--() {
  52                 m_index --;
  53         }
  54
  55         bool operator==(const map_iterator& x) const {
  56                 return m_index == x.m_index;
  57         }
  58         bool operator!=(const map_iterator& x) const {
  59                 return !(*this == x);
  60         }
  61         value_type& operator*() {
  62                 _libcxx_assert(m_index < m_map->m_size);
  63                 return m_map->m_items[m_index];
  64         }
  65         value_type* operator->() {
  66                 _libcxx_assert(m_index < m_map->m_size);
  67                 return &m_map->m_items[m_index];
  68         }
  69 };
  70
  71 }       // namespace _bits
  72
  73 template <class Key, class T, class Compare=less<Key>, class Alloc=allocator<pair<const Key,T> > >
  74 class map
  75 {
  76         typedef map     this_type;
  77 public:
  78         typedef Key     key_type;
  79         typedef T       mapped_type;
  80         typedef pair<const Key, T>      value_type;
  81         typedef Compare key_compare;
  82         typedef Alloc   allocator_type;
  83         typedef typename allocator_type::reference      reference;
  84         typedef typename allocator_type::const_reference        const_reference;
  85         typedef typename allocator_type::pointer        pointer;
  86         typedef typename allocator_type::const_pointer  const_pointer;
  87         typedef _bits::map_iterator<value_type,this_type>       iterator;
  88         typedef _bits::map_iterator<const value_type,this_type> const_iterator;
  89         typedef size_t  size_type;
  90
  91 private:
  92         friend class ::std::_bits::map_iterator<value_type, this_type>;
  93         friend class ::std::_bits::map_iterator<const value_type, this_type>;
  94
  95         key_compare     m_comp;
  96         allocator_type  m_alloc;
  97         value_type*     m_items;        // sorted array
  98         size_type       m_size;
  99         size_type       m_capacity;
 100
 101 public:
 102         map(const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type()):
 103                 m_comp(comp),
 104                 m_alloc(alloc),
 105                 m_items(0), m_size(0), m_capacity(0)
 106         {
 107         }
 108         template <class InputInterator>
 109         map(InputInterator first, InputInterator last):
 110                 map()
 111         {
 112                 insert(first, last);
 113         }
 114         map(const map& x):
 115                 map(x.m_comp, x.m_alloc)
 116         {
 117                 *this = x;
 118         }
 119         ~map() {
 120                 clear();
 121                 reserve(0);
 122         }
 123         map& operator=(const map& x) {
 124                 clear();
 125                 reserve(x.m_size);
 126                 for( size_type i = 0; i < x.m_size; i ++ ) {
 127                         emplace_hint( end(), x.m_items[i] );
 128                 }
 129                 return *this;
 130         }
 131
 132         // Iterators
 133         iterator begin() {
 134                 return iterator(this, 0);
 135         }
 136         const_iterator begin() const {
 137                 return const_iterator(this, 0);
 138         }
 139         iterator end() {
 140                 return iterator(this, m_size);
 141         }
 142         const_iterator end() const {
 143                 return const_iterator(this, m_size);
 144         }
 145         #if _CXX11_AVAIL
 146         const_iterator cbegin() const {
 147                 return const_iterator(this, 0);
 148         }
 149         const_iterator cend() const {
 150                 return const_iterator(this, m_size);
 151         }
 152         #endif
 153         //reverse_iterator rbegin();
 154         //const_reverse_iterator rbegin() const;
 155         //const_reverse_iterator crbegin() const;
 156         //reverse_iterator rend();
 157         //const reverse_iterator rend() const;
 158         //const reverse_iterator crend() const;
 159
 160         // Capacity
 161         bool empty() const {
 162                 return m_size == 0;
 163         }
 164         size_type size() const {
 165                 return m_size;
 166         }
 167         size_type max_size() const {
 168                 return (size_type)-1 / sizeof(value_type);
 169         }
 170
 171         // Element access
 172         mapped_type& operator[](const key_type& k) {
 173                 iterator it = upper_bound(k);
 174                 if( it == end() || m_comp(k, it->first) ) {     // if k < it->first, no match
 175                         insert_at(it.m_index, value_type(k,mapped_type()) );
 176                 }
 177                 return it->second;
 178         }
 179         #if _CXX11_AVAIL
 180         mapped_type& at(const key_type& k) {
 181                 iterator it = lower_bound(k);
 182                 if( it == end() || m_comp(it->first, k) )
 183                         throw ::std::out_of_range("::std:map::at");
 184                 return it->second;
 185         }
 186         const mapped_type& at(const key_type& k) const {
 187                 iterator it = lower_bound(k);
 188                 if( it == end() || m_comp(it->first, k) )
 189                         throw ::std::out_of_range("::std:map::at");
 190                 return it->second;
 191         }
 192         #endif
 193
 194         // Modifiers
 195         // - insert
 196         pair<iterator,bool> insert(const value_type& val)
 197         {
 198                 const key_type& k = val.first;
 199                 iterator it = upper_bound(k);
 200                 if( it == end() || m_comp(k, it->first) ) {     // if k < it->first, no match
 201                         insert_at(it.m_index, value_type(k,mapped_type()) );
 202                         return pair<iterator,bool>(it, true);
 203                 }
 204                 else {
 205                         return pair<iterator,bool>(it, false);
 206                 }
 207         }
 208         iterator insert(iterator position, const value_type& val);
 209         template <class InputInterator>
 210         void insert(InputInterator first, InputInterator last);
 211         // - erase
 212         void erase(iterator position)
 213         {
 214                 auto pos = position;
 215                 erase(pos, ++position);
 216         }
 217         size_type erase(const key_type& k)
 218         {
 219                 auto it = find(k);
 220                 if( it != end() ) {
 221                         erase(it);
 222                         return 1;
 223                 }
 224                 else {
 225                         return 0;
 226                 }
 227         }
 228         void erase(iterator first, iterator last)
 229         {
 230                 _libcxx_assert(first.m_index <= last.m_index);
 231                 unsigned int ofs = first.m_index;
 232                 unsigned int count = last.m_index - first.m_index;
 233                 for( unsigned int i = 0; i < count; i ++ )
 234                 {
 235                         // Construct new item
 236                         m_alloc.destroy(&m_items[ofs]);
 237                         m_size --;
 238                         // Move following items down
 239                         shift_items(&m_items[ofs+1], &m_items[ofs], m_size-ofs);
 240                 }
 241         }
 242         // - swap
 243         void swap(map& x);
 244         // - clear
 245         void clear() {
 246                 for( size_type i = 0; i < m_size; i ++ ) {
 247                         m_alloc.destroy( &m_items[i] );
 248                 }
 249                 m_size = 0;
 250         }
 251         // - emplace
 252         #if _CXX11_AVAIL
 253         template <class... Args>
 254         pair<iterator,bool> emplace(Args&&... args) {
 255                 return emplace_hint(begin(), args...);
 256         }
 257         template <class... Args>
 258         pair<iterator,bool> emplace_hint(iterator position, Args&&... args);
 259         #endif
 260
 261         // TODO: Observers
 262
 263         // Operators
 264         iterator find(const key_type& k) {
 265                 iterator it = lower_bound(k);
 266                 if( it == end() || m_comp(it->first, k) )       // if it->first < k
 267                         return end();
 268                 return it;
 269         }
 270         const_iterator find(const key_type& k) const {
 271                 const_iterator it = lower_bound(k);
 272                 if( it == end() || m_comp(it->first, k) )       // if it->first < k
 273                         return end();
 274                 return it;
 275         }
 276         size_type count(const key_type& k) {
 277                 if( find(k) == end() )
 278                         return 0;
 279                 return 1;
 280         }
 281         iterator lower_bound(const key_type& k) {
 282                 size_type idx;
 283                 if( _search(k, idx) ) {
 284                         // found, return direct iterator
 285                         return iterator(this, idx);
 286                 }
 287                 else {
 288                         // not found, return iterator to before
 289                         if( idx == 0 )  return begin();
 290                         return iterator(this, idx-1);
 291                 }
 292         }
 293         const_iterator lower_bound(const key_type& k) const {
 294                 size_type idx;
 295                 if( _search(k, idx) ) {
 296                         // found, return direct iterator
 297                         return iterator(this, idx);
 298                 }
 299                 else {
 300                         // not found, return iterator to before
 301                         if( idx == 0 )  return begin();
 302                         return iterator(this, idx-1);
 303                 }
 304         }
 305         iterator upper_bound(const key_type& k) {
 306                 size_type idx;
 307                 _search(k, idx);
 308                 // idx == item or just after it
 309                 return iterator(this, idx);
 310         }
 311         const_iterator upper_bound(const key_type& k) const {
 312                 size_type idx;
 313                 _search(k, idx);
 314                 return const_iterator(this, idx);
 315         }
 316         pair<iterator,iterator> equal_range(const key_type& k);
 317         pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
 318
 319 private:
 320         // Change reservation to fit 'n' items
 321         // - NOTE: Will also resize down
 322         void reserve(size_type n) {
 323                 n = (n + 31) & ~31;
 324                 if( n > max_size() )
 325                         throw ::std::length_error("::std::map::reserve");
 326                 if( n != m_capacity )
 327                 {
 328                         auto new_area = m_alloc.allocate(n);
 329                         for( size_type i = 0; i < m_size && i < n; i ++ )
 330                                 m_alloc.construct(&new_area[i], m_items[i]);
 331                         for( size_type i = n; i < m_size; i ++ )
 332                                 m_alloc.destroy( &m_items[i] );
 333                         m_alloc.deallocate(m_items, m_capacity);
 334                         m_items = new_area;
 335                         m_capacity = n;
 336                         if(m_size > n)
 337                                 m_size = n;
 338                 }
 339         }
 340         // Returns the index above or equal to 'k'
 341         // - TODO: Reimplement as a binary search
 342         bool _search(const key_type& k, size_type &pos_out) const {
 343                 #if 0
 344                 size_type pos = m_size / 2;
 345                 size_type step = m_size / 4;
 346                 while( step > 0 ) {
 347                         const key_type& item_key = m_items[pos].first;
 348                         if( m_comp(item_key, k) )
 349                                 pos += step;
 350                         else if( m_comp(k, item_key) )
 351                                 pos -= step;
 352                         else {
 353                                 pos_out = pos;
 354                                 return true;
 355                         }
 356                         step /= 2;
 357                 }
 358                 pos_out = pos;
 359                 return false;
 360                 #else
 361                 //::_sys::debug("map::_search (m_size=%i)", m_size);
 362                 for( size_type pos = 0; pos < m_size; pos ++ )
 363                 {
 364                         const key_type& item_key = m_items[pos].first;
 365                         if( m_comp(item_key, k) ) {
 366                                 continue;
 367                         }
 368                         else if( m_comp(k, item_key) ) {
 369                                 //::_sys::debug("map::_search - Passed %i", pos);
 370                                 pos_out = pos;
 371                                 return false;
 372                         }
 373                         else {
 374                                 //::_sys::debug("map::_search - Found %i", pos);
 375                                 pos_out = pos;
 376                                 return true;
 377                         }
 378                 }
 379                 //::_sys::debug("map::_search - Off end %i", m_size);
 380                 pos_out = m_size;
 381                 return false;
 382                 #endif
 383         }
 384         void insert_at(size_type ofs, const value_type& val) {
 385                 //_libcxx_assert( ofs == 0 || m_comp(m_items[ofs-1].first, val.first) );
 386                 //_libcxx_assert( ofs == m_size || m_comp(m_items[ofs].first, val.first) );
 387                 // Resize up
 388                 reserve( m_size + 1 );
 389                 // Move following items up
 390                 shift_items(&m_items[ofs], &m_items[ofs+1], m_size-ofs);
 391                 // Construct new item
 392                 m_alloc.construct(&m_items[ofs], val);
 393                 m_size ++;
 394         }
 395         void shift_items(value_type *start, value_type *end, size_type count) {
 396                 if( start < end ) {
 397                         for( size_type i = count; i --; ) {
 398                                 #if _CXX11_AVAIL && 0
 399                                 m_alloc.construct(&end[i], ::std::move(start[i]));
 400                                 #else
 401                                 m_alloc.construct(&end[i], start[i]);
 402                                 m_alloc.destroy(&start[i]);
 403                                 #endif
 404                         }
 405                 }
 406                 else {
 407                         for( size_type i = 0; i < count; i ++ ) {
 408                         }
 409                 }
 410         }
 411 };
 412
 413 }       // namespace std
 414
 415 #endif
 416
 417 // vim: ft=cpp
 418