contrib/gcc-4.1/libstdc++-v3/include/ext/pb_assoc/detail/rb_tree_map_/rb_tree_.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005 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
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 2, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // You should have received a copy of the GNU General Public License along
  17 // with this library; see the file COPYING.  If not, write to the Free
  18 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  19 // USA.
  20
  21 // As a special exception, you may use this file as part of a free software
  22 // library without restriction.  Specifically, if other files instantiate
  23 // templates or use macros or inline functions from this file, or you compile
  24 // this file and link it with other files to produce an executable, this
  25 // file does not by itself cause the resulting executable to be covered by
  26 // the GNU General Public License.  This exception does not however
  27 // invalidate any other reasons why the executable file might be covered by
  28 // the GNU General Public License.
  29
  30 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  31
  32 // Permission to use, copy, modify, sell, and distribute this software
  33 // is hereby granted without fee, provided that the above copyright
  34 // notice appears in all copies, and that both that copyright notice and
  35 // this permission notice appear in supporting documentation. None of
  36 // the above authors, nor IBM Haifa Research Laboratories, make any
  37 // representation about the suitability of this software for any
  38 // purpose. It is provided "as is" without express or implied warranty.
  39
  40 /**
  41  * @file rb_tree_.hpp
  42  * Contains an implementation for rb_tree_.
  43  */
  44
  45 /*
  46  * This implementation uses an idea from the SGI STL (using a "header" node
  47  *      which is needed for efficient iteration).
  48  */
  49
  50 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
  51 #ifndef BIN_SEARCH_TREE_HPP__DATA_TRUE_INDICATOR
  52 #define BIN_SEARCH_TREE_HPP__DATA_TRUE_INDICATOR
  53 #include <ext/pb_assoc/detail/bin_search_tree_/bin_search_tree_.hpp>
  54 #endif // #ifndef BIN_SEARCH_TREE_HPP__DATA_TRUE_INDICATOR
  55 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
  56
  57 #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
  58 #ifndef BIN_SEARCH_TREE_HPP__DATA_FALSE_INDICATOR
  59 #define BIN_SEARCH_TREE_HPP__DATA_FALSE_INDICATOR
  60 #include <ext/pb_assoc/detail/bin_search_tree_/bin_search_tree_.hpp>
  61 #endif // #ifndef BIN_SEARCH_TREE_HPP__DATA_FALSE_INDICATOR
  62 #endif // #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
  63
  64 #include <ext/pb_assoc/tree_policy.hpp>
  65 #include <ext/pb_assoc/detail/standard_policies.hpp>
  66 #include <ext/pb_assoc/detail/rb_tree_map_/node.hpp>
  67 #include <utility>
  68 #include <vector>
  69 #include <assert.h>
  70
  71 namespace pb_assoc
  72 {
  73
  74   namespace detail
  75   {
  76
  77 #ifdef PB_ASSOC_RB_TREE_DEBUG_
  78 #define PB_ASSOC_DBG_ASSERT(X) assert(X)
  79 #define PB_ASSOC_DBG_VERIFY(X) assert(X)
  80 #define PB_ASSOC_DBG_ONLY(X) X
  81 #else // #ifdef PB_ASSOC_RB_TREE_DEBUG_
  82 #define PB_ASSOC_DBG_ASSERT(X)
  83 #define PB_ASSOC_DBG_VERIFY(X) {if((X)==0);}
  84 #define PB_ASSOC_DBG_ONLY(X) ;
  85 #endif // #ifdef PB_ASSOC_RB_TREE_DEBUG_
  86
  87 #define PB_ASSOC_CLASS_T_DEC \
  88         template< \
  89                 typename Key, \
  90                 typename Data, \
  91                 class Cmp_Fn, \
  92                 class Allocator, \
  93                 class Node_Updator>
  94
  95 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
  96 #define PB_ASSOC_CLASS_NAME \
  97         rb_tree_data_
  98 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
  99
 100 #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
 101 #define PB_ASSOC_CLASS_NAME \
 102         rb_tree_no_data_
 103 #endif // #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
 104
 105 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
 106 #define PB_ASSOC_BASE_CLASS_NAME \
 107         bin_search_tree_data_
 108 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
 109
 110 #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
 111 #define PB_ASSOC_BASE_CLASS_NAME \
 112         bin_search_tree_no_data_
 113 #endif // #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
 114
 115 #define PB_ASSOC_CLASS_C_DEC \
 116         PB_ASSOC_CLASS_NAME< \
 117                 Key, \
 118                 Data, \
 119                 Cmp_Fn, \
 120                 Allocator, \
 121                 Node_Updator>
 122
 123 #define PB_ASSOC_TYPES_TRAITS_C_DEC \
 124         types_traits< \
 125                 Key, \
 126                 Data, \
 127                 Allocator>
 128
 129 #define PB_ASSOC_NODE_C_DEC \
 130         rb_tree_node_< \
 131                 typename PB_ASSOC_TYPES_TRAITS_C_DEC::value_type, \
 132                 Allocator>
 133
 134 #define PB_ASSOC_BASE_C_DEC \
 135         PB_ASSOC_BASE_CLASS_NAME< \
 136                 Key, \
 137                 Data, \
 138                 PB_ASSOC_NODE_C_DEC, \
 139                 Cmp_Fn, \
 140                 Allocator, \
 141                 Node_Updator>
 142
 143 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
 144 #define PB_ASSOC_V2F(X) (X).first
 145 #define PB_ASSOC_V2S(X) (X).second
 146 #define PB_ASSOC_EP2VP(X)& ((X)->m_value)
 147 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
 148
 149 #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
 150 #define PB_ASSOC_V2F(X) (X)
 151 #define PB_ASSOC_V2S(X) Mapped_Data()
 152 #define PB_ASSOC_EP2VP(X)& ((X)->m_value.first)
 153 #endif // #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
 154
 155     template<typename Key,
 156              typename Data,
 157              class Cmp_Fn,
 158              class Allocator,
 159              class Node_Updator>
 160     struct PB_ASSOC_CLASS_NAME : public PB_ASSOC_BASE_C_DEC
 161     {
 162
 163     public:
 164
 165       typedef typename Allocator::size_type size_type;
 166
 167       typedef
 168       typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_key_reference
 169       const_key_reference;
 170
 171       typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::data_type data_type;
 172
 173       typedef
 174       typename PB_ASSOC_TYPES_TRAITS_C_DEC::data_reference
 175       data_reference;
 176
 177       typedef
 178       typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_data_reference
 179       const_data_reference;
 180
 181       typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::value_type value_type;
 182
 183       typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::pointer pointer;
 184
 185       typedef
 186       typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_pointer
 187       const_pointer;
 188
 189       typedef typename PB_ASSOC_TYPES_TRAITS_C_DEC::reference reference;
 190
 191       typedef
 192       typename PB_ASSOC_TYPES_TRAITS_C_DEC::const_reference
 193       const_reference;
 194
 195       typedef typename PB_ASSOC_BASE_C_DEC::find_iterator find_iterator;
 196
 197       typedef
 198       typename PB_ASSOC_BASE_C_DEC::const_iterator
 199       const_find_iterator;
 200
 201       typedef typename PB_ASSOC_BASE_C_DEC::iterator iterator;
 202
 203       typedef typename PB_ASSOC_BASE_C_DEC::const_iterator const_iterator;
 204
 205       typedef
 206       typename PB_ASSOC_BASE_C_DEC::reverse_iterator
 207       reverse_iterator;
 208
 209       typedef
 210       typename PB_ASSOC_BASE_C_DEC::const_reverse_iterator
 211       const_reverse_iterator;
 212
 213     private:
 214
 215       typedef typename PB_ASSOC_BASE_C_DEC::node_pointer node_pointer;
 216
 217     protected:
 218
 219       PB_ASSOC_CLASS_NAME();
 220
 221       PB_ASSOC_CLASS_NAME(const Cmp_Fn& r_cmp_fn);
 222
 223       PB_ASSOC_CLASS_NAME(const Cmp_Fn& r_cmp_fn, const Node_Updator& r_node_updator);
 224
 225       PB_ASSOC_CLASS_NAME(const PB_ASSOC_CLASS_C_DEC& r_other);
 226
 227       void
 228       swap(PB_ASSOC_CLASS_C_DEC& r_other);
 229
 230       template<class It>
 231       void
 232       copy_from_range(It first_it, It last_it);
 233
 234       inline std::pair<find_iterator, bool>
 235       insert(const_reference r_value);
 236
 237 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
 238       inline data_reference
 239       subscript_imp(const_key_reference r_key);
 240 #endif // #ifdef PB_ASSOC_DATA_TRUE
 241
 242       inline static bool
 243       is_effectively_black(const node_pointer p_nd);
 244
 245       inline size_type
 246       erase(const_key_reference r_key);
 247
 248       inline const_iterator
 249       erase(const_iterator it);
 250
 251 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
 252       inline iterator
 253       erase(iterator it);
 254 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
 255
 256       inline const_reverse_iterator
 257       erase(const_reverse_iterator it);
 258
 259 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
 260       inline reverse_iterator
 261       erase(reverse_iterator it);
 262 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
 263
 264       template<class Pred>
 265       inline size_type
 266       erase_if(Pred pred);
 267
 268       void
 269       join(PB_ASSOC_CLASS_C_DEC& r_other);
 270
 271       void
 272       split(const_key_reference r_key, PB_ASSOC_CLASS_C_DEC& r_other);
 273
 274 #ifdef PB_ASSOC_RB_TREE_DEBUG_
 275
 276       virtual void
 277       assert_valid() const;
 278
 279       size_type
 280       assert_node_consistent(const node_pointer p_nd) const;
 281
 282 #endif // #ifdef PB_ASSOC_RB_TREE_DEBUG_
 283
 284     private:
 285
 286       void
 287       initialize();
 288
 289       void
 290       insert_fixup(node_pointer p_nd);
 291
 292       void
 293       erase_node(node_pointer p_nd);
 294
 295       void
 296       remove_node(node_pointer p_nd);
 297
 298       void
 299       remove_fixup(node_pointer p_x, node_pointer p_new_x_parent);
 300
 301       void
 302       split_imp(node_pointer p_nd, PB_ASSOC_CLASS_C_DEC& r_other);
 303
 304       inline node_pointer
 305       split_min();
 306
 307       std::pair<node_pointer, node_pointer>
 308       split_min_imp();
 309
 310       void
 311       join_imp(node_pointer p_x, node_pointer p_r);
 312
 313       std::pair<node_pointer, node_pointer>
 314       find_join_pos_right(node_pointer p_l, size_type h_l, size_type h_r);
 315
 316       std::pair<node_pointer, node_pointer>
 317       find_join_pos_left(node_pointer p_r, size_type h_l, size_type h_r);
 318
 319       inline size_type
 320       black_height(node_pointer p_nd);
 321
 322       void
 323       split_at_node(node_pointer p_nd, PB_ASSOC_CLASS_C_DEC& r_other);
 324
 325     };
 326
 327 #include <ext/pb_assoc/detail/rb_tree_map_/constructors_destructor_fn_imps.hpp>
 328 #include <ext/pb_assoc/detail/rb_tree_map_/insert_fn_imps.hpp>
 329 #include <ext/pb_assoc/detail/rb_tree_map_/erase_fn_imps.hpp>
 330 #include <ext/pb_assoc/detail/rb_tree_map_/find_fn_imps.hpp>
 331 #include <ext/pb_assoc/detail/rb_tree_map_/debug_fn_imps.hpp>
 332 #include <ext/pb_assoc/detail/rb_tree_map_/split_join_fn_imps.hpp>
 333 #include <ext/pb_assoc/detail/rb_tree_map_/info_fn_imps.hpp>
 334
 335 #undef PB_ASSOC_CLASS_T_DEC
 336
 337 #undef PB_ASSOC_CLASS_C_DEC
 338
 339 #undef PB_ASSOC_CLASS_NAME
 340
 341 #undef PB_ASSOC_TYPES_TRAITS_C_DEC
 342
 343 #undef PB_ASSOC_BASE_CLASS_NAME
 344
 345 #undef PB_ASSOC_NODE_C_DEC
 346
 347 #undef PB_ASSOC_BASE_C_DEC
 348
 349 #undef PB_ASSOC_DBG_ASSERT
 350 #undef PB_ASSOC_DBG_VERIFY
 351 #undef PB_ASSOC_DBG_ONLY
 352
 353 #undef PB_ASSOC_V2F
 354 #undef PB_ASSOC_EP2VP
 355 #undef PB_ASSOC_V2S
 356
 357   } // namespace detail
 358
 359 } // namespace pb_assoc
 360