| |
| // 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 |