ceph/src/boost/libs/unordered/test/helpers/list.hpp

   1
   2 // Copyright 2008-2009 Daniel James.
   3 // Distributed under the Boost Software License, Version 1.0. (See accompanying
   4 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   5
   6 // Gratuitous single linked list.
   7 //
   8 // Sadly some STL implementations aren't up to scratch and I need a simple
   9 // cross-platform container. So here it is.
  10
  11 #if !defined(UNORDERED_TEST_LIST_HEADER)
  12 #define UNORDERED_TEST_LIST_HEADER
  13
  14 #include <boost/limits.hpp>
  15 #include <functional>
  16 #include <iterator>
  17
  18 namespace test {
  19   template <typename It1, typename It2>
  20   bool equal(It1 begin, It1 end, It2 compare)
  21   {
  22     for (; begin != end; ++begin, ++compare)
  23       if (*begin != *compare)
  24         return false;
  25     return true;
  26   }
  27
  28   template <typename It1, typename It2, typename Pred>
  29   bool equal(It1 begin, It1 end, It2 compare, Pred predicate)
  30   {
  31     for (; begin != end; ++begin, ++compare)
  32       if (!predicate(*begin, *compare))
  33         return false;
  34     return true;
  35   }
  36
  37   template <typename T> class list;
  38
  39   namespace test_detail {
  40     template <typename T> class list_node;
  41     template <typename T> class list_data;
  42     template <typename T> class list_iterator;
  43     template <typename T> class list_const_iterator;
  44
  45     template <typename T> class list_node
  46     {
  47       list_node(list_node const&);
  48       list_node& operator=(list_node const&);
  49
  50     public:
  51       T value_;
  52       list_node* next_;
  53
  54       list_node(T const& v) : value_(v), next_(0) {}
  55       list_node(T const& v, list_node* n) : value_(v), next_(n) {}
  56     };
  57
  58     template <typename T> class list_data
  59     {
  60     public:
  61       typedef list_node<T> node;
  62       typedef unsigned int size_type;
  63
  64       node* first_;
  65       node** last_ptr_;
  66       size_type size_;
  67
  68       list_data() : first_(0), last_ptr_(&first_), size_(0) {}
  69
  70       ~list_data()
  71       {
  72         while (first_) {
  73           node* tmp = first_;
  74           first_ = first_->next_;
  75           delete tmp;
  76         }
  77       }
  78
  79     private:
  80       list_data(list_data const&);
  81       list_data& operator=(list_data const&);
  82     };
  83
  84     template <typename T>
  85     class list_iterator
  86       : public std::iterator<std::forward_iterator_tag, T, int, T*, T&>
  87     {
  88       friend class list_const_iterator<T>;
  89       friend class test::list<T>;
  90       typedef list_node<T> node;
  91       typedef list_const_iterator<T> const_iterator;
  92
  93       node* ptr_;
  94
  95     public:
  96       list_iterator() : ptr_(0) {}
  97       explicit list_iterator(node* x) : ptr_(x) {}
  98
  99       T& operator*() const { return ptr_->value_; }
 100       T* operator->() const { return &ptr_->value_; }
 101       list_iterator& operator++()
 102       {
 103         ptr_ = ptr_->next_;
 104         return *this;
 105       }
 106       list_iterator operator++(int)
 107       {
 108         list_iterator tmp = *this;
 109         ptr_ = ptr_->next_;
 110         return tmp;
 111       }
 112       bool operator==(const_iterator y) const { return ptr_ == y.ptr_; }
 113       bool operator!=(const_iterator y) const { return ptr_ != y.ptr_; }
 114     };
 115
 116     template <typename T>
 117     class list_const_iterator : public std::iterator<std::forward_iterator_tag,
 118                                   T, int, T const*, T const&>
 119     {
 120       friend class list_iterator<T>;
 121       friend class test::list<T>;
 122       typedef list_node<T> node;
 123       typedef list_iterator<T> iterator;
 124       typedef list_const_iterator<T> const_iterator;
 125
 126       node* ptr_;
 127
 128     public:
 129       list_const_iterator() : ptr_(0) {}
 130       list_const_iterator(list_iterator<T> const& x) : ptr_(x.ptr_) {}
 131
 132       T const& operator*() const { return ptr_->value_; }
 133       T const* operator->() const { return &ptr_->value_; }
 134
 135       list_const_iterator& operator++()
 136       {
 137         ptr_ = ptr_->next_;
 138         return *this;
 139       }
 140
 141       list_const_iterator operator++(int)
 142       {
 143         list_const_iterator tmp = *this;
 144         ptr_ = ptr_->next_;
 145         return tmp;
 146       }
 147
 148       bool operator==(const_iterator y) const { return ptr_ == y.ptr_; }
 149
 150       bool operator!=(const_iterator y) const { return ptr_ != y.ptr_; }
 151     };
 152   }
 153
 154   template <typename T> class list
 155   {
 156     typedef test::test_detail::list_data<T> data;
 157     typedef test::test_detail::list_node<T> node;
 158     data data_;
 159
 160   public:
 161     typedef T value_type;
 162     typedef value_type& reference;
 163     typedef value_type const& const_reference;
 164     typedef unsigned int size_type;
 165
 166     typedef test::test_detail::list_iterator<T> iterator;
 167     typedef test::test_detail::list_const_iterator<T> const_iterator;
 168
 169     list() : data_() {}
 170
 171     list(list const& other) : data_() { insert(other.begin(), other.end()); }
 172
 173     template <class InputIterator>
 174     list(InputIterator i, InputIterator j) : data_()
 175     {
 176       insert(i, j);
 177     }
 178
 179     list& operator=(list const& other)
 180     {
 181       clear();
 182       insert(other.begin(), other.end());
 183       return *this;
 184     }
 185
 186     iterator begin() { return iterator(data_.first_); }
 187     iterator end() { return iterator(); }
 188     const_iterator begin() const { return iterator(data_.first_); }
 189     const_iterator end() const { return iterator(); }
 190     const_iterator cbegin() const { return iterator(data_.first_); }
 191     const_iterator cend() const { return iterator(); }
 192
 193     template <class InputIterator> void insert(InputIterator i, InputIterator j)
 194     {
 195       for (; i != j; ++i)
 196         push_back(*i);
 197     }
 198
 199     void push_front(value_type const& v)
 200     {
 201       data_.first_ = new node(v, data_.first_);
 202       if (!data_.size_)
 203         data_.last_ptr_ = &(*data_.last_ptr_)->next_;
 204       ++data_.size_;
 205     }
 206
 207     void push_back(value_type const& v)
 208     {
 209       *data_.last_ptr_ = new node(v);
 210       data_.last_ptr_ = &(*data_.last_ptr_)->next_;
 211       ++data_.size_;
 212     }
 213
 214     void clear()
 215     {
 216       while (data_.first_) {
 217         node* tmp = data_.first_;
 218         data_.first_ = data_.first_->next_;
 219         --data_.size_;
 220         delete tmp;
 221       }
 222       data_.last_ptr_ = &data_.first_;
 223     }
 224
 225     void erase(const_iterator i, const_iterator j)
 226     {
 227       node** ptr = &data_.first_;
 228
 229       while (*ptr != i.ptr_) {
 230         ptr = &(*ptr)->next_;
 231       }
 232
 233       while (*ptr != j.ptr_) {
 234         node* to_delete = *ptr;
 235         *ptr = (*ptr)->next_;
 236         --data_.size_;
 237         delete to_delete;
 238       }
 239
 240       if (!*ptr)
 241         data_.last_ptr_ = ptr;
 242     }
 243
 244     bool empty() const { return !data_.size_; }
 245
 246     size_type size() const { return data_.size_; }
 247
 248     void sort() { sort(std::less<T>()); }
 249
 250     template <typename Less> void sort(Less less = Less())
 251     {
 252       if (!empty())
 253         merge_sort(
 254           &data_.first_, (std::numeric_limits<size_type>::max)(), less);
 255     }
 256
 257     bool operator==(list const& y) const
 258     {
 259       return size() == y.size() && test::equal(begin(), end(), y.begin());
 260     }
 261
 262     bool operator!=(list const& y) const { return !(*this == y); }
 263
 264   private:
 265     template <typename Less>
 266     node** merge_sort(node** l, size_type recurse_limit, Less less)
 267     {
 268       node** ptr = &(*l)->next_;
 269       for (size_type count = 0; count < recurse_limit && *ptr; ++count) {
 270         ptr = merge_adjacent_ranges(l, ptr, merge_sort(ptr, count, less), less);
 271       }
 272       return ptr;
 273     }
 274
 275     template <typename Less>
 276     node** merge_adjacent_ranges(
 277       node** first, node** second, node** third, Less less)
 278     {
 279       for (;;) {
 280         for (;;) {
 281           if (first == second)
 282             return third;
 283           if (less((*second)->value_, (*first)->value_))
 284             break;
 285           first = &(*first)->next_;
 286         }
 287
 288         swap_adjacent_ranges(first, second, third);
 289         first = &(*first)->next_;
 290
 291         // Since the two ranges we just swapped, the order is now:
 292         // first...third...second
 293
 294         for (;;) {
 295           if (first == third)
 296             return second;
 297           if (!less((*first)->value_, (*third)->value_))
 298             break;
 299           first = &(*first)->next_;
 300         }
 301
 302         swap_adjacent_ranges(first, third, second);
 303         first = &(*first)->next_;
 304       }
 305     }
 306
 307     void swap_adjacent_ranges(node** first, node** second, node** third)
 308     {
 309       node* tmp = *first;
 310       *first = *second;
 311       *second = *third;
 312       *third = tmp;
 313       if (!*second)
 314         data_.last_ptr_ = second;
 315     }
 316   };
 317 }
 318
 319 #endif