ceph/src/boost/boost/graph/detail/list_base.hpp

   1 //=======================================================================
   2 // Copyright 2002 Indiana University.
   3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
   4 //
   5 // Distributed under the Boost Software License, Version 1.0. (See
   6 // accompanying file LICENSE_1_0.txt or copy at
   7 // http://www.boost.org/LICENSE_1_0.txt)
   8 //=======================================================================
   9
  10 #ifndef BOOST_LIST_BASE_HPP
  11 #define BOOST_LIST_BASE_HPP
  12
  13 #include <boost/iterator_adaptors.hpp>
  14
  15 // Perhaps this should go through formal review, and move to <boost/>.
  16
  17 /*
  18   An alternate interface idea:
  19     Extend the std::list functionality by creating remove/insert
  20     functions that do not require the container object!
  21  */
  22
  23 namespace boost {
  24   namespace detail {
  25
  26     //=========================================================================
  27     // Linked-List Generic Implementation Functions
  28
  29     template <class Node, class Next>
  30     inline Node
  31     slist_insert_after(Node pos, Node x,
  32                        Next next)
  33     {
  34       next(x) = next(pos);
  35       next(pos) = x;
  36       return x;
  37     }
  38
  39     // return next(pos) or next(next(pos)) ?
  40     template <class Node, class Next>
  41     inline Node
  42     slist_remove_after(Node pos,
  43                        Next next)
  44     {
  45       Node n = next(pos);
  46       next(pos) = next(n);
  47       return n;
  48     }
  49
  50     template <class Node, class Next>
  51     inline Node
  52     slist_remove_range(Node before_first, Node last,
  53                        Next next)
  54     {
  55       next(before_first) = last;
  56       return last;
  57     }
  58
  59     template <class Node, class Next>
  60     inline Node
  61     slist_previous(Node head, Node x, Node empty,
  62                    Next next)
  63     {
  64       while (head != empty && next(head) != x)
  65         head = next(head);
  66       return head;
  67     }
  68
  69     template<class Node, class Next>
  70     inline void
  71     slist_splice_after(Node pos, Node before_first, Node before_last,
  72                        Next next)
  73     {
  74       if (pos != before_first && pos != before_last) {
  75         Node first = next(before_first);
  76         Node after = next(pos);
  77         next(before_first) = next(before_last);
  78         next(pos) = first;
  79         next(before_last) = after;
  80       }
  81     }
  82
  83     template <class Node, class Next>
  84     inline Node
  85     slist_reverse(Node node, Node empty,
  86                   Next next)
  87     {
  88       Node result = node;
  89       node = next(node);
  90       next(result) = empty;
  91       while(node) {
  92         Node next = next(node);
  93         next(node) = result;
  94         result = node;
  95         node = next;
  96       }
  97       return result;
  98     }
  99
 100     template <class Node, class Next>
 101     inline std::size_t
 102     slist_size(Node head, Node empty,
 103                Next next)
 104     {
 105       std::size_t s = 0;
 106       for ( ; head != empty; head = next(head))
 107         ++s;
 108       return s;
 109     }
 110
 111     template <class Next, class Data>
 112     class slist_iterator_policies
 113     {
 114     public:
 115       explicit slist_iterator_policies(const Next& n, const Data& d)
 116         : m_next(n), m_data(d) { }
 117
 118       template <class Reference, class Node>
 119       Reference dereference(type<Reference>, const Node& x) const
 120         { return m_data(x); }
 121
 122       template <class Node>
 123       void increment(Node& x) const
 124         { x = m_next(x); }
 125
 126       template <class Node>
 127       bool equal(Node& x, Node& y) const
 128         { return x == y; }
 129
 130     protected:
 131       Next m_next;
 132       Data m_data;
 133     };
 134
 135   //===========================================================================
 136   // Doubly-Linked List Generic Implementation Functions
 137
 138     template <class Node, class Next, class Prev>
 139     inline void
 140     dlist_insert_before(Node pos, Node x,
 141                         Next next, Prev prev)
 142     {
 143       next(x) = pos;
 144       prev(x) = prev(pos);
 145       next(prev(pos)) = x;
 146       prev(pos) = x;
 147     }
 148
 149     template <class Node, class Next, class Prev>
 150     void
 151     dlist_remove(Node pos,
 152                  Next next, Prev prev)
 153     {
 154       Node next_node = next(pos);
 155       Node prev_node = prev(pos);
 156       next(prev_node) = next_node;
 157       prev(next_node) = prev_node;
 158     }
 159
 160     // This deletes every node in the list except the
 161     // sentinel node.
 162     template <class Node, class Delete>
 163     inline void
 164     dlist_clear(Node sentinel, Delete del)
 165     {
 166       Node i, tmp;
 167       i = next(sentinel);
 168       while (i != sentinel) {
 169         tmp = i;
 170         i = next(i);
 171         del(tmp);
 172       }
 173     }
 174
 175     template <class Node>
 176     inline bool
 177     dlist_empty(Node dummy)
 178     {
 179       return next(dummy) == dummy;
 180     }
 181
 182     template <class Node, class Next, class Prev>
 183     void
 184     dlist_transfer(Node pos, Node first, Node last,
 185                    Next next, Prev prev)
 186     {
 187       if (pos != last) {
 188         // Remove [first,last) from its old position
 189         next(prev(last)) = pos;
 190         next(prev(first)) = last;
 191         next(prev(pos)) = first;
 192
 193         // Splice [first,last) into its new position
 194         Node tmp = prev(pos);
 195         prev(pos) = prev(last);
 196         prev(last) = prev(first);
 197         prev(first) = tmp;
 198       }
 199     }
 200
 201     template <class Next, class Prev, class Data>
 202     class dlist_iterator_policies
 203       : public slist_iterator_policies<Next, Data>
 204     {
 205       typedef slist_iterator_policies<Next, Data> Base;
 206     public:
 207       template <class Node>
 208       void decrement(Node& x) const
 209         { x = m_prev(x); }
 210
 211       dlist_iterator_policies(Next n, Prev p, Data d)
 212         : Base(n,d), m_prev(p) { }
 213     protected:
 214       Prev m_prev;
 215     };
 216
 217   } // namespace detail
 218 } // namespace boost
 219
 220 #endif // BOOST_LIST_BASE_HPP