1 // -*- C++ -*- 2 3 // Copyright (C) 2005, 2006, 2009, 2010 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 3, 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 // Under Section 7 of GPL version 3, you are granted additional 17 // permissions described in the GCC Runtime Library Exception, version 18 // 3.1, as published by the Free Software Foundation. 19 20 // You should have received a copy of the GNU General Public License and 21 // a copy of the GCC Runtime Library Exception along with this program; 22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23 // <http://www.gnu.org/licenses/>. 24 25 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 26 27 // Permission to use, copy, modify, sell, and distribute this software 28 // is hereby granted without fee, provided that the above copyright 29 // notice appears in all copies, and that both that copyright notice 30 // and this permission notice appear in supporting documentation. None 31 // of the above authors, nor IBM Haifa Research Laboratories, make any 32 // representation about the suitability of this software for any 33 // purpose. It is provided "as is" without express or implied 34 // warranty. 35 36 /** 37 * @file lu_map_.hpp 38 * Contains a list update map. 39 */ 40 41 #include <utility> 42 #include <iterator> 43 #include <ext/pb_ds/detail/cond_dealtor.hpp> 44 #include <ext/pb_ds/tag_and_trait.hpp> 45 #include <ext/pb_ds/detail/types_traits.hpp> 46 #include <ext/pb_ds/detail/list_update_map_/entry_metadata_base.hpp> 47 #include <ext/pb_ds/exception.hpp> 48 #ifdef _GLIBCXX_DEBUG 49 #include <ext/pb_ds/detail/debug_map_base.hpp> 50 #endif 51 #ifdef PB_DS_LU_MAP_TRACE_ 52 #include <iostream> 53 #endif 54 #include <debug/debug.h> 55 56 namespace __gnu_pbds 57 { 58 namespace detail 59 { 60 #define PB_DS_CLASS_T_DEC \ 61 template<typename Key, typename Mapped, class Eq_Fn, \ 62 class Allocator, class Update_Policy> 63 64 #ifdef PB_DS_DATA_TRUE_INDICATOR 65 #define PB_DS_CLASS_NAME lu_map_data_ 66 #endif 67 68 #ifdef PB_DS_DATA_FALSE_INDICATOR 69 #define PB_DS_CLASS_NAME lu_map_no_data_ 70 #endif 71 72 #define PB_DS_CLASS_C_DEC \ 73 PB_DS_CLASS_NAME<Key, Mapped, Eq_Fn, Allocator, Update_Policy> 74 75 #define PB_DS_TYPES_TRAITS_C_DEC \ 76 types_traits<Key, Mapped, Allocator, false> 77 78 #ifdef _GLIBCXX_DEBUG 79 #define PB_DS_DEBUG_MAP_BASE_C_DEC \ 80 debug_map_base<Key, Eq_Fn, \ 81 typename Allocator::template rebind<Key>::other::const_reference> 82 #endif 83 84 #ifdef PB_DS_DATA_TRUE_INDICATOR 85 #define PB_DS_V2F(X) (X).first 86 #define PB_DS_V2S(X) (X).second 87 #define PB_DS_EP2VP(X)& ((X)->m_value) 88 #endif 89 90 #ifdef PB_DS_DATA_FALSE_INDICATOR 91 #define PB_DS_V2F(X) (X) 92 #define PB_DS_V2S(X) Mapped_Data() 93 #define PB_DS_EP2VP(X)& ((X)->m_value.first) 94 #endif 95 96 /* Skip to the lu, my darling. */ 97 // list-based (with updates) associative container. 98 template<typename Key, 99 typename Mapped, 100 class Eq_Fn, 101 class Allocator, 102 class Update_Policy> 103 class PB_DS_CLASS_NAME : 104 #ifdef _GLIBCXX_DEBUG 105 protected PB_DS_DEBUG_MAP_BASE_C_DEC, 106 #endif 107 public PB_DS_TYPES_TRAITS_C_DEC 108 { 109 private: 110 typedef PB_DS_TYPES_TRAITS_C_DEC traits_base; 111 112 struct entry 113 : public lu_map_entry_metadata_base<typename Update_Policy::metadata_type> 114 { 115 typename traits_base::value_type m_value; 116 typename Allocator::template rebind<entry>::other::pointer m_p_next; 117 }; 118 119 typedef typename Allocator::template rebind<entry>::other entry_allocator; 120 typedef typename entry_allocator::pointer entry_pointer; 121 typedef typename entry_allocator::const_pointer const_entry_pointer; 122 typedef typename entry_allocator::reference entry_reference; 123 typedef typename entry_allocator::const_reference const_entry_reference; 124 125 typedef typename Allocator::template rebind<entry_pointer>::other entry_pointer_allocator; 126 typedef typename entry_pointer_allocator::pointer entry_pointer_array; 127 128 typedef typename traits_base::value_type value_type_; 129 typedef typename traits_base::pointer pointer_; 130 typedef typename traits_base::const_pointer const_pointer_; 131 typedef typename traits_base::reference reference_; 132 typedef typename traits_base::const_reference const_reference_; 133 134 #define PB_DS_GEN_POS entry_pointer 135 136 #include <ext/pb_ds/detail/unordered_iterator/const_point_iterator.hpp> 137 #include <ext/pb_ds/detail/unordered_iterator/point_iterator.hpp> 138 #include <ext/pb_ds/detail/unordered_iterator/const_iterator.hpp> 139 #include <ext/pb_ds/detail/unordered_iterator/iterator.hpp> 140 141 #undef PB_DS_GEN_POS 142 143 144 #ifdef _GLIBCXX_DEBUG 145 typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base; 146 #endif 147 148 typedef cond_dealtor<entry, Allocator> cond_dealtor_t; 149 150 public: 151 typedef Allocator allocator_type; 152 typedef typename Allocator::size_type size_type; 153 typedef typename Allocator::difference_type difference_type; 154 typedef Eq_Fn eq_fn; 155 typedef Update_Policy update_policy; 156 typedef typename Update_Policy::metadata_type update_metadata; 157 typedef typename traits_base::key_type key_type; 158 typedef typename traits_base::key_pointer key_pointer; 159 typedef typename traits_base::const_key_pointer const_key_pointer; 160 typedef typename traits_base::key_reference key_reference; 161 typedef typename traits_base::const_key_reference const_key_reference; 162 typedef typename traits_base::mapped_type mapped_type; 163 typedef typename traits_base::mapped_pointer mapped_pointer; 164 typedef typename traits_base::const_mapped_pointer const_mapped_pointer; 165 typedef typename traits_base::mapped_reference mapped_reference; 166 typedef typename traits_base::const_mapped_reference const_mapped_reference; 167 typedef typename traits_base::value_type value_type; 168 typedef typename traits_base::pointer pointer; 169 typedef typename traits_base::const_pointer const_pointer; 170 typedef typename traits_base::reference reference; 171 typedef typename traits_base::const_reference const_reference; 172 173 #ifdef PB_DS_DATA_TRUE_INDICATOR 174 typedef point_iterator_ point_iterator; 175 #endif 176 177 #ifdef PB_DS_DATA_FALSE_INDICATOR 178 typedef const_point_iterator_ point_iterator; 179 #endif 180 181 typedef const_point_iterator_ const_point_iterator; 182 183 #ifdef PB_DS_DATA_TRUE_INDICATOR 184 typedef iterator_ iterator; 185 #endif 186 187 #ifdef PB_DS_DATA_FALSE_INDICATOR 188 typedef const_iterator_ iterator; 189 #endif 190 191 typedef const_iterator_ const_iterator; 192 193 public: 194 PB_DS_CLASS_NAME(); 195 196 PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC&); 197 198 virtual 199 ~PB_DS_CLASS_NAME(); 200 201 template<typename It> 202 PB_DS_CLASS_NAME(It first_it, It last_it); 203 204 void 205 swap(PB_DS_CLASS_C_DEC&); 206 207 inline size_type 208 size() const; 209 210 inline size_type 211 max_size() const; 212 213 inline bool 214 empty() const; 215 216 inline mapped_reference 217 operator[](const_key_reference r_key) 218 { 219 #ifdef PB_DS_DATA_TRUE_INDICATOR 220 _GLIBCXX_DEBUG_ONLY(assert_valid();) 221 return insert(std::make_pair(r_key, mapped_type())).first->second; 222 #else 223 insert(r_key); 224 return traits_base::s_null_mapped; 225 #endif 226 } 227 228 inline std::pair<point_iterator, bool> 229 insert(const_reference); 230 231 inline point_iterator 232 find(const_key_reference r_key) 233 { 234 _GLIBCXX_DEBUG_ONLY(assert_valid();) 235 entry_pointer p_e = find_imp(r_key); 236 return point_iterator(p_e == 0 ? 0: &p_e->m_value); 237 } 238 239 inline const_point_iterator 240 find(const_key_reference r_key) const 241 { 242 _GLIBCXX_DEBUG_ONLY(assert_valid();) 243 entry_pointer p_e = find_imp(r_key); 244 return const_point_iterator(p_e == 0 ? 0: &p_e->m_value); 245 } 246 247 inline bool 248 erase(const_key_reference); 249 250 template<typename Pred> 251 inline size_type 252 erase_if(Pred); 253 254 void 255 clear(); 256 257 inline iterator 258 begin(); 259 260 inline const_iterator 261 begin() const; 262 263 inline iterator 264 end(); 265 266 inline const_iterator 267 end() const; 268 269 #ifdef _GLIBCXX_DEBUG 270 void 271 assert_valid() const; 272 #endif 273 274 #ifdef PB_DS_LU_MAP_TRACE_ 275 void 276 trace() const; 277 #endif 278 279 protected: 280 281 template<typename It> 282 void 283 copy_from_range(It, It); 284 285 private: 286 #ifdef PB_DS_DATA_TRUE_INDICATOR 287 friend class iterator_; 288 #endif 289 290 friend class const_iterator_; 291 292 inline entry_pointer 293 allocate_new_entry(const_reference, false_type); 294 295 inline entry_pointer 296 allocate_new_entry(const_reference, true_type); 297 298 template<typename Metadata> 299 inline static void 300 init_entry_metadata(entry_pointer, type_to_type<Metadata>); 301 302 inline static void 303 init_entry_metadata(entry_pointer, type_to_type<null_lu_metadata>); 304 305 void 306 deallocate_all(); 307 308 void 309 erase_next(entry_pointer); 310 311 void 312 actual_erase_entry(entry_pointer); 313 314 void 315 inc_it_state(const_pointer& r_p_value, entry_pointer& r_pos) const 316 { 317 r_pos = r_pos->m_p_next; 318 r_p_value = (r_pos == 0) ? 0 : &r_pos->m_value; 319 } 320 321 template<typename Metadata> 322 inline static bool 323 apply_update(entry_pointer, type_to_type<Metadata>); 324 325 inline static bool 326 apply_update(entry_pointer, type_to_type<null_lu_metadata>); 327 328 inline entry_pointer 329 find_imp(const_key_reference) const; 330 331 static entry_allocator s_entry_allocator; 332 static Eq_Fn s_eq_fn; 333 static Update_Policy s_update_policy; 334 static type_to_type<update_metadata> s_metadata_type_indicator; 335 static null_lu_metadata s_null_lu_metadata; 336 337 mutable entry_pointer m_p_l; 338 }; 339 340 #include <ext/pb_ds/detail/list_update_map_/constructor_destructor_fn_imps.hpp> 341 #include <ext/pb_ds/detail/list_update_map_/info_fn_imps.hpp> 342 #include <ext/pb_ds/detail/list_update_map_/debug_fn_imps.hpp> 343 #include <ext/pb_ds/detail/list_update_map_/iterators_fn_imps.hpp> 344 #include <ext/pb_ds/detail/list_update_map_/erase_fn_imps.hpp> 345 #include <ext/pb_ds/detail/list_update_map_/find_fn_imps.hpp> 346 #include <ext/pb_ds/detail/list_update_map_/insert_fn_imps.hpp> 347 #include <ext/pb_ds/detail/list_update_map_/trace_fn_imps.hpp> 348 349 #undef PB_DS_CLASS_T_DEC 350 #undef PB_DS_CLASS_C_DEC 351 #undef PB_DS_TYPES_TRAITS_C_DEC 352 #undef PB_DS_DEBUG_MAP_BASE_C_DEC 353 #undef PB_DS_CLASS_NAME 354 #undef PB_DS_V2F 355 #undef PB_DS_EP2VP 356 #undef PB_DS_V2S 357 358 } // namespace detail 359 } // namespace __gnu_pbds 360
