X-Git-Url: http://g0dil.de/git?a=blobdiff_plain;f=senf%2Fboost_intrusive%2Fslist_algorithms.hpp;fp=senf%2Fboost_intrusive%2Fslist_algorithms.hpp;h=19158ce780e3963e6bca443ef8eb345a9c3c5021;hb=8f1ff66f5b7d10cfc6d35fb72267bc2fb3b588f7;hp=0000000000000000000000000000000000000000;hpb=fbd3d0ff298683f08b59f25288d8c243e03b206c;p=senf.git diff --git a/senf/boost_intrusive/slist_algorithms.hpp b/senf/boost_intrusive/slist_algorithms.hpp new file mode 100644 index 0000000..19158ce --- /dev/null +++ b/senf/boost_intrusive/slist_algorithms.hpp @@ -0,0 +1,246 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Olaf Krzikalla 2004-2006. +// (C) Copyright Ion Gaztañaga 2006-2007 +// +// Distributed under the Boost Software License, Version 1.0. +// (See accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) +// +// See http://www.boost.org/libs/intrusive for documentation. +// +///////////////////////////////////////////////////////////////////////////// + +#ifndef BOOST_INTRUSIVE_SLIST_ALGORITHMS_HPP +#define BOOST_INTRUSIVE_SLIST_ALGORITHMS_HPP + +#include "detail/config_begin.hpp" +#include +#include +#include "detail/pointer_type.hpp" +#include "detail/pointer_to_other.hpp" +#include +#include + +namespace boost { +namespace intrusive { + +//! slist_algorithms provides basic algorithms to manipulate nodes +//! forming a circular singly linked list. An empty circular list is formed by a node +//! whose pointer to the next node points to itself. +//! +//! slist_algorithms is configured with a NodeTraits class, which capsulates the +//! information about the node to be manipulated. NodeTraits must support the +//! following interface: +//! +//! Typedefs: +//! +//! node: The type of the node that forms the circular list +//! +//! node_ptr: A pointer to a node +//! +//! const_node_ptr: A pointer to a const node +//! +//! Static functions: +//! +//! static node_ptr get_next(const_node_ptr n); +//! +//! static void set_next(node_ptr n, node_ptr next); +template +class slist_algorithms +{ + public: + typedef typename NodeTraits::node_ptr node_ptr; + typedef typename NodeTraits::const_node_ptr const_node_ptr; + + //! Requires: this_node must be in a circular list or be an empty circular list. + //! + //! Effects: Returns the previous node of this_node in the circular list. + //! + //! Complexity: Linear to the number of elements in the circular list. + //! + //! Throws: Nothing. + static node_ptr get_previous_node(node_ptr this_node) + { + node_ptr p = this_node; + while (this_node != NodeTraits::get_next(p)) + p = NodeTraits::get_next(p); + return p; + } + + //! Requires: this_node and prev_init_node must be in the same circular list. + //! + //! Effects: Returns the previous node of this_node in the circular list starting. + //! the search from prev_init_node. The first node checked for equality + //! is NodeTraits::get_next(prev_init_node). + //! + //! Complexity: Linear to the number of elements between prev_init_node and this_node. + //! + //! Throws: Nothing. + static node_ptr get_previous_node(node_ptr prev_init_node, node_ptr this_node) + { + node_ptr p = prev_init_node; + while (this_node != NodeTraits::get_next(p)) + p = NodeTraits::get_next(p); + return p; + } + + //! Effects: Constructs an empty list, making this_node the only + //! node of the circular list: + //! NodeTraits::get_next(this_node) == NodeTraits::get_previous(this_node) + //! == this_node. + //! + //! Complexity: Constant + //! + //! Throws: Nothing. + static void init(node_ptr this_node) + { NodeTraits::set_next(this_node, this_node); } + + //! Requires: this_node must be in a circular list or be an empty circular list. + //! + //! Effects: Returns true is "this_node" is the only node of a circular list: + //! return NodeTraits::get_next(this_node) == this_node + //! + //! Complexity: Constant + //! + //! Throws: Nothing. + static bool unique(const_node_ptr this_node) + { return NodeTraits::get_next(this_node) == this_node; } + + //! Requires: this_node must be in a circular list or be an empty circular list. + //! + //! Effects: Returns the number of nodes in a circular list. If the circular list + //! is empty, returns 1. + //! + //! Complexity: Constant + //! + //! Throws: Nothing. + static std::size_t count(const_node_ptr this_node) + { + std::size_t result = 0; + const_node_ptr p = this_node; + do{ + p = NodeTraits::get_next(p); + ++result; + } while (p != this_node); + return result; + } + + //! Requires: prev_node must be in a circular list or be an empty circular list. + //! + //! Effects: Unlinks the next node of prev_node from the circular list. + //! + //! Complexity: Constant + //! + //! Throws: Nothing. + static void unlink_after(node_ptr prev_node) + { + node_ptr this_node(NodeTraits::get_next(prev_node)); + NodeTraits::set_next(prev_node, NodeTraits::get_next(this_node)); + NodeTraits::set_next(this_node, this_node); + } + + //! Requires: this_node must be in a circular list or be an empty circular list. + //! + //! Effects: Unlinks the node from the circular list. + //! + //! Complexity: Linear to the number of elements in the circular list + //! + //! Throws: Nothing. + static void unlink(node_ptr this_node) + { unlink_after(get_previous_node(this_node)); } + + //! Requires: prev_node must be a node of a circular list. + //! + //! Effects: Links this_node after prev_node in the circular list. + //! + //! Complexity: Constant + //! + //! Throws: Nothing. + static void link_after(node_ptr prev_node, node_ptr this_node) + { + NodeTraits::set_next(this_node, NodeTraits::get_next(prev_node)); + NodeTraits::set_next(prev_node, this_node); + } + + //! Requires: nxt_node must be a node of a circular list. + //! + //! Effects: Links this_node before nxt_node in the circular list. + //! + //! Complexity: Linear to the number of elements in the circular list. + //! + //! Throws: Nothing. + static void link_before (node_ptr nxt_node, node_ptr this_node) + { link_after(get_previous_node(nxt_node), this_node); } + + //! Requires: this_node and other_node must be nodes inserted + //! in circular lists or be empty circular lists. + //! + //! Effects: Swaps the position of the nodes: this_node is inserted in + //! other_nodes position in the second circular list and the other_node is inserted + //! in this_node's position in the first circular list. + //! + //! Complexity: Linear to number of elements of both lists + //! + //! Throws: Nothing. + static void swap_nodes(node_ptr this_node, node_ptr other_node) + { + if (other_node == this_node) + return; + bool empty1 = unique(this_node); + bool empty2 = unique(other_node); + node_ptr prev_this (get_previous_node(this_node)); + node_ptr prev_other(get_previous_node(other_node)); + + node_ptr this_next (NodeTraits::get_next(this_node)); + node_ptr other_next(NodeTraits::get_next(other_node)); + NodeTraits::set_next(this_node, other_next); + NodeTraits::set_next(other_node, this_next); + NodeTraits::set_next(empty1 ? other_node : prev_this, other_node); + NodeTraits::set_next(empty2 ? this_node : prev_other, this_node); + } + + //! Requires: b and e must be nodes of the same circular list or an empty range. + //! and p must be a node of a different circular list. + //! + //! Effects: Removes the nodes from [b, e) range from their circular list and inserts + //! them after p in p's circular list. + //! + //! Complexity: Constant + //! + //! Throws: Nothing. + static void transfer_after(node_ptr p, node_ptr b, node_ptr e) + { + if (p != b && p != e) { + node_ptr next_b = NodeTraits::get_next(b); + node_ptr next_e = NodeTraits::get_next(e); + node_ptr next_p = NodeTraits::get_next(p); + NodeTraits::set_next(b, next_e); + NodeTraits::set_next(e, next_p); + NodeTraits::set_next(p, next_b); + } + } + + //! Effects: Reverses the order of elements in the list. + //! + //! Throws: Nothing. + //! + //! Complexity: This function is linear to the contained elements. + static void reverse(node_ptr p) + { + node_ptr i = NodeTraits::get_next(p), e(p); + for (;;) { + node_ptr nxt(NodeTraits::get_next(i)); + if (nxt == e) + break; + transfer_after(e, i, nxt); + } + } +}; + +} //namespace intrusive +} //namespace boost + +#include "detail/config_end.hpp" + +#endif //BOOST_INTRUSIVE_SLIST_ALGORITHMS_HPP