ceph/src/boost/libs/multi_index/include/boost/multi_index/detail/hash_index_node.hpp

   1 /* Copyright 2003-2015 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
   9 #ifndef BOOST_MULTI_INDEX_DETAIL_HASH_INDEX_NODE_HPP
  10 #define BOOST_MULTI_INDEX_DETAIL_HASH_INDEX_NODE_HPP
  11
  12 #if defined(_MSC_VER)
  13 #pragma once
  14 #endif
  15
  16 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
  17 #include <boost/detail/allocator_utilities.hpp>
  18 #include <boost/multi_index/detail/raw_ptr.hpp>
  19 #include <utility>
  20
  21 namespace boost{
  22
  23 namespace multi_index{
  24
  25 namespace detail{
  26
  27 /* Certain C++ requirements on unordered associative containers (see LWG issue
  28  * #579) imply a data structure where nodes are linked in a single list, which
  29  * in its turn forces implementors to add additional overhed per node to
  30  * associate each with its corresponding bucket. Others resort to storing hash
  31  * values, we use an alternative structure providing unconditional O(1)
  32  * manipulation, even in situations of unfair hash distribution, plus some
  33  * lookup speedups. For unique indices we maintain a doubly linked list of
  34  * nodes except that if N is the first node of a bucket its associated
  35  * bucket node is embedded between N and the preceding node in the following
  36  * manner:
  37  *
  38  *        +---+   +---+       +---+   +---+
  39  *     <--+   |<--+   |    <--+   |<--+   |
  40  *   ...  | B0|   | B1|  ...  | B1|   | B2|  ...
  41  *        |   |-+ |   +-->    |   |-+ |   +-->
  42  *        +-+-+ | +---+       +-+-+ | +---+
  43  *              |   ^               |   ^
  44  *              |   |               |   |
  45  *              | +-+               | +-+
  46  *              | |                 | |
  47  *              v |                 v |
  48  *       --+---+---+---+--   --+---+---+---+--
  49  *     ... |   | B1|   |  ...  |   | B2|   | ...
  50  *       --+---+---+---+--   --+---+---+---+--
  51  *
  52  *
  53  * The fist and last nodes of buckets can be checked with
  54  *
  55  *   first node of a bucket: Npn != N
  56  *   last node of a bucket:  Nnp != N
  57  *
  58  * (n and p short for ->next(), ->prior(), bucket nodes have prior pointers
  59  * only). Pure insert and erase (without lookup) can be unconditionally done
  60  * in O(1).
  61  * For non-unique indices we add the following additional complexity: when
  62  * there is a group of 3 or more equivalent elements, they are linked as
  63  * follows:
  64  *
  65  *         +-----------------------+
  66  *         |                       v
  67  *   +---+ | +---+       +---+   +---+
  68  *   |   | +-+   |       |   |<--+   |
  69  *   | F |   | S |  ...  | P |   | L |
  70  *   |   +-->|   |       |   +-+ |   |
  71  *   +---+   +---+       +---+ | +---+
  72  *     ^                       |
  73  *     +-----------------------+
  74  *
  75  * F, S, P and L are the first, second, penultimate and last node in the
  76  * group, respectively (S and P can coincide if the group has size 3.) This
  77  * arrangement is used to skip equivalent elements in O(1) when doing lookup,
  78  * while preserving O(1) insert/erase. The following invariants identify
  79  * special positions (some of the operations have to be carefully implemented
  80  * as Xnn is not valid if Xn points to a bucket):
  81  *
  82  *   first node of a bucket: Npnp  == N
  83  *   last node of a bucket:  Nnpp  == N
  84  *   first node of a group:  Nnp != N && Nnppn == N
  85  *   second node of a group: Npn != N && Nppnn == N
  86  *   n-1 node of a group:    Nnp != N && Nnnpp == N
  87  *   last node of a group:   Npn != N && Npnnp == N
  88  *
  89  * The memory overhead is one pointer per bucket plus two pointers per node,
  90  * probably unbeatable. The resulting structure is bidirectonally traversable,
  91  * though currently we are just providing forward iteration.
  92  */
  93
  94 template<typename Allocator>
  95 struct hashed_index_node_impl;
  96
  97 /* half-header (only prior() pointer) to use for the bucket array */
  98
  99 template<typename Allocator>
 100 struct hashed_index_base_node_impl
 101 {
 102   typedef typename
 103   boost::detail::allocator::rebind_to<
 104       Allocator,hashed_index_base_node_impl
 105   >::type::pointer                          base_pointer;
 106   typedef typename
 107   boost::detail::allocator::rebind_to<
 108     Allocator,hashed_index_base_node_impl
 109   >::type::const_pointer                    const_base_pointer;
 110   typedef typename
 111   boost::detail::allocator::rebind_to<
 112     Allocator,
 113     hashed_index_node_impl<Allocator>
 114   >::type::pointer                          pointer;
 115   typedef typename
 116   boost::detail::allocator::rebind_to<
 117     Allocator,
 118     hashed_index_node_impl<Allocator>
 119   >::type::const_pointer                    const_pointer;
 120
 121   pointer& prior(){return prior_;}
 122   pointer  prior()const{return prior_;}
 123
 124 private:
 125   pointer prior_;
 126 };
 127
 128 /* full header (prior() and next()) for the nodes */
 129
 130 template<typename Allocator>
 131 struct hashed_index_node_impl:hashed_index_base_node_impl<Allocator>
 132 {
 133 private:
 134   typedef hashed_index_base_node_impl<Allocator> super;
 135
 136 public:
 137   typedef typename super::base_pointer           base_pointer;
 138   typedef typename super::const_base_pointer     const_base_pointer;
 139   typedef typename super::pointer                pointer;
 140   typedef typename super::const_pointer          const_pointer;
 141
 142   base_pointer& next(){return next_;}
 143   base_pointer  next()const{return next_;}
 144
 145   static pointer pointer_from(base_pointer x)
 146   {
 147     return static_cast<pointer>(
 148       static_cast<hashed_index_node_impl*>(
 149         raw_ptr<super*>(x)));
 150   }
 151
 152   static base_pointer base_pointer_from(pointer x)
 153   {
 154     return static_cast<base_pointer>(
 155       raw_ptr<hashed_index_node_impl*>(x));
 156   }
 157
 158 private:
 159   base_pointer next_;
 160 };
 161
 162 /* Boost.MultiIndex requires machinery to reverse unlink operations. A simple
 163  * way to make a pointer-manipulation function undoable is to templatize
 164  * its internal pointer assignments with a functor that, besides doing the
 165  * assignment, keeps track of the original pointer values and can later undo
 166  * the operations in reverse order.
 167  */
 168
 169 struct default_assigner
 170 {
 171   template<typename T> void operator()(T& x,const T& val){x=val;}
 172 };
 173
 174 template<typename Node>
 175 struct unlink_undo_assigner
 176 {
 177   typedef typename Node::base_pointer base_pointer;
 178   typedef typename Node::pointer      pointer;
 179
 180   unlink_undo_assigner():pointer_track_count(0),base_pointer_track_count(0){}
 181
 182   void operator()(pointer& x,pointer val)
 183   {
 184     pointer_tracks[pointer_track_count].x=&x;
 185     pointer_tracks[pointer_track_count++].val=x;
 186     x=val;
 187   }
 188
 189   void operator()(base_pointer& x,base_pointer val)
 190   {
 191     base_pointer_tracks[base_pointer_track_count].x=&x;
 192     base_pointer_tracks[base_pointer_track_count++].val=x;
 193     x=val;
 194   }
 195
 196   void operator()() /* undo op */
 197   {
 198     /* in the absence of aliasing, restitution order is immaterial */
 199
 200     while(pointer_track_count--){
 201       *(pointer_tracks[pointer_track_count].x)=
 202         pointer_tracks[pointer_track_count].val;
 203     }
 204     while(base_pointer_track_count--){
 205       *(base_pointer_tracks[base_pointer_track_count].x)=
 206         base_pointer_tracks[base_pointer_track_count].val;
 207     }
 208   }
 209
 210   struct pointer_track     {pointer*      x; pointer      val;};
 211   struct base_pointer_track{base_pointer* x; base_pointer val;};
 212
 213   /* We know the maximum number of pointer and base pointer assignments that
 214    * the two unlink versions do, so we can statically reserve the needed
 215    * storage.
 216    */
 217
 218   pointer_track      pointer_tracks[3];
 219   int                pointer_track_count;
 220   base_pointer_track base_pointer_tracks[2];
 221   int                base_pointer_track_count;
 222 };
 223
 224 /* algorithmic stuff for unique and non-unique variants */
 225
 226 struct hashed_unique_tag{};
 227 struct hashed_non_unique_tag{};
 228
 229 template<typename Node,typename Category>
 230 struct hashed_index_node_alg;
 231
 232 template<typename Node>
 233 struct hashed_index_node_alg<Node,hashed_unique_tag>
 234 {
 235   typedef typename Node::base_pointer       base_pointer;
 236   typedef typename Node::const_base_pointer const_base_pointer;
 237   typedef typename Node::pointer            pointer;
 238   typedef typename Node::const_pointer      const_pointer;
 239
 240   static bool is_first_of_bucket(pointer x)
 241   {
 242     return x->prior()->next()!=base_pointer_from(x);
 243   }
 244
 245   static pointer after(pointer x)
 246   {
 247     return is_last_of_bucket(x)?x->next()->prior():pointer_from(x->next());
 248   }
 249
 250   static pointer after_local(pointer x)
 251   {
 252     return is_last_of_bucket(x)?pointer(0):pointer_from(x->next());
 253   }
 254
 255   static pointer next_to_inspect(pointer x)
 256   {
 257     return is_last_of_bucket(x)?pointer(0):pointer_from(x->next());
 258   }
 259
 260   static void link(pointer x,base_pointer buc,pointer end)
 261   {
 262     if(buc->prior()==pointer(0)){ /* empty bucket */
 263       x->prior()=end->prior();
 264       x->next()=end->prior()->next();
 265       x->prior()->next()=buc;
 266       buc->prior()=x;
 267       end->prior()=x;
 268     }
 269     else{
 270       x->prior()=buc->prior()->prior();
 271       x->next()=base_pointer_from(buc->prior());
 272       buc->prior()=x;
 273       x->next()->prior()=x;
 274     }
 275   }
 276
 277   static void unlink(pointer x)
 278   {
 279     default_assigner assign;
 280     unlink(x,assign);
 281   }
 282
 283   typedef unlink_undo_assigner<Node> unlink_undo;
 284
 285   template<typename Assigner>
 286   static void unlink(pointer x,Assigner& assign)
 287   {
 288     if(is_first_of_bucket(x)){
 289       if(is_last_of_bucket(x)){
 290         assign(x->prior()->next()->prior(),pointer(0));
 291         assign(x->prior()->next(),x->next());
 292         assign(x->next()->prior()->prior(),x->prior());
 293       }
 294       else{
 295         assign(x->prior()->next()->prior(),pointer_from(x->next()));
 296         assign(x->next()->prior(),x->prior());
 297       }
 298     }
 299     else if(is_last_of_bucket(x)){
 300       assign(x->prior()->next(),x->next());
 301       assign(x->next()->prior()->prior(),x->prior());
 302     }
 303     else{
 304       assign(x->prior()->next(),x->next());
 305       assign(x->next()->prior(),x->prior());
 306     }
 307   }
 308
 309   /* used only at rehashing */
 310
 311   static void append(pointer x,pointer end)
 312   {
 313     x->prior()=end->prior();
 314     x->next()=end->prior()->next();
 315     x->prior()->next()=base_pointer_from(x);
 316     end->prior()=x;
 317   }
 318
 319   static bool unlink_last(pointer end)
 320   {
 321     /* returns true iff bucket is emptied */
 322
 323     pointer x=end->prior();
 324     if(x->prior()->next()==base_pointer_from(x)){
 325       x->prior()->next()=x->next();
 326       end->prior()=x->prior();
 327       return false;
 328     }
 329     else{
 330       x->prior()->next()->prior()=pointer(0);
 331       x->prior()->next()=x->next();
 332       end->prior()=x->prior();
 333       return true;
 334     }
 335   }
 336
 337 private:
 338   static pointer pointer_from(base_pointer x)
 339   {
 340     return Node::pointer_from(x);
 341   }
 342
 343   static base_pointer base_pointer_from(pointer x)
 344   {
 345     return Node::base_pointer_from(x);
 346   }
 347
 348   static bool is_last_of_bucket(pointer x)
 349   {
 350     return x->next()->prior()!=x;
 351   }
 352 };
 353
 354 template<typename Node>
 355 struct hashed_index_node_alg<Node,hashed_non_unique_tag>
 356 {
 357   typedef typename Node::base_pointer       base_pointer;
 358   typedef typename Node::const_base_pointer const_base_pointer;
 359   typedef typename Node::pointer            pointer;
 360   typedef typename Node::const_pointer      const_pointer;
 361
 362   static bool is_first_of_bucket(pointer x)
 363   {
 364     return x->prior()->next()->prior()==x;
 365   }
 366
 367   static bool is_first_of_group(pointer x)
 368   {
 369     return
 370       x->next()->prior()!=x&&
 371       x->next()->prior()->prior()->next()==base_pointer_from(x);
 372   }
 373
 374   static pointer after(pointer x)
 375   {
 376     if(x->next()->prior()==x)return pointer_from(x->next());
 377     if(x->next()->prior()->prior()==x)return x->next()->prior();
 378     if(x->next()->prior()->prior()->next()==base_pointer_from(x))
 379       return pointer_from(x->next());
 380     return pointer_from(x->next())->next()->prior();
 381   }
 382
 383   static pointer after_local(pointer x)
 384   {
 385     if(x->next()->prior()==x)return pointer_from(x->next());
 386     if(x->next()->prior()->prior()==x)return pointer(0);
 387     if(x->next()->prior()->prior()->next()==base_pointer_from(x))
 388       return pointer_from(x->next());
 389     return pointer_from(x->next())->next()->prior();
 390   }
 391
 392   static pointer next_to_inspect(pointer x)
 393   {
 394     if(x->next()->prior()==x)return pointer_from(x->next());
 395     if(x->next()->prior()->prior()==x)return pointer(0);
 396     if(x->next()->prior()->next()->prior()!=x->next()->prior())
 397       return pointer(0);
 398     return pointer_from(x->next()->prior()->next());
 399   }
 400
 401   static void link(pointer x,base_pointer buc,pointer end)
 402   {
 403     if(buc->prior()==pointer(0)){ /* empty bucket */
 404       x->prior()=end->prior();
 405       x->next()=end->prior()->next();
 406       x->prior()->next()=buc;
 407       buc->prior()=x;
 408       end->prior()=x;
 409     }
 410     else{
 411       x->prior()=buc->prior()->prior();
 412       x->next()=base_pointer_from(buc->prior());
 413       buc->prior()=x;
 414       x->next()->prior()=x;
 415     }
 416   };
 417
 418   static void link(pointer x,pointer first,pointer last)
 419   {
 420     x->prior()=first->prior();
 421     x->next()=base_pointer_from(first);
 422     if(is_first_of_bucket(first)){
 423       x->prior()->next()->prior()=x;
 424     }
 425     else{
 426       x->prior()->next()=base_pointer_from(x);
 427     }
 428
 429     if(first==last){
 430       last->prior()=x;
 431     }
 432     else if(first->next()==base_pointer_from(last)){
 433       first->prior()=last;
 434       first->next()=base_pointer_from(x);
 435     }
 436     else{
 437       pointer second=pointer_from(first->next()),
 438               lastbutone=last->prior();
 439       second->prior()=first;
 440       first->prior()=last;
 441       lastbutone->next()=base_pointer_from(x);
 442     }
 443   }
 444
 445   static void unlink(pointer x)
 446   {
 447     default_assigner assign;
 448     unlink(x,assign);
 449   }
 450
 451   typedef unlink_undo_assigner<Node> unlink_undo;
 452
 453   template<typename Assigner>
 454   static void unlink(pointer x,Assigner& assign)
 455   {
 456     if(x->prior()->next()==base_pointer_from(x)){
 457       if(x->next()->prior()==x){
 458         left_unlink(x,assign);
 459         right_unlink(x,assign);
 460       }
 461       else if(x->next()->prior()->prior()==x){           /* last of bucket */
 462         left_unlink(x,assign);
 463         right_unlink_last_of_bucket(x,assign);
 464       }
 465       else if(x->next()->prior()->prior()->next()==
 466               base_pointer_from(x)){                /* first of group size */
 467         left_unlink(x,assign);
 468         right_unlink_first_of_group(x,assign);
 469       }
 470       else{                                                /* n-1 of group */
 471         unlink_last_but_one_of_group(x,assign);
 472       }
 473     }
 474     else if(x->prior()->next()->prior()==x){            /* first of bucket */
 475       if(x->next()->prior()==x){
 476         left_unlink_first_of_bucket(x,assign);
 477         right_unlink(x,assign);
 478       }
 479       else if(x->next()->prior()->prior()==x){           /* last of bucket */
 480         assign(x->prior()->next()->prior(),pointer(0));
 481         assign(x->prior()->next(),x->next());
 482         assign(x->next()->prior()->prior(),x->prior());
 483       }
 484       else{                                              /* first of group */
 485         left_unlink_first_of_bucket(x,assign);
 486         right_unlink_first_of_group(x,assign);
 487       }
 488     }
 489     else if(x->next()->prior()->prior()==x){   /* last of group and bucket */
 490       left_unlink_last_of_group(x,assign);
 491       right_unlink_last_of_bucket(x,assign);
 492     }
 493     else if(pointer_from(x->prior()->prior()->next())
 494             ->next()==base_pointer_from(x)){            /* second of group */
 495       unlink_second_of_group(x,assign);
 496     }
 497     else{                              /* last of group, ~(last of bucket) */
 498       left_unlink_last_of_group(x,assign);
 499       right_unlink(x,assign);
 500     }
 501   }
 502
 503   /* used only at rehashing */
 504
 505   static void link_range(
 506     pointer first,pointer last,base_pointer buc,pointer cend)
 507   {
 508     if(buc->prior()==pointer(0)){ /* empty bucket */
 509       first->prior()=cend->prior();
 510       last->next()=cend->prior()->next();
 511       first->prior()->next()=buc;
 512       buc->prior()=first;
 513       cend->prior()=last;
 514     }
 515     else{
 516       first->prior()=buc->prior()->prior();
 517       last->next()=base_pointer_from(buc->prior());
 518       buc->prior()=first;
 519       last->next()->prior()=last;
 520     }
 521   }
 522
 523   static void append_range(pointer first,pointer last,pointer cend)
 524   {
 525     first->prior()=cend->prior();
 526     last->next()=cend->prior()->next();
 527     first->prior()->next()=base_pointer_from(first);
 528     cend->prior()=last;
 529   }
 530
 531   static std::pair<pointer,bool> unlink_last_group(pointer end)
 532   {
 533     /* returns first of group true iff bucket is emptied */
 534
 535     pointer x=end->prior();
 536     if(x->prior()->next()==base_pointer_from(x)){
 537       x->prior()->next()=x->next();
 538       end->prior()=x->prior();
 539       return std::make_pair(x,false);
 540     }
 541     else if(x->prior()->next()->prior()==x){
 542       x->prior()->next()->prior()=pointer(0);
 543       x->prior()->next()=x->next();
 544       end->prior()=x->prior();
 545       return std::make_pair(x,true);
 546     }
 547     else{
 548       pointer y=pointer_from(x->prior()->next());
 549
 550       if(y->prior()->next()==base_pointer_from(y)){
 551         y->prior()->next()=x->next();
 552         end->prior()=y->prior();
 553         return std::make_pair(y,false);
 554       }
 555       else{
 556         y->prior()->next()->prior()=pointer(0);
 557         y->prior()->next()=x->next();
 558         end->prior()=y->prior();
 559         return std::make_pair(y,true);
 560       }
 561     }
 562   }
 563
 564   static void unlink_range(pointer first,pointer last)
 565   {
 566     if(is_first_of_bucket(first)){
 567       if(is_last_of_bucket(last)){
 568         first->prior()->next()->prior()=pointer(0);
 569         first->prior()->next()=last->next();
 570         last->next()->prior()->prior()=first->prior();
 571       }
 572       else{
 573         first->prior()->next()->prior()=pointer_from(last->next());
 574         last->next()->prior()=first->prior();
 575       }
 576     }
 577     else if(is_last_of_bucket(last)){
 578       first->prior()->next()=last->next();
 579       last->next()->prior()->prior()=first->prior();
 580     }
 581     else{
 582       first->prior()->next()=last->next();
 583       last->next()->prior()=first->prior();
 584     }
 585   }
 586
 587 private:
 588   static pointer pointer_from(base_pointer x)
 589   {
 590     return Node::pointer_from(x);
 591   }
 592
 593   static base_pointer base_pointer_from(pointer x)
 594   {
 595     return Node::base_pointer_from(x);
 596   }
 597
 598   static bool is_last_of_bucket(pointer x)
 599   {
 600     return x->next()->prior()->prior()==x;
 601   }
 602
 603   template<typename Assigner>
 604   static void left_unlink(pointer x,Assigner& assign)
 605   {
 606     assign(x->prior()->next(),x->next());
 607   }
 608
 609   template<typename Assigner>
 610   static void right_unlink(pointer x,Assigner& assign)
 611   {
 612     assign(x->next()->prior(),x->prior());
 613   }
 614
 615   template<typename Assigner>
 616   static void left_unlink_first_of_bucket(pointer x,Assigner& assign)
 617   {
 618     assign(x->prior()->next()->prior(),pointer_from(x->next()));
 619   }
 620
 621   template<typename Assigner>
 622   static void right_unlink_last_of_bucket(pointer x,Assigner& assign)
 623   {
 624     assign(x->next()->prior()->prior(),x->prior());
 625   }
 626
 627   template<typename Assigner>
 628   static void right_unlink_first_of_group(pointer x,Assigner& assign)
 629   {
 630     pointer second=pointer_from(x->next()),
 631             last=second->prior(),
 632             lastbutone=last->prior();
 633     if(second==lastbutone){
 634       assign(second->next(),base_pointer_from(last));
 635       assign(second->prior(),x->prior());
 636     }
 637     else{
 638       assign(lastbutone->next(),base_pointer_from(second));
 639       assign(second->next()->prior(),last);
 640       assign(second->prior(),x->prior());
 641     }
 642   }
 643
 644   template<typename Assigner>
 645   static void left_unlink_last_of_group(pointer x,Assigner& assign)
 646   {
 647     pointer lastbutone=x->prior(),
 648             first=pointer_from(lastbutone->next()),
 649             second=pointer_from(first->next());
 650     if(lastbutone==second){
 651       assign(lastbutone->prior(),first);
 652       assign(lastbutone->next(),x->next());
 653     }
 654     else{
 655       assign(second->prior(),lastbutone);
 656       assign(lastbutone->prior()->next(),base_pointer_from(first));
 657       assign(lastbutone->next(),x->next());
 658     }
 659   }
 660
 661   template<typename Assigner>
 662   static void unlink_last_but_one_of_group(pointer x,Assigner& assign)
 663   {
 664     pointer first=pointer_from(x->next()),
 665             second=pointer_from(first->next()),
 666             last=second->prior();
 667     if(second==x){
 668       assign(last->prior(),first);
 669       assign(first->next(),base_pointer_from(last));
 670     }
 671     else{
 672       assign(last->prior(),x->prior());
 673       assign(x->prior()->next(),base_pointer_from(first));
 674     }
 675   }
 676
 677   template<typename Assigner>
 678   static void unlink_second_of_group(pointer x,Assigner& assign)
 679   {
 680     pointer last=x->prior(),
 681             lastbutone=last->prior(),
 682             first=pointer_from(lastbutone->next());
 683     if(lastbutone==x){
 684       assign(first->next(),base_pointer_from(last));
 685       assign(last->prior(),first);
 686     }
 687     else{
 688       assign(first->next(),x->next());
 689       assign(x->next()->prior(),last);
 690     }
 691   }
 692 };
 693
 694 template<typename Super>
 695 struct hashed_index_node_trampoline:
 696   hashed_index_node_impl<
 697     typename boost::detail::allocator::rebind_to<
 698       typename Super::allocator_type,
 699       char
 700     >::type
 701   >
 702 {
 703   typedef typename boost::detail::allocator::rebind_to<
 704     typename Super::allocator_type,
 705     char
 706   >::type                                               impl_allocator_type;
 707   typedef hashed_index_node_impl<impl_allocator_type>   impl_type;
 708 };
 709
 710 template<typename Super,typename Category>
 711 struct hashed_index_node:
 712   Super,hashed_index_node_trampoline<Super>
 713 {
 714 private:
 715   typedef hashed_index_node_trampoline<Super> trampoline;
 716
 717 public:
 718   typedef typename trampoline::impl_type          impl_type;
 719   typedef hashed_index_node_alg<
 720     impl_type,Category>                           node_alg;
 721   typedef typename trampoline::base_pointer       impl_base_pointer;
 722   typedef typename trampoline::const_base_pointer const_impl_base_pointer;
 723   typedef typename trampoline::pointer            impl_pointer;
 724   typedef typename trampoline::const_pointer      const_impl_pointer;
 725
 726   impl_pointer&      prior(){return trampoline::prior();}
 727   impl_pointer       prior()const{return trampoline::prior();}
 728   impl_base_pointer& next(){return trampoline::next();}
 729   impl_base_pointer  next()const{return trampoline::next();}
 730
 731   impl_pointer impl()
 732   {
 733     return static_cast<impl_pointer>(
 734       static_cast<impl_type*>(static_cast<trampoline*>(this)));
 735   }
 736
 737   const_impl_pointer impl()const
 738   {
 739     return static_cast<const_impl_pointer>(
 740       static_cast<const impl_type*>(static_cast<const trampoline*>(this)));
 741   }
 742
 743   static hashed_index_node* from_impl(impl_pointer x)
 744   {
 745     return
 746       static_cast<hashed_index_node*>(
 747         static_cast<trampoline*>(
 748           raw_ptr<impl_type*>(x)));
 749   }
 750
 751   static const hashed_index_node* from_impl(const_impl_pointer x)
 752   {
 753     return
 754       static_cast<const hashed_index_node*>(
 755         static_cast<const trampoline*>(
 756           raw_ptr<const impl_type*>(x)));
 757   }
 758
 759   /* interoperability with hashed_index_iterator */
 760
 761   static void increment(hashed_index_node*& x)
 762   {
 763     x=from_impl(node_alg::after(x->impl()));
 764   }
 765
 766   static void increment_local(hashed_index_node*& x)
 767   {
 768     x=from_impl(node_alg::after_local(x->impl()));
 769   }
 770 };
 771
 772 } /* namespace multi_index::detail */
 773
 774 } /* namespace multi_index */
 775
 776 } /* namespace boost */
 777
 778 #endif