boost_ext/boost/multi_index/detail/ord_index_node.hpp

   1 /* Copyright 2003-2007 Joaquín M López Muñoz.
   2  * Distributed under the Boost Software License, Version 1.0.
   3  * (See accompanying file LICENSE_1_0.txt or copy at
   4  * http://www.boost.org/LICENSE_1_0.txt)
   5  *
   6  * See http://www.boost.org/libs/multi_index for library home page.
   7  *
   8  * The internal implementation of red-black trees is based on that of SGI STL
   9  * stl_tree.h file:
  10  *
  11  * Copyright (c) 1996,1997
  12  * Silicon Graphics Computer Systems, Inc.
  13  *
  14  * Permission to use, copy, modify, distribute and sell this software
  15  * and its documentation for any purpose is hereby granted without fee,
  16  * provided that the above copyright notice appear in all copies and
  17  * that both that copyright notice and this permission notice appear
  18  * in supporting documentation.  Silicon Graphics makes no
  19  * representations about the suitability of this software for any
  20  * purpose.  It is provided "as is" without express or implied warranty.
  21  *
  22  *
  23  * Copyright (c) 1994
  24  * Hewlett-Packard Company
  25  *
  26  * Permission to use, copy, modify, distribute and sell this software
  27  * and its documentation for any purpose is hereby granted without fee,
  28  * provided that the above copyright notice appear in all copies and
  29  * that both that copyright notice and this permission notice appear
  30  * in supporting documentation.  Hewlett-Packard Company makes no
  31  * representations about the suitability of this software for any
  32  * purpose.  It is provided "as is" without express or implied warranty.
  33  *
  34  */
  35
  36 #ifndef BOOST_MULTI_INDEX_DETAIL_ORD_INDEX_NODE_HPP
  37 #define BOOST_MULTI_INDEX_DETAIL_ORD_INDEX_NODE_HPP
  38
  39 #if defined(_MSC_VER)&&(_MSC_VER>=1200)
  40 #pragma once
  41 #endif
  42
  43 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
  44 #include <cstddef>
  45 #include <boost/detail/allocator_utilities.hpp>
  46 #include <boost/multi_index/detail/prevent_eti.hpp>
  47
  48 #if !defined(BOOST_MULTI_INDEX_DISABLE_COMPRESSED_ORDERED_INDEX_NODES)
  49 #include <boost/mpl/and.hpp>
  50 #include <boost/mpl/if.hpp>
  51 #include <boost/multi_index/detail/uintptr_type.hpp>
  52 #include <boost/type_traits/alignment_of.hpp>
  53 #include <boost/type_traits/is_same.hpp>
  54 #endif
  55
  56 namespace boost{
  57
  58 namespace multi_index{
  59
  60 namespace detail{
  61
  62 /* definition of red-black nodes for ordered_index */
  63
  64 enum ordered_index_color{red=false,black=true};
  65 enum ordered_index_side{to_left=false,to_right=true};
  66
  67 template<typename Allocator>
  68 struct ordered_index_node_impl; /* fwd decl. */
  69
  70 template<typename Allocator>
  71 struct ordered_index_node_std_base
  72 {
  73   typedef typename prevent_eti<
  74     Allocator,
  75     typename boost::detail::allocator::rebind_to<
  76       Allocator,
  77       ordered_index_node_impl<Allocator>
  78     >::type
  79   >::type::pointer                                pointer;
  80   typedef typename prevent_eti<
  81     Allocator,
  82     typename boost::detail::allocator::rebind_to<
  83       Allocator,
  84       ordered_index_node_impl<Allocator>
  85     >::type
  86   >::type::const_pointer                          const_pointer;
  87   typedef ordered_index_color&                    color_ref;
  88   typedef pointer&                                parent_ref;
  89
  90   ordered_index_color& color(){return color_;}
  91   ordered_index_color  color()const{return color_;}
  92   pointer&             parent(){return parent_;}
  93   pointer              parent()const{return parent_;}
  94   pointer&             left(){return left_;}
  95   pointer              left()const{return left_;}
  96   pointer&             right(){return right_;}
  97   pointer              right()const{return right_;}
  98
  99 private:
 100   ordered_index_color color_;
 101   pointer             parent_;
 102   pointer             left_;
 103   pointer             right_;
 104 };
 105
 106 #if !defined(BOOST_MULTI_INDEX_DISABLE_COMPRESSED_ORDERED_INDEX_NODES)
 107 /* If ordered_index_node_impl has even alignment, we can use the least
 108  * significant bit of one of the ordered_index_node_impl pointers to
 109  * store color information. This typically reduces the size of
 110  * ordered_index_node_impl by 25%.
 111  */
 112
 113 #if defined(BOOST_MSVC)
 114 /* This code casts pointers to an integer type that has been computed
 115  * to be large enough to hold the pointer, however the metaprogramming
 116  * logic is not always spotted by the VC++ code analyser that issues a
 117  * long list of warnings.
 118  */
 119
 120 #pragma warning(push)
 121 #pragma warning(disable:4312 4311)
 122 #endif
 123
 124 template<typename Allocator>
 125 struct ordered_index_node_compressed_base
 126 {
 127   typedef ordered_index_node_impl<Allocator>*       pointer;
 128   typedef const ordered_index_node_impl<Allocator>* const_pointer;
 129
 130   struct color_ref
 131   {
 132     color_ref(uintptr_type* r_):r(r_){}
 133
 134     operator ordered_index_color()const
 135     {
 136       return ordered_index_color(*r&uintptr_type(1));
 137     }
 138
 139     color_ref& operator=(ordered_index_color c)
 140     {
 141       *r&=~uintptr_type(1);
 142       *r|=uintptr_type(c);
 143       return *this;
 144     }
 145
 146     color_ref& operator=(const color_ref& x)
 147     {
 148       return operator=(x.operator ordered_index_color());
 149     }
 150
 151   private:
 152     uintptr_type* r;
 153   };
 154
 155   struct parent_ref
 156   {
 157     parent_ref(uintptr_type* r_):r(r_){}
 158
 159     operator pointer()const
 160     {
 161       return (pointer)(void*)(*r&~uintptr_type(1));
 162     }
 163
 164     parent_ref& operator=(pointer p)
 165     {
 166       *r=((uintptr_type)(void*)p)|(*r&uintptr_type(1));
 167       return *this;
 168     }
 169
 170     parent_ref& operator=(const parent_ref& x)
 171     {
 172       return operator=(x.operator pointer());
 173     }
 174
 175     pointer operator->()const
 176     {
 177       return operator pointer();
 178     }
 179
 180   private:
 181     uintptr_type* r;
 182   };
 183
 184   color_ref           color(){return color_ref(&parentcolor_);}
 185   ordered_index_color color()const
 186   {
 187     return ordered_index_color(parentcolor_&std::size_t(1ul));
 188   }
 189
 190   parent_ref parent(){return parent_ref(&parentcolor_);}
 191   pointer    parent()const
 192   {
 193     return (pointer)(void*)(parentcolor_&~uintptr_type(1));
 194   }
 195
 196   pointer& left(){return left_;}
 197   pointer  left()const{return left_;}
 198   pointer& right(){return right_;}
 199   pointer  right()const{return right_;}
 200
 201 private:
 202   uintptr_type parentcolor_;
 203   pointer      left_;
 204   pointer      right_;
 205 };
 206 #if defined(BOOST_MSVC)
 207 #pragma warning(pop)
 208 #endif
 209 #endif
 210
 211 template<typename Allocator>
 212 struct ordered_index_node_impl_base:
 213
 214 #if !defined(BOOST_MULTI_INDEX_DISABLE_COMPRESSED_ORDERED_INDEX_NODES)
 215   mpl::if_c<
 216     !(has_uintptr_type::value)||
 217     (alignment_of<ordered_index_node_compressed_base<Allocator> >::value%2)||
 218     !(is_same<
 219       typename prevent_eti<
 220         Allocator,
 221         typename boost::detail::allocator::rebind_to<
 222           Allocator,
 223           ordered_index_node_impl<Allocator>
 224         >::type
 225       >::type::pointer,
 226       ordered_index_node_impl<Allocator>*>::value),
 227     ordered_index_node_std_base<Allocator>,
 228     ordered_index_node_compressed_base<Allocator>
 229   >::type
 230 #else
 231   ordered_index_node_std_base<Allocator>
 232 #endif
 233
 234 {};
 235
 236 template<typename Allocator>
 237 struct ordered_index_node_impl:ordered_index_node_impl_base<Allocator>
 238 {
 239 private:
 240   typedef ordered_index_node_impl_base<Allocator> super;
 241
 242 public:
 243   typedef typename super::color_ref               color_ref;
 244   typedef typename super::parent_ref              parent_ref;
 245   typedef typename super::pointer                 pointer;
 246   typedef typename super::const_pointer           const_pointer;
 247
 248   /* interoperability with bidir_node_iterator */
 249
 250   static void increment(pointer& x)
 251   {
 252     if(x->right()!=pointer(0)){
 253       x=x->right();
 254       while(x->left()!=pointer(0))x=x->left();
 255     }
 256     else{
 257       pointer y=x->parent();
 258       while(x==y->right()){
 259         x=y;
 260         y=y->parent();
 261       }
 262       if(x->right()!=y)x=y;
 263     }
 264   }
 265
 266   static void decrement(pointer& x)
 267   {
 268     if(x->color()==red&&x->parent()->parent()==x){
 269       x=x->right();
 270     }
 271     else if(x->left()!=pointer(0)){
 272       pointer y=x->left();
 273       while(y->right()!=pointer(0))y=y->right();
 274       x=y;
 275     }else{
 276       pointer y=x->parent();
 277       while(x==y->left()){
 278         x=y;
 279         y=y->parent();
 280       }
 281       x=y;
 282     }
 283   }
 284
 285   /* algorithmic stuff */
 286
 287   static void rotate_left(pointer x,parent_ref root)
 288   {
 289     pointer y=x->right();
 290     x->right()=y->left();
 291     if(y->left()!=pointer(0))y->left()->parent()=x;
 292     y->parent()=x->parent();
 293
 294     if(x==root)                    root=y;
 295     else if(x==x->parent()->left())x->parent()->left()=y;
 296     else                           x->parent()->right()=y;
 297     y->left()=x;
 298     x->parent()=y;
 299   }
 300
 301   static pointer minimum(pointer x)
 302   {
 303     while(x->left()!=pointer(0))x=x->left();
 304     return x;
 305   }
 306
 307   static pointer maximum(pointer x)
 308   {
 309     while(x->right()!=pointer(0))x=x->right();
 310     return x;
 311   }
 312
 313   static void rotate_right(pointer x,parent_ref root)
 314   {
 315     pointer y=x->left();
 316     x->left()=y->right();
 317     if(y->right()!=pointer(0))y->right()->parent()=x;
 318     y->parent()=x->parent();
 319
 320     if(x==root)                     root=y;
 321     else if(x==x->parent()->right())x->parent()->right()=y;
 322     else                            x->parent()->left()=y;
 323     y->right()=x;
 324     x->parent()=y;
 325   }
 326
 327   static void rebalance(pointer x,parent_ref root)
 328   {
 329     x->color()=red;
 330     while(x!=root&&x->parent()->color()==red){
 331       if(x->parent()==x->parent()->parent()->left()){
 332         pointer y=x->parent()->parent()->right();
 333         if(y!=pointer(0)&&y->color()==red){
 334           x->parent()->color()=black;
 335           y->color()=black;
 336           x->parent()->parent()->color()=red;
 337           x=x->parent()->parent();
 338         }
 339         else{
 340           if(x==x->parent()->right()){
 341             x=x->parent();
 342             rotate_left(x,root);
 343           }
 344           x->parent()->color()=black;
 345           x->parent()->parent()->color()=red;
 346           rotate_right(x->parent()->parent(),root);
 347         }
 348       }
 349       else{
 350         pointer y=x->parent()->parent()->left();
 351         if(y!=pointer(0)&&y->color()==red){
 352           x->parent()->color()=black;
 353           y->color()=black;
 354           x->parent()->parent()->color()=red;
 355           x=x->parent()->parent();
 356         }
 357         else{
 358           if(x==x->parent()->left()){
 359             x=x->parent();
 360             rotate_right(x,root);
 361           }
 362           x->parent()->color()=black;
 363           x->parent()->parent()->color()=red;
 364           rotate_left(x->parent()->parent(),root);
 365         }
 366       }
 367     }
 368     root->color()=black;
 369   }
 370
 371   static void link(
 372     pointer x,ordered_index_side side,pointer position,pointer header)
 373   {
 374     if(side==to_left){
 375       position->left()=x;  /* also makes leftmost=x when parent==header */
 376       if(position==header){
 377         header->parent()=x;
 378         header->right()=x;
 379       }
 380       else if(position==header->left()){
 381         header->left()=x;  /* maintain leftmost pointing to min node */
 382       }
 383     }
 384     else{
 385       position->right()=x;
 386       if(position==header->right()){
 387         header->right()=x; /* maintain rightmost pointing to max node */
 388       }
 389     }
 390     x->parent()=position;
 391     x->left()=pointer(0);
 392     x->right()=pointer(0);
 393     ordered_index_node_impl::rebalance(x,header->parent());
 394   }
 395
 396   static pointer rebalance_for_erase(
 397     pointer z,parent_ref root,pointer& leftmost,pointer& rightmost)
 398   {
 399     pointer y=z;
 400     pointer x=pointer(0);
 401     pointer x_parent=pointer(0);
 402     if(y->left()==pointer(0)){    /* z has at most one non-null child. y==z. */
 403       x=y->right();               /* x might be null */
 404     }
 405     else{
 406       if(y->right()==pointer(0)){ /* z has exactly one non-null child. y==z. */
 407         x=y->left();              /* x is not null */
 408       }
 409       else{                       /* z has two non-null children.  Set y to */
 410         y=y->right();             /* z's successor. x might be null.        */
 411         while(y->left()!=pointer(0))y=y->left();
 412         x=y->right();
 413       }
 414     }
 415     if(y!=z){
 416       z->left()->parent()=y;   /* relink y in place of z. y is z's successor */
 417       y->left()=z->left();
 418       if(y!=z->right()){
 419         x_parent=y->parent();
 420         if(x!=pointer(0))x->parent()=y->parent();
 421         y->parent()->left()=x; /* y must be a child of left */
 422         y->right()=z->right();
 423         z->right()->parent()=y;
 424       }
 425       else{
 426         x_parent=y;
 427       }
 428
 429       if(root==z)                    root=y;
 430       else if(z->parent()->left()==z)z->parent()->left()=y;
 431       else                           z->parent()->right()=y;
 432       y->parent()=z->parent();
 433       ordered_index_color c=y->color();
 434       y->color()=z->color();
 435       z->color()=c;
 436       y=z;                    /* y now points to node to be actually deleted */
 437     }
 438     else{                     /* y==z */
 439       x_parent=y->parent();
 440       if(x!=pointer(0))x->parent()=y->parent();
 441       if(root==z){
 442         root=x;
 443       }
 444       else{
 445         if(z->parent()->left()==z)z->parent()->left()=x;
 446         else                      z->parent()->right()=x;
 447       }
 448       if(leftmost==z){
 449         if(z->right()==pointer(0)){ /* z->left() must be null also */
 450           leftmost=z->parent();
 451         }
 452         else{
 453           leftmost=minimum(x);      /* makes leftmost==header if z==root */
 454         }
 455       }
 456       if(rightmost==z){
 457         if(z->left()==pointer(0)){  /* z->right() must be null also */
 458           rightmost=z->parent();
 459         }
 460         else{                   /* x==z->left() */
 461           rightmost=maximum(x); /* makes rightmost==header if z==root */
 462         }
 463       }
 464     }
 465     if(y->color()!=red){
 466       while(x!=root&&(x==pointer(0)|| x->color()==black)){
 467         if(x==x_parent->left()){
 468           pointer w=x_parent->right();
 469           if(w->color()==red){
 470             w->color()=black;
 471             x_parent->color()=red;
 472             rotate_left(x_parent,root);
 473             w=x_parent->right();
 474           }
 475           if((w->left()==pointer(0)||w->left()->color()==black) &&
 476              (w->right()==pointer(0)||w->right()->color()==black)){
 477             w->color()=red;
 478             x=x_parent;
 479             x_parent=x_parent->parent();
 480           }
 481           else{
 482             if(w->right()==pointer(0 )
 483                 || w->right()->color()==black){
 484               if(w->left()!=pointer(0)) w->left()->color()=black;
 485               w->color()=red;
 486               rotate_right(w,root);
 487               w=x_parent->right();
 488             }
 489             w->color()=x_parent->color();
 490             x_parent->color()=black;
 491             if(w->right()!=pointer(0))w->right()->color()=black;
 492             rotate_left(x_parent,root);
 493             break;
 494           }
 495         }
 496         else{                   /* same as above,with right <-> left */
 497           pointer w=x_parent->left();
 498           if(w->color()==red){
 499             w->color()=black;
 500             x_parent->color()=red;
 501             rotate_right(x_parent,root);
 502             w=x_parent->left();
 503           }
 504           if((w->right()==pointer(0)||w->right()->color()==black) &&
 505              (w->left()==pointer(0)||w->left()->color()==black)){
 506             w->color()=red;
 507             x=x_parent;
 508             x_parent=x_parent->parent();
 509           }
 510           else{
 511             if(w->left()==pointer(0)||w->left()->color()==black){
 512               if(w->right()!=pointer(0))w->right()->color()=black;
 513               w->color()=red;
 514               rotate_left(w,root);
 515               w=x_parent->left();
 516             }
 517             w->color()=x_parent->color();
 518             x_parent->color()=black;
 519             if(w->left()!=pointer(0))w->left()->color()=black;
 520             rotate_right(x_parent,root);
 521             break;
 522           }
 523         }
 524       }
 525       if(x!=pointer(0))x->color()=black;
 526     }
 527     return y;
 528   }
 529
 530   static void restore(pointer x,pointer position,pointer header)
 531   {
 532     if(position->left()==pointer(0)||position->left()==header){
 533       link(x,to_left,position,header);
 534     }
 535     else{
 536       decrement(position);
 537       link(x,to_right,position,header);
 538     }
 539   }
 540
 541 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
 542   /* invariant stuff */
 543
 544   static std::size_t black_count(pointer node,pointer root)
 545   {
 546     if(node==pointer(0))return 0;
 547     std::size_t sum=0;
 548     for(;;){
 549       if(node->color()==black)++sum;
 550       if(node==root)break;
 551       node=node->parent();
 552     }
 553     return sum;
 554   }
 555 #endif
 556 };
 557
 558 template<typename Super>
 559 struct ordered_index_node_trampoline:
 560   prevent_eti<
 561     Super,
 562     ordered_index_node_impl<
 563       typename boost::detail::allocator::rebind_to<
 564         typename Super::allocator_type,
 565         void
 566       >::type
 567     >
 568   >::type
 569 {
 570   typedef typename prevent_eti<
 571     Super,
 572     ordered_index_node_impl<
 573       typename boost::detail::allocator::rebind_to<
 574         typename Super::allocator_type,
 575         void
 576       >::type
 577     >
 578   >::type impl_type;
 579 };
 580
 581 template<typename Super>
 582 struct ordered_index_node:Super,ordered_index_node_trampoline<Super>
 583 {
 584 private:
 585   typedef ordered_index_node_trampoline<Super> trampoline;
 586
 587 public:
 588   typedef typename trampoline::impl_type     impl_type;
 589   typedef typename trampoline::color_ref     impl_color_ref;
 590   typedef typename trampoline::parent_ref    impl_parent_ref;
 591   typedef typename trampoline::pointer       impl_pointer;
 592   typedef typename trampoline::const_pointer const_impl_pointer;
 593
 594   impl_color_ref      color(){return trampoline::color();}
 595   ordered_index_color color()const{return trampoline::color();}
 596   impl_parent_ref     parent(){return trampoline::parent();}
 597   impl_pointer        parent()const{return trampoline::parent();}
 598   impl_pointer&       left(){return trampoline::left();}
 599   impl_pointer        left()const{return trampoline::left();}
 600   impl_pointer&       right(){return trampoline::right();}
 601   impl_pointer        right()const{return trampoline::right();}
 602
 603   impl_pointer impl()
 604   {
 605     return static_cast<impl_pointer>(
 606       static_cast<impl_type*>(static_cast<trampoline*>(this)));
 607   }
 608
 609   const_impl_pointer impl()const
 610   {
 611     return static_cast<const_impl_pointer>(
 612       static_cast<const impl_type*>(static_cast<const trampoline*>(this)));
 613   }
 614
 615   static ordered_index_node* from_impl(impl_pointer x)
 616   {
 617     return static_cast<ordered_index_node*>(
 618       static_cast<trampoline*>(&*x));
 619   }
 620
 621   static const ordered_index_node* from_impl(const_impl_pointer x)
 622   {
 623     return static_cast<const ordered_index_node*>(
 624       static_cast<const trampoline*>(&*x));
 625   }
 626
 627   /* interoperability with bidir_node_iterator */
 628
 629   static void increment(ordered_index_node*& x)
 630   {
 631     impl_pointer xi=x->impl();
 632     trampoline::increment(xi);
 633     x=from_impl(xi);
 634   }
 635
 636   static void decrement(ordered_index_node*& x)
 637   {
 638     impl_pointer xi=x->impl();
 639     trampoline::decrement(xi);
 640     x=from_impl(xi);
 641   }
 642 };
 643
 644 } /* namespace multi_index::detail */
 645
 646 } /* namespace multi_index */
 647
 648 } /* namespace boost */
 649
 650 #endif