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

   1 /*
   2  * Acess2 C++ Library
   3  * - By John Hodge (thePowersGang)
   4  *
   5  * list (header)
   6  * - List container
   7  */
   8 #ifndef _LIBCXX_LIST_
   9 #define _LIBCXX_LIST_
  10
  11 #include <cstddef>
  12 #include "allocator"
  13 #include "stdexcept"
  14 #include "utility"
  15
  16 namespace std {
  17
  18 namespace _bits {
  19 template <class ListType, class T> class list_iterator;
  20 template <class T> class list_item;
  21 }
  22
  23 template <class T, class Alloc = allocator<T> >
  24 class list
  25 {
  26         typedef ::std::_bits::list_item<T>      item_type;
  27         typedef ::std::_bits::list_item<const T>        const_item_type;
  28         friend class ::std::_bits::list_iterator<list, T>;
  29
  30         typedef typename Alloc::template rebind<item_type>::other       item_allocator;
  31 public:
  32         typedef T value_type;
  33         typedef Alloc   allocator_type;
  34         typedef typename allocator_type::reference      reference;
  35         typedef typename allocator_type::const_reference        const_reference;
  36         typedef typename allocator_type::pointer        pointer;
  37         typedef typename allocator_type::const_pointer  const_pointer;
  38         typedef _bits::list_iterator<list,T>    iterator;
  39         typedef _bits::list_iterator<list,const T>      const_iterator;
  40         typedef int     difference_type;
  41         typedef size_t  size_type;
  42
  43 private:
  44         item_allocator  m_item_allocator;
  45         allocator_type  m_allocator;
  46         item_type       *m_start;
  47         item_type       *m_end;
  48         size_type       m_item_count;
  49
  50 public:
  51         list(const allocator_type& alloc = allocator_type()):
  52                 m_item_allocator(),
  53                 m_allocator(alloc),
  54                 m_start(0), m_end(0)
  55         {
  56         }
  57         list(size_t n, const value_type& val = value_type(), const allocator_type& alloc = allocator_type()):
  58                 list()
  59         {
  60                 assign(n, val);
  61         }
  62         list(const list& x);
  63         ~list() {
  64                 clear();
  65         }
  66
  67         list& operator =(const list& x);
  68
  69         iterator begin() {
  70                 return iterator(*this, m_start);
  71         }
  72         const_iterator begin() const {
  73                 return const_iterator(*this, m_start);
  74         }
  75
  76         iterator end() {
  77                 return iterator(*this, 0);
  78         }
  79         const_iterator end() const {
  80                 return const_iterator(*this, 0);
  81         }
  82
  83         bool empty() const {
  84                 return !m_start;
  85         }
  86         size_t size() const {
  87                 return m_item_count;
  88         }
  89         size_t max_size() const {
  90                 return (size_type)-1 / sizeof(item_type);
  91         }
  92
  93         T& front() {
  94                 return m_start->value;
  95         }
  96         const T& front() const {
  97                 return m_start->value;
  98         }
  99         T& back() {
 100                 return m_end->value;
 101         }
 102         const T& back() const {
 103                 return m_end->value;
 104         }
 105
 106         void assign(size_type n, const value_type& val) {
 107                 clear();
 108                 for( size_t i = 0; i < n; i ++ )
 109                 {
 110                         push_back(val);
 111                 }
 112         }
 113
 114         void push_front(const value_type& val) {
 115                 insert(front(), val);
 116         }
 117         void pop_front() {
 118                 erase(front());
 119         }
 120         void push_back(const value_type& val) {
 121                 insert(end(), val);
 122         }
 123         void pop_back() {
 124                 erase(end());
 125         }
 126
 127         template <class... Args>
 128         iterator emplace(iterator position, Args&&... args) {
 129                 item_type *newi = m_item_allocator.allocate(1);
 130                 m_allocator.construct(&newi->value, ::std::forward<Args>(args)...);
 131                 return insert_item(position, newi);
 132         }
 133
 134         iterator insert(iterator position, const value_type& val) {
 135                 item_type *newi = m_item_allocator.allocate(1);
 136                 m_allocator.construct(&newi->value, val);
 137                 return insert_item(position, newi);
 138         }
 139         void insert(iterator position, size_type n, const value_type& val) {
 140                 for( size_type i = 0; i < n; i ++ )
 141                 {
 142                         position = insert(position, val);
 143                 }
 144         }
 145         iterator erase(iterator position) {
 146                 if( position == end() ) {
 147                 }
 148                 else {
 149                         item_type *oldi = position.m_cur;
 150                         ++ position;
 151
 152                         if(oldi->prev)
 153                                 oldi->prev->next = oldi->next;
 154                         else
 155                                 m_start = oldi->next;
 156                         if(oldi->next)
 157                                 oldi->next->prev = oldi->prev;
 158                         else
 159                                 m_end = oldi->prev;
 160
 161                         m_item_count --;
 162                         m_allocator.destroy(&oldi->value);
 163                         m_item_allocator.deallocate(oldi, 1);
 164                 }
 165                 return position;
 166         }
 167
 168         void clear() {
 169                 while( m_start ) {
 170                         item_type* item = m_start;
 171                         m_start = m_start->next;
 172                         delete item;
 173                 }
 174                 m_item_count = 0;
 175         }
 176
 177         void splice(iterator position, list& x) {
 178                 splice(position, x, x.begin(), x.end());
 179         }
 180         void splice(iterator position, list& x, iterator i) {
 181                 splice(position, x, i, x.end());
 182         }
 183         void splice(iterator position, list& x, iterator first, iterator last);
 184
 185 private:
 186         class _equal
 187         {
 188                 const value_type&       m_val;
 189         public:
 190                 _equal(const value_type& val):
 191                         m_val(val)
 192                 {
 193                 };
 194                 bool operator() (const value_type& v1)
 195                 {
 196                         return m_val == v1;
 197                 }
 198         };
 199 public:
 200         void remove(const value_type& val) {
 201                 remove_if(_equal(val));
 202         }
 203         template <class Predicate> void remove_if(Predicate pred) {
 204                 for( iterator it = begin(); it != end(); )
 205                 {
 206                         if( pred(*it) )
 207                                 it = erase(it);
 208                         else
 209                                 ++ it;
 210                 }
 211         }
 212
 213         void unique();
 214         template <class BinaryPredicate> void unique(BinaryPredicate binary_pred);
 215
 216         void merge(list& x);
 217         template <class Compare> void merge(list& x, Compare comp);
 218
 219         void sort();
 220         template <class Compare> void sort(Compare comp);
 221
 222         void reverse() throw();
 223 private:
 224         iterator insert_item(iterator position, item_type *newi) {
 225                 m_item_count ++;
 226                 if( m_start == 0 ) {
 227                         newi->next = 0;
 228                         newi->prev = m_end;
 229                         m_start = newi;
 230                         m_end = newi;
 231                         return end();
 232                 }
 233                 if( position == end() ) {
 234                         newi->next = 0;
 235                         newi->prev = m_end;
 236                         //assert(m_end);
 237                         m_end->next = newi;
 238                         m_end = newi;
 239                 }
 240                 else if( position == begin() ) {
 241                         newi->next = m_start;
 242                         newi->prev = 0;
 243                         //assert(m_start);
 244                         m_start->prev = newi;
 245                         m_start = newi;
 246                 }
 247                 else {
 248                         newi->prev = position.m_cur->prev;
 249                         newi->next = position.m_cur;
 250                         position.m_cur->prev->next = newi;
 251                         position.m_cur->prev = newi;
 252                 }
 253                 return ++iterator(*this, newi);
 254         }
 255 };
 256
 257
 258 namespace _bits {
 259
 260 template <class T>
 261 struct list_item
 262 {
 263         typedef T       value_type;
 264         list_item<T>    *next;
 265         list_item<T>    *prev;
 266         value_type      value;
 267 };
 268
 269 template <class ListType, class T>
 270 class list_iterator//:
 271         //public bidirectional_iterator_tag;
 272 {
 273         const ListType* m_list;
 274         list_item<T>    *m_cur;
 275         friend ListType;
 276 public:
 277         list_iterator(const list_iterator& x):
 278                 m_list(x.m_list),
 279                 m_cur (x.m_cur)
 280         {
 281         }
 282         list_iterator& operator=(const list_iterator& x) {
 283                 m_list = x.m_list;
 284                 m_cur  = x.m_cur;
 285         }
 286
 287         bool operator == (const list_iterator& other) const {
 288                 return m_cur == other.m_cur;
 289         }
 290         bool operator != (const list_iterator& other) const {
 291                 return !(*this == other);
 292         }
 293
 294         T& operator * () {
 295                 return m_cur->value;
 296         }
 297         T& operator -> () {
 298                 return m_cur->value;
 299         }
 300         list_iterator& operator ++ () {
 301                 if(!m_cur)
 302                         throw ::std::logic_error("list iterator ++ on end");
 303                 m_cur = m_cur->next;
 304                 return *this;
 305         }
 306         list_iterator& operator -- () {
 307                 if( m_cur == m_list->m_start )
 308                         throw ::std::logic_error("list iterator -- on start");
 309                 if(!m_cur)
 310                         m_cur = m_list->m_end;
 311                 else
 312                         m_cur = m_cur->prev;
 313                 return *this;
 314         }
 315
 316 private:
 317         list_iterator(const ListType& list, list_item<T> *item):
 318                 m_list(&list),
 319                 m_cur(item)
 320         {
 321         }
 322 };
 323
 324 };      // namespace _bits
 325
 326 };      // namespace std
 327
 328 #endif
 329
 330 // vim: ft=cpp
 331