x
Yes
No
Do you want to visit DriveHQ English website?
Inicio
Características
Precios
Prueba gratuita
Software cliente
Acerca de nosotros
Servidor de archivos
|
Solución de copias de seguridad
|
Servidor FTP
|
Servidor de correo electrónico
|
Alojamiento web
|
Software cliente
Servidor de archivos
Solución de copia de seguridad
Servidor FTP
Servidor de correo electrónico
Alojamiento web
Software cliente
tree.hpp - Hosted on DriveHQ Cloud IT Platform
Arriba
Subir
Descargar
Compartir
Publicar
Nueva carpeta
Nuevo archivo
Copiar
Cortar
Eliminar
Pegar
Clasificación
Actualizar
Ruta de la carpeta: \\game3dprogramming\materials\GameFactory\GameFactoryDemo\references\boost_1_35_0\boost\interprocess\containers\detail\tree.hpp
Girar
Efecto
Propiedad
Historial
////////////////////////////////////////////////////////////////////////////// // // (C) Copyright Ion Gaztanaga 2005-2008. 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/interprocess for documentation. // ////////////////////////////////////////////////////////////////////////////// // // This file comes from SGI's stl_tree file. Modified by Ion Gaztanaga 2005. // Renaming, isolating and porting to generic algorithms. Pointer typedef // set to allocator::pointer to allow placing it in shared memory. // /////////////////////////////////////////////////////////////////////////////// /* * * Copyright (c) 1994 * Hewlett-Packard Company * * Permission to use, copy, modify, distribute and sell this software * and its documentation for any purpose is hereby granted without fee, * provided that the above copyright notice appear in all copies and * that both that copyright notice and this permission notice appear * in supporting documentation. Hewlett-Packard Company makes no * representations about the suitability of this software for any * purpose. It is provided "as is" without express or implied warranty. * * * Copyright (c) 1996 * Silicon Graphics Computer Systems, Inc. * * Permission to use, copy, modify, distribute and sell this software * and its documentation for any purpose is hereby granted without fee, * provided that the above copyright notice appear in all copies and * that both that copyright notice and this permission notice appear * in supporting documentation. Silicon Graphics makes no * representations about the suitability of this software for any * purpose. It is provided "as is" without express or implied warranty. * */ #ifndef BOOST_INTERPROCESS_TREE_HPP #define BOOST_INTERPROCESS_TREE_HPP #include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
namespace boost { namespace interprocess { namespace detail { template
struct value_compare_impl : public KeyCompare { typedef Value value_type; typedef KeyCompare key_compare; typedef KeyOfValue key_of_value; typedef Key key_type; value_compare_impl(key_compare kcomp) : key_compare(kcomp) {} const key_compare &key_comp() const { return static_cast
(*this); } key_compare &key_comp() { return static_cast
(*this); } template
bool operator()(const A &a, const B &b) const { return key_compare::operator()(KeyOfValue()(a), KeyOfValue()(b)); } }; template
struct rbtree_node : public bi::make_set_base_hook < bi::void_pointer
, bi::link_mode
, bi::optimize_size
>::type { typedef typename bi::make_set_base_hook < bi::void_pointer
, bi::link_mode
, bi::optimize_size
>::type hook_type; typedef T value_type; typedef rbtree_node
node_type; #ifndef BOOST_INTERPROCESS_RVALUE_REFERENCE template
rbtree_node(const Convertible &conv) : m_data(conv){} #else template
rbtree_node(Convertible &&conv) : m_data(forward
(conv)){} #endif rbtree_node &operator=(const rbtree_node &other) { do_assign(other.m_data); return *this; } T m_data; private: template
void do_assign(const std::pair
&p) { const_cast
(m_data.first) = p.first; m_data.second = p.second; } template
void do_assign(const V &v) { m_data = v; } public: #ifndef BOOST_INTERPROCESS_RVALUE_REFERENCE template
static void construct(node_type *ptr, const Convertible &value) { new(ptr) node_type(value); } template
static void construct(node_type *ptr, const detail::moved_object
> &value) { //std::pair is not movable so we define our own type and overwrite it typedef detail::pair
hack_pair_t; typedef rbtree_node
hack_node_t; new((void*)ptr) hack_node_t(value); } #else template
static void construct(node_type *ptr, Convertible &&value) { new(ptr) node_type(forward
(value)); } template
static void construct(node_type *ptr, std::pair
&&value) { //std::pair is not movable so we define our own type and overwrite it typedef detail::pair
hack_pair_t; typedef rbtree_node
hack_node_t; new((void*)ptr) hack_node_t(value); } #endif }; }//namespace detail { template
struct has_own_construct_from_it < boost::interprocess::detail::rbtree_node
> { static const bool value = true; }; namespace detail { template
struct intrusive_rbtree_type { typedef typename A::value_type value_type; typedef typename detail::pointer_to_other
::type void_pointer; typedef typename detail::rbtree_node
node_type; typedef node_compare
node_compare_type; typedef typename bi::make_rbtree
,bi::base_hook
,bi::constant_time_size
,bi::size_type
>::type container_type; typedef container_type type ; }; } //namespace detail { namespace detail { template
class rbtree : protected detail::node_alloc_holder
>::type > { typedef typename detail::intrusive_rbtree_type
>::type Icont; typedef detail::node_alloc_holder
AllocHolder; typedef typename AllocHolder::NodePtr NodePtr; typedef rbtree < Key, Value, KeyOfValue , KeyCompare, A> ThisType; typedef typename AllocHolder::NodeAlloc NodeAlloc; typedef typename AllocHolder::ValAlloc ValAlloc; typedef typename AllocHolder::Node Node; typedef typename Icont::iterator iiterator; typedef typename Icont::const_iterator iconst_iterator; typedef detail::allocator_destroyer
Destroyer; typedef typename AllocHolder::allocator_v1 allocator_v1; typedef typename AllocHolder::allocator_v2 allocator_v2; typedef typename AllocHolder::alloc_version alloc_version; class RecyclingCloner; friend class RecyclingCloner; class RecyclingCloner { public: RecyclingCloner(AllocHolder &holder, Icont &irbtree) : m_holder(holder), m_icont(irbtree) {} NodePtr operator()(const Node &other) const { // if(!m_icont.empty()){ if(NodePtr p = m_icont.unlink_leftmost_without_rebalance()){ //First recycle a node (this can't throw) //NodePtr p = m_icont.unlink_leftmost_without_rebalance(); try{ //This can throw *p = other; return p; } catch(...){ //If there is an exception destroy the whole source m_holder.destroy_node(p); while((p = m_icont.unlink_leftmost_without_rebalance())){ m_holder.destroy_node(p); } throw; } } else{ return m_holder.create_node(other); } } AllocHolder &m_holder; Icont &m_icont; }; public: typedef Key key_type; typedef Value value_type; typedef A allocator_type; typedef KeyCompare key_compare; typedef value_compare_impl< Key, Value , KeyCompare, KeyOfValue> value_compare; typedef typename A::pointer pointer; typedef typename A::const_pointer const_pointer; typedef typename A::reference reference; typedef typename A::const_reference const_reference; typedef typename A::size_type size_type; typedef typename A::difference_type difference_type; typedef difference_type rbtree_difference_type; typedef pointer rbtree_pointer; typedef const_pointer rbtree_const_pointer; typedef reference rbtree_reference; typedef const_reference rbtree_const_reference; typedef NodeAlloc stored_allocator_type; private: template
struct key_node_compare : private KeyValueCompare { key_node_compare(KeyValueCompare comp) : KeyValueCompare(comp) {} template
bool operator()(const Node &n, const KeyType &k) const { return KeyValueCompare::operator()(n.m_data, k); } template
bool operator()(const KeyType &k, const Node &n) const { return KeyValueCompare::operator()(k, n.m_data); } }; typedef key_node_compare
KeyNodeCompare; public: //rbtree const_iterator class const_iterator : public std::iterator < std::bidirectional_iterator_tag , value_type , rbtree_difference_type , rbtree_const_pointer , rbtree_const_reference> { protected: typedef typename Icont::iterator iiterator; iiterator m_it; explicit const_iterator(iiterator it) : m_it(it){} void prot_incr() { ++m_it; } void prot_decr() { --m_it; } private: iiterator get() { return this->m_it; } public: friend class rbtree
; typedef rbtree_difference_type difference_type; //Constructors const_iterator() : m_it() {} //Pointer like operators const_reference operator*() const { return m_it->m_data; } const_pointer operator->() const { return const_pointer(&m_it->m_data); } //Increment / Decrement const_iterator& operator++() { prot_incr(); return *this; } const_iterator operator++(int) { iiterator tmp = m_it; ++*this; return const_iterator(tmp); } const_iterator& operator--() { prot_decr(); return *this; } const_iterator operator--(int) { iiterator tmp = m_it; --*this; return const_iterator(tmp); } //Comparison operators bool operator== (const const_iterator& r) const { return m_it == r.m_it; } bool operator!= (const const_iterator& r) const { return m_it != r.m_it; } }; //rbtree iterator class iterator : public const_iterator { private: explicit iterator(iiterator it) : const_iterator(it) {} iiterator get() { return this->m_it; } public: friend class rbtree
; typedef rbtree_pointer pointer; typedef rbtree_reference reference; //Constructors iterator(){} //Pointer like operators reference operator*() const { return this->m_it->m_data; } pointer operator->() const { return pointer(&this->m_it->m_data); } //Increment / Decrement iterator& operator++() { this->prot_incr(); return *this; } iterator operator++(int) { iiterator tmp = this->m_it; ++*this; return iterator(tmp); } iterator& operator--() { this->prot_decr(); return *this; } iterator operator--(int) { iterator tmp = *this; --*this; return tmp; } }; typedef std::reverse_iterator
reverse_iterator; typedef std::reverse_iterator
const_reverse_iterator; rbtree(const key_compare& comp = key_compare(), const allocator_type& a = allocator_type()) : AllocHolder(a, comp) {} template
rbtree(InputIterator first, InputIterator last, const key_compare& comp, const allocator_type& a, bool unique_insertion) : AllocHolder(a, comp) { typedef typename std::iterator_traits
::iterator_category ItCat; priv_create_and_insert_nodes(first, last, unique_insertion, alloc_version(), ItCat()); } rbtree(const rbtree& x) : AllocHolder(x, x.key_comp()) { this->icont().clone_from (x.icont(), typename AllocHolder::cloner(*this), Destroyer(this->node_alloc())); } #ifndef BOOST_INTERPROCESS_RVALUE_REFERENCE rbtree(const detail::moved_object
& x) : AllocHolder(x.get(), x.get().key_comp()) { this->swap(x.get()); } #else rbtree(rbtree &&x) : AllocHolder(x, x.key_comp()) { this->swap(x); } #endif ~rbtree() { this->clear(); } rbtree& operator=(const rbtree& x) { if (this != &x) { //Transfer all the nodes to a temporary tree //If anything goes wrong, all the nodes will be destroyed //automatically Icont other_tree(this->icont().value_comp()); other_tree.swap(this->icont()); //Now recreate the source tree reusing nodes stored by other_tree this->icont().clone_from (x.icont() , RecyclingCloner(*this, other_tree) //, AllocHolder::cloner(*this) , Destroyer(this->node_alloc())); //If there are remaining nodes, destroy them NodePtr p; while((p = other_tree.unlink_leftmost_without_rebalance())){ AllocHolder::destroy_node(p); } } return *this; } #ifndef BOOST_INTERPROCESS_RVALUE_REFERENCE rbtree& operator=(const detail::moved_object
& mx) { this->clear(); this->swap(mx.get()); return *this; } #else rbtree& operator=(rbtree &&mx) { this->clear(); this->swap(mx); return *this; } #endif public: // accessors: value_compare value_comp() const { return this->icont().value_comp().value_comp(); } key_compare key_comp() const { return this->icont().value_comp().value_comp().key_comp(); } allocator_type get_allocator() const { return allocator_type(this->node_alloc()); } const stored_allocator_type &get_stored_allocator() const { return this->node_alloc(); } stored_allocator_type &get_stored_allocator() { return this->node_alloc(); } iterator begin() { return iterator(this->icont().begin()); } const_iterator begin() const { return const_iterator(this->non_const_icont().begin()); } iterator end() { return iterator(this->icont().end()); } const_iterator end() const { return const_iterator(this->non_const_icont().end()); } reverse_iterator rbegin() { return reverse_iterator(end()); } const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); } reverse_iterator rend() { return reverse_iterator(begin()); } const_reverse_iterator rend() const { return const_reverse_iterator(begin()); } bool empty() const { return !this->size(); } size_type size() const { return this->icont().size(); } size_type max_size() const { return AllocHolder::max_size(); } void swap(ThisType& x) { AllocHolder::swap(x); } #ifndef BOOST_INTERPROCESS_RVALUE_REFERENCE void swap(const detail::moved_object
& mt) { this->swap(mt.get()); } #else void swap(rbtree &&mt) { this->swap(mt); } #endif public: typedef typename Icont::insert_commit_data insert_commit_data; // insert/erase std::pair
insert_unique_check (const key_type& key, insert_commit_data &data) { std::pair
ret = this->icont().insert_unique_check(key, KeyNodeCompare(value_comp()), data); return std::pair
(iterator(ret.first), ret.second); } std::pair
insert_unique_check (const_iterator hint, const key_type& key, insert_commit_data &data) { std::pair
ret = this->icont().insert_unique_check(hint.get(), key, KeyNodeCompare(value_comp()), data); return std::pair
(iterator(ret.first), ret.second); } iterator insert_unique_commit(const value_type& v, insert_commit_data &data) { NodePtr tmp = AllocHolder::create_node(v); iiterator it(this->icont().insert_unique_commit(*tmp, data)); return iterator(it); } #ifndef BOOST_INTERPROCESS_RVALUE_REFERENCE template
iterator insert_unique_commit (const detail::moved_object
& mv, insert_commit_data &data) { NodePtr tmp = AllocHolder::create_node(mv); iiterator it(this->icont().insert_unique_commit(*tmp, data)); return iterator(it); } #else template
iterator insert_unique_commit (MovableConvertible && mv, insert_commit_data &data) { NodePtr tmp = AllocHolder::create_node(forward
(mv)); iiterator it(this->icont().insert_unique_commit(*tmp, data)); return iterator(it); } #endif std::pair
insert_unique(const value_type& v) { insert_commit_data data; std::pair
ret = this->insert_unique_check(KeyOfValue()(v), data); if(!ret.second) return ret; return std::pair
(this->insert_unique_commit(v, data), true); } #ifndef BOOST_INTERPROCESS_RVALUE_REFERENCE template
std::pair
insert_unique (const detail::moved_object
& mv) { insert_commit_data data; std::pair
ret = this->insert_unique_check(KeyOfValue()(mv.get()), data); if(!ret.second) return ret; return std::pair
(this->insert_unique_commit(mv, data), true); } #else template
std::pair
insert_unique(MovableConvertible &&mv) { insert_commit_data data; std::pair
ret = this->insert_unique_check(KeyOfValue()(mv), data); if(!ret.second) return ret; return std::pair
(this->insert_unique_commit(forward
(mv), data), true); } #endif iterator insert_unique(const_iterator hint, const value_type& v) { insert_commit_data data; std::pair
ret = this->insert_unique_check(hint, KeyOfValue()(v), data); if(!ret.second) return ret.first; return this->insert_unique_commit(v, data); } #ifndef BOOST_INTERPROCESS_RVALUE_REFERENCE template
iterator insert_unique (const_iterator hint, const detail::moved_object
&mv) { insert_commit_data data; std::pair
ret = this->insert_unique_check(hint, KeyOfValue()(mv.get()), data); if(!ret.second) return ret.first; return this->insert_unique_commit(mv, data); } #else template
iterator insert_unique (const_iterator hint, MovableConvertible &&mv) { insert_commit_data data; std::pair
ret = this->insert_unique_check(hint, KeyOfValue()(mv), data); if(!ret.second) return ret.first; return this->insert_unique_commit(forward
(mv), data); } #endif template
void insert_unique(InputIterator first, InputIterator last) { if(this->empty()){ //Insert with end hint, to achieve linear //complexity if [first, last) is ordered iterator end(this->end()); for( ; first != last; ++first) this->insert_unique(end, *first); } else{ for( ; first != last; ++first) this->insert_unique(*first); } } iterator insert_equal(const value_type& v) { NodePtr p(AllocHolder::create_node(v)); return iterator(this->icont().insert_equal(this->icont().end(), *p)); } #ifndef BOOST_INTERPROCESS_RVALUE_REFERENCE template
iterator insert_equal(const detail::moved_object
&mv) { NodePtr p(AllocHolder::create_node(mv)); return iterator(this->icont().insert_equal(this->icont().end(), *p)); } #else template
iterator insert_equal(MovableConvertible &&mv) { NodePtr p(AllocHolder::create_node(forward
(mv))); return iterator(this->icont().insert_equal(this->icont().end(), *p)); } #endif iterator insert_equal(const_iterator hint, const value_type& v) { NodePtr p(AllocHolder::create_node(v)); return iterator(this->icont().insert_equal(hint.get(), *p)); } #ifndef BOOST_INTERPROCESS_RVALUE_REFERENCE template
iterator insert_equal(const_iterator hint, const detail::moved_object
&mv) { NodePtr p(AllocHolder::create_node(mv)); return iterator(this->icont().insert_equal(hint.get(), *p)); } #else template
iterator insert_equal(const_iterator hint, MovableConvertible &&mv) { NodePtr p(AllocHolder::create_node(move(mv))); return iterator(this->icont().insert_equal(hint.get(), *p)); } #endif template
void insert_equal(InputIterator first, InputIterator last) { //Insert with end hint, to achieve linear //complexity if [first, last) is ordered iterator end(this->end()); for( ; first != last; ++first) this->insert_equal(end, *first); } iterator erase(const_iterator position) { return iterator(this->icont().erase_and_dispose(position.get(), Destroyer(this->node_alloc()))); } size_type erase(const key_type& k) { return AllocHolder::erase_key(k, KeyNodeCompare(value_comp()), alloc_version()); } iterator erase(const_iterator first, const_iterator last) { return iterator(AllocHolder::erase_range(first.get(), last.get(), alloc_version())); } void clear() { AllocHolder::clear(alloc_version()); } // set operations: iterator find(const key_type& k) { return iterator(this->icont().find(k, KeyNodeCompare(value_comp()))); } const_iterator find(const key_type& k) const { return const_iterator(this->non_const_icont().find(k, KeyNodeCompare(value_comp()))); } size_type count(const key_type& k) const { return size_type(this->icont().count(k, KeyNodeCompare(value_comp()))); } iterator lower_bound(const key_type& k) { return iterator(this->icont().lower_bound(k, KeyNodeCompare(value_comp()))); } const_iterator lower_bound(const key_type& k) const { return const_iterator(this->non_const_icont().lower_bound(k, KeyNodeCompare(value_comp()))); } iterator upper_bound(const key_type& k) { return iterator(this->icont().upper_bound(k, KeyNodeCompare(value_comp()))); } const_iterator upper_bound(const key_type& k) const { return const_iterator(this->non_const_icont().upper_bound(k, KeyNodeCompare(value_comp()))); } std::pair
equal_range(const key_type& k) { std::pair
ret = this->icont().equal_range(k, KeyNodeCompare(value_comp())); return std::pair
(iterator(ret.first), iterator(ret.second)); } std::pair
equal_range(const key_type& k) const { std::pair
ret = this->non_const_icont().equal_range(k, KeyNodeCompare(value_comp())); return std::pair
(const_iterator(ret.first), const_iterator(ret.second)); } private: //Iterator range version template
void priv_create_and_insert_nodes (InpIterator beg, InpIterator end, bool unique) { typedef typename std::iterator_traits
::iterator_category ItCat; priv_create_and_insert_nodes(beg, end, unique, alloc_version(), ItCat()); } template
void priv_create_and_insert_nodes (InpIterator beg, InpIterator end, bool unique, allocator_v1, std::input_iterator_tag) { if(unique){ for (; beg != end; ++beg){ this->insert_unique(*beg); } } else{ for (; beg != end; ++beg){ this->insert_equal(*beg); } } } template
void priv_create_and_insert_nodes (InpIterator beg, InpIterator end, bool unique, allocator_v2, std::input_iterator_tag) { //Just forward to the default one priv_create_and_insert_nodes(beg, end, unique, allocator_v1(), std::input_iterator_tag()); } class insertion_functor; friend class insertion_functor; class insertion_functor { Icont &icont_; typename Icont::iterator pos_; public: insertion_functor(Icont &icont) : icont_(icont) {} void operator()(Node &n) { this->icont_.insert_equal(this->icont_.end(), n); } }; template
void priv_create_and_insert_nodes (FwdIterator beg, FwdIterator end, bool unique, allocator_v2, std::forward_iterator_tag) { if(unique){ priv_create_and_insert_nodes(beg, end, unique, allocator_v2(), std::input_iterator_tag()); } else{ //Optimized allocation and construction this->allocate_many_and_construct (beg, std::distance(beg, end), insertion_functor(this->icont())); } } }; template
inline bool operator==(const rbtree
& x, const rbtree
& y) { return x.size() == y.size() && std::equal(x.begin(), x.end(), y.begin()); } template
inline bool operator<(const rbtree
& x, const rbtree
& y) { return std::lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); } template
inline bool operator!=(const rbtree
& x, const rbtree
& y) { return !(x == y); } template
inline bool operator>(const rbtree
& x, const rbtree
& y) { return y < x; } template
inline bool operator<=(const rbtree
& x, const rbtree
& y) { return !(y < x); } template
inline bool operator>=(const rbtree
& x, const rbtree
& y) { return !(x < y); } template
inline void swap(rbtree
& x, rbtree
& y) { x.swap(y); } } //namespace detail { //!This class is movable template
struct is_movable
> { enum { value = true }; }; //!This class is movable template
struct is_movable
> { enum { value = true }; }; //!This class is movable /* template
struct is_movable
> { enum { value = true }; }; */ //!has_trivial_destructor_after_move<> == true_type //!specialization for optimizations template
struct has_trivial_destructor_after_move
> { enum { value = has_trivial_destructor
::value && has_trivial_destructor
::value }; }; } //namespace interprocess { } //namespace boost { #include
#endif //BOOST_INTERPROCESS_TREE_HPP
tree.hpp
Dirección de la página
Dirección del archivo
Anterior
3/3 Siguiente
Descargar
( 30 KB )
Comments
Total ratings:
0
Average rating:
No clasificado
of 10
Would you like to comment?
Join now
, or
Logon
if you are already a member.