libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.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 ov_tree_map_.hpp
  44  * Contains an implementation class for ov_tree_.
  45  */
  46
  47 #include <map>
  48 #include <set>
  49 #include <ext/pb_ds/tree_policy.hpp>
  50 #include <ext/pb_ds/detail/eq_fn/eq_by_less.hpp>
  51 #include <ext/pb_ds/detail/types_traits.hpp>
  52 #include <ext/pb_ds/detail/map_debug_base.hpp>
  53 #include <ext/pb_ds/detail/type_utils.hpp>
  54 #include <ext/pb_ds/exception.hpp>
  55 #include <ext/pb_ds/detail/tree_trace_base.hpp>
  56 #include <utility>
  57 #include <functional>
  58 #include <algorithm>
  59 #include <vector>
  60 #include <assert.h>
  61
  62 namespace pb_ds
  63 {
  64   namespace detail
  65   {
  66
  67 #ifdef PB_DS_OV_TREE_DEBUG_
  68 #define PB_DS_DBG_ASSERT(X) assert(X);
  69 #define PB_DS_DBG_VERIFY(X) PB_DS_DBG_ASSERT(X)
  70 #define PB_DS_DBG_ONLY(X) X
  71 #else // #ifdef PB_DS_OV_TREE_DEBUG_
  72 #define PB_DS_DBG_ASSERT(X) ((void)0)
  73 #define PB_DS_DBG_VERIFY(X) X
  74 #define PB_DS_DBG_ONLY(X) ;
  75 #endif // #ifdef PB_DS_OV_TREE_DEBUG_
  76
  77 #define PB_DS_CLASS_T_DEC                                               \
  78     template<                                                           \
  79                                                 typename Key,           \
  80                                                 typename Mapped,        \
  81                                                 class Cmp_Fn,           \
  82                                                 class Node_And_It_Traits, \
  83                                                 class Allocator>
  84
  85 #ifdef PB_DS_DATA_TRUE_INDICATOR
  86 #define PB_DS_OV_TREE_CLASS_NAME                \
  87     ov_tree_data_
  88 #endif // #ifdef PB_DS_DATA_TRUE_INDICATOR
  89
  90 #ifdef PB_DS_DATA_FALSE_INDICATOR
  91 #define PB_DS_OV_TREE_CLASS_NAME                \
  92     ov_tree_no_data_
  93 #endif // #ifdef PB_DS_DATA_FALSE_INDICATOR
  94
  95 #ifdef PB_DS_DATA_TRUE_INDICATOR
  96 #define PB_DS_CONST_NODE_ITERATOR_NAME ov_tree_const_node_iterator_data_
  97 #else // #ifdef PB_DS_DATA_TRUE_INDICATOR
  98 #define PB_DS_CONST_NODE_ITERATOR_NAME ov_tree_const_node_iterator_no_data_
  99 #endif // #ifdef PB_DS_DATA_TRUE_INDICATOR
 100
 101 #define PB_DS_CLASS_C_DEC                                               \
 102     PB_DS_OV_TREE_CLASS_NAME<                                           \
 103                                                         Key,            \
 104                                                         Mapped,         \
 105                                                         Cmp_Fn,         \
 106                                                         Node_And_It_Traits, \
 107                                                         Allocator>
 108
 109 #define PB_DS_TYPES_TRAITS_C_DEC                                \
 110     types_traits<                                               \
 111                                                 Key,            \
 112                                                 Mapped,         \
 113                                                 Allocator,      \
 114                                                 false>
 115
 116 #ifdef PB_DS_USE_MAP_DEBUG_BASE
 117 #define PB_DS_MAP_DEBUG_BASE_C_DEC                                      \
 118     map_debug_base<                                     \
 119                                                                         Key, \
 120                                                                         eq_by_less<Key, Cmp_Fn>, \
 121                                                                         typename Allocator::template rebind< \
 122                                                                                                              Key>::other::const_reference>
 123 #endif // #ifdef PB_DS_USE_MAP_DEBUG_BASE
 124
 125 #ifdef PB_DS_DATA_TRUE_INDICATOR
 126 #define PB_DS_V2F(X) (X).first
 127 #define PB_DS_V2S(X) (X).second
 128 #define PB_DS_EP2VP(X)& ((X)->m_value)
 129 #endif // #ifdef PB_DS_DATA_TRUE_INDICATOR
 130
 131 #ifdef PB_DS_DATA_FALSE_INDICATOR
 132 #define PB_DS_V2F(X) (X)
 133 #define PB_DS_V2S(X) Mapped_Data()
 134 #define PB_DS_EP2VP(X)& ((X)->m_value.first)
 135 #endif // #ifdef PB_DS_DATA_FALSE_INDICATOR
 136
 137 #ifdef PB_DS_TREE_TRACE
 138 #define PB_DS_TREE_TRACE_BASE_C_DEC                                     \
 139     tree_trace_base<                                                    \
 140                                                                         typename Node_And_It_Traits::const_node_iterator, \
 141                                                                         typename Node_And_It_Traits::node_iterator, \
 142                                                                         Cmp_Fn, \
 143                                                                         false, \
 144                                                                         Allocator>
 145 #endif // #ifdef PB_DS_TREE_TRACE
 146
 147     // Ordered-vector tree associative-container.
 148     template<typename Key,
 149              typename Mapped,
 150              class Cmp_Fn,
 151              class Node_And_It_Traits,
 152              class Allocator>
 153     class PB_DS_OV_TREE_CLASS_NAME :
 154 #ifdef PB_DS_OV_TREE_DEBUG_
 155       protected PB_DS_MAP_DEBUG_BASE_C_DEC,
 156 #endif // #ifdef PB_DS_OV_TREE_DEBUG_
 157 #ifdef PB_DS_TREE_TRACE
 158       public PB_DS_TREE_TRACE_BASE_C_DEC,
 159 #endif // #ifdef PB_DS_TREE_TRACE
 160       public Cmp_Fn,
 161       public Node_And_It_Traits::node_update,
 162       public PB_DS_TYPES_TRAITS_C_DEC
 163     {
 164
 165     private:
 166       typedef
 167       typename remove_const<
 168       typename PB_DS_TYPES_TRAITS_C_DEC::value_type>::type
 169       non_const_value_type;
 170
 171       typedef
 172       typename Allocator::template rebind<
 173         non_const_value_type>::other
 174       value_allocator;
 175
 176       typedef typename value_allocator::pointer value_vector;
 177
 178       typedef PB_DS_TYPES_TRAITS_C_DEC traits_base;
 179
 180       typedef Cmp_Fn cmp_fn_base;
 181
 182 #ifdef PB_DS_USE_MAP_DEBUG_BASE
 183       typedef PB_DS_MAP_DEBUG_BASE_C_DEC map_debug_base;
 184 #endif // #ifdef PB_DS_USE_MAP_DEBUG_BASE
 185
 186       typedef typename PB_DS_TYPES_TRAITS_C_DEC::pointer mapped_pointer_;
 187
 188       typedef
 189       typename PB_DS_TYPES_TRAITS_C_DEC::const_pointer
 190       const_mapped_pointer_;
 191
 192       typedef typename Node_And_It_Traits::metadata_type metadata_type;
 193
 194       typedef
 195       typename Allocator::template rebind<
 196         metadata_type>::other
 197       metadata_allocator;
 198
 199       typedef typename metadata_allocator::pointer metadata_pointer;
 200
 201       typedef
 202       typename metadata_allocator::const_reference
 203       const_metadata_reference;
 204
 205       typedef typename metadata_allocator::reference metadata_reference;
 206
 207       typedef
 208       typename Node_And_It_Traits::null_node_update_pointer
 209       null_node_update_pointer;
 210
 211     public:
 212
 213       typedef typename Allocator::size_type size_type;
 214
 215       typedef typename Allocator::difference_type difference_type;
 216
 217       typedef Cmp_Fn cmp_fn;
 218
 219       typedef typename Node_And_It_Traits::node_update node_update;
 220
 221       typedef Allocator allocator;
 222
 223       typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_type key_type;
 224
 225       typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_pointer key_pointer;
 226
 227       typedef
 228       typename PB_DS_TYPES_TRAITS_C_DEC::const_key_pointer
 229       const_key_pointer;
 230
 231       typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_reference key_reference;
 232
 233       typedef
 234       typename PB_DS_TYPES_TRAITS_C_DEC::const_key_reference
 235       const_key_reference;
 236
 237       typedef typename PB_DS_TYPES_TRAITS_C_DEC::mapped_type mapped_type;
 238
 239       typedef
 240       typename PB_DS_TYPES_TRAITS_C_DEC::mapped_pointer
 241       mapped_pointer;
 242
 243       typedef
 244       typename PB_DS_TYPES_TRAITS_C_DEC::const_mapped_pointer
 245       const_mapped_pointer;
 246
 247       typedef
 248       typename PB_DS_TYPES_TRAITS_C_DEC::mapped_reference
 249       mapped_reference;
 250
 251       typedef
 252       typename PB_DS_TYPES_TRAITS_C_DEC::const_mapped_reference
 253       const_mapped_reference;
 254
 255       typedef typename PB_DS_TYPES_TRAITS_C_DEC::value_type value_type;
 256
 257       typedef typename PB_DS_TYPES_TRAITS_C_DEC::pointer pointer;
 258
 259       typedef typename PB_DS_TYPES_TRAITS_C_DEC::const_pointer const_pointer;
 260
 261       typedef typename PB_DS_TYPES_TRAITS_C_DEC::reference reference;
 262
 263       typedef
 264       typename PB_DS_TYPES_TRAITS_C_DEC::const_reference
 265       const_reference;
 266
 267       typedef const_pointer const_point_iterator;
 268
 269 #ifdef PB_DS_DATA_TRUE_INDICATOR
 270       typedef pointer point_iterator;
 271 #else // #ifdef PB_DS_DATA_TRUE_INDICATOR
 272       typedef const_point_iterator point_iterator;
 273 #endif // #ifdef PB_DS_DATA_TRUE_INDICATOR
 274
 275       typedef const_point_iterator const_iterator;
 276
 277       typedef point_iterator iterator;
 278
 279 #include <ext/pb_ds/detail/ov_tree_map_/cond_dtor.hpp>
 280
 281       typedef
 282       typename Node_And_It_Traits::const_node_iterator
 283       const_node_iterator;
 284
 285       typedef typename Node_And_It_Traits::node_iterator node_iterator;
 286
 287     public:
 288
 289       PB_DS_OV_TREE_CLASS_NAME();
 290
 291       PB_DS_OV_TREE_CLASS_NAME(const Cmp_Fn& r_cmp_fn);
 292
 293       PB_DS_OV_TREE_CLASS_NAME(const Cmp_Fn& r_cmp_fn, const node_update& r_node_update);
 294
 295       PB_DS_OV_TREE_CLASS_NAME(const PB_DS_CLASS_C_DEC& other);
 296
 297       ~PB_DS_OV_TREE_CLASS_NAME();
 298
 299       void
 300       swap(PB_DS_CLASS_C_DEC& other);
 301
 302       template<typename It>
 303       void
 304       copy_from_range(It first_it, It last_it);
 305
 306       inline size_type
 307       max_size() const;
 308
 309       inline bool
 310       empty() const;
 311
 312       inline size_type
 313       size() const;
 314
 315       Cmp_Fn&
 316       get_cmp_fn();
 317
 318       const Cmp_Fn&
 319       get_cmp_fn() const;
 320
 321       inline mapped_reference
 322       operator[](const_key_reference r_key)
 323       {
 324 #ifdef PB_DS_DATA_TRUE_INDICATOR
 325         PB_DS_DBG_ONLY(assert_valid();)
 326
 327           point_iterator it = lower_bound(r_key);
 328
 329         if (it != end()&&  !Cmp_Fn::operator()(
 330                                                r_key,
 331                                                PB_DS_V2F(*it)))
 332           {
 333             PB_DS_DBG_ONLY(map_debug_base::check_key_exists(r_key));
 334
 335             PB_DS_DBG_ONLY(assert_valid();)
 336
 337               return (it->second);
 338           }
 339
 340         PB_DS_DBG_ONLY(assert_valid();)
 341
 342           return (insert_new_val(it,
 343                                  std::make_pair(
 344                                                 r_key,
 345                                                 mapped_type()))->second);
 346 #else // #ifdef PB_DS_DATA_TRUE_INDICATOR
 347         insert(r_key);
 348
 349         return (traits_base::s_null_mapped);
 350 #endif // #ifdef PB_DS_DATA_TRUE_INDICATOR
 351       }
 352
 353       inline std::pair<point_iterator, bool>
 354       insert(const_reference r_value)
 355       {
 356         PB_DS_DBG_ONLY(assert_valid();)
 357
 358           const_key_reference r_key = PB_DS_V2F(r_value);
 359
 360         point_iterator it = lower_bound(r_key);
 361
 362         if (it != end()&&  !Cmp_Fn::operator()(
 363                                                r_key,
 364                                                PB_DS_V2F(*it)))
 365           {
 366             PB_DS_DBG_ONLY(assert_valid();)
 367
 368               PB_DS_DBG_ONLY(map_debug_base::check_key_exists(r_key));
 369
 370             return (std::make_pair(it, false));
 371           }
 372
 373         PB_DS_DBG_ONLY(assert_valid();)
 374
 375           return (std::make_pair(insert_new_val(it, r_value), true));
 376       }
 377
 378       inline point_iterator
 379       lower_bound(const_key_reference r_key)
 380       {
 381         pointer it = m_a_values;
 382
 383         pointer e_it = m_a_values + m_size;
 384
 385         while (it != e_it)
 386           {
 387             pointer mid_it = it + ((e_it - it) >> 1);
 388
 389             if (cmp_fn_base::operator()(
 390                                         PB_DS_V2F(*mid_it),
 391                                         r_key))
 392               it = ++mid_it;
 393             else
 394               e_it = mid_it;
 395           }
 396
 397         return (it);
 398       }
 399
 400       inline const_point_iterator
 401       lower_bound(const_key_reference r_key) const
 402       {
 403         return (const_cast<PB_DS_CLASS_C_DEC& >(*this).lower_bound(r_key));
 404       }
 405
 406       inline point_iterator
 407       upper_bound(const_key_reference r_key)
 408       {
 409         iterator pot_it = lower_bound(r_key);
 410
 411         if (pot_it != end()&&  !Cmp_Fn::operator()(
 412                                                    r_key,
 413                                                    PB_DS_V2F(*pot_it)))
 414           {
 415             PB_DS_DBG_ONLY(map_debug_base::check_key_exists(r_key));
 416
 417             return (++pot_it);
 418           }
 419
 420         PB_DS_DBG_ONLY(map_debug_base::check_key_does_not_exist(r_key));
 421
 422         return (pot_it);
 423       }
 424
 425       inline const_point_iterator
 426       upper_bound(const_key_reference r_key) const
 427       {
 428         return (const_cast<PB_DS_CLASS_C_DEC& >(*this).upper_bound(r_key));
 429       }
 430
 431       inline point_iterator
 432       find(const_key_reference r_key)
 433       {
 434         PB_DS_DBG_ONLY(assert_valid();)
 435
 436           iterator pot_it = lower_bound(r_key);
 437
 438         if (pot_it != end()&&  !Cmp_Fn::operator()(
 439                                                    r_key,
 440                                                    PB_DS_V2F(*pot_it)))
 441           {
 442             PB_DS_DBG_ONLY(map_debug_base::check_key_exists(r_key));
 443
 444             return (pot_it);
 445           }
 446
 447         PB_DS_DBG_ONLY(map_debug_base::check_key_does_not_exist(r_key));
 448
 449         return (end());
 450       }
 451
 452       inline const_point_iterator
 453       find(const_key_reference r_key) const
 454       {
 455         return (const_cast<PB_DS_CLASS_C_DEC& >(*this).find(r_key));
 456       }
 457
 458       bool
 459       erase(const_key_reference r_key);
 460
 461       template<typename Pred>
 462       inline size_type
 463       erase_if(Pred pred);
 464
 465       inline iterator
 466       erase(iterator it)
 467       {
 468         return (erase_imp<iterator>(it));
 469       }
 470
 471       void
 472       clear();
 473
 474       void
 475       join(PB_DS_CLASS_C_DEC& other);
 476
 477       void
 478       split(const_key_reference r_key, PB_DS_CLASS_C_DEC& other);
 479
 480       inline iterator
 481       begin()
 482       {
 483         return (m_a_values);
 484       }
 485
 486       inline const_iterator
 487       begin() const
 488       {
 489         return (m_a_values);
 490       }
 491
 492       inline iterator
 493       end()
 494       {
 495         return (m_end_it);
 496       }
 497
 498       inline const_iterator
 499       end() const
 500       {
 501         return (m_end_it);
 502       }
 503
 504       inline const_node_iterator
 505       node_begin() const;
 506
 507       inline const_node_iterator
 508       node_end() const;
 509
 510       inline node_iterator
 511       node_begin();
 512
 513       inline node_iterator
 514       node_end();
 515
 516     private:
 517
 518       inline void
 519       update(node_iterator /*it*/, null_node_update_pointer);
 520
 521       template<typename Node_Update>
 522       void
 523       update(node_iterator it, Node_Update* p_update);
 524
 525       void
 526       reallocate_metadata(null_node_update_pointer, size_type);
 527
 528       template<typename Node_Update_>
 529       void
 530       reallocate_metadata(Node_Update_* p_update, size_type new_size);
 531
 532       template<typename It>
 533       void
 534       copy_from_ordered_range(It first_it, It last_it);
 535
 536       void
 537       value_swap(PB_DS_CLASS_C_DEC& other);
 538
 539       template<typename It>
 540       void
 541       copy_from_ordered_range(It first_it, It last_it, It other_first_it, It other_last_it);
 542
 543       template<typename Ptr>
 544       inline static Ptr
 545       mid_pointer(Ptr p_begin, Ptr p_end)
 546       {
 547         PB_DS_DBG_ASSERT(p_end >= p_begin);
 548
 549         return (p_begin + (p_end - p_begin) / 2);
 550       }
 551
 552       inline iterator
 553       insert_new_val(iterator it, const_reference r_value)
 554       {
 555         PB_DS_DBG_ONLY(assert_valid();)
 556
 557 #ifdef PB_DS_REGRESSION
 558           typename Allocator::group_throw_prob_adjustor adjust(m_size);
 559 #endif // #ifdef PB_DS_REGRESSION
 560
 561         PB_DS_DBG_ONLY(map_debug_base::check_key_does_not_exist(
 562                                                                 PB_DS_V2F(r_value)));
 563
 564         value_vector a_values = s_value_alloc.allocate(m_size + 1);
 565
 566         iterator source_it = begin();
 567         iterator source_end_it = end();
 568         iterator target_it = a_values;
 569         iterator ret_it;
 570
 571         cond_dtor<size_type> cd(a_values, target_it, m_size + 1);
 572
 573         while (source_it != it)
 574           {
 575             new (const_cast<void* >(
 576                                     static_cast<const void* >(target_it)))
 577               value_type(*source_it++);
 578
 579             ++target_it;
 580           }
 581
 582         new (const_cast<void* >(
 583                                 static_cast<const void* >(ret_it = target_it)))
 584           value_type(r_value);
 585
 586         ++target_it;
 587
 588         while (source_it != source_end_it)
 589           {
 590             new (const_cast<void* >(
 591                                     static_cast<const void* >(target_it)))
 592               value_type(*source_it++);
 593
 594             ++target_it;
 595           }
 596
 597         reallocate_metadata((node_update* )this, m_size + 1);
 598
 599         cd.set_no_action();
 600
 601         if (m_size != 0)
 602           {
 603             cond_dtor<size_type> cd1(m_a_values, m_end_it, m_size);
 604           }
 605
 606         ++m_size;
 607
 608         m_a_values = a_values;
 609
 610         m_end_it = m_a_values + m_size;
 611
 612         PB_DS_DBG_ONLY(map_debug_base::insert_new(
 613                                                   PB_DS_V2F(r_value)));
 614
 615         update(node_begin(), (node_update* )this);
 616
 617         PB_DS_DBG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();)
 618
 619           return (ret_it);
 620       }
 621
 622 #ifdef PB_DS_OV_TREE_DEBUG_
 623
 624       void
 625       assert_valid() const;
 626
 627       void
 628       assert_iterators() const;
 629
 630 #endif // #ifdef PB_DS_OV_TREE_DEBUG_
 631
 632       template<typename It>
 633       It
 634       erase_imp(It it);
 635
 636       inline const_node_iterator
 637       PB_DS_node_begin_imp() const;
 638
 639       inline const_node_iterator
 640       PB_DS_node_end_imp() const;
 641
 642       inline node_iterator
 643       PB_DS_node_begin_imp();
 644
 645       inline node_iterator
 646       PB_DS_node_end_imp();
 647
 648     private:
 649       value_vector m_a_values;
 650
 651       static value_allocator s_value_alloc;
 652
 653       metadata_pointer m_a_metadata;
 654
 655       static metadata_allocator s_metadata_alloc;
 656
 657       iterator m_end_it;
 658
 659       size_type m_size;
 660     };
 661
 662 #include <ext/pb_ds/detail/ov_tree_map_/constructors_destructor_fn_imps.hpp>
 663 #include <ext/pb_ds/detail/ov_tree_map_/iterators_fn_imps.hpp>
 664 #include <ext/pb_ds/detail/ov_tree_map_/debug_fn_imps.hpp>
 665 #include <ext/pb_ds/detail/ov_tree_map_/erase_fn_imps.hpp>
 666 #include <ext/pb_ds/detail/ov_tree_map_/insert_fn_imps.hpp>
 667 #include <ext/pb_ds/detail/ov_tree_map_/info_fn_imps.hpp>
 668 #include <ext/pb_ds/detail/ov_tree_map_/split_join_fn_imps.hpp>
 669 #include <ext/pb_ds/detail/bin_search_tree_/policy_access_fn_imps.hpp>
 670
 671 #undef PB_DS_CLASS_C_DEC
 672
 673 #undef PB_DS_CLASS_T_DEC
 674
 675 #undef PB_DS_OV_TREE_CLASS_NAME
 676
 677 #undef PB_DS_TYPES_TRAITS_C_DEC
 678
 679 #undef PB_DS_MAP_DEBUG_BASE_C_DEC
 680
 681 #ifdef PB_DS_TREE_TRACE
 682 #undef PB_DS_TREE_TRACE_BASE_C_DEC
 683 #endif // #ifdef PB_DS_TREE_TRACE
 684
 685 #undef PB_DS_V2F
 686 #undef PB_DS_EP2VP
 687 #undef PB_DS_V2S
 688
 689 #undef PB_DS_DBG_ASSERT
 690 #undef PB_DS_DBG_VERIFY
 691 #undef PB_DS_DBG_ONLY
 692
 693 #undef PB_DS_CONST_NODE_ITERATOR_NAME
 694
 695   } // namespace detail
 696 } // namespace pb_ds