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