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