/* Copyright 2003-2008 Joaquin M Lopez Munoz. | |
* 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/multi_index for library home page. | |
*/ | |
#ifndef BOOST_MULTI_INDEX_DETAIL_HASH_INDEX_NODE_HPP | |
#define BOOST_MULTI_INDEX_DETAIL_HASH_INDEX_NODE_HPP | |
#if defined(_MSC_VER)&&(_MSC_VER>=1200) | |
#pragma once | |
#endif | |
#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */ | |
#include <boost/detail/allocator_utilities.hpp> | |
#include <boost/multi_index/detail/prevent_eti.hpp> | |
#include <functional> | |
namespace boost{ | |
namespace multi_index{ | |
namespace detail{ | |
/* singly-linked node for use by hashed_index */ | |
template<typename Allocator> | |
struct hashed_index_node_impl | |
{ | |
typedef typename prevent_eti< | |
Allocator, | |
typename boost::detail::allocator::rebind_to< | |
Allocator,hashed_index_node_impl | |
>::type | |
>::type::pointer pointer; | |
typedef typename prevent_eti< | |
Allocator, | |
typename boost::detail::allocator::rebind_to< | |
Allocator,hashed_index_node_impl | |
>::type | |
>::type::const_pointer const_pointer; | |
pointer& next(){return next_;} | |
pointer next()const{return next_;} | |
/* algorithmic stuff */ | |
static void increment(pointer& x,pointer bbegin,pointer bend) | |
{ | |
std::less_equal<pointer> leq; | |
x=x->next(); | |
if(leq(bbegin,x)&&leq(x,bend)){ /* bucket node */ | |
do{ | |
++x; | |
}while(x->next()==x); | |
x=x->next(); | |
} | |
} | |
static void link(pointer x,pointer pos) | |
{ | |
x->next()=pos->next(); | |
pos->next()=x; | |
}; | |
static void unlink(pointer x) | |
{ | |
pointer y=x->next(); | |
while(y->next()!=x){y=y->next();} | |
y->next()=x->next(); | |
} | |
static pointer prev(pointer x) | |
{ | |
pointer y=x->next(); | |
while(y->next()!=x){y=y->next();} | |
return y; | |
} | |
static void unlink_next(pointer x) | |
{ | |
x->next()=x->next()->next(); | |
} | |
private: | |
pointer next_; | |
}; | |
template<typename Super> | |
struct hashed_index_node_trampoline: | |
prevent_eti< | |
Super, | |
hashed_index_node_impl< | |
typename boost::detail::allocator::rebind_to< | |
typename Super::allocator_type, | |
char | |
>::type | |
> | |
>::type | |
{ | |
typedef typename prevent_eti< | |
Super, | |
hashed_index_node_impl< | |
typename boost::detail::allocator::rebind_to< | |
typename Super::allocator_type, | |
char | |
>::type | |
> | |
>::type impl_type; | |
}; | |
template<typename Super> | |
struct hashed_index_node:Super,hashed_index_node_trampoline<Super> | |
{ | |
private: | |
typedef hashed_index_node_trampoline<Super> trampoline; | |
public: | |
typedef typename trampoline::impl_type impl_type; | |
typedef typename trampoline::pointer impl_pointer; | |
typedef typename trampoline::const_pointer const_impl_pointer; | |
impl_pointer impl() | |
{ | |
return static_cast<impl_pointer>( | |
static_cast<impl_type*>(static_cast<trampoline*>(this))); | |
} | |
const_impl_pointer impl()const | |
{ | |
return static_cast<const_impl_pointer>( | |
static_cast<const impl_type*>(static_cast<const trampoline*>(this))); | |
} | |
static hashed_index_node* from_impl(impl_pointer x) | |
{ | |
return static_cast<hashed_index_node*>( | |
static_cast<trampoline*>(&*x)); | |
} | |
static const hashed_index_node* from_impl(const_impl_pointer x) | |
{ | |
return static_cast<const hashed_index_node*>( | |
static_cast<const trampoline*>(&*x)); | |
} | |
static void increment( | |
hashed_index_node*& x,impl_pointer bbegin,impl_pointer bend) | |
{ | |
impl_pointer xi=x->impl(); | |
trampoline::increment(xi,bbegin,bend); | |
x=from_impl(xi); | |
} | |
}; | |
} /* namespace multi_index::detail */ | |
} /* namespace multi_index */ | |
} /* namespace boost */ | |
#endif |