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 private:
 177         iterator insert_item(iterator position, item_type *newi) {
 178                 m_item_count ++;
 179                 if( m_start == 0 ) {
 180                         newi->next = 0;
 181                         newi->prev = m_end;
 182                         m_start = newi;
 183                         m_end = newi;
 184                         return end();
 185                 }
 186                 if( position == end() ) {
 187                         newi->next = 0;
 188                         newi->prev = m_end;
 189                         //assert(m_end);
 190                         m_end->next = newi;
 191                         m_end = newi;
 192                 }
 193                 else if( position == begin() ) {
 194                         newi->next = m_start;
 195                         newi->prev = 0;
 196                         //assert(m_start);
 197                         m_start->prev = newi;
 198                         m_start = newi;
 199                 }
 200                 else {
 201                         newi->prev = position.m_cur->prev;
 202                         newi->next = position.m_cur;
 203                         position.m_cur->prev->next = newi;
 204                         position.m_cur->prev = newi;
 205                 }
 206                 return ++position;
 207         }
 208 };
 209
 210
 211 namespace _bits {
 212
 213 template <class T>
 214 struct list_item
 215 {
 216         typedef T       value_type;
 217         list_item<T>    *next;
 218         list_item<T>    *prev;
 219         value_type      value;
 220 };
 221
 222 template <class ListType, class T>
 223 class list_iterator//:
 224         //public bidirectional_iterator_tag;
 225 {
 226         const ListType* m_list;
 227         list_item<T>    *m_cur;
 228         friend ListType;
 229 public:
 230         list_iterator(const list_iterator& x):
 231                 m_list(x.m_list),
 232                 m_cur (x.m_cur)
 233         {
 234         }
 235         list_iterator& operator=(const list_iterator& x) {
 236                 m_list = x.m_list;
 237                 m_cur  = x.m_cur;
 238         }
 239
 240         bool operator == (const list_iterator& other) const {
 241                 return m_cur == other.m_cur;
 242         }
 243         bool operator != (const list_iterator& other) const {
 244                 return !(*this == other);
 245         }
 246
 247         T& operator * () {
 248                 return m_cur->value;
 249         }
 250         T& operator -> () {
 251                 return m_cur->value;
 252         }
 253         list_iterator& operator ++ () {
 254                 if(!m_cur)
 255                         throw ::std::logic_error("list iterator ++ on end");
 256                 m_cur = m_cur->next;
 257                 return *this;
 258         }
 259         list_iterator& operator -- () {
 260                 if( m_cur == m_list->m_start )
 261                         throw ::std::logic_error("list iterator -- on start");
 262                 if(!m_cur)
 263                         m_cur = m_list->m_end;
 264                 else
 265                         m_cur = m_cur->prev;
 266                 return *this;
 267         }
 268
 269 private:
 270         list_iterator(const ListType& list, list_item<T> *item):
 271                 m_list(&list),
 272                 m_cur(item)
 273         {
 274         }
 275 };
 276
 277 };      // namespace _bits
 278
 279 };      // namespace std
 280
 281 #endif
 282
 283 // vim: ft=cpp
 284