3 // Copyright (C) 2005 Free Software Foundation, Inc.
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
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 2, or (at your option)
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
16 // You should have received a copy of the GNU General Public License along
17 // with this library; see the file COPYING. If not, write to the Free
18 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
21 // As a special exception, you may use this file as part of a free software
22 // library without restriction. Specifically, if other files instantiate
23 // templates or use macros or inline functions from this file, or you compile
24 // this file and link it with other files to produce an executable, this
25 // file does not by itself cause the resulting executable to be covered by
26 // the GNU General Public License. This exception does not however
27 // invalidate any other reasons why the executable file might be covered by
28 // the GNU General Public License.
30 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
32 // Permission to use, copy, modify, sell, and distribute this software
33 // is hereby granted without fee, provided that the above copyright
34 // notice appears in all copies, and that both that copyright notice and
35 // this permission notice appear in supporting documentation. None of
36 // the above authors, nor IBM Haifa Research Laboratories, make any
37 // representation about the suitability of this software for any
38 // purpose. It is provided "as is" without express or implied warranty.
42 * Contains a list update map.
47 #include <ext/pb_assoc/detail/cond_dealtor.hpp>
48 #include <ext/pb_assoc/trivial_iterator_def.hpp>
49 #include <ext/pb_assoc/detail/types_traits.hpp>
50 #include <ext/pb_assoc/exception.hpp>
51 #include <ext/pb_assoc/detail/map_debug_base.hpp>
59 #ifdef PB_ASSOC_LU_MAP_DEBUG_
60 #define PB_ASSOC_DBG_ASSERT(X) assert(X)
61 #define PB_ASSOC_DBG_VERIFY(X) assert(X)
62 #define PB_ASSOC_DBG_ONLY(X) X
63 #else // #ifdef PB_ASSOC_LU_MAP_DEBUG_
64 #define PB_ASSOC_DBG_ASSERT(X)
65 #define PB_ASSOC_DBG_VERIFY(X) {if((X)==0);}
66 #define PB_ASSOC_DBG_ONLY(X) ;
67 #endif // #ifdef PB_ASSOC_LU_MAP_DEBUG_
69 #define PB_ASSOC_CLASS_T_DEC \
77 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
78 #define PB_ASSOC_CLASS_NAME \
80 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
82 #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
83 #define PB_ASSOC_CLASS_NAME \
85 #endif // #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
87 #define PB_ASSOC_CLASS_C_DEC \
88 PB_ASSOC_CLASS_NAME< \
95 #define PB_ASSOC_TYPES_TRAITS_C_DEC \
96 pb_assoc::detail::types_traits< \
101 #ifdef PB_ASSOC_USE_MAP_DEBUG_BASE
102 #define PB_ASSOC_MAP_DEBUG_BASE_C_DEC \
103 pb_assoc::detail::map_debug_base< \
106 #endif // #ifdef PB_ASSOC_USE_MAP_DEBUG_BASE
108 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
109 #define PB_ASSOC_V2F(X) (X).first
110 #define PB_ASSOC_V2S(X) (X).second
111 #define PB_ASSOC_EP2VP(X)& ((X)->m_value)
112 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
114 #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
115 #define PB_ASSOC_V2F(X) (X)
116 #define PB_ASSOC_V2S(X) Data()
117 #define PB_ASSOC_EP2VP(X)& ((X)->m_value.first)
118 #endif // #ifdef PB_ASSOC_DATA_FALSE_INDICATOR
120 #ifdef PB_ASSOC_LU_MAP_DEBUG_
121 #define PB_ASSOC_DBG_ASSERT(X) assert(X)
122 #define PB_ASSOC_DBG_VERIFY(X) assert(X)
123 #define PB_ASSOC_DBG_ONLY(X) X
124 #else // #ifdef PB_ASSOC_LU_MAP_DEBUG_
125 #define PB_ASSOC_DBG_ASSERT(X)
126 #define PB_ASSOC_DBG_VERIFY(X) {if((X)==0);}
127 #define PB_ASSOC_DBG_ONLY(X) ;
128 #endif // #ifdef PB_ASSOC_LU_MAP_DEBUG_
130 /* Skip to the lu, my darling. */
132 template<typename Key
,
137 class PB_ASSOC_CLASS_NAME
:
138 #ifdef PB_ASSOC_LU_MAP_DEBUG_
139 protected PB_ASSOC_MAP_DEBUG_BASE_C_DEC
,
140 #endif // #ifdef PB_ASSOC_LU_MAP_DEBUG_
142 public Update_Policy
,
143 public PB_ASSOC_TYPES_TRAITS_C_DEC
148 typedef typename
Allocator::size_type size_type
;
151 typename
PB_ASSOC_TYPES_TRAITS_C_DEC::const_key_reference
154 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
156 typedef typename
PB_ASSOC_TYPES_TRAITS_C_DEC::data_type data_type
;
159 typename
PB_ASSOC_TYPES_TRAITS_C_DEC::data_reference
163 typename
PB_ASSOC_TYPES_TRAITS_C_DEC::const_data_reference
164 const_data_reference
;
166 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
168 typedef typename
PB_ASSOC_TYPES_TRAITS_C_DEC::value_type value_type
;
170 typedef typename
PB_ASSOC_TYPES_TRAITS_C_DEC::pointer pointer
;
173 typename
PB_ASSOC_TYPES_TRAITS_C_DEC::const_pointer
176 typedef typename
PB_ASSOC_TYPES_TRAITS_C_DEC::reference reference
;
179 typename
PB_ASSOC_TYPES_TRAITS_C_DEC::const_reference
182 typedef Update_Policy update_policy
;
184 typedef typename
Update_Policy::metadata_type update_metadata
;
188 typename
PB_ASSOC_TYPES_TRAITS_C_DEC::value_type m_value
;
190 update_metadata m_update_metadata
;
192 typename
Allocator::template rebind
<entry
>::other::pointer m_p_next
;
196 typename
Allocator::template rebind
<entry
>::other
199 typedef typename
entry_allocator::pointer entry_pointer
;
201 typedef typename
entry_allocator::const_pointer const_entry_pointer
;
203 typedef typename
entry_allocator::reference entry_reference
;
206 typename
entry_allocator::const_reference
207 const_entry_reference
;
210 typename
Allocator::template rebind
<entry_pointer
>::other
211 entry_pointer_allocator
;
213 typedef typename
entry_pointer_allocator::pointer entry_pointer_array
;
215 #define PB_ASSOC_GEN_POS entry_pointer
217 typedef value_type mapped_value_type
;
219 typedef pointer mapped_pointer
;
221 typedef const_pointer const_mapped_pointer
;
223 typedef reference mapped_reference
;
225 typedef const_reference const_mapped_reference
;
227 #include <ext/pb_assoc/detail/unordered_iterator/const_find_iterator.hpp>
228 #include <ext/pb_assoc/detail/unordered_iterator/find_iterator.hpp>
229 #include <ext/pb_assoc/detail/unordered_iterator/const_iterator.hpp>
230 #include <ext/pb_assoc/detail/unordered_iterator/iterator.hpp>
232 #undef PB_ASSOC_GEN_POS
234 typedef find_iterator_ find_iterator
;
236 typedef const_find_iterator_ const_find_iterator
;
238 typedef iterator_ iterator
;
240 typedef const_iterator_ const_iterator
;
244 typedef Allocator allocator
;
248 PB_ASSOC_CLASS_NAME();
250 PB_ASSOC_CLASS_NAME(const Eq_Fn
& r_eq_fn
);
252 PB_ASSOC_CLASS_NAME(const Eq_Fn
& r_eq_fn
, const Update_Policy
& r_update_policy
);
254 PB_ASSOC_CLASS_NAME(const PB_ASSOC_CLASS_C_DEC
& r_other
);
257 ~PB_ASSOC_CLASS_NAME();
260 swap(PB_ASSOC_CLASS_C_DEC
& r_other
);
264 copy_from_range(It first_it
, It last_it
);
281 inline std::pair
<find_iterator
, bool>
282 insert(const_reference r_val
);
284 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
285 inline data_reference
286 subscript_imp(const_key_reference r_key
);
287 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
290 find(const_key_reference r_key
);
292 inline const_find_iterator
293 find(const_key_reference r_key
) const;
295 #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
296 inline const_data_reference
297 const_subscript_imp(const_key_reference r_key
) const;
298 #endif // #ifdef PB_ASSOC_DATA_TRUE_INDICATOR
301 erase(const_key_reference r_key
);
305 erase_if(Pred
& r_pred
);
313 inline const_iterator
319 inline const_iterator
322 #ifdef PB_ASSOC_LU_MAP_DEBUG_
325 assert_valid() const;
327 #endif // #ifdef PB_ASSOC_LU_MAP_DEBUG_
331 typedef PB_ASSOC_TYPES_TRAITS_C_DEC my_traits_base
;
333 #ifdef PB_ASSOC_USE_MAP_DEBUG_BASE
334 typedef PB_ASSOC_MAP_DEBUG_BASE_C_DEC my_map_debug_base
;
335 #endif // #ifdef PB_ASSOC_USE_MAP_DEBUG_BASE
338 pb_assoc::detail::cond_dealtor
<
346 deallocate_all(bool deallocate_root
);
349 move_next_to_front(entry_pointer p_l
) const;
355 insert_new_after(entry_pointer p_l
, const_reference r_val
);
358 find_imp(const_key_reference r_key
) const
360 entry_pointer p_l
= m_p_l
;
362 while (p_l
->m_p_next
!= NULL
)
363 if (Eq_Fn::operator()(
365 PB_ASSOC_V2F(p_l
->m_p_next
->m_value
)))
367 if (Update_Policy::operator()(p_l
->m_update_metadata
))
369 move_next_to_front(p_l
);
383 erase_imp(entry_pointer p_l
);
388 inline const_find_iterator
392 inc_it_state(pointer
& r_p_value
, std::pair
<entry_pointer
, size_type
>& r_pos
) const;
395 inc_it_state(const_pointer
& r_p_value
, entry_pointer
& r_pos
) const;
398 get_start_it_state(pointer
& r_p_value
, std::pair
<entry_pointer
, size_type
>& r_pos
) const;
400 #ifdef PB_ASSOC_LU_MAP_DEBUG_
403 assert_entry_pointer_array_valid(const entry_pointer_array a_p_lntries
) const;
406 assert_entry_pointer_valid(const entry_pointer p_l
, store_hash_true_indicator
) const;
409 assert_entry_pointer_valid(const entry_pointer p_l
, store_hash_false_indicator
) const;
411 #endif // #ifdef PB_ASSOC_LU_MAP_DEBUG_
415 static entry_allocator s_entry_allocator
;
417 mutable entry_pointer m_p_l
;
421 friend class iterator_
;
423 friend class const_iterator_
;
425 static iterator s_end_it
;
427 static const_iterator s_const_end_it
;
429 static find_iterator s_find_end_it
;
431 static const_find_iterator s_const_find_end_it
;
435 #include <ext/pb_assoc/detail/lu_map_/constructor_destructor_fn_imps.hpp>
436 #include <ext/pb_assoc/detail/lu_map_/info_fn_imps.hpp>
437 #include <ext/pb_assoc/detail/lu_map_/debug_fn_imps.hpp>
438 #include <ext/pb_assoc/detail/lu_map_/policy_access_fn_imps.hpp>
439 #include <ext/pb_assoc/detail/lu_map_/iterators_fn_imps.hpp>
440 #include <ext/pb_assoc/detail/lu_map_/erase_fn_imps.hpp>
441 #include <ext/pb_assoc/detail/lu_map_/find_fn_imps.hpp>
442 #include <ext/pb_assoc/detail/lu_map_/insert_fn_imps.hpp>
444 #undef PB_ASSOC_CLASS_T_DEC
446 #undef PB_ASSOC_CLASS_C_DEC
448 #undef PB_ASSOC_TYPES_TRAITS_C_DEC
450 #undef PB_ASSOC_MAP_DEBUG_BASE_C_DEC
452 #undef PB_ASSOC_CLASS_NAME
455 #undef PB_ASSOC_EP2VP
458 #undef PB_ASSOC_DBG_ASSERT
459 #undef PB_ASSOC_DBG_VERIFY
460 #undef PB_ASSOC_DBG_ONLY
462 } // namespace detail
464 } // namespace pb_assoc