1// -*- C++ -*- 2 3// Copyright (C) 2005-2013 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 list_update_map_/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#ifdef PB_DS_DATA_TRUE_INDICATOR 61#define PB_DS_LU_NAME lu_map 62#endif 63 64#ifdef PB_DS_DATA_FALSE_INDICATOR 65#define PB_DS_LU_NAME lu_set 66#endif 67 68#define PB_DS_CLASS_T_DEC \ 69 template<typename Key, typename Mapped, typename Eq_Fn, \ 70 typename _Alloc, typename Update_Policy> 71 72#define PB_DS_CLASS_C_DEC \ 73 PB_DS_LU_NAME<Key, Mapped, Eq_Fn, _Alloc, Update_Policy> 74 75#define PB_DS_LU_TRAITS_BASE \ 76 types_traits<Key, Mapped, _Alloc, false> 77 78#ifdef _GLIBCXX_DEBUG 79#define PB_DS_DEBUG_MAP_BASE_C_DEC \ 80 debug_map_base<Key, Eq_Fn, \ 81 typename _Alloc::template rebind<Key>::other::const_reference> 82#endif 83 84 /// list-based (with updates) associative container. 85 /// Skip to the lu, my darling. 86 template<typename Key, 87 typename Mapped, 88 typename Eq_Fn, 89 typename _Alloc, 90 typename Update_Policy> 91 class PB_DS_LU_NAME : 92#ifdef _GLIBCXX_DEBUG 93 protected PB_DS_DEBUG_MAP_BASE_C_DEC, 94#endif 95 public PB_DS_LU_TRAITS_BASE 96 { 97 private: 98 typedef PB_DS_LU_TRAITS_BASE traits_base; 99 100 struct entry 101 : public lu_map_entry_metadata_base<typename Update_Policy::metadata_type> 102 { 103 typename traits_base::value_type m_value; 104 typename _Alloc::template rebind<entry>::other::pointer m_p_next; 105 }; 106 107 typedef typename _Alloc::template rebind<entry>::other entry_allocator; 108 typedef typename entry_allocator::pointer entry_pointer; 109 typedef typename entry_allocator::const_pointer const_entry_pointer; 110 typedef typename entry_allocator::reference entry_reference; 111 typedef typename entry_allocator::const_reference const_entry_reference; 112 113 typedef typename _Alloc::template rebind<entry_pointer>::other entry_pointer_allocator; 114 typedef typename entry_pointer_allocator::pointer entry_pointer_array; 115 116 typedef typename traits_base::value_type value_type_; 117 typedef typename traits_base::pointer pointer_; 118 typedef typename traits_base::const_pointer const_pointer_; 119 typedef typename traits_base::reference reference_; 120 typedef typename traits_base::const_reference const_reference_; 121 122#define PB_DS_GEN_POS entry_pointer 123 124#include <ext/pb_ds/detail/unordered_iterator/point_const_iterator.hpp> 125#include <ext/pb_ds/detail/unordered_iterator/point_iterator.hpp> 126#include <ext/pb_ds/detail/unordered_iterator/const_iterator.hpp> 127#include <ext/pb_ds/detail/unordered_iterator/iterator.hpp> 128 129#undef PB_DS_GEN_POS 130 131 132#ifdef _GLIBCXX_DEBUG 133 typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base; 134#endif 135 136 typedef cond_dealtor<entry, _Alloc> cond_dealtor_t; 137 138 public: 139 typedef _Alloc allocator_type; 140 typedef typename _Alloc::size_type size_type; 141 typedef typename _Alloc::difference_type difference_type; 142 typedef Eq_Fn eq_fn; 143 typedef Update_Policy update_policy; 144 typedef typename Update_Policy::metadata_type update_metadata; 145 typedef typename traits_base::key_type key_type; 146 typedef typename traits_base::key_pointer key_pointer; 147 typedef typename traits_base::key_const_pointer key_const_pointer; 148 typedef typename traits_base::key_reference key_reference; 149 typedef typename traits_base::key_const_reference key_const_reference; 150 typedef typename traits_base::mapped_type mapped_type; 151 typedef typename traits_base::mapped_pointer mapped_pointer; 152 typedef typename traits_base::mapped_const_pointer mapped_const_pointer; 153 typedef typename traits_base::mapped_reference mapped_reference; 154 typedef typename traits_base::mapped_const_reference mapped_const_reference; 155 typedef typename traits_base::value_type value_type; 156 typedef typename traits_base::pointer pointer; 157 typedef typename traits_base::const_pointer const_pointer; 158 typedef typename traits_base::reference reference; 159 typedef typename traits_base::const_reference const_reference; 160 161#ifdef PB_DS_DATA_TRUE_INDICATOR 162 typedef point_iterator_ point_iterator; 163#endif 164 165#ifdef PB_DS_DATA_FALSE_INDICATOR 166 typedef point_const_iterator_ point_iterator; 167#endif 168 169 typedef point_const_iterator_ point_const_iterator; 170 171#ifdef PB_DS_DATA_TRUE_INDICATOR 172 typedef iterator_ iterator; 173#endif 174 175#ifdef PB_DS_DATA_FALSE_INDICATOR 176 typedef const_iterator_ iterator; 177#endif 178 179 typedef const_iterator_ const_iterator; 180 181 public: 182 PB_DS_LU_NAME(); 183 184 PB_DS_LU_NAME(const PB_DS_CLASS_C_DEC&); 185 186 virtual 187 ~PB_DS_LU_NAME(); 188 189 template<typename It> 190 PB_DS_LU_NAME(It, It); 191 192 void 193 swap(PB_DS_CLASS_C_DEC&); 194 195 inline size_type 196 size() const; 197 198 inline size_type 199 max_size() const; 200 201 inline bool 202 empty() const; 203 204 inline mapped_reference 205 operator[](key_const_reference r_key) 206 { 207#ifdef PB_DS_DATA_TRUE_INDICATOR 208 _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);) 209 return insert(std::make_pair(r_key, mapped_type())).first->second; 210#else 211 insert(r_key); 212 return traits_base::s_null_type; 213#endif 214 } 215 216 inline std::pair<point_iterator, bool> 217 insert(const_reference); 218 219 inline point_iterator 220 find(key_const_reference r_key) 221 { 222 _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);) 223 entry_pointer p_e = find_imp(r_key); 224 return point_iterator(p_e == 0 ? 0: &p_e->m_value); 225 } 226 227 inline point_const_iterator 228 find(key_const_reference r_key) const 229 { 230 _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);) 231 entry_pointer p_e = find_imp(r_key); 232 return point_const_iterator(p_e == 0 ? 0: &p_e->m_value); 233 } 234 235 inline bool 236 erase(key_const_reference); 237 238 template<typename Pred> 239 inline size_type 240 erase_if(Pred); 241 242 void 243 clear(); 244 245 inline iterator 246 begin(); 247 248 inline const_iterator 249 begin() const; 250 251 inline iterator 252 end(); 253 254 inline const_iterator 255 end() const; 256 257#ifdef _GLIBCXX_DEBUG 258 void 259 assert_valid(const char* file, int line) const; 260#endif 261 262#ifdef PB_DS_LU_MAP_TRACE_ 263 void 264 trace() const; 265#endif 266 267 protected: 268 269 template<typename It> 270 void 271 copy_from_range(It, It); 272 273 private: 274#ifdef PB_DS_DATA_TRUE_INDICATOR 275 friend class iterator_; 276#endif 277 278 friend class const_iterator_; 279 280 inline entry_pointer 281 allocate_new_entry(const_reference, false_type); 282 283 inline entry_pointer 284 allocate_new_entry(const_reference, true_type); 285 286 template<typename Metadata> 287 inline static void 288 init_entry_metadata(entry_pointer, type_to_type<Metadata>); 289 290 inline static void 291 init_entry_metadata(entry_pointer, type_to_type<null_type>); 292 293 void 294 deallocate_all(); 295 296 void 297 erase_next(entry_pointer); 298 299 void 300 actual_erase_entry(entry_pointer); 301 302 void 303 inc_it_state(const_pointer& r_p_value, entry_pointer& r_pos) const 304 { 305 r_pos = r_pos->m_p_next; 306 r_p_value = (r_pos == 0) ? 0 : &r_pos->m_value; 307 } 308 309 template<typename Metadata> 310 inline static bool 311 apply_update(entry_pointer, type_to_type<Metadata>); 312 313 inline static bool 314 apply_update(entry_pointer, type_to_type<null_type>); 315 316 inline entry_pointer 317 find_imp(key_const_reference) const; 318 319 static entry_allocator s_entry_allocator; 320 static Eq_Fn s_eq_fn; 321 static Update_Policy s_update_policy; 322 static type_to_type<update_metadata> s_metadata_type_indicator; 323 static null_type s_null_type; 324 325 mutable entry_pointer m_p_l; 326 }; 327 328#include <ext/pb_ds/detail/list_update_map_/constructor_destructor_fn_imps.hpp> 329#include <ext/pb_ds/detail/list_update_map_/info_fn_imps.hpp> 330#include <ext/pb_ds/detail/list_update_map_/debug_fn_imps.hpp> 331#include <ext/pb_ds/detail/list_update_map_/iterators_fn_imps.hpp> 332#include <ext/pb_ds/detail/list_update_map_/erase_fn_imps.hpp> 333#include <ext/pb_ds/detail/list_update_map_/find_fn_imps.hpp> 334#include <ext/pb_ds/detail/list_update_map_/insert_fn_imps.hpp> 335#include <ext/pb_ds/detail/list_update_map_/trace_fn_imps.hpp> 336 337#undef PB_DS_CLASS_T_DEC 338#undef PB_DS_CLASS_C_DEC 339#undef PB_DS_LU_TRAITS_BASE 340#undef PB_DS_DEBUG_MAP_BASE_C_DEC 341#undef PB_DS_LU_NAME 342 } // namespace detail 343} // namespace __gnu_pbds 344