3 // Copyright (C) 2005, 2006 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 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
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.
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.
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
31 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
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
43 * @file gp_ht_map_.hpp
44 * Contains an implementation class for gp_ht_map_.
47 #include <ext/pb_ds/tag_and_trait.hpp>
48 #include <ext/pb_ds/detail/hash_fn/ranged_probe_fn.hpp>
49 #include <ext/pb_ds/detail/types_traits.hpp>
50 #include <ext/pb_ds/exception.hpp>
51 #include <ext/pb_ds/detail/eq_fn/hash_eq_fn.hpp>
53 #ifdef PB_DS_HT_MAP_TRACE_
57 #include <ext/pb_ds/detail/map_debug_base.hpp>
59 #include <debug/debug.h>
65 #define PB_DS_CLASS_T_DEC \
66 template<typename Key, typename Mapped, typename Hash_Fn, typename Eq_Fn, \
67 typename Allocator, bool Store_Hash, typename Comb_Probe_Fn, \
68 typename Probe_Fn, typename Resize_Policy>
70 #ifdef PB_DS_DATA_TRUE_INDICATOR
71 #define PB_DS_CLASS_NAME gp_ht_map_data_
74 #ifdef PB_DS_DATA_FALSE_INDICATOR
75 #define PB_DS_CLASS_NAME gp_ht_map_no_data_
78 #define PB_DS_CLASS_C_DEC \
79 PB_DS_CLASS_NAME<Key, Mapped, Hash_Fn, Eq_Fn, Allocator, \
80 Store_Hash, Comb_Probe_Fn, Probe_Fn, Resize_Policy>
82 #define PB_DS_HASH_EQ_FN_C_DEC \
83 hash_eq_fn<Key, Eq_Fn, Allocator, Store_Hash>
85 #define PB_DS_RANGED_PROBE_FN_C_DEC \
86 ranged_probe_fn<Key, Hash_Fn, Allocator, Comb_Probe_Fn, Probe_Fn, Store_Hash>
88 #define PB_DS_TYPES_TRAITS_C_DEC \
89 types_traits<Key, Mapped, Allocator, Store_Hash>
92 #define PB_DS_MAP_DEBUG_BASE_C_DEC \
93 map_debug_base<Key, Eq_Fn, typename Allocator::template rebind<Key>::other::const_reference>
96 #ifdef PB_DS_DATA_TRUE_INDICATOR
97 #define PB_DS_V2F(X) (X).first
98 #define PB_DS_V2S(X) (X).second
101 #ifdef PB_DS_DATA_FALSE_INDICATOR
102 #define PB_DS_V2F(X) (X)
103 #define PB_DS_V2S(X) Mapped()
106 #define PB_DS_STATIC_ASSERT(UNIQUE, E) \
107 typedef static_assert_dumclass<sizeof(static_assert<(bool)(E)>)> \
108 UNIQUE##static_assert_type
110 template<typename Key
,
116 typename Comb_Probe_Fn
,
118 typename Resize_Policy
>
119 class PB_DS_CLASS_NAME
:
120 #ifdef _GLIBCXX_DEBUG
121 protected PB_DS_MAP_DEBUG_BASE_C_DEC
,
123 public PB_DS_HASH_EQ_FN_C_DEC
,
124 public Resize_Policy
,
125 public PB_DS_RANGED_PROBE_FN_C_DEC
,
126 public PB_DS_TYPES_TRAITS_C_DEC
129 typedef PB_DS_TYPES_TRAITS_C_DEC traits_base
;
130 typedef typename
traits_base::value_type value_type_
;
131 typedef typename
traits_base::pointer pointer_
;
132 typedef typename
traits_base::const_pointer const_pointer_
;
133 typedef typename
traits_base::reference reference_
;
134 typedef typename
traits_base::const_reference const_reference_
;
135 typedef typename
traits_base::comp_hash comp_hash
;
142 } __attribute__ ((packed
));
144 struct entry
: public traits_base::stored_value_type
149 typedef typename
Allocator::template rebind
<entry
>::other entry_allocator
;
150 typedef typename
entry_allocator::pointer entry_pointer
;
151 typedef typename
entry_allocator::const_pointer const_entry_pointer
;
152 typedef typename
entry_allocator::reference entry_reference
;
153 typedef typename
entry_allocator::const_reference const_entry_reference
;
154 typedef typename
entry_allocator::pointer entry_array
;
156 typedef PB_DS_RANGED_PROBE_FN_C_DEC ranged_probe_fn_base
;
158 #ifdef _GLIBCXX_DEBUG
159 typedef PB_DS_MAP_DEBUG_BASE_C_DEC map_debug_base
;
162 typedef PB_DS_HASH_EQ_FN_C_DEC hash_eq_fn_base
;
163 typedef Resize_Policy resize_base
;
165 #define PB_DS_GEN_POS typename Allocator::size_type
167 #include <ext/pb_ds/detail/unordered_iterator/const_point_iterator.hpp>
168 #include <ext/pb_ds/detail/unordered_iterator/point_iterator.hpp>
169 #include <ext/pb_ds/detail/unordered_iterator/const_iterator.hpp>
170 #include <ext/pb_ds/detail/unordered_iterator/iterator.hpp>
175 typedef Allocator allocator
;
176 typedef typename
Allocator::size_type size_type
;
177 typedef typename
Allocator::difference_type difference_type
;
178 typedef Hash_Fn hash_fn
;
180 typedef Probe_Fn probe_fn
;
181 typedef Comb_Probe_Fn comb_probe_fn
;
182 typedef Resize_Policy resize_policy
;
186 store_hash
= Store_Hash
189 typedef typename
traits_base::key_type key_type
;
190 typedef typename
traits_base::key_pointer key_pointer
;
191 typedef typename
traits_base::const_key_pointer const_key_pointer
;
192 typedef typename
traits_base::key_reference key_reference
;
193 typedef typename
traits_base::const_key_reference const_key_reference
;
194 typedef typename
traits_base::mapped_type mapped_type
;
195 typedef typename
traits_base::mapped_pointer mapped_pointer
;
196 typedef typename
traits_base::const_mapped_pointer const_mapped_pointer
;
197 typedef typename
traits_base::mapped_reference mapped_reference
;
198 typedef typename
traits_base::const_mapped_reference const_mapped_reference
;
199 typedef typename
traits_base::value_type value_type
;
200 typedef typename
traits_base::pointer pointer
;
201 typedef typename
traits_base::const_pointer const_pointer
;
202 typedef typename
traits_base::reference reference
;
203 typedef typename
traits_base::const_reference const_reference
;
205 #ifdef PB_DS_DATA_TRUE_INDICATOR
206 typedef point_iterator_ point_iterator
;
209 #ifdef PB_DS_DATA_FALSE_INDICATOR
210 typedef const_point_iterator_ point_iterator
;
213 typedef const_point_iterator_ const_point_iterator
;
215 #ifdef PB_DS_DATA_TRUE_INDICATOR
216 typedef iterator_ iterator
;
219 #ifdef PB_DS_DATA_FALSE_INDICATOR
220 typedef const_iterator_ iterator
;
223 typedef const_iterator_ const_iterator
;
227 PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC
&);
229 PB_DS_CLASS_NAME(const Hash_Fn
&);
231 PB_DS_CLASS_NAME(const Hash_Fn
&, const Eq_Fn
&);
233 PB_DS_CLASS_NAME(const Hash_Fn
&, const Eq_Fn
&, const Comb_Probe_Fn
&);
235 PB_DS_CLASS_NAME(const Hash_Fn
&, const Eq_Fn
&, const Comb_Probe_Fn
&,
238 PB_DS_CLASS_NAME(const Hash_Fn
&, const Eq_Fn
&, const Comb_Probe_Fn
&,
239 const Probe_Fn
&, const Resize_Policy
&);
241 template<typename It
>
243 copy_from_range(It first_it
, It last_it
);
249 swap(PB_DS_CLASS_C_DEC
& other
);
276 get_probe_fn() const;
282 get_comb_probe_fn() const;
288 get_resize_policy() const;
290 inline std::pair
<point_iterator
, bool>
291 insert(const_reference r_val
)
293 _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();)
294 return insert_imp(r_val
, traits_base::m_store_extra_indicator
);
297 inline mapped_reference
298 operator[](const_key_reference r_key
)
300 #ifdef PB_DS_DATA_TRUE_INDICATOR
301 return subscript_imp(r_key
, traits_base::m_store_extra_indicator
);
304 return traits_base::s_null_mapped
;
308 inline point_iterator
309 find(const_key_reference r_key
);
311 inline const_point_iterator
312 find(const_key_reference r_key
) const;
314 inline point_iterator
317 inline const_point_iterator
321 erase(const_key_reference r_key
);
323 template<typename Pred
>
333 inline const_iterator
339 inline const_iterator
342 #ifdef _GLIBCXX_DEBUG
344 assert_valid() const;
347 #ifdef PB_DS_HT_MAP_TRACE_
353 #ifdef PB_DS_DATA_TRUE_INDICATOR
354 friend class iterator_
;
357 friend class const_iterator_
;
366 erase_all_valid_entries(entry_array
, size_type
);
369 do_resize_if_needed();
372 do_resize_if_needed_no_throw();
375 resize_imp(size_type
);
378 do_resize(size_type
);
381 resize_imp(entry_array
, size_type
);
384 resize_imp_reassign(entry_pointer
, entry_array
, false_type
);
387 resize_imp_reassign(entry_pointer
, entry_array
, true_type
);
390 find_ins_pos(const_key_reference
, false_type
);
393 find_ins_pos(const_key_reference
, true_type
);
395 inline std::pair
<point_iterator
, bool>
396 insert_imp(const_reference
, false_type
);
398 inline std::pair
<point_iterator
, bool>
399 insert_imp(const_reference
, true_type
);
402 insert_new_imp(const_reference r_val
, size_type pos
)
404 _GLIBCXX_DEBUG_ASSERT(m_entries
[pos
].m_stat
!= valid_entry_status
);
406 if (do_resize_if_needed())
407 pos
= find_ins_pos(PB_DS_V2F(r_val
),
408 traits_base::m_store_extra_indicator
);
410 _GLIBCXX_DEBUG_ASSERT(m_entries
[pos
].m_stat
!= valid_entry_status
);
412 entry
* const p_e
= m_entries
+ pos
;
413 new (&p_e
->m_value
) value_type(r_val
);
414 p_e
->m_stat
= valid_entry_status
;
415 resize_base::notify_inserted(++m_num_used_e
);
417 _GLIBCXX_DEBUG_ONLY(map_debug_base::insert_new(PB_DS_V2F(p_e
->m_value
));)
419 _GLIBCXX_DEBUG_ONLY(assert_valid();)
420 return &p_e
->m_value
;
424 insert_new_imp(const_reference r_val
, comp_hash
& r_pos_hash_pair
)
426 _GLIBCXX_DEBUG_ASSERT(m_entries
[r_pos_hash_pair
.first
].m_stat
!=
429 if (do_resize_if_needed())
430 r_pos_hash_pair
= find_ins_pos(PB_DS_V2F(r_val
),
431 traits_base::m_store_extra_indicator
);
433 _GLIBCXX_DEBUG_ASSERT(m_entries
[r_pos_hash_pair
.first
].m_stat
!=
436 entry
* const p_e
= m_entries
+ r_pos_hash_pair
.first
;
437 new (&p_e
->m_value
) value_type(r_val
);
438 p_e
->m_hash
= r_pos_hash_pair
.second
;
439 p_e
->m_stat
= valid_entry_status
;
441 resize_base::notify_inserted(++m_num_used_e
);
443 _GLIBCXX_DEBUG_ONLY(map_debug_base::insert_new(PB_DS_V2F(p_e
->m_value
));)
445 _GLIBCXX_DEBUG_ONLY(assert_valid();)
446 return &p_e
->m_value
;
449 #ifdef PB_DS_DATA_TRUE_INDICATOR
450 inline mapped_reference
451 subscript_imp(const_key_reference key
, false_type
)
453 _GLIBCXX_DEBUG_ONLY(assert_valid();)
455 const size_type pos
= find_ins_pos(key
,
456 traits_base::m_store_extra_indicator
);
458 entry_pointer p_e
= &m_entries
[pos
];
459 if (p_e
->m_stat
!= valid_entry_status
)
460 return insert_new_imp(value_type(key
, mapped_type()), pos
)->second
;
462 _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(key
);)
463 return p_e
->m_value
.second
;
466 inline mapped_reference
467 subscript_imp(const_key_reference key
, true_type
)
469 _GLIBCXX_DEBUG_ONLY(assert_valid();)
471 comp_hash pos_hash_pair
=
472 find_ins_pos(key
, traits_base::m_store_extra_indicator
);
474 if (m_entries
[pos_hash_pair
.first
].m_stat
!= valid_entry_status
)
475 return insert_new_imp(value_type(key
, mapped_type()),
476 pos_hash_pair
)->second
;
478 _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(key
));
479 return (m_entries
+ pos_hash_pair
.first
)->m_value
.second
;
484 find_key_pointer(const_key_reference key
, false_type
)
486 const size_type hash
= ranged_probe_fn_base::operator()(key
);
488 resize_base::notify_find_search_start();
490 // Loop until entry is found or until all possible entries accessed.
491 for (i
= 0; i
< m_num_e
; ++i
)
493 const size_type pos
= ranged_probe_fn_base::operator()(key
, hash
, i
);
495 entry
* const p_e
= m_entries
+ pos
;
498 case empty_entry_status
:
500 resize_base::notify_find_search_end();
501 _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(key
);)
506 case valid_entry_status
:
507 if (hash_eq_fn_base::operator()(PB_DS_V2F(p_e
->m_value
), key
))
509 resize_base::notify_find_search_end();
510 _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(key
);)
512 return pointer(&p_e
->m_value
);
515 case erased_entry_status
:
518 _GLIBCXX_DEBUG_ASSERT(0);
521 resize_base::notify_find_search_collision();
524 _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(key
);)
525 resize_base::notify_find_search_end();
530 find_key_pointer(const_key_reference key
, true_type
)
532 comp_hash pos_hash_pair
= ranged_probe_fn_base::operator()(key
);
534 resize_base::notify_find_search_start();
536 // Loop until entry is found or until all possible entries accessed.
537 for (i
= 0; i
< m_num_e
; ++i
)
539 const size_type pos
=
540 ranged_probe_fn_base::operator()(key
, pos_hash_pair
.second
, i
);
542 entry
* const p_e
= m_entries
+ pos
;
546 case empty_entry_status
:
548 resize_base::notify_find_search_end();
549 _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(key
);)
554 case valid_entry_status
:
555 if (hash_eq_fn_base::operator()(PB_DS_V2F(p_e
->m_value
),
557 key
, pos_hash_pair
.second
))
559 resize_base::notify_find_search_end();
560 _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(key
);)
561 return pointer(&p_e
->m_value
);
564 case erased_entry_status
:
567 _GLIBCXX_DEBUG_ASSERT(0);
570 resize_base::notify_find_search_collision();
573 _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(key
);)
574 resize_base::notify_find_search_end();
579 erase_imp(const_key_reference
, true_type
);
582 erase_imp(const_key_reference
, false_type
);
585 erase_entry(entry_pointer p_e
);
587 #ifdef PB_DS_DATA_TRUE_INDICATOR
589 inc_it_state(pointer
& r_p_value
, size_type
& r_pos
) const
590 { inc_it_state((const_mapped_pointer
& )r_p_value
, r_pos
); }
594 inc_it_state(const_pointer
& r_p_value
, size_type
& r_pos
) const
596 _GLIBCXX_DEBUG_ASSERT(r_p_value
!= NULL
);
597 for (++r_pos
; r_pos
< m_num_e
; ++r_pos
)
599 const_entry_pointer p_e
=& m_entries
[r_pos
];
600 if (p_e
->m_stat
== valid_entry_status
)
602 r_p_value
=& p_e
->m_value
;
610 get_start_it_state(const_pointer
& r_p_value
, size_type
& r_pos
) const
612 for (r_pos
= 0; r_pos
< m_num_e
; ++r_pos
)
614 const_entry_pointer p_e
= &m_entries
[r_pos
];
615 if (p_e
->m_stat
== valid_entry_status
)
617 r_p_value
= &p_e
->m_value
;
625 get_start_it_state(pointer
& r_p_value
, size_type
& r_pos
)
627 for (r_pos
= 0; r_pos
< m_num_e
; ++r_pos
)
629 entry_pointer p_e
= &m_entries
[r_pos
];
630 if (p_e
->m_stat
== valid_entry_status
)
632 r_p_value
= &p_e
->m_value
;
639 #ifdef _GLIBCXX_DEBUG
641 assert_entry_array_valid(const entry_array
, false_type
) const;
644 assert_entry_array_valid(const entry_array
, true_type
) const;
647 static entry_allocator s_entry_allocator
;
648 static iterator s_end_it
;
649 static const_iterator s_const_end_it
;
652 size_type m_num_used_e
;
653 entry_pointer m_entries
;
657 store_hash_ok
= !Store_Hash
658 || !is_same
<Hash_Fn
, pb_ds::null_hash_fn
>::value
661 PB_DS_STATIC_ASSERT(sth
, store_hash_ok
);
664 #include <ext/pb_ds/detail/gp_hash_table_map_/constructor_destructor_fn_imps.hpp>
665 #include <ext/pb_ds/detail/gp_hash_table_map_/find_fn_imps.hpp>
666 #include <ext/pb_ds/detail/gp_hash_table_map_/resize_fn_imps.hpp>
667 #include <ext/pb_ds/detail/gp_hash_table_map_/debug_fn_imps.hpp>
668 #include <ext/pb_ds/detail/gp_hash_table_map_/info_fn_imps.hpp>
669 #include <ext/pb_ds/detail/gp_hash_table_map_/policy_access_fn_imps.hpp>
670 #include <ext/pb_ds/detail/gp_hash_table_map_/erase_fn_imps.hpp>
671 #include <ext/pb_ds/detail/gp_hash_table_map_/iterator_fn_imps.hpp>
672 #include <ext/pb_ds/detail/gp_hash_table_map_/insert_fn_imps.hpp>
673 #include <ext/pb_ds/detail/gp_hash_table_map_/trace_fn_imps.hpp>
675 #undef PB_DS_CLASS_T_DEC
676 #undef PB_DS_CLASS_C_DEC
677 #undef PB_DS_HASH_EQ_FN_C_DEC
678 #undef PB_DS_RANGED_PROBE_FN_C_DEC
679 #undef PB_DS_TYPES_TRAITS_C_DEC
680 #undef PB_DS_MAP_DEBUG_BASE_C_DEC
681 #undef PB_DS_CLASS_NAME
684 #undef PB_DS_STATIC_ASSERT
686 } // namespace detail