FM / detail

/usr/include/boost/intrusive/detail

Name	Size	Mode	Actions
algorithm.hpp	2880	0644	edit dl rm
algo_type.hpp	1303	0644	edit dl rm
any_node_and_algorithms.hpp	9467	0644	edit dl rm
array_initializer.hpp	2235	0644	edit dl rm
assert.hpp	1520	0644	edit dl rm
avltree_node.hpp	6714	0644	edit dl rm
bstree_algorithms_base.hpp	5523	0644	edit dl rm
common_slist_algorithms.hpp	5974	0644	edit dl rm
config_begin.hpp	2456	0644	edit dl rm
config_end.hpp	496	0644	edit dl rm
default_header_holder.hpp	2243	0644	edit dl rm
ebo_functor_holder.hpp	8005	0644	edit dl rm
empty_node_checker.hpp	1243	0644	edit dl rm
equal_to_value.hpp	1217	0644	edit dl rm
exception_disposer.hpp	2132	0644	edit dl rm
function_detector.hpp	3456	0644	edit dl rm
generic_hook.hpp	6588	0644	edit dl rm
get_value_traits.hpp	7098	0644	edit dl rm
hashtable_node.hpp	10234	0644	edit dl rm
has_member_function_callable_with.hpp	18438	0644	edit dl rm
hook_traits.hpp	8438	0644	edit dl rm
iiterator.hpp	4446	0644	edit dl rm
is_stateful_value_traits.hpp	2524	0644	edit dl rm
iterator.hpp	7612	0644	edit dl rm
key_nodeptr_comp.hpp	4882	0644	edit dl rm
list_iterator.hpp	5230	0644	edit dl rm
list_node.hpp	2152	0644	edit dl rm
math.hpp	8059	0644	edit dl rm
minimal_less_equal_header.hpp	932	0644	edit dl rm
minimal_pair_header.hpp	904	0644	edit dl rm
mpl.hpp	8592	0644	edit dl rm
node_cloner_disposer.hpp	3973	0644	edit dl rm
node_holder.hpp	883	0644	edit dl rm
node_to_value.hpp	3994	0644	edit dl rm
parent_from_member.hpp	4191	0644	edit dl rm
rbtree_node.hpp	6952	0644	edit dl rm
reverse_iterator.hpp	4644	0644	edit dl rm
simple_disposers.hpp	1177	0644	edit dl rm
size_holder.hpp	2261	0644	edit dl rm
slist_iterator.hpp	4968	0644	edit dl rm
slist_node.hpp	1907	0644	edit dl rm
std_fwd.hpp	1226	0644	edit dl rm
transform_iterator.hpp	5789	0644	edit dl rm
tree_iterator.hpp	6605	0644	edit dl rm
tree_node.hpp	2307	0644	edit dl rm
tree_value_compare.hpp	7711	0644	edit dl rm
uncast.hpp	1646	0644	edit dl rm
workaround.hpp	2061	0644	edit dl rm

Edit: /usr/include/boost/intrusive/detail/bstree_algorithms_base.hpp (5523B)

/////////////////////////////////////////////////////////////////////////////
//
// (C) Copyright Ion Gaztanaga  2014-2014
//
// 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_BSTREE_ALGORITHMS_BASE_HPP
#define BOOST_INTRUSIVE_BSTREE_ALGORITHMS_BASE_HPP

#ifndef BOOST_CONFIG_HPP
# include <boost/config.hpp>
#endif

#if defined(BOOST_HAS_PRAGMA_ONCE)
#  pragma once
#endif

#include <boost/intrusive/detail/uncast.hpp>

