Swiftdiff options
22 files changed, 6165 insertions, 1 deletions
diff --git a/3rdParty/Boost/src/boost/compressed_pair.hpp b/3rdParty/Boost/src/boost/compressed_pair.hpp new file mode 100644 index 0000000..e6cd6a0 --- /dev/null +++ b/3rdParty/Boost/src/boost/compressed_pair.hpp @@ -0,0 +1,24 @@ +// (C) Copyright Steve Cleary, Beman Dawes, Howard Hinnant & John Maddock 2000. +// Use, modification and distribution are subject to 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/utility for most recent version including documentation. + +// See boost/detail/compressed_pair.hpp and boost/detail/ob_compressed_pair.hpp +// for full copyright notices. + +#ifndef BOOST_COMPRESSED_PAIR_HPP +#define BOOST_COMPRESSED_PAIR_HPP + +#ifndef BOOST_CONFIG_HPP +#include <boost/config.hpp> +#endif + +#ifdef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION +#include <boost/detail/ob_compressed_pair.hpp> +#else +#include <boost/detail/compressed_pair.hpp> +#endif + +#endif // BOOST_COMPRESSED_PAIR_HPP diff --git a/3rdParty/Boost/src/boost/detail/allocator_utilities.hpp b/3rdParty/Boost/src/boost/detail/allocator_utilities.hpp new file mode 100644 index 0000000..5d6ef48 --- /dev/null +++ b/3rdParty/Boost/src/boost/detail/allocator_utilities.hpp @@ -0,0 +1,212 @@ +/* Copyright 2003-2009 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 Boost website at http://www.boost.org/ + */ + +#ifndef BOOST_DETAIL_ALLOCATOR_UTILITIES_HPP +#define BOOST_DETAIL_ALLOCATOR_UTILITIES_HPP + +#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */ +#include <boost/detail/workaround.hpp> +#include <boost/mpl/aux_/msvc_never_true.hpp> +#include <boost/mpl/eval_if.hpp> +#include <boost/type_traits/is_same.hpp> +#include <cstddef> +#include <memory> +#include <new> + +namespace boost{ + +namespace detail{ + +/* Allocator adaption layer. Some stdlibs provide allocators without rebind + * and template ctors. These facilities are simulated with the external + * template class rebind_to and the aid of partial_std_allocator_wrapper. + */ + +namespace allocator{ + +/* partial_std_allocator_wrapper inherits the functionality of a std + * allocator while providing a templatized ctor and other bits missing + * in some stdlib implementation or another. + */ + +template<typename Type> +class partial_std_allocator_wrapper:public std::allocator<Type> +{ +public: + /* Oddly enough, STLport does not define std::allocator<void>::value_type + * when configured to work without partial template specialization. + * No harm in supplying the definition here unconditionally. + */ + + typedef Type value_type; + + partial_std_allocator_wrapper(){}; + + template<typename Other> + partial_std_allocator_wrapper(const partial_std_allocator_wrapper<Other>&){} + + partial_std_allocator_wrapper(const std::allocator<Type>& x): + std::allocator<Type>(x) + { + }; + +#if defined(BOOST_DINKUMWARE_STDLIB) + /* Dinkumware guys didn't provide a means to call allocate() without + * supplying a hint, in disagreement with the standard. + */ + + Type* allocate(std::size_t n,const void* hint=0) + { + std::allocator<Type>& a=*this; + return a.allocate(n,hint); + } +#endif + +}; + +/* Detects whether a given allocator belongs to a defective stdlib not + * having the required member templates. + * Note that it does not suffice to check the Boost.Config stdlib + * macros, as the user might have passed a custom, compliant allocator. + * The checks also considers partial_std_allocator_wrapper to be + * a standard defective allocator. + */ + +#if defined(BOOST_NO_STD_ALLOCATOR)&&\ + (defined(BOOST_HAS_PARTIAL_STD_ALLOCATOR)||defined(BOOST_DINKUMWARE_STDLIB)) + +template<typename Allocator> +struct is_partial_std_allocator +{ + BOOST_STATIC_CONSTANT(bool, + value= + (is_same< + std::allocator<BOOST_DEDUCED_TYPENAME Allocator::value_type>, + Allocator + >::value)|| + (is_same< + partial_std_allocator_wrapper< + BOOST_DEDUCED_TYPENAME Allocator::value_type>, + Allocator + >::value)); +}; + +#else + +template<typename Allocator> +struct is_partial_std_allocator +{ + BOOST_STATIC_CONSTANT(bool,value=false); +}; + +#endif + +/* rebind operations for defective std allocators */ + +template<typename Allocator,typename Type> +struct partial_std_allocator_rebind_to +{ + typedef partial_std_allocator_wrapper<Type> type; +}; + +/* rebind operation in all other cases */ + +#if BOOST_WORKAROUND(BOOST_MSVC,<1300) +/* Workaround for a problem in MSVC with dependent template typedefs + * when doing rebinding of allocators. + * Modeled after <boost/mpl/aux_/msvc_dtw.hpp> (thanks, Aleksey!) + */ + +template<typename Allocator> +struct rebinder +{ + template<bool> struct fake_allocator:Allocator{}; + template<> struct fake_allocator<true> + { + template<typename Type> struct rebind{}; + }; + + template<typename Type> + struct result: + fake_allocator<mpl::aux::msvc_never_true<Allocator>::value>:: + template rebind<Type> + { + }; +}; +#else +template<typename Allocator> +struct rebinder +{ + template<typename Type> + struct result + { + typedef typename Allocator::BOOST_NESTED_TEMPLATE + rebind<Type>::other other; + }; +}; +#endif + +template<typename Allocator,typename Type> +struct compliant_allocator_rebind_to +{ + typedef typename rebinder<Allocator>:: + BOOST_NESTED_TEMPLATE result<Type>::other type; +}; + +/* rebind front-end */ + +template<typename Allocator,typename Type> +struct rebind_to: + mpl::eval_if_c< + is_partial_std_allocator<Allocator>::value, + partial_std_allocator_rebind_to<Allocator,Type>, + compliant_allocator_rebind_to<Allocator,Type> + > +{ +}; + +/* allocator-independent versions of construct and destroy */ + +template<typename Type> +void construct(void* p,const Type& t) +{ + new (p) Type(t); +} + +#if BOOST_WORKAROUND(BOOST_MSVC,BOOST_TESTED_AT(1500)) +/* MSVC++ issues spurious warnings about unreferencend formal parameters + * in destroy<Type> when Type is a class with trivial dtor. + */ + +#pragma warning(push) +#pragma warning(disable:4100) +#endif + +template<typename Type> +void destroy(const Type* p) +{ + +#if BOOST_WORKAROUND(__SUNPRO_CC,BOOST_TESTED_AT(0x590)) + const_cast<Type*>(p)->~Type(); +#else + p->~Type(); +#endif + +} + +#if BOOST_WORKAROUND(BOOST_MSVC,BOOST_TESTED_AT(1500)) +#pragma warning(pop) +#endif + +} /* namespace boost::detail::allocator */ + +} /* namespace boost::detail */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/detail/compressed_pair.hpp b/3rdParty/Boost/src/boost/detail/compressed_pair.hpp new file mode 100644 index 0000000..3f32645 --- /dev/null +++ b/3rdParty/Boost/src/boost/detail/compressed_pair.hpp @@ -0,0 +1,443 @@ +// (C) Copyright Steve Cleary, Beman Dawes, Howard Hinnant & John Maddock 2000. +// Use, modification and distribution are subject to 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/utility for most recent version including documentation. + +// compressed_pair: pair that "compresses" empty members +// (see libs/utility/compressed_pair.htm) +// +// JM changes 25 Jan 2004: +// For the case where T1 == T2 and both are empty, then first() and second() +// should return different objects. +// JM changes 25 Jan 2000: +// Removed default arguments from compressed_pair_switch to get +// C++ Builder 4 to accept them +// rewriten swap to get gcc and C++ builder to compile. +// added partial specialisations for case T1 == T2 to avoid duplicate constructor defs. + +#ifndef BOOST_DETAIL_COMPRESSED_PAIR_HPP +#define BOOST_DETAIL_COMPRESSED_PAIR_HPP + +#include <algorithm> + +#include <boost/type_traits/remove_cv.hpp> +#include <boost/type_traits/is_empty.hpp> +#include <boost/type_traits/is_same.hpp> +#include <boost/call_traits.hpp> + +#ifdef BOOST_MSVC +# pragma warning(push) +# pragma warning(disable:4512) +#endif +namespace boost +{ + +template <class T1, class T2> +class compressed_pair; + + +// compressed_pair + +namespace details +{ + // JM altered 26 Jan 2000: + template <class T1, class T2, bool IsSame, bool FirstEmpty, bool SecondEmpty> + struct compressed_pair_switch; + + template <class T1, class T2> + struct compressed_pair_switch<T1, T2, false, false, false> + {static const int value = 0;}; + + template <class T1, class T2> + struct compressed_pair_switch<T1, T2, false, true, true> + {static const int value = 3;}; + + template <class T1, class T2> + struct compressed_pair_switch<T1, T2, false, true, false> + {static const int value = 1;}; + + template <class T1, class T2> + struct compressed_pair_switch<T1, T2, false, false, true> + {static const int value = 2;}; + + template <class T1, class T2> + struct compressed_pair_switch<T1, T2, true, true, true> + {static const int value = 4;}; + + template <class T1, class T2> + struct compressed_pair_switch<T1, T2, true, false, false> + {static const int value = 5;}; + + template <class T1, class T2, int Version> class compressed_pair_imp; + +#ifdef __GNUC__ + // workaround for GCC (JM): + using std::swap; +#endif + // + // can't call unqualified swap from within classname::swap + // as Koenig lookup rules will find only the classname::swap + // member function not the global declaration, so use cp_swap + // as a forwarding function (JM): + template <typename T> + inline void cp_swap(T& t1, T& t2) + { +#ifndef __GNUC__ + using std::swap; +#endif + swap(t1, t2); + } + + // 0 derive from neither + + template <class T1, class T2> + class compressed_pair_imp<T1, T2, 0> + { + public: + typedef T1 first_type; + typedef T2 second_type; + typedef typename call_traits<first_type>::param_type first_param_type; + typedef typename call_traits<second_type>::param_type second_param_type; + typedef typename call_traits<first_type>::reference first_reference; + typedef typename call_traits<second_type>::reference second_reference; + typedef typename call_traits<first_type>::const_reference first_const_reference; + typedef typename call_traits<second_type>::const_reference second_const_reference; + + compressed_pair_imp() {} + + compressed_pair_imp(first_param_type x, second_param_type y) + : first_(x), second_(y) {} + + compressed_pair_imp(first_param_type x) + : first_(x) {} + + compressed_pair_imp(second_param_type y) + : second_(y) {} + + first_reference first() {return first_;} + first_const_reference first() const {return first_;} + + second_reference second() {return second_;} + second_const_reference second() const {return second_;} + + void swap(::boost::compressed_pair<T1, T2>& y) + { + cp_swap(first_, y.first()); + cp_swap(second_, y.second()); + } + private: + first_type first_; + second_type second_; + }; + + // 1 derive from T1 + + template <class T1, class T2> + class compressed_pair_imp<T1, T2, 1> + : protected ::boost::remove_cv<T1>::type + { + public: + typedef T1 first_type; + typedef T2 second_type; + typedef typename call_traits<first_type>::param_type first_param_type; + typedef typename call_traits<second_type>::param_type second_param_type; + typedef typename call_traits<first_type>::reference first_reference; + typedef typename call_traits<second_type>::reference second_reference; + typedef typename call_traits<first_type>::const_reference first_const_reference; + typedef typename call_traits<second_type>::const_reference second_const_reference; + + compressed_pair_imp() {} + + compressed_pair_imp(first_param_type x, second_param_type y) + : first_type(x), second_(y) {} + + compressed_pair_imp(first_param_type x) + : first_type(x) {} + + compressed_pair_imp(second_param_type y) + : second_(y) {} + + first_reference first() {return *this;} + first_const_reference first() const {return *this;} + + second_reference second() {return second_;} + second_const_reference second() const {return second_;} + + void swap(::boost::compressed_pair<T1,T2>& y) + { + // no need to swap empty base class: + cp_swap(second_, y.second()); + } + private: + second_type second_; + }; + + // 2 derive from T2 + + template <class T1, class T2> + class compressed_pair_imp<T1, T2, 2> + : protected ::boost::remove_cv<T2>::type + { + public: + typedef T1 first_type; + typedef T2 second_type; + typedef typename call_traits<first_type>::param_type first_param_type; + typedef typename call_traits<second_type>::param_type second_param_type; + typedef typename call_traits<first_type>::reference first_reference; + typedef typename call_traits<second_type>::reference second_reference; + typedef typename call_traits<first_type>::const_reference first_const_reference; + typedef typename call_traits<second_type>::const_reference second_const_reference; + + compressed_pair_imp() {} + + compressed_pair_imp(first_param_type x, second_param_type y) + : second_type(y), first_(x) {} + + compressed_pair_imp(first_param_type x) + : first_(x) {} + + compressed_pair_imp(second_param_type y) + : second_type(y) {} + + first_reference first() {return first_;} + first_const_reference first() const {return first_;} + + second_reference second() {return *this;} + second_const_reference second() const {return *this;} + + void swap(::boost::compressed_pair<T1,T2>& y) + { + // no need to swap empty base class: + cp_swap(first_, y.first()); + } + + private: + first_type first_; + }; + + // 3 derive from T1 and T2 + + template <class T1, class T2> + class compressed_pair_imp<T1, T2, 3> + : protected ::boost::remove_cv<T1>::type, + protected ::boost::remove_cv<T2>::type + { + public: + typedef T1 first_type; + typedef T2 second_type; + typedef typename call_traits<first_type>::param_type first_param_type; + typedef typename call_traits<second_type>::param_type second_param_type; + typedef typename call_traits<first_type>::reference first_reference; + typedef typename call_traits<second_type>::reference second_reference; + typedef typename call_traits<first_type>::const_reference first_const_reference; + typedef typename call_traits<second_type>::const_reference second_const_reference; + + compressed_pair_imp() {} + + compressed_pair_imp(first_param_type x, second_param_type y) + : first_type(x), second_type(y) {} + + compressed_pair_imp(first_param_type x) + : first_type(x) {} + + compressed_pair_imp(second_param_type y) + : second_type(y) {} + + first_reference first() {return *this;} + first_const_reference first() const {return *this;} + + second_reference second() {return *this;} + second_const_reference second() const {return *this;} + // + // no need to swap empty bases: + void swap(::boost::compressed_pair<T1,T2>&) {} + }; + + // JM + // 4 T1 == T2, T1 and T2 both empty + // Originally this did not store an instance of T2 at all + // but that led to problems beause it meant &x.first() == &x.second() + // which is not true for any other kind of pair, so now we store an instance + // of T2 just in case the user is relying on first() and second() returning + // different objects (albeit both empty). + template <class T1, class T2> + class compressed_pair_imp<T1, T2, 4> + : protected ::boost::remove_cv<T1>::type + { + public: + typedef T1 first_type; + typedef T2 second_type; + typedef typename call_traits<first_type>::param_type first_param_type; + typedef typename call_traits<second_type>::param_type second_param_type; + typedef typename call_traits<first_type>::reference first_reference; + typedef typename call_traits<second_type>::reference second_reference; + typedef typename call_traits<first_type>::const_reference first_const_reference; + typedef typename call_traits<second_type>::const_reference second_const_reference; + + compressed_pair_imp() {} + + compressed_pair_imp(first_param_type x, second_param_type y) + : first_type(x), m_second(y) {} + + compressed_pair_imp(first_param_type x) + : first_type(x), m_second(x) {} + + first_reference first() {return *this;} + first_const_reference first() const {return *this;} + + second_reference second() {return m_second;} + second_const_reference second() const {return m_second;} + + void swap(::boost::compressed_pair<T1,T2>&) {} + private: + T2 m_second; + }; + + // 5 T1 == T2 and are not empty: //JM + + template <class T1, class T2> + class compressed_pair_imp<T1, T2, 5> + { + public: + typedef T1 first_type; + typedef T2 second_type; + typedef typename call_traits<first_type>::param_type first_param_type; + typedef typename call_traits<second_type>::param_type second_param_type; + typedef typename call_traits<first_type>::reference first_reference; + typedef typename call_traits<second_type>::reference second_reference; + typedef typename call_traits<first_type>::const_reference first_const_reference; + typedef typename call_traits<second_type>::const_reference second_const_reference; + + compressed_pair_imp() {} + + compressed_pair_imp(first_param_type x, second_param_type y) + : first_(x), second_(y) {} + + compressed_pair_imp(first_param_type x) + : first_(x), second_(x) {} + + first_reference first() {return first_;} + first_const_reference first() const {return first_;} + + second_reference second() {return second_;} + second_const_reference second() const {return second_;} + + void swap(::boost::compressed_pair<T1, T2>& y) + { + cp_swap(first_, y.first()); + cp_swap(second_, y.second()); + } + private: + first_type first_; + second_type second_; + }; + +} // details + +template <class T1, class T2> +class compressed_pair + : private ::boost::details::compressed_pair_imp<T1, T2, + ::boost::details::compressed_pair_switch< + T1, + T2, + ::boost::is_same<typename remove_cv<T1>::type, typename remove_cv<T2>::type>::value, + ::boost::is_empty<T1>::value, + ::boost::is_empty<T2>::value>::value> +{ +private: + typedef details::compressed_pair_imp<T1, T2, + ::boost::details::compressed_pair_switch< + T1, + T2, + ::boost::is_same<typename remove_cv<T1>::type, typename remove_cv<T2>::type>::value, + ::boost::is_empty<T1>::value, + ::boost::is_empty<T2>::value>::value> base; +public: + typedef T1 first_type; + typedef T2 second_type; + typedef typename call_traits<first_type>::param_type first_param_type; + typedef typename call_traits<second_type>::param_type second_param_type; + typedef typename call_traits<first_type>::reference first_reference; + typedef typename call_traits<second_type>::reference second_reference; + typedef typename call_traits<first_type>::const_reference first_const_reference; + typedef typename call_traits<second_type>::const_reference second_const_reference; + + compressed_pair() : base() {} + compressed_pair(first_param_type x, second_param_type y) : base(x, y) {} + explicit compressed_pair(first_param_type x) : base(x) {} + explicit compressed_pair(second_param_type y) : base(y) {} + + first_reference first() {return base::first();} + first_const_reference first() const {return base::first();} + + second_reference second() {return base::second();} + second_const_reference second() const {return base::second();} + + void swap(compressed_pair& y) { base::swap(y); } +}; + +// JM +// Partial specialisation for case where T1 == T2: +// +template <class T> +class compressed_pair<T, T> + : private details::compressed_pair_imp<T, T, + ::boost::details::compressed_pair_switch< + T, + T, + ::boost::is_same<typename remove_cv<T>::type, typename remove_cv<T>::type>::value, + ::boost::is_empty<T>::value, + ::boost::is_empty<T>::value>::value> +{ +private: + typedef details::compressed_pair_imp<T, T, + ::boost::details::compressed_pair_switch< + T, + T, + ::boost::is_same<typename remove_cv<T>::type, typename remove_cv<T>::type>::value, + ::boost::is_empty<T>::value, + ::boost::is_empty<T>::value>::value> base; +public: + typedef T first_type; + typedef T second_type; + typedef typename call_traits<first_type>::param_type first_param_type; + typedef typename call_traits<second_type>::param_type second_param_type; + typedef typename call_traits<first_type>::reference first_reference; + typedef typename call_traits<second_type>::reference second_reference; + typedef typename call_traits<first_type>::const_reference first_const_reference; + typedef typename call_traits<second_type>::const_reference second_const_reference; + + compressed_pair() : base() {} + compressed_pair(first_param_type x, second_param_type y) : base(x, y) {} +#if !(defined(__SUNPRO_CC) && (__SUNPRO_CC <= 0x530)) + explicit +#endif + compressed_pair(first_param_type x) : base(x) {} + + first_reference first() {return base::first();} + first_const_reference first() const {return base::first();} + + second_reference second() {return base::second();} + second_const_reference second() const {return base::second();} + + void swap(::boost::compressed_pair<T,T>& y) { base::swap(y); } +}; + +template <class T1, class T2> +inline +void +swap(compressed_pair<T1, T2>& x, compressed_pair<T1, T2>& y) +{ + x.swap(y); +} + +} // boost + +#ifdef BOOST_MSVC +# pragma warning(pop) +#endif + +#endif // BOOST_DETAIL_COMPRESSED_PAIR_HPP + diff --git a/3rdParty/Boost/src/boost/detail/ob_compressed_pair.hpp b/3rdParty/Boost/src/boost/detail/ob_compressed_pair.hpp new file mode 100644 index 0000000..727acab --- /dev/null +++ b/3rdParty/Boost/src/boost/detail/ob_compressed_pair.hpp @@ -0,0 +1,510 @@ +// (C) Copyright Steve Cleary, Beman Dawes, Howard Hinnant & John Maddock 2000. +// Use, modification and distribution are subject to 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/utility for most recent version including documentation. +// see libs/utility/compressed_pair.hpp +// +/* Release notes: + 20 Jan 2001: + Fixed obvious bugs (David Abrahams) + 07 Oct 2000: + Added better single argument constructor support. + 03 Oct 2000: + Added VC6 support (JM). + 23rd July 2000: + Additional comments added. (JM) + Jan 2000: + Original version: this version crippled for use with crippled compilers + - John Maddock Jan 2000. +*/ + + +#ifndef BOOST_OB_COMPRESSED_PAIR_HPP +#define BOOST_OB_COMPRESSED_PAIR_HPP + +#include <algorithm> +#ifndef BOOST_OBJECT_TYPE_TRAITS_HPP +#include <boost/type_traits/object_traits.hpp> +#endif +#ifndef BOOST_SAME_TRAITS_HPP +#include <boost/type_traits/same_traits.hpp> +#endif +#ifndef BOOST_CALL_TRAITS_HPP +#include <boost/call_traits.hpp> +#endif + +namespace boost +{ +#ifdef BOOST_MSVC6_MEMBER_TEMPLATES +// +// use member templates to emulate +// partial specialisation. Note that due to +// problems with overload resolution with VC6 +// each of the compressed_pair versions that follow +// have one template single-argument constructor +// in place of two specific constructors: +// + +template <class T1, class T2> +class compressed_pair; + +namespace detail{ + +template <class A, class T1, class T2> +struct best_conversion_traits +{ + typedef char one; + typedef char (&two)[2]; + static A a; + static one test(T1); + static two test(T2); + + enum { value = sizeof(test(a)) }; +}; + +template <int> +struct init_one; + +template <> +struct init_one<1> +{ + template <class A, class T1, class T2> + static void init(const A& a, T1* p1, T2*) + { + *p1 = a; + } +}; + +template <> +struct init_one<2> +{ + template <class A, class T1, class T2> + static void init(const A& a, T1*, T2* p2) + { + *p2 = a; + } +}; + + +// T1 != T2, both non-empty +template <class T1, class T2> +class compressed_pair_0 +{ +private: + T1 _first; + T2 _second; +public: + typedef T1 first_type; + typedef T2 second_type; + typedef typename call_traits<first_type>::param_type first_param_type; + typedef typename call_traits<second_type>::param_type second_param_type; + typedef typename call_traits<first_type>::reference first_reference; + typedef typename call_traits<second_type>::reference second_reference; + typedef typename call_traits<first_type>::const_reference first_const_reference; + typedef typename call_traits<second_type>::const_reference second_const_reference; + + compressed_pair_0() : _first(), _second() {} + compressed_pair_0(first_param_type x, second_param_type y) : _first(x), _second(y) {} + template <class A> + explicit compressed_pair_0(const A& val) + { + init_one<best_conversion_traits<A, T1, T2>::value>::init(val, &_first, &_second); + } + compressed_pair_0(const ::boost::compressed_pair<T1,T2>& x) + : _first(x.first()), _second(x.second()) {} + +#if 0 + compressed_pair_0& operator=(const compressed_pair_0& x) { + cout << "assigning compressed pair 0" << endl; + _first = x._first; + _second = x._second; + cout << "finished assigning compressed pair 0" << endl; + return *this; + } +#endif + + first_reference first() { return _first; } + first_const_reference first() const { return _first; } + + second_reference second() { return _second; } + second_const_reference second() const { return _second; } + + void swap(compressed_pair_0& y) + { + using std::swap; + swap(_first, y._first); + swap(_second, y._second); + } +}; + +// T1 != T2, T2 empty +template <class T1, class T2> +class compressed_pair_1 : T2 +{ +private: + T1 _first; +public: + typedef T1 first_type; + typedef T2 second_type; + typedef typename call_traits<first_type>::param_type first_param_type; + typedef typename call_traits<second_type>::param_type second_param_type; + typedef typename call_traits<first_type>::reference first_reference; + typedef typename call_traits<second_type>::reference second_reference; + typedef typename call_traits<first_type>::const_reference first_const_reference; + typedef typename call_traits<second_type>::const_reference second_const_reference; + + compressed_pair_1() : T2(), _first() {} + compressed_pair_1(first_param_type x, second_param_type y) : T2(y), _first(x) {} + + template <class A> + explicit compressed_pair_1(const A& val) + { + init_one<best_conversion_traits<A, T1, T2>::value>::init(val, &_first, static_cast<T2*>(this)); + } + + compressed_pair_1(const ::boost::compressed_pair<T1,T2>& x) + : T2(x.second()), _first(x.first()) {} + +#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300 + // Total weirdness. If the assignment to _first is moved after + // the call to the inherited operator=, then this breaks graph/test/graph.cpp + // by way of iterator_adaptor. + compressed_pair_1& operator=(const compressed_pair_1& x) { + _first = x._first; + T2::operator=(x); + return *this; + } +#endif + + first_reference first() { return _first; } + first_const_reference first() const { return _first; } + + second_reference second() { return *this; } + second_const_reference second() const { return *this; } + + void swap(compressed_pair_1& y) + { + // no need to swap empty base class: + using std::swap; + swap(_first, y._first); + } +}; + +// T1 != T2, T1 empty +template <class T1, class T2> +class compressed_pair_2 : T1 +{ +private: + T2 _second; +public: + typedef T1 first_type; + typedef T2 second_type; + typedef typename call_traits<first_type>::param_type first_param_type; + typedef typename call_traits<second_type>::param_type second_param_type; + typedef typename call_traits<first_type>::reference first_reference; + typedef typename call_traits<second_type>::reference second_reference; + typedef typename call_traits<first_type>::const_reference first_const_reference; + typedef typename call_traits<second_type>::const_reference second_const_reference; + + compressed_pair_2() : T1(), _second() {} + compressed_pair_2(first_param_type x, second_param_type y) : T1(x), _second(y) {} + template <class A> + explicit compressed_pair_2(const A& val) + { + init_one<best_conversion_traits<A, T1, T2>::value>::init(val, static_cast<T1*>(this), &_second); + } + compressed_pair_2(const ::boost::compressed_pair<T1,T2>& x) + : T1(x.first()), _second(x.second()) {} + +#if 0 + compressed_pair_2& operator=(const compressed_pair_2& x) { + cout << "assigning compressed pair 2" << endl; + T1::operator=(x); + _second = x._second; + cout << "finished assigning compressed pair 2" << endl; + return *this; + } +#endif + first_reference first() { return *this; } + first_const_reference first() const { return *this; } + + second_reference second() { return _second; } + second_const_reference second() const { return _second; } + + void swap(compressed_pair_2& y) + { + // no need to swap empty base class: + using std::swap; + swap(_second, y._second); + } +}; + +// T1 != T2, both empty +template <class T1, class T2> +class compressed_pair_3 : T1, T2 +{ +public: + typedef T1 first_type; + typedef T2 second_type; + typedef typename call_traits<first_type>::param_type first_param_type; + typedef typename call_traits<second_type>::param_type second_param_type; + typedef typename call_traits<first_type>::reference first_reference; + typedef typename call_traits<second_type>::reference second_reference; + typedef typename call_traits<first_type>::const_reference first_const_reference; + typedef typename call_traits<second_type>::const_reference second_const_reference; + + compressed_pair_3() : T1(), T2() {} + compressed_pair_3(first_param_type x, second_param_type y) : T1(x), T2(y) {} + template <class A> + explicit compressed_pair_3(const A& val) + { + init_one<best_conversion_traits<A, T1, T2>::value>::init(val, static_cast<T1*>(this), static_cast<T2*>(this)); + } + compressed_pair_3(const ::boost::compressed_pair<T1,T2>& x) + : T1(x.first()), T2(x.second()) {} + + first_reference first() { return *this; } + first_const_reference first() const { return *this; } + + second_reference second() { return *this; } + second_const_reference second() const { return *this; } + + void swap(compressed_pair_3& y) + { + // no need to swap empty base classes: + } +}; + +// T1 == T2, and empty +template <class T1, class T2> +class compressed_pair_4 : T1 +{ +public: + typedef T1 first_type; + typedef T2 second_type; + typedef typename call_traits<first_type>::param_type first_param_type; + typedef typename call_traits<second_type>::param_type second_param_type; + typedef typename call_traits<first_type>::reference first_reference; + typedef typename call_traits<second_type>::reference second_reference; + typedef typename call_traits<first_type>::const_reference first_const_reference; + typedef typename call_traits<second_type>::const_reference second_const_reference; + + compressed_pair_4() : T1() {} + compressed_pair_4(first_param_type x, second_param_type y) : T1(x), m_second(y) {} + // only one single argument constructor since T1 == T2 + explicit compressed_pair_4(first_param_type x) : T1(x), m_second(x) {} + compressed_pair_4(const ::boost::compressed_pair<T1,T2>& x) + : T1(x.first()), m_second(x.second()) {} + + first_reference first() { return *this; } + first_const_reference first() const { return *this; } + + second_reference second() { return m_second; } + second_const_reference second() const { return m_second; } + + void swap(compressed_pair_4& y) + { + // no need to swap empty base classes: + } +private: + T2 m_second; +}; + +// T1 == T2, not empty +template <class T1, class T2> +class compressed_pair_5 +{ +private: + T1 _first; + T2 _second; +public: + typedef T1 first_type; + typedef T2 second_type; + typedef typename call_traits<first_type>::param_type first_param_type; + typedef typename call_traits<second_type>::param_type second_param_type; + typedef typename call_traits<first_type>::reference first_reference; + typedef typename call_traits<second_type>::reference second_reference; + typedef typename call_traits<first_type>::const_reference first_const_reference; + typedef typename call_traits<second_type>::const_reference second_const_reference; + + compressed_pair_5() : _first(), _second() {} + compressed_pair_5(first_param_type x, second_param_type y) : _first(x), _second(y) {} + // only one single argument constructor since T1 == T2 + explicit compressed_pair_5(first_param_type x) : _first(x), _second(x) {} + compressed_pair_5(const ::boost::compressed_pair<T1,T2>& c) + : _first(c.first()), _second(c.second()) {} + + first_reference first() { return _first; } + first_const_reference first() const { return _first; } + + second_reference second() { return _second; } + second_const_reference second() const { return _second; } + + void swap(compressed_pair_5& y) + { + using std::swap; + swap(_first, y._first); + swap(_second, y._second); + } +}; + +template <bool e1, bool e2, bool same> +struct compressed_pair_chooser +{ + template <class T1, class T2> + struct rebind + { + typedef compressed_pair_0<T1, T2> type; + }; +}; + +template <> +struct compressed_pair_chooser<false, true, false> +{ + template <class T1, class T2> + struct rebind + { + typedef compressed_pair_1<T1, T2> type; + }; +}; + +template <> +struct compressed_pair_chooser<true, false, false> +{ + template <class T1, class T2> + struct rebind + { + typedef compressed_pair_2<T1, T2> type; + }; +}; + +template <> +struct compressed_pair_chooser<true, true, false> +{ + template <class T1, class T2> + struct rebind + { + typedef compressed_pair_3<T1, T2> type; + }; +}; + +template <> +struct compressed_pair_chooser<true, true, true> +{ + template <class T1, class T2> + struct rebind + { + typedef compressed_pair_4<T1, T2> type; + }; +}; + +template <> +struct compressed_pair_chooser<false, false, true> +{ + template <class T1, class T2> + struct rebind + { + typedef compressed_pair_5<T1, T2> type; + }; +}; + +template <class T1, class T2> +struct compressed_pair_traits +{ +private: + typedef compressed_pair_chooser<is_empty<T1>::value, is_empty<T2>::value, is_same<T1,T2>::value> chooser; + typedef typename chooser::template rebind<T1, T2> bound_type; +public: + typedef typename bound_type::type type; +}; + +} // namespace detail + +template <class T1, class T2> +class compressed_pair : public detail::compressed_pair_traits<T1, T2>::type +{ +private: + typedef typename detail::compressed_pair_traits<T1, T2>::type base_type; +public: + typedef T1 first_type; + typedef T2 second_type; + typedef typename call_traits<first_type>::param_type first_param_type; + typedef typename call_traits<second_type>::param_type second_param_type; + typedef typename call_traits<first_type>::reference first_reference; + typedef typename call_traits<second_type>::reference second_reference; + typedef typename call_traits<first_type>::const_reference first_const_reference; + typedef typename call_traits<second_type>::const_reference second_const_reference; + + compressed_pair() : base_type() {} + compressed_pair(first_param_type x, second_param_type y) : base_type(x, y) {} + template <class A> + explicit compressed_pair(const A& x) : base_type(x){} + + first_reference first() { return base_type::first(); } + first_const_reference first() const { return base_type::first(); } + + second_reference second() { return base_type::second(); } + second_const_reference second() const { return base_type::second(); } +}; + +template <class T1, class T2> +inline void swap(compressed_pair<T1, T2>& x, compressed_pair<T1, T2>& y) +{ + x.swap(y); +} + +#else +// no partial specialisation, no member templates: + +template <class T1, class T2> +class compressed_pair +{ +private: + T1 _first; + T2 _second; +public: + typedef T1 first_type; + typedef T2 second_type; + typedef typename call_traits<first_type>::param_type first_param_type; + typedef typename call_traits<second_type>::param_type second_param_type; + typedef typename call_traits<first_type>::reference first_reference; + typedef typename call_traits<second_type>::reference second_reference; + typedef typename call_traits<first_type>::const_reference first_const_reference; + typedef typename call_traits<second_type>::const_reference second_const_reference; + + compressed_pair() : _first(), _second() {} + compressed_pair(first_param_type x, second_param_type y) : _first(x), _second(y) {} + explicit compressed_pair(first_param_type x) : _first(x), _second() {} + // can't define this in case T1 == T2: + // explicit compressed_pair(second_param_type y) : _first(), _second(y) {} + + first_reference first() { return _first; } + first_const_reference first() const { return _first; } + + second_reference second() { return _second; } + second_const_reference second() const { return _second; } + + void swap(compressed_pair& y) + { + using std::swap; + swap(_first, y._first); + swap(_second, y._second); + } +}; + +template <class T1, class T2> +inline void swap(compressed_pair<T1, T2>& x, compressed_pair<T1, T2>& y) +{ + x.swap(y); +} + +#endif + +} // boost + +#endif // BOOST_OB_COMPRESSED_PAIR_HPP + + + diff --git a/3rdParty/Boost/src/boost/functional/hash_fwd.hpp b/3rdParty/Boost/src/boost/functional/hash_fwd.hpp new file mode 100644 index 0000000..b640988 --- /dev/null +++ b/3rdParty/Boost/src/boost/functional/hash_fwd.hpp @@ -0,0 +1,7 @@ + +// Copyright 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) + +#include <boost/functional/hash/hash_fwd.hpp> + diff --git a/3rdParty/Boost/src/boost/type_traits/object_traits.hpp b/3rdParty/Boost/src/boost/type_traits/object_traits.hpp new file mode 100644 index 0000000..c812a62 --- /dev/null +++ b/3rdParty/Boost/src/boost/type_traits/object_traits.hpp @@ -0,0 +1,33 @@ +// (C) Copyright Steve Cleary, Beman Dawes, Howard Hinnant & John Maddock 2000. +// Use, modification and distribution are subject to 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/type_traits for most recent version including documentation. +// +// defines object traits classes: +// is_object, is_scalar, is_class, is_compound, is_pod, +// has_trivial_constructor, has_trivial_copy, has_trivial_assign, +// has_trivial_destructor, is_empty. +// + +#ifndef BOOST_TT_OBJECT_TRAITS_HPP_INLCUDED +#define BOOST_TT_OBJECT_TRAITS_HPP_INLCUDED + +#include <boost/type_traits/has_trivial_assign.hpp> +#include <boost/type_traits/has_trivial_constructor.hpp> +#include <boost/type_traits/has_trivial_copy.hpp> +#include <boost/type_traits/has_trivial_destructor.hpp> +#include <boost/type_traits/has_nothrow_constructor.hpp> +#include <boost/type_traits/has_nothrow_copy.hpp> +#include <boost/type_traits/has_nothrow_assign.hpp> +#include <boost/type_traits/is_base_and_derived.hpp> +#include <boost/type_traits/is_class.hpp> +#include <boost/type_traits/is_compound.hpp> +#include <boost/type_traits/is_empty.hpp> +#include <boost/type_traits/is_object.hpp> +#include <boost/type_traits/is_pod.hpp> +#include <boost/type_traits/is_scalar.hpp> +#include <boost/type_traits/is_stateless.hpp> + +#endif // BOOST_TT_OBJECT_TRAITS_HPP_INLCUDED diff --git a/3rdParty/Boost/src/boost/type_traits/same_traits.hpp b/3rdParty/Boost/src/boost/type_traits/same_traits.hpp new file mode 100644 index 0000000..dab7dac --- /dev/null +++ b/3rdParty/Boost/src/boost/type_traits/same_traits.hpp @@ -0,0 +1,15 @@ +// (C) Copyright Steve Cleary, Beman Dawes, Aleksey Gurtovoy, Howard Hinnant & John Maddock 2000. +// Use, modification and distribution are subject to 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/type_traits for most recent version including documentation. +// +// defines is_same: + +#ifndef BOOST_TT_SAME_TRAITS_HPP_INCLUDED +#define BOOST_TT_SAME_TRAITS_HPP_INCLUDED + +#include <boost/type_traits/is_same.hpp> + +#endif // BOOST_TT_SAME_TRAITS_HPP_INCLUDED diff --git a/3rdParty/Boost/src/boost/unordered/detail/allocator_helpers.hpp b/3rdParty/Boost/src/boost/unordered/detail/allocator_helpers.hpp new file mode 100644 index 0000000..2c64223 --- /dev/null +++ b/3rdParty/Boost/src/boost/unordered/detail/allocator_helpers.hpp @@ -0,0 +1,111 @@ + +// Copyright 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) + +// A couple of templates to make using allocators easier. + +#ifndef BOOST_UNORDERED_DETAIL_ALLOCATOR_UTILITIES_HPP_INCLUDED +#define BOOST_UNORDERED_DETAIL_ALLOCATOR_UTILITIES_HPP_INCLUDED + +#if defined(_MSC_VER) && (_MSC_VER >= 1020) +# pragma once +#endif + +#include <boost/config.hpp> + +#if (defined(BOOST_NO_STD_ALLOCATOR) || defined(BOOST_DINKUMWARE_STDLIB)) \ + && !defined(__BORLANDC__) +# define BOOST_UNORDERED_USE_ALLOCATOR_UTILITIES +#endif + +#if defined(BOOST_UNORDERED_USE_ALLOCATOR_UTILITIES) +# include <boost/detail/allocator_utilities.hpp> +#endif + +namespace boost { namespace unordered_detail { + + // rebind_wrap + // + // Rebind allocators. For some problematic libraries, use rebind_to + // from <boost/detail/allocator_utilities.hpp>. + +#if defined(BOOST_UNORDERED_USE_ALLOCATOR_UTILITIES) + template <class Alloc, class T> + struct rebind_wrap : ::boost::detail::allocator::rebind_to<Alloc, T> {}; +#else + template <class Alloc, class T> + struct rebind_wrap + { + typedef BOOST_DEDUCED_TYPENAME + Alloc::BOOST_NESTED_TEMPLATE rebind<T>::other + type; + }; +#endif + + // allocator_array_constructor + // + // Allocate and construct an array in an exception safe manner, and + // clean up if an exception is thrown before the container takes charge + // of it. + + template <class Allocator> + struct allocator_array_constructor + { + typedef BOOST_DEDUCED_TYPENAME Allocator::pointer pointer; + + Allocator& alloc_; + pointer ptr_; + pointer constructed_; + std::size_t length_; + + allocator_array_constructor(Allocator& a) + : alloc_(a), ptr_(), constructed_(), length_(0) + { + constructed_ = pointer(); + ptr_ = pointer(); + } + + ~allocator_array_constructor() { + if (ptr_) { + for(pointer p = ptr_; p != constructed_; ++p) + alloc_.destroy(p); + + alloc_.deallocate(ptr_, length_); + } + } + + template <class V> + void construct(V const& v, std::size_t l) + { + BOOST_ASSERT(!ptr_); + length_ = l; + ptr_ = alloc_.allocate(length_); + pointer end = ptr_ + static_cast<std::ptrdiff_t>(length_); + for(constructed_ = ptr_; constructed_ != end; ++constructed_) + alloc_.construct(constructed_, v); + } + + pointer get() const + { + return ptr_; + } + + pointer release() + { + pointer p(ptr_); + ptr_ = pointer(); + return p; + } + private: + allocator_array_constructor(allocator_array_constructor const&); + allocator_array_constructor& operator=( + allocator_array_constructor const&); + }; +}} + +#if defined(BOOST_UNORDERED_USE_ALLOCATOR_UTILITIES) +# undef BOOST_UNORDERED_USE_ALLOCATOR_UTILITIES +#endif + +#endif diff --git a/3rdParty/Boost/src/boost/unordered/detail/buckets.hpp b/3rdParty/Boost/src/boost/unordered/detail/buckets.hpp new file mode 100644 index 0000000..b1dee5c --- /dev/null +++ b/3rdParty/Boost/src/boost/unordered/detail/buckets.hpp @@ -0,0 +1,183 @@ + +// 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) + +#ifndef BOOST_UNORDERED_DETAIL_MANAGER_HPP_INCLUDED +#define BOOST_UNORDERED_DETAIL_MANAGER_HPP_INCLUDED + +#include <boost/config.hpp> +#include <boost/assert.hpp> +#include <boost/unordered/detail/node.hpp> +#include <boost/unordered/detail/util.hpp> + +namespace boost { namespace unordered_detail { + + //////////////////////////////////////////////////////////////////////////// + // Buckets + + template <class A, class G> + inline std::size_t hash_buckets<A, G>::max_bucket_count() const { + // -1 to account for the sentinel. + return prev_prime(this->bucket_alloc().max_size() - 1); + } + + template <class A, class G> + inline BOOST_DEDUCED_TYPENAME hash_buckets<A, G>::bucket_ptr + hash_buckets<A, G>::get_bucket(std::size_t num) const + { + return buckets_ + static_cast<std::ptrdiff_t>(num); + } + + template <class A, class G> + inline BOOST_DEDUCED_TYPENAME hash_buckets<A, G>::bucket_ptr + hash_buckets<A, G>::bucket_ptr_from_hash(std::size_t hashed) const + { + return get_bucket(hashed % bucket_count_); + } + + template <class A, class G> + std::size_t hash_buckets<A, G>::bucket_size(std::size_t index) const + { + if(!buckets_) return 0; + bucket_ptr ptr = get_bucket(index)->next_; + std::size_t count = 0; + while(ptr) { + ++count; + ptr = ptr->next_; + } + return count; + } + + template <class A, class G> + inline BOOST_DEDUCED_TYPENAME hash_buckets<A, G>::node_ptr + hash_buckets<A, G>::bucket_begin(std::size_t num) const + { + return buckets_ ? get_bucket(num)->next_ : node_ptr(); + } + + //////////////////////////////////////////////////////////////////////////// + // Delete + + template <class A, class G> + inline void hash_buckets<A, G>::delete_node(node_ptr b) + { + node* raw_ptr = static_cast<node*>(&*b); + boost::unordered_detail::destroy(&raw_ptr->value()); + real_node_ptr n(node_alloc().address(*raw_ptr)); + node_alloc().destroy(n); + node_alloc().deallocate(n, 1); + } + + template <class A, class G> + inline void hash_buckets<A, G>::clear_bucket(bucket_ptr b) + { + node_ptr node_it = b->next_; + b->next_ = node_ptr(); + + while(node_it) { + node_ptr node_to_delete = node_it; + node_it = node_it->next_; + delete_node(node_to_delete); + } + } + + template <class A, class G> + inline void hash_buckets<A, G>::delete_buckets() + { + bucket_ptr end = this->get_bucket(this->bucket_count_); + + for(bucket_ptr begin = this->buckets_; begin != end; ++begin) { + clear_bucket(begin); + } + + // Destroy the buckets (including the sentinel bucket). + ++end; + for(bucket_ptr begin = this->buckets_; begin != end; ++begin) { + bucket_alloc().destroy(begin); + } + + bucket_alloc().deallocate(this->buckets_, this->bucket_count_ + 1); + + this->buckets_ = bucket_ptr(); + } + + template <class A, class G> + inline std::size_t hash_buckets<A, G>::delete_nodes( + node_ptr begin, node_ptr end) + { + std::size_t count = 0; + while(begin != end) { + node_ptr n = begin; + begin = begin->next_; + delete_node(n); + ++count; + } + return count; + } + + //////////////////////////////////////////////////////////////////////////// + // Constructors and Destructors + + template <class A, class G> + inline hash_buckets<A, G>::hash_buckets( + node_allocator const& a, std::size_t bucket_count) + : buckets_(), + bucket_count_(bucket_count), + allocators_(a,a) + { + } + + template <class A, class G> + inline hash_buckets<A, G>::~hash_buckets() + { + if(this->buckets_) { this->delete_buckets(); } + } + + template <class A, class G> + inline void hash_buckets<A, G>::create_buckets() + { + // The array constructor will clean up in the event of an + // exception. + allocator_array_constructor<bucket_allocator> + constructor(bucket_alloc()); + + // Creates an extra bucket to act as a sentinel. + constructor.construct(bucket(), this->bucket_count_ + 1); + + // Set up the sentinel (node_ptr cast) + bucket_ptr sentinel = constructor.get() + + static_cast<std::ptrdiff_t>(this->bucket_count_); + sentinel->next_ = sentinel; + + // Only release the buckets once everything is successfully + // done. + this->buckets_ = constructor.release(); + } + + //////////////////////////////////////////////////////////////////////////// + // Constructors and Destructors + + // no throw + template <class A, class G> + inline void hash_buckets<A, G>::move(hash_buckets& other) + { + BOOST_ASSERT(node_alloc() == other.node_alloc()); + if(this->buckets_) { this->delete_buckets(); } + this->buckets_ = other.buckets_; + this->bucket_count_ = other.bucket_count_; + other.buckets_ = bucket_ptr(); + other.bucket_count_ = 0; + } + + template <class A, class G> + inline void hash_buckets<A, G>::swap(hash_buckets<A, G>& other) + { + BOOST_ASSERT(node_alloc() == other.node_alloc()); + std::swap(buckets_, other.buckets_); + std::swap(bucket_count_, other.bucket_count_); + } +}} + +#endif diff --git a/3rdParty/Boost/src/boost/unordered/detail/equivalent.hpp b/3rdParty/Boost/src/boost/unordered/detail/equivalent.hpp new file mode 100644 index 0000000..1c497c3 --- /dev/null +++ b/3rdParty/Boost/src/boost/unordered/detail/equivalent.hpp @@ -0,0 +1,304 @@ + +// 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) + +#ifndef BOOST_UNORDERED_DETAIL_EQUIVALENT_HPP_INCLUDED +#define BOOST_UNORDERED_DETAIL_EQUIVALENT_HPP_INCLUDED + +#include <boost/unordered/detail/table.hpp> +#include <boost/unordered/detail/extract_key.hpp> + +namespace boost { namespace unordered_detail { + + template <class T> + class hash_equivalent_table : public T::table + { + public: + typedef BOOST_DEDUCED_TYPENAME T::hasher hasher; + typedef BOOST_DEDUCED_TYPENAME T::key_equal key_equal; + typedef BOOST_DEDUCED_TYPENAME T::value_allocator value_allocator; + typedef BOOST_DEDUCED_TYPENAME T::key_type key_type; + typedef BOOST_DEDUCED_TYPENAME T::value_type value_type; + typedef BOOST_DEDUCED_TYPENAME T::table table; + typedef BOOST_DEDUCED_TYPENAME T::node_constructor node_constructor; + + typedef BOOST_DEDUCED_TYPENAME T::node node; + typedef BOOST_DEDUCED_TYPENAME T::node_ptr node_ptr; + typedef BOOST_DEDUCED_TYPENAME T::bucket_ptr bucket_ptr; + typedef BOOST_DEDUCED_TYPENAME T::iterator_base iterator_base; + typedef BOOST_DEDUCED_TYPENAME T::extractor extractor; + + // Constructors + + hash_equivalent_table(std::size_t n, + hasher const& hf, key_equal const& eq, value_allocator const& a) + : table(n, hf, eq, a) {} + hash_equivalent_table(hash_equivalent_table const& x) + : table(x, x.node_alloc()) {} + hash_equivalent_table(hash_equivalent_table const& x, + value_allocator const& a) + : table(x, a) {} + hash_equivalent_table(hash_equivalent_table& x, move_tag m) + : table(x, m) {} + hash_equivalent_table(hash_equivalent_table& x, + value_allocator const& a, move_tag m) + : table(x, a, m) {} + ~hash_equivalent_table() {} + + // Insert methods + + iterator_base emplace_impl(node_constructor& a); + void emplace_impl_no_rehash(node_constructor& a); + + // equals + + bool equals(hash_equivalent_table const&) const; + + inline node_ptr add_node(node_constructor& a, + bucket_ptr bucket, node_ptr pos); + +#if defined(BOOST_UNORDERED_STD_FORWARD) + + template <class... Args> + iterator_base emplace(Args&&... args); + +#else + +#define BOOST_UNORDERED_INSERT_IMPL(z, n, _) \ + template <BOOST_UNORDERED_TEMPLATE_ARGS(z, n)> \ + iterator_base emplace(BOOST_UNORDERED_FUNCTION_PARAMS(z, n)); + + BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT, + BOOST_UNORDERED_INSERT_IMPL, _) + +#undef BOOST_UNORDERED_INSERT_IMPL +#endif + + template <class I> + void insert_for_range(I i, I j, forward_traversal_tag); + template <class I> + void insert_for_range(I i, I j, boost::incrementable_traversal_tag); + template <class I> + void insert_range(I i, I j); + }; + + template <class H, class P, class A> + struct multiset : public types< + BOOST_DEDUCED_TYPENAME A::value_type, + BOOST_DEDUCED_TYPENAME A::value_type, + H, P, A, + set_extractor<BOOST_DEDUCED_TYPENAME A::value_type>, + grouped> + { + typedef hash_equivalent_table<multiset<H, P, A> > impl; + typedef hash_table<multiset<H, P, A> > table; + }; + + template <class K, class H, class P, class A> + struct multimap : public types< + K, BOOST_DEDUCED_TYPENAME A::value_type, + H, P, A, + map_extractor<K, BOOST_DEDUCED_TYPENAME A::value_type>, + grouped> + { + typedef hash_equivalent_table<multimap<K, H, P, A> > impl; + typedef hash_table<multimap<K, H, P, A> > table; + }; + + //////////////////////////////////////////////////////////////////////////// + // Equality + + template <class T> + bool hash_equivalent_table<T> + ::equals(hash_equivalent_table<T> const& other) const + { + if(this->size_ != other.size_) return false; + if(!this->size_) return true; + + bucket_ptr end = this->get_bucket(this->bucket_count_); + for(bucket_ptr i = this->cached_begin_bucket_; i != end; ++i) + { + node_ptr it1 = i->next_; + while(BOOST_UNORDERED_BORLAND_BOOL(it1)) + { + node_ptr it2 = other.find_iterator(this->get_key_from_ptr(it1)); + if(!BOOST_UNORDERED_BORLAND_BOOL(it2)) return false; + + node_ptr end1 = node::next_group(it1); + node_ptr end2 = node::next_group(it2); + + do { + if(!extractor::compare_mapped( + node::get_value(it1), node::get_value(it2))) + return false; + it1 = it1->next_; + it2 = it2->next_; + } while(it1 != end1 && it2 != end2); + if(it1 != end1 || it2 != end2) return false; + } + } + + return true; + } + + //////////////////////////////////////////////////////////////////////////// + // A convenience method for adding nodes. + + template <class T> + inline BOOST_DEDUCED_TYPENAME hash_equivalent_table<T>::node_ptr + hash_equivalent_table<T> + ::add_node(node_constructor& a, bucket_ptr bucket, node_ptr pos) + { + node_ptr n = a.release(); + if(BOOST_UNORDERED_BORLAND_BOOL(pos)) { + node::add_after_node(n, pos); + } + else { + node::add_to_bucket(n, *bucket); + if(bucket < this->cached_begin_bucket_) + this->cached_begin_bucket_ = bucket; + } + ++this->size_; + return n; + } + + //////////////////////////////////////////////////////////////////////////// + // Insert methods + + template <class T> + inline BOOST_DEDUCED_TYPENAME + hash_equivalent_table<T>::iterator_base + hash_equivalent_table<T>::emplace_impl(node_constructor& a) + { + key_type const& k = this->get_key(a.value()); + std::size_t hash_value = this->hash_function()(k); + + if(!this->size_) { + return this->emplace_empty_impl_with_node(a, 1); + } + else { + bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value); + node_ptr position = this->find_iterator(bucket, k); + + // reserve has basic exception safety if the hash function + // throws, strong otherwise. + if(this->reserve_for_insert(this->size_ + 1)) + bucket = this->bucket_ptr_from_hash(hash_value); + + return iterator_base(bucket, add_node(a, bucket, position)); + } + } + + template <class T> + inline void hash_equivalent_table<T> + ::emplace_impl_no_rehash(node_constructor& a) + { + key_type const& k = this->get_key(a.value()); + bucket_ptr bucket = this->get_bucket(this->bucket_index(k)); + add_node(a, bucket, this->find_iterator(bucket, k)); + } + +#if defined(BOOST_UNORDERED_STD_FORWARD) + + // Emplace (equivalent key containers) + // (I'm using an overloaded emplace for both 'insert' and 'emplace') + + // if hash function throws, basic exception safety + // strong otherwise + template <class T> + template <class... Args> + BOOST_DEDUCED_TYPENAME hash_equivalent_table<T>::iterator_base + hash_equivalent_table<T> + ::emplace(Args&&... args) + { + // Create the node before rehashing in case it throws an + // exception (need strong safety in such a case). + node_constructor a(*this); + a.construct(std::forward<Args>(args)...); + + return emplace_impl(a); + } + +#else + +#define BOOST_UNORDERED_INSERT_IMPL(z, num_params, _) \ + template <class T> \ + template <BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params)> \ + BOOST_DEDUCED_TYPENAME hash_equivalent_table<T>::iterator_base \ + hash_equivalent_table<T> \ + ::emplace(BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params)) \ + { \ + node_constructor a(*this); \ + a.construct(BOOST_UNORDERED_CALL_PARAMS(z, num_params)); \ + return emplace_impl(a); \ + } + + BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT, + BOOST_UNORDERED_INSERT_IMPL, _) + +#undef BOOST_UNORDERED_INSERT_IMPL +#endif + + //////////////////////////////////////////////////////////////////////////// + // Insert range methods + + // if hash function throws, or inserting > 1 element, basic exception safety + // strong otherwise + template <class T> + template <class I> + inline void hash_equivalent_table<T> + ::insert_for_range(I i, I j, forward_traversal_tag) + { + if(i == j) return; + std::size_t distance = unordered_detail::distance(i, j); + if(distance == 1) { + emplace(*i); + } + else { + node_constructor a(*this); + + // Only require basic exception safety here + if(this->size_) { + this->reserve_for_insert(this->size_ + distance); + } + else { + a.construct(*i++); + this->emplace_empty_impl_with_node(a, distance); + } + + for (; i != j; ++i) { + a.construct(*i); + emplace_impl_no_rehash(a); + } + } + } + + // if hash function throws, or inserting > 1 element, basic exception safety + // strong otherwise + template <class T> + template <class I> + inline void hash_equivalent_table<T> + ::insert_for_range(I i, I j, boost::incrementable_traversal_tag) + { + node_constructor a(*this); + for (; i != j; ++i) { + a.construct(*i); + emplace_impl(a); + } + } + + // if hash function throws, or inserting > 1 element, basic exception safety + // strong otherwise + template <class T> + template <class I> + void hash_equivalent_table<T>::insert_range(I i, I j) + { + BOOST_DEDUCED_TYPENAME boost::iterator_traversal<I>::type + iterator_traversal_tag; + insert_for_range(i, j, iterator_traversal_tag); + } +}} + +#endif diff --git a/3rdParty/Boost/src/boost/unordered/detail/extract_key.hpp b/3rdParty/Boost/src/boost/unordered/detail/extract_key.hpp new file mode 100644 index 0000000..bedb175 --- /dev/null +++ b/3rdParty/Boost/src/boost/unordered/detail/extract_key.hpp @@ -0,0 +1,148 @@ + +// 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) + +#ifndef BOOST_UNORDERED_DETAIL_EXTRACT_KEY_HPP_INCLUDED +#define BOOST_UNORDERED_DETAIL_EXTRACT_KEY_HPP_INCLUDED + +#include <boost/config.hpp> +#include <boost/type_traits/remove_const.hpp> +#include <boost/unordered/detail/fwd.hpp> + +namespace boost { +namespace unordered_detail { + + // key extractors + // + // no throw + // + // 'extract_key' is called with the emplace parameters to return a + // key if available or 'no_key' is one isn't and will need to be + // constructed. This could be done by overloading the emplace implementation + // for the different cases, but that's a bit tricky on compilers without + // variadic templates. + + struct no_key { + no_key() {} + template <class T> no_key(T const&) {} + }; + + template <class ValueType> + struct set_extractor + { + typedef ValueType value_type; + typedef ValueType key_type; + + static key_type const& extract(key_type const& v) + { + return v; + } + + static no_key extract() + { + return no_key(); + } + +#if defined(BOOST_UNORDERED_STD_FORWARD) + template <class... Args> + static no_key extract(Args const&...) + { + return no_key(); + } + +#else + template <class Arg> + static no_key extract(Arg const&) + { + return no_key(); + } + + template <class Arg> + static no_key extract(Arg const&, Arg const&) + { + return no_key(); + } +#endif + + static bool compare_mapped(value_type const&, value_type const&) + { + return true; + } + }; + + template <class Key, class ValueType> + struct map_extractor + { + typedef ValueType value_type; + typedef BOOST_DEDUCED_TYPENAME boost::remove_const<Key>::type key_type; + + static key_type const& extract(value_type const& v) + { + return v.first; + } + + static key_type const& extract(key_type const& v) + { + return v; + } + + template <class Second> + static key_type const& extract(std::pair<key_type, Second> const& v) + { + return v.first; + } + + template <class Second> + static key_type const& extract( + std::pair<key_type const, Second> const& v) + { + return v.first; + } + +#if defined(BOOST_UNORDERED_STD_FORWARD) + template <class Arg1, class... Args> + static key_type const& extract(key_type const& k, + Arg1 const&, Args const&...) + { + return k; + } + + template <class... Args> + static no_key extract(Args const&...) + { + return no_key(); + } +#else + template <class Arg1> + static key_type const& extract(key_type const& k, Arg1 const&) + { + return k; + } + + static no_key extract() + { + return no_key(); + } + + template <class Arg> + static no_key extract(Arg const&) + { + return no_key(); + } + + template <class Arg, class Arg1> + static no_key extract(Arg const&, Arg1 const&) + { + return no_key(); + } +#endif + + static bool compare_mapped(value_type const& x, value_type const& y) + { + return x.second == y.second; + } + }; +}} + +#endif diff --git a/3rdParty/Boost/src/boost/unordered/detail/fwd.hpp b/3rdParty/Boost/src/boost/unordered/detail/fwd.hpp new file mode 100644 index 0000000..be4d5e1 --- /dev/null +++ b/3rdParty/Boost/src/boost/unordered/detail/fwd.hpp @@ -0,0 +1,856 @@ + +// 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_FWD_HPP_INCLUDED +#define BOOST_UNORDERED_DETAIL_FWD_HPP_INCLUDED + +#include <boost/config.hpp> +#include <boost/iterator.hpp> +#include <boost/compressed_pair.hpp> +#include <boost/type_traits/aligned_storage.hpp> +#include <boost/type_traits/alignment_of.hpp> +#include <boost/unordered/detail/allocator_helpers.hpp> +#include <algorithm> + +// This header defines most of the classes used to implement the unordered +// containers. It doesn't include the insert methods as they require a lot +// of preprocessor metaprogramming - they are in insert.hpp + +// Template parameters: +// +// H = Hash Function +// P = Predicate +// A = Value Allocator +// G = Grouped/Ungrouped +// E = Key Extractor + +#if !defined(BOOST_NO_RVALUE_REFERENCES) && !defined(BOOST_NO_VARIADIC_TEMPLATES) +# if defined(__SGI_STL_PORT) || defined(_STLPORT_VERSION) + // STLport doesn't have std::forward. +# else +# define BOOST_UNORDERED_STD_FORWARD +# endif +#endif + +#if !defined(BOOST_UNORDERED_EMPLACE_LIMIT) +#define BOOST_UNORDERED_EMPLACE_LIMIT 10 +#endif + +#if !defined(BOOST_UNORDERED_STD_FORWARD) + +#include <boost/preprocessor/repetition/enum_params.hpp> +#include <boost/preprocessor/repetition/enum_binary_params.hpp> +#include <boost/preprocessor/repetition/repeat_from_to.hpp> + +#define BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params) \ + BOOST_PP_ENUM_PARAMS_Z(z, num_params, class Arg) +#define BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params) \ + BOOST_PP_ENUM_BINARY_PARAMS_Z(z, num_params, Arg, const& arg) +#define BOOST_UNORDERED_CALL_PARAMS(z, num_params) \ + BOOST_PP_ENUM_PARAMS_Z(z, num_params, arg) + +#endif + +namespace boost { namespace unordered_detail { + + static const float minimum_max_load_factor = 1e-3f; + static const std::size_t default_bucket_count = 11; + struct move_tag {}; + + template <class T> class hash_unique_table; + template <class T> class hash_equivalent_table; + template <class Alloc, class Grouped> + class hash_node_constructor; + template <class ValueType> + struct set_extractor; + template <class Key, class ValueType> + struct map_extractor; + struct no_key; + + // Explicitly call a destructor + +#if defined(BOOST_MSVC) +#pragma warning(push) +#pragma warning(disable:4100) // unreferenced formal parameter +#endif + + template <class T> + inline void destroy(T* x) { + x->~T(); + } + +#if defined(BOOST_MSVC) +#pragma warning(pop) +#endif + + // hash_bucket + + template <class A> + class hash_bucket + { + hash_bucket& operator=(hash_bucket const&); + public: + typedef hash_bucket<A> bucket; + typedef BOOST_DEDUCED_TYPENAME + boost::unordered_detail::rebind_wrap<A, bucket>::type + bucket_allocator; + typedef BOOST_DEDUCED_TYPENAME bucket_allocator::pointer bucket_ptr; + typedef bucket_ptr node_ptr; + + node_ptr next_; + + hash_bucket() : next_() {} + }; + + template <class A> + struct ungrouped_node_base : hash_bucket<A> { + typedef hash_bucket<A> bucket; + typedef BOOST_DEDUCED_TYPENAME bucket::bucket_ptr bucket_ptr; + typedef BOOST_DEDUCED_TYPENAME bucket::node_ptr node_ptr; + + ungrouped_node_base() : bucket() {} + static inline node_ptr& next_group(node_ptr ptr); + static inline std::size_t group_count(node_ptr ptr); + static inline void add_to_bucket(node_ptr n, bucket& b); + static inline void add_after_node(node_ptr n, node_ptr position); + static void unlink_node(bucket& b, node_ptr n); + static void unlink_nodes(bucket& b, node_ptr begin, node_ptr end); + static void unlink_nodes(bucket& b, node_ptr end); + }; + + template <class A> + struct grouped_node_base : hash_bucket<A> + { + typedef hash_bucket<A> bucket; + typedef BOOST_DEDUCED_TYPENAME bucket::bucket_ptr bucket_ptr; + typedef BOOST_DEDUCED_TYPENAME bucket::node_ptr node_ptr; + + node_ptr group_prev_; + + grouped_node_base() : bucket(), group_prev_() {} + static inline node_ptr& next_group(node_ptr ptr); + static inline node_ptr first_in_group(node_ptr n); + static inline std::size_t group_count(node_ptr ptr); + static inline void add_to_bucket(node_ptr n, bucket& b); + static inline void add_after_node(node_ptr n, node_ptr position); + static void unlink_node(bucket& b, node_ptr n); + static void unlink_nodes(bucket& b, node_ptr begin, node_ptr end); + static void unlink_nodes(bucket& b, node_ptr end); + + private: + static inline node_ptr split_group(node_ptr split); + static inline grouped_node_base& get(node_ptr ptr) { + return static_cast<grouped_node_base&>(*ptr); + } + }; + + struct ungrouped + { + template <class A> + struct base { + typedef ungrouped_node_base<A> type; + }; + }; + + struct grouped + { + template <class A> + struct base { + typedef grouped_node_base<A> type; + }; + }; + + template <class ValueType> + struct value_base + { + typedef ValueType value_type; + BOOST_DEDUCED_TYPENAME boost::aligned_storage< + sizeof(value_type), + ::boost::alignment_of<value_type>::value>::type data_; + + void* address() { + return this; + } + value_type& value() { + return *(ValueType*) this; + } + private: + value_base& operator=(value_base const&); + }; + + // Node + + template <class A, class G> + class hash_node : + public G::BOOST_NESTED_TEMPLATE base<A>::type, + public value_base<BOOST_DEDUCED_TYPENAME A::value_type> + { + public: + typedef BOOST_DEDUCED_TYPENAME A::value_type value_type; + typedef BOOST_DEDUCED_TYPENAME hash_bucket<A>::node_ptr node_ptr; + + static value_type& get_value(node_ptr p) { + return static_cast<hash_node&>(*p).value(); + } + private: + hash_node& operator=(hash_node const&); + }; + + // Iterator Base + + template <class A, class G> + class hash_iterator_base + { + public: + typedef A value_allocator; + typedef hash_bucket<A> bucket; + typedef hash_node<A, G> node; + typedef BOOST_DEDUCED_TYPENAME A::value_type value_type; + typedef BOOST_DEDUCED_TYPENAME bucket::bucket_ptr bucket_ptr; + typedef BOOST_DEDUCED_TYPENAME bucket::node_ptr node_ptr; + + bucket_ptr bucket_; + node_ptr node_; + + hash_iterator_base() : bucket_(), node_() {} + explicit hash_iterator_base(bucket_ptr b) + : bucket_(b), + node_(b ? b->next_ : node_ptr()) {} + hash_iterator_base(bucket_ptr b, node_ptr n) + : bucket_(b), + node_(n) {} + + bool operator==(hash_iterator_base const& x) const { + return node_ == x.node_; } + bool operator!=(hash_iterator_base const& x) const { + return node_ != x.node_; } + value_type& operator*() const { + return node::get_value(node_); + } + + void increment_bucket(node_ptr n) { + while(!n) { + ++bucket_; + n = bucket_->next_; + } + node_ = bucket_ == n ? node_ptr() : n; + } + + void increment() { + increment_bucket(node_->next_); + } + }; + + // hash_buckets + // + // This is responsible for allocating and deallocating buckets and nodes. + // + // Notes: + // 1. For the sake exception safety the allocators themselves don't allocate + // anything. + // 2. It's the callers responsibility to allocate the buckets before calling + // any of the methods (other than getters and setters). + + template <class A, class G> + class hash_buckets + { + hash_buckets(hash_buckets const&); + hash_buckets& operator=(hash_buckets const&); + public: + // Types + + typedef A value_allocator; + typedef hash_bucket<A> bucket; + typedef hash_iterator_base<A, G> iterator_base; + typedef BOOST_DEDUCED_TYPENAME A::value_type value_type; + typedef BOOST_DEDUCED_TYPENAME iterator_base::node node; + + typedef BOOST_DEDUCED_TYPENAME bucket::bucket_allocator + bucket_allocator; + typedef BOOST_DEDUCED_TYPENAME bucket::bucket_ptr bucket_ptr; + typedef BOOST_DEDUCED_TYPENAME bucket::node_ptr node_ptr; + + typedef BOOST_DEDUCED_TYPENAME rebind_wrap<value_allocator, node>::type + node_allocator; + typedef BOOST_DEDUCED_TYPENAME node_allocator::pointer real_node_ptr; + + // Members + + bucket_ptr buckets_; + std::size_t bucket_count_; + boost::compressed_pair<bucket_allocator, node_allocator> allocators_; + + // Data access + + bucket_allocator const& bucket_alloc() const { + return allocators_.first(); } + node_allocator const& node_alloc() const { + return allocators_.second(); } + bucket_allocator& bucket_alloc() { + return allocators_.first(); } + node_allocator& node_alloc() { + return allocators_.second(); } + std::size_t max_bucket_count() const; + + // Constructors + + hash_buckets(node_allocator const& a, std::size_t n); + void create_buckets(); + ~hash_buckets(); + + // no throw + void swap(hash_buckets& other); + void move(hash_buckets& other); + + // For the remaining functions, buckets_ must not be null. + + bucket_ptr get_bucket(std::size_t n) const; + bucket_ptr bucket_ptr_from_hash(std::size_t hashed) const; + std::size_t bucket_size(std::size_t index) const; + node_ptr bucket_begin(std::size_t n) const; + + // Alloc/Dealloc + + void delete_node(node_ptr); + + // + void delete_buckets(); + void clear_bucket(bucket_ptr); + std::size_t delete_nodes(node_ptr begin, node_ptr end); + std::size_t delete_to_bucket_end(node_ptr begin); + }; + + template <class H, class P> class set_hash_functions; + + template <class H, class P> + class hash_buffered_functions + { + friend class set_hash_functions<H, P>; + hash_buffered_functions& operator=(hash_buffered_functions const&); + + typedef boost::compressed_pair<H, P> function_pair; + typedef BOOST_DEDUCED_TYPENAME boost::aligned_storage< + sizeof(function_pair), + ::boost::alignment_of<function_pair>::value>::type aligned_function; + + bool current_; // The currently active functions. + aligned_function funcs_[2]; + + function_pair const& current() const { + return *static_cast<function_pair const*>( + static_cast<void const*>(&funcs_[current_])); + } + + void construct(bool which, H const& hf, P const& eq) + { + new((void*) &funcs_[which]) function_pair(hf, eq); + } + + void construct(bool which, function_pair const& f) + { + new((void*) &funcs_[which]) function_pair(f); + } + + void destroy(bool which) + { + boost::unordered_detail::destroy((function_pair*)(&funcs_[which])); + } + + public: + + hash_buffered_functions(H const& hf, P const& eq) + : current_(false) + { + construct(current_, hf, eq); + } + + hash_buffered_functions(hash_buffered_functions const& bf) + : current_(false) + { + construct(current_, bf.current()); + } + + ~hash_buffered_functions() { + destroy(current_); + } + + H const& hash_function() const { + return current().first(); + } + + P const& key_eq() const { + return current().second(); + } + }; + + template <class H, class P> + class set_hash_functions + { + set_hash_functions(set_hash_functions const&); + set_hash_functions& operator=(set_hash_functions const&); + + typedef hash_buffered_functions<H, P> buffered_functions; + buffered_functions& buffered_functions_; + bool tmp_functions_; + + public: + + set_hash_functions(buffered_functions& f, H const& h, P const& p) + : buffered_functions_(f), + tmp_functions_(!f.current_) + { + f.construct(tmp_functions_, h, p); + } + + set_hash_functions(buffered_functions& f, + buffered_functions const& other) + : buffered_functions_(f), + tmp_functions_(!f.current_) + { + f.construct(tmp_functions_, other.current()); + } + + ~set_hash_functions() + { + buffered_functions_.destroy(tmp_functions_); + } + + void commit() + { + buffered_functions_.current_ = tmp_functions_; + tmp_functions_ = !tmp_functions_; + } + }; + + template <class T> + class hash_table : public T::buckets, public T::buffered_functions + { + hash_table(hash_table const&); + public: + typedef BOOST_DEDUCED_TYPENAME T::hasher hasher; + typedef BOOST_DEDUCED_TYPENAME T::key_equal key_equal; + typedef BOOST_DEDUCED_TYPENAME T::value_allocator value_allocator; + typedef BOOST_DEDUCED_TYPENAME T::key_type key_type; + typedef BOOST_DEDUCED_TYPENAME T::value_type value_type; + typedef BOOST_DEDUCED_TYPENAME T::buffered_functions base; + typedef BOOST_DEDUCED_TYPENAME T::buckets buckets; + typedef BOOST_DEDUCED_TYPENAME T::extractor extractor; + typedef BOOST_DEDUCED_TYPENAME T::node_constructor node_constructor; + + typedef BOOST_DEDUCED_TYPENAME T::node node; + typedef BOOST_DEDUCED_TYPENAME T::bucket bucket; + typedef BOOST_DEDUCED_TYPENAME T::node_ptr node_ptr; + typedef BOOST_DEDUCED_TYPENAME T::bucket_ptr bucket_ptr; + typedef BOOST_DEDUCED_TYPENAME T::iterator_base iterator_base; + typedef BOOST_DEDUCED_TYPENAME T::node_allocator node_allocator; + typedef BOOST_DEDUCED_TYPENAME T::iterator_pair iterator_pair; + + // Members + + std::size_t size_; + float mlf_; + // Cached data - invalid if !this->buckets_ + bucket_ptr cached_begin_bucket_; + std::size_t max_load_; + + // Helper methods + + key_type const& get_key(value_type const& v) const { + return extractor::extract(v); + } + key_type const& get_key_from_ptr(node_ptr n) const { + return extractor::extract(node::get_value(n)); + } + bool equal(key_type const& k, value_type const& v) const; + template <class Key, class Pred> + node_ptr find_iterator(bucket_ptr bucket, Key const& k, + Pred const&) const; + node_ptr find_iterator(bucket_ptr bucket, key_type const& k) const; + node_ptr find_iterator(key_type const& k) const; + node_ptr* find_for_erase(bucket_ptr bucket, key_type const& k) const; + + // Load methods + + std::size_t max_size() const; + std::size_t bucket_index(key_type const& k) const; + void max_load_factor(float z); + std::size_t min_buckets_for_size(std::size_t n) const; + std::size_t calculate_max_load(); + + // Constructors + + hash_table(std::size_t n, hasher const& hf, key_equal const& eq, + node_allocator const& a); + hash_table(hash_table const& x, node_allocator const& a); + hash_table(hash_table& x, move_tag m); + hash_table(hash_table& x, node_allocator const& a, move_tag m); + ~hash_table() {} + hash_table& operator=(hash_table const&); + + // Iterators + + iterator_base begin() const { + return this->size_ ? + iterator_base(this->cached_begin_bucket_) : + iterator_base(); + } + iterator_base end() const { + return iterator_base(); + } + + // Swap & Move + + void swap(hash_table& x); + void fast_swap(hash_table& other); + void slow_swap(hash_table& other); + void partial_swap(hash_table& other); + void move(hash_table& x); + + // Reserve and rehash + + void create_for_insert(std::size_t n); + bool reserve_for_insert(std::size_t n); + void rehash(std::size_t n); + void rehash_impl(std::size_t n); + + // Move/copy buckets + + void move_buckets_to(buckets& dst); + void copy_buckets_to(buckets& dst) const; + + // Misc. key methods + + std::size_t count(key_type const& k) const; + iterator_base find(key_type const& k) const; + template <class Key, class Hash, class Pred> + iterator_base find(Key const& k, Hash const& h, Pred const& eq) const; + value_type& at(key_type const& k) const; + iterator_pair equal_range(key_type const& k) const; + + // Erase + // + // no throw + + void clear(); + std::size_t erase_key(key_type const& k); + iterator_base erase_return_iterator(iterator_base r); + void erase(iterator_base r); + std::size_t erase_group(node_ptr* it, bucket_ptr bucket); + iterator_base erase_range(iterator_base r1, iterator_base r2); + + // recompute_begin_bucket + + void init_buckets(); + + // After an erase cached_begin_bucket_ might be left pointing to + // an empty bucket, so this is called to update it + // + // no throw + + void recompute_begin_bucket(bucket_ptr b); + + // This is called when a range has been erased + // + // no throw + + void recompute_begin_bucket(bucket_ptr b1, bucket_ptr b2); + + // no throw + float load_factor() const; + + iterator_base emplace_empty_impl_with_node( + node_constructor&, std::size_t); + }; + + // Iterator Access + +#if !defined(__clang__) + class iterator_access + { + public: + template <class Iterator> + static BOOST_DEDUCED_TYPENAME Iterator::base const& + get(Iterator const& it) + { + return it.base_; + } + }; +#else + class iterator_access + { + public: + // Note: we access Iterator::base here, rather than in the function + // signature to work around a bug in the friend support of an + // early version of clang. + + template <class Iterator> + struct base + { + typedef BOOST_DEDUCED_TYPENAME Iterator::base type; + }; + + template <class Iterator> + static BOOST_DEDUCED_TYPENAME base<Iterator>::type const& + get(Iterator const& it) + { + return it.base_; + } + }; +#endif + + // Iterators + + template <class A, class G> class hash_iterator; + template <class A, class G> class hash_const_iterator; + template <class A, class G> class hash_local_iterator; + template <class A, class G> class hash_const_local_iterator; + + // Local Iterators + // + // all no throw + + template <class A, class G> + class hash_local_iterator + : public boost::iterator < + std::forward_iterator_tag, + BOOST_DEDUCED_TYPENAME A::value_type, + std::ptrdiff_t, + BOOST_DEDUCED_TYPENAME A::pointer, + BOOST_DEDUCED_TYPENAME A::reference> + { + public: + typedef BOOST_DEDUCED_TYPENAME A::value_type value_type; + + private: + typedef hash_buckets<A, G> buckets; + typedef BOOST_DEDUCED_TYPENAME buckets::node_ptr node_ptr; + typedef BOOST_DEDUCED_TYPENAME buckets::node node; + typedef hash_const_local_iterator<A, G> const_local_iterator; + + friend class hash_const_local_iterator<A, G>; + node_ptr ptr_; + + public: + hash_local_iterator() : ptr_() {} + explicit hash_local_iterator(node_ptr x) : ptr_(x) {} + BOOST_DEDUCED_TYPENAME A::reference operator*() const { + return node::get_value(ptr_); + } + value_type* operator->() const { + return &node::get_value(ptr_); + } + hash_local_iterator& operator++() { + ptr_ = ptr_->next_; return *this; + } + hash_local_iterator operator++(int) { + hash_local_iterator tmp(ptr_); ptr_ = ptr_->next_; return tmp; } + bool operator==(hash_local_iterator x) const { + return ptr_ == x.ptr_; + } + bool operator==(const_local_iterator x) const { + return ptr_ == x.ptr_; + } + bool operator!=(hash_local_iterator x) const { + return ptr_ != x.ptr_; + } + bool operator!=(const_local_iterator x) const { + return ptr_ != x.ptr_; + } + }; + + template <class A, class G> + class hash_const_local_iterator + : public boost::iterator < + std::forward_iterator_tag, + BOOST_DEDUCED_TYPENAME A::value_type, + std::ptrdiff_t, + BOOST_DEDUCED_TYPENAME A::const_pointer, + BOOST_DEDUCED_TYPENAME A::const_reference > + { + public: + typedef BOOST_DEDUCED_TYPENAME A::value_type value_type; + + private: + typedef hash_buckets<A, G> buckets; + typedef BOOST_DEDUCED_TYPENAME buckets::node_ptr ptr; + typedef BOOST_DEDUCED_TYPENAME buckets::node node; + typedef hash_local_iterator<A, G> local_iterator; + friend class hash_local_iterator<A, G>; + ptr ptr_; + + public: + hash_const_local_iterator() : ptr_() {} + explicit hash_const_local_iterator(ptr x) : ptr_(x) {} + hash_const_local_iterator(local_iterator x) : ptr_(x.ptr_) {} + BOOST_DEDUCED_TYPENAME A::const_reference + operator*() const { + return node::get_value(ptr_); + } + value_type const* operator->() const { + return &node::get_value(ptr_); + } + hash_const_local_iterator& operator++() { + ptr_ = ptr_->next_; return *this; + } + hash_const_local_iterator operator++(int) { + hash_const_local_iterator tmp(ptr_); ptr_ = ptr_->next_; return tmp; + } + bool operator==(local_iterator x) const { + return ptr_ == x.ptr_; + } + bool operator==(hash_const_local_iterator x) const { + return ptr_ == x.ptr_; + } + bool operator!=(local_iterator x) const { + return ptr_ != x.ptr_; + } + bool operator!=(hash_const_local_iterator x) const { + return ptr_ != x.ptr_; + } + }; + + // iterators + // + // all no throw + + + template <class A, class G> + class hash_iterator + : public boost::iterator < + std::forward_iterator_tag, + BOOST_DEDUCED_TYPENAME A::value_type, + std::ptrdiff_t, + BOOST_DEDUCED_TYPENAME A::pointer, + BOOST_DEDUCED_TYPENAME A::reference > + { + public: + typedef BOOST_DEDUCED_TYPENAME A::value_type value_type; + + private: + typedef hash_buckets<A, G> buckets; + typedef BOOST_DEDUCED_TYPENAME buckets::node node; + typedef BOOST_DEDUCED_TYPENAME buckets::iterator_base base; + typedef hash_const_iterator<A, G> const_iterator; + friend class hash_const_iterator<A, G>; + base base_; + + public: + + hash_iterator() : base_() {} + explicit hash_iterator(base const& x) : base_(x) {} + BOOST_DEDUCED_TYPENAME A::reference operator*() const { + return *base_; + } + value_type* operator->() const { + return &*base_; + } + hash_iterator& operator++() { + base_.increment(); return *this; + } + hash_iterator operator++(int) { + hash_iterator tmp(base_); base_.increment(); return tmp; + } + bool operator==(hash_iterator const& x) const { + return base_ == x.base_; + } + bool operator==(const_iterator const& x) const { + return base_ == x.base_; + } + bool operator!=(hash_iterator const& x) const { + return base_ != x.base_; + } + bool operator!=(const_iterator const& x) const { + return base_ != x.base_; + } + }; + + template <class A, class G> + class hash_const_iterator + : public boost::iterator < + std::forward_iterator_tag, + BOOST_DEDUCED_TYPENAME A::value_type, + std::ptrdiff_t, + BOOST_DEDUCED_TYPENAME A::const_pointer, + BOOST_DEDUCED_TYPENAME A::const_reference > + { + public: + typedef BOOST_DEDUCED_TYPENAME A::value_type value_type; + + private: + typedef hash_buckets<A, G> buckets; + typedef BOOST_DEDUCED_TYPENAME buckets::node node; + typedef BOOST_DEDUCED_TYPENAME buckets::iterator_base base; + typedef hash_iterator<A, G> iterator; + friend class hash_iterator<A, G>; + friend class iterator_access; + base base_; + + public: + + hash_const_iterator() : base_() {} + explicit hash_const_iterator(base const& x) : base_(x) {} + hash_const_iterator(iterator const& x) : base_(x.base_) {} + BOOST_DEDUCED_TYPENAME A::const_reference operator*() const { + return *base_; + } + value_type const* operator->() const { + return &*base_; + } + hash_const_iterator& operator++() { + base_.increment(); return *this; + } + hash_const_iterator operator++(int) { + hash_const_iterator tmp(base_); base_.increment(); return tmp; + } + bool operator==(iterator const& x) const { + return base_ == x.base_; + } + bool operator==(hash_const_iterator const& x) const { + return base_ == x.base_; + } + bool operator!=(iterator const& x) const { + return base_ != x.base_; + } + bool operator!=(hash_const_iterator const& x) const { + return base_ != x.base_; + } + }; + + // types + + template <class K, class V, class H, class P, class A, class E, class G> + struct types + { + public: + typedef K key_type; + typedef V value_type; + typedef H hasher; + typedef P key_equal; + typedef A value_allocator; + typedef E extractor; + typedef G group_type; + + typedef hash_node_constructor<value_allocator, group_type> + node_constructor; + typedef hash_buckets<value_allocator, group_type> buckets; + typedef hash_buffered_functions<hasher, key_equal> buffered_functions; + + typedef BOOST_DEDUCED_TYPENAME buckets::node node; + typedef BOOST_DEDUCED_TYPENAME buckets::bucket bucket; + typedef BOOST_DEDUCED_TYPENAME buckets::node_ptr node_ptr; + typedef BOOST_DEDUCED_TYPENAME buckets::bucket_ptr bucket_ptr; + typedef BOOST_DEDUCED_TYPENAME buckets::iterator_base iterator_base; + typedef BOOST_DEDUCED_TYPENAME buckets::node_allocator node_allocator; + + typedef std::pair<iterator_base, iterator_base> iterator_pair; + }; +}} + +#endif diff --git a/3rdParty/Boost/src/boost/unordered/detail/move.hpp b/3rdParty/Boost/src/boost/unordered/detail/move.hpp new file mode 100644 index 0000000..16fd921 --- /dev/null +++ b/3rdParty/Boost/src/boost/unordered/detail/move.hpp @@ -0,0 +1,243 @@ +/* + Copyright 2005-2007 Adobe Systems Incorporated + + Use, modification and distribution are subject to 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). +*/ + +/*************************************************************************************************/ + +#ifndef BOOST_UNORDERED_DETAIL_MOVE_HEADER +#define BOOST_UNORDERED_DETAIL_MOVE_HEADER + +#include <boost/config.hpp> +#include <boost/mpl/bool.hpp> +#include <boost/mpl/and.hpp> +#include <boost/mpl/or.hpp> +#include <boost/mpl/not.hpp> +#include <boost/type_traits/is_convertible.hpp> +#include <boost/type_traits/is_same.hpp> +#include <boost/type_traits/is_class.hpp> +#include <boost/utility/enable_if.hpp> +#include <boost/detail/workaround.hpp> + +/*************************************************************************************************/ + +#if defined(BOOST_NO_SFINAE) +# define BOOST_UNORDERED_NO_HAS_MOVE_ASSIGN +#elif defined(__GNUC__) && \ + (__GNUC__ < 3 || __GNUC__ == 3 && __GNUC_MINOR__ <= 3) +# define BOOST_UNORDERED_NO_HAS_MOVE_ASSIGN +#elif BOOST_WORKAROUND(BOOST_INTEL, < 900) || \ + BOOST_WORKAROUND(__EDG_VERSION__, < 304) || \ + BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x0593)) +# define BOOST_UNORDERED_NO_HAS_MOVE_ASSIGN +#endif + +/*************************************************************************************************/ + +namespace boost { +namespace unordered_detail { + +/*************************************************************************************************/ + +namespace move_detail { + +/*************************************************************************************************/ + +#if !defined(BOOST_UNORDERED_NO_HAS_MOVE_ASSIGN) + +/*************************************************************************************************/ + +template <typename T> +struct class_has_move_assign { + class type { + typedef T& (T::*E)(T t); + typedef char (&no_type)[1]; + typedef char (&yes_type)[2]; + template <E e> struct sfinae { typedef yes_type type; }; + template <class U> + static typename sfinae<&U::operator=>::type test(int); + template <class U> + static no_type test(...); + public: + enum {value = sizeof(test<T>(1)) == sizeof(yes_type)}; + }; + }; + +/*************************************************************************************************/ + +template<typename T> +struct has_move_assign : boost::mpl::and_<boost::is_class<T>, class_has_move_assign<T> > {}; + +/*************************************************************************************************/ + +class test_can_convert_anything { }; + +/*************************************************************************************************/ + +#endif // BOOST_UNORDERED_NO_HAS_MOVE_ASSIGN + +/*************************************************************************************************/ + +/* + REVISIT (sparent@adobe.com): This is a work around for Boost 1.34.1 and VC++ 2008 where + boost::is_convertible<T, T> fails to compile. +*/ + +template <typename T, typename U> +struct is_convertible : boost::mpl::or_< + boost::is_same<T, U>, + boost::is_convertible<T, U> +> { }; + +/*************************************************************************************************/ + +} //namespace move_detail + + +/*************************************************************************************************/ + +/*! +\ingroup move_related +\brief move_from is used for move_ctors. +*/ + +template <typename T> +struct move_from +{ + explicit move_from(T& x) : source(x) { } + T& source; +private: + move_from& operator=(move_from const&); +}; + +/*************************************************************************************************/ + +#if !defined(BOOST_UNORDERED_NO_HAS_MOVE_ASSIGN) + +/*************************************************************************************************/ + +/*! +\ingroup move_related +\brief The is_movable trait can be used to identify movable types. +*/ +template <typename T> +struct is_movable : boost::mpl::and_< + boost::is_convertible<move_from<T>, T>, + move_detail::has_move_assign<T>, + boost::mpl::not_<boost::is_convertible<move_detail::test_can_convert_anything, T> > + > { }; + +/*************************************************************************************************/ + +#else // BOOST_UNORDERED_NO_HAS_MOVE_ASSIGN + +// On compilers which don't have adequate SFINAE support, treat most types as unmovable, +// unless the trait is specialized. + +template <typename T> +struct is_movable : boost::mpl::false_ { }; + +#endif + +/*************************************************************************************************/ + +#if !defined(BOOST_NO_SFINAE) + +/*************************************************************************************************/ + +/*! +\ingroup move_related +\brief copy_sink and move_sink are used to select between overloaded operations according to + whether type T is movable and convertible to type U. +\sa move +*/ + +template <typename T, + typename U = T, + typename R = void*> +struct copy_sink : boost::enable_if< + boost::mpl::and_< + boost::unordered_detail::move_detail::is_convertible<T, U>, + boost::mpl::not_<is_movable<T> > + >, + R + > +{ }; + +/*************************************************************************************************/ + +/*! +\ingroup move_related +\brief move_sink and copy_sink are used to select between overloaded operations according to + whether type T is movable and convertible to type U. + \sa move +*/ + +template <typename T, + typename U = T, + typename R = void*> +struct move_sink : boost::enable_if< + boost::mpl::and_< + boost::unordered_detail::move_detail::is_convertible<T, U>, + is_movable<T> + >, + R + > +{ }; + +/*************************************************************************************************/ + +/*! +\ingroup move_related +\brief This version of move is selected when T is_movable . It in turn calls the move +constructor. This call, with the help of the return value optimization, will cause x to be moved +instead of copied to its destination. See adobe/test/move/main.cpp for examples. + +*/ +template <typename T> +T move(T& x, typename move_sink<T>::type = 0) { return T(move_from<T>(x)); } + +/*************************************************************************************************/ + +/*! +\ingroup move_related +\brief This version of move is selected when T is not movable . The net result will be that +x gets copied. +*/ +template <typename T> +T& move(T& x, typename copy_sink<T>::type = 0) { return x; } + +/*************************************************************************************************/ + +#else // BOOST_NO_SFINAE + +// On compilers without SFINAE, define copy_sink to always use the copy function. + +template <typename T, + typename U = T, + typename R = void*> +struct copy_sink +{ + typedef R type; +}; + +// Always copy the element unless this is overloaded. + +template <typename T> +T& move(T& x) { + return x; +} + +#endif // BOOST_NO_SFINAE + +} // namespace unordered_detail +} // namespace boost + +/*************************************************************************************************/ + +#endif + +/*************************************************************************************************/ diff --git a/3rdParty/Boost/src/boost/unordered/detail/node.hpp b/3rdParty/Boost/src/boost/unordered/detail/node.hpp new file mode 100644 index 0000000..85a3141 --- /dev/null +++ b/3rdParty/Boost/src/boost/unordered/detail/node.hpp @@ -0,0 +1,226 @@ + +// 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 diff --git a/3rdParty/Boost/src/boost/unordered/detail/table.hpp b/3rdParty/Boost/src/boost/unordered/detail/table.hpp new file mode 100644 index 0000000..d37c015 --- /dev/null +++ b/3rdParty/Boost/src/boost/unordered/detail/table.hpp @@ -0,0 +1,778 @@ + +// 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) + +#ifndef BOOST_UNORDERED_DETAIL_ALL_HPP_INCLUDED +#define BOOST_UNORDERED_DETAIL_ALL_HPP_INCLUDED + +#include <cstddef> +#include <stdexcept> +#include <algorithm> +#include <boost/config/no_tr1/cmath.hpp> +#include <boost/iterator/iterator_categories.hpp> +#include <boost/throw_exception.hpp> + +#include <boost/unordered/detail/buckets.hpp> + +namespace boost { namespace unordered_detail { + + //////////////////////////////////////////////////////////////////////////// + // Helper methods + + // strong exception safety, no side effects + template <class T> + inline bool hash_table<T>::equal( + key_type const& k, value_type const& v) const + { + return this->key_eq()(k, get_key(v)); + } + + // strong exception safety, no side effects + template <class T> + template <class Key, class Pred> + inline BOOST_DEDUCED_TYPENAME T::node_ptr + hash_table<T>::find_iterator(bucket_ptr bucket, Key const& k, + Pred const& eq) const + { + node_ptr it = bucket->next_; + while (BOOST_UNORDERED_BORLAND_BOOL(it) && + !eq(k, get_key(node::get_value(it)))) + { + it = node::next_group(it); + } + + return it; + } + + // strong exception safety, no side effects + template <class T> + inline BOOST_DEDUCED_TYPENAME T::node_ptr + hash_table<T>::find_iterator( + bucket_ptr bucket, key_type const& k) const + { + node_ptr it = bucket->next_; + while (BOOST_UNORDERED_BORLAND_BOOL(it) && + !equal(k, node::get_value(it))) + { + it = node::next_group(it); + } + + return it; + } + + // strong exception safety, no side effects + // pre: this->buckets_ + template <class T> + inline BOOST_DEDUCED_TYPENAME T::node_ptr + hash_table<T>::find_iterator(key_type const& k) const + { + return find_iterator(this->get_bucket(this->bucket_index(k)), k); + } + + // strong exception safety, no side effects + template <class T> + inline BOOST_DEDUCED_TYPENAME T::node_ptr* + hash_table<T>::find_for_erase( + bucket_ptr bucket, key_type const& k) const + { + node_ptr* it = &bucket->next_; + while(BOOST_UNORDERED_BORLAND_BOOL(*it) && + !equal(k, node::get_value(*it))) + { + it = &node::next_group(*it); + } + + return it; + } + + //////////////////////////////////////////////////////////////////////////// + // Load methods + + // no throw + template <class T> + std::size_t hash_table<T>::max_size() const + { + using namespace std; + + // size < mlf_ * count + return double_to_size_t(ceil( + (double) this->mlf_ * this->max_bucket_count())) - 1; + } + + // strong safety + template <class T> + inline std::size_t hash_table<T>::bucket_index( + key_type const& k) const + { + // hash_function can throw: + return this->hash_function()(k) % this->bucket_count_; + } + + + // no throw + template <class T> + inline std::size_t hash_table<T>::calculate_max_load() + { + using namespace std; + + // From 6.3.1/13: + // Only resize when size >= mlf_ * count + return double_to_size_t(ceil((double) mlf_ * this->bucket_count_)); + } + + template <class T> + void hash_table<T>::max_load_factor(float z) + { + BOOST_ASSERT(z > 0); + mlf_ = (std::max)(z, minimum_max_load_factor); + this->max_load_ = this->calculate_max_load(); + } + + // no throw + template <class T> + inline std::size_t hash_table<T>::min_buckets_for_size( + std::size_t size) const + { + BOOST_ASSERT(this->mlf_ != 0); + + using namespace std; + + // From 6.3.1/13: + // size < mlf_ * count + // => count > size / mlf_ + // + // Or from rehash post-condition: + // count > size / mlf_ + return next_prime(double_to_size_t(floor(size / (double) mlf_)) + 1); + } + + //////////////////////////////////////////////////////////////////////////// + // recompute_begin_bucket + + // init_buckets + + template <class T> + inline void hash_table<T>::init_buckets() + { + if (this->size_) { + this->cached_begin_bucket_ = this->buckets_; + while (!this->cached_begin_bucket_->next_) + ++this->cached_begin_bucket_; + } else { + this->cached_begin_bucket_ = this->get_bucket(this->bucket_count_); + } + this->max_load_ = calculate_max_load(); + } + + // After an erase cached_begin_bucket_ might be left pointing to + // an empty bucket, so this is called to update it + // + // no throw + + template <class T> + inline void hash_table<T>::recompute_begin_bucket(bucket_ptr b) + { + BOOST_ASSERT(!(b < this->cached_begin_bucket_)); + + if(b == this->cached_begin_bucket_) + { + if (this->size_ != 0) { + while (!this->cached_begin_bucket_->next_) + ++this->cached_begin_bucket_; + } else { + this->cached_begin_bucket_ = + this->get_bucket(this->bucket_count_); + } + } + } + + // This is called when a range has been erased + // + // no throw + + template <class T> + inline void hash_table<T>::recompute_begin_bucket( + bucket_ptr b1, bucket_ptr b2) + { + BOOST_ASSERT(!(b1 < this->cached_begin_bucket_) && !(b2 < b1)); + BOOST_ASSERT(BOOST_UNORDERED_BORLAND_BOOL(b2->next_)); + + if(b1 == this->cached_begin_bucket_ && !b1->next_) + this->cached_begin_bucket_ = b2; + } + + // no throw + template <class T> + inline float hash_table<T>::load_factor() const + { + BOOST_ASSERT(this->bucket_count_ != 0); + return static_cast<float>(this->size_) + / static_cast<float>(this->bucket_count_); + } + + //////////////////////////////////////////////////////////////////////////// + // Constructors + + template <class T> + hash_table<T>::hash_table(std::size_t num_buckets, + hasher const& hf, key_equal const& eq, node_allocator const& a) + : buckets(a, next_prime(num_buckets)), + base(hf, eq), + size_(), + mlf_(1.0f), + cached_begin_bucket_(), + max_load_(0) + { + } + + // Copy Construct with allocator + + template <class T> + hash_table<T>::hash_table(hash_table const& x, + node_allocator const& a) + : buckets(a, x.min_buckets_for_size(x.size_)), + base(x), + size_(x.size_), + mlf_(x.mlf_), + cached_begin_bucket_(), + max_load_(0) + { + if(x.size_) { + x.copy_buckets_to(*this); + this->init_buckets(); + } + } + + // Move Construct + + template <class T> + hash_table<T>::hash_table(hash_table& x, move_tag) + : buckets(x.node_alloc(), x.bucket_count_), + base(x), + size_(0), + mlf_(1.0f), + cached_begin_bucket_(), + max_load_(0) + { + this->partial_swap(x); + } + + template <class T> + hash_table<T>::hash_table(hash_table& x, + node_allocator const& a, move_tag) + : buckets(a, x.bucket_count_), + base(x), + size_(0), + mlf_(x.mlf_), + cached_begin_bucket_(), + max_load_(0) + { + if(a == x.node_alloc()) { + this->partial_swap(x); + } + else if(x.size_) { + x.copy_buckets_to(*this); + this->size_ = x.size_; + this->init_buckets(); + } + } + + template <class T> + hash_table<T>& hash_table<T>::operator=( + hash_table const& x) + { + hash_table tmp(x, this->node_alloc()); + this->fast_swap(tmp); + return *this; + } + + //////////////////////////////////////////////////////////////////////////// + // Swap & Move + + // Swap + // + // Strong exception safety + // + // Can throw if hash or predicate object's copy constructor throws + // or if allocators are unequal. + + template <class T> + inline void hash_table<T>::partial_swap(hash_table& x) + { + this->buckets::swap(x); // No throw + std::swap(this->size_, x.size_); + std::swap(this->mlf_, x.mlf_); + std::swap(this->cached_begin_bucket_, x.cached_begin_bucket_); + std::swap(this->max_load_, x.max_load_); + } + + template <class T> + inline void hash_table<T>::fast_swap(hash_table& x) + { + // These can throw, but they only affect the function objects + // that aren't in use so it is strongly exception safe, via. + // double buffering. + { + set_hash_functions<hasher, key_equal> op1(*this, x); + set_hash_functions<hasher, key_equal> op2(x, *this); + op1.commit(); + op2.commit(); + } + this->buckets::swap(x); // No throw + std::swap(this->size_, x.size_); + std::swap(this->mlf_, x.mlf_); + std::swap(this->cached_begin_bucket_, x.cached_begin_bucket_); + std::swap(this->max_load_, x.max_load_); + } + + template <class T> + inline void hash_table<T>::slow_swap(hash_table& x) + { + if(this == &x) return; + + { + // These can throw, but they only affect the function objects + // that aren't in use so it is strongly exception safe, via. + // double buffering. + set_hash_functions<hasher, key_equal> op1(*this, x); + set_hash_functions<hasher, key_equal> op2(x, *this); + + // Create new buckets in separate hash_buckets objects + // which will clean up if anything throws an exception. + // (all can throw, but with no effect as these are new objects). + + buckets b1(this->node_alloc(), x.min_buckets_for_size(x.size_)); + if(x.size_) x.copy_buckets_to(b1); + + buckets b2(x.node_alloc(), this->min_buckets_for_size(this->size_)); + if(this->size_) copy_buckets_to(b2); + + // Modifying the data, so no throw from now on. + + b1.swap(*this); + b2.swap(x); + op1.commit(); + op2.commit(); + } + + std::swap(this->size_, x.size_); + + if(this->buckets_) this->init_buckets(); + if(x.buckets_) x.init_buckets(); + } + + template <class T> + void hash_table<T>::swap(hash_table& x) + { + if(this->node_alloc() == x.node_alloc()) { + if(this != &x) this->fast_swap(x); + } + else { + this->slow_swap(x); + } + } + + + // Move + // + // Strong exception safety (might change unused function objects) + // + // Can throw if hash or predicate object's copy constructor throws + // or if allocators are unequal. + + template <class T> + void hash_table<T>::move(hash_table& x) + { + // This can throw, but it only affects the function objects + // that aren't in use so it is strongly exception safe, via. + // double buffering. + set_hash_functions<hasher, key_equal> new_func_this(*this, x); + + if(this->node_alloc() == x.node_alloc()) { + this->buckets::move(x); // no throw + this->size_ = x.size_; + this->cached_begin_bucket_ = x.cached_begin_bucket_; + this->max_load_ = x.max_load_; + x.size_ = 0; + } + else { + // Create new buckets in separate HASH_TABLE_DATA objects + // which will clean up if anything throws an exception. + // (all can throw, but with no effect as these are new objects). + + buckets b(this->node_alloc(), x.min_buckets_for_size(x.size_)); + if(x.size_) x.copy_buckets_to(b); + + // Start updating the data here, no throw from now on. + this->size_ = x.size_; + b.swap(*this); + this->init_buckets(); + } + + // We've made it, the rest is no throw. + this->mlf_ = x.mlf_; + new_func_this.commit(); + } + + //////////////////////////////////////////////////////////////////////////// + // Reserve & Rehash + + // basic exception safety + template <class T> + inline void hash_table<T>::create_for_insert(std::size_t size) + { + this->bucket_count_ = (std::max)(this->bucket_count_, + this->min_buckets_for_size(size)); + this->create_buckets(); + this->init_buckets(); + } + + // basic exception safety + template <class T> + inline bool hash_table<T>::reserve_for_insert(std::size_t size) + { + if(size >= max_load_) { + std::size_t num_buckets + = this->min_buckets_for_size((std::max)(size, + this->size_ + (this->size_ >> 1))); + if(num_buckets != this->bucket_count_) { + rehash_impl(num_buckets); + return true; + } + } + + return false; + } + + // if hash function throws, basic exception safety + // strong otherwise. + + template <class T> + inline void hash_table<T>::rehash(std::size_t min_buckets) + { + using namespace std; + + if(!this->size_) { + if(this->buckets_) this->delete_buckets(); + this->bucket_count_ = next_prime(min_buckets); + } + else { + // no throw: + min_buckets = next_prime((std::max)(min_buckets, + double_to_size_t(floor(this->size_ / (double) mlf_)) + 1)); + if(min_buckets != this->bucket_count_) rehash_impl(min_buckets); + } + } + + // if hash function throws, basic exception safety + // strong otherwise + + template <class T> + void hash_table<T> + ::rehash_impl(std::size_t num_buckets) + { + hasher const& hf = this->hash_function(); + std::size_t size = this->size_; + bucket_ptr end = this->get_bucket(this->bucket_count_); + + buckets dst(this->node_alloc(), num_buckets); + dst.create_buckets(); + + buckets src(this->node_alloc(), this->bucket_count_); + src.swap(*this); + this->size_ = 0; + + for(bucket_ptr bucket = this->cached_begin_bucket_; + bucket != end; ++bucket) + { + node_ptr group = bucket->next_; + while(group) { + // Move the first group of equivalent nodes in bucket to dst. + + // This next line throws iff the hash function throws. + bucket_ptr dst_bucket = dst.bucket_ptr_from_hash( + hf(get_key_from_ptr(group))); + + node_ptr& next_group = node::next_group(group); + bucket->next_ = next_group; + next_group = dst_bucket->next_; + dst_bucket->next_ = group; + group = bucket->next_; + } + } + + // Swap the new nodes back into the container and setup the local + // variables. + this->size_ = size; + dst.swap(*this); // no throw + this->init_buckets(); + } + + //////////////////////////////////////////////////////////////////////////// + // copy_buckets_to + + // copy_buckets_to + // + // basic excpetion safety. If an exception is thrown this will + // leave dst partially filled. + + template <class T> + void hash_table<T> + ::copy_buckets_to(buckets& dst) const + { + BOOST_ASSERT(this->buckets_ && !dst.buckets_); + + hasher const& hf = this->hash_function(); + bucket_ptr end = this->get_bucket(this->bucket_count_); + + node_constructor a(dst); + dst.create_buckets(); + + // no throw: + for(bucket_ptr i = this->cached_begin_bucket_; i != end; ++i) { + // no throw: + for(node_ptr it = i->next_; it;) { + // hash function can throw. + bucket_ptr dst_bucket = dst.bucket_ptr_from_hash( + hf(get_key_from_ptr(it))); + // throws, strong + + node_ptr group_end = node::next_group(it); + + a.construct(node::get_value(it)); + node_ptr n = a.release(); + node::add_to_bucket(n, *dst_bucket); + + for(it = it->next_; it != group_end; it = it->next_) { + a.construct(node::get_value(it)); + node::add_after_node(a.release(), n); + } + } + } + } + + //////////////////////////////////////////////////////////////////////////// + // Misc. key methods + + // strong exception safety + + // count + // + // strong exception safety, no side effects + + template <class T> + std::size_t hash_table<T>::count(key_type const& k) const + { + if(!this->size_) return 0; + node_ptr it = find_iterator(k); // throws, strong + return BOOST_UNORDERED_BORLAND_BOOL(it) ? node::group_count(it) : 0; + } + + // find + // + // strong exception safety, no side effects + template <class T> + BOOST_DEDUCED_TYPENAME T::iterator_base + hash_table<T>::find(key_type const& k) const + { + if(!this->size_) return this->end(); + + bucket_ptr bucket = this->get_bucket(this->bucket_index(k)); + node_ptr it = find_iterator(bucket, k); + + if (BOOST_UNORDERED_BORLAND_BOOL(it)) + return iterator_base(bucket, it); + else + return this->end(); + } + + template <class T> + template <class Key, class Hash, class Pred> + BOOST_DEDUCED_TYPENAME T::iterator_base hash_table<T>::find(Key const& k, + Hash const& h, Pred const& eq) const + { + if(!this->size_) return this->end(); + + bucket_ptr bucket = this->get_bucket(h(k) % this->bucket_count_); + node_ptr it = find_iterator(bucket, k, eq); + + if (BOOST_UNORDERED_BORLAND_BOOL(it)) + return iterator_base(bucket, it); + else + return this->end(); + } + + template <class T> + BOOST_DEDUCED_TYPENAME T::value_type& + hash_table<T>::at(key_type const& k) const + { + if(!this->size_) + boost::throw_exception(std::out_of_range("Unable to find key in unordered_map.")); + + bucket_ptr bucket = this->get_bucket(this->bucket_index(k)); + node_ptr it = find_iterator(bucket, k); + + if (!it) + boost::throw_exception(std::out_of_range("Unable to find key in unordered_map.")); + + return node::get_value(it); + } + + // equal_range + // + // strong exception safety, no side effects + template <class T> + BOOST_DEDUCED_TYPENAME T::iterator_pair + hash_table<T>::equal_range(key_type const& k) const + { + if(!this->size_) + return iterator_pair(this->end(), this->end()); + + bucket_ptr bucket = this->get_bucket(this->bucket_index(k)); + node_ptr it = find_iterator(bucket, k); + if (BOOST_UNORDERED_BORLAND_BOOL(it)) { + iterator_base first(iterator_base(bucket, it)); + iterator_base second(first); + second.increment_bucket(node::next_group(second.node_)); + return iterator_pair(first, second); + } + else { + return iterator_pair(this->end(), this->end()); + } + } + + //////////////////////////////////////////////////////////////////////////// + // Erase methods + + template <class T> + void hash_table<T>::clear() + { + if(!this->size_) return; + + bucket_ptr end = this->get_bucket(this->bucket_count_); + for(bucket_ptr begin = this->buckets_; begin != end; ++begin) { + this->clear_bucket(begin); + } + + this->size_ = 0; + this->cached_begin_bucket_ = end; + } + + template <class T> + inline std::size_t hash_table<T>::erase_group( + node_ptr* it, bucket_ptr bucket) + { + node_ptr pos = *it; + node_ptr end = node::next_group(pos); + *it = end; + std::size_t count = this->delete_nodes(pos, end); + this->size_ -= count; + this->recompute_begin_bucket(bucket); + return count; + } + + template <class T> + std::size_t hash_table<T>::erase_key(key_type const& k) + { + if(!this->size_) return 0; + + // No side effects in initial section + bucket_ptr bucket = this->get_bucket(this->bucket_index(k)); + node_ptr* it = this->find_for_erase(bucket, k); + + // No throw. + return *it ? this->erase_group(it, bucket) : 0; + } + + template <class T> + void hash_table<T>::erase(iterator_base r) + { + BOOST_ASSERT(r.node_); + --this->size_; + node::unlink_node(*r.bucket_, r.node_); + this->delete_node(r.node_); + // r has been invalidated but its bucket is still valid + this->recompute_begin_bucket(r.bucket_); + } + + template <class T> + BOOST_DEDUCED_TYPENAME T::iterator_base + hash_table<T>::erase_return_iterator(iterator_base r) + { + BOOST_ASSERT(r.node_); + iterator_base next = r; + next.increment(); + --this->size_; + node::unlink_node(*r.bucket_, r.node_); + this->delete_node(r.node_); + // r has been invalidated but its bucket is still valid + this->recompute_begin_bucket(r.bucket_, next.bucket_); + return next; + } + + template <class T> + BOOST_DEDUCED_TYPENAME T::iterator_base + hash_table<T>::erase_range( + iterator_base r1, iterator_base r2) + { + if(r1 != r2) + { + BOOST_ASSERT(r1.node_); + if (r1.bucket_ == r2.bucket_) { + node::unlink_nodes(*r1.bucket_, r1.node_, r2.node_); + this->size_ -= this->delete_nodes(r1.node_, r2.node_); + + // No need to call recompute_begin_bucket because + // the nodes are only deleted from one bucket, which + // still contains r2 after the erase. + BOOST_ASSERT(r1.bucket_->next_); + } + else { + bucket_ptr end_bucket = r2.node_ ? + r2.bucket_ : this->get_bucket(this->bucket_count_); + BOOST_ASSERT(r1.bucket_ < end_bucket); + node::unlink_nodes(*r1.bucket_, r1.node_, node_ptr()); + this->size_ -= this->delete_nodes(r1.node_, node_ptr()); + + bucket_ptr i = r1.bucket_; + for(++i; i != end_bucket; ++i) { + this->size_ -= this->delete_nodes(i->next_, node_ptr()); + i->next_ = node_ptr(); + } + + if(r2.node_) { + node_ptr first = r2.bucket_->next_; + node::unlink_nodes(*r2.bucket_, r2.node_); + this->size_ -= this->delete_nodes(first, r2.node_); + } + + // r1 has been invalidated but its bucket is still + // valid. + this->recompute_begin_bucket(r1.bucket_, end_bucket); + } + } + + return r2; + } + + template <class T> + BOOST_DEDUCED_TYPENAME hash_table<T>::iterator_base + hash_table<T>::emplace_empty_impl_with_node( + node_constructor& a, std::size_t size) + { + key_type const& k = get_key(a.value()); + std::size_t hash_value = this->hash_function()(k); + if(this->buckets_) this->reserve_for_insert(size); + else this->create_for_insert(size); + bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value); + node_ptr n = a.release(); + node::add_to_bucket(n, *bucket); + ++this->size_; + this->cached_begin_bucket_ = bucket; + return iterator_base(bucket, n); + } +}} + +#endif diff --git a/3rdParty/Boost/src/boost/unordered/detail/unique.hpp b/3rdParty/Boost/src/boost/unordered/detail/unique.hpp new file mode 100644 index 0000000..96fdfee --- /dev/null +++ b/3rdParty/Boost/src/boost/unordered/detail/unique.hpp @@ -0,0 +1,513 @@ + +// Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard. +// Copyright (C) 2005-2010 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) + +#ifndef BOOST_UNORDERED_DETAIL_UNIQUE_HPP_INCLUDED +#define BOOST_UNORDERED_DETAIL_UNIQUE_HPP_INCLUDED + +#include <boost/unordered/detail/table.hpp> +#include <boost/unordered/detail/extract_key.hpp> + +namespace boost { namespace unordered_detail { + + template <class T> + class hash_unique_table : public T::table + { + public: + typedef BOOST_DEDUCED_TYPENAME T::hasher hasher; + typedef BOOST_DEDUCED_TYPENAME T::key_equal key_equal; + typedef BOOST_DEDUCED_TYPENAME T::value_allocator value_allocator; + typedef BOOST_DEDUCED_TYPENAME T::key_type key_type; + typedef BOOST_DEDUCED_TYPENAME T::value_type value_type; + typedef BOOST_DEDUCED_TYPENAME T::table table; + typedef BOOST_DEDUCED_TYPENAME T::node_constructor node_constructor; + + typedef BOOST_DEDUCED_TYPENAME T::node node; + typedef BOOST_DEDUCED_TYPENAME T::node_ptr node_ptr; + typedef BOOST_DEDUCED_TYPENAME T::bucket_ptr bucket_ptr; + typedef BOOST_DEDUCED_TYPENAME T::iterator_base iterator_base; + typedef BOOST_DEDUCED_TYPENAME T::extractor extractor; + + typedef std::pair<iterator_base, bool> emplace_return; + + // Constructors + + hash_unique_table(std::size_t n, hasher const& hf, key_equal const& eq, + value_allocator const& a) + : table(n, hf, eq, a) {} + hash_unique_table(hash_unique_table const& x) + : table(x, x.node_alloc()) {} + hash_unique_table(hash_unique_table const& x, value_allocator const& a) + : table(x, a) {} + hash_unique_table(hash_unique_table& x, move_tag m) + : table(x, m) {} + hash_unique_table(hash_unique_table& x, value_allocator const& a, + move_tag m) + : table(x, a, m) {} + ~hash_unique_table() {} + + // Insert methods + + emplace_return emplace_impl_with_node(node_constructor& a); + value_type& operator[](key_type const& k); + + // equals + + bool equals(hash_unique_table const&) const; + + node_ptr add_node(node_constructor& a, bucket_ptr bucket); + +#if defined(BOOST_UNORDERED_STD_FORWARD) + + template<class... Args> + emplace_return emplace(Args&&... args); + template<class... Args> + emplace_return emplace_impl(key_type const& k, Args&&... args); + template<class... Args> + emplace_return emplace_impl(no_key, Args&&... args); + template<class... Args> + emplace_return emplace_empty_impl(Args&&... args); +#else + +#define BOOST_UNORDERED_INSERT_IMPL(z, n, _) \ + template <BOOST_UNORDERED_TEMPLATE_ARGS(z, n)> \ + emplace_return emplace( \ + BOOST_UNORDERED_FUNCTION_PARAMS(z, n)); \ + template <BOOST_UNORDERED_TEMPLATE_ARGS(z, n)> \ + emplace_return emplace_impl(key_type const& k, \ + BOOST_UNORDERED_FUNCTION_PARAMS(z, n)); \ + template <BOOST_UNORDERED_TEMPLATE_ARGS(z, n)> \ + emplace_return emplace_impl(no_key, \ + BOOST_UNORDERED_FUNCTION_PARAMS(z, n)); \ + template <BOOST_UNORDERED_TEMPLATE_ARGS(z, n)> \ + emplace_return emplace_empty_impl( \ + BOOST_UNORDERED_FUNCTION_PARAMS(z, n)); + + BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT, + BOOST_UNORDERED_INSERT_IMPL, _) + +#undef BOOST_UNORDERED_INSERT_IMPL + +#endif + + // if hash function throws, or inserting > 1 element, basic exception + // safety strong otherwise + template <class InputIt> + void insert_range(InputIt i, InputIt j); + template <class InputIt> + void insert_range_impl(key_type const&, InputIt i, InputIt j); + template <class InputIt> + void insert_range_impl2(node_constructor&, key_type const&, InputIt i, InputIt j); + template <class InputIt> + void insert_range_impl(no_key, InputIt i, InputIt j); + }; + + template <class H, class P, class A> + struct set : public types< + BOOST_DEDUCED_TYPENAME A::value_type, + BOOST_DEDUCED_TYPENAME A::value_type, + H, P, A, + set_extractor<BOOST_DEDUCED_TYPENAME A::value_type>, + ungrouped> + { + typedef hash_unique_table<set<H, P, A> > impl; + typedef hash_table<set<H, P, A> > table; + }; + + template <class K, class H, class P, class A> + struct map : public types< + K, BOOST_DEDUCED_TYPENAME A::value_type, + H, P, A, + map_extractor<K, BOOST_DEDUCED_TYPENAME A::value_type>, + ungrouped> + { + typedef hash_unique_table<map<K, H, P, A> > impl; + typedef hash_table<map<K, H, P, A> > table; + }; + + //////////////////////////////////////////////////////////////////////////// + // Equality + + template <class T> + bool hash_unique_table<T> + ::equals(hash_unique_table<T> const& other) const + { + if(this->size_ != other.size_) return false; + if(!this->size_) return true; + + bucket_ptr end = this->get_bucket(this->bucket_count_); + for(bucket_ptr i = this->cached_begin_bucket_; i != end; ++i) + { + node_ptr it1 = i->next_; + while(BOOST_UNORDERED_BORLAND_BOOL(it1)) + { + node_ptr it2 = other.find_iterator(this->get_key_from_ptr(it1)); + if(!BOOST_UNORDERED_BORLAND_BOOL(it2)) return false; + if(!extractor::compare_mapped( + node::get_value(it1), node::get_value(it2))) + return false; + it1 = it1->next_; + } + } + + return true; + } + + //////////////////////////////////////////////////////////////////////////// + // A convenience method for adding nodes. + + template <class T> + inline BOOST_DEDUCED_TYPENAME hash_unique_table<T>::node_ptr + hash_unique_table<T>::add_node(node_constructor& a, + bucket_ptr bucket) + { + node_ptr n = a.release(); + node::add_to_bucket(n, *bucket); + ++this->size_; + if(bucket < this->cached_begin_bucket_) + this->cached_begin_bucket_ = bucket; + return n; + } + + //////////////////////////////////////////////////////////////////////////// + // Insert methods + + // if hash function throws, basic exception safety + // strong otherwise + template <class T> + BOOST_DEDUCED_TYPENAME hash_unique_table<T>::value_type& + hash_unique_table<T>::operator[](key_type const& k) + { + typedef BOOST_DEDUCED_TYPENAME value_type::second_type mapped_type; + + std::size_t hash_value = this->hash_function()(k); + bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value); + + if(!this->buckets_) { + node_constructor a(*this); + a.construct_pair(k, (mapped_type*) 0); + return *this->emplace_empty_impl_with_node(a, 1); + } + + node_ptr pos = this->find_iterator(bucket, k); + + if (BOOST_UNORDERED_BORLAND_BOOL(pos)) { + return node::get_value(pos); + } + else { + // Side effects only in this block. + + // Create the node before rehashing in case it throws an + // exception (need strong safety in such a case). + node_constructor a(*this); + a.construct_pair(k, (mapped_type*) 0); + + // reserve has basic exception safety if the hash function + // throws, strong otherwise. + if(this->reserve_for_insert(this->size_ + 1)) + bucket = this->bucket_ptr_from_hash(hash_value); + + // Nothing after this point can throw. + + return node::get_value(add_node(a, bucket)); + } + } + + template <class T> + inline BOOST_DEDUCED_TYPENAME hash_unique_table<T>::emplace_return + hash_unique_table<T>::emplace_impl_with_node(node_constructor& a) + { + // No side effects in this initial code + key_type const& k = this->get_key(a.value()); + std::size_t hash_value = this->hash_function()(k); + bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value); + node_ptr pos = this->find_iterator(bucket, k); + + if (BOOST_UNORDERED_BORLAND_BOOL(pos)) { + // Found an existing key, return it (no throw). + return emplace_return(iterator_base(bucket, pos), false); + } else { + // reserve has basic exception safety if the hash function + // throws, strong otherwise. + if(this->reserve_for_insert(this->size_ + 1)) + bucket = this->bucket_ptr_from_hash(hash_value); + + // Nothing after this point can throw. + + return emplace_return( + iterator_base(bucket, add_node(a, bucket)), + true); + } + } + +#if defined(BOOST_UNORDERED_STD_FORWARD) + + template <class T> + template<class... Args> + inline BOOST_DEDUCED_TYPENAME hash_unique_table<T>::emplace_return + hash_unique_table<T>::emplace_impl(key_type const& k, + Args&&... args) + { + // No side effects in this initial code + std::size_t hash_value = this->hash_function()(k); + bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value); + node_ptr pos = this->find_iterator(bucket, k); + + if (BOOST_UNORDERED_BORLAND_BOOL(pos)) { + // Found an existing key, return it (no throw). + return emplace_return(iterator_base(bucket, pos), false); + + } else { + // Doesn't already exist, add to bucket. + // Side effects only in this block. + + // Create the node before rehashing in case it throws an + // exception (need strong safety in such a case). + node_constructor a(*this); + a.construct(std::forward<Args>(args)...); + + // reserve has basic exception safety if the hash function + // throws, strong otherwise. + if(this->reserve_for_insert(this->size_ + 1)) + bucket = this->bucket_ptr_from_hash(hash_value); + + // Nothing after this point can throw. + + return emplace_return( + iterator_base(bucket, add_node(a, bucket)), + true); + } + } + + template <class T> + template<class... Args> + inline BOOST_DEDUCED_TYPENAME hash_unique_table<T>::emplace_return + hash_unique_table<T>::emplace_impl(no_key, Args&&... args) + { + // Construct the node regardless - in order to get the key. + // It will be discarded if it isn't used + node_constructor a(*this); + a.construct(std::forward<Args>(args)...); + return emplace_impl_with_node(a); + } + + template <class T> + template<class... Args> + inline BOOST_DEDUCED_TYPENAME hash_unique_table<T>::emplace_return + hash_unique_table<T>::emplace_empty_impl(Args&&... args) + { + node_constructor a(*this); + a.construct(std::forward<Args>(args)...); + return emplace_return(this->emplace_empty_impl_with_node(a, 1), true); + } + +#else + +#define BOOST_UNORDERED_INSERT_IMPL(z, num_params, _) \ + template <class T> \ + template <BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params)> \ + inline BOOST_DEDUCED_TYPENAME \ + hash_unique_table<T>::emplace_return \ + hash_unique_table<T>::emplace_impl( \ + key_type const& k, \ + BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params)) \ + { \ + std::size_t hash_value = this->hash_function()(k); \ + bucket_ptr bucket \ + = this->bucket_ptr_from_hash(hash_value); \ + node_ptr pos = this->find_iterator(bucket, k); \ + \ + if (BOOST_UNORDERED_BORLAND_BOOL(pos)) { \ + return emplace_return(iterator_base(bucket, pos), false); \ + } else { \ + node_constructor a(*this); \ + a.construct(BOOST_UNORDERED_CALL_PARAMS(z, num_params)); \ + \ + if(this->reserve_for_insert(this->size_ + 1)) \ + bucket = this->bucket_ptr_from_hash(hash_value); \ + \ + return emplace_return(iterator_base(bucket, \ + add_node(a, bucket)), true); \ + } \ + } \ + \ + template <class T> \ + template <BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params)> \ + inline BOOST_DEDUCED_TYPENAME \ + hash_unique_table<T>::emplace_return \ + hash_unique_table<T>:: \ + emplace_impl(no_key, \ + BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params)) \ + { \ + node_constructor a(*this); \ + a.construct(BOOST_UNORDERED_CALL_PARAMS(z, num_params)); \ + return emplace_impl_with_node(a); \ + } \ + \ + template <class T> \ + template <BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params)> \ + inline BOOST_DEDUCED_TYPENAME \ + hash_unique_table<T>::emplace_return \ + hash_unique_table<T>:: \ + emplace_empty_impl( \ + BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params)) \ + { \ + node_constructor a(*this); \ + a.construct(BOOST_UNORDERED_CALL_PARAMS(z, num_params)); \ + return emplace_return(this->emplace_empty_impl_with_node(a, 1), true); \ + } + + BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT, + BOOST_UNORDERED_INSERT_IMPL, _) + +#undef BOOST_UNORDERED_INSERT_IMPL + +#endif + +#if defined(BOOST_UNORDERED_STD_FORWARD) + + // Emplace (unique keys) + // (I'm using an overloaded emplace for both 'insert' and 'emplace') + + // if hash function throws, basic exception safety + // strong otherwise + + template <class T> + template<class... Args> + BOOST_DEDUCED_TYPENAME hash_unique_table<T>::emplace_return + hash_unique_table<T>::emplace(Args&&... args) + { + return this->size_ ? + emplace_impl( + extractor::extract(std::forward<Args>(args)...), + std::forward<Args>(args)...) : + emplace_empty_impl(std::forward<Args>(args)...); + } + +#else + + template <class T> + template <class Arg0> + BOOST_DEDUCED_TYPENAME hash_unique_table<T>::emplace_return + hash_unique_table<T>::emplace(Arg0 const& arg0) + { + return this->size_ ? + emplace_impl(extractor::extract(arg0), arg0) : + emplace_empty_impl(arg0); + } + +#define BOOST_UNORDERED_INSERT_IMPL(z, num_params, _) \ + template <class T> \ + template <BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params)> \ + BOOST_DEDUCED_TYPENAME hash_unique_table<T>::emplace_return \ + hash_unique_table<T>::emplace( \ + BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params)) \ + { \ + return this->size_ ? \ + emplace_impl(extractor::extract(arg0, arg1), \ + BOOST_UNORDERED_CALL_PARAMS(z, num_params)) : \ + emplace_empty_impl( \ + BOOST_UNORDERED_CALL_PARAMS(z, num_params)); \ + } + + BOOST_PP_REPEAT_FROM_TO(2, BOOST_UNORDERED_EMPLACE_LIMIT, + BOOST_UNORDERED_INSERT_IMPL, _) + +#undef BOOST_UNORDERED_INSERT_IMPL + +#endif + + //////////////////////////////////////////////////////////////////////////// + // Insert range methods + + template <class T> + template <class InputIt> + inline void hash_unique_table<T>::insert_range_impl2( + node_constructor& a, key_type const& k, InputIt i, InputIt j) + { + // No side effects in this initial code + std::size_t hash_value = this->hash_function()(k); + bucket_ptr bucket = this->bucket_ptr_from_hash(hash_value); + node_ptr pos = this->find_iterator(bucket, k); + + if (!BOOST_UNORDERED_BORLAND_BOOL(pos)) { + // Doesn't already exist, add to bucket. + // Side effects only in this block. + + // Create the node before rehashing in case it throws an + // exception (need strong safety in such a case). + a.construct(*i); + + // reserve has basic exception safety if the hash function + // throws, strong otherwise. + if(this->size_ + 1 >= this->max_load_) { + this->reserve_for_insert(this->size_ + insert_size(i, j)); + bucket = this->bucket_ptr_from_hash(hash_value); + } + + // Nothing after this point can throw. + add_node(a, bucket); + } + } + + template <class T> + template <class InputIt> + inline void hash_unique_table<T>::insert_range_impl( + key_type const&, InputIt i, InputIt j) + { + node_constructor a(*this); + + if(!this->size_) { + a.construct(*i); + this->emplace_empty_impl_with_node(a, 1); + ++i; + if(i == j) return; + } + + do { + // Note: can't use get_key as '*i' might not be value_type - it + // could be a pair with first_types as key_type without const or a + // different second_type. + // + // TODO: Might be worth storing the value_type instead of the key + // here. Could be more efficient if '*i' is expensive. Could be + // less efficient if copying the full value_type is expensive. + insert_range_impl2(a, extractor::extract(*i), i, j); + } while(++i != j); + } + + template <class T> + template <class InputIt> + inline void hash_unique_table<T>::insert_range_impl( + no_key, InputIt i, InputIt j) + { + node_constructor a(*this); + + if(!this->size_) { + a.construct(*i); + this->emplace_empty_impl_with_node(a, 1); + ++i; + if(i == j) return; + } + + do { + // No side effects in this initial code + a.construct(*i); + emplace_impl_with_node(a); + } while(++i != j); + } + + // if hash function throws, or inserting > 1 element, basic exception safety + // strong otherwise + template <class T> + template <class InputIt> + void hash_unique_table<T>::insert_range(InputIt i, InputIt j) + { + if(i != j) + return insert_range_impl(extractor::extract(*i), i, j); + } +}} + +#endif diff --git a/3rdParty/Boost/src/boost/unordered/detail/util.hpp b/3rdParty/Boost/src/boost/unordered/detail/util.hpp new file mode 100644 index 0000000..5540965 --- /dev/null +++ b/3rdParty/Boost/src/boost/unordered/detail/util.hpp @@ -0,0 +1,331 @@ + +// 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) + +#ifndef BOOST_UNORDERED_DETAIL_UTIL_HPP_INCLUDED +#define BOOST_UNORDERED_DETAIL_UTIL_HPP_INCLUDED + +#include <cstddef> +#include <utility> +#include <algorithm> +#include <boost/limits.hpp> +#include <boost/iterator/iterator_categories.hpp> +#include <boost/preprocessor/seq/size.hpp> +#include <boost/preprocessor/seq/enum.hpp> +#include <boost/unordered/detail/fwd.hpp> + +namespace boost { namespace unordered_detail { + + //////////////////////////////////////////////////////////////////////////// + // convert double to std::size_t + + inline std::size_t double_to_size_t(double f) + { + return f >= static_cast<double>( + (std::numeric_limits<std::size_t>::max)()) ? + (std::numeric_limits<std::size_t>::max)() : + static_cast<std::size_t>(f); + } + + //////////////////////////////////////////////////////////////////////////// + // primes + +#define BOOST_UNORDERED_PRIMES \ + (5ul)(11ul)(17ul)(29ul)(37ul)(53ul)(67ul)(79ul) \ + (97ul)(131ul)(193ul)(257ul)(389ul)(521ul)(769ul) \ + (1031ul)(1543ul)(2053ul)(3079ul)(6151ul)(12289ul)(24593ul) \ + (49157ul)(98317ul)(196613ul)(393241ul)(786433ul) \ + (1572869ul)(3145739ul)(6291469ul)(12582917ul)(25165843ul) \ + (50331653ul)(100663319ul)(201326611ul)(402653189ul)(805306457ul) \ + (1610612741ul)(3221225473ul)(4294967291ul) + + template<class T> struct prime_list_template + { + static std::size_t const value[]; + +#if !defined(SUNPRO_CC) + static std::ptrdiff_t const length; +#else + static std::ptrdiff_t const length + = BOOST_PP_SEQ_SIZE(BOOST_UNORDERED_PRIMES); +#endif + }; + + template<class T> + std::size_t const prime_list_template<T>::value[] = { + BOOST_PP_SEQ_ENUM(BOOST_UNORDERED_PRIMES) + }; + +#if !defined(SUNPRO_CC) + template<class T> + std::ptrdiff_t const prime_list_template<T>::length + = BOOST_PP_SEQ_SIZE(BOOST_UNORDERED_PRIMES); +#endif + +#undef BOOST_UNORDERED_PRIMES + + typedef prime_list_template<std::size_t> prime_list; + + // no throw + inline std::size_t next_prime(std::size_t num) { + std::size_t const* const prime_list_begin = prime_list::value; + std::size_t const* const prime_list_end = prime_list_begin + + prime_list::length; + std::size_t const* bound = + std::lower_bound(prime_list_begin, prime_list_end, num); + if(bound == prime_list_end) + bound--; + return *bound; + } + + // no throw + inline std::size_t prev_prime(std::size_t num) { + std::size_t const* const prime_list_begin = prime_list::value; + std::size_t const* const prime_list_end = prime_list_begin + + prime_list::length; + std::size_t const* bound = + std::upper_bound(prime_list_begin,prime_list_end, num); + if(bound != prime_list_begin) + bound--; + return *bound; + } + + //////////////////////////////////////////////////////////////////////////// + // pair_cast - because some libraries don't have the full pair constructors. + + template <class Dst1, class Dst2, class Src1, class Src2> + inline std::pair<Dst1, Dst2> pair_cast(std::pair<Src1, Src2> const& x) + { + return std::pair<Dst1, Dst2>(Dst1(x.first), Dst2(x.second)); + } + + //////////////////////////////////////////////////////////////////////////// + // insert_size/initial_size + +#if !defined(BOOST_NO_STD_DISTANCE) + using ::std::distance; +#else + template <class ForwardIterator> + inline std::size_t distance(ForwardIterator i, ForwardIterator j) { + std::size_t x; + std::distance(i, j, x); + return x; + } +#endif + + template <class I> + inline std::size_t insert_size(I i, I j, boost::forward_traversal_tag) + { + return std::distance(i, j); + } + + template <class I> + inline std::size_t insert_size(I, I, boost::incrementable_traversal_tag) + { + return 1; + } + + template <class I> + inline std::size_t insert_size(I i, I j) + { + BOOST_DEDUCED_TYPENAME boost::iterator_traversal<I>::type + iterator_traversal_tag; + return insert_size(i, j, iterator_traversal_tag); + } + + template <class I> + inline std::size_t initial_size(I i, I j, + std::size_t num_buckets = boost::unordered_detail::default_bucket_count) + { + return (std::max)(static_cast<std::size_t>(insert_size(i, j)) + 1, + num_buckets); + } + + //////////////////////////////////////////////////////////////////////////// + // Node Constructors + +#if defined(BOOST_UNORDERED_STD_FORWARD) + + template <class T, class... Args> + inline void construct_impl(T*, void* address, Args&&... args) + { + new(address) T(std::forward<Args>(args)...); + } + +#if defined(BOOST_UNORDERED_CPP0X_PAIR) + template <class First, class Second, class Key, class Arg0, class... Args> + inline void construct_impl(std::pair<First, Second>*, void* address, + Key&& k, Arg0&& arg0, Args&&... args) + ) + { + new(address) std::pair<First, Second>(k, + Second(arg0, std::forward<Args>(args)...); + } +#endif + +#else + +#define BOOST_UNORDERED_CONSTRUCT_IMPL(z, num_params, _) \ + template < \ + class T, \ + BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params) \ + > \ + inline void construct_impl( \ + T*, void* address, \ + BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params) \ + ) \ + { \ + new(address) T( \ + BOOST_UNORDERED_CALL_PARAMS(z, num_params)); \ + } \ + \ + template <class First, class Second, class Key, \ + BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params) \ + > \ + inline void construct_impl( \ + std::pair<First, Second>*, void* address, \ + Key const& k, BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params)) \ + { \ + new(address) std::pair<First, Second>(k, \ + Second(BOOST_UNORDERED_CALL_PARAMS(z, num_params))); \ + } + + BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT, + BOOST_UNORDERED_CONSTRUCT_IMPL, _) + +#undef BOOST_UNORDERED_CONSTRUCT_IMPL +#endif + + // hash_node_constructor + // + // Used to construct nodes in an exception safe manner. + + template <class Alloc, class Grouped> + class hash_node_constructor + { + typedef hash_buckets<Alloc, Grouped> buckets; + typedef BOOST_DEDUCED_TYPENAME buckets::node node; + typedef BOOST_DEDUCED_TYPENAME buckets::real_node_ptr real_node_ptr; + typedef BOOST_DEDUCED_TYPENAME buckets::value_type value_type; + + buckets& buckets_; + real_node_ptr node_; + bool node_constructed_; + bool value_constructed_; + + public: + + hash_node_constructor(buckets& m) : + buckets_(m), + node_(), + node_constructed_(false), + value_constructed_(false) + { + } + + ~hash_node_constructor(); + void construct_preamble(); + +#if defined(BOOST_UNORDERED_STD_FORWARD) + template <class... Args> + void construct(Args&&... args) + { + construct_preamble(); + construct_impl((value_type*) 0, node_->address(), + std::forward<Args>(args)...); + value_constructed_ = true; + } +#else + +#define BOOST_UNORDERED_CONSTRUCT(z, num_params, _) \ + template < \ + BOOST_UNORDERED_TEMPLATE_ARGS(z, num_params) \ + > \ + void construct( \ + BOOST_UNORDERED_FUNCTION_PARAMS(z, num_params) \ + ) \ + { \ + construct_preamble(); \ + construct_impl( \ + (value_type*) 0, node_->address(), \ + BOOST_UNORDERED_CALL_PARAMS(z, num_params) \ + ); \ + value_constructed_ = true; \ + } + + BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT, + BOOST_UNORDERED_CONSTRUCT, _) + +#undef BOOST_UNORDERED_CONSTRUCT + +#endif + template <class K, class M> + void construct_pair(K const& k, M*) + { + construct_preamble(); + new(node_->address()) value_type(k, M()); + value_constructed_ = true; + } + + value_type& value() const + { + BOOST_ASSERT(node_); + return node_->value(); + } + + // no throw + BOOST_DEDUCED_TYPENAME buckets::node_ptr release() + { + real_node_ptr p = node_; + node_ = real_node_ptr(); + // node_ptr cast + return buckets_.bucket_alloc().address(*p); + } + + private: + hash_node_constructor(hash_node_constructor const&); + hash_node_constructor& operator=(hash_node_constructor const&); + }; + + // hash_node_constructor + + template <class Alloc, class Grouped> + inline hash_node_constructor<Alloc, Grouped>::~hash_node_constructor() + { + if (node_) { + if (value_constructed_) { +#if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613)) + struct dummy { hash_node<Alloc, Grouped> x; }; +#endif + boost::unordered_detail::destroy(&node_->value()); + } + + if (node_constructed_) + buckets_.node_alloc().destroy(node_); + + buckets_.node_alloc().deallocate(node_, 1); + } + } + + template <class Alloc, class Grouped> + inline void hash_node_constructor<Alloc, Grouped>::construct_preamble() + { + if(!node_) { + node_constructed_ = false; + value_constructed_ = false; + + node_ = buckets_.node_alloc().allocate(1); + buckets_.node_alloc().construct(node_, node()); + node_constructed_ = true; + } + else { + BOOST_ASSERT(node_constructed_ && value_constructed_); + boost::unordered_detail::destroy(&node_->value()); + value_constructed_ = false; + } + } +}} + +#endif diff --git a/3rdParty/Boost/src/boost/unordered/unordered_map.hpp b/3rdParty/Boost/src/boost/unordered/unordered_map.hpp new file mode 100644 index 0000000..5bad0eb --- /dev/null +++ b/3rdParty/Boost/src/boost/unordered/unordered_map.hpp @@ -0,0 +1,1118 @@ + +// 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) + +// See http://www.boost.org/libs/unordered for documentation + +#ifndef BOOST_UNORDERED_UNORDERED_MAP_HPP_INCLUDED +#define BOOST_UNORDERED_UNORDERED_MAP_HPP_INCLUDED + +#if defined(_MSC_VER) && (_MSC_VER >= 1020) +# pragma once +#endif + +#include <boost/unordered/unordered_map_fwd.hpp> +#include <boost/functional/hash.hpp> +#include <boost/unordered/detail/allocator_helpers.hpp> +#include <boost/unordered/detail/equivalent.hpp> +#include <boost/unordered/detail/unique.hpp> + +#if defined(BOOST_NO_RVALUE_REFERENCES) +#include <boost/unordered/detail/move.hpp> +#endif + +#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST) +#include <initializer_list> +#endif + +#if defined(BOOST_MSVC) +#pragma warning(push) +#if BOOST_MSVC >= 1400 +#pragma warning(disable:4396) //the inline specifier cannot be used when a + // friend declaration refers to a specialization + // of a function template +#endif +#endif + +namespace boost +{ + template <class K, class T, class H, class P, class A> + class unordered_map + { + public: + typedef K key_type; + typedef std::pair<const K, T> value_type; + typedef T mapped_type; + typedef H hasher; + typedef P key_equal; + typedef A allocator_type; + +#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582) + private: +#endif + + typedef BOOST_DEDUCED_TYPENAME + boost::unordered_detail::rebind_wrap< + allocator_type, value_type>::type + value_allocator; + + typedef boost::unordered_detail::map<K, H, P, + value_allocator> types; + typedef BOOST_DEDUCED_TYPENAME types::impl table; + + typedef BOOST_DEDUCED_TYPENAME types::iterator_base iterator_base; + + public: + + typedef BOOST_DEDUCED_TYPENAME + value_allocator::pointer pointer; + typedef BOOST_DEDUCED_TYPENAME + value_allocator::const_pointer const_pointer; + typedef BOOST_DEDUCED_TYPENAME + value_allocator::reference reference; + typedef BOOST_DEDUCED_TYPENAME + value_allocator::const_reference const_reference; + + typedef std::size_t size_type; + typedef std::ptrdiff_t difference_type; + + typedef boost::unordered_detail::hash_const_local_iterator< + value_allocator, boost::unordered_detail::ungrouped> + const_local_iterator; + typedef boost::unordered_detail::hash_local_iterator< + value_allocator, boost::unordered_detail::ungrouped> + local_iterator; + typedef boost::unordered_detail::hash_const_iterator< + value_allocator, boost::unordered_detail::ungrouped> + const_iterator; + typedef boost::unordered_detail::hash_iterator< + value_allocator, boost::unordered_detail::ungrouped> + iterator; + +#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582) + private: +#endif + + table table_; + + BOOST_DEDUCED_TYPENAME types::iterator_base const& + get(const_iterator const& it) + { + return boost::unordered_detail::iterator_access::get(it); + } + + public: + + // construct/destroy/copy + + explicit unordered_map( + size_type n = boost::unordered_detail::default_bucket_count, + const hasher &hf = hasher(), + const key_equal &eql = key_equal(), + const allocator_type &a = allocator_type()) + : table_(n, hf, eql, a) + { + } + + explicit unordered_map(allocator_type const& a) + : table_(boost::unordered_detail::default_bucket_count, + hasher(), key_equal(), a) + { + } + + unordered_map(unordered_map const& other, allocator_type const& a) + : table_(other.table_, a) + { + } + + template <class InputIt> + unordered_map(InputIt f, InputIt l) + : table_(boost::unordered_detail::initial_size(f, l), + hasher(), key_equal(), allocator_type()) + { + table_.insert_range(f, l); + } + + template <class InputIt> + unordered_map(InputIt f, InputIt l, + size_type n, + const hasher &hf = hasher(), + const key_equal &eql = key_equal()) + : table_(boost::unordered_detail::initial_size(f, l, n), + hf, eql, allocator_type()) + { + table_.insert_range(f, l); + } + + template <class InputIt> + unordered_map(InputIt f, InputIt l, + size_type n, + const hasher &hf, + const key_equal &eql, + const allocator_type &a) + : table_(boost::unordered_detail::initial_size(f, l, n), hf, eql, a) + { + table_.insert_range(f, l); + } + + ~unordered_map() {} + +#if !defined(BOOST_NO_RVALUE_REFERENCES) + unordered_map(unordered_map&& other) + : table_(other.table_, boost::unordered_detail::move_tag()) + { + } + + unordered_map(unordered_map&& other, allocator_type const& a) + : table_(other.table_, a, boost::unordered_detail::move_tag()) + { + } + + unordered_map& operator=(unordered_map&& x) + { + table_.move(x.table_); + return *this; + } +#else + unordered_map(boost::unordered_detail::move_from< + unordered_map<K, T, H, P, A> + > other) + : table_(other.source.table_, boost::unordered_detail::move_tag()) + { + } + +#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0593) + unordered_map& operator=(unordered_map x) + { + table_.move(x.table_); + return *this; + } +#endif +#endif + +#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST) + unordered_map(std::initializer_list<value_type> list, + size_type n = boost::unordered_detail::default_bucket_count, + const hasher &hf = hasher(), + const key_equal &eql = key_equal(), + const allocator_type &a = allocator_type()) + : table_(boost::unordered_detail::initial_size( + list.begin(), list.end(), n), + hf, eql, a) + { + table_.insert_range(list.begin(), list.end()); + } + + unordered_map& operator=(std::initializer_list<value_type> list) + { + table_.clear(); + table_.insert_range(list.begin(), list.end()); + return *this; + } +#endif + + allocator_type get_allocator() const + { + return table_.node_alloc(); + } + + // size and capacity + + bool empty() const + { + return table_.size_ == 0; + } + + size_type size() const + { + return table_.size_; + } + + size_type max_size() const + { + return table_.max_size(); + } + + // iterators + + iterator begin() + { + return iterator(table_.begin()); + } + + const_iterator begin() const + { + return const_iterator(table_.begin()); + } + + iterator end() + { + return iterator(table_.end()); + } + + const_iterator end() const + { + return const_iterator(table_.end()); + } + + const_iterator cbegin() const + { + return const_iterator(table_.begin()); + } + + const_iterator cend() const + { + return const_iterator(table_.end()); + } + + // modifiers + +#if defined(BOOST_UNORDERED_STD_FORWARD) + template <class... Args> + std::pair<iterator, bool> emplace(Args&&... args) + { + return boost::unordered_detail::pair_cast<iterator, bool>( + table_.emplace(std::forward<Args>(args)...)); + } + + template <class... Args> + iterator emplace_hint(const_iterator, Args&&... args) + { + return iterator(table_.emplace(std::forward<Args>(args)...).first); + } +#else + + #if !BOOST_WORKAROUND(__SUNPRO_CC, BOOST_TESTED_AT(0x5100)) + std::pair<iterator, bool> emplace(value_type const& v = value_type()) + { + return boost::unordered_detail::pair_cast<iterator, bool>( + table_.emplace(v)); + } + + iterator emplace_hint(const_iterator, + value_type const& v = value_type()) + { + return iterator(table_.emplace(v).first); + } + #endif + +#define BOOST_UNORDERED_EMPLACE(z, n, _) \ + template < \ + BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \ + > \ + std::pair<iterator, bool> emplace( \ + BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \ + ) \ + { \ + return boost::unordered_detail::pair_cast<iterator, bool>( \ + table_.emplace( \ + BOOST_UNORDERED_CALL_PARAMS(z, n) \ + )); \ + } \ + \ + template < \ + BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \ + > \ + iterator emplace_hint(const_iterator, \ + BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \ + ) \ + { \ + return iterator(table_.emplace( \ + BOOST_UNORDERED_CALL_PARAMS(z, n)).first); \ + } + + BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT, + BOOST_UNORDERED_EMPLACE, _) + +#undef BOOST_UNORDERED_EMPLACE + +#endif + + std::pair<iterator, bool> insert(const value_type& obj) + { + return boost::unordered_detail::pair_cast<iterator, bool>( + table_.emplace(obj)); + } + + iterator insert(const_iterator, const value_type& obj) + { + return iterator(table_.emplace(obj).first); + } + + template <class InputIt> + void insert(InputIt first, InputIt last) + { + table_.insert_range(first, last); + } + +#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST) + void insert(std::initializer_list<value_type> list) + { + table_.insert_range(list.begin(), list.end()); + } +#endif + + iterator erase(const_iterator position) + { + return iterator(table_.erase_return_iterator(get(position))); + } + + size_type erase(const key_type& k) + { + return table_.erase_key(k); + } + + iterator erase(const_iterator first, const_iterator last) + { + return iterator(table_.erase_range(get(first), get(last))); + } + + void quick_erase(const_iterator position) + { + table_.erase(get(position)); + } + + void erase_return_void(const_iterator position) + { + table_.erase(get(position)); + } + + void clear() + { + table_.clear(); + } + + void swap(unordered_map& other) + { + table_.swap(other.table_); + } + + // observers + + hasher hash_function() const + { + return table_.hash_function(); + } + + key_equal key_eq() const + { + return table_.key_eq(); + } + + mapped_type& operator[](const key_type &k) + { + return table_[k].second; + } + + mapped_type& at(const key_type& k) + { + return table_.at(k).second; + } + + mapped_type const& at(const key_type& k) const + { + return table_.at(k).second; + } + + // lookup + + iterator find(const key_type& k) + { + return iterator(table_.find(k)); + } + + const_iterator find(const key_type& k) const + { + return const_iterator(table_.find(k)); + } + + template <class CompatibleKey, class CompatibleHash, + class CompatiblePredicate> + iterator find( + CompatibleKey const& k, + CompatibleHash const& hash, + CompatiblePredicate const& eq) + { + return iterator(table_.find(k, hash, eq)); + } + + template <class CompatibleKey, class CompatibleHash, + class CompatiblePredicate> + const_iterator find( + CompatibleKey const& k, + CompatibleHash const& hash, + CompatiblePredicate const& eq) const + { + return iterator(table_.find(k, hash, eq)); + } + + size_type count(const key_type& k) const + { + return table_.count(k); + } + + std::pair<iterator, iterator> + equal_range(const key_type& k) + { + return boost::unordered_detail::pair_cast< + iterator, iterator>( + table_.equal_range(k)); + } + + std::pair<const_iterator, const_iterator> + equal_range(const key_type& k) const + { + return boost::unordered_detail::pair_cast< + const_iterator, const_iterator>( + table_.equal_range(k)); + } + + // bucket interface + + size_type bucket_count() const + { + return table_.bucket_count_; + } + + size_type max_bucket_count() const + { + return table_.max_bucket_count(); + } + + size_type bucket_size(size_type n) const + { + return table_.bucket_size(n); + } + + size_type bucket(const key_type& k) const + { + return table_.bucket_index(k); + } + + local_iterator begin(size_type n) + { + return local_iterator(table_.bucket_begin(n)); + } + + const_local_iterator begin(size_type n) const + { + return const_local_iterator(table_.bucket_begin(n)); + } + + local_iterator end(size_type) + { + return local_iterator(); + } + + const_local_iterator end(size_type) const + { + return const_local_iterator(); + } + + const_local_iterator cbegin(size_type n) const + { + return const_local_iterator(table_.bucket_begin(n)); + } + + const_local_iterator cend(size_type) const + { + return const_local_iterator(); + } + + // hash policy + + float load_factor() const + { + return table_.load_factor(); + } + + float max_load_factor() const + { + return table_.mlf_; + } + + void max_load_factor(float m) + { + table_.max_load_factor(m); + } + + void rehash(size_type n) + { + table_.rehash(n); + } + +#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582) + friend bool operator==<K, T, H, P, A>( + unordered_map const&, unordered_map const&); + friend bool operator!=<K, T, H, P, A>( + unordered_map const&, unordered_map const&); +#endif + }; // class template unordered_map + + template <class K, class T, class H, class P, class A> + inline bool operator==(unordered_map<K, T, H, P, A> const& m1, + unordered_map<K, T, H, P, A> const& m2) + { +#if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613)) + struct dummy { unordered_map<K,T,H,P,A> x; }; +#endif + return m1.table_.equals(m2.table_); + } + + template <class K, class T, class H, class P, class A> + inline bool operator!=(unordered_map<K, T, H, P, A> const& m1, + unordered_map<K, T, H, P, A> const& m2) + { +#if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613)) + struct dummy { unordered_map<K,T,H,P,A> x; }; +#endif + return !m1.table_.equals(m2.table_); + } + + template <class K, class T, class H, class P, class A> + inline void swap(unordered_map<K, T, H, P, A> &m1, + unordered_map<K, T, H, P, A> &m2) + { +#if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613)) + struct dummy { unordered_map<K,T,H,P,A> x; }; +#endif + m1.swap(m2); + } + + template <class K, class T, class H, class P, class A> + class unordered_multimap + { + public: + + typedef K key_type; + typedef std::pair<const K, T> value_type; + typedef T mapped_type; + typedef H hasher; + typedef P key_equal; + typedef A allocator_type; + +#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582) + private: +#endif + + typedef BOOST_DEDUCED_TYPENAME + boost::unordered_detail::rebind_wrap< + allocator_type, value_type>::type + value_allocator; + + typedef boost::unordered_detail::multimap<K, H, P, + value_allocator> types; + typedef BOOST_DEDUCED_TYPENAME types::impl table; + + typedef BOOST_DEDUCED_TYPENAME types::iterator_base iterator_base; + + public: + + typedef BOOST_DEDUCED_TYPENAME + value_allocator::pointer pointer; + typedef BOOST_DEDUCED_TYPENAME + value_allocator::const_pointer const_pointer; + typedef BOOST_DEDUCED_TYPENAME + value_allocator::reference reference; + typedef BOOST_DEDUCED_TYPENAME + value_allocator::const_reference const_reference; + + typedef std::size_t size_type; + typedef std::ptrdiff_t difference_type; + + typedef boost::unordered_detail::hash_const_local_iterator< + value_allocator, boost::unordered_detail::grouped> + const_local_iterator; + typedef boost::unordered_detail::hash_local_iterator< + value_allocator, boost::unordered_detail::grouped> + local_iterator; + typedef boost::unordered_detail::hash_const_iterator< + value_allocator, boost::unordered_detail::grouped> + const_iterator; + typedef boost::unordered_detail::hash_iterator< + value_allocator, boost::unordered_detail::grouped> + iterator; + +#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582) + private: +#endif + + table table_; + + BOOST_DEDUCED_TYPENAME types::iterator_base const& + get(const_iterator const& it) + { + return boost::unordered_detail::iterator_access::get(it); + } + + public: + + // construct/destroy/copy + + explicit unordered_multimap( + size_type n = boost::unordered_detail::default_bucket_count, + const hasher &hf = hasher(), + const key_equal &eql = key_equal(), + const allocator_type &a = allocator_type()) + : table_(n, hf, eql, a) + { + } + + explicit unordered_multimap(allocator_type const& a) + : table_(boost::unordered_detail::default_bucket_count, + hasher(), key_equal(), a) + { + } + + unordered_multimap(unordered_multimap const& other, + allocator_type const& a) + : table_(other.table_, a) + { + } + + template <class InputIt> + unordered_multimap(InputIt f, InputIt l) + : table_(boost::unordered_detail::initial_size(f, l), + hasher(), key_equal(), allocator_type()) + { + table_.insert_range(f, l); + } + + template <class InputIt> + unordered_multimap(InputIt f, InputIt l, + size_type n, + const hasher &hf = hasher(), + const key_equal &eql = key_equal()) + : table_(boost::unordered_detail::initial_size(f, l, n), + hf, eql, allocator_type()) + { + table_.insert_range(f, l); + } + + template <class InputIt> + unordered_multimap(InputIt f, InputIt l, + size_type n, + const hasher &hf, + const key_equal &eql, + const allocator_type &a) + : table_(boost::unordered_detail::initial_size(f, l, n), hf, eql, a) + { + table_.insert_range(f, l); + } + + ~unordered_multimap() {} + +#if !defined(BOOST_NO_RVALUE_REFERENCES) + unordered_multimap(unordered_multimap&& other) + : table_(other.table_, boost::unordered_detail::move_tag()) + { + } + + unordered_multimap(unordered_multimap&& other, allocator_type const& a) + : table_(other.table_, a, boost::unordered_detail::move_tag()) + { + } + + unordered_multimap& operator=(unordered_multimap&& x) + { + table_.move(x.table_); + return *this; + } +#else + unordered_multimap(boost::unordered_detail::move_from< + unordered_multimap<K, T, H, P, A> + > other) + : table_(other.source.table_, boost::unordered_detail::move_tag()) + { + } + +#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0593) + unordered_multimap& operator=(unordered_multimap x) + { + table_.move(x.table_); + return *this; + } +#endif +#endif + +#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST) + unordered_multimap(std::initializer_list<value_type> list, + size_type n = boost::unordered_detail::default_bucket_count, + const hasher &hf = hasher(), + const key_equal &eql = key_equal(), + const allocator_type &a = allocator_type()) + : table_(boost::unordered_detail::initial_size( + list.begin(), list.end(), n), + hf, eql, a) + { + table_.insert_range(list.begin(), list.end()); + } + + unordered_multimap& operator=(std::initializer_list<value_type> list) + { + table_.clear(); + table_.insert_range(list.begin(), list.end()); + return *this; + } +#endif + + allocator_type get_allocator() const + { + return table_.node_alloc(); + } + + // size and capacity + + bool empty() const + { + return table_.size_ == 0; + } + + size_type size() const + { + return table_.size_; + } + + size_type max_size() const + { + return table_.max_size(); + } + + // iterators + + iterator begin() + { + return iterator(table_.begin()); + } + + const_iterator begin() const + { + return const_iterator(table_.begin()); + } + + iterator end() + { + return iterator(table_.end()); + } + + const_iterator end() const + { + return const_iterator(table_.end()); + } + + const_iterator cbegin() const + { + return const_iterator(table_.begin()); + } + + const_iterator cend() const + { + return const_iterator(table_.end()); + } + + // modifiers + +#if defined(BOOST_UNORDERED_STD_FORWARD) + template <class... Args> + iterator emplace(Args&&... args) + { + return iterator(table_.emplace(std::forward<Args>(args)...)); + } + + template <class... Args> + iterator emplace_hint(const_iterator, Args&&... args) + { + return iterator(table_.emplace(std::forward<Args>(args)...)); + } +#else + + #if !BOOST_WORKAROUND(__SUNPRO_CC, BOOST_TESTED_AT(0x5100)) + iterator emplace(value_type const& v = value_type()) + { + return iterator(table_.emplace(v)); + } + + iterator emplace_hint(const_iterator, + value_type const& v = value_type()) + { + return iterator(table_.emplace(v)); + } + #endif + +#define BOOST_UNORDERED_EMPLACE(z, n, _) \ + template < \ + BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \ + > \ + iterator emplace( \ + BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \ + ) \ + { \ + return iterator( \ + table_.emplace( \ + BOOST_UNORDERED_CALL_PARAMS(z, n) \ + )); \ + } \ + \ + template < \ + BOOST_UNORDERED_TEMPLATE_ARGS(z, n) \ + > \ + iterator emplace_hint(const_iterator, \ + BOOST_UNORDERED_FUNCTION_PARAMS(z, n) \ + ) \ + { \ + return iterator(table_.emplace( \ + BOOST_UNORDERED_CALL_PARAMS(z, n) \ + )); \ + } + + BOOST_PP_REPEAT_FROM_TO(1, BOOST_UNORDERED_EMPLACE_LIMIT, + BOOST_UNORDERED_EMPLACE, _) + +#undef BOOST_UNORDERED_EMPLACE + +#endif + + iterator insert(const value_type& obj) + { + return iterator(table_.emplace(obj)); + } + + iterator insert(const_iterator, const value_type& obj) + { + return iterator(table_.emplace(obj)); + } + + template <class InputIt> + void insert(InputIt first, InputIt last) + { + table_.insert_range(first, last); + } + +#if !defined(BOOST_NO_0X_HDR_INITIALIZER_LIST) + void insert(std::initializer_list<value_type> list) + { + table_.insert_range(list.begin(), list.end()); + } +#endif + + iterator erase(const_iterator position) + { + return iterator(table_.erase_return_iterator(get(position))); + } + + size_type erase(const key_type& k) + { + return table_.erase_key(k); + } + + iterator erase(const_iterator first, const_iterator last) + { + return iterator(table_.erase_range(get(first), get(last))); + } + + void quick_erase(const_iterator position) + { + table_.erase(get(position)); + } + + void erase_return_void(const_iterator position) + { + table_.erase(get(position)); + } + + void clear() + { + table_.clear(); + } + + void swap(unordered_multimap& other) + { + table_.swap(other.table_); + } + + // observers + + hasher hash_function() const + { + return table_.hash_function(); + } + + key_equal key_eq() const + { + return table_.key_eq(); + } + + // lookup + + iterator find(const key_type& k) + { + return iterator(table_.find(k)); + } + + const_iterator find(const key_type& k) const + { + return const_iterator(table_.find(k)); + } + + template <class CompatibleKey, class CompatibleHash, + class CompatiblePredicate> + iterator find( + CompatibleKey const& k, + CompatibleHash const& hash, + CompatiblePredicate const& eq) + { + return iterator(table_.find(k, hash, eq)); + } + + template <class CompatibleKey, class CompatibleHash, + class CompatiblePredicate> + const_iterator find( + CompatibleKey const& k, + CompatibleHash const& hash, + CompatiblePredicate const& eq) const + { + return iterator(table_.find(k, hash, eq)); + } + + size_type count(const key_type& k) const + { + return table_.count(k); + } + + std::pair<iterator, iterator> + equal_range(const key_type& k) + { + return boost::unordered_detail::pair_cast< + iterator, iterator>( + table_.equal_range(k)); + } + + std::pair<const_iterator, const_iterator> + equal_range(const key_type& k) const + { + return boost::unordered_detail::pair_cast< + const_iterator, const_iterator>( + table_.equal_range(k)); + } + + // bucket interface + + size_type bucket_count() const + { + return table_.bucket_count_; + } + + size_type max_bucket_count() const + { + return table_.max_bucket_count(); + } + + size_type bucket_size(size_type n) const + { + return table_.bucket_size(n); + } + + size_type bucket(const key_type& k) const + { + return table_.bucket_index(k); + } + + local_iterator begin(size_type n) + { + return local_iterator(table_.bucket_begin(n)); + } + + const_local_iterator begin(size_type n) const + { + return const_local_iterator(table_.bucket_begin(n)); + } + + local_iterator end(size_type) + { + return local_iterator(); + } + + const_local_iterator end(size_type) const + { + return const_local_iterator(); + } + + const_local_iterator cbegin(size_type n) const + { + return const_local_iterator(table_.bucket_begin(n)); + } + + const_local_iterator cend(size_type) const + { + return const_local_iterator(); + } + + // hash policy + + float load_factor() const + { + return table_.load_factor(); + } + + float max_load_factor() const + { + return table_.mlf_; + } + + void max_load_factor(float m) + { + table_.max_load_factor(m); + } + + void rehash(size_type n) + { + table_.rehash(n); + } + +#if !BOOST_WORKAROUND(__BORLANDC__, < 0x0582) + friend bool operator==<K, T, H, P, A>( + unordered_multimap const&, unordered_multimap const&); + friend bool operator!=<K, T, H, P, A>( + unordered_multimap const&, unordered_multimap const&); +#endif + }; // class template unordered_multimap + + template <class K, class T, class H, class P, class A> + inline bool operator==(unordered_multimap<K, T, H, P, A> const& m1, + unordered_multimap<K, T, H, P, A> const& m2) + { +#if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613)) + struct dummy { unordered_multimap<K,T,H,P,A> x; }; +#endif + return m1.table_.equals(m2.table_); + } + + template <class K, class T, class H, class P, class A> + inline bool operator!=(unordered_multimap<K, T, H, P, A> const& m1, + unordered_multimap<K, T, H, P, A> const& m2) + { +#if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613)) + struct dummy { unordered_multimap<K,T,H,P,A> x; }; +#endif + return !m1.table_.equals(m2.table_); + } + + template <class K, class T, class H, class P, class A> + inline void swap(unordered_multimap<K, T, H, P, A> &m1, + unordered_multimap<K, T, H, P, A> &m2) + { +#if BOOST_WORKAROUND(__CODEGEARC__, BOOST_TESTED_AT(0x0613)) + struct dummy { unordered_multimap<K,T,H,P,A> x; }; +#endif + m1.swap(m2); + } + +} // namespace boost + +#if defined(BOOST_MSVC) +#pragma warning(pop) +#endif + +#endif // BOOST_UNORDERED_UNORDERED_MAP_HPP_INCLUDED diff --git a/3rdParty/Boost/src/boost/unordered/unordered_map_fwd.hpp b/3rdParty/Boost/src/boost/unordered/unordered_map_fwd.hpp new file mode 100644 index 0000000..5e9bb07 --- /dev/null +++ b/3rdParty/Boost/src/boost/unordered/unordered_map_fwd.hpp @@ -0,0 +1,53 @@ + +// Copyright (C) 2008-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) + +#ifndef BOOST_UNORDERED_MAP_FWD_HPP_INCLUDED +#define BOOST_UNORDERED_MAP_FWD_HPP_INCLUDED + +#if defined(_MSC_VER) && (_MSC_VER >= 1020) +# pragma once +#endif + +#include <boost/config.hpp> +#include <memory> +#include <functional> +#include <boost/functional/hash_fwd.hpp> + +namespace boost +{ + template <class K, + class T, + class H = hash<K>, + class P = std::equal_to<K>, + class A = std::allocator<std::pair<const K, T> > > + class unordered_map; + template <class K, class T, class H, class P, class A> + bool operator==(unordered_map<K, T, H, P, A> const&, + unordered_map<K, T, H, P, A> const&); + template <class K, class T, class H, class P, class A> + bool operator!=(unordered_map<K, T, H, P, A> const&, + unordered_map<K, T, H, P, A> const&); + template <class K, class T, class H, class P, class A> + void swap(unordered_map<K, T, H, P, A>&, + unordered_map<K, T, H, P, A>&); + + template <class K, + class T, + class H = hash<K>, + class P = std::equal_to<K>, + class A = std::allocator<std::pair<const K, T> > > + class unordered_multimap; + template <class K, class T, class H, class P, class A> + bool operator==(unordered_multimap<K, T, H, P, A> const&, + unordered_multimap<K, T, H, P, A> const&); + template <class K, class T, class H, class P, class A> + bool operator!=(unordered_multimap<K, T, H, P, A> const&, + unordered_multimap<K, T, H, P, A> const&); + template <class K, class T, class H, class P, class A> + void swap(unordered_multimap<K, T, H, P, A>&, + unordered_multimap<K, T, H, P, A>&); +} + +#endif diff --git a/3rdParty/Boost/src/boost/unordered_map.hpp b/3rdParty/Boost/src/boost/unordered_map.hpp new file mode 100644 index 0000000..00d3c91 --- /dev/null +++ b/3rdParty/Boost/src/boost/unordered_map.hpp @@ -0,0 +1,18 @@ + +// Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard. +// Copyright (C) 2005-2008 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) + +// See http://www.boost.org/libs/unordered for documentation + +#ifndef BOOST_UNORDERED_MAP_HPP_INCLUDED +#define BOOST_UNORDERED_MAP_HPP_INCLUDED + +#if defined(_MSC_VER) && (_MSC_VER >= 1020) +# pragma once +#endif + +#include <boost/unordered/unordered_map.hpp> + +#endif // BOOST_UNORDERED_MAP_HPP_INCLUDED diff --git a/3rdParty/Boost/update.sh b/3rdParty/Boost/update.sh index 49d55ba..5e5a9ef 100755 --- a/3rdParty/Boost/update.sh +++ b/3rdParty/Boost/update.sh @@ -30,6 +30,7 @@ fi uuid/uuid_generators.hpp \ variant.hpp \ regex.hpp \ + boost/unordered_map.hpp \ $TARGET_DIR rm -rf $TARGET_DIR/libs/config diff --git a/Swiften/JID/JID.cpp b/Swiften/JID/JID.cpp index cf5317e..3ecd881 100644 --- a/Swiften/JID/JID.cpp +++ b/Swiften/JID/JID.cpp @@ -4,13 +4,28 @@ * See Documentation/Licenses/GPLv3.txt for more information. */ -#include <stringprep.h> +#define SWIFTEN_CACHE_JID_PREP + #include <vector> #include <iostream> +#include <Swiften/Base/String.h> +#ifdef SWIFTEN_CACHE_JID_PREP +#include <boost/unordered_map.hpp> +#endif +#include <stringprep.h> + #include "Swiften/JID/JID.h" #include "Swiften/IDN/StringPrep.h" +#ifdef SWIFTEN_CACHE_JID_PREP +typedef boost::unordered_map<std::string, Swift::String> PrepCache; + +static PrepCache nodePrepCache; +static PrepCache domainPrepCache; +static PrepCache resourcePrepCache; +#endif + namespace Swift { JID::JID(const char* jid) { @@ -56,9 +71,31 @@ void JID::initializeFromString(const String& jid) { void JID::nameprepAndSetComponents(const String& node, const String& domain, const String& resource) { +#ifndef SWIFTEN_CACHE_JID_PREP node_ = StringPrep::getPrepared(node, StringPrep::NamePrep); domain_ = StringPrep::getPrepared(domain, StringPrep::XMPPNodePrep); resource_ = StringPrep::getPrepared(resource, StringPrep::XMPPResourcePrep); +#else + std::pair<PrepCache::iterator, bool> r; + + r = nodePrepCache.insert(std::make_pair(node.getUTF8String(), String())); + if (r.second) { + r.first->second = StringPrep::getPrepared(node, StringPrep::NamePrep); + } + node_ = r.first->second; + + r = domainPrepCache.insert(std::make_pair(domain.getUTF8String(), String())); + if (r.second) { + r.first->second = StringPrep::getPrepared(domain, StringPrep::XMPPNodePrep); + } + domain_ = r.first->second; + + r = resourcePrepCache.insert(std::make_pair(resource.getUTF8String(), String())); + if (r.second) { + r.first->second = StringPrep::getPrepared(resource, StringPrep::XMPPResourcePrep); + } + resource_ = r.first->second; +#endif } String JID::toString() const { |