X-Git-Url: https://git.proxmox.com/?a=blobdiff_plain;f=ceph%2Fsrc%2Fboost%2Flibs%2Funordered%2Ftest%2Fhelpers%2Flist.hpp;h=137cb17cf1d4d203546a9595527c93724a9c80c0;hb=b32b81446b3b05102be0267e79203f59329c1d97;hp=0c92928d42bf33dac8168788b801dfc20b3c4836;hpb=215dd7151453fae88e6f968c975b6ce309d42dcf;p=ceph.git

diff --git a/ceph/src/boost/libs/unordered/test/helpers/list.hpp b/ceph/src/boost/libs/unordered/test/helpers/list.hpp
index 0c92928d4..137cb17cf 100644
--- a/ceph/src/boost/libs/unordered/test/helpers/list.hpp
+++ b/ceph/src/boost/libs/unordered/test/helpers/list.hpp
@@ -12,307 +12,308 @@
 #define UNORDERED_TEST_LIST_HEADER
 
 #include <boost/limits.hpp>
-#include <iterator>
 #include <functional>
+#include <iterator>
+
+namespace test {
+  template <typename It1, typename It2>
+  bool equal(It1 begin, It1 end, It2 compare)
+  {
+    for (; begin != end; ++begin, ++compare)
+      if (*begin != *compare)
+        return false;
+    return true;
+  }
+
+  template <typename It1, typename It2, typename Pred>
+  bool equal(It1 begin, It1 end, It2 compare, Pred predicate)
+  {
+    for (; begin != end; ++begin, ++compare)
+      if (!predicate(*begin, *compare))
+        return false;
+    return true;
+  }
+
+  template <typename T> class list;
+
+  namespace test_detail {
+    template <typename T> class list_node;
+    template <typename T> class list_data;
+    template <typename T> class list_iterator;
+    template <typename T> class list_const_iterator;
+
+    template <typename T> class list_node
+    {
+      list_node(list_node const&);
+      list_node& operator=(list_node const&);
+
+    public:
+      T value_;
+      list_node* next_;
+
+      list_node(T const& v) : value_(v), next_(0) {}
+      list_node(T const& v, list_node* n) : value_(v), next_(n) {}
+    };
+
+    template <typename T> class list_data
+    {
+    public:
+      typedef list_node<T> node;
+      typedef unsigned int size_type;
+
+      node* first_;
+      node** last_ptr_;
+      size_type size_;
+
+      list_data() : first_(0), last_ptr_(&first_), size_(0) {}
+
+      ~list_data()
+      {
+        while (first_) {
+          node* tmp = first_;
+          first_ = first_->next_;
+          delete tmp;
+        }
+      }
+
+    private:
+      list_data(list_data const&);
+      list_data& operator=(list_data const&);
+    };
+
+    template <typename T>
+    class list_iterator
+      : public std::iterator<std::forward_iterator_tag, T, int, T*, T&>
+    {
+      friend class list_const_iterator<T>;
+      friend class test::list<T>;
+      typedef list_node<T> node;
+      typedef list_const_iterator<T> const_iterator;
+
+      node* ptr_;
+
+    public:
+      list_iterator() : ptr_(0) {}
+      explicit list_iterator(node* x) : ptr_(x) {}
+
+      T& operator*() const { return ptr_->value_; }
+      T* operator->() const { return &ptr_->value_; }
+      list_iterator& operator++()
+      {
+        ptr_ = ptr_->next_;
+        return *this;
+      }
+      list_iterator operator++(int)
+      {
+        list_iterator tmp = *this;
+        ptr_ = ptr_->next_;
+        return tmp;
+      }
+      bool operator==(const_iterator y) const { return ptr_ == y.ptr_; }
+      bool operator!=(const_iterator y) const { return ptr_ != y.ptr_; }
+    };
+
+    template <typename T>
+    class list_const_iterator : public std::iterator<std::forward_iterator_tag,
+                                  T, int, T const*, T const&>
+    {
+      friend class list_iterator<T>;
+      friend class test::list<T>;
+      typedef list_node<T> node;
+      typedef list_iterator<T> iterator;
+      typedef list_const_iterator<T> const_iterator;
+
+      node* ptr_;
+
+    public:
+      list_const_iterator() : ptr_(0) {}
+      list_const_iterator(list_iterator<T> const& x) : ptr_(x.ptr_) {}
+
+      T const& operator*() const { return ptr_->value_; }
+      T const* operator->() const { return &ptr_->value_; }
+
+      list_const_iterator& operator++()
+      {
+        ptr_ = ptr_->next_;
+        return *this;
+      }
+
+      list_const_iterator operator++(int)
+      {
+        list_const_iterator tmp = *this;
+        ptr_ = ptr_->next_;
+        return tmp;
+      }
+
+      bool operator==(const_iterator y) const { return ptr_ == y.ptr_; }
+
+      bool operator!=(const_iterator y) const { return ptr_ != y.ptr_; }
+    };
+  }
+
+  template <typename T> class list
+  {
+    typedef test::test_detail::list_data<T> data;
+    typedef test::test_detail::list_node<T> node;
+    data data_;
+
+  public:
+    typedef T value_type;
+    typedef value_type& reference;
+    typedef value_type const& const_reference;
+    typedef unsigned int size_type;
 
-namespace test
-{
-    template <typename It1, typename It2>
-    bool equal(It1 begin, It1 end, It2 compare)
+    typedef test::test_detail::list_iterator<T> iterator;
+    typedef test::test_detail::list_const_iterator<T> const_iterator;
+
+    list() : data_() {}
+
+    list(list const& other) : data_() { insert(other.begin(), other.end()); }
+
+    template <class InputIterator>
+    list(InputIterator i, InputIterator j) : data_()
     {
-        for(;begin != end; ++begin, ++compare)
-            if(*begin != *compare) return false;
-        return true;
+      insert(i, j);
     }
 
-    template <typename It1, typename It2, typename Pred>
-    bool equal(It1 begin, It1 end, It2 compare, Pred predicate)
+    list& operator=(list const& other)
     {
-        for(;begin != end; ++begin, ++compare)
-            if(!predicate(*begin, *compare)) return false;
-        return true;
+      clear();
+      insert(other.begin(), other.end());
+      return *this;
     }
 
+    iterator begin() { return iterator(data_.first_); }
+    iterator end() { return iterator(); }
+    const_iterator begin() const { return iterator(data_.first_); }
+    const_iterator end() const { return iterator(); }
+    const_iterator cbegin() const { return iterator(data_.first_); }
+    const_iterator cend() const { return iterator(); }
 
-    template <typename T> class list;
+    template <class InputIterator> void insert(InputIterator i, InputIterator j)
+    {
+      for (; i != j; ++i)
+        push_back(*i);
+    }
 
-    namespace test_detail
+    void push_front(value_type const& v)
     {
-        template <typename T> class list_node;
-        template <typename T> class list_data;
-        template <typename T> class list_iterator;
-        template <typename T> class list_const_iterator;
-
-        template <typename T>
-        class list_node
-        {
-            list_node(list_node const&);
-            list_node& operator=(list_node const&);
-        public:
-            T value_;
-            list_node* next_;
-                    
-            list_node(T const& v) : value_(v), next_(0) {}
-            list_node(T const& v, list_node* n) : value_(v), next_(n) {}
-        };
-
-        template <typename T>
-        class list_data
-        {
-        public:
-            typedef list_node<T> node;
-            typedef unsigned int size_type;
-
-            node* first_;
-            node** last_ptr_;
-            size_type size_;
-            
-            list_data() : first_(0), last_ptr_(&first_), size_(0) {}
-
-            ~list_data() {
-                while(first_) {
-                    node* tmp = first_;
-                    first_ = first_->next_;
-                    delete tmp;
-                }
-            }
-        private:
-            list_data(list_data const&);
-            list_data& operator=(list_data const&);
-        };
-
-        template <typename T>
-        class list_iterator
-            : public std::iterator<
-                std::forward_iterator_tag, T,
-                  int, T*, T&>
-        {
-            friend class list_const_iterator<T>;
-            friend class test::list<T>;
-            typedef list_node<T> node;
-            typedef list_const_iterator<T> const_iterator;
-
-            node* ptr_;
-        public:
-            list_iterator() : ptr_(0) {}
-            explicit list_iterator(node* x) : ptr_(x) {}
-
-            T& operator*() const { return ptr_->value_; }
-            T* operator->() const { return &ptr_->value_; }
-            list_iterator& operator++() {
-                ptr_ = ptr_->next_; return *this; }
-            list_iterator operator++(int) {
-                list_iterator tmp = *this; ptr_ = ptr_->next_; return tmp; }
-            bool operator==(const_iterator y) const { return ptr_ == y.ptr_; }
-            bool operator!=(const_iterator y) const { return ptr_ != y.ptr_; }
-        };
-
-        template <typename T>
-        class list_const_iterator
-            : public std::iterator<
-                std::forward_iterator_tag, T,
-                  int, T const*, T const&>
-        {
-            friend class list_iterator<T>;
-            friend class test::list<T>;
-            typedef list_node<T> node;
-            typedef list_iterator<T> iterator;
-            typedef list_const_iterator<T> const_iterator;
-
-            node* ptr_;
-        public:
-            list_const_iterator() : ptr_(0) {}
-            list_const_iterator(list_iterator<T> const& x) : ptr_(x.ptr_) {}
-
-            T const& operator*() const { return ptr_->value_; }
-            T const* operator->() const { return &ptr_->value_; }
-
-            list_const_iterator& operator++()
-            {
-                ptr_ = ptr_->next_;
-                return *this;
-            }
-
-            list_const_iterator operator++(int)
-            {
-                list_const_iterator tmp = *this;
-                ptr_ = ptr_->next_;
-                return tmp;
-            }
-
-            bool operator==(const_iterator y) const
-            {
-                return ptr_ == y.ptr_;
-            }
-
-            bool operator!=(const_iterator y) const
-            {
-                return ptr_ != y.ptr_;
-            }
-        };
+      data_.first_ = new node(v, data_.first_);
+      if (!data_.size_)
+        data_.last_ptr_ = &(*data_.last_ptr_)->next_;
+      ++data_.size_;
     }
 
-    template <typename T>
-    class list
+    void push_back(value_type const& v)
     {
-        typedef test::test_detail::list_data<T> data;
-        typedef test::test_detail::list_node<T> node;
-        data data_;
-    public:
-        typedef T value_type;
-        typedef value_type& reference;
-        typedef value_type const& const_reference;
-        typedef unsigned int size_type;
+      *data_.last_ptr_ = new node(v);
+      data_.last_ptr_ = &(*data_.last_ptr_)->next_;
+      ++data_.size_;
+    }
 
-        typedef test::test_detail::list_iterator<T> iterator;
-        typedef test::test_detail::list_const_iterator<T> const_iterator;
+    void clear()
+    {
+      while (data_.first_) {
+        node* tmp = data_.first_;
+        data_.first_ = data_.first_->next_;
+        --data_.size_;
+        delete tmp;
+      }
+      data_.last_ptr_ = &data_.first_;
+    }
 
-        list() : data_() {}
+    void erase(const_iterator i, const_iterator j)
+    {
+      node** ptr = &data_.first_;
 
-        list(list const& other) : data_() {
-            insert(other.begin(), other.end());
-        }
+      while (*ptr != i.ptr_) {
+        ptr = &(*ptr)->next_;
+      }
 
-        template <class InputIterator>
-        list(InputIterator i, InputIterator j) : data_() {
-            insert(i, j);
-        }
+      while (*ptr != j.ptr_) {
+        node* to_delete = *ptr;
+        *ptr = (*ptr)->next_;
+        --data_.size_;
+        delete to_delete;
+      }
 
-        list& operator=(list const& other) {
-            clear();
-            insert(other.begin(), other.end());
-            return *this;
-        }
+      if (!*ptr)
+        data_.last_ptr_ = ptr;
+    }
 
-        iterator begin() { return iterator(data_.first_); }
-        iterator end() { return iterator(); }
-        const_iterator begin() const { return iterator(data_.first_); }
-        const_iterator end() const { return iterator(); }
-        const_iterator cbegin() const { return iterator(data_.first_); }
-        const_iterator cend() const { return iterator(); }
-
-        template <class InputIterator>
-        void insert(InputIterator i, InputIterator j) {
-            for(; i != j; ++i)
-                push_back(*i);
-        }
+    bool empty() const { return !data_.size_; }
 
-        void push_front(value_type const& v) {
-            data_.first_ = new node(v, data_.first_);
-            if(!data_.size_) data_.last_ptr_ = &(*data_.last_ptr_)->next_;
-            ++data_.size_;
-        }
-    
-        void push_back(value_type const& v) {
-            *data_.last_ptr_ = new node(v);
-            data_.last_ptr_ = &(*data_.last_ptr_)->next_;
-            ++data_.size_;
-        }
-        
-        void clear() {
-            while(data_.first_) {
-                node* tmp = data_.first_;
-                data_.first_ = data_.first_->next_;
-                --data_.size_;
-                delete tmp;
-            }
-            data_.last_ptr_ = &data_.first_;
-        }
+    size_type size() const { return data_.size_; }
 
-        void erase(const_iterator i, const_iterator j) {
-            node** ptr = &data_.first_;
+    void sort() { sort(std::less<T>()); }
 
-            while(*ptr != i.ptr_) {
-                ptr = &(*ptr)->next_;
-            }
+    template <typename Less> void sort(Less less = Less())
+    {
+      if (!empty())
+        merge_sort(
+          &data_.first_, (std::numeric_limits<size_type>::max)(), less);
+    }
 
-            while(*ptr != j.ptr_) {
-                node* to_delete = *ptr;
-                *ptr = (*ptr)->next_;
-                --data_.size_;
-                delete to_delete;
-            }
+    bool operator==(list const& y) const
+    {
+      return size() == y.size() && test::equal(begin(), end(), y.begin());
+    }
 
-            if(!*ptr) data_.last_ptr_ = ptr;
-        }
+    bool operator!=(list const& y) const { return !(*this == y); }
 
-        bool empty() const {
-            return !data_.size_;
-        }
+  private:
+    template <typename Less>
+    node** merge_sort(node** l, size_type recurse_limit, Less less)
+    {
+      node** ptr = &(*l)->next_;
+      for (size_type count = 0; count < recurse_limit && *ptr; ++count) {
+        ptr = merge_adjacent_ranges(l, ptr, merge_sort(ptr, count, less), less);
+      }
+      return ptr;
+    }
 
-        size_type size() const {
-            return data_.size_;
+    template <typename Less>
+    node** merge_adjacent_ranges(
+      node** first, node** second, node** third, Less less)
+    {
+      for (;;) {
+        for (;;) {
+          if (first == second)
+            return third;
+          if (less((*second)->value_, (*first)->value_))
+            break;
+          first = &(*first)->next_;
         }
 
-        void sort() {
-            sort(std::less<T>());
-        }
+        swap_adjacent_ranges(first, second, third);
+        first = &(*first)->next_;
 
-        template <typename Less>
-        void sort(Less less = Less()) {
-            if(!empty()) merge_sort(&data_.first_,
-                    (std::numeric_limits<size_type>::max)(), less);
-        }
+        // Since the two ranges we just swapped, the order is now:
+        // first...third...second
 
-        bool operator==(list const& y) const {
-            return size() == y.size() &&
-                test::equal(begin(), end(), y.begin());
+        for (;;) {
+          if (first == third)
+            return second;
+          if (!less((*first)->value_, (*third)->value_))
+            break;
+          first = &(*first)->next_;
         }
 
-        bool operator!=(list const& y) const {
-            return !(*this == y);
-        }
+        swap_adjacent_ranges(first, third, second);
+        first = &(*first)->next_;
+      }
+    }
 
-    private:
-        template <typename Less>
-        node** merge_sort(node** l, size_type recurse_limit, Less less)
-        {
-            node** ptr = &(*l)->next_;
-            for(size_type count = 0; count < recurse_limit && *ptr; ++count)
-            {
-                ptr = merge_adjacent_ranges(l, ptr,
-                        merge_sort(ptr, count, less), less);
-            }
-            return ptr;
-        }
-        
-        template <typename Less>
-        node** merge_adjacent_ranges(node** first, node** second,
-                node** third, Less less)
-        {
-            for(;;) {
-                for(;;) {
-                    if(first == second) return third;
-                    if(less((*second)->value_, (*first)->value_)) break;
-                    first = &(*first)->next_;
-                }
-
-                swap_adjacent_ranges(first, second, third);
-                first = &(*first)->next_;
-                
-                // Since the two ranges we just swapped, the order is now:
-                // first...third...second
-                
-                for(;;) {
-                    if(first == third) return second;
-                    if(!less((*first)->value_, (*third)->value_)) break;
-                    first = &(*first)->next_;
-                }
-
-                swap_adjacent_ranges(first, third, second);
-                first = &(*first)->next_;
-            }
-        }
-        
-        void swap_adjacent_ranges(node** first, node** second, node** third)
-        {
-            node* tmp = *first;
-            *first = *second;
-            *second = *third;
-            *third = tmp;
-            if(!*second) data_.last_ptr_ = second;
-        }
-    };
+    void swap_adjacent_ranges(node** first, node** second, node** third)
+    {
+      node* tmp = *first;
+      *first = *second;
+      *second = *third;
+      *third = tmp;
+      if (!*second)
+        data_.last_ptr_ = second;
+    }
+  };
 }
 
 #endif