1169691Skan// -*- C++ -*- 2169691Skan 3169691Skan// Copyright (C) 2005, 2006 Free Software Foundation, Inc. 4169691Skan// 5169691Skan// This file is part of the GNU ISO C++ Library. This library is free 6169691Skan// software; you can redistribute it and/or modify it under the terms 7169691Skan// of the GNU General Public License as published by the Free Software 8169691Skan// Foundation; either version 2, or (at your option) any later 9169691Skan// version. 10169691Skan 11169691Skan// This library is distributed in the hope that it will be useful, but 12169691Skan// WITHOUT ANY WARRANTY; without even the implied warranty of 13169691Skan// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14169691Skan// General Public License for more details. 15169691Skan 16169691Skan// You should have received a copy of the GNU General Public License 17169691Skan// along with this library; see the file COPYING. If not, write to 18169691Skan// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 19169691Skan// MA 02111-1307, USA. 20169691Skan 21169691Skan// As a special exception, you may use this file as part of a free 22169691Skan// software library without restriction. Specifically, if other files 23169691Skan// instantiate templates or use macros or inline functions from this 24169691Skan// file, or you compile this file and link it with other files to 25169691Skan// produce an executable, this file does not by itself cause the 26169691Skan// resulting executable to be covered by the GNU General Public 27169691Skan// License. This exception does not however invalidate any other 28169691Skan// reasons why the executable file might be covered by the GNU General 29169691Skan// Public License. 30169691Skan 31169691Skan// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 32169691Skan 33169691Skan// Permission to use, copy, modify, sell, and distribute this software 34169691Skan// is hereby granted without fee, provided that the above copyright 35169691Skan// notice appears in all copies, and that both that copyright notice 36169691Skan// and this permission notice appear in supporting documentation. None 37169691Skan// of the above authors, nor IBM Haifa Research Laboratories, make any 38169691Skan// representation about the suitability of this software for any 39169691Skan// purpose. It is provided "as is" without express or implied 40169691Skan// warranty. 41169691Skan 42169691Skan/** 43169691Skan * @file lu_map_.hpp 44169691Skan * Contains a list update map. 45169691Skan */ 46169691Skan 47169691Skan#include <utility> 48169691Skan#include <iterator> 49169691Skan#include <ext/pb_ds/detail/cond_dealtor.hpp> 50169691Skan#include <ext/pb_ds/tag_and_trait.hpp> 51169691Skan#include <ext/pb_ds/detail/types_traits.hpp> 52169691Skan#include <ext/pb_ds/detail/list_update_map_/entry_metadata_base.hpp> 53169691Skan#include <ext/pb_ds/exception.hpp> 54169691Skan#ifdef _GLIBCXX_DEBUG 55169691Skan#include <ext/pb_ds/detail/map_debug_base.hpp> 56169691Skan#endif 57169691Skan#ifdef PB_DS_LU_MAP_TRACE_ 58169691Skan#include <iostream> 59169691Skan#endif 60169691Skan#include <debug/debug.h> 61169691Skan 62169691Skannamespace pb_ds 63169691Skan{ 64169691Skan namespace detail 65169691Skan { 66169691Skan#define PB_DS_CLASS_T_DEC \ 67169691Skan template<typename Key, typename Mapped, class Eq_Fn, \ 68169691Skan class Allocator, class Update_Policy> 69169691Skan 70169691Skan#ifdef PB_DS_DATA_TRUE_INDICATOR 71169691Skan#define PB_DS_CLASS_NAME lu_map_data_ 72169691Skan#endif 73169691Skan 74169691Skan#ifdef PB_DS_DATA_FALSE_INDICATOR 75169691Skan#define PB_DS_CLASS_NAME lu_map_no_data_ 76169691Skan#endif 77169691Skan 78169691Skan#define PB_DS_CLASS_C_DEC \ 79169691Skan PB_DS_CLASS_NAME<Key, Mapped, Eq_Fn, Allocator, Update_Policy> 80169691Skan 81169691Skan#define PB_DS_TYPES_TRAITS_C_DEC \ 82169691Skan types_traits<Key, Mapped, Allocator, false> 83169691Skan 84169691Skan#ifdef _GLIBCXX_DEBUG 85169691Skan#define PB_DS_MAP_DEBUG_BASE_C_DEC \ 86169691Skan map_debug_base<Key, Eq_Fn, \ 87169691Skan typename Allocator::template rebind<Key>::other::const_reference> 88169691Skan#endif 89169691Skan 90169691Skan#ifdef PB_DS_DATA_TRUE_INDICATOR 91169691Skan#define PB_DS_V2F(X) (X).first 92169691Skan#define PB_DS_V2S(X) (X).second 93169691Skan#define PB_DS_EP2VP(X)& ((X)->m_value) 94169691Skan#endif 95169691Skan 96169691Skan#ifdef PB_DS_DATA_FALSE_INDICATOR 97169691Skan#define PB_DS_V2F(X) (X) 98169691Skan#define PB_DS_V2S(X) Mapped_Data() 99169691Skan#define PB_DS_EP2VP(X)& ((X)->m_value.first) 100169691Skan#endif 101169691Skan 102169691Skan /* Skip to the lu, my darling. */ 103169691Skan // list-based (with updates) associative container. 104169691Skan template<typename Key, 105169691Skan typename Mapped, 106169691Skan class Eq_Fn, 107169691Skan class Allocator, 108169691Skan class Update_Policy> 109169691Skan class PB_DS_CLASS_NAME : 110169691Skan#ifdef _GLIBCXX_DEBUG 111169691Skan protected PB_DS_MAP_DEBUG_BASE_C_DEC, 112169691Skan#endif 113169691Skan public PB_DS_TYPES_TRAITS_C_DEC 114169691Skan { 115169691Skan private: 116169691Skan typedef PB_DS_TYPES_TRAITS_C_DEC traits_base; 117169691Skan 118169691Skan struct entry 119169691Skan : public lu_map_entry_metadata_base<typename Update_Policy::metadata_type> 120169691Skan { 121169691Skan typename traits_base::value_type m_value; 122169691Skan typename Allocator::template rebind<entry>::other::pointer m_p_next; 123169691Skan }; 124169691Skan 125169691Skan typedef typename Allocator::template rebind<entry>::other entry_allocator; 126169691Skan typedef typename entry_allocator::pointer entry_pointer; 127169691Skan typedef typename entry_allocator::const_pointer const_entry_pointer; 128169691Skan typedef typename entry_allocator::reference entry_reference; 129169691Skan typedef typename entry_allocator::const_reference const_entry_reference; 130169691Skan 131169691Skan typedef typename Allocator::template rebind<entry_pointer>::other entry_pointer_allocator; 132169691Skan typedef typename entry_pointer_allocator::pointer entry_pointer_array; 133169691Skan 134169691Skan typedef typename traits_base::value_type value_type_; 135169691Skan typedef typename traits_base::pointer pointer_; 136169691Skan typedef typename traits_base::const_pointer const_pointer_; 137169691Skan typedef typename traits_base::reference reference_; 138169691Skan typedef typename traits_base::const_reference const_reference_; 139169691Skan 140169691Skan#define PB_DS_GEN_POS entry_pointer 141169691Skan 142169691Skan#include <ext/pb_ds/detail/unordered_iterator/const_point_iterator.hpp> 143169691Skan#include <ext/pb_ds/detail/unordered_iterator/point_iterator.hpp> 144169691Skan#include <ext/pb_ds/detail/unordered_iterator/const_iterator.hpp> 145169691Skan#include <ext/pb_ds/detail/unordered_iterator/iterator.hpp> 146169691Skan 147169691Skan#undef PB_DS_GEN_POS 148169691Skan 149169691Skan 150169691Skan#ifdef _GLIBCXX_DEBUG 151169691Skan typedef PB_DS_MAP_DEBUG_BASE_C_DEC map_debug_base; 152169691Skan#endif 153169691Skan 154169691Skan typedef cond_dealtor<entry, Allocator> cond_dealtor_t; 155169691Skan 156169691Skan public: 157169691Skan typedef Allocator allocator; 158169691Skan typedef typename Allocator::size_type size_type; 159169691Skan typedef typename Allocator::difference_type difference_type; 160169691Skan typedef Eq_Fn eq_fn; 161169691Skan typedef Update_Policy update_policy; 162169691Skan typedef typename Update_Policy::metadata_type update_metadata; 163169691Skan typedef typename traits_base::key_type key_type; 164169691Skan typedef typename traits_base::key_pointer key_pointer; 165169691Skan typedef typename traits_base::const_key_pointer const_key_pointer; 166169691Skan typedef typename traits_base::key_reference key_reference; 167169691Skan typedef typename traits_base::const_key_reference const_key_reference; 168169691Skan typedef typename traits_base::mapped_type mapped_type; 169169691Skan typedef typename traits_base::mapped_pointer mapped_pointer; 170169691Skan typedef typename traits_base::const_mapped_pointer const_mapped_pointer; 171169691Skan typedef typename traits_base::mapped_reference mapped_reference; 172169691Skan typedef typename traits_base::const_mapped_reference const_mapped_reference; 173169691Skan typedef typename traits_base::value_type value_type; 174169691Skan typedef typename traits_base::pointer pointer; 175169691Skan typedef typename traits_base::const_pointer const_pointer; 176169691Skan typedef typename traits_base::reference reference; 177169691Skan typedef typename traits_base::const_reference const_reference; 178169691Skan 179169691Skan#ifdef PB_DS_DATA_TRUE_INDICATOR 180169691Skan typedef point_iterator_ point_iterator; 181169691Skan#endif 182169691Skan 183169691Skan#ifdef PB_DS_DATA_FALSE_INDICATOR 184169691Skan typedef const_point_iterator_ point_iterator; 185169691Skan#endif 186169691Skan 187169691Skan typedef const_point_iterator_ const_point_iterator; 188169691Skan 189169691Skan#ifdef PB_DS_DATA_TRUE_INDICATOR 190169691Skan typedef iterator_ iterator; 191169691Skan#endif 192169691Skan 193169691Skan#ifdef PB_DS_DATA_FALSE_INDICATOR 194169691Skan typedef const_iterator_ iterator; 195169691Skan#endif 196169691Skan 197169691Skan typedef const_iterator_ const_iterator; 198169691Skan 199169691Skan public: 200169691Skan PB_DS_CLASS_NAME(); 201169691Skan 202169691Skan PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC&); 203169691Skan 204169691Skan virtual 205169691Skan ~PB_DS_CLASS_NAME(); 206169691Skan 207169691Skan template<typename It> 208169691Skan PB_DS_CLASS_NAME(It first_it, It last_it); 209169691Skan 210169691Skan void 211169691Skan swap(PB_DS_CLASS_C_DEC&); 212169691Skan 213169691Skan inline size_type 214169691Skan size() const; 215169691Skan 216169691Skan inline size_type 217169691Skan max_size() const; 218169691Skan 219169691Skan inline bool 220169691Skan empty() const; 221169691Skan 222169691Skan inline mapped_reference 223169691Skan operator[](const_key_reference r_key) 224169691Skan { 225169691Skan#ifdef PB_DS_DATA_TRUE_INDICATOR 226169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid();) 227169691Skan return insert(std::make_pair(r_key, mapped_type())).first->second; 228169691Skan#else 229169691Skan insert(r_key); 230169691Skan return traits_base::s_null_mapped; 231169691Skan#endif 232169691Skan } 233169691Skan 234169691Skan inline std::pair<point_iterator, bool> 235169691Skan insert(const_reference); 236169691Skan 237169691Skan inline point_iterator 238169691Skan find(const_key_reference r_key) 239169691Skan { 240169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid();) 241169691Skan entry_pointer p_e = find_imp(r_key); 242169691Skan return point_iterator(p_e == NULL ? NULL: &p_e->m_value); 243169691Skan } 244169691Skan 245169691Skan inline const_point_iterator 246169691Skan find(const_key_reference r_key) const 247169691Skan { 248169691Skan _GLIBCXX_DEBUG_ONLY(assert_valid();) 249169691Skan entry_pointer p_e = find_imp(r_key); 250169691Skan return const_point_iterator(p_e == NULL ? NULL: &p_e->m_value); 251169691Skan } 252169691Skan 253169691Skan inline bool 254169691Skan erase(const_key_reference); 255169691Skan 256169691Skan template<typename Pred> 257169691Skan inline size_type 258169691Skan erase_if(Pred); 259169691Skan 260169691Skan void 261169691Skan clear(); 262169691Skan 263169691Skan inline iterator 264169691Skan begin(); 265169691Skan 266169691Skan inline const_iterator 267169691Skan begin() const; 268169691Skan 269169691Skan inline iterator 270169691Skan end(); 271169691Skan 272169691Skan inline const_iterator 273169691Skan end() const; 274169691Skan 275169691Skan#ifdef _GLIBCXX_DEBUG 276169691Skan void 277169691Skan assert_valid() const; 278169691Skan#endif 279169691Skan 280169691Skan#ifdef PB_DS_LU_MAP_TRACE_ 281169691Skan void 282169691Skan trace() const; 283169691Skan#endif 284169691Skan 285169691Skan protected: 286169691Skan 287169691Skan template<typename It> 288169691Skan void 289169691Skan copy_from_range(It, It); 290169691Skan 291169691Skan private: 292169691Skan#ifdef PB_DS_DATA_TRUE_INDICATOR 293169691Skan friend class iterator_; 294169691Skan#endif 295169691Skan 296169691Skan friend class const_iterator_; 297169691Skan 298169691Skan inline entry_pointer 299169691Skan allocate_new_entry(const_reference, false_type); 300169691Skan 301169691Skan inline entry_pointer 302169691Skan allocate_new_entry(const_reference, true_type); 303169691Skan 304169691Skan template<typename Metadata> 305169691Skan inline static void 306169691Skan init_entry_metadata(entry_pointer, type_to_type<Metadata>); 307169691Skan 308169691Skan inline static void 309169691Skan init_entry_metadata(entry_pointer, type_to_type<null_lu_metadata>); 310169691Skan 311169691Skan void 312169691Skan deallocate_all(); 313169691Skan 314169691Skan void 315169691Skan erase_next(entry_pointer); 316169691Skan 317169691Skan void 318169691Skan actual_erase_entry(entry_pointer); 319169691Skan 320169691Skan void 321169691Skan inc_it_state(const_pointer& r_p_value, entry_pointer& r_pos) const 322169691Skan { 323169691Skan r_pos = r_pos->m_p_next; 324169691Skan r_p_value = (r_pos == NULL) ? NULL : &r_pos->m_value; 325169691Skan } 326169691Skan 327169691Skan template<typename Metadata> 328169691Skan inline static bool 329169691Skan apply_update(entry_pointer, type_to_type<Metadata>); 330169691Skan 331169691Skan inline static bool 332169691Skan apply_update(entry_pointer, type_to_type<null_lu_metadata>); 333169691Skan 334169691Skan inline entry_pointer 335169691Skan find_imp(const_key_reference) const; 336169691Skan 337169691Skan static entry_allocator s_entry_allocator; 338169691Skan static Eq_Fn s_eq_fn; 339169691Skan static Update_Policy s_update_policy; 340169691Skan static type_to_type<update_metadata> s_metadata_type_indicator; 341169691Skan static null_lu_metadata s_null_lu_metadata; 342169691Skan 343169691Skan mutable entry_pointer m_p_l; 344169691Skan }; 345169691Skan 346169691Skan#include <ext/pb_ds/detail/list_update_map_/constructor_destructor_fn_imps.hpp> 347169691Skan#include <ext/pb_ds/detail/list_update_map_/info_fn_imps.hpp> 348169691Skan#include <ext/pb_ds/detail/list_update_map_/debug_fn_imps.hpp> 349169691Skan#include <ext/pb_ds/detail/list_update_map_/iterators_fn_imps.hpp> 350169691Skan#include <ext/pb_ds/detail/list_update_map_/erase_fn_imps.hpp> 351169691Skan#include <ext/pb_ds/detail/list_update_map_/find_fn_imps.hpp> 352169691Skan#include <ext/pb_ds/detail/list_update_map_/insert_fn_imps.hpp> 353169691Skan#include <ext/pb_ds/detail/list_update_map_/trace_fn_imps.hpp> 354169691Skan 355169691Skan#undef PB_DS_CLASS_T_DEC 356169691Skan#undef PB_DS_CLASS_C_DEC 357169691Skan#undef PB_DS_TYPES_TRAITS_C_DEC 358169691Skan#undef PB_DS_MAP_DEBUG_BASE_C_DEC 359169691Skan#undef PB_DS_CLASS_NAME 360169691Skan#undef PB_DS_V2F 361169691Skan#undef PB_DS_EP2VP 362169691Skan#undef PB_DS_V2S 363169691Skan 364169691Skan } // namespace detail 365169691Skan} // namespace pb_ds 366