123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777 |
- namespace boost{
- namespace multi_index{
- namespace detail{
- template<typename Allocator>
- struct hashed_index_node_impl;
- template<typename Allocator>
- struct hashed_index_base_node_impl
- {
- typedef typename rebind_alloc_for<
- Allocator,hashed_index_base_node_impl
- >::type base_allocator;
- typedef typename rebind_alloc_for<
- Allocator,hashed_index_node_impl<Allocator>
- >::type node_allocator;
- typedef allocator_traits<base_allocator> base_alloc_traits;
- typedef allocator_traits<node_allocator> node_alloc_traits;
- typedef typename base_alloc_traits::pointer base_pointer;
- typedef typename base_alloc_traits::const_pointer const_base_pointer;
- typedef typename node_alloc_traits::pointer pointer;
- typedef typename node_alloc_traits::const_pointer const_pointer;
- typedef typename node_alloc_traits::difference_type difference_type;
- pointer& prior(){return prior_;}
- pointer prior()const{return prior_;}
- private:
- pointer prior_;
- };
- template<typename Allocator>
- struct hashed_index_node_impl:hashed_index_base_node_impl<Allocator>
- {
- private:
- typedef hashed_index_base_node_impl<Allocator> super;
- public:
- typedef typename super::base_pointer base_pointer;
- typedef typename super::const_base_pointer const_base_pointer;
- typedef typename super::pointer pointer;
- typedef typename super::const_pointer const_pointer;
- base_pointer& next(){return next_;}
- base_pointer next()const{return next_;}
- static pointer pointer_from(base_pointer x)
- {
- return static_cast<pointer>(
- static_cast<hashed_index_node_impl*>(
- raw_ptr<super*>(x)));
- }
- static base_pointer base_pointer_from(pointer x)
- {
- return static_cast<base_pointer>(
- raw_ptr<hashed_index_node_impl*>(x));
- }
- private:
- base_pointer next_;
- };
- struct default_assigner
- {
- template<typename T> void operator()(T& x,const T& val){x=val;}
- };
- template<typename Node>
- struct unlink_undo_assigner
- {
- typedef typename Node::base_pointer base_pointer;
- typedef typename Node::pointer pointer;
- unlink_undo_assigner():pointer_track_count(0),base_pointer_track_count(0){}
- void operator()(pointer& x,pointer val)
- {
- pointer_tracks[pointer_track_count].x=&x;
- pointer_tracks[pointer_track_count++].val=x;
- x=val;
- }
- void operator()(base_pointer& x,base_pointer val)
- {
- base_pointer_tracks[base_pointer_track_count].x=&x;
- base_pointer_tracks[base_pointer_track_count++].val=x;
- x=val;
- }
- void operator()()
- {
-
- while(pointer_track_count--){
- *(pointer_tracks[pointer_track_count].x)=
- pointer_tracks[pointer_track_count].val;
- }
- while(base_pointer_track_count--){
- *(base_pointer_tracks[base_pointer_track_count].x)=
- base_pointer_tracks[base_pointer_track_count].val;
- }
- }
- struct pointer_track {pointer* x; pointer val;};
- struct base_pointer_track{base_pointer* x; base_pointer val;};
-
- pointer_track pointer_tracks[3];
- int pointer_track_count;
- base_pointer_track base_pointer_tracks[2];
- int base_pointer_track_count;
- };
- struct hashed_unique_tag{};
- struct hashed_non_unique_tag{};
- template<typename Node,typename Category>
- struct hashed_index_node_alg;
- template<typename Node>
- struct hashed_index_node_alg<Node,hashed_unique_tag>
- {
- typedef typename Node::base_pointer base_pointer;
- typedef typename Node::const_base_pointer const_base_pointer;
- typedef typename Node::pointer pointer;
- typedef typename Node::const_pointer const_pointer;
- static bool is_first_of_bucket(pointer x)
- {
- return x->prior()->next()!=base_pointer_from(x);
- }
- static pointer after(pointer x)
- {
- return is_last_of_bucket(x)?x->next()->prior():pointer_from(x->next());
- }
- static pointer after_local(pointer x)
- {
- return is_last_of_bucket(x)?pointer(0):pointer_from(x->next());
- }
- static pointer next_to_inspect(pointer x)
- {
- return is_last_of_bucket(x)?pointer(0):pointer_from(x->next());
- }
- static void link(pointer x,base_pointer buc,pointer end)
- {
- if(buc->prior()==pointer(0)){
- x->prior()=end->prior();
- x->next()=end->prior()->next();
- x->prior()->next()=buc;
- buc->prior()=x;
- end->prior()=x;
- }
- else{
- x->prior()=buc->prior()->prior();
- x->next()=base_pointer_from(buc->prior());
- buc->prior()=x;
- x->next()->prior()=x;
- }
- }
- static void unlink(pointer x)
- {
- default_assigner assign;
- unlink(x,assign);
- }
- typedef unlink_undo_assigner<Node> unlink_undo;
- template<typename Assigner>
- static void unlink(pointer x,Assigner& assign)
- {
- if(is_first_of_bucket(x)){
- if(is_last_of_bucket(x)){
- assign(x->prior()->next()->prior(),pointer(0));
- assign(x->prior()->next(),x->next());
- assign(x->next()->prior()->prior(),x->prior());
- }
- else{
- assign(x->prior()->next()->prior(),pointer_from(x->next()));
- assign(x->next()->prior(),x->prior());
- }
- }
- else if(is_last_of_bucket(x)){
- assign(x->prior()->next(),x->next());
- assign(x->next()->prior()->prior(),x->prior());
- }
- else{
- assign(x->prior()->next(),x->next());
- assign(x->next()->prior(),x->prior());
- }
- }
- /* used only at rehashing */
- static void append(pointer x,pointer end)
- {
- x->prior()=end->prior();
- x->next()=end->prior()->next();
- x->prior()->next()=base_pointer_from(x);
- end->prior()=x;
- }
- static bool unlink_last(pointer end)
- {
-
- pointer x=end->prior();
- if(x->prior()->next()==base_pointer_from(x)){
- x->prior()->next()=x->next();
- end->prior()=x->prior();
- return false;
- }
- else{
- x->prior()->next()->prior()=pointer(0);
- x->prior()->next()=x->next();
- end->prior()=x->prior();
- return true;
- }
- }
- private:
- static pointer pointer_from(base_pointer x)
- {
- return Node::pointer_from(x);
- }
- static base_pointer base_pointer_from(pointer x)
- {
- return Node::base_pointer_from(x);
- }
- static bool is_last_of_bucket(pointer x)
- {
- return x->next()->prior()!=x;
- }
- };
- template<typename Node>
- struct hashed_index_node_alg<Node,hashed_non_unique_tag>
- {
- typedef typename Node::base_pointer base_pointer;
- typedef typename Node::const_base_pointer const_base_pointer;
- typedef typename Node::pointer pointer;
- typedef typename Node::const_pointer const_pointer;
- static bool is_first_of_bucket(pointer x)
- {
- return x->prior()->next()->prior()==x;
- }
- static bool is_first_of_group(pointer x)
- {
- return
- x->next()->prior()!=x&&
- x->next()->prior()->prior()->next()==base_pointer_from(x);
- }
- static pointer after(pointer x)
- {
- if(x->next()->prior()==x)return pointer_from(x->next());
- if(x->next()->prior()->prior()==x)return x->next()->prior();
- if(x->next()->prior()->prior()->next()==base_pointer_from(x))
- return pointer_from(x->next());
- return pointer_from(x->next())->next()->prior();
- }
- static pointer after_local(pointer x)
- {
- if(x->next()->prior()==x)return pointer_from(x->next());
- if(x->next()->prior()->prior()==x)return pointer(0);
- if(x->next()->prior()->prior()->next()==base_pointer_from(x))
- return pointer_from(x->next());
- return pointer_from(x->next())->next()->prior();
- }
- static pointer next_to_inspect(pointer x)
- {
- if(x->next()->prior()==x)return pointer_from(x->next());
- if(x->next()->prior()->prior()==x)return pointer(0);
- if(x->next()->prior()->next()->prior()!=x->next()->prior())
- return pointer(0);
- return pointer_from(x->next()->prior()->next());
- }
- static void link(pointer x,base_pointer buc,pointer end)
- {
- if(buc->prior()==pointer(0)){ /* empty bucket */
- x->prior()=end->prior();
- x->next()=end->prior()->next();
- x->prior()->next()=buc;
- buc->prior()=x;
- end->prior()=x;
- }
- else{
- x->prior()=buc->prior()->prior();
- x->next()=base_pointer_from(buc->prior());
- buc->prior()=x;
- x->next()->prior()=x;
- }
- }
- static void link(pointer x,pointer first,pointer last)
- {
- x->prior()=first->prior();
- x->next()=base_pointer_from(first);
- if(is_first_of_bucket(first)){
- x->prior()->next()->prior()=x;
- }
- else{
- x->prior()->next()=base_pointer_from(x);
- }
- if(first==last){
- last->prior()=x;
- }
- else if(first->next()==base_pointer_from(last)){
- first->prior()=last;
- first->next()=base_pointer_from(x);
- }
- else{
- pointer second=pointer_from(first->next()),
- lastbutone=last->prior();
- second->prior()=first;
- first->prior()=last;
- lastbutone->next()=base_pointer_from(x);
- }
- }
- static void unlink(pointer x)
- {
- default_assigner assign;
- unlink(x,assign);
- }
- typedef unlink_undo_assigner<Node> unlink_undo;
- template<typename Assigner>
- static void unlink(pointer x,Assigner& assign)
- {
- if(x->prior()->next()==base_pointer_from(x)){
- if(x->next()->prior()==x){
- left_unlink(x,assign);
- right_unlink(x,assign);
- }
- else if(x->next()->prior()->prior()==x){ /* last of bucket */
- left_unlink(x,assign);
- right_unlink_last_of_bucket(x,assign);
- }
- else if(x->next()->prior()->prior()->next()==
- base_pointer_from(x)){ /* first of group size */
- left_unlink(x,assign);
- right_unlink_first_of_group(x,assign);
- }
- else{ /* n-1 of group */
- unlink_last_but_one_of_group(x,assign);
- }
- }
- else if(x->prior()->next()->prior()==x){ /* first of bucket */
- if(x->next()->prior()==x){
- left_unlink_first_of_bucket(x,assign);
- right_unlink(x,assign);
- }
- else if(x->next()->prior()->prior()==x){ /* last of bucket */
- assign(x->prior()->next()->prior(),pointer(0));
- assign(x->prior()->next(),x->next());
- assign(x->next()->prior()->prior(),x->prior());
- }
- else{ /* first of group */
- left_unlink_first_of_bucket(x,assign);
- right_unlink_first_of_group(x,assign);
- }
- }
- else if(x->next()->prior()->prior()==x){ /* last of group and bucket */
- left_unlink_last_of_group(x,assign);
- right_unlink_last_of_bucket(x,assign);
- }
- else if(pointer_from(x->prior()->prior()->next())
- ->next()==base_pointer_from(x)){ /* second of group */
- unlink_second_of_group(x,assign);
- }
- else{ /* last of group, ~(last of bucket) */
- left_unlink_last_of_group(x,assign);
- right_unlink(x,assign);
- }
- }
- /* used only at rehashing */
- static void link_range(
- pointer first,pointer last,base_pointer buc,pointer cend)
- {
- if(buc->prior()==pointer(0)){ /* empty bucket */
- first->prior()=cend->prior();
- last->next()=cend->prior()->next();
- first->prior()->next()=buc;
- buc->prior()=first;
- cend->prior()=last;
- }
- else{
- first->prior()=buc->prior()->prior();
- last->next()=base_pointer_from(buc->prior());
- buc->prior()=first;
- last->next()->prior()=last;
- }
- }
- static void append_range(pointer first,pointer last,pointer cend)
- {
- first->prior()=cend->prior();
- last->next()=cend->prior()->next();
- first->prior()->next()=base_pointer_from(first);
- cend->prior()=last;
- }
- static std::pair<pointer,bool> unlink_last_group(pointer end)
- {
-
- pointer x=end->prior();
- if(x->prior()->next()==base_pointer_from(x)){
- x->prior()->next()=x->next();
- end->prior()=x->prior();
- return std::make_pair(x,false);
- }
- else if(x->prior()->next()->prior()==x){
- x->prior()->next()->prior()=pointer(0);
- x->prior()->next()=x->next();
- end->prior()=x->prior();
- return std::make_pair(x,true);
- }
- else{
- pointer y=pointer_from(x->prior()->next());
- if(y->prior()->next()==base_pointer_from(y)){
- y->prior()->next()=x->next();
- end->prior()=y->prior();
- return std::make_pair(y,false);
- }
- else{
- y->prior()->next()->prior()=pointer(0);
- y->prior()->next()=x->next();
- end->prior()=y->prior();
- return std::make_pair(y,true);
- }
- }
- }
- static void unlink_range(pointer first,pointer last)
- {
- if(is_first_of_bucket(first)){
- if(is_last_of_bucket(last)){
- first->prior()->next()->prior()=pointer(0);
- first->prior()->next()=last->next();
- last->next()->prior()->prior()=first->prior();
- }
- else{
- first->prior()->next()->prior()=pointer_from(last->next());
- last->next()->prior()=first->prior();
- }
- }
- else if(is_last_of_bucket(last)){
- first->prior()->next()=last->next();
- last->next()->prior()->prior()=first->prior();
- }
- else{
- first->prior()->next()=last->next();
- last->next()->prior()=first->prior();
- }
- }
- private:
- static pointer pointer_from(base_pointer x)
- {
- return Node::pointer_from(x);
- }
- static base_pointer base_pointer_from(pointer x)
- {
- return Node::base_pointer_from(x);
- }
- static bool is_last_of_bucket(pointer x)
- {
- return x->next()->prior()->prior()==x;
- }
- template<typename Assigner>
- static void left_unlink(pointer x,Assigner& assign)
- {
- assign(x->prior()->next(),x->next());
- }
-
- template<typename Assigner>
- static void right_unlink(pointer x,Assigner& assign)
- {
- assign(x->next()->prior(),x->prior());
- }
- template<typename Assigner>
- static void left_unlink_first_of_bucket(pointer x,Assigner& assign)
- {
- assign(x->prior()->next()->prior(),pointer_from(x->next()));
- }
- template<typename Assigner>
- static void right_unlink_last_of_bucket(pointer x,Assigner& assign)
- {
- assign(x->next()->prior()->prior(),x->prior());
- }
- template<typename Assigner>
- static void right_unlink_first_of_group(pointer x,Assigner& assign)
- {
- pointer second=pointer_from(x->next()),
- last=second->prior(),
- lastbutone=last->prior();
- if(second==lastbutone){
- assign(second->next(),base_pointer_from(last));
- assign(second->prior(),x->prior());
- }
- else{
- assign(lastbutone->next(),base_pointer_from(second));
- assign(second->next()->prior(),last);
- assign(second->prior(),x->prior());
- }
- }
- template<typename Assigner>
- static void left_unlink_last_of_group(pointer x,Assigner& assign)
- {
- pointer lastbutone=x->prior(),
- first=pointer_from(lastbutone->next()),
- second=pointer_from(first->next());
- if(lastbutone==second){
- assign(lastbutone->prior(),first);
- assign(lastbutone->next(),x->next());
- }
- else{
- assign(second->prior(),lastbutone);
- assign(lastbutone->prior()->next(),base_pointer_from(first));
- assign(lastbutone->next(),x->next());
- }
- }
- template<typename Assigner>
- static void unlink_last_but_one_of_group(pointer x,Assigner& assign)
- {
- pointer first=pointer_from(x->next()),
- second=pointer_from(first->next()),
- last=second->prior();
- if(second==x){
- assign(last->prior(),first);
- assign(first->next(),base_pointer_from(last));
- }
- else{
- assign(last->prior(),x->prior());
- assign(x->prior()->next(),base_pointer_from(first));
- }
- }
- template<typename Assigner>
- static void unlink_second_of_group(pointer x,Assigner& assign)
- {
- pointer last=x->prior(),
- lastbutone=last->prior(),
- first=pointer_from(lastbutone->next());
- if(lastbutone==x){
- assign(first->next(),base_pointer_from(last));
- assign(last->prior(),first);
- }
- else{
- assign(first->next(),x->next());
- assign(x->next()->prior(),last);
- }
- }
- };
- template<typename Super>
- struct hashed_index_node_trampoline:
- hashed_index_node_impl<
- typename rebind_alloc_for<
- typename Super::allocator_type,char
- >::type
- >
- {
- typedef typename rebind_alloc_for<
- typename Super::allocator_type,char
- >::type impl_allocator_type;
- typedef hashed_index_node_impl<impl_allocator_type> impl_type;
- };
- template<typename Super>
- struct hashed_index_node:
- Super,hashed_index_node_trampoline<Super>
- {
- private:
- typedef hashed_index_node_trampoline<Super> trampoline;
- public:
- typedef typename trampoline::impl_type impl_type;
- typedef typename trampoline::base_pointer impl_base_pointer;
- typedef typename trampoline::const_base_pointer const_impl_base_pointer;
- typedef typename trampoline::pointer impl_pointer;
- typedef typename trampoline::const_pointer const_impl_pointer;
- typedef typename trampoline::difference_type difference_type;
- template<typename Category>
- struct node_alg{
- typedef hashed_index_node_alg<impl_type,Category> type;
- };
- impl_pointer& prior(){return trampoline::prior();}
- impl_pointer prior()const{return trampoline::prior();}
- impl_base_pointer& next(){return trampoline::next();}
- impl_base_pointer next()const{return trampoline::next();}
- impl_pointer impl()
- {
- return static_cast<impl_pointer>(
- static_cast<impl_type*>(static_cast<trampoline*>(this)));
- }
- const_impl_pointer impl()const
- {
- return static_cast<const_impl_pointer>(
- static_cast<const impl_type*>(static_cast<const trampoline*>(this)));
- }
- static hashed_index_node* from_impl(impl_pointer x)
- {
- return
- static_cast<hashed_index_node*>(
- static_cast<trampoline*>(
- raw_ptr<impl_type*>(x)));
- }
- static const hashed_index_node* from_impl(const_impl_pointer x)
- {
- return
- static_cast<const hashed_index_node*>(
- static_cast<const trampoline*>(
- raw_ptr<const impl_type*>(x)));
- }
- /* interoperability with hashed_index_iterator */
- template<typename Category>
- static void increment(hashed_index_node*& x)
- {
- x=from_impl(node_alg<Category>::type::after(x->impl()));
- }
- template<typename Category>
- static void increment_local(hashed_index_node*& x)
- {
- x=from_impl(node_alg<Category>::type::after_local(x->impl()));
- }
- };
- } /* namespace multi_index::detail */
- } /* namespace multi_index */
- } /* namespace boost */
- #endif
|