boost/unordered/detail/node.hpp
// Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard. // Copyright (C) 2005-2009 Daniel James // 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) // This contains the basic data structure, apart from the actual values. There's // no construction or deconstruction here. So this only depends on the pointer // type. #ifndef BOOST_UNORDERED_DETAIL_NODE_HPP_INCLUDED #define BOOST_UNORDERED_DETAIL_NODE_HPP_INCLUDED #include <boost/config.hpp> #include <boost/assert.hpp> #include <boost/detail/workaround.hpp> #include <boost/unordered/detail/fwd.hpp> #if BOOST_WORKAROUND(__BORLANDC__, <= 0X0582) #define BOOST_UNORDERED_BORLAND_BOOL(x) (bool)(x) #else #define BOOST_UNORDERED_BORLAND_BOOL(x) x #endif namespace boost { namespace unordered_detail { //////////////////////////////////////////////////////////////////////////// // ungrouped node implementation template <class A> inline BOOST_DEDUCED_TYPENAME ungrouped_node_base<A>::node_ptr& ungrouped_node_base<A>::next_group(node_ptr ptr) { return ptr->next_; } template <class A> inline std::size_t ungrouped_node_base<A>::group_count(node_ptr) { return 1; } template <class A> inline void ungrouped_node_base<A>::add_to_bucket(node_ptr n, bucket& b) { n->next_ = b.next_; b.next_ = n; } template <class A> inline void ungrouped_node_base<A>::add_after_node(node_ptr n, node_ptr position) { n->next_ = position->next_; position->next_ = position; } template <class A> inline void ungrouped_node_base<A>::unlink_nodes(bucket& b, node_ptr begin, node_ptr end) { node_ptr* pos = &b.next_; while(*pos != begin) pos = &(*pos)->next_; *pos = end; } template <class A> inline void ungrouped_node_base<A>::unlink_nodes(bucket& b, node_ptr end) { b.next_ = end; } template <class A> inline void ungrouped_node_base<A>::unlink_node(bucket& b, node_ptr n) { unlink_nodes(b, n, n->next_); } //////////////////////////////////////////////////////////////////////////// // grouped node implementation // If ptr is the first element in a group, return pointer to next group. // Otherwise returns a pointer to ptr. template <class A> inline BOOST_DEDUCED_TYPENAME grouped_node_base<A>::node_ptr& grouped_node_base<A>::next_group(node_ptr ptr) { return get(ptr).group_prev_->next_; } template <class A> inline BOOST_DEDUCED_TYPENAME grouped_node_base<A>::node_ptr grouped_node_base<A>::first_in_group(node_ptr ptr) { while(next_group(ptr) == ptr) ptr = get(ptr).group_prev_; return ptr; } template <class A> inline std::size_t grouped_node_base<A>::group_count(node_ptr ptr) { node_ptr start = ptr; std::size_t size = 0; do { ++size; ptr = get(ptr).group_prev_; } while(ptr != start); return size; } template <class A> inline void grouped_node_base<A>::add_to_bucket(node_ptr n, bucket& b) { n->next_ = b.next_; get(n).group_prev_ = n; b.next_ = n; } template <class A> inline void grouped_node_base<A>::add_after_node(node_ptr n, node_ptr pos) { n->next_ = next_group(pos); get(n).group_prev_ = get(pos).group_prev_; next_group(pos) = n; get(pos).group_prev_ = n; } // Break a ciruclar list into two, with split as the beginning // of the second group (if split is at the beginning then don't // split). template <class A> inline BOOST_DEDUCED_TYPENAME grouped_node_base<A>::node_ptr grouped_node_base<A>::split_group(node_ptr split) { node_ptr first = first_in_group(split); if(first == split) return split; node_ptr last = get(first).group_prev_; get(first).group_prev_ = get(split).group_prev_; get(split).group_prev_ = last; return first; } template <class A> void grouped_node_base<A>::unlink_node(bucket& b, node_ptr n) { node_ptr next = n->next_; node_ptr* pos = &next_group(n); if(*pos != n) { // The node is at the beginning of a group. // Find the previous node pointer: pos = &b.next_; while(*pos != n) pos = &next_group(*pos); // Remove from group if(BOOST_UNORDERED_BORLAND_BOOL(next) && get(next).group_prev_ == n) { get(next).group_prev_ = get(n).group_prev_; } } else if(BOOST_UNORDERED_BORLAND_BOOL(next) && get(next).group_prev_ == n) { // The deleted node is not at the end of the group, so // change the link from the next node. get(next).group_prev_ = get(n).group_prev_; } else { // The deleted node is at the end of the group, so the // first node in the group is pointing to it. // Find that to change its pointer. node_ptr x = get(n).group_prev_; while(get(x).group_prev_ != n) { x = get(x).group_prev_; } get(x).group_prev_ = get(n).group_prev_; } *pos = next; } template <class A> void grouped_node_base<A>::unlink_nodes(bucket& b, node_ptr begin, node_ptr end) { node_ptr* pos = &next_group(begin); if(*pos != begin) { // The node is at the beginning of a group. // Find the previous node pointer: pos = &b.next_; while(*pos != begin) pos = &next_group(*pos); // Remove from group if(BOOST_UNORDERED_BORLAND_BOOL(end)) split_group(end); } else { node_ptr group1 = split_group(begin); if(BOOST_UNORDERED_BORLAND_BOOL(end)) { node_ptr group2 = split_group(end); if(begin == group2) { node_ptr end1 = get(group1).group_prev_; node_ptr end2 = get(group2).group_prev_; get(group1).group_prev_ = end2; get(group2).group_prev_ = end1; } } } *pos = end; } template <class A> void grouped_node_base<A>::unlink_nodes(bucket& b, node_ptr end) { split_group(end); b.next_ = end; } }} #endif