namespace boost {
namespace intrusive {

template<class NodeTraits>
class bstree_algorithms_base
{
 public:
 typedef typename NodeTraits::node node;
 typedef NodeTraits node_traits;
 typedef typename NodeTraits::node_ptr node_ptr;
 typedef typename NodeTraits::const_node_ptr const_node_ptr;

//! Requires: 'node' is a node from the tree except the header.
 //!
 //! Effects: Returns the next node of the tree.
 //!
 //! Complexity: Average constant time.
 //!
 //! Throws: Nothing.
 static node_ptr next_node(const node_ptr & node)
 {
 node_ptr const n_right(NodeTraits::get_right(node));
 if(n_right){
 return minimum(n_right);
 }
 else {
 node_ptr n(node);
 node_ptr p(NodeTraits::get_parent(n));
 while(n == NodeTraits::get_right(p)){
 n = p;
 p = NodeTraits::get_parent(p);
 }
 return NodeTraits::get_right(n) != p ? p : n;
 }
 }

//! Requires: 'node' is a node from the tree except the leftmost node.
 //!
 //! Effects: Returns the previous node of the tree.
 //!
 //! Complexity: Average constant time.
 //!
 //! Throws: Nothing.
 static node_ptr prev_node(const node_ptr & node)
 {
 if(is_header(node)){
 //return NodeTraits::get_right(node);
 return maximum(NodeTraits::get_parent(node));
 }
 else if(NodeTraits::get_left(node)){
 return maximum(NodeTraits::get_left(node));
 }
 else {
 node_ptr p(node);
 node_ptr x = NodeTraits::get_parent(p);
 while(p == NodeTraits::get_left(x)){
 p = x;
 x = NodeTraits::get_parent(x);
 }
 return x;
 }
 }

//! Requires: 'node' is a node of a tree but not the header.
 //!
 //! Effects: Returns the minimum node of the subtree starting at p.
 //!
 //! Complexity: Logarithmic to the size of the subtree.
 //!
 //! Throws: Nothing.
 static node_ptr minimum(node_ptr node)
 {
 for(node_ptr p_left = NodeTraits::get_left(node)
 ;p_left
 ;p_left = NodeTraits::get_left(node)){
 node = p_left;
 }
 return node;
 }

//! Requires: 'node' is a node of a tree but not the header.
 //!
 //! Effects: Returns the maximum node of the subtree starting at p.
 //!
 //! Complexity: Logarithmic to the size of the subtree.
 //!
 //! Throws: Nothing.
 static node_ptr maximum(node_ptr node)
 {
 for(node_ptr p_right = NodeTraits::get_right(node)
 ;p_right
 ;p_right = NodeTraits::get_right(node)){
 node = p_right;
 }
 return node;
 }

//! Requires: p is a node of a tree.
 //!
 //! Effects: Returns true if p is the header of the tree.
 //!
 //! Complexity: Constant.
 //!
 //! Throws: Nothing.
 static bool is_header(const const_node_ptr & p)
 {
 node_ptr p_left (NodeTraits::get_left(p));
 node_ptr p_right(NodeTraits::get_right(p));
 if(!NodeTraits::get_parent(p) || //Header condition when empty tree
 (p_left && p_right && //Header always has leftmost and rightmost
 (p_left == p_right || //Header condition when only node
 (NodeTraits::get_parent(p_left) != p ||
 NodeTraits::get_parent(p_right) != p ))
 //When tree size > 1 headers can't be leftmost's
 //and rightmost's parent
 )){
 return true;
 }
 return false;
 }

//! Requires: 'node' is a node of the tree or a header node.
 //!
 //! Effects: Returns the header of the tree.
 //!
 //! Complexity: Logarithmic.
 //!
 //! Throws: Nothing.
 static node_ptr get_header(const const_node_ptr & node)
 {
 node_ptr n(detail::uncast(node));
 node_ptr p(NodeTraits::get_parent(node));
 //If p is null, then n is the header of an empty tree
 if(p){
 //Non-empty tree, check if n is neither root nor header
 node_ptr pp(NodeTraits::get_parent(p));
 //If granparent is not equal to n, then n is neither root nor header,
 //the try the fast path
 if(n != pp){
 do{
 n = p;
 p = pp;
 pp = NodeTraits::get_parent(pp);
 }while(n != pp);
 n = p;
 }
 //Check if n is root or header when size() > 0
 else if(!bstree_algorithms_base::is_header(n)){
 n = p;
 }
 }
 return n;
 }
};

}  //namespace intrusive
}  //namespace boost

#endif //BOOST_INTRUSIVE_BSTREE_ALGORITHMS_BASE_HPP

cmd: