libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/insert_join_fn_imps.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the terms
   7 // of the GNU General Public License as published by the Free Software
   8 // Foundation; either version 2, or (at your option) any later
   9 // version.
  10
  11 // This library is distributed in the hope that it will be useful, but
  12 // WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 // General Public License for more details.
  15
  16 // You should have received a copy of the GNU General Public License
  17 // along with this library; see the file COPYING.  If not, write to
  18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
  19 // MA 02111-1307, USA.
  20
  21 // As a special exception, you may use this file as part of a free
  22 // software library without restriction.  Specifically, if other files
  23 // instantiate templates or use macros or inline functions from this
  24 // file, or you compile this file and link it with other files to
  25 // produce an executable, this file does not by itself cause the
  26 // resulting executable to be covered by the GNU General Public
  27 // License.  This exception does not however invalidate any other
  28 // reasons why the executable file might be covered by the GNU General
  29 // Public License.
  30
  31 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  32
  33 // Permission to use, copy, modify, sell, and distribute this software
  34 // is hereby granted without fee, provided that the above copyright
  35 // notice appears in all copies, and that both that copyright notice
  36 // and this permission notice appear in supporting documentation. None
  37 // of the above authors, nor IBM Haifa Research Laboratories, make any
  38 // representation about the suitability of this software for any
  39 // purpose. It is provided "as is" without express or implied
  40 // warranty.
  41
  42 /**
  43  * @file insert_join_fn_imps.hpp
  44  * Contains an implementation class for bin_search_tree_.
  45  */
  46
  47 PB_DS_CLASS_T_DEC
  48 void
  49 PB_DS_CLASS_C_DEC::
  50 join(PB_DS_CLASS_C_DEC& other)
  51 {
  52   PB_DS_DBG_ONLY(assert_valid(););
  53   PB_DS_DBG_ONLY(other.assert_valid(););
  54
  55   split_join_branch_bag bag;
  56
  57   if (!join_prep(other, bag))
  58     {
  59       PB_DS_DBG_ONLY(assert_valid(););
  60       PB_DS_DBG_ONLY(other.assert_valid(););
  61
  62       return;
  63     }
  64
  65   m_p_head->m_p_parent = rec_join(m_p_head->m_p_parent, other.m_p_head->m_p_parent, 0, bag);
  66
  67   m_p_head->m_p_parent->m_p_parent = m_p_head;
  68
  69   m_size += other.m_size;
  70
  71   other.initialize();
  72
  73   PB_DS_DBG_ONLY(other.assert_valid(););
  74
  75   m_p_head->m_p_min = leftmost_descendant(m_p_head->m_p_parent);
  76   m_p_head->m_p_max = rightmost_descendant(m_p_head->m_p_parent);
  77
  78   PB_DS_DBG_ONLY(assert_valid(););
  79 }
  80
  81 PB_DS_CLASS_T_DEC
  82 bool
  83 PB_DS_CLASS_C_DEC::
  84 join_prep(PB_DS_CLASS_C_DEC& other, split_join_branch_bag& r_bag)
  85 {
  86   PB_DS_DBG_ONLY(assert_valid();)
  87     PB_DS_DBG_ONLY(other.assert_valid();)
  88
  89     if (other.m_size == 0)
  90       return (false);
  91
  92   if (m_size == 0)
  93     {
  94       value_swap(other);
  95
  96       return (false);
  97     }
  98
  99   const bool greater = synth_e_access_traits::cmp_keys(
 100                                                        PB_DS_V2F(static_cast<const_leaf_pointer>(
 101                                                                                                  m_p_head->m_p_max)->value()),
 102                                                        PB_DS_V2F(static_cast<const_leaf_pointer>(
 103                                                                                                  other.m_p_head->m_p_min)->value()));
 104
 105   const bool lesser = synth_e_access_traits::cmp_keys(
 106                                                       PB_DS_V2F(static_cast<const_leaf_pointer>(
 107                                                                                                 other.m_p_head->m_p_max)->value()),
 108                                                       PB_DS_V2F(static_cast<const_leaf_pointer>(
 109                                                                                                 m_p_head->m_p_min)->value()));
 110
 111   if (!greater&&  !lesser)
 112     throw join_error();
 113
 114   rec_join_prep(m_p_head->m_p_parent, other.m_p_head->m_p_parent, r_bag);
 115
 116   PB_DS_DBG_ONLY(map_debug_base::join(other);)
 117
 118     return (true);
 119 }
 120
 121 PB_DS_CLASS_T_DEC
 122 void
 123 PB_DS_CLASS_C_DEC::
 124 rec_join_prep(const_node_pointer p_l, const_node_pointer p_r, split_join_branch_bag& r_bag)
 125 {
 126   if (p_l->m_type == pat_trie_leaf_node_type)
 127     {
 128       if (p_r->m_type == pat_trie_leaf_node_type)
 129         {
 130           rec_join_prep(
 131                         static_cast<const_leaf_pointer>(p_l),
 132                         static_cast<const_leaf_pointer>(p_r),
 133                         r_bag);
 134
 135           return;
 136         }
 137
 138       PB_DS_DBG_ASSERT(p_r->m_type == pat_trie_internal_node_type);
 139
 140       rec_join_prep(
 141                     static_cast<const_leaf_pointer>(p_l),
 142                     static_cast<const_internal_node_pointer>(p_r),
 143                     r_bag);
 144
 145       return;
 146     }
 147
 148   PB_DS_DBG_ASSERT(p_l->m_type == pat_trie_internal_node_type);
 149
 150   if (p_r->m_type == pat_trie_leaf_node_type)
 151     {
 152       rec_join_prep(
 153                     static_cast<const_internal_node_pointer>(p_l),
 154                     static_cast<const_leaf_pointer>(p_r),
 155                     r_bag);
 156
 157       return;
 158     }
 159
 160   PB_DS_DBG_ASSERT(p_r->m_type == pat_trie_internal_node_type);
 161
 162   rec_join_prep(
 163                 static_cast<const_internal_node_pointer>(p_l),
 164                 static_cast<const_internal_node_pointer>(p_r),
 165                 r_bag);
 166 }
 167
 168 PB_DS_CLASS_T_DEC
 169 void
 170 PB_DS_CLASS_C_DEC::
 171 rec_join_prep(const_leaf_pointer /*p_l*/, const_leaf_pointer /*p_r*/, split_join_branch_bag& r_bag)
 172 {
 173   r_bag.add_branch();
 174 }
 175
 176 PB_DS_CLASS_T_DEC
 177 void
 178 PB_DS_CLASS_C_DEC::
 179 rec_join_prep(const_leaf_pointer /*p_l*/, const_internal_node_pointer /*p_r*/, split_join_branch_bag& r_bag)
 180 {
 181   r_bag.add_branch();
 182 }
 183
 184 PB_DS_CLASS_T_DEC
 185 void
 186 PB_DS_CLASS_C_DEC::
 187 rec_join_prep(const_internal_node_pointer /*p_l*/, const_leaf_pointer /*p_r*/, split_join_branch_bag& r_bag)
 188 {
 189   r_bag.add_branch();
 190 }
 191
 192 PB_DS_CLASS_T_DEC
 193 void
 194 PB_DS_CLASS_C_DEC::
 195 rec_join_prep(const_internal_node_pointer p_l, const_internal_node_pointer p_r, split_join_branch_bag& r_bag)
 196 {
 197   if (p_l->get_e_ind() == p_r->get_e_ind()&&
 198       synth_e_access_traits::equal_prefixes(
 199                                             p_l->pref_b_it(),
 200                                             p_l->pref_e_it(),
 201                                             p_r->pref_b_it(),
 202                                             p_r->pref_e_it()))
 203     {
 204       for (typename internal_node::const_iterator it = p_r->begin();
 205            it != p_r->end(); ++ it)
 206         {
 207           const_node_pointer p_l_join_child =
 208             p_l->get_join_child(*it, this);
 209
 210           if (p_l_join_child != NULL)
 211             rec_join_prep(p_l_join_child, * it, r_bag);
 212         }
 213
 214       return;
 215     }
 216
 217   if (p_r->get_e_ind() < p_l->get_e_ind()&&
 218       p_r->should_be_mine(
 219                           p_l->pref_b_it(),
 220                           p_l->pref_e_it(),
 221                           0,
 222                           this))
 223     {
 224       const_node_pointer p_r_join_child =
 225         p_r->get_join_child(p_l, this);
 226
 227       if (p_r_join_child != NULL)
 228         rec_join_prep(p_r_join_child, p_l, r_bag);
 229
 230       return;
 231     }
 232
 233   if (p_r->get_e_ind() < p_l->get_e_ind()&&
 234       p_r->should_be_mine(
 235                           p_l->pref_b_it(),
 236                           p_l->pref_e_it(),
 237                           0,
 238                           this))
 239     {
 240       const_node_pointer p_r_join_child =
 241         p_r->get_join_child(p_l, this);
 242
 243       if (p_r_join_child != NULL)
 244         rec_join_prep(p_r_join_child, p_l, r_bag);
 245
 246       return;
 247     }
 248
 249   r_bag.add_branch();
 250 }
 251
 252 PB_DS_CLASS_T_DEC
 253 typename PB_DS_CLASS_C_DEC::node_pointer
 254 PB_DS_CLASS_C_DEC::
 255 rec_join(node_pointer p_l, node_pointer p_r, size_type checked_ind, split_join_branch_bag& r_bag)
 256 {
 257   PB_DS_DBG_ASSERT(p_r != NULL);
 258
 259   if (p_l == NULL)
 260     {
 261       apply_update(p_r, (node_update* )this);
 262
 263       return (p_r);
 264     }
 265
 266   if (p_l->m_type == pat_trie_leaf_node_type)
 267     {
 268       if (p_r->m_type == pat_trie_leaf_node_type)
 269         {
 270           node_pointer p_ret = rec_join(
 271                                         static_cast<leaf_pointer>(p_l),
 272                                         static_cast<leaf_pointer>(p_r),
 273                                         r_bag);
 274
 275           apply_update(p_ret, (node_update* )this);
 276
 277           return (p_ret);
 278         }
 279
 280       PB_DS_DBG_ASSERT(p_r->m_type == pat_trie_internal_node_type);
 281
 282       node_pointer p_ret = rec_join(
 283                                     static_cast<leaf_pointer>(p_l),
 284                                     static_cast<internal_node_pointer>(p_r),
 285                                     checked_ind,
 286                                     r_bag);
 287
 288       apply_update(p_ret, (node_update* )this);
 289
 290       return (p_ret);
 291     }
 292
 293   PB_DS_DBG_ASSERT(p_l->m_type == pat_trie_internal_node_type);
 294
 295   if (p_r->m_type == pat_trie_leaf_node_type)
 296     {
 297       node_pointer p_ret = rec_join(
 298                                     static_cast<internal_node_pointer>(p_l),
 299                                     static_cast<leaf_pointer>(p_r),
 300                                     checked_ind,
 301                                     r_bag);
 302
 303       apply_update(p_ret, (node_update* )this);
 304
 305       return (p_ret);
 306     }
 307
 308   PB_DS_DBG_ASSERT(p_r->m_type == pat_trie_internal_node_type);
 309
 310   node_pointer p_ret = rec_join(
 311                                 static_cast<internal_node_pointer>(p_l),
 312                                 static_cast<internal_node_pointer>(p_r),
 313                                 r_bag);
 314
 315   apply_update(p_ret, (node_update* )this);
 316
 317   return (p_ret);
 318 }
 319
 320 PB_DS_CLASS_T_DEC
 321 typename PB_DS_CLASS_C_DEC::node_pointer
 322 PB_DS_CLASS_C_DEC::
 323 rec_join(leaf_pointer p_l, leaf_pointer p_r, split_join_branch_bag& r_bag)
 324 {
 325   PB_DS_DBG_ASSERT(p_r != NULL);
 326
 327   if (p_l == NULL)
 328     return (p_r);
 329
 330   node_pointer p_ret = insert_branch(p_l, p_r, r_bag);
 331
 332   PB_DS_DBG_ASSERT(recursive_count_leafs(p_ret) == 2);
 333
 334   return (p_ret);
 335 }
 336
 337 PB_DS_CLASS_T_DEC
 338 typename PB_DS_CLASS_C_DEC::node_pointer
 339 PB_DS_CLASS_C_DEC::
 340 rec_join(leaf_pointer p_l, internal_node_pointer p_r, size_type checked_ind, split_join_branch_bag& r_bag)
 341 {
 342 #ifdef PB_DS_PAT_TRIE_DEBUG_
 343   const size_type lhs_leafs = recursive_count_leafs(p_l);
 344
 345   const size_type rhs_leafs = recursive_count_leafs(p_r);
 346 #endif // #ifdef PB_DS_PAT_TRIE_DEBUG_
 347
 348   PB_DS_DBG_ASSERT(p_r != NULL);
 349
 350   node_pointer p_ret = rec_join(p_r, p_l, checked_ind, r_bag);
 351
 352   PB_DS_DBG_ASSERT(recursive_count_leafs(p_ret) ==
 353                    lhs_leafs + rhs_leafs);
 354
 355   return (p_ret);
 356 }
 357
 358 PB_DS_CLASS_T_DEC
 359 typename PB_DS_CLASS_C_DEC::node_pointer
 360 PB_DS_CLASS_C_DEC::
 361 rec_join(internal_node_pointer p_l, leaf_pointer p_r, size_type checked_ind, split_join_branch_bag& r_bag)
 362 {
 363   PB_DS_DBG_ASSERT(p_l != NULL);
 364   PB_DS_DBG_ASSERT(p_r != NULL);
 365
 366 #ifdef PB_DS_PAT_TRIE_DEBUG_
 367   const size_type lhs_leafs = recursive_count_leafs(p_l);
 368
 369   const size_type rhs_leafs = recursive_count_leafs(p_r);
 370 #endif // #ifdef PB_DS_PAT_TRIE_DEBUG_
 371
 372   if (!p_l->should_be_mine(
 373                            pref_begin(p_r),
 374                            pref_end(p_r),
 375                            checked_ind,
 376                            this))
 377     {
 378       node_pointer p_ret = insert_branch(p_l, p_r, r_bag);
 379
 380       PB_DS_DBG_ONLY(p_ret->assert_valid(this);)
 381
 382         PB_DS_DBG_ASSERT(recursive_count_leafs(p_ret) ==
 383                          lhs_leafs + rhs_leafs);
 384
 385       return (p_ret);
 386     }
 387
 388   node_pointer p_pot_child = p_l->add_child(
 389                                             p_r,
 390                                             pref_begin(p_r),
 391                                             pref_end(p_r),
 392                                             this);
 393
 394   if (p_pot_child != p_r)
 395     {
 396       node_pointer p_new_child = rec_join(
 397                                           p_pot_child,
 398                                           p_r,
 399                                           p_l->get_e_ind(),
 400                                           r_bag);
 401
 402       p_l->replace_child(
 403                          p_new_child,
 404                          pref_begin(p_new_child),
 405                          pref_end(p_new_child),
 406                          this);
 407     }
 408
 409   PB_DS_DBG_ONLY(p_l->assert_valid(this));
 410
 411   PB_DS_DBG_ASSERT(recursive_count_leafs(p_l) ==
 412                    lhs_leafs + rhs_leafs);
 413
 414   return (p_l);
 415 }
 416
 417 PB_DS_CLASS_T_DEC
 418 typename PB_DS_CLASS_C_DEC::node_pointer
 419 PB_DS_CLASS_C_DEC::
 420 rec_join(internal_node_pointer p_l, internal_node_pointer p_r, split_join_branch_bag& r_bag)
 421 {
 422   PB_DS_DBG_ASSERT(p_l != NULL);
 423   PB_DS_DBG_ASSERT(p_r != NULL);
 424
 425 #ifdef PB_DS_PAT_TRIE_DEBUG_
 426   const size_type lhs_leafs = recursive_count_leafs(p_l);
 427
 428   const size_type rhs_leafs = recursive_count_leafs(p_r);
 429 #endif // #ifdef PB_DS_PAT_TRIE_DEBUG_
 430
 431   if (p_l->get_e_ind() == p_r->get_e_ind()&&
 432       synth_e_access_traits::equal_prefixes(
 433                                             p_l->pref_b_it(),
 434                                             p_l->pref_e_it(),
 435                                             p_r->pref_b_it(),
 436                                             p_r->pref_e_it()))
 437     {
 438       for (typename internal_node::iterator it = p_r->begin();
 439            it != p_r->end(); ++ it)
 440         {
 441           node_pointer p_new_child = rec_join(
 442                                               p_l->get_join_child(*it, this),
 443                                               * it,
 444                                               0,
 445                                               r_bag);
 446
 447           p_l->replace_child(
 448                              p_new_child,
 449                              pref_begin(p_new_child),
 450                              pref_end(p_new_child),
 451                              this);
 452         }
 453
 454       p_r->~internal_node();
 455
 456       s_internal_node_allocator.deallocate(p_r, 1);
 457
 458       PB_DS_DBG_ONLY(p_l->assert_valid(this);)
 459
 460         PB_DS_DBG_ASSERT(recursive_count_leafs(p_l) ==
 461                          lhs_leafs + rhs_leafs);
 462
 463       return (p_l);
 464     }
 465
 466   if (p_l->get_e_ind() < p_r->get_e_ind()&&
 467       p_l->should_be_mine(
 468                           p_r->pref_b_it(),
 469                           p_r->pref_e_it(),
 470                           0,
 471                           this))
 472     {
 473       node_pointer p_new_child = rec_join(
 474                                           p_l->get_join_child(p_r, this),
 475                                           p_r,
 476                                           0,
 477                                           r_bag);
 478
 479       p_l->replace_child(
 480                          p_new_child,
 481                          pref_begin(p_new_child),
 482                          pref_end(p_new_child),
 483                          this);
 484
 485       PB_DS_DBG_ONLY(p_l->assert_valid(this);)
 486
 487         return (p_l);
 488     }
 489
 490   if (p_r->get_e_ind() < p_l->get_e_ind()&&
 491       p_r->should_be_mine(
 492                           p_l->pref_b_it(),
 493                           p_l->pref_e_it(),
 494                           0,
 495                           this))
 496     {
 497       node_pointer p_new_child = rec_join(
 498                                           p_r->get_join_child(p_l, this),
 499                                           p_l,
 500                                           0,
 501                                           r_bag);
 502
 503       p_r->replace_child(
 504                          p_new_child,
 505                          pref_begin(p_new_child),
 506                          pref_end(p_new_child),
 507                          this);
 508
 509       PB_DS_DBG_ONLY(p_r->assert_valid(this);)
 510
 511         PB_DS_DBG_ASSERT(recursive_count_leafs(p_r) ==
 512                          lhs_leafs + rhs_leafs);
 513
 514       return (p_r);
 515     }
 516
 517   node_pointer p_ret = insert_branch(p_l, p_r, r_bag);
 518
 519   PB_DS_DBG_ONLY(p_ret->assert_valid(this);)
 520
 521     PB_DS_DBG_ASSERT(recursive_count_leafs(p_ret) ==
 522                      lhs_leafs + rhs_leafs);
 523
 524   return (p_ret);
 525 }
 526
 527 PB_DS_CLASS_T_DEC
 528 inline std::pair<
 529   typename PB_DS_CLASS_C_DEC::iterator,
 530   bool>
 531 PB_DS_CLASS_C_DEC::
 532 insert(const_reference r_val)
 533 {
 534   node_pointer p_lf = find_imp(PB_DS_V2F(r_val));
 535
 536   if (p_lf != NULL&&  p_lf->m_type == pat_trie_leaf_node_type&&
 537       synth_e_access_traits::equal_keys(
 538                                         PB_DS_V2F(static_cast<leaf_pointer>(p_lf)->value()),
 539                                         PB_DS_V2F(r_val)))
 540     {
 541       PB_DS_DBG_ONLY(map_debug_base::check_key_exists(
 542                                                       PB_DS_V2F(r_val)));
 543
 544       PB_DS_DBG_ONLY(assert_valid();)
 545
 546         return (std::make_pair(
 547                                iterator(p_lf),
 548                                false));
 549     }
 550
 551   PB_DS_DBG_ONLY(map_debug_base::check_key_does_not_exist(
 552                                                           PB_DS_V2F(r_val)));
 553
 554   leaf_pointer p_new_lf = s_leaf_allocator.allocate(1);
 555
 556   cond_dealtor cond(p_new_lf);
 557
 558   new (p_new_lf) leaf(r_val);
 559
 560   apply_update(p_new_lf, (node_update* )this);
 561
 562   cond.set_call_destructor();
 563
 564   split_join_branch_bag bag;
 565
 566   bag.add_branch();
 567
 568   m_p_head->m_p_parent =
 569     rec_join(m_p_head->m_p_parent, p_new_lf, 0, bag);
 570
 571   m_p_head->m_p_parent->m_p_parent = m_p_head;
 572
 573   cond.set_no_action_dtor();
 574
 575   ++m_size;
 576
 577   update_min_max_for_inserted_leaf(p_new_lf);
 578
 579   PB_DS_DBG_ONLY(map_debug_base::insert_new(
 580                                             PB_DS_V2F(r_val));)
 581
 582     PB_DS_DBG_ONLY(assert_valid();)
 583
 584     return (std::make_pair(
 585                            point_iterator(p_new_lf),
 586                            true));
 587 }
 588
 589 PB_DS_CLASS_T_DEC
 590 typename PB_DS_CLASS_C_DEC::size_type
 591 PB_DS_CLASS_C_DEC::
 592 keys_diff_ind(typename e_access_traits::const_iterator b_l, typename e_access_traits::const_iterator e_l, typename e_access_traits::const_iterator b_r, typename e_access_traits::const_iterator e_r)
 593 {
 594   size_type diff_pos = 0;
 595
 596   while (b_l != e_l)
 597     {
 598       if (b_r == e_r)
 599         return (diff_pos);
 600
 601       if (e_access_traits::e_pos(*b_l) != e_access_traits::e_pos(*b_r))
 602         return (diff_pos);
 603
 604       ++b_l;
 605       ++b_r;
 606
 607       ++diff_pos;
 608     }
 609
 610   PB_DS_DBG_ASSERT(b_r != e_r);
 611
 612   return (diff_pos);
 613 }
 614
 615 PB_DS_CLASS_T_DEC
 616 typename PB_DS_CLASS_C_DEC::internal_node_pointer
 617 PB_DS_CLASS_C_DEC::
 618 insert_branch(node_pointer p_l, node_pointer p_r, split_join_branch_bag& r_bag)
 619 {
 620   typename synth_e_access_traits::const_iterator left_b_it =
 621     pref_begin(p_l);
 622   typename synth_e_access_traits::const_iterator left_e_it =
 623     pref_end(p_l);
 624
 625   typename synth_e_access_traits::const_iterator right_b_it =
 626     pref_begin(p_r);
 627   typename synth_e_access_traits::const_iterator right_e_it =
 628     pref_end(p_r);
 629
 630   const size_type diff_ind =
 631     keys_diff_ind(left_b_it, left_e_it, right_b_it, right_e_it);
 632
 633   internal_node_pointer p_new_nd = r_bag.get_branch();
 634
 635   new (p_new_nd) internal_node(diff_ind, left_b_it);
 636
 637   p_new_nd->add_child(        p_l, left_b_it, left_e_it, this);
 638
 639   p_new_nd->add_child(        p_r, right_b_it, right_e_it, this);
 640
 641   p_l->m_p_parent = p_new_nd;
 642   p_r->m_p_parent = p_new_nd;
 643
 644   PB_DS_DBG_ONLY(p_new_nd->assert_valid(this);)
 645
 646     return (p_new_nd);
 647 }
 648
 649 PB_DS_CLASS_T_DEC
 650 void
 651 PB_DS_CLASS_C_DEC::
 652 update_min_max_for_inserted_leaf(leaf_pointer p_new_lf)
 653 {
 654   if (m_p_head->m_p_min == m_p_head ||
 655       synth_e_access_traits::cmp_keys(
 656                                       PB_DS_V2F(p_new_lf->value()),
 657                                       PB_DS_V2F(static_cast<const_leaf_pointer>(m_p_head->m_p_min)->value())))
 658     m_p_head->m_p_min = p_new_lf;
 659
 660   if (m_p_head->m_p_max == m_p_head ||
 661       synth_e_access_traits::cmp_keys(
 662                                       PB_DS_V2F(static_cast<const_leaf_pointer>(m_p_head->m_p_max)->value()),
 663                                       PB_DS_V2F(p_new_lf->value())))
 664     m_p_head->m_p_max = p_new_lf;
 665 }