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