1// -*- C++ -*- 2 3// Copyright (C) 2005, 2006, 2009 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 56namespace __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 == NULL ? NULL: &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 == NULL ? NULL: &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 == NULL) ? NULL : &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