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 56 namespace __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
