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 62namespace 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 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 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 246 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 321 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