1// -*- C++ -*-
2
3// Copyright (C) 2005, 2006, 2009 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 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#define PB_DS_CLASS_T_DEC \
61    template<typename Key, typename Mapped, class Eq_Fn, \
62	     class Allocator, class Update_Policy>
63
64#ifdef PB_DS_DATA_TRUE_INDICATOR
65#define PB_DS_CLASS_NAME lu_map_data_
66#endif
67
68#ifdef PB_DS_DATA_FALSE_INDICATOR
69#define PB_DS_CLASS_NAME lu_map_no_data_
70#endif
71
72#define PB_DS_CLASS_C_DEC \
73    PB_DS_CLASS_NAME<Key, Mapped, Eq_Fn, Allocator, Update_Policy>
74
75#define PB_DS_TYPES_TRAITS_C_DEC \
76    types_traits<Key, Mapped, Allocator, false>
77
78#ifdef _GLIBCXX_DEBUG
79#define PB_DS_DEBUG_MAP_BASE_C_DEC \
80    debug_map_base<Key, Eq_Fn, \
81	      typename Allocator::template rebind<Key>::other::const_reference>
82#endif
83
84#ifdef PB_DS_DATA_TRUE_INDICATOR
85#define PB_DS_V2F(X) (X).first
86#define PB_DS_V2S(X) (X).second
87#define PB_DS_EP2VP(X)& ((X)->m_value)
88#endif
89
90#ifdef PB_DS_DATA_FALSE_INDICATOR
91#define PB_DS_V2F(X) (X)
92#define PB_DS_V2S(X) Mapped_Data()
93#define PB_DS_EP2VP(X)& ((X)->m_value.first)
94#endif
95
96    /* Skip to the lu, my darling. */
97    // list-based (with updates) associative container.
98    template<typename Key,
99	     typename Mapped,
100	     class Eq_Fn,
101	     class Allocator,
102	     class Update_Policy>
103    class PB_DS_CLASS_NAME :
104#ifdef _GLIBCXX_DEBUG
105      protected PB_DS_DEBUG_MAP_BASE_C_DEC,
106#endif
107      public PB_DS_TYPES_TRAITS_C_DEC
108    {
109    private:
110      typedef PB_DS_TYPES_TRAITS_C_DEC traits_base;
111
112      struct entry
113     : public lu_map_entry_metadata_base<typename Update_Policy::metadata_type>
114      {
115	typename traits_base::value_type m_value;
116	typename Allocator::template rebind<entry>::other::pointer m_p_next;
117      };
118
119      typedef typename Allocator::template rebind<entry>::other entry_allocator;
120      typedef typename entry_allocator::pointer entry_pointer;
121      typedef typename entry_allocator::const_pointer const_entry_pointer;
122      typedef typename entry_allocator::reference entry_reference;
123      typedef typename entry_allocator::const_reference const_entry_reference;
124
125      typedef typename Allocator::template rebind<entry_pointer>::other entry_pointer_allocator;
126      typedef typename entry_pointer_allocator::pointer entry_pointer_array;
127
128      typedef typename traits_base::value_type value_type_;
129      typedef typename traits_base::pointer pointer_;
130      typedef typename traits_base::const_pointer const_pointer_;
131      typedef typename traits_base::reference reference_;
132      typedef typename traits_base::const_reference const_reference_;
133
134#define PB_DS_GEN_POS entry_pointer
135
136#include <ext/pb_ds/detail/unordered_iterator/const_point_iterator.hpp>
137#include <ext/pb_ds/detail/unordered_iterator/point_iterator.hpp>
138#include <ext/pb_ds/detail/unordered_iterator/const_iterator.hpp>
139#include <ext/pb_ds/detail/unordered_iterator/iterator.hpp>
140
141#undef PB_DS_GEN_POS
142
143
144#ifdef _GLIBCXX_DEBUG
145      typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base;
146#endif
147
148      typedef cond_dealtor<entry, Allocator> cond_dealtor_t;
149
150    public:
151      typedef Allocator allocator_type;
152      typedef typename Allocator::size_type size_type;
153      typedef typename Allocator::difference_type difference_type;
154      typedef Eq_Fn eq_fn;
155      typedef Update_Policy update_policy;
156      typedef typename Update_Policy::metadata_type update_metadata;
157      typedef typename traits_base::key_type key_type;
158      typedef typename traits_base::key_pointer key_pointer;
159      typedef typename traits_base::const_key_pointer const_key_pointer;
160      typedef typename traits_base::key_reference key_reference;
161      typedef typename traits_base::const_key_reference const_key_reference;
162      typedef typename traits_base::mapped_type mapped_type;
163      typedef typename traits_base::mapped_pointer mapped_pointer;
164      typedef typename traits_base::const_mapped_pointer const_mapped_pointer;
165      typedef typename traits_base::mapped_reference mapped_reference;
166      typedef typename traits_base::const_mapped_reference const_mapped_reference;
167      typedef typename traits_base::value_type value_type;
168      typedef typename traits_base::pointer pointer;
169      typedef typename traits_base::const_pointer const_pointer;
170      typedef typename traits_base::reference reference;
171      typedef typename traits_base::const_reference const_reference;
172
173#ifdef PB_DS_DATA_TRUE_INDICATOR
174      typedef point_iterator_ point_iterator;
175#endif
176
177#ifdef PB_DS_DATA_FALSE_INDICATOR
178      typedef const_point_iterator_ point_iterator;
179#endif
180
181      typedef const_point_iterator_ const_point_iterator;
182
183#ifdef PB_DS_DATA_TRUE_INDICATOR
184      typedef iterator_ iterator;
185#endif
186
187#ifdef PB_DS_DATA_FALSE_INDICATOR
188      typedef const_iterator_ iterator;
189#endif
190
191      typedef const_iterator_ const_iterator;
192
193    public:
194      PB_DS_CLASS_NAME();
195
196      PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC&);
197
198      virtual
199      ~PB_DS_CLASS_NAME();
200
201      template<typename It>
202      PB_DS_CLASS_NAME(It first_it, It last_it);
203
204      void
205      swap(PB_DS_CLASS_C_DEC&);
206
207      inline size_type
208      size() const;
209
210      inline size_type
211      max_size() const;
212
213      inline bool
214      empty() const;
215
216      inline mapped_reference
217      operator[](const_key_reference r_key)
218      {
219#ifdef PB_DS_DATA_TRUE_INDICATOR
220	_GLIBCXX_DEBUG_ONLY(assert_valid();)
221	return insert(std::make_pair(r_key, mapped_type())).first->second;
222#else
223	insert(r_key);
224	return traits_base::s_null_mapped;
225#endif
226      }
227
228      inline std::pair<point_iterator, bool>
229      insert(const_reference);
230
231      inline point_iterator
232      find(const_key_reference r_key)
233      {
234	_GLIBCXX_DEBUG_ONLY(assert_valid();)
235	entry_pointer p_e = find_imp(r_key);
236	return point_iterator(p_e == NULL ? NULL: &p_e->m_value);
237      }
238
239      inline const_point_iterator
240      find(const_key_reference r_key) const
241      {
242	_GLIBCXX_DEBUG_ONLY(assert_valid();)
243	entry_pointer p_e = find_imp(r_key);
244	return const_point_iterator(p_e == NULL ? NULL: &p_e->m_value);
245      }
246
247      inline bool
248      erase(const_key_reference);
249
250      template<typename Pred>
251      inline size_type
252      erase_if(Pred);
253
254      void
255      clear();
256
257      inline iterator
258      begin();
259
260      inline const_iterator
261      begin() const;
262
263      inline iterator
264      end();
265
266      inline const_iterator
267      end() const;
268
269#ifdef _GLIBCXX_DEBUG
270      void
271      assert_valid() const;
272#endif
273
274#ifdef PB_DS_LU_MAP_TRACE_
275      void
276      trace() const;
277#endif
278
279    protected:
280
281      template<typename It>
282      void
283      copy_from_range(It, It);
284
285    private:
286#ifdef PB_DS_DATA_TRUE_INDICATOR
287      friend class iterator_;
288#endif
289
290      friend class const_iterator_;
291
292      inline entry_pointer
293      allocate_new_entry(const_reference, false_type);
294
295      inline entry_pointer
296      allocate_new_entry(const_reference, true_type);
297
298      template<typename Metadata>
299      inline static void
300      init_entry_metadata(entry_pointer, type_to_type<Metadata>);
301
302      inline static void
303      init_entry_metadata(entry_pointer, type_to_type<null_lu_metadata>);
304
305      void
306      deallocate_all();
307
308      void
309      erase_next(entry_pointer);
310
311      void
312      actual_erase_entry(entry_pointer);
313
314      void
315      inc_it_state(const_pointer& r_p_value, entry_pointer& r_pos) const
316      {
317	r_pos = r_pos->m_p_next;
318	r_p_value = (r_pos == NULL) ? NULL : &r_pos->m_value;
319      }
320
321      template<typename Metadata>
322      inline static bool
323      apply_update(entry_pointer, type_to_type<Metadata>);
324
325      inline static bool
326      apply_update(entry_pointer, type_to_type<null_lu_metadata>);
327
328      inline entry_pointer
329      find_imp(const_key_reference) const;
330
331      static entry_allocator s_entry_allocator;
332      static Eq_Fn s_eq_fn;
333      static Update_Policy s_update_policy;
334      static type_to_type<update_metadata> s_metadata_type_indicator;
335      static null_lu_metadata s_null_lu_metadata;
336
337      mutable entry_pointer m_p_l;
338    };
339
340#include <ext/pb_ds/detail/list_update_map_/constructor_destructor_fn_imps.hpp>
341#include <ext/pb_ds/detail/list_update_map_/info_fn_imps.hpp>
342#include <ext/pb_ds/detail/list_update_map_/debug_fn_imps.hpp>
343#include <ext/pb_ds/detail/list_update_map_/iterators_fn_imps.hpp>
344#include <ext/pb_ds/detail/list_update_map_/erase_fn_imps.hpp>
345#include <ext/pb_ds/detail/list_update_map_/find_fn_imps.hpp>
346#include <ext/pb_ds/detail/list_update_map_/insert_fn_imps.hpp>
347#include <ext/pb_ds/detail/list_update_map_/trace_fn_imps.hpp>
348
349#undef PB_DS_CLASS_T_DEC
350#undef PB_DS_CLASS_C_DEC
351#undef  PB_DS_TYPES_TRAITS_C_DEC
352#undef PB_DS_DEBUG_MAP_BASE_C_DEC
353#undef PB_DS_CLASS_NAME
354#undef PB_DS_V2F
355#undef PB_DS_EP2VP
356#undef PB_DS_V2S
357
358  } // namespace detail
359} // namespace __gnu_pbds
360