1// -*- C++ -*-
2
3// Copyright (C) 2005-2022 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
56namespace __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 rebind_traits<_Alloc, Key>::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 rebind_traits<_Alloc, entry>::pointer m_p_next;
105      };
106
107      typedef rebind_traits<_Alloc, entry>		  entry_alloc_traits;
108      typedef typename entry_alloc_traits::allocator_type entry_allocator;
109      typedef typename entry_alloc_traits::pointer	  entry_pointer;
110      typedef typename entry_alloc_traits::const_pointer  const_entry_pointer;
111      typedef typename entry_alloc_traits::reference	  entry_reference;
112      typedef typename entry_alloc_traits::const_reference const_entry_reference;
113
114      typedef rebind_traits<_Alloc, entry_pointer>	entry_pointer_alloc_traits;
115      typedef typename entry_pointer_alloc_traits::allocator_type entry_pointer_allocator;
116      typedef typename entry_pointer_alloc_traits::pointer entry_pointer_array;
117
118      typedef typename traits_base::value_type value_type_;
119      typedef typename traits_base::pointer pointer_;
120      typedef typename traits_base::const_pointer const_pointer_;
121      typedef typename traits_base::reference reference_;
122      typedef typename traits_base::const_reference const_reference_;
123
124#define PB_DS_GEN_POS entry_pointer
125
126#include <ext/pb_ds/detail/unordered_iterator/point_const_iterator.hpp>
127#include <ext/pb_ds/detail/unordered_iterator/point_iterator.hpp>
128#include <ext/pb_ds/detail/unordered_iterator/const_iterator.hpp>
129#include <ext/pb_ds/detail/unordered_iterator/iterator.hpp>
130
131#undef PB_DS_GEN_POS
132
133
134#ifdef _GLIBCXX_DEBUG
135      typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base;
136#endif
137
138      typedef cond_dealtor<entry, _Alloc> cond_dealtor_t;
139
140    public:
141      typedef _Alloc allocator_type;
142      typedef typename _Alloc::size_type size_type;
143      typedef typename _Alloc::difference_type difference_type;
144      typedef Eq_Fn eq_fn;
145      typedef Update_Policy update_policy;
146      typedef typename Update_Policy::metadata_type update_metadata;
147      typedef typename traits_base::key_type key_type;
148      typedef typename traits_base::key_pointer key_pointer;
149      typedef typename traits_base::key_const_pointer key_const_pointer;
150      typedef typename traits_base::key_reference key_reference;
151      typedef typename traits_base::key_const_reference key_const_reference;
152      typedef typename traits_base::mapped_type mapped_type;
153      typedef typename traits_base::mapped_pointer mapped_pointer;
154      typedef typename traits_base::mapped_const_pointer mapped_const_pointer;
155      typedef typename traits_base::mapped_reference mapped_reference;
156      typedef typename traits_base::mapped_const_reference mapped_const_reference;
157      typedef typename traits_base::value_type value_type;
158      typedef typename traits_base::pointer pointer;
159      typedef typename traits_base::const_pointer const_pointer;
160      typedef typename traits_base::reference reference;
161      typedef typename traits_base::const_reference const_reference;
162
163#ifdef PB_DS_DATA_TRUE_INDICATOR
164      typedef point_iterator_ 			point_iterator;
165#endif
166
167#ifdef PB_DS_DATA_FALSE_INDICATOR
168      typedef point_const_iterator_ 		point_iterator;
169#endif
170
171      typedef point_const_iterator_ 		point_const_iterator;
172
173#ifdef PB_DS_DATA_TRUE_INDICATOR
174      typedef iterator_ 			iterator;
175#endif
176
177#ifdef PB_DS_DATA_FALSE_INDICATOR
178      typedef const_iterator_ 			iterator;
179#endif
180
181      typedef const_iterator_ 			const_iterator;
182
183    public:
184      PB_DS_LU_NAME();
185
186      PB_DS_LU_NAME(const PB_DS_CLASS_C_DEC&);
187
188      virtual
189      ~PB_DS_LU_NAME();
190
191      template<typename It>
192      PB_DS_LU_NAME(It, It);
193
194      void
195      swap(PB_DS_CLASS_C_DEC&);
196
197      inline size_type
198      size() const;
199
200      inline size_type
201      max_size() const;
202
203      _GLIBCXX_NODISCARD inline bool
204      empty() const;
205
206      inline mapped_reference
207      operator[](key_const_reference r_key)
208      {
209#ifdef PB_DS_DATA_TRUE_INDICATOR
210	_GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);)
211	return insert(std::make_pair(r_key, mapped_type())).first->second;
212#else
213	insert(r_key);
214	return traits_base::s_null_type;
215#endif
216      }
217
218      inline std::pair<point_iterator, bool>
219      insert(const_reference);
220
221      inline point_iterator
222      find(key_const_reference r_key)
223      {
224	_GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);)
225	entry_pointer p_e = find_imp(r_key);
226	return point_iterator(p_e == 0 ? 0: &p_e->m_value);
227      }
228
229      inline point_const_iterator
230      find(key_const_reference r_key) const
231      {
232	_GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);)
233	entry_pointer p_e = find_imp(r_key);
234	return point_const_iterator(p_e == 0 ? 0: &p_e->m_value);
235      }
236
237      inline bool
238      erase(key_const_reference);
239
240      template<typename Pred>
241      inline size_type
242      erase_if(Pred);
243
244      void
245      clear();
246
247      inline iterator
248      begin();
249
250      inline const_iterator
251      begin() const;
252
253      inline iterator
254      end();
255
256      inline const_iterator
257      end() const;
258
259#ifdef _GLIBCXX_DEBUG
260      void
261      assert_valid(const char* file, int line) const;
262#endif
263
264#ifdef PB_DS_LU_MAP_TRACE_
265      void
266      trace() const;
267#endif
268
269    protected:
270
271      template<typename It>
272      void
273      copy_from_range(It, It);
274
275    private:
276#ifdef PB_DS_DATA_TRUE_INDICATOR
277      friend class iterator_;
278#endif
279
280      friend class const_iterator_;
281
282      inline entry_pointer
283      allocate_new_entry(const_reference, false_type);
284
285      inline entry_pointer
286      allocate_new_entry(const_reference, true_type);
287
288      template<typename Metadata>
289      inline static void
290      init_entry_metadata(entry_pointer, type_to_type<Metadata>);
291
292      inline static void
293      init_entry_metadata(entry_pointer, type_to_type<null_type>);
294
295      void
296      deallocate_all();
297
298      void
299      erase_next(entry_pointer);
300
301      void
302      actual_erase_entry(entry_pointer);
303
304      void
305      inc_it_state(const_pointer& r_p_value, entry_pointer& r_pos) const
306      {
307	r_pos = r_pos->m_p_next;
308	r_p_value = (r_pos == 0) ? 0 : &r_pos->m_value;
309      }
310
311      template<typename Metadata>
312      inline static bool
313      apply_update(entry_pointer, type_to_type<Metadata>);
314
315      inline static bool
316      apply_update(entry_pointer, type_to_type<null_type>);
317
318      inline entry_pointer
319      find_imp(key_const_reference) const;
320
321      static entry_allocator 			s_entry_allocator;
322      static Eq_Fn 				s_eq_fn;
323      static Update_Policy 			s_update_policy;
324      static type_to_type<update_metadata> 	s_metadata_type_indicator;
325      static null_type 				s_null_type;
326
327      mutable entry_pointer 			m_p_l;
328    };
329
330#include <ext/pb_ds/detail/list_update_map_/constructor_destructor_fn_imps.hpp>
331#include <ext/pb_ds/detail/list_update_map_/info_fn_imps.hpp>
332#include <ext/pb_ds/detail/list_update_map_/debug_fn_imps.hpp>
333#include <ext/pb_ds/detail/list_update_map_/iterators_fn_imps.hpp>
334#include <ext/pb_ds/detail/list_update_map_/erase_fn_imps.hpp>
335#include <ext/pb_ds/detail/list_update_map_/find_fn_imps.hpp>
336#include <ext/pb_ds/detail/list_update_map_/insert_fn_imps.hpp>
337#include <ext/pb_ds/detail/list_update_map_/trace_fn_imps.hpp>
338
339#undef PB_DS_CLASS_T_DEC
340#undef PB_DS_CLASS_C_DEC
341#undef PB_DS_LU_TRAITS_BASE
342#undef PB_DS_DEBUG_MAP_BASE_C_DEC
343#undef PB_DS_LU_NAME
344  } // namespace detail
345} // namespace __gnu_pbds
346