ceph/src/boost/boost/multi_index/detail/ord_index_node.hpp

   1 /* Copyright 2003-2020 Joaquin M Lopez Munoz.
   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)
  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/multi_index/detail/allocator_traits.hpp>
  46 #include <boost/multi_index/detail/raw_ptr.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 AugmentPolicy,typename Allocator>
  68 struct ordered_index_node_impl; /* fwd decl. */
  69
  70 template<typename AugmentPolicy,typename Allocator>
  71 struct ordered_index_node_traits
  72 {
  73   typedef typename rebind_alloc_for<
  74     Allocator,
  75     ordered_index_node_impl<AugmentPolicy,Allocator>
  76   >::type                                            allocator;
  77   typedef allocator_traits<allocator>                alloc_traits;
  78   typedef typename alloc_traits::pointer             pointer;
  79   typedef typename alloc_traits::const_pointer       const_pointer;
  80   typedef typename alloc_traits::difference_type     difference_type;
  81   typedef typename alloc_traits::size_type           size_type;
  82 };
  83
  84 template<typename AugmentPolicy,typename Allocator>
  85 struct ordered_index_node_std_base
  86 {
  87   typedef ordered_index_node_traits<
  88     AugmentPolicy,Allocator>                    node_traits;
  89   typedef typename node_traits::allocator       node_allocator;
  90   typedef typename node_traits::pointer         pointer;
  91   typedef typename node_traits::const_pointer   const_pointer;
  92   typedef typename node_traits::difference_type difference_type;
  93   typedef typename node_traits::size_type       size_type;
  94   typedef ordered_index_color&                  color_ref;
  95   typedef pointer&                              parent_ref;
  96
  97   ordered_index_color& color(){return color_;}
  98   ordered_index_color  color()const{return color_;}
  99   pointer&             parent(){return parent_;}
 100   pointer              parent()const{return parent_;}
 101   pointer&             left(){return left_;}
 102   pointer              left()const{return left_;}
 103   pointer&             right(){return right_;}
 104   pointer              right()const{return right_;}
 105
 106 private:
 107   ordered_index_color color_;
 108   pointer             parent_;
 109   pointer             left_;
 110   pointer             right_;
 111 };
 112
 113 #if !defined(BOOST_MULTI_INDEX_DISABLE_COMPRESSED_ORDERED_INDEX_NODES)
 114 /* If ordered_index_node_impl has even alignment, we can use the least
 115  * significant bit of one of the ordered_index_node_impl pointers to
 116  * store color information. This typically reduces the size of
 117  * ordered_index_node_impl by 25%.
 118  */
 119
 120 #if defined(BOOST_MSVC)
 121 /* This code casts pointers to an integer type that has been computed
 122  * to be large enough to hold the pointer, however the metaprogramming
 123  * logic is not always spotted by the VC++ code analyser that issues a
 124  * long list of warnings.
 125  */
 126
 127 #pragma warning(push)
 128 #pragma warning(disable:4312 4311)
 129 #endif
 130
 131 template<typename AugmentPolicy,typename Allocator>
 132 struct ordered_index_node_compressed_base
 133 {
 134   typedef ordered_index_node_traits<
 135     AugmentPolicy,Allocator>                    node_traits;
 136   typedef ordered_index_node_impl<
 137     AugmentPolicy,Allocator>*                   pointer;
 138   typedef const ordered_index_node_impl<
 139     AugmentPolicy,Allocator>*                   const_pointer;
 140   typedef typename node_traits::difference_type difference_type;
 141   typedef typename node_traits::size_type       size_type;
 142
 143   struct color_ref
 144   {
 145     color_ref(uintptr_type* r_):r(r_){}
 146     color_ref(const color_ref& x):r(x.r){}
 147
 148     operator ordered_index_color()const
 149     {
 150       return ordered_index_color(*r&uintptr_type(1));
 151     }
 152
 153     color_ref& operator=(ordered_index_color c)
 154     {
 155       *r&=~uintptr_type(1);
 156       *r|=uintptr_type(c);
 157       return *this;
 158     }
 159
 160     color_ref& operator=(const color_ref& x)
 161     {
 162       return operator=(x.operator ordered_index_color());
 163     }
 164
 165   private:
 166     uintptr_type* r;
 167   };
 168
 169   struct parent_ref
 170   {
 171     parent_ref(uintptr_type* r_):r(r_){}
 172     parent_ref(const parent_ref& x):r(x.r){}
 173
 174     operator pointer()const
 175     {
 176       return (pointer)(void*)(*r&~uintptr_type(1));
 177     }
 178
 179     parent_ref& operator=(pointer p)
 180     {
 181       *r=((uintptr_type)(void*)p)|(*r&uintptr_type(1));
 182       return *this;
 183     }
 184
 185     parent_ref& operator=(const parent_ref& x)
 186     {
 187       return operator=(x.operator pointer());
 188     }
 189
 190     pointer operator->()const
 191     {
 192       return operator pointer();
 193     }
 194
 195   private:
 196     uintptr_type* r;
 197   };
 198
 199   color_ref           color(){return color_ref(&parentcolor_);}
 200   ordered_index_color color()const
 201   {
 202     return ordered_index_color(parentcolor_&uintptr_type(1));
 203   }
 204
 205   parent_ref parent(){return parent_ref(&parentcolor_);}
 206   pointer    parent()const
 207   {
 208     return (pointer)(void*)(parentcolor_&~uintptr_type(1));
 209   }
 210
 211   pointer& left(){return left_;}
 212   pointer  left()const{return left_;}
 213   pointer& right(){return right_;}
 214   pointer  right()const{return right_;}
 215
 216 private:
 217   uintptr_type parentcolor_;
 218   pointer      left_;
 219   pointer      right_;
 220 };
 221 #if defined(BOOST_MSVC)
 222 #pragma warning(pop)
 223 #endif
 224 #endif
 225
 226 template<typename AugmentPolicy,typename Allocator>
 227 struct ordered_index_node_impl_base:
 228
 229 #if !defined(BOOST_MULTI_INDEX_DISABLE_COMPRESSED_ORDERED_INDEX_NODES)
 230   AugmentPolicy::template augmented_node<
 231     typename mpl::if_c<
 232       !(has_uintptr_type::value)||
 233       (alignment_of<
 234         ordered_index_node_compressed_base<AugmentPolicy,Allocator>
 235        >::value%2)||
 236       !(is_same<
 237         typename ordered_index_node_traits<AugmentPolicy,Allocator>::pointer,
 238         ordered_index_node_impl<AugmentPolicy,Allocator>*>::value),
 239       ordered_index_node_std_base<AugmentPolicy,Allocator>,
 240       ordered_index_node_compressed_base<AugmentPolicy,Allocator>
 241     >::type
 242   >::type
 243 #else
 244   AugmentPolicy::template augmented_node<
 245     ordered_index_node_std_base<AugmentPolicy,Allocator>
 246   >::type
 247 #endif
 248
 249 {};
 250
 251 template<typename AugmentPolicy,typename Allocator>
 252 struct ordered_index_node_impl:
 253   ordered_index_node_impl_base<AugmentPolicy,Allocator>
 254 {
 255 private:
 256   typedef ordered_index_node_impl_base<AugmentPolicy,Allocator> super;
 257
 258 public:
 259   typedef typename super::color_ref                             color_ref;
 260   typedef typename super::parent_ref                            parent_ref;
 261   typedef typename super::pointer                               pointer;
 262   typedef typename super::const_pointer                         const_pointer;
 263
 264   /* interoperability with bidir_node_iterator */
 265
 266   static void increment(pointer& x)
 267   {
 268     if(x->right()!=pointer(0)){
 269       x=x->right();
 270       while(x->left()!=pointer(0))x=x->left();
 271     }
 272     else{
 273       pointer y=x->parent();
 274       while(x==y->right()){
 275         x=y;
 276         y=y->parent();
 277       }
 278       if(x->right()!=y)x=y;
 279     }
 280   }
 281
 282   static void decrement(pointer& x)
 283   {
 284     if(x->color()==red&&x->parent()->parent()==x){
 285       x=x->right();
 286     }
 287     else if(x->left()!=pointer(0)){
 288       pointer y=x->left();
 289       while(y->right()!=pointer(0))y=y->right();
 290       x=y;
 291     }else{
 292       pointer y=x->parent();
 293       while(x==y->left()){
 294         x=y;
 295         y=y->parent();
 296       }
 297       x=y;
 298     }
 299   }
 300
 301   /* algorithmic stuff */
 302
 303   static void rotate_left(pointer x,parent_ref root)
 304   {
 305     pointer y=x->right();
 306     x->right()=y->left();
 307     if(y->left()!=pointer(0))y->left()->parent()=x;
 308     y->parent()=x->parent();
 309
 310     if(x==root)                    root=y;
 311     else if(x==x->parent()->left())x->parent()->left()=y;
 312     else                           x->parent()->right()=y;
 313     y->left()=x;
 314     x->parent()=y;
 315     AugmentPolicy::rotate_left(x,y);
 316   }
 317
 318   static pointer minimum(pointer x)
 319   {
 320     while(x->left()!=pointer(0))x=x->left();
 321     return x;
 322   }
 323
 324   static pointer maximum(pointer x)
 325   {
 326     while(x->right()!=pointer(0))x=x->right();
 327     return x;
 328   }
 329
 330   static void rotate_right(pointer x,parent_ref root)
 331   {
 332     pointer y=x->left();
 333     x->left()=y->right();
 334     if(y->right()!=pointer(0))y->right()->parent()=x;
 335     y->parent()=x->parent();
 336
 337     if(x==root)                     root=y;
 338     else if(x==x->parent()->right())x->parent()->right()=y;
 339     else                            x->parent()->left()=y;
 340     y->right()=x;
 341     x->parent()=y;
 342     AugmentPolicy::rotate_right(x,y);
 343   }
 344
 345   static void rebalance(pointer x,parent_ref root)
 346   {
 347     x->color()=red;
 348     while(x!=root&&x->parent()->color()==red){
 349       if(x->parent()==x->parent()->parent()->left()){
 350         pointer y=x->parent()->parent()->right();
 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()->right()){
 359             x=x->parent();
 360             rotate_left(x,root);
 361           }
 362           x->parent()->color()=black;
 363           x->parent()->parent()->color()=red;
 364           rotate_right(x->parent()->parent(),root);
 365         }
 366       }
 367       else{
 368         pointer y=x->parent()->parent()->left();
 369         if(y!=pointer(0)&&y->color()==red){
 370           x->parent()->color()=black;
 371           y->color()=black;
 372           x->parent()->parent()->color()=red;
 373           x=x->parent()->parent();
 374         }
 375         else{
 376           if(x==x->parent()->left()){
 377             x=x->parent();
 378             rotate_right(x,root);
 379           }
 380           x->parent()->color()=black;
 381           x->parent()->parent()->color()=red;
 382           rotate_left(x->parent()->parent(),root);
 383         }
 384       }
 385     }
 386     root->color()=black;
 387   }
 388
 389   static void link(
 390     pointer x,ordered_index_side side,pointer position,pointer header)
 391   {
 392     if(side==to_left){
 393       position->left()=x;  /* also makes leftmost=x when parent==header */
 394       if(position==header){
 395         header->parent()=x;
 396         header->right()=x;
 397       }
 398       else if(position==header->left()){
 399         header->left()=x;  /* maintain leftmost pointing to min node */
 400       }
 401     }
 402     else{
 403       position->right()=x;
 404       if(position==header->right()){
 405         header->right()=x; /* maintain rightmost pointing to max node */
 406       }
 407     }
 408     x->parent()=position;
 409     x->left()=pointer(0);
 410     x->right()=pointer(0);
 411     AugmentPolicy::add(x,pointer(header->parent()));
 412     ordered_index_node_impl::rebalance(x,header->parent());
 413   }
 414
 415   static pointer rebalance_for_extract(
 416     pointer z,parent_ref root,pointer& leftmost,pointer& rightmost)
 417   {
 418     pointer y=z;
 419     pointer x=pointer(0);
 420     pointer x_parent=pointer(0);
 421     if(y->left()==pointer(0)){    /* z has at most one non-null child. y==z. */
 422       x=y->right();               /* x might be null */
 423     }
 424     else{
 425       if(y->right()==pointer(0)){ /* z has exactly one non-null child. y==z. */
 426         x=y->left();              /* x is not null */
 427       }
 428       else{                       /* z has two non-null children.  Set y to */
 429         y=y->right();             /* z's successor. x might be null.        */
 430         while(y->left()!=pointer(0))y=y->left();
 431         x=y->right();
 432       }
 433     }
 434     AugmentPolicy::remove(y,pointer(root));
 435     if(y!=z){
 436       AugmentPolicy::copy(z,y);
 437       z->left()->parent()=y;   /* relink y in place of z. y is z's successor */
 438       y->left()=z->left();
 439       if(y!=z->right()){
 440         x_parent=y->parent();
 441         if(x!=pointer(0))x->parent()=y->parent();
 442         y->parent()->left()=x; /* y must be a child of left */
 443         y->right()=z->right();
 444         z->right()->parent()=y;
 445       }
 446       else{
 447         x_parent=y;
 448       }
 449
 450       if(root==z)                    root=y;
 451       else if(z->parent()->left()==z)z->parent()->left()=y;
 452       else                           z->parent()->right()=y;
 453       y->parent()=z->parent();
 454       ordered_index_color c=y->color();
 455       y->color()=z->color();
 456       z->color()=c;
 457       y=z;                    /* y now points to node to be actually deleted */
 458     }
 459     else{                     /* y==z */
 460       x_parent=y->parent();
 461       if(x!=pointer(0))x->parent()=y->parent();
 462       if(root==z){
 463         root=x;
 464       }
 465       else{
 466         if(z->parent()->left()==z)z->parent()->left()=x;
 467         else                      z->parent()->right()=x;
 468       }
 469       if(leftmost==z){
 470         if(z->right()==pointer(0)){ /* z->left() must be null also */
 471           leftmost=z->parent();
 472         }
 473         else{
 474           leftmost=minimum(x);      /* makes leftmost==header if z==root */
 475         }
 476       }
 477       if(rightmost==z){
 478         if(z->left()==pointer(0)){  /* z->right() must be null also */
 479           rightmost=z->parent();
 480         }
 481         else{                   /* x==z->left() */
 482           rightmost=maximum(x); /* makes rightmost==header if z==root */
 483         }
 484       }
 485     }
 486     if(y->color()!=red){
 487       while(x!=root&&(x==pointer(0)|| x->color()==black)){
 488         if(x==x_parent->left()){
 489           pointer w=x_parent->right();
 490           if(w->color()==red){
 491             w->color()=black;
 492             x_parent->color()=red;
 493             rotate_left(x_parent,root);
 494             w=x_parent->right();
 495           }
 496           if((w->left()==pointer(0)||w->left()->color()==black) &&
 497              (w->right()==pointer(0)||w->right()->color()==black)){
 498             w->color()=red;
 499             x=x_parent;
 500             x_parent=x_parent->parent();
 501           }
 502           else{
 503             if(w->right()==pointer(0 )
 504                 || w->right()->color()==black){
 505               if(w->left()!=pointer(0)) w->left()->color()=black;
 506               w->color()=red;
 507               rotate_right(w,root);
 508               w=x_parent->right();
 509             }
 510             w->color()=x_parent->color();
 511             x_parent->color()=black;
 512             if(w->right()!=pointer(0))w->right()->color()=black;
 513             rotate_left(x_parent,root);
 514             break;
 515           }
 516         }
 517         else{                   /* same as above,with right <-> left */
 518           pointer w=x_parent->left();
 519           if(w->color()==red){
 520             w->color()=black;
 521             x_parent->color()=red;
 522             rotate_right(x_parent,root);
 523             w=x_parent->left();
 524           }
 525           if((w->right()==pointer(0)||w->right()->color()==black) &&
 526              (w->left()==pointer(0)||w->left()->color()==black)){
 527             w->color()=red;
 528             x=x_parent;
 529             x_parent=x_parent->parent();
 530           }
 531           else{
 532             if(w->left()==pointer(0)||w->left()->color()==black){
 533               if(w->right()!=pointer(0))w->right()->color()=black;
 534               w->color()=red;
 535               rotate_left(w,root);
 536               w=x_parent->left();
 537             }
 538             w->color()=x_parent->color();
 539             x_parent->color()=black;
 540             if(w->left()!=pointer(0))w->left()->color()=black;
 541             rotate_right(x_parent,root);
 542             break;
 543           }
 544         }
 545       }
 546       if(x!=pointer(0))x->color()=black;
 547     }
 548     return y;
 549   }
 550
 551   static void restore(pointer x,pointer position,pointer header)
 552   {
 553     if(position->left()==pointer(0)||position->left()==header){
 554       link(x,to_left,position,header);
 555     }
 556     else{
 557       decrement(position);
 558       link(x,to_right,position,header);
 559     }
 560   }
 561
 562 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
 563   /* invariant stuff */
 564
 565   static std::size_t black_count(pointer node,pointer root)
 566   {
 567     if(node==pointer(0))return 0;
 568     std::size_t sum=0;
 569     for(;;){
 570       if(node->color()==black)++sum;
 571       if(node==root)break;
 572       node=node->parent();
 573     }
 574     return sum;
 575   }
 576 #endif
 577 };
 578
 579 template<typename AugmentPolicy,typename Super>
 580 struct ordered_index_node_trampoline:
 581   ordered_index_node_impl<
 582     AugmentPolicy,
 583     typename rebind_alloc_for<
 584       typename Super::allocator_type,
 585       char
 586     >::type
 587   >
 588 {
 589   typedef ordered_index_node_impl<
 590     AugmentPolicy,
 591     typename rebind_alloc_for<
 592       typename Super::allocator_type,
 593       char
 594     >::type
 595   > impl_type;
 596 };
 597
 598 template<typename AugmentPolicy,typename Super>
 599 struct ordered_index_node:
 600   Super,ordered_index_node_trampoline<AugmentPolicy,Super>
 601 {
 602 private:
 603   typedef ordered_index_node_trampoline<AugmentPolicy,Super> trampoline;
 604
 605 public:
 606   typedef typename trampoline::impl_type       impl_type;
 607   typedef typename trampoline::color_ref       impl_color_ref;
 608   typedef typename trampoline::parent_ref      impl_parent_ref;
 609   typedef typename trampoline::pointer         impl_pointer;
 610   typedef typename trampoline::const_pointer   const_impl_pointer;
 611   typedef typename trampoline::difference_type difference_type;
 612   typedef typename trampoline::size_type       size_type;
 613
 614   impl_color_ref      color(){return trampoline::color();}
 615   ordered_index_color color()const{return trampoline::color();}
 616   impl_parent_ref     parent(){return trampoline::parent();}
 617   impl_pointer        parent()const{return trampoline::parent();}
 618   impl_pointer&       left(){return trampoline::left();}
 619   impl_pointer        left()const{return trampoline::left();}
 620   impl_pointer&       right(){return trampoline::right();}
 621   impl_pointer        right()const{return trampoline::right();}
 622
 623   impl_pointer impl()
 624   {
 625     return static_cast<impl_pointer>(
 626       static_cast<impl_type*>(static_cast<trampoline*>(this)));
 627   }
 628
 629   const_impl_pointer impl()const
 630   {
 631     return static_cast<const_impl_pointer>(
 632       static_cast<const impl_type*>(static_cast<const trampoline*>(this)));
 633   }
 634
 635   static ordered_index_node* from_impl(impl_pointer x)
 636   {
 637     return
 638       static_cast<ordered_index_node*>(
 639         static_cast<trampoline*>(
 640           raw_ptr<impl_type*>(x)));
 641   }
 642
 643   static const ordered_index_node* from_impl(const_impl_pointer x)
 644   {
 645     return
 646       static_cast<const ordered_index_node*>(
 647         static_cast<const trampoline*>(
 648           raw_ptr<const impl_type*>(x)));
 649   }
 650
 651   /* interoperability with bidir_node_iterator */
 652
 653   static void increment(ordered_index_node*& x)
 654   {
 655     impl_pointer xi=x->impl();
 656     trampoline::increment(xi);
 657     x=from_impl(xi);
 658   }
 659
 660   static void decrement(ordered_index_node*& x)
 661   {
 662     impl_pointer xi=x->impl();
 663     trampoline::decrement(xi);
 664     x=from_impl(xi);
 665   }
 666 };
 667
 668 } /* namespace multi_index::detail */
 669
 670 } /* namespace multi_index */
 671
 672 } /* namespace boost */
 673
 674 #endif