+2006-09-27 Benjamin Kosnik <bkoz@redhat.com>
+
+ * include/ext/typelist.h (type_to_type): Remove.
+ * include/ext/throw_allocator.h (assert_allocatod): Remove.
+ (check_allocated(label)): New.
+ (print_to_string): Print numerical output correctly.
+
+ * testsuite/ext/pb_ds/example/hash_resize_neg.cc: Adjust line numbers.
+
+ * testsuite/util/regression/rand/priority_queue/detail/
+ operator_fn_imps.hpp: Set and clear label, throw
+ probability. Check only allocations of the marked label.
+ * testsuite/util/regression/rand/assoc/detail/
+ operator_fn_imps.hpp: Same.
+
+ * testsuite/performance/ext/pb_ds/text_find_timing.cc: Adjustments for
+ removal of type_to_type.
+ * testsuite/performance/ext/pb_ds/
+ hash_random_int_erase_mem_usage.cc: Same.
+ * testsuite/performance/ext/pb_ds/tree_text_insert_timing.cc: Same.
+ * testsuite/performance/ext/pb_ds/
+ priority_queue_text_push_timing.cc: Same.
+ * testsuite/performance/ext/pb_ds/
+ random_int_subscript_find_timing.cc: Same.
+ * testsuite/performance/ext/pb_ds/tree_split_join_timing.cc: Same.
+ * testsuite/performance/ext/pb_ds/random_int_find_timing.cc: Same.
+ * testsuite/performance/ext/pb_ds/
+ multimap_text_insert_mem_usage.hpp: Same.
+ * testsuite/performance/ext/pb_ds/
+ priority_queue_random_int_push_timing.cc: Same.
+ * testsuite/performance/ext/pb_ds/multimap_text_find_timing.hpp: Same.
+ * testsuite/performance/ext/pb_ds/
+ priority_queue_text_modify_timing.hpp: Same.
+ * testsuite/performance/ext/pb_ds/
+ tree_order_statistics_timing.cc: Same.
+ * testsuite/performance/ext/pb_ds/
+ priority_queue_text_push_pop_timing.cc: Same.
+ * testsuite/performance/ext/pb_ds/
+ priority_queue_text_join_timing.cc: Same.
+ * testsuite/performance/ext/pb_ds/
+ priority_queue_random_int_push_pop_timing.cc: Same.
+ * testsuite/performance/ext/pb_ds/
+ random_int_subscript_insert_timing.cc: Same.
+ * testsuite/performance/ext/pb_ds/tree_text_lor_find_timing.cc: Same.
+ * testsuite/performance/ext/pb_ds/
+ multimap_text_insert_timing.hpp: Same.
+ * testsuite/performance/ext/pb_ds/
+ priority_queue_text_pop_mem_usage.cc: Same.
+ * testsuite/performance/ext/pb_ds/
+ hash_zlob_random_int_find_timing.cc: Same.
+ * testsuite/util/regression/trait/assoc/type_trait.hpp: Same.
+ * testsuite/util/regression/rand/priority_queue/
+ rand_regression_test.hpp: Same.
+ * testsuite/util/regression/rand/assoc/detail/
+ constructor_destructor_fn_imps.hpp: Same.
+ * testsuite/util/regression/rand/assoc/detail/insert_fn_imps.hpp: Same.
+ * testsuite/util/regression/rand/assoc/rand_regression_test.hpp: Same.
+ * testsuite/util/regression/rand/assoc/
+ container_rand_regression_test.hpp: Same.
+ * testsuite/util/regression/assoc/common_type.hpp: Same.
+ * testsuite/util/regression/basic_type.hpp: Same.
+ * testsuite/util/common_type/assoc/common_type.hpp: Same.
+ * testsuite/util/common_type/assoc/string_form.hpp: Same.
+ * testsuite/util/common_type/assoc/template_policy.hpp: Same.
+ * testsuite/util/common_type/assoc/native_set.hpp: Same.
+ * testsuite/util/performance/priority_queue/mem_usage/
+ pop_test.hpp: Same.
+ * testsuite/util/performance/priority_queue/timing/
+ push_pop_test.hpp: Same.
+ * testsuite/util/performance/priority_queue/timing/join_test.hpp: Same.
+ * testsuite/util/performance/priority_queue/timing/push_test.hpp: Same.
+ * testsuite/util/performance/priority_queue/timing/
+ modify_test.hpp: Same.
+ * testsuite/util/performance/assoc/mem_usage/
+ multimap_insert_test.hpp: Same.
+ * testsuite/util/performance/assoc/mem_usage/erase_test.hpp: Same.
+ * testsuite/util/performance/assoc/timing/
+ multimap_insert_test.hpp: Same.
+ * testsuite/util/performance/assoc/timing/
+ subscript_find_test.hpp: Same.
+ * testsuite/util/performance/assoc/timing/find_test.hpp: Same.
+ * testsuite/util/performance/assoc/timing/
+ subscript_insert_test.hpp: Same.
+ * testsuite/util/performance/assoc/timing/insert_test.hpp: Same.
+ * testsuite/util/performance/assoc/timing/
+ tree_order_statistics_test.hpp: Same.
+ * testsuite/util/performance/assoc/timing/multimap_find_test.hpp: Same.
+ * testsuite/util/performance/assoc/timing/
+ tree_split_join_test.hpp: Same.
+ * testsuite/util/performance/assoc/multimap_common_type.hpp: Same.
+ * testsuite/util/testsuite_common_types.h: Same.
+
+ * include/ext/pb_ds/detail/cc_hash_table_map_/
+ constructor_destructor_no_store_hash_fn_imps.hpp: Typedef
+ normalization, consistency in member names between cc and gp hash
+ tables, formatting fixes.
+ * include/ext/pb_ds/detail/cc_hash_table_map_/
+ erase_store_hash_fn_imps.hpp: Same.
+ * include/ext/pb_ds/detail/cc_hash_table_map_/
+ insert_no_store_hash_fn_imps.hpp: Same.
+ * include/ext/pb_ds/detail/cc_hash_table_map_/
+ constructor_destructor_store_hash_fn_imps.hpp: Same.
+ * include/ext/pb_ds/detail/cc_hash_table_map_/
+ insert_store_hash_fn_imps.hpp: Same.
+ * include/ext/pb_ds/detail/cc_hash_table_map_/debug_fn_imps.hpp: Same.
+ * include/ext/pb_ds/detail/cc_hash_table_map_/trace_fn_imps.hpp: Same.
+ * include/ext/pb_ds/detail/cc_hash_table_map_/erase_fn_imps.hpp: Same.
+ * include/ext/pb_ds/detail/cc_hash_table_map_/cc_ht_map_.hpp: Same.
+ * include/ext/pb_ds/detail/cc_hash_table_map_/resize_fn_imps.hpp: Same.
+ * include/ext/pb_ds/detail/cc_hash_table_map_/
+ constructor_destructor_fn_imps.hpp: Same.
+ * include/ext/pb_ds/detail/cc_hash_table_map_/
+ erase_no_store_hash_fn_imps.hpp: Same.
+ * include/ext/pb_ds/detail/gp_hash_table_map_/
+ constructor_destructor_no_store_hash_fn_imps.hpp: Same.
+ * include/ext/pb_ds/detail/gp_hash_table_map_/
+ erase_store_hash_fn_imps.hpp: Same.
+ * include/ext/pb_ds/detail/gp_hash_table_map_/
+ insert_no_store_hash_fn_imps.hpp: Same.
+ * include/ext/pb_ds/detail/gp_hash_table_map_/find_fn_imps.hpp: Same.
+ * include/ext/pb_ds/detail/gp_hash_table_map_/
+ constructor_destructor_store_hash_fn_imps.hpp: Same.
+ * include/ext/pb_ds/detail/gp_hash_table_map_/gp_ht_map_.hpp: Same.
+ * include/ext/pb_ds/detail/gp_hash_table_map_/
+ insert_store_hash_fn_imps.hpp: Same.
+ * include/ext/pb_ds/detail/gp_hash_table_map_/debug_fn_imps.hpp: Same.
+ * include/ext/pb_ds/detail/gp_hash_table_map_/trace_fn_imps.hpp: Same.
+ * include/ext/pb_ds/detail/gp_hash_table_map_/erase_fn_imps.hpp: Same.
+ * include/ext/pb_ds/detail/gp_hash_table_map_/resize_fn_imps.hpp: Same.
+ * include/ext/pb_ds/detail/gp_hash_table_map_/
+ constructor_destructor_fn_imps.hpp: Same.
+ * include/ext/pb_ds/detail/gp_hash_table_map_/
+ erase_no_store_hash_fn_imps.hpp: Same.
+
+ * include/ext/pb_ds/assoc_container.hpp: Formatting fixes.
+ * include/ext/pb_ds/detail/resize_policy/
+ hash_prime_size_policy_imp.hpp: Same.
+ * include/ext/pb_ds/detail/resize_policy/
+ hash_standard_resize_policy_imp.hpp: Same.
+ * include/ext/pb_ds/detail/types_traits.hpp: Same.
+ * include/ext/pb_ds/detail/constructors_destructor_fn_imps.hpp: Same.
+ * include/ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp: Same.
+ * include/ext/pb_ds/detail/hash_fn/ranged_probe_fn.hpp: Same.
+ * include/ext/pb_ds/detail/hash_fn/
+ direct_mod_range_hashing_imp.hpp: Same.
+ * include/ext/pb_ds/detail/hash_fn/mask_based_range_hashing.hpp: Same.
+ * include/ext/pb_ds/detail/hash_fn/
+ direct_mask_range_hashing_imp.hpp: Same.
+
2006-09-27 Paolo Carlini <pcarlini@suse.de>
PR libstdc++/29217
// Constructor taking some policy objects. r_hash_fn will be
// copied by the Hash_Fn object of the container object.
cc_hash_table(const hash_fn& h)
- : base_type(h) { }
+ : base_type(h) { }
// Constructor taking some policy objects. r_hash_fn will be
// copied by the hash_fn object of the container object, and
// r_eq_fn will be copied by the eq_fn object of the container
// object.
cc_hash_table(const hash_fn& h, const eq_fn& e)
- : base_type(h, e) { }
+ : base_type(h, e) { }
// Constructor taking some policy objects. r_hash_fn will be
// copied by the hash_fn object of the container object, r_eq_fn
// r_comb_hash_fn will be copied by the comb_hash_fn object of the
// container object.
cc_hash_table(const hash_fn& h, const eq_fn& e, const comb_hash_fn& ch)
- : base_type(h, e, ch) { }
+ : base_type(h, e, ch) { }
// Constructor taking some policy objects. r_hash_fn will be
// copied by the hash_fn object of the container object, r_eq_fn
// resize_policy object of the container object.
cc_hash_table(const hash_fn& h, const eq_fn& e, const comb_hash_fn& ch,
const resize_policy& rp)
- : base_type(h, e, ch, rp) { }
+ : base_type(h, e, ch, rp) { }
// Constructor taking __iterators to a range of value_types. The
// value_types between first_it and last_it will be inserted into
// last_it will be inserted into the container object.
template<typename It>
cc_hash_table(It first, It last, const hash_fn& h)
- : base_type(h)
+ : base_type(h)
{ copy_from_range(first, last); }
// Constructor taking __iterators to a range of value_types and
// object.
template<typename It>
cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e)
- : base_type(h, e)
+ : base_type(h, e)
{ copy_from_range(first, last); }
// Constructor taking __iterators to a range of value_types and
template<typename It>
cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
const comb_hash_fn& ch)
- : base_type(h, e, ch)
+ : base_type(h, e, ch)
{ copy_from_range(first, last); }
// Constructor taking __iterators to a range of value_types and
template<typename It>
cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
const comb_hash_fn& ch, const resize_policy& rp)
- : base_type(h, e, ch, rp)
+ : base_type(h, e, ch, rp)
{ copy_from_range(first, last); }
cc_hash_table(const cc_hash_table& other)
- : base_type((const base_type&)other)
+ : base_type((const base_type&)other)
{ }
virtual
cc_hash_table&
operator=(const cc_hash_table& other)
{
- if (this !=& other)
+ if (this != &other)
{
cc_hash_table tmp(other);
swap(tmp);
// Constructor taking some policy objects. r_hash_fn will be
// copied by the hash_fn object of the container object.
gp_hash_table(const hash_fn& h)
- : base_type(h) { }
+ : base_type(h) { }
// Constructor taking some policy objects. r_hash_fn will be
// copied by the hash_fn object of the container object, and
// r_eq_fn will be copied by the eq_fn object of the container
// object.
gp_hash_table(const hash_fn& h, const eq_fn& e)
- : base_type(h, e) { }
+ : base_type(h, e) { }
// Constructor taking some policy objects. r_hash_fn will be
// copied by the hash_fn object of the container object, r_eq_fn
// r_comb_probe_fn will be copied by the comb_probe_fn object of
// the container object.
gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp)
- : base_type(h, e, cp) { }
+ : base_type(h, e, cp) { }
// Constructor taking some policy objects. r_hash_fn will be
// copied by the hash_fn object of the container object, r_eq_fn
// probe_fn object of the container object.
gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp,
const probe_fn& p)
- : base_type(h, e, cp, p) { }
+ : base_type(h, e, cp, p) { }
// Constructor taking some policy objects. r_hash_fn will be
// copied by the hash_fn object of the container object, r_eq_fn
// copied by the Resize_Policy object of the container object.
gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp,
const probe_fn& p, const resize_policy& rp)
- : base_type(h, e, cp, p, rp) { }
+ : base_type(h, e, cp, p, rp) { }
// Constructor taking __iterators to a range of value_types. The
// value_types between first_it and last_it will be inserted into
// will be copied by the hash_fn object of the container object.
template<typename It>
gp_hash_table(It first, It last, const hash_fn& h)
- : base_type(h)
+ : base_type(h)
{ base_type::copy_from_range(first, last); }
// Constructor taking __iterators to a range of value_types and
// object.
template<typename It>
gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e)
- : base_type(h, e)
+ : base_type(h, e)
{ base_type::copy_from_range(first, last); }
// Constructor taking __iterators to a range of value_types and
template<typename It>
gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
const comb_probe_fn& cp)
- : base_type(h, e, cp)
+ : base_type(h, e, cp)
{ base_type::copy_from_range(first, last); }
// Constructor taking __iterators to a range of value_types and
template<typename It>
gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
const comb_probe_fn& cp, const probe_fn& p)
- : base_type(h, e, cp, p)
+ : base_type(h, e, cp, p)
{ base_type::copy_from_range(first, last); }
// Constructor taking __iterators to a range of value_types and
gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
const comb_probe_fn& cp, const probe_fn& p,
const resize_policy& rp)
- : base_type(h, e, cp, p, rp)
+ : base_type(h, e, cp, p, rp)
{ base_type::copy_from_range(first, last); }
gp_hash_table(const gp_hash_table& other)
- : base_type((const base_type&)other)
+ : base_type((const base_type&)other)
{ }
virtual
gp_hash_table&
operator=(const gp_hash_table& other)
{
- if (this !=& other)
+ if (this != &other)
{
gp_hash_table tmp(other);
swap(tmp);
#undef PB_DS_BASE_C_DEC
-#define PB_DS_BASE_C_DEC \
+#define PB_DS_BASE_C_DEC \
container_base<Key, Mapped, Tag, Policy_Tl, Allocator>
// An abstract basic tree-like (tree, trie) associative container.
#undef PB_DS_BASE_C_DEC
-#define PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC \
+#define PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC \
detail::tree_traits<Key, Mapped,Cmp_Fn,Node_Update,Tag, Allocator>
-#define PB_DS_BASE_C_DEC \
+#define PB_DS_BASE_C_DEC \
basic_tree<Key,Mapped,Tag,typename PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC::node_update, \
typename __gnu_cxx::typelist::create2<Cmp_Fn, PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC >::type, Allocator>
// Constructor taking some policy objects. r_cmp_fn will be copied
// by the Cmp_Fn object of the container object.
tree(const cmp_fn& c)
- : base_type(c) { }
+ : base_type(c) { }
// Constructor taking __iterators to a range of value_types. The
// value_types between first_it and last_it will be inserted into
{ base_type::copy_from_range(first, last); }
tree(const tree& other)
- : base_type((const base_type&)other) { }
+ : base_type((const base_type&)other) { }
virtual
~tree() { }
tree&
operator=(const tree& other)
{
- if (this !=& other)
+ if (this != &other)
{
tree tmp(other);
swap(tmp);
#undef PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC
-#define PB_DS_TRIE_NODE_AND_ITS_TRAITS \
+#define PB_DS_TRIE_NODE_AND_ITS_TRAITS \
detail::trie_traits<Key,Mapped,E_Access_Traits,Node_Update,Tag,Allocator>
-#define PB_DS_BASE_C_DEC \
+#define PB_DS_BASE_C_DEC \
basic_tree<Key,Mapped,Tag, typename PB_DS_TRIE_NODE_AND_ITS_TRAITS::node_update, \
typename __gnu_cxx::typelist::create2<E_Access_Traits, PB_DS_TRIE_NODE_AND_ITS_TRAITS >::type, Allocator>
// be copied by the E_Access_Traits object of the container
// object.
trie(const e_access_traits& t)
- : base_type(t) { }
+ : base_type(t) { }
// Constructor taking __iterators to a range of value_types. The
// value_types between first_it and last_it will be inserted into
// last_it will be inserted into the container object.
template<typename It>
trie(It first, It last, const e_access_traits& t)
- : base_type(t)
+ : base_type(t)
{ base_type::copy_from_range(first, last); }
trie(const trie& other)
- : base_type((const base_type&)other) { }
+ : base_type((const base_type&)other) { }
virtual
~trie() { }
trie&
operator=(const trie& other)
{
- if (this !=& other)
+ if (this != &other)
{
trie tmp(other);
swap(tmp);
{ base_type::copy_from_range(first, last); }
list_update(const list_update& other)
- : base_type((const base_type&)other) { }
+ : base_type((const base_type&)other) { }
virtual
~list_update() { }
{
#define PB_DS_CLASS_T_DEC \
- template<typename Key, typename Mapped, class Hash_Fn, \
- class Eq_Fn, class Allocator, bool Store_Hash, \
- class Comb_Hash_Fn, class Resize_Policy>
+ template<typename Key, typename Mapped, typename Hash_Fn, \
+ typename Eq_Fn, typename Allocator, bool Store_Hash, \
+ typename Comb_Hash_Fn, typename Resize_Policy>
#ifdef PB_DS_DATA_TRUE_INDICATOR
#define PB_DS_CLASS_NAME cc_ht_map_data_
// <011i$i0|\|-<|-|4i|\|i|\|g |-|4$|-| 74813.
template<typename Key,
typename Mapped,
- class Hash_Fn,
- class Eq_Fn,
- class Allocator,
+ typename Hash_Fn,
+ typename Eq_Fn,
+ typename Allocator,
bool Store_Hash,
- class Comb_Hash_Fn,
- class Resize_Policy >
+ typename Comb_Hash_Fn,
+ typename Resize_Policy >
class PB_DS_CLASS_NAME:
#ifdef _GLIBCXX_DEBUG
protected PB_DS_MAP_DEBUG_BASE_C_DEC,
public PB_DS_RANGED_HASH_FN_C_DEC,
public PB_DS_TYPES_TRAITS_C_DEC
{
-
private:
- typedef typename PB_DS_TYPES_TRAITS_C_DEC::comp_hash comp_hash;
-
- struct entry : public PB_DS_TYPES_TRAITS_C_DEC::stored_value_type
+ typedef PB_DS_TYPES_TRAITS_C_DEC traits_base;
+ typedef typename traits_base::comp_hash comp_hash;
+ typedef typename traits_base::value_type value_type_;
+ typedef typename traits_base::pointer pointer_;
+ typedef typename traits_base::const_pointer const_pointer_;
+ typedef typename traits_base::reference reference_;
+ typedef typename traits_base::const_reference const_reference_;
+ typedef typename traits_base::store_extra_false_type store_hash_false_type;
+ typedef typename traits_base::store_extra_true_type store_hash_true_type;
+ typedef typename traits_base::no_throw_copies_false_type no_throw_copies_false_type;
+ typedef typename traits_base::no_throw_copies_true_type no_throw_copies_true_type;
+
+ struct entry : public traits_base::stored_value_type
{
typename Allocator::template rebind<entry>::other::pointer m_p_next;
};
- typedef
- typename Allocator::template rebind<entry>::other
- entry_allocator;
+ typedef cond_dealtor<entry, Allocator> cond_dealtor_t;
+ typedef typename Allocator::template rebind<entry>::other entry_allocator;
typedef typename entry_allocator::pointer entry_pointer;
-
typedef typename entry_allocator::const_pointer const_entry_pointer;
-
typedef typename entry_allocator::reference entry_reference;
+ typedef typename entry_allocator::const_reference const_entry_reference;
- typedef
- typename entry_allocator::const_reference
- const_entry_reference;
-
- typedef
- typename Allocator::template rebind<entry_pointer>::other
- entry_pointer_allocator;
-
+ typedef typename Allocator::template rebind<entry_pointer>::other entry_pointer_allocator;
typedef typename entry_pointer_allocator::pointer entry_pointer_array;
- typedef typename PB_DS_TYPES_TRAITS_C_DEC::value_type value_type_;
-
- typedef typename PB_DS_TYPES_TRAITS_C_DEC::pointer pointer_;
-
- typedef
- typename PB_DS_TYPES_TRAITS_C_DEC::const_pointer
- const_pointer_;
-
- typedef typename PB_DS_TYPES_TRAITS_C_DEC::reference reference_;
+ typedef PB_DS_RANGED_HASH_FN_C_DEC ranged_hash_fn_base;
+ typedef PB_DS_HASH_EQ_FN_C_DEC hash_eq_fn_base;
+ typedef Resize_Policy resize_base;
- typedef
- typename PB_DS_TYPES_TRAITS_C_DEC::const_reference
- const_reference_;
+#ifdef _GLIBCXX_DEBUG
+ typedef PB_DS_MAP_DEBUG_BASE_C_DEC map_debug_base;
+#endif
#define PB_DS_GEN_POS std::pair<entry_pointer, typename Allocator::size_type>
#undef PB_DS_GEN_POS
public:
-
+ typedef Allocator allocator;
typedef typename Allocator::size_type size_type;
-
typedef typename Allocator::difference_type difference_type;
-
typedef Hash_Fn hash_fn;
-
typedef Eq_Fn eq_fn;
-
- typedef Allocator allocator;
-
typedef Comb_Hash_Fn comb_hash_fn;
-
typedef Resize_Policy resize_policy;
enum
store_hash = Store_Hash
};
- typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_type key_type;
-
- typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_pointer key_pointer;
-
- typedef
- typename PB_DS_TYPES_TRAITS_C_DEC::const_key_pointer
- const_key_pointer;
-
- typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_reference key_reference;
-
- typedef
- typename PB_DS_TYPES_TRAITS_C_DEC::const_key_reference
- const_key_reference;
-
- typedef typename PB_DS_TYPES_TRAITS_C_DEC::mapped_type mapped_type;
-
- typedef
- typename PB_DS_TYPES_TRAITS_C_DEC::mapped_pointer
- mapped_pointer;
-
- typedef
- typename PB_DS_TYPES_TRAITS_C_DEC::const_mapped_pointer
- const_mapped_pointer;
-
- typedef
- typename PB_DS_TYPES_TRAITS_C_DEC::mapped_reference
- mapped_reference;
-
- typedef
- typename PB_DS_TYPES_TRAITS_C_DEC::const_mapped_reference
- const_mapped_reference;
-
- typedef typename PB_DS_TYPES_TRAITS_C_DEC::value_type value_type;
-
- typedef typename PB_DS_TYPES_TRAITS_C_DEC::pointer pointer;
-
- typedef typename PB_DS_TYPES_TRAITS_C_DEC::const_pointer const_pointer;
-
- typedef typename PB_DS_TYPES_TRAITS_C_DEC::reference reference;
-
- typedef
- typename PB_DS_TYPES_TRAITS_C_DEC::const_reference
- const_reference;
+ typedef typename traits_base::key_type key_type;
+ typedef typename traits_base::key_pointer key_pointer;
+ typedef typename traits_base::const_key_pointer const_key_pointer;
+ typedef typename traits_base::key_reference key_reference;
+ typedef typename traits_base::const_key_reference const_key_reference;
+ typedef typename traits_base::mapped_type mapped_type;
+ typedef typename traits_base::mapped_pointer mapped_pointer;
+ typedef typename traits_base::const_mapped_pointer const_mapped_pointer;
+ typedef typename traits_base::mapped_reference mapped_reference;
+ typedef typename traits_base::const_mapped_reference const_mapped_reference;
+ typedef typename traits_base::value_type value_type;
+ typedef typename traits_base::pointer pointer;
+ typedef typename traits_base::const_pointer const_pointer;
+ typedef typename traits_base::reference reference;
+ typedef typename traits_base::const_reference const_reference;
#ifdef PB_DS_DATA_TRUE_INDICATOR
typedef point_iterator_ point_iterator;
typedef const_iterator_ const_iterator;
- public:
-
PB_DS_CLASS_NAME();
- PB_DS_CLASS_NAME(const Hash_Fn& r_hash_fn);
+ PB_DS_CLASS_NAME(const Hash_Fn&);
- PB_DS_CLASS_NAME(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn);
+ PB_DS_CLASS_NAME(const Hash_Fn&, const Eq_Fn&);
- PB_DS_CLASS_NAME(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn, const Comb_Hash_Fn& r_comb_hash_fn);
+ PB_DS_CLASS_NAME(const Hash_Fn&, const Eq_Fn&, const Comb_Hash_Fn&);
- PB_DS_CLASS_NAME(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn, const Comb_Hash_Fn& r_comb_hash_fn, const Resize_Policy& r_resize_policy);
+ PB_DS_CLASS_NAME(const Hash_Fn&, const Eq_Fn&, const Comb_Hash_Fn&,
+ const Resize_Policy&);
- PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC& other);
+ PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC&);
virtual
~PB_DS_CLASS_NAME();
void
- swap(PB_DS_CLASS_C_DEC& other);
+ swap(PB_DS_CLASS_C_DEC&);
template<typename It>
void
- copy_from_range(It first_it, It last_it);
+ copy_from_range(It, It);
void
initialize();
inline std::pair<point_iterator, bool>
insert(const_reference r_val)
- {
- return insert_imp(r_val, traits_base::m_store_extra_indicator);
- }
+ { return insert_imp(r_val, traits_base::m_store_extra_indicator); }
inline mapped_reference
operator[](const_key_reference r_key)
}
inline point_iterator
- find(const_key_reference r_key);
+ find(const_key_reference);
inline const_point_iterator
- find(const_key_reference r_key) const;
+ find(const_key_reference) const;
inline point_iterator
find_end();
find_end() const;
inline bool
- erase(const_key_reference r_key);
+ erase(const_key_reference);
template<typename Pred>
inline size_type
- erase_if(Pred pred);
+ erase_if(Pred);
void
clear();
#endif
private:
- typedef PB_DS_TYPES_TRAITS_C_DEC traits_base;
-
- typedef PB_DS_RANGED_HASH_FN_C_DEC ranged_hash_fn_base;
-
- typedef PB_DS_HASH_EQ_FN_C_DEC hash_eq_fn_base;
-
- typedef Resize_Policy resize_base;
-
-#ifdef _GLIBCXX_DEBUG
- typedef PB_DS_MAP_DEBUG_BASE_C_DEC map_debug_base;
-#endif
-
- typedef
- typename PB_DS_TYPES_TRAITS_C_DEC::store_extra_false_type
- store_hash_false_type;
-
- typedef
- typename PB_DS_TYPES_TRAITS_C_DEC::store_extra_true_type
- store_hash_true_type;
-
- typedef
- typename PB_DS_TYPES_TRAITS_C_DEC::
- no_throw_copies_false_type
- no_throw_copies_false_type;
-
- typedef
- typename PB_DS_TYPES_TRAITS_C_DEC::
- no_throw_copies_true_type
- no_throw_copies_true_type;
-
- private:
-
void
deallocate_all();
resize_imp_no_exceptions_reassign_pointer(entry_pointer, entry_pointer_array, store_hash_false_type);
inline entry_pointer
- resize_imp_no_exceptions_reassign_pointer(entry_pointer p_e, entry_pointer_array a_p_entries_resized, store_hash_true_type);
+ resize_imp_no_exceptions_reassign_pointer(entry_pointer, entry_pointer_array, store_hash_true_type);
void
- deallocate_links_in_list(entry_pointer p_e);
+ deallocate_links_in_list(entry_pointer);
inline entry_pointer
- get_entry(const_reference r_val, no_throw_copies_false_type);
+ get_entry(const_reference, no_throw_copies_false_type);
inline entry_pointer
- get_entry(const_reference r_val, no_throw_copies_true_type);
+ get_entry(const_reference, no_throw_copies_true_type);
inline void
- rels_entry(entry_pointer p_e);
+ rels_entry(entry_pointer);
#ifdef PB_DS_DATA_TRUE_INDICATOR
inline mapped_reference
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
const size_type pos = ranged_hash_fn_base::operator()(r_key);
- entry_pointer p_e = m_a_p_entries[pos];
+ entry_pointer p_e = m_entries[pos];
resize_base::notify_insert_search_start();
while (p_e != NULL
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
comp_hash pos_hash_pair = ranged_hash_fn_base::operator()(r_key);
- entry_pointer p_e = m_a_p_entries[pos_hash_pair.first];
+ entry_pointer p_e = m_entries[pos_hash_pair.first];
resize_base::notify_insert_search_start();
while (p_e != NULL &&
!hash_eq_fn_base::operator()(p_e->m_value.first, p_e->m_hash, r_key, pos_hash_pair.second))
}
_GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key);)
- return insert_new_imp(value_type(r_key, mapped_type()), pos_hash_pair)->second;
+ return insert_new_imp(value_type(r_key, mapped_type()),
+ pos_hash_pair)->second;
}
#endif
inline std::pair<point_iterator, bool>
- insert_imp(const_reference r_val, store_hash_false_type);
+ insert_imp(const_reference, store_hash_false_type);
inline std::pair<point_iterator, bool>
- insert_imp(const_reference r_val, store_hash_true_type);
+ insert_imp(const_reference, store_hash_true_type);
inline pointer
insert_new_imp(const_reference r_val, size_type pos)
pos = ranged_hash_fn_base::operator()(PB_DS_V2F(r_val));
// Following lines might throw an exception.
- entry_pointer p_e = get_entry(r_val, PB_DS_TYPES_TRAITS_C_DEC::m_no_throw_copies_indicator);
+ entry_pointer p_e = get_entry(r_val, traits_base::m_no_throw_copies_indicator);
// At this point no exceptions can be thrown.
- p_e->m_p_next = m_a_p_entries[pos];
- m_a_p_entries[pos] = p_e;
+ p_e->m_p_next = m_entries[pos];
+ m_entries[pos] = p_e;
resize_base::notify_inserted(++m_num_used_e);
_GLIBCXX_DEBUG_ONLY(map_debug_base::insert_new(PB_DS_V2F(r_val));)
if (do_resize_if_needed())
r_pos_hash_pair = ranged_hash_fn_base::operator()(PB_DS_V2F(r_val));
- entry_pointer p_e = get_entry(r_val, PB_DS_TYPES_TRAITS_C_DEC::m_no_throw_copies_indicator);
+ entry_pointer p_e = get_entry(r_val, traits_base::m_no_throw_copies_indicator);
// At this point no exceptions can be thrown.
p_e->m_hash = r_pos_hash_pair.second;
- p_e->m_p_next = m_a_p_entries[r_pos_hash_pair.first];
- m_a_p_entries[r_pos_hash_pair.first] = p_e;
+ p_e->m_p_next = m_entries[r_pos_hash_pair.first];
+ m_entries[r_pos_hash_pair.first] = p_e;
resize_base::notify_inserted(++m_num_used_e);
_GLIBCXX_DEBUG_ONLY(map_debug_base::insert_new(PB_DS_V2F(r_val));)
_GLIBCXX_DEBUG_ONLY(assert_valid();)
inline pointer
find_key_pointer(const_key_reference r_key, store_hash_false_type)
{
- entry_pointer p_e = m_a_p_entries[ranged_hash_fn_base::operator()(r_key)];
+ entry_pointer p_e = m_entries[ranged_hash_fn_base::operator()(r_key)];
resize_base::notify_find_search_start();
while (p_e != NULL &&
!hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), r_key))
find_key_pointer(const_key_reference r_key, store_hash_true_type)
{
comp_hash pos_hash_pair = ranged_hash_fn_base::operator()(r_key);
- entry_pointer p_e = m_a_p_entries[pos_hash_pair.first];
+ entry_pointer p_e = m_entries[pos_hash_pair.first];
resize_base::notify_find_search_start();
while (p_e != NULL &&
!hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value),
}
inline bool
- erase_in_pos_imp(const_key_reference r_key, size_type pos);
+ erase_in_pos_imp(const_key_reference, size_type);
inline bool
- erase_in_pos_imp(const_key_reference r_key, const comp_hash& r_pos_hash_pair);
+ erase_in_pos_imp(const_key_reference, const comp_hash&);
inline void
- erase_entry_pointer(entry_pointer& r_p_e);
+ erase_entry_pointer(entry_pointer&);
#ifdef PB_DS_DATA_TRUE_INDICATOR
void
- inc_it_state(pointer& r_p_value, std::pair<entry_pointer, size_type>& r_pos) const
+ inc_it_state(pointer& r_p_value,
+ std::pair<entry_pointer, size_type>& r_pos) const
{
inc_it_state((const_mapped_pointer& )r_p_value, r_pos);
}
r_pos.first = r_pos.first->m_p_next;
if (r_pos.first != NULL)
{
- r_p_value =& r_pos.first->m_value;
+ r_p_value = &r_pos.first->m_value;
return;
}
- for (++r_pos.second; r_pos.second < m_num_e_p; ++r_pos.second)
- if (m_a_p_entries[r_pos.second] != NULL)
+ for (++r_pos.second; r_pos.second < m_num_e; ++r_pos.second)
+ if (m_entries[r_pos.second] != NULL)
{
- r_pos.first = m_a_p_entries[r_pos.second];
- r_p_value =& r_pos.first->m_value;
+ r_pos.first = m_entries[r_pos.second];
+ r_p_value = &r_pos.first->m_value;
return;
}
r_p_value = NULL;
get_start_it_state(pointer& r_p_value,
std::pair<entry_pointer, size_type>& r_pos) const
{
- for (r_pos.second = 0; r_pos.second < m_num_e_p; ++r_pos.second)
- if (m_a_p_entries[r_pos.second] != NULL)
+ for (r_pos.second = 0; r_pos.second < m_num_e; ++r_pos.second)
+ if (m_entries[r_pos.second] != NULL)
{
- r_pos.first = m_a_p_entries[r_pos.second];
- r_p_value =& r_pos.first->m_value;
+ r_pos.first = m_entries[r_pos.second];
+ r_p_value = &r_pos.first->m_value;
return;
}
r_p_value = NULL;
#endif
private:
- static entry_allocator s_entry_allocator;
-
- static entry_pointer_allocator s_entry_pointer_allocator;
-
- typedef cond_dealtor< entry, Allocator> cond_dealtor_t;
-
- entry_pointer_array m_a_p_entries;
-
- size_type m_num_e_p;
-
- size_type m_num_used_e;
-
#ifdef PB_DS_DATA_TRUE_INDICATOR
friend class iterator_;
#endif
friend class const_iterator_;
- static iterator s_end_it;
+ static entry_allocator s_entry_allocator;
+ static entry_pointer_allocator s_entry_pointer_allocator;
+ static iterator s_end_it;
+ static const_iterator s_const_end_it;
+ static point_iterator s_find_end_it;
+ static const_point_iterator s_const_find_end_it;
- static const_iterator s_const_end_it;
-
- static point_iterator s_find_end_it;
-
- static const_point_iterator s_const_find_end_it;
+ size_type m_num_e;
+ size_type m_num_used_e;
+ entry_pointer_array m_entries;
enum
{
#undef PB_DS_TYPES_TRAITS_C_DEC
#undef PB_DS_MAP_DEBUG_BASE_C_DEC
#undef PB_DS_CLASS_NAME
-
#undef PB_DS_V2F
#undef PB_DS_V2S
-
#undef PB_DS_STATIC_ASSERT
} // namespace detail
PB_DS_CLASS_C_DEC::
PB_DS_CLASS_NAME() :
ranged_hash_fn_base(resize_base::get_nearest_larger_size(1)),
- m_a_p_entries(s_entry_pointer_allocator.allocate(resize_base::get_nearest_larger_size(1))),
- m_num_e_p(resize_base::get_nearest_larger_size(1)),
- m_num_used_e(0)
+ m_num_e(resize_base::get_nearest_larger_size(1)), m_num_used_e(0),
+ m_entries(s_entry_pointer_allocator.allocate(m_num_e))
{
initialize();
_GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();)
PB_DS_CLASS_C_DEC::
PB_DS_CLASS_NAME(const Hash_Fn& r_hash_fn) :
ranged_hash_fn_base(resize_base::get_nearest_larger_size(1), r_hash_fn),
- m_a_p_entries(s_entry_pointer_allocator.allocate(resize_base::get_nearest_larger_size(1))),
- m_num_e_p(resize_base::get_nearest_larger_size(1)),
- m_num_used_e(0)
+ m_num_e(resize_base::get_nearest_larger_size(1)), m_num_used_e(0),
+ m_entries(s_entry_pointer_allocator.allocate(m_num_e))
{
initialize();
_GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();)
PB_DS_CLASS_NAME(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn) :
PB_DS_HASH_EQ_FN_C_DEC(r_eq_fn),
ranged_hash_fn_base(resize_base::get_nearest_larger_size(1), r_hash_fn),
- m_a_p_entries(s_entry_pointer_allocator.allocate(resize_base::get_nearest_larger_size(1))),
- m_num_e_p(resize_base::get_nearest_larger_size(1)),
- m_num_used_e(0)
+ m_num_e(resize_base::get_nearest_larger_size(1)), m_num_used_e(0),
+ m_entries(s_entry_pointer_allocator.allocate(m_num_e))
{
- std::fill(m_a_p_entries, m_a_p_entries + m_num_e_p, (entry_pointer)NULL);
+ std::fill(m_entries, m_entries + m_num_e, (entry_pointer)NULL);
Resize_Policy::notify_cleared();
- ranged_hash_fn_base::notify_resized(m_num_e_p);
+ ranged_hash_fn_base::notify_resized(m_num_e);
_GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();)
}
PB_DS_CLASS_NAME(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn, const Comb_Hash_Fn& r_comb_hash_fn) :
PB_DS_HASH_EQ_FN_C_DEC(r_eq_fn),
ranged_hash_fn_base(resize_base::get_nearest_larger_size(1),
- r_hash_fn,
- r_comb_hash_fn),
- m_a_p_entries(s_entry_pointer_allocator.allocate(resize_base::get_nearest_larger_size(1))),
- m_num_e_p(resize_base::get_nearest_larger_size(1)),
- m_num_used_e(0)
+ r_hash_fn, r_comb_hash_fn),
+ m_num_e(resize_base::get_nearest_larger_size(1)), m_num_used_e(0),
+ m_entries(s_entry_pointer_allocator.allocate(m_num_e))
{
initialize();
_GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();)
PB_DS_HASH_EQ_FN_C_DEC(r_eq_fn),
Resize_Policy(r_resize_policy),
ranged_hash_fn_base(resize_base::get_nearest_larger_size(1),
- r_hash_fn,
- r_comb_hash_fn),
- m_a_p_entries(s_entry_pointer_allocator.allocate(resize_base::get_nearest_larger_size(1))),
- m_num_e_p(resize_base::get_nearest_larger_size(1)),
- m_num_used_e(0)
+ r_hash_fn, r_comb_hash_fn),
+ m_num_e(resize_base::get_nearest_larger_size(1)), m_num_used_e(0),
+ m_entries(s_entry_pointer_allocator.allocate(m_num_e))
{
initialize();
_GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();)
map_debug_base(other),
#endif
PB_DS_HASH_EQ_FN_C_DEC(other),
- resize_base(other),
- ranged_hash_fn_base(other),
- m_a_p_entries(m_a_p_entries = s_entry_pointer_allocator.allocate(resize_base::get_nearest_larger_size(1))),
- m_num_e_p(resize_base::get_nearest_larger_size(1)),
- m_num_used_e(0)
+ resize_base(other), ranged_hash_fn_base(other),
+ m_num_e(resize_base::get_nearest_larger_size(1)), m_num_used_e(0),
+ m_entries(m_entries = s_entry_pointer_allocator.allocate(m_num_e))
{
initialize();
_GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();)
{
copy_from_range(other.begin(), other.end());
}
- catch(...)
+ catch (...)
{
deallocate_all();
throw;
_GLIBCXX_DEBUG_ONLY(assert_valid());
_GLIBCXX_DEBUG_ONLY(other.assert_valid());
- std::swap(m_a_p_entries, other.m_a_p_entries);
- std::swap(m_num_e_p, other.m_num_e_p);
+ std::swap(m_entries, other.m_entries);
+ std::swap(m_num_e, other.m_num_e);
std::swap(m_num_used_e, other.m_num_used_e);
ranged_hash_fn_base::swap(other);
hash_eq_fn_base::swap(other);
deallocate_all()
{
clear();
- s_entry_pointer_allocator.deallocate(m_a_p_entries, m_num_e_p);
+ s_entry_pointer_allocator.deallocate(m_entries, m_num_e);
}
PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
initialize()
{
- std::fill(m_a_p_entries, m_a_p_entries + m_num_e_p, entry_pointer(NULL));
- Resize_Policy::notify_resized(m_num_e_p);
+ std::fill(m_entries, m_entries + m_num_e, entry_pointer(NULL));
+ Resize_Policy::notify_resized(m_num_e);
Resize_Policy::notify_cleared();
- ranged_hash_fn_base::notify_resized(m_num_e_p);
+ ranged_hash_fn_base::notify_resized(m_num_e);
}
// At this point no exceptions can be thrown.
- p_e->m_p_next = m_a_p_entries[pos];
- m_a_p_entries[pos] = p_e;
+ p_e->m_p_next = m_entries[pos];
+ m_entries[pos] = p_e;
_GLIBCXX_DEBUG_ONLY(map_debug_base::insert_new(r_key);)
}
traits_base::s_no_throw_copies_indicator);
// At this point no exceptions can be thrown.
- p_e->m_p_next = m_a_p_entries[pos];
+ p_e->m_p_next = m_entries[pos];
p_e->m_hash = ranged_hash_fn_base::operator()((const_key_reference)(PB_DS_V2F(p_e->m_value))).second;
- m_a_p_entries[pos] = p_e;
+ m_entries[pos] = p_e;
_GLIBCXX_DEBUG_ONLY(map_debug_base::insert_new(r_key);)
}
assert_valid() const
{
map_debug_base::check_size(m_num_used_e);
- assert_entry_pointer_array_valid(m_a_p_entries);
+ assert_entry_pointer_array_valid(m_entries);
}
PB_DS_CLASS_T_DEC
assert_entry_pointer_array_valid(const entry_pointer_array a_p_entries) const
{
size_type iterated_num_used_e = 0;
- for (size_type pos = 0; pos < m_num_e_p; ++pos)
+ for (size_type pos = 0; pos < m_num_e; ++pos)
{
entry_pointer p_e = a_p_entries[pos];
while (p_e != NULL)
{
size_type num_ersd = 0;
- for (size_type pos = 0; pos < m_num_e_p; ++pos)
+ for (size_type pos = 0; pos < m_num_e; ++pos)
{
typedef
typename PB_DS_TYPES_TRAITS_C_DEC::const_reference
const_reference;
- while (m_a_p_entries[pos] != NULL&&
- pred(m_a_p_entries[pos]->m_value))
+ while (m_entries[pos] != NULL&&
+ pred(m_entries[pos]->m_value))
{
++num_ersd;
- entry_pointer p_next_e = m_a_p_entries[pos]->m_p_next;
+ entry_pointer p_next_e = m_entries[pos]->m_p_next;
- erase_entry_pointer(m_a_p_entries[pos]);
+ erase_entry_pointer(m_entries[pos]);
- m_a_p_entries[pos] = p_next_e;
+ m_entries[pos] = p_next_e;
}
- entry_pointer p_e = m_a_p_entries[pos];
+ entry_pointer p_e = m_entries[pos];
while (p_e != NULL&& p_e->m_p_next != NULL)
{
PB_DS_CLASS_C_DEC::
clear()
{
- for (size_type pos = 0; pos < m_num_e_p; ++pos)
- while (m_a_p_entries[pos] != NULL)
- erase_entry_pointer(m_a_p_entries[pos]);
+ for (size_type pos = 0; pos < m_num_e; ++pos)
+ while (m_entries[pos] != NULL)
+ erase_entry_pointer(m_entries[pos]);
do_resize_if_needed_no_throw();
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
- entry_pointer p_e = m_a_p_entries[pos];
+ entry_pointer p_e = m_entries[pos];
resize_base::notify_erase_search_start();
_GLIBCXX_DEBUG_ONLY(map_debug_base::
check_key_exists(r_key);)
- erase_entry_pointer(m_a_p_entries[pos]);
+ erase_entry_pointer(m_entries[pos]);
do_resize_if_needed_no_throw();
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
- entry_pointer p_e = m_a_p_entries[r_pos_hash_pair.first];
+ entry_pointer p_e = m_entries[r_pos_hash_pair.first];
resize_base::notify_erase_search_start();
_GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(
r_key);)
- erase_entry_pointer(m_a_p_entries[r_pos_hash_pair.first]);
+ erase_entry_pointer(m_entries[r_pos_hash_pair.first]);
do_resize_if_needed_no_throw();
const size_type pos = ranged_hash_fn_base::operator()(r_key);
- entry_pointer p_e = m_a_p_entries[pos];
+ entry_pointer p_e = m_entries[pos];
resize_base::notify_insert_search_start();
comp_hash pos_hash_pair = ranged_hash_fn_base::operator()(r_key);
- entry_pointer p_e = m_a_p_entries[pos_hash_pair.first];
+ entry_pointer p_e = m_entries[pos_hash_pair.first];
resize_base::notify_insert_search_start();
if (!resize_base::is_resize_needed())
return (false);
- resize_imp(resize_base::get_new_size( m_num_e_p, m_num_used_e));
+ resize_imp(resize_base::get_new_size( m_num_e, m_num_used_e));
return (true);
}
try
{
- resize_imp(resize_base::get_new_size( m_num_e_p, m_num_used_e));
+ resize_imp(resize_base::get_new_size( m_num_e, m_num_used_e));
}
catch(...)
{ }
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
- if (new_size == m_num_e_p)
+ if (new_size == m_num_e)
return;
- const size_type old_size = m_num_e_p;
+ const size_type old_size = m_num_e;
entry_pointer_array a_p_entries_resized;
a_p_entries_resized = s_entry_pointer_allocator.allocate(new_size);
- m_num_e_p = new_size;
+ m_num_e = new_size;
}
catch(...)
{
PB_DS_CLASS_C_DEC::
resize_imp_no_exceptions(size_type new_size, entry_pointer_array a_p_entries_resized, size_type old_size)
{
- std::fill(a_p_entries_resized, a_p_entries_resized + m_num_e_p,(entry_pointer)NULL);
+ std::fill(a_p_entries_resized, a_p_entries_resized + m_num_e,(entry_pointer)NULL);
for (size_type pos = 0; pos < old_size; ++pos)
{
- entry_pointer p_e = m_a_p_entries[pos];
+ entry_pointer p_e = m_entries[pos];
while (p_e != NULL)
p_e = resize_imp_no_exceptions_reassign_pointer(p_e, a_p_entries_resized, traits_base::m_store_extra_indicator);
}
- m_num_e_p = new_size;
+ m_num_e = new_size;
_GLIBCXX_DEBUG_ONLY(assert_entry_pointer_array_valid(a_p_entries_resized);)
- s_entry_pointer_allocator.deallocate(m_a_p_entries, old_size);
+ s_entry_pointer_allocator.deallocate(m_entries, old_size);
- m_a_p_entries = a_p_entries_resized;
+ m_entries = a_p_entries_resized;
_GLIBCXX_DEBUG_ONLY(assert_valid();)
}
PB_DS_CLASS_C_DEC::
trace() const
{
- std::cerr << static_cast<unsigned long>(m_num_e_p) << " " <<
+ std::cerr << static_cast<unsigned long>(m_num_e) << " " <<
static_cast<unsigned long>(m_num_used_e) << std::endl;
- for (size_type i = 0; i < m_num_e_p; ++i)
+ for (size_type i = 0; i < m_num_e; ++i)
{
std::cerr << static_cast<unsigned long>(i) << " ";
- trace_list(m_a_p_entries[i]);
+ trace_list(m_entries[i]);
std::cerr << std::endl;
}
{ }
inline
-PB_DS_CLASS_NAME(const PB_DS_CLASS_NAME& other) : base_type((const base_type&)other)
+PB_DS_CLASS_NAME(const PB_DS_CLASS_NAME& other)
+: base_type((const base_type&)other)
{ }
template<typename T0>
template<typename T0, typename T1, typename T2, typename T3>
inline
-PB_DS_CLASS_NAME(T0 t0, T1 t1, T2 t2, T3 t3) : base_type(t0, t1, t2, t3)
+PB_DS_CLASS_NAME(T0 t0, T1 t1, T2 t2, T3 t3)
+: base_type(t0, t1, t2, t3)
{ }
-template<typename T0,
- typename T1,
- typename T2,
- typename T3,
- typename T4>
+template<typename T0, typename T1, typename T2, typename T3, typename T4>
inline
-PB_DS_CLASS_NAME(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4) : base_type(t0, t1, t2, t3, t4)
+PB_DS_CLASS_NAME(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4)
+: base_type(t0, t1, t2, t3, t4)
{ }
-template<typename T0,
- typename T1,
- typename T2,
- typename T3,
- typename T4,
+template<typename T0, typename T1, typename T2, typename T3, typename T4,
typename T5>
inline
-PB_DS_CLASS_NAME(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5) : base_type(t0, t1, t2, t3, t4, t5)
+PB_DS_CLASS_NAME(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5)
+: base_type(t0, t1, t2, t3, t4, t5)
{ }
-template<typename T0,
- typename T1,
- typename T2,
- typename T3,
- typename T4,
- typename T5,
- typename T6>
+template<typename T0, typename T1, typename T2, typename T3, typename T4,
+ typename T5, typename T6>
inline
-PB_DS_CLASS_NAME(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6) : base_type(t0, t1, t2, t3, t4, t5, t6)
+PB_DS_CLASS_NAME(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6)
+: base_type(t0, t1, t2, t3, t4, t5, t6)
{ }
-template<typename T0,
- typename T1,
- typename T2,
- typename T3,
- typename T4,
- typename T5,
- typename T6,
- typename T7>
+template<typename T0, typename T1, typename T2, typename T3, typename T4,
+ typename T5, typename T6, typename T7>
inline
-PB_DS_CLASS_NAME(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6, T7 t7) : base_type(t0, t1, t2, t3, t4, t5, t6, t7)
+PB_DS_CLASS_NAME(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6, T7 t7)
+: base_type(t0, t1, t2, t3, t4, t5, t6, t7)
{ }
-template<typename T0,
- typename T1,
- typename T2,
- typename T3,
- typename T4,
- typename T5,
- typename T6,
- typename T7,
- typename T8>
+template<typename T0, typename T1, typename T2, typename T3, typename T4,
+ typename T5, typename T6, typename T7, typename T8>
inline
-PB_DS_CLASS_NAME(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6, T7 t7, T8 t8) : base_type(t0, t1, t2, t3, t4, t5, t6, t7, t8)
+PB_DS_CLASS_NAME(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6, T7 t7, T8 t8)
+: base_type(t0, t1, t2, t3, t4, t5, t6, t7, t8)
{ }
PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
-PB_DS_CLASS_NAME() :
- ranged_probe_fn_base(resize_base::get_nearest_larger_size(1)),
- m_a_entries(s_entry_allocator.allocate(resize_base::get_nearest_larger_size(1))),
- m_num_e(resize_base::get_nearest_larger_size(1)),
- m_num_used_e(0)
+PB_DS_CLASS_NAME()
+: ranged_probe_fn_base(resize_base::get_nearest_larger_size(1)),
+ m_num_e(resize_base::get_nearest_larger_size(1)), m_num_used_e(0),
+ m_entries(s_entry_allocator.allocate(m_num_e))
{
initialize();
_GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();)
PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
-PB_DS_CLASS_NAME(const Hash_Fn& r_hash_fn) :
- ranged_probe_fn_base(resize_base::get_nearest_larger_size(1), r_hash_fn),
- m_a_entries(s_entry_allocator.allocate(resize_base::get_nearest_larger_size(1))),
- m_num_e(resize_base::get_nearest_larger_size(1)),
- m_num_used_e(0)
+PB_DS_CLASS_NAME(const Hash_Fn& r_hash_fn)
+: ranged_probe_fn_base(resize_base::get_nearest_larger_size(1), r_hash_fn),
+ m_num_e(resize_base::get_nearest_larger_size(1)), m_num_used_e(0),
+ m_entries(s_entry_allocator.allocate(m_num_e))
{
initialize();
_GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();)
PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
-PB_DS_CLASS_NAME(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn) :
- hash_eq_fn_base(r_eq_fn),
+PB_DS_CLASS_NAME(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn)
+: hash_eq_fn_base(r_eq_fn),
ranged_probe_fn_base(resize_base::get_nearest_larger_size(1), r_hash_fn),
- m_a_entries(s_entry_allocator.allocate(resize_base::get_nearest_larger_size(1))),
- m_num_e(resize_base::get_nearest_larger_size(1)),
- m_num_used_e(0)
+ m_num_e(resize_base::get_nearest_larger_size(1)), m_num_used_e(0),
+ m_entries(s_entry_allocator.allocate(m_num_e))
{
initialize();
_GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();)
PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
-PB_DS_CLASS_NAME(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn, const Comb_Probe_Fn& r_comb_hash_fn) :
- hash_eq_fn_base(r_eq_fn),
+PB_DS_CLASS_NAME(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn,
+ const Comb_Probe_Fn& r_comb_hash_fn)
+: hash_eq_fn_base(r_eq_fn),
ranged_probe_fn_base(resize_base::get_nearest_larger_size(1),
r_hash_fn, r_comb_hash_fn),
- m_a_entries(s_entry_allocator.allocate(resize_base::get_nearest_larger_size(1))),
- m_num_e(resize_base::get_nearest_larger_size(1)),
- m_num_used_e(0)
+ m_num_e(resize_base::get_nearest_larger_size(1)), m_num_used_e(0),
+ m_entries(s_entry_allocator.allocate(m_num_e))
{
initialize();
_GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();)
PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
-PB_DS_CLASS_NAME(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn, const Comb_Probe_Fn& r_comb_hash_fn, const Probe_Fn& r_probe_fn) :
- hash_eq_fn_base(r_eq_fn),
+PB_DS_CLASS_NAME(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn,
+ const Comb_Probe_Fn& comb_hash_fn, const Probe_Fn& probe_fn)
+: hash_eq_fn_base(r_eq_fn),
ranged_probe_fn_base(resize_base::get_nearest_larger_size(1),
- r_hash_fn, r_comb_hash_fn, r_probe_fn),
- m_a_entries(s_entry_allocator.allocate(resize_base::get_nearest_larger_size(1))),
- m_num_e(resize_base::get_nearest_larger_size(1)),
- m_num_used_e(0)
+ r_hash_fn, comb_hash_fn, probe_fn),
+ m_num_e(resize_base::get_nearest_larger_size(1)), m_num_used_e(0),
+ m_entries(s_entry_allocator.allocate(m_num_e))
{
initialize();
_GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();)
PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
-PB_DS_CLASS_NAME(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn, const Comb_Probe_Fn& r_comb_hash_fn, const Probe_Fn& r_probe_fn, const Resize_Policy& r_resize_policy) :
- hash_eq_fn_base(r_eq_fn),
- resize_base(r_resize_policy),
+PB_DS_CLASS_NAME(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn,
+ const Comb_Probe_Fn& comb_hash_fn, const Probe_Fn& probe_fn,
+ const Resize_Policy& r_resize_policy)
+: hash_eq_fn_base(r_eq_fn), resize_base(r_resize_policy),
ranged_probe_fn_base(resize_base::get_nearest_larger_size(1),
- r_hash_fn, r_comb_hash_fn, r_probe_fn),
- m_a_entries(s_entry_allocator.allocate(resize_base::get_nearest_larger_size(1))),
- m_num_e(resize_base::get_nearest_larger_size(1)),
- m_num_used_e(0)
+ r_hash_fn, comb_hash_fn, probe_fn),
+ m_num_e(resize_base::get_nearest_larger_size(1)), m_num_used_e(0),
+ m_entries(s_entry_allocator.allocate(m_num_e))
{
initialize();
_GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();)
hash_eq_fn_base(other),
resize_base(other),
ranged_probe_fn_base(other),
- m_a_entries(s_entry_allocator.allocate(other.m_num_e)),
m_num_e(other.m_num_e),
- m_num_used_e(other.m_num_used_e)
+ m_num_used_e(other.m_num_used_e),
+ m_entries(s_entry_allocator.allocate(m_num_e))
{
for (size_type i = 0; i < m_num_e; ++i)
- m_a_entries[i].m_stat = (entry_status)empty_entry_status;
+ m_entries[i].m_stat = (entry_status)empty_entry_status;
try
{
for (size_type i = 0; i < m_num_e; ++i)
{
- m_a_entries[i].m_stat = other.m_a_entries[i].m_stat;
- if (m_a_entries[i].m_stat == valid_entry_status)
- new (m_a_entries + i) entry(other.m_a_entries[i]);
+ m_entries[i].m_stat = other.m_entries[i].m_stat;
+ if (m_entries[i].m_stat == valid_entry_status)
+ new (m_entries + i) entry(other.m_entries[i]);
}
}
- catch(...)
+ catch (...)
{
deallocate_all();
throw;
}
-
_GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();)
- }
+}
PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
~PB_DS_CLASS_NAME()
-{
- deallocate_all();
-}
+{ deallocate_all(); }
PB_DS_CLASS_T_DEC
void
{
_GLIBCXX_DEBUG_ONLY(assert_valid());
_GLIBCXX_DEBUG_ONLY(other.assert_valid());
- std::swap(m_a_entries, other.m_a_entries);
std::swap(m_num_e, other.m_num_e);
std::swap(m_num_used_e, other.m_num_used_e);
+ std::swap(m_entries, other.m_entries);
ranged_probe_fn_base::swap(other);
hash_eq_fn_base::swap(other);
resize_base::swap(other);
deallocate_all()
{
clear();
- erase_all_valid_entries(m_a_entries, m_num_e);
- s_entry_allocator.deallocate(m_a_entries, m_num_e);
+ erase_all_valid_entries(m_entries, m_num_e);
+ s_entry_allocator.deallocate(m_entries, m_num_e);
}
PB_DS_CLASS_T_DEC
{
for (size_type pos = 0; pos < size; ++pos)
{
- entry_pointer p_e =& a_entries_resized[pos];
+ entry_pointer p_e = &a_entries_resized[pos];
if (p_e->m_stat == valid_entry_status)
p_e->m_value.~value_type();
}
Resize_Policy::notify_cleared();
ranged_probe_fn_base::notify_resized(m_num_e);
for (size_type i = 0; i < m_num_e; ++i)
- m_a_entries[i].m_stat = (entry_status)empty_entry_status;
+ m_entries[i].m_stat = empty_entry_status;
}
PB_DS_CLASS_C_DEC::
constructor_insert_new_imp(const_mapped_reference r_val, size_type pos, integral_constant<int,false>)
{
- _GLIBCXX_DEBUG_ASSERT(m_a_entries[pos].m_stat != valid_entry_status);
+ _GLIBCXX_DEBUG_ASSERT(m_entries[pos].m_stat != valid_entry_status);
- entry* const p_e = m_a_entries + pos;
+ entry* const p_e = m_entries + pos;
new (&p_e->m_value) mapped_value_type(r_val);
PB_DS_CLASS_C_DEC::
constructor_insert_new_imp(const_mapped_reference r_val, size_type pos, true_type)
{
- _GLIBCXX_DEBUG_ASSERT(m_a_entries[pos].m_stat != valid_entry_status);
+ _GLIBCXX_DEBUG_ASSERT(m_entries[pos].m_stat != valid_entry_status);
- entry* const p_e = m_a_entries + pos;
+ entry* const p_e = m_entries + pos;
new (&p_e->m_value) mapped_value_type(r_val);
assert_valid() const
{
map_debug_base::check_size(m_num_used_e);
- assert_entry_array_valid(m_a_entries, traits_base::m_store_extra_indicator);
+ assert_entry_array_valid(m_entries, traits_base::m_store_extra_indicator);
}
#include <ext/pb_ds/detail/gp_hash_table_map_/debug_no_store_hash_fn_imps.hpp>
erase_entry(entry_pointer p_e)
{
_GLIBCXX_DEBUG_ASSERT(p_e->m_stat = valid_entry_status);
-
- _GLIBCXX_DEBUG_ONLY(map_debug_base::erase_existing(
- PB_DS_V2F(p_e->m_value));)
-
- typedef
- typename PB_DS_TYPES_TRAITS_C_DEC::stored_value_type
- stored_value_type;
-
+ _GLIBCXX_DEBUG_ONLY(map_debug_base::erase_existing(PB_DS_V2F(p_e->m_value));)
p_e->m_value.~value_type();
-
p_e->m_stat = erased_entry_status;
-
_GLIBCXX_DEBUG_ASSERT(m_num_used_e > 0);
resize_base::notify_erased(--m_num_used_e);
}
{
for (size_type pos = 0; pos < m_num_e; ++pos)
{
- entry_pointer p_e =& m_a_entries[pos];
-
+ entry_pointer p_e = &m_entries[pos];
if (p_e->m_stat == valid_entry_status)
erase_entry(p_e);
}
-
do_resize_if_needed_no_throw();
-
resize_base::notify_cleared();
}
erase_if(Pred pred)
{
_GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();)
-
- size_type num_ersd = 0;
-
+ size_type num_ersd = 0;
for (size_type pos = 0; pos < m_num_e; ++pos)
{
- entry_pointer p_e =& m_a_entries[pos];
-
+ entry_pointer p_e = &m_entries[pos];
if (p_e->m_stat == valid_entry_status)
if (pred(p_e->m_value))
{
++num_ersd;
-
erase_entry(p_e);
}
}
do_resize_if_needed_no_throw();
-
_GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();)
-
- return (num_ersd);
+ return num_ersd;
}
PB_DS_CLASS_T_DEC
inline bool
PB_DS_CLASS_C_DEC::
erase(const_key_reference r_key)
-{
- return (erase_imp(r_key, traits_base::m_store_extra_indicator));
-}
+{ return erase_imp(r_key, traits_base::m_store_extra_indicator); }
#include <ext/pb_ds/detail/gp_hash_table_map_/erase_no_store_hash_fn_imps.hpp>
#include <ext/pb_ds/detail/gp_hash_table_map_/erase_store_hash_fn_imps.hpp>
const size_type pos =
ranged_probe_fn_base::operator()( r_key, hash, i);
- entry* const p_e = m_a_entries + pos;
+ entry* const p_e = m_entries + pos;
switch(p_e->m_stat)
{
{
const size_type pos = ranged_probe_fn_base::operator()( r_key, pos_hash_pair.second, i);
- entry* const p_e = m_a_entries + pos;
+ entry* const p_e = m_entries + pos;
switch(p_e->m_stat)
{
find(const_key_reference r_key)
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
-
- return ((find_key_pointer(r_key, traits_base::m_store_extra_indicator)));
+ return find_key_pointer(r_key, traits_base::m_store_extra_indicator);
}
PB_DS_CLASS_T_DEC
find(const_key_reference r_key) const
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
-
- return (const_cast<PB_DS_CLASS_C_DEC& >(*this).
- find_key_pointer(r_key, traits_base::m_store_extra_indicator));
+ return const_cast<PB_DS_CLASS_C_DEC&>(*this).find_key_pointer(r_key, traits_base::m_store_extra_indicator);
}
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::point_iterator
PB_DS_CLASS_C_DEC::
find_end()
-{
- return (NULL);
-}
+{ return NULL; }
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::const_point_iterator
PB_DS_CLASS_C_DEC::
find_end() const
-{
- return (NULL);
-}
+{ return NULL; }
{
namespace detail
{
-
-#define PB_DS_CLASS_T_DEC \
- template< \
- typename Key, \
- typename Mapped, \
- class Hash_Fn, \
- class Eq_Fn, \
- class Allocator, \
- bool Store_Hash, \
- class Comb_Probe_Fn, \
- class Probe_Fn, \
- class Resize_Policy>
+#define PB_DS_CLASS_T_DEC \
+ template<typename Key, typename Mapped, typename Hash_Fn, typename Eq_Fn, \
+ typename Allocator, bool Store_Hash, typename Comb_Probe_Fn, \
+ typename Probe_Fn, typename Resize_Policy>
#ifdef PB_DS_DATA_TRUE_INDICATOR
#define PB_DS_CLASS_NAME gp_ht_map_data_
#define PB_DS_CLASS_NAME gp_ht_map_no_data_
#endif
-#define PB_DS_CLASS_C_DEC \
- PB_DS_CLASS_NAME< \
- Key, \
- Mapped, \
- Hash_Fn, \
- Eq_Fn, \
- Allocator, \
- Store_Hash, \
- Comb_Probe_Fn, \
- Probe_Fn, \
- Resize_Policy>
-
-#define PB_DS_HASH_EQ_FN_C_DEC \
- hash_eq_fn< \
- Key, \
- Eq_Fn, \
- Allocator, \
- Store_Hash>
-
-#define PB_DS_RANGED_PROBE_FN_C_DEC \
- ranged_probe_fn< \
- Key, \
- Hash_Fn, \
- Allocator, \
- Comb_Probe_Fn, \
- Probe_Fn, \
- Store_Hash>
-
-#define PB_DS_TYPES_TRAITS_C_DEC \
- types_traits< \
- Key, \
- Mapped, \
- Allocator, \
- Store_Hash>
+#define PB_DS_CLASS_C_DEC \
+ PB_DS_CLASS_NAME<Key, Mapped, Hash_Fn, Eq_Fn, Allocator, \
+ Store_Hash, Comb_Probe_Fn, Probe_Fn, Resize_Policy>
+
+#define PB_DS_HASH_EQ_FN_C_DEC \
+ hash_eq_fn<Key, Eq_Fn, Allocator, Store_Hash>
+
+#define PB_DS_RANGED_PROBE_FN_C_DEC \
+ ranged_probe_fn<Key, Hash_Fn, Allocator, Comb_Probe_Fn, Probe_Fn, Store_Hash>
+
+#define PB_DS_TYPES_TRAITS_C_DEC \
+ types_traits<Key, Mapped, Allocator, Store_Hash>
#ifdef _GLIBCXX_DEBUG
-#define PB_DS_MAP_DEBUG_BASE_C_DEC \
+#define PB_DS_MAP_DEBUG_BASE_C_DEC \
map_debug_base<Key, Eq_Fn, typename Allocator::template rebind<Key>::other::const_reference>
#endif
#define PB_DS_V2S(X) Mapped()
#endif
-#define PB_DS_STATIC_ASSERT(UNIQUE, E) \
- typedef \
- static_assert_dumclass< \
- sizeof(static_assert<(bool)(E)>)> \
+#define PB_DS_STATIC_ASSERT(UNIQUE, E) \
+ typedef static_assert_dumclass<sizeof(static_assert<(bool)(E)>)> \
UNIQUE##static_assert_type
template<typename Key,
typename Mapped,
- class Hash_Fn,
- class Eq_Fn,
- class Allocator,
+ typename Hash_Fn,
+ typename Eq_Fn,
+ typename Allocator,
bool Store_Hash,
- class Comb_Probe_Fn,
- class Probe_Fn,
- class Resize_Policy>
+ typename Comb_Probe_Fn,
+ typename Probe_Fn,
+ typename Resize_Policy>
class PB_DS_CLASS_NAME :
#ifdef _GLIBCXX_DEBUG
protected PB_DS_MAP_DEBUG_BASE_C_DEC,
public PB_DS_RANGED_PROBE_FN_C_DEC,
public PB_DS_TYPES_TRAITS_C_DEC
{
-
private:
+ typedef PB_DS_TYPES_TRAITS_C_DEC traits_base;
+ typedef typename traits_base::store_extra_false_type store_hash_false_type;
+ typedef typename traits_base::store_extra_true_type store_hash_true_type;
+ typedef typename traits_base::value_type value_type_;
+ typedef typename traits_base::pointer pointer_;
+ typedef typename traits_base::const_pointer const_pointer_;
+ typedef typename traits_base::reference reference_;
+ typedef typename traits_base::const_reference const_reference_;
+ typedef typename traits_base::comp_hash comp_hash;
+
+ enum entry_status
+ {
+ empty_entry_status,
+ valid_entry_status,
+ erased_entry_status
+ } __attribute__ ((packed));
- typedef
- typename PB_DS_TYPES_TRAITS_C_DEC::store_extra_false_type
- store_hash_false_type;
-
- typedef
- typename PB_DS_TYPES_TRAITS_C_DEC::store_extra_true_type
- store_hash_true_type;
-
- typedef typename PB_DS_TYPES_TRAITS_C_DEC::value_type value_type_;
+ struct entry : public traits_base::stored_value_type
+ {
+ entry_status m_stat;
+ };
- typedef typename PB_DS_TYPES_TRAITS_C_DEC::pointer pointer_;
+ typedef typename Allocator::template rebind<entry>::other entry_allocator;
+ typedef typename entry_allocator::pointer entry_pointer;
+ typedef typename entry_allocator::const_pointer const_entry_pointer;
+ typedef typename entry_allocator::reference entry_reference;
+ typedef typename entry_allocator::const_reference const_entry_reference;
+ typedef typename entry_allocator::pointer entry_array;
- typedef
- typename PB_DS_TYPES_TRAITS_C_DEC::const_pointer
- const_pointer_;
+ typedef PB_DS_RANGED_PROBE_FN_C_DEC ranged_probe_fn_base;
- typedef typename PB_DS_TYPES_TRAITS_C_DEC::reference reference_;
+#ifdef _GLIBCXX_DEBUG
+ typedef PB_DS_MAP_DEBUG_BASE_C_DEC map_debug_base;
+#endif
- typedef
- typename PB_DS_TYPES_TRAITS_C_DEC::const_reference
- const_reference_;
+ typedef PB_DS_HASH_EQ_FN_C_DEC hash_eq_fn_base;
+ typedef Resize_Policy resize_base;
-#define PB_DS_GEN_POS \
- typename Allocator::size_type
+#define PB_DS_GEN_POS typename Allocator::size_type
#include <ext/pb_ds/detail/unordered_iterator/const_point_iterator.hpp>
#include <ext/pb_ds/detail/unordered_iterator/point_iterator.hpp>
#undef PB_DS_GEN_POS
public:
-
+ typedef Allocator allocator;
typedef typename Allocator::size_type size_type;
-
typedef typename Allocator::difference_type difference_type;
-
typedef Hash_Fn hash_fn;
-
typedef Eq_Fn eq_fn;
-
- typedef Allocator allocator;
-
typedef Probe_Fn probe_fn;
-
typedef Comb_Probe_Fn comb_probe_fn;
-
typedef Resize_Policy resize_policy;
enum
store_hash = Store_Hash
};
- typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_type key_type;
-
- typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_pointer key_pointer;
-
- typedef
- typename PB_DS_TYPES_TRAITS_C_DEC::const_key_pointer
- const_key_pointer;
-
- typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_reference key_reference;
-
- typedef
- typename PB_DS_TYPES_TRAITS_C_DEC::const_key_reference
- const_key_reference;
-
- typedef typename PB_DS_TYPES_TRAITS_C_DEC::mapped_type mapped_type;
-
- typedef
- typename PB_DS_TYPES_TRAITS_C_DEC::mapped_pointer
- mapped_pointer;
-
- typedef
- typename PB_DS_TYPES_TRAITS_C_DEC::const_mapped_pointer
- const_mapped_pointer;
-
- typedef
- typename PB_DS_TYPES_TRAITS_C_DEC::mapped_reference
- mapped_reference;
-
- typedef
- typename PB_DS_TYPES_TRAITS_C_DEC::const_mapped_reference
- const_mapped_reference;
-
- typedef typename PB_DS_TYPES_TRAITS_C_DEC::value_type value_type;
-
- typedef typename PB_DS_TYPES_TRAITS_C_DEC::pointer pointer;
-
- typedef typename PB_DS_TYPES_TRAITS_C_DEC::const_pointer const_pointer;
-
- typedef typename PB_DS_TYPES_TRAITS_C_DEC::reference reference;
-
- typedef
- typename PB_DS_TYPES_TRAITS_C_DEC::const_reference
- const_reference;
+ typedef typename traits_base::key_type key_type;
+ typedef typename traits_base::key_pointer key_pointer;
+ typedef typename traits_base::const_key_pointer const_key_pointer;
+ typedef typename traits_base::key_reference key_reference;
+ typedef typename traits_base::const_key_reference const_key_reference;
+ typedef typename traits_base::mapped_type mapped_type;
+ typedef typename traits_base::mapped_pointer mapped_pointer;
+ typedef typename traits_base::const_mapped_pointer const_mapped_pointer;
+ typedef typename traits_base::mapped_reference mapped_reference;
+ typedef typename traits_base::const_mapped_reference const_mapped_reference;
+ typedef typename traits_base::value_type value_type;
+ typedef typename traits_base::pointer pointer;
+ typedef typename traits_base::const_pointer const_pointer;
+ typedef typename traits_base::reference reference;
+ typedef typename traits_base::const_reference const_reference;
#ifdef PB_DS_DATA_TRUE_INDICATOR
typedef point_iterator_ point_iterator;
-#endif // #ifdef PB_DS_DATA_TRUE_INDICATOR
+#endif
#ifdef PB_DS_DATA_FALSE_INDICATOR
typedef const_point_iterator_ point_iterator;
-#endif // #ifdef PB_DS_DATA_FALSE_INDICATOR
+#endif
typedef const_point_iterator_ const_point_iterator;
#ifdef PB_DS_DATA_TRUE_INDICATOR
typedef iterator_ iterator;
-#endif // #ifdef PB_DS_DATA_TRUE_INDICATOR
+#endif
#ifdef PB_DS_DATA_FALSE_INDICATOR
typedef const_iterator_ iterator;
-#endif // #ifdef PB_DS_DATA_FALSE_INDICATOR
+#endif
typedef const_iterator_ const_iterator;
- public:
-
PB_DS_CLASS_NAME();
- PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC& other);
+ PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC&);
- PB_DS_CLASS_NAME(const Hash_Fn& r_hash_fn);
+ PB_DS_CLASS_NAME(const Hash_Fn&);
- PB_DS_CLASS_NAME(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn);
+ PB_DS_CLASS_NAME(const Hash_Fn&, const Eq_Fn&);
- PB_DS_CLASS_NAME(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn, const Comb_Probe_Fn& r_comb_probe_fn);
+ PB_DS_CLASS_NAME(const Hash_Fn&, const Eq_Fn&, const Comb_Probe_Fn&);
- PB_DS_CLASS_NAME(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn, const Comb_Probe_Fn& r_comb_probe_fn, const Probe_Fn& r_probe_fn);
+ PB_DS_CLASS_NAME(const Hash_Fn&, const Eq_Fn&, const Comb_Probe_Fn&,
+ const Probe_Fn&);
- PB_DS_CLASS_NAME(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn, const Comb_Probe_Fn& r_comb_probe_fn, const Probe_Fn& r_probe_fn, const Resize_Policy& r_resize_policy);
+ PB_DS_CLASS_NAME(const Hash_Fn&, const Eq_Fn&, const Comb_Probe_Fn&,
+ const Probe_Fn&, const Resize_Policy&);
template<typename It>
void
insert(const_reference r_val)
{
_GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();)
-
- return (insert_imp(r_val, traits_base::m_store_extra_indicator));
+ return insert_imp(r_val, traits_base::m_store_extra_indicator);
}
inline mapped_reference
operator[](const_key_reference r_key)
{
#ifdef PB_DS_DATA_TRUE_INDICATOR
- return (subscript_imp(r_key, traits_base::m_store_extra_indicator));
-#else // #ifdef PB_DS_DATA_TRUE_INDICATOR
+ return subscript_imp(r_key, traits_base::m_store_extra_indicator);
+#else
insert(r_key);
-
- return (traits_base::s_null_mapped);
-#endif // #ifdef PB_DS_DATA_TRUE_INDICATOR
+ return traits_base::s_null_mapped;
+#endif
}
inline point_iterator
#endif
private:
- typedef PB_DS_TYPES_TRAITS_C_DEC traits_base;
-
- enum ENTRY_STATUS
- {
- empty_entry_status,
- valid_entry_status,
- erased_entry_status
- };
-
- typedef char entry_status;
-
- struct entry : public PB_DS_TYPES_TRAITS_C_DEC::stored_value_type
- {
- entry_status m_stat;
- };
-
- typedef
- typename Allocator::template rebind<entry>::other
- entry_allocator;
-
- typedef typename entry_allocator::pointer entry_pointer;
-
- typedef typename entry_allocator::const_pointer const_entry_pointer;
-
- typedef typename entry_allocator::reference entry_reference;
-
- typedef
- typename entry_allocator::const_reference
- const_entry_reference;
-
- typedef typename entry_allocator::pointer entry_array;
-
- typedef PB_DS_RANGED_PROBE_FN_C_DEC ranged_probe_fn_base;
-
-#ifdef _GLIBCXX_DEBUG
- typedef PB_DS_MAP_DEBUG_BASE_C_DEC map_debug_base;
-#endif
-
- typedef PB_DS_HASH_EQ_FN_C_DEC hash_eq_fn_base;
-
- typedef Resize_Policy resize_base;
-
#ifdef PB_DS_DATA_TRUE_INDICATOR
friend class iterator_;
-#endif // #ifdef PB_DS_DATA_TRUE_INDICATOR
+#endif
friend class const_iterator_;
- typedef typename PB_DS_TYPES_TRAITS_C_DEC::comp_hash comp_hash;
-
- private:
-
void
deallocate_all();
initialize();
void
- erase_all_valid_entries(entry_array a_entries_resized, size_type size);
+ erase_all_valid_entries(entry_array, size_type);
inline bool
do_resize_if_needed();
do_resize_if_needed_no_throw();
void
- resize_imp(size_type new_size);
+ resize_imp(size_type);
virtual void
- do_resize(size_type new_size);
+ do_resize(size_type);
void
- resize_imp(entry_array a_entries_resized, size_type old_size);
+ resize_imp(entry_array, size_type);
inline void
- resize_imp_reassign(entry_pointer p_e, entry_array a_entries_resized, store_hash_false_type);
+ resize_imp_reassign(entry_pointer, entry_array, store_hash_false_type);
inline void
- resize_imp_reassign(entry_pointer p_e, entry_array a_entries_resized, store_hash_true_type);
+ resize_imp_reassign(entry_pointer, entry_array, store_hash_true_type);
inline size_type
- find_ins_pos(const_key_reference r_key, store_hash_false_type);
+ find_ins_pos(const_key_reference, store_hash_false_type);
inline comp_hash
- find_ins_pos(const_key_reference r_key, store_hash_true_type);
+ find_ins_pos(const_key_reference, store_hash_true_type);
inline std::pair<point_iterator, bool>
- insert_imp(const_reference r_val, store_hash_false_type);
+ insert_imp(const_reference, store_hash_false_type);
inline std::pair<point_iterator, bool>
- insert_imp(const_reference r_val, store_hash_true_type);
+ insert_imp(const_reference, store_hash_true_type);
inline pointer
insert_new_imp(const_reference r_val, size_type pos)
{
- _GLIBCXX_DEBUG_ASSERT(m_a_entries[pos].m_stat != valid_entry_status);
+ _GLIBCXX_DEBUG_ASSERT(m_entries[pos].m_stat != valid_entry_status);
if (do_resize_if_needed())
pos = find_ins_pos(PB_DS_V2F(r_val),
traits_base::m_store_extra_indicator);
- _GLIBCXX_DEBUG_ASSERT(m_a_entries[pos].m_stat != valid_entry_status);
-
- entry* const p_e = m_a_entries + pos;
+ _GLIBCXX_DEBUG_ASSERT(m_entries[pos].m_stat != valid_entry_status);
+ entry* const p_e = m_entries + pos;
new (&p_e->m_value) value_type(r_val);
-
p_e->m_stat = valid_entry_status;
-
resize_base::notify_inserted(++m_num_used_e);
- _GLIBCXX_DEBUG_ONLY(map_debug_base::
- insert_new(PB_DS_V2F(p_e->m_value));)
+ _GLIBCXX_DEBUG_ONLY(map_debug_base::insert_new(PB_DS_V2F(p_e->m_value));)
- _GLIBCXX_DEBUG_ONLY(assert_valid();)
-
- return (&p_e->m_value);
+ _GLIBCXX_DEBUG_ONLY(assert_valid();)
+ return &p_e->m_value;
}
inline pointer
insert_new_imp(const_reference r_val, comp_hash& r_pos_hash_pair)
{
- _GLIBCXX_DEBUG_ASSERT(m_a_entries[r_pos_hash_pair.first].m_stat !=
+ _GLIBCXX_DEBUG_ASSERT(m_entries[r_pos_hash_pair.first].m_stat !=
valid_entry_status);
if (do_resize_if_needed())
- r_pos_hash_pair = find_ins_pos(
- PB_DS_V2F(r_val),
+ r_pos_hash_pair = find_ins_pos(PB_DS_V2F(r_val),
traits_base::m_store_extra_indicator);
- _GLIBCXX_DEBUG_ASSERT(m_a_entries[r_pos_hash_pair.first].m_stat !=
- valid_entry_status);
-
- entry* const p_e = m_a_entries + r_pos_hash_pair.first;
+ _GLIBCXX_DEBUG_ASSERT(m_entries[r_pos_hash_pair.first].m_stat !=
+ valid_entry_status);
+ entry* const p_e = m_entries + r_pos_hash_pair.first;
new (&p_e->m_value) value_type(r_val);
-
p_e->m_hash = r_pos_hash_pair.second;
-
p_e->m_stat = valid_entry_status;
resize_base::notify_inserted(++m_num_used_e);
- _GLIBCXX_DEBUG_ONLY(map_debug_base::insert_new(
- PB_DS_V2F(p_e->m_value));)
-
- _GLIBCXX_DEBUG_ONLY(assert_valid();)
+ _GLIBCXX_DEBUG_ONLY(map_debug_base::insert_new(PB_DS_V2F(p_e->m_value));)
- return (&p_e->m_value);
+ _GLIBCXX_DEBUG_ONLY(assert_valid();)
+ return &p_e->m_value;
}
#ifdef PB_DS_DATA_TRUE_INDICATOR
inline mapped_reference
- subscript_imp(const_key_reference r_key, store_hash_false_type)
+ subscript_imp(const_key_reference key, store_hash_false_type)
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
- const size_type pos =
- find_ins_pos(r_key, traits_base::m_store_extra_indicator);
+ const size_type pos = find_ins_pos(key,
+ traits_base::m_store_extra_indicator);
- entry_pointer p_e =& m_a_entries[pos];
+ entry_pointer p_e =& m_entries[pos];
if (p_e->m_stat != valid_entry_status)
- return (insert_new_imp(
- value_type(
- r_key,
- mapped_type()),
- pos)->second);
-
- _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(r_key);)
+ return insert_new_imp(value_type(key, mapped_type()), pos)->second;
- return (p_e->m_value.second);
+ _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(key);)
+ return p_e->m_value.second;
}
inline mapped_reference
- subscript_imp(const_key_reference r_key, store_hash_true_type)
+ subscript_imp(const_key_reference key, store_hash_true_type)
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
- comp_hash pos_hash_pair =
- find_ins_pos(r_key, traits_base::m_store_extra_indicator);
+ comp_hash pos_hash_pair =
+ find_ins_pos(key, traits_base::m_store_extra_indicator);
- if (m_a_entries[pos_hash_pair.first].m_stat != valid_entry_status)
- return (insert_new_imp(
- value_type(
- r_key,
- mapped_type()),
- pos_hash_pair)->second);
+ if (m_entries[pos_hash_pair.first].m_stat != valid_entry_status)
+ return insert_new_imp(value_type(key, mapped_type()),
+ pos_hash_pair)->second;
- _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(r_key));
-
- return ((m_a_entries + pos_hash_pair.first)->m_value.second);
+ _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(key));
+ return (m_entries + pos_hash_pair.first)->m_value.second;
}
-#endif // #ifdef PB_DS_DATA_TRUE_INDICATOR
+#endif
inline pointer
- find_key_pointer(const_key_reference r_key, store_hash_false_type)
+ find_key_pointer(const_key_reference key, store_hash_false_type)
{
- const size_type hash = ranged_probe_fn_base::operator()(r_key);
-
+ const size_type hash = ranged_probe_fn_base::operator()(key);
size_type i;
-
resize_base::notify_find_search_start();
// Loop until entry is found or until all possible entries accessed.
-
for (i = 0; i < m_num_e; ++i)
{
- const size_type pos =
- ranged_probe_fn_base::operator()( r_key, hash, i);
-
- entry* const p_e = m_a_entries + pos;
+ const size_type pos = ranged_probe_fn_base::operator()(key, hash, i);
- switch(p_e->m_stat)
+ entry* const p_e = m_entries + pos;
+ switch (p_e->m_stat)
{
case empty_entry_status:
{
resize_base::notify_find_search_end();
+ _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(key);)
- _GLIBCXX_DEBUG_ONLY(map_debug_base::
- check_key_does_not_exist(r_key);)
-
- return (NULL);
+ return NULL;
}
break;
case valid_entry_status:
- if (hash_eq_fn_base::operator()(
- PB_DS_V2F(p_e->m_value),
- r_key))
+ if (hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), key))
{
resize_base::notify_find_search_end();
+ _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(key);)
- _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(r_key);)
-
- return ((pointer)&p_e->m_value);
+ return pointer(&p_e->m_value);
}
break;
case erased_entry_status:
resize_base::notify_find_search_collision();
}
- _GLIBCXX_DEBUG_ONLY(map_debug_base::
- check_key_does_not_exist(r_key);)
-
- resize_base::notify_find_search_end();
-
- return (NULL);
+ _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(key);)
+ resize_base::notify_find_search_end();
+ return NULL;
}
inline pointer
- find_key_pointer(const_key_reference r_key, store_hash_true_type)
+ find_key_pointer(const_key_reference key, store_hash_true_type)
{
- comp_hash pos_hash_pair = ranged_probe_fn_base::operator()(r_key);
-
+ comp_hash pos_hash_pair = ranged_probe_fn_base::operator()(key);
size_type i;
-
resize_base::notify_find_search_start();
// Loop until entry is found or until all possible entries accessed.
-
for (i = 0; i < m_num_e; ++i)
{
const size_type pos =
- ranged_probe_fn_base::operator()( r_key, pos_hash_pair.second, i);
+ ranged_probe_fn_base::operator()(key, pos_hash_pair.second, i);
- entry* const p_e = m_a_entries + pos;
+ entry* const p_e = m_entries + pos;
switch(p_e->m_stat)
{
case empty_entry_status:
{
resize_base::notify_find_search_end();
+ _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(key);)
- _GLIBCXX_DEBUG_ONLY(map_debug_base::
- check_key_does_not_exist(r_key);)
-
- return (NULL);
+ return NULL;
}
break;
case valid_entry_status:
- if (hash_eq_fn_base::operator()(
- PB_DS_V2F(p_e->m_value),
+ if (hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value),
p_e->m_hash,
- r_key, pos_hash_pair.second))
+ key, pos_hash_pair.second))
{
resize_base::notify_find_search_end();
-
- _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(r_key);)
-
- return ((pointer)&p_e->m_value);
+ _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(key);)
+ return pointer(&p_e->m_value);
}
break;
case erased_entry_status:
resize_base::notify_find_search_collision();
}
- _GLIBCXX_DEBUG_ONLY(map_debug_base::
- check_key_does_not_exist(r_key);)
-
- resize_base::notify_find_search_end();
-
- return (NULL);
+ _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(key);)
+ resize_base::notify_find_search_end();
+ return NULL;
}
inline bool
- erase_imp(const_key_reference r_key, true_type);
+ erase_imp(const_key_reference, true_type);
inline bool
- erase_imp(const_key_reference r_key, false_type);
+ erase_imp(const_key_reference, false_type);
inline void
erase_entry(entry_pointer p_e);
#ifdef PB_DS_DATA_TRUE_INDICATOR
void
inc_it_state(pointer& r_p_value, size_type& r_pos) const
- {
- inc_it_state((const_mapped_pointer& )r_p_value, r_pos);
- }
-#endif // #ifdef PB_DS_DATA_TRUE_INDICATOR
+ { inc_it_state((const_mapped_pointer& )r_p_value, r_pos); }
+#endif
void
inc_it_state(const_pointer& r_p_value, size_type& r_pos) const
{
_GLIBCXX_DEBUG_ASSERT(r_p_value != NULL);
-
for (++r_pos; r_pos < m_num_e; ++r_pos)
{
- const_entry_pointer p_e =& m_a_entries[r_pos];
-
+ const_entry_pointer p_e =& m_entries[r_pos];
if (p_e->m_stat == valid_entry_status)
{
r_p_value =& p_e->m_value;
-
return;
}
}
-
r_p_value = NULL;
}
{
for (r_pos = 0; r_pos < m_num_e; ++r_pos)
{
- const_entry_pointer p_e =& m_a_entries[r_pos];
-
+ const_entry_pointer p_e = &m_entries[r_pos];
if (p_e->m_stat == valid_entry_status)
{
- r_p_value =& p_e->m_value;
-
+ r_p_value = &p_e->m_value;
return;
}
}
-
r_p_value = NULL;
}
{
for (r_pos = 0; r_pos < m_num_e; ++r_pos)
{
- entry_pointer p_e =& m_a_entries[r_pos];
-
+ entry_pointer p_e = &m_entries[r_pos];
if (p_e->m_stat == valid_entry_status)
{
- r_p_value =& p_e->m_value;
-
+ r_p_value = &p_e->m_value;
return;
}
}
-
r_p_value = NULL;
}
#ifdef _GLIBCXX_DEBUG
void
- assert_entry_array_valid(const entry_array a_entries,
- store_hash_false_type) const;
+ assert_entry_array_valid(const entry_array, store_hash_false_type) const;
void
- assert_entry_array_valid(const entry_array a_entries,
- store_hash_true_type) const;
+ assert_entry_array_valid(const entry_array, store_hash_true_type) const;
#endif
- private:
- static entry_allocator s_entry_allocator;
-
- entry_pointer m_a_entries;
-
- size_type m_num_e;
-
- size_type m_num_used_e;
+ static entry_allocator s_entry_allocator;
+ static iterator s_end_it;
+ static const_iterator s_const_end_it;
- static iterator s_end_it;
-
- static const_iterator s_const_end_it;
+ size_type m_num_e;
+ size_type m_num_used_e;
+ entry_pointer m_entries;
enum
{
- store_hash_ok =
- !Store_Hash ||
- !is_same<
- Hash_Fn,
- pb_ds::null_hash_fn>::value
+ store_hash_ok = !Store_Hash
+ || !is_same<Hash_Fn, pb_ds::null_hash_fn>::value
};
PB_DS_STATIC_ASSERT(sth, store_hash_ok);
#include <ext/pb_ds/detail/gp_hash_table_map_/trace_fn_imps.hpp>
#undef PB_DS_CLASS_T_DEC
-
#undef PB_DS_CLASS_C_DEC
-
#undef PB_DS_HASH_EQ_FN_C_DEC
-
#undef PB_DS_RANGED_PROBE_FN_C_DEC
-
#undef PB_DS_TYPES_TRAITS_C_DEC
-
#undef PB_DS_MAP_DEBUG_BASE_C_DEC
-
#undef PB_DS_CLASS_NAME
-
#undef PB_DS_V2F
#undef PB_DS_V2S
-
#undef PB_DS_STATIC_ASSERT
} // namespace detail
_GLIBCXX_DEBUG_ASSERT(pos < m_num_e);
- entry* const p_e = m_a_entries + pos;
+ entry* const p_e = m_entries + pos;
switch(p_e->m_stat)
{
const size_type pos =
find_ins_pos(r_key, traits_base::m_store_extra_indicator);
- if (m_a_entries[pos].m_stat == valid_entry_status)
+ if (m_entries[pos].m_stat == valid_entry_status)
{
_GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(r_key);)
return (std::make_pair(
- & (m_a_entries + pos)->m_value,
+ & (m_entries + pos)->m_value,
false));
}
find_ins_pos(const_key_reference r_key, store_hash_true_type)
{
_GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();)
-
- comp_hash pos_hash_pair = ranged_probe_fn_base::operator()(r_key);
+ comp_hash pos_hash_pair = ranged_probe_fn_base::operator()(r_key);
size_type i;
* that it has not been initted yet.
*/
size_type ins_pos = m_num_e;
-
resize_base::notify_insert_search_start();
-
for (i = 0; i < m_num_e; ++i)
{
- const size_type pos =
- ranged_probe_fn_base::operator()(r_key, pos_hash_pair.second, i);
-
- entry* const p_e = m_a_entries + pos;
+ const size_type pos = ranged_probe_fn_base::operator()(r_key, pos_hash_pair.second, i);
+ entry* const p_e = m_entries + pos;
switch(p_e->m_stat)
{
case empty_entry_status:
{
resize_base::notify_insert_search_end();
- _GLIBCXX_DEBUG_ONLY(
- map_debug_base::check_key_does_not_exist(r_key);)
+ _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key);)
- return ((ins_pos == m_num_e)?
+ return ((ins_pos == m_num_e) ?
std::make_pair(pos, pos_hash_pair.second) :
std::make_pair(ins_pos, pos_hash_pair.second));
}
ins_pos = pos;
break;
case valid_entry_status:
- if (hash_eq_fn_base::operator()(
- PB_DS_V2F(p_e->m_value),
- p_e->m_hash,
- r_key,
- pos_hash_pair.second))
+ if (hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), p_e->m_hash,
+ r_key, pos_hash_pair.second))
{
resize_base::notify_insert_search_end();
-
_GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(r_key);)
-
- return (std::make_pair(pos, pos_hash_pair.second));
+ return std::make_pair(pos, pos_hash_pair.second);
}
break;
default:
_GLIBCXX_DEBUG_ASSERT(0);
};
-
resize_base::notify_insert_search_collision();
}
-
resize_base::notify_insert_search_end();
-
if (ins_pos == m_num_e)
throw insert_error();
-
- return (std::make_pair(ins_pos, pos_hash_pair.second));
+ return std::make_pair(ins_pos, pos_hash_pair.second);
}
PB_DS_CLASS_T_DEC
insert_imp(const_reference r_val, store_hash_true_type)
{
const_key_reference r_key = PB_DS_V2F(r_val);
-
- comp_hash pos_hash_pair =
- find_ins_pos(r_key, traits_base::m_store_extra_indicator);
+ comp_hash pos_hash_pair = find_ins_pos(r_key,
+ traits_base::m_store_extra_indicator);
_GLIBCXX_DEBUG_ASSERT(pos_hash_pair.first < m_num_e);
-
- entry_pointer p_e =& m_a_entries[pos_hash_pair.first];
-
+ entry_pointer p_e =& m_entries[pos_hash_pair.first];
if (p_e->m_stat == valid_entry_status)
{
_GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(r_key));
-
- return (std::make_pair(&p_e->m_value, false));
+ return std::make_pair(&p_e->m_value, false);
}
_GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key));
-
- return (std::make_pair(
- insert_new_imp(r_val, pos_hash_pair),
- true));
+ return std::make_pair(insert_new_imp(r_val, pos_hash_pair), true);
}
do_resize_if_needed()
{
if (!resize_base::is_resize_needed())
- return (false);
-
- resize_imp(resize_base::get_new_size( m_num_e, m_num_used_e));
-
- return (true);
+ return false;
+ resize_imp(resize_base::get_new_size(m_num_e, m_num_used_e));
+ return true;
}
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
-do_resize(size_type size)
-{
- resize_imp(resize_base::get_nearest_larger_size(
- size));
-}
+do_resize(size_type n)
+{ resize_imp(resize_base::get_nearest_larger_size(n)); }
PB_DS_CLASS_T_DEC
inline void
try
{
- resize_imp(resize_base::get_new_size( m_num_e, m_num_used_e));
+ resize_imp(resize_base::get_new_size(m_num_e, m_num_used_e));
}
- catch(...)
+ catch (...)
{ }
_GLIBCXX_DEBUG_ONLY(assert_valid();)
- }
+}
PB_DS_CLASS_T_DEC
void
{
#ifdef PB_DS_REGRESSION
typename Allocator::group_throw_prob_adjustor adjust(m_num_e);
-#endif // #ifdef PB_DS_REGRESSION
+#endif
if (new_size == m_num_e)
return;
_GLIBCXX_DEBUG_ONLY(assert_valid();)
-
- const size_type old_size = m_num_e;
-
+ const size_type old_size = m_num_e;
entry_array a_entries_resized = NULL;
// Following line might throw an exception.
-
a_entries_resized = s_entry_allocator.allocate(new_size);
ranged_probe_fn_base::notify_resized(new_size);
-
m_num_e = new_size;
for (size_type i = 0; i < m_num_e; ++i)
{
resize_imp(a_entries_resized, old_size);
}
- catch(...)
+ catch (...)
{
erase_all_valid_entries(a_entries_resized, new_size);
-
m_num_e = old_size;
-
s_entry_allocator.deallocate(a_entries_resized, new_size);
-
ranged_probe_fn_base::notify_resized(old_size);
-
throw;
}
// At this point no exceptions can be thrown.
-
_GLIBCXX_DEBUG_ONLY(assert_entry_array_valid(a_entries_resized, traits_base::m_store_extra_indicator);)
- Resize_Policy::notify_resized(new_size);
-
- erase_all_valid_entries(m_a_entries, old_size);
-
- s_entry_allocator.deallocate(m_a_entries, old_size);
-
- m_a_entries = a_entries_resized;
-
+ Resize_Policy::notify_resized(new_size);
+ erase_all_valid_entries(m_entries, old_size);
+ s_entry_allocator.deallocate(m_entries, old_size);
+ m_entries = a_entries_resized;
_GLIBCXX_DEBUG_ONLY(assert_valid();)
- }
+}
PB_DS_CLASS_T_DEC
void
resize_imp(entry_array a_entries_resized, size_type old_size)
{
for (size_type pos = 0; pos < old_size; ++pos)
- if (m_a_entries[pos].m_stat == valid_entry_status)
- resize_imp_reassign(m_a_entries + pos, a_entries_resized, traits_base::m_store_extra_indicator);
+ if (m_entries[pos].m_stat == valid_entry_status)
+ resize_imp_reassign(m_entries + pos, a_entries_resized,
+ traits_base::m_store_extra_indicator);
}
#include <ext/pb_ds/detail/gp_hash_table_map_/resize_no_store_hash_fn_imps.hpp>
{
std::cerr << static_cast<unsigned long>(i) << " ";
- switch(m_a_entries[i].m_stat)
+ switch(m_entries[i].m_stat)
{
case empty_entry_status:
std::cerr << "<empty>";
std::cerr << "<erased>";
break;
case valid_entry_status:
- std::cerr << PB_DS_V2F(m_a_entries[i].m_value);
+ std::cerr << PB_DS_V2F(m_entries[i].m_value);
break;
default:
_GLIBCXX_DEBUG_ASSERT(0);
void
PB_DS_CLASS_C_DEC::
swap(PB_DS_CLASS_C_DEC& other)
-{
- mask_based_base::swap(other);
-}
+{ mask_based_base::swap(other); }
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
notify_resized(size_type size)
-{
- mask_based_base::notify_resized(size);
-}
+{ mask_based_base::notify_resized(size); }
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::size_type
PB_DS_CLASS_C_DEC::
operator()(size_type hash) const
-{
- return (mask_based_base::range_hash(hash));
-}
+{ return mask_based_base::range_hash(hash); }
void
PB_DS_CLASS_C_DEC::
swap(PB_DS_CLASS_C_DEC& other)
-{
- mod_based_base::swap(other);
-}
+{ mod_based_base::swap(other); }
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
-notify_resized(size_type size)
-{
- mod_based_base::notify_resized(size);
-}
+notify_resized(size_type n)
+{ mod_based_base::notify_resized(n); }
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::size_type
PB_DS_CLASS_C_DEC::
operator()(size_type hash) const
-{
- return (mod_based_base::range_hash(hash));
-}
+{ return mod_based_base::range_hash(hash); }
namespace pb_ds
{
-
namespace detail
{
-
-#define PB_DS_CLASS_T_DEC \
- template<typename Size_Type>
-
-#define PB_DS_CLASS_C_DEC \
- mask_based_range_hashing< \
- Size_Type>
+#define PB_DS_CLASS_T_DEC template<typename Size_Type>
+#define PB_DS_CLASS_C_DEC mask_based_range_hashing<Size_Type>
template<typename Size_Type>
class mask_based_range_hashing
protected:
typedef Size_Type size_type;
- protected:
void
- swap(PB_DS_CLASS_C_DEC& other);
+ swap(mask_based_range_hashing& other)
+ { std::swap(m_mask, other.m_mask); }
void
notify_resized(size_type size);
inline size_type
- range_hash(size_type hash) const;
+ range_hash(size_type hash) const
+ { return size_type(hash & m_mask); }
private:
- size_type m_mask;
-
- const static size_type s_num_bits_in_size_type;
-
- const static size_type s_highest_bit_1;
+ size_type m_mask;
+ const static size_type s_num_bits_in_size_type;
+ const static size_type s_highest_bit_1;
};
PB_DS_CLASS_T_DEC
sizeof(typename PB_DS_CLASS_C_DEC::size_type) << 3;
PB_DS_CLASS_T_DEC
- const typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC::s_highest_bit_1 =
- static_cast<typename PB_DS_CLASS_C_DEC::size_type>(1) << (s_num_bits_in_size_type - 1);
-
- PB_DS_CLASS_T_DEC
- void
- PB_DS_CLASS_C_DEC::
- swap(PB_DS_CLASS_C_DEC& other)
- {
- std::swap(m_mask, other.m_mask);
- }
+ const typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC::s_highest_bit_1 = static_cast<typename PB_DS_CLASS_C_DEC::size_type>(1) << (s_num_bits_in_size_type - 1);
+
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
notify_resized(size_type size)
{
size_type i = 0;
-
while (size ^ s_highest_bit_1)
{
size <<= 1;
-
++i;
}
m_mask = 1;
-
i += 2;
-
while (i++ < s_num_bits_in_size_type)
m_mask = (m_mask << 1) ^ 1;
}
- PB_DS_CLASS_T_DEC
- inline typename PB_DS_CLASS_C_DEC::size_type
- PB_DS_CLASS_C_DEC::
- range_hash(size_type hash) const
- {
- return (hash& m_mask);
- }
-
#undef PB_DS_CLASS_T_DEC
#undef PB_DS_CLASS_C_DEC
} // namespace detail
-
} // namespace pb_ds
-#endif // #ifndef PB_DS_MASK_BASED_RANGE_HASHING_HPP
+#endif
namespace detail
{
template<typename Key,
- class Hash_Fn,
- class Allocator,
- class Comb_Probe_Fn,
- class Probe_Fn,
+ typename Hash_Fn,
+ typename Allocator,
+ typename Comb_Probe_Fn,
+ typename Probe_Fn,
bool Store_Hash>
class ranged_probe_fn;
-#define PB_DS_CLASS_T_DEC \
- template< \
- typename Key, \
- class Hash_Fn, \
- class Allocator, \
- class Comb_Probe_Fn, \
- class Probe_Fn>
-
-#define PB_DS_CLASS_C_DEC \
- ranged_probe_fn< \
- Key, \
- Hash_Fn, \
- Allocator, \
- Comb_Probe_Fn, \
- Probe_Fn, \
- false>
+#define PB_DS_CLASS_T_DEC \
+ template<typename Key, typename Hash_Fn, typename Allocator, \
+ typename Comb_Probe_Fn, typename Probe_Fn>
+
+#define PB_DS_CLASS_C_DEC \
+ ranged_probe_fn<Key, Hash_Fn, Allocator, Comb_Probe_Fn, Probe_Fn, false>
/**
* Specialization 1- The client supplies a probe function and a ranged
* probe function, and requests that hash values not be stored.
**/
- template<typename Key,
- class Hash_Fn,
- class Allocator,
- class Comb_Probe_Fn,
- class Probe_Fn>
- class ranged_probe_fn<
- Key,
- Hash_Fn,
- Allocator,
- Comb_Probe_Fn,
- Probe_Fn,
- false> : public Hash_Fn,
- public Comb_Probe_Fn,
- public Probe_Fn
+ template<typename Key, typename Hash_Fn, typename Allocator,
+ typename Comb_Probe_Fn, typename Probe_Fn>
+ class ranged_probe_fn<Key, Hash_Fn, Allocator, Comb_Probe_Fn,
+ Probe_Fn, false>
+ : public Hash_Fn, public Comb_Probe_Fn, public Probe_Fn
{
protected:
typedef typename Allocator::size_type size_type;
PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
ranged_probe_fn(size_type size)
- {
- Comb_Probe_Fn::notify_resized(size);
- }
+ { Comb_Probe_Fn::notify_resized(size); }
PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn) :
Hash_Fn(r_hash_fn)
- {
- Comb_Probe_Fn::notify_resized(size);
- }
+ { Comb_Probe_Fn::notify_resized(size); }
PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, const Comb_Probe_Fn& r_comb_probe_fn) :
Hash_Fn(r_hash_fn),
Comb_Probe_Fn(r_comb_probe_fn)
- {
- comb_probe_fn_base::notify_resized(size);
- }
+ { comb_probe_fn_base::notify_resized(size); }
PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
Hash_Fn(r_hash_fn),
Comb_Probe_Fn(r_comb_probe_fn),
Probe_Fn(r_probe_fn)
- {
- comb_probe_fn_base::notify_resized(size);
- }
+ { comb_probe_fn_base::notify_resized(size); }
PB_DS_CLASS_T_DEC
void
swap(PB_DS_CLASS_C_DEC& other)
{
comb_probe_fn_base::swap(other);
-
- std::swap((Hash_Fn& )(*this), (Hash_Fn& )other);
+ std::swap((Hash_Fn& )(*this), (Hash_Fn&)other);
}
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
notify_resized(size_type size)
- {
- comb_probe_fn_base::notify_resized(size);
- }
+ { comb_probe_fn_base::notify_resized(size); }
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::size_type
PB_DS_CLASS_C_DEC::
operator()(const_key_reference r_key) const
- {
- return (comb_probe_fn_base::operator()(
- hash_fn_base::operator()(r_key)));
- }
+ { return comb_probe_fn_base::operator()(hash_fn_base::operator()(r_key)); }
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::size_type
PB_DS_CLASS_C_DEC::
- operator()(const_key_reference /*r_key*/, size_type hash, size_type i) const
+ operator()(const_key_reference, size_type hash, size_type i) const
{
- return (comb_probe_fn_base::operator()(
- hash + probe_fn_base::operator()(i)));
+ return comb_probe_fn_base::operator()(hash + probe_fn_base::operator()(i));
}
#undef PB_DS_CLASS_T_DEC
#undef PB_DS_CLASS_C_DEC
-#define PB_DS_CLASS_T_DEC \
- template< \
- typename Key, \
- class Hash_Fn, \
- class Allocator, \
- class Comb_Probe_Fn, \
- class Probe_Fn>
-
-#define PB_DS_CLASS_C_DEC \
- ranged_probe_fn< \
- Key, \
- Hash_Fn, \
- Allocator, \
- Comb_Probe_Fn, \
- Probe_Fn, \
- true>
+#define PB_DS_CLASS_T_DEC \
+ template<typename Key, class Hash_Fn, class Allocator, \
+ class Comb_Probe_Fn, class Probe_Fn>
+
+#define PB_DS_CLASS_C_DEC \
+ ranged_probe_fn<Key, Hash_Fn, Allocator, Comb_Probe_Fn, Probe_Fn, true>
/**
* Specialization 2- The client supplies a probe function and a ranged
* probe function, and requests that hash values not be stored.
**/
- template<typename Key,
- class Hash_Fn,
- class Allocator,
- class Comb_Probe_Fn,
- class Probe_Fn>
- class ranged_probe_fn<
- Key,
- Hash_Fn,
- Allocator,
- Comb_Probe_Fn,
- Probe_Fn,
- true> :
- public Hash_Fn,
- public Comb_Probe_Fn,
- public Probe_Fn
+ template<typename Key, typename Hash_Fn, typename Allocator,
+ typename Comb_Probe_Fn, typename Probe_Fn>
+ class ranged_probe_fn<Key, Hash_Fn, Allocator, Comb_Probe_Fn,
+ Probe_Fn, true>
+ : public Hash_Fn, public Comb_Probe_Fn, public Probe_Fn
{
protected:
typedef typename Allocator::size_type size_type;
typedef typename key_allocator::const_reference const_key_reference;
- protected:
ranged_probe_fn(size_type size);
ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn);
- ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, const Comb_Probe_Fn& r_comb_probe_fn);
+ ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn,
+ const Comb_Probe_Fn& r_comb_probe_fn);
- ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, const Comb_Probe_Fn& r_comb_probe_fn, const Probe_Fn& r_probe_fn);
+ ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn,
+ const Comb_Probe_Fn& r_comb_probe_fn,
+ const Probe_Fn& r_probe_fn);
void
swap(PB_DS_CLASS_C_DEC& other);
PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
- ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, const Comb_Probe_Fn& r_comb_probe_fn) :
+ ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn,
+ const Comb_Probe_Fn& r_comb_probe_fn) :
Hash_Fn(r_hash_fn),
Comb_Probe_Fn(r_comb_probe_fn)
{ comb_probe_fn_base::notify_resized(size); }
PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
- ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn, const Comb_Probe_Fn& r_comb_probe_fn, const Probe_Fn& r_probe_fn) :
+ ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn,
+ const Comb_Probe_Fn& r_comb_probe_fn,
+ const Probe_Fn& r_probe_fn) :
Hash_Fn(r_hash_fn),
Comb_Probe_Fn(r_comb_probe_fn),
Probe_Fn(r_probe_fn)
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::size_type
PB_DS_CLASS_C_DEC::
- operator()(const_key_reference /*r_key*/, size_type hash, size_type i) const
+ operator()(const_key_reference, size_type hash, size_type i) const
{
return comb_probe_fn_base::operator()(hash + probe_fn_base::operator()(i));
}
#undef PB_DS_CLASS_T_DEC
#undef PB_DS_CLASS_C_DEC
-#define PB_DS_CLASS_T_DEC \
- template<typename Key, class Allocator, class Comb_Probe_Fn>
-
-#define PB_DS_CLASS_C_DEC \
- ranged_probe_fn< \
- Key, \
- null_hash_fn, \
- Allocator, \
- Comb_Probe_Fn, \
- null_probe_fn, \
- false>
-
/**
* Specialization 3 and 4- The client does not supply a hash function or
* probe function, and requests that hash values not be stored.
**/
- template<typename Key, class Allocator, class Comb_Probe_Fn>
- class ranged_probe_fn<
- Key,
- null_hash_fn,
- Allocator,
- Comb_Probe_Fn,
- null_probe_fn,
- false> :
- public Comb_Probe_Fn,
- public null_hash_fn,
- public null_probe_fn
+ template<typename Key, typename Allocator, typename Comb_Probe_Fn>
+ class ranged_probe_fn<Key, null_hash_fn, Allocator, Comb_Probe_Fn,
+ null_probe_fn, false>
+ : public Comb_Probe_Fn, public null_hash_fn, public null_probe_fn
{
protected:
typedef typename Allocator::size_type size_type;
typedef typename key_allocator::const_reference const_key_reference;
- protected:
- ranged_probe_fn(size_type size);
+ ranged_probe_fn(size_type size)
+ { Comb_Probe_Fn::notify_resized(size); }
- ranged_probe_fn(size_type size, const Comb_Probe_Fn& r_comb_probe_fn);
+ ranged_probe_fn(size_type size, const Comb_Probe_Fn& r_comb_probe_fn)
+ : Comb_Probe_Fn(r_comb_probe_fn)
+ { }
- ranged_probe_fn(size_type size, const null_hash_fn& r_null_hash_fn, const Comb_Probe_Fn& r_comb_probe_fn, const null_probe_fn& r_null_probe_fn);
+ ranged_probe_fn(size_type size, const null_hash_fn& r_null_hash_fn,
+ const Comb_Probe_Fn& r_comb_probe_fn,
+ const null_probe_fn& r_null_probe_fn)
+ : Comb_Probe_Fn(r_comb_probe_fn)
+ { }
void
- swap(PB_DS_CLASS_C_DEC& other);
+ swap(ranged_probe_fn& other)
+ { comb_probe_fn_base::swap(other); }
};
-
- PB_DS_CLASS_T_DEC
- PB_DS_CLASS_C_DEC::
- ranged_probe_fn(size_type size)
- { Comb_Probe_Fn::notify_resized(size); }
-
- PB_DS_CLASS_T_DEC
- PB_DS_CLASS_C_DEC::
- ranged_probe_fn(size_type size, const Comb_Probe_Fn& r_comb_probe_fn) :
- Comb_Probe_Fn(r_comb_probe_fn)
- { }
-
- PB_DS_CLASS_T_DEC
- PB_DS_CLASS_C_DEC::
- ranged_probe_fn(size_type size, const null_hash_fn& r_null_hash_fn, const Comb_Probe_Fn& r_comb_probe_fn, const null_probe_fn& r_null_probe_fn) :
- Comb_Probe_Fn(r_comb_probe_fn)
- { }
-
- PB_DS_CLASS_T_DEC
- void
- PB_DS_CLASS_C_DEC::
- swap(PB_DS_CLASS_C_DEC& other)
- { comb_probe_fn_base::swap(other); }
-
-#undef PB_DS_CLASS_T_DEC
-#undef PB_DS_CLASS_C_DEC
} // namespace detail
} // namespace pb_ds
if (pot_it != end()&& !Cmp_Fn::operator()(r_key, PB_DS_V2F(*pot_it)))
{
_GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(r_key));
- return (++pot_it);
+ return ++pot_it;
}
_GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key));
inline const_point_iterator
upper_bound(const_key_reference r_key) const
- { return const_cast<PB_DS_CLASS_C_DEC& >(*this).upper_bound(r_key); }
+ { return const_cast<PB_DS_CLASS_C_DEC&>(*this).upper_bound(r_key); }
inline point_iterator
find(const_key_reference r_key)
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
iterator pot_it = lower_bound(r_key);
- if (pot_it != end()&& !Cmp_Fn::operator()(r_key, PB_DS_V2F(*pot_it)))
+ if (pot_it != end() && !Cmp_Fn::operator()(r_key, PB_DS_V2F(*pot_it)))
{
_GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(r_key));
- return (pot_it);
+ return pot_it;
}
_GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key));
PB_DS_CLASS_T_DEC
inline
PB_DS_CLASS_C_DEC::
-hash_prime_size_policy(size_type start_size) : m_start_size(start_size)
-{ m_start_size = get_nearest_larger_size(start_size); }
+hash_prime_size_policy(size_type n) : m_start_size(n)
+{ m_start_size = get_nearest_larger_size(n); }
PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_T_DEC
inline PB_DS_CLASS_C_DEC::size_type
PB_DS_CLASS_C_DEC::
-get_nearest_larger_size(size_type size) const
+get_nearest_larger_size(size_type n) const
{
const std::size_t* const p_upper = std::upper_bound(detail::g_a_sizes,
- detail::g_a_sizes + detail::num_distinct_sizes, size);
+ detail::g_a_sizes + detail::num_distinct_sizes, n);
if (p_upper == detail::g_a_sizes + detail::num_distinct_sizes)
throw resize_error();
PB_DS_CLASS_T_DEC
inline PB_DS_CLASS_C_DEC::size_type
PB_DS_CLASS_C_DEC::
-get_nearest_smaller_size(size_type size) const
+get_nearest_smaller_size(size_type n) const
{
const size_t* p_lower = std::lower_bound(detail::g_a_sizes,
- detail::g_a_sizes + detail::num_distinct_sizes, size);
+ detail::g_a_sizes + detail::num_distinct_sizes, n);
- if (*p_lower >= size&& p_lower != detail::g_a_sizes)
+ if (*p_lower >= n && p_lower != detail::g_a_sizes)
--p_lower;
if (*p_lower < m_start_size)
return m_start_size;
PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
-hash_standard_resize_policy() :
- m_size(Size_Policy::get_nearest_larger_size(1))
+hash_standard_resize_policy()
+: m_size(Size_Policy::get_nearest_larger_size(1))
{ trigger_policy_base::notify_externally_resized(m_size); }
PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
-hash_standard_resize_policy(const Size_Policy& r_size_policy) :
- Size_Policy(r_size_policy),
- m_size(Size_Policy::get_nearest_larger_size(1))
+hash_standard_resize_policy(const Size_Policy& r_size_policy)
+: Size_Policy(r_size_policy), m_size(Size_Policy::get_nearest_larger_size(1))
{ trigger_policy_base::notify_externally_resized(m_size); }
PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
hash_standard_resize_policy(const Size_Policy& r_size_policy,
- const Trigger_Policy& r_trigger_policy) :
- Size_Policy(r_size_policy),
- Trigger_Policy(r_trigger_policy),
+ const Trigger_Policy& r_trigger_policy)
+: Size_Policy(r_size_policy), Trigger_Policy(r_trigger_policy),
m_size(Size_Policy::get_nearest_larger_size(1))
{ trigger_policy_base::notify_externally_resized(m_size); }
PB_DS_CLASS_C_DEC::
get_new_size(size_type size, size_type num_used_e) const
{
- if (trigger_policy_base::
- is_grow_needed(size, num_used_e))
+ if (trigger_policy_base::is_grow_needed(size, num_used_e))
return size_policy_base::get_nearest_larger_size(size);
return size_policy_base::get_nearest_smaller_size(size);
}
resize(size_type new_size)
{
PB_DS_STATIC_ASSERT(access, external_size_access);
- size_type actual_new_size = size_policy_base::get_nearest_larger_size(1);
- while (actual_new_size < new_size)
+ size_type actual_size = size_policy_base::get_nearest_larger_size(1);
+ while (actual_size < new_size)
{
- const size_type pot =
- size_policy_base::get_nearest_larger_size(actual_new_size);
+ const size_type pot = size_policy_base::get_nearest_larger_size(actual_size);
- if (pot == actual_new_size&& pot < new_size)
+ if (pot == actual_size && pot < new_size)
throw resize_error();
- actual_new_size = pot;
+ actual_size = pot;
}
- if (actual_new_size > 0)
- --actual_new_size;
+ if (actual_size > 0)
+ --actual_size;
const size_type old_size = m_size;
try
{
- do_resize(actual_new_size - 1);
+ do_resize(actual_size - 1);
}
catch(insert_error& )
{
{
namespace detail
{
-
- template<typename Key, typename Mapped, class Allocator, bool Store_Extra>
+ template<typename Key, typename Mapped, typename Alloc, bool Store_Extra>
struct vt_base_selector
{
- typedef value_type_base< Key, Mapped, Allocator, Store_Extra> type;
+ typedef value_type_base<Key, Mapped, Alloc, Store_Extra> type;
};
- template<typename Key, typename Mapped, class Allocator, bool Store_Extra>
+ template<typename Key, typename Mapped, typename Alloc, bool Store_Extra>
struct types_traits
- : public vt_base_selector<Key, Mapped, Allocator, Store_Extra>::type
+ : public vt_base_selector<Key, Mapped, Alloc, Store_Extra>::type
{
- typedef typename Allocator::template rebind< Key>::other key_allocator;
-
+ typedef typename Alloc::template rebind< Key>::other key_allocator;
typedef typename key_allocator::value_type key_type;
-
typedef typename key_allocator::pointer key_pointer;
-
typedef typename key_allocator::const_pointer const_key_pointer;
-
typedef typename key_allocator::reference key_reference;
-
typedef typename key_allocator::const_reference const_key_reference;
-
- typedef typename Allocator::size_type size_type;
-
+ typedef typename Alloc::size_type size_type;
typedef false_type store_extra_false_type;
-
typedef true_type store_extra_true_type;
-
- integral_constant<int,Store_Extra> m_store_extra_indicator;
-
typedef false_type no_throw_copies_false_type;
-
typedef true_type no_throw_copies_true_type;
- typename no_throw_copies<Key, Mapped>::indicator
- m_no_throw_copies_indicator;
+ integral_constant<int, Store_Extra> m_store_extra_indicator;
+ typename no_throw_copies<Key, Mapped>::indicator m_no_throw_copies_indicator;
// Extra value (used when the extra value is stored with each value).
- typedef typename comp_hash_< size_type>::comp_hash comp_hash;
+ typedef typename comp_hash_<size_type>::comp_hash comp_hash;
};
} // namespace detail
static void
throw_conditionally();
+ // See if a particular address and size has been allocated by this
+ // allocator.
static void
- assert_allocatod(const void*, size_t);
+ check_allocated(void*, size_t);
+ // See if a given label has been allocated by this allocator.
static void
- check_allocated(void*, size_t);
+ check_allocated(size_t);
private:
typedef std::pair<size_t, size_t> alloc_data_type;
class throw_allocator : public throw_allocator_base
{
public:
- typedef size_t size_type;
- typedef ptrdiff_t difference_type;
- typedef T* pointer;
- typedef const T* const_pointer;
- typedef T& reference;
- typedef const T& const_reference;
- typedef T value_type;
+ typedef size_t size_type;
+ typedef ptrdiff_t difference_type;
+ typedef T value_type;
+ typedef value_type* pointer;
+ typedef const value_type* const_pointer;
+ typedef value_type& reference;
+ typedef const value_type& const_reference;
+
template<typename U>
struct rebind
throw_allocator() throw() { }
- throw_allocator(const throw_allocator<T>&) throw() { }
+ throw_allocator(const throw_allocator&) throw() { }
- template <class U>
+ template<typename U>
throw_allocator(const throw_allocator<U>&) throw() { }
~throw_allocator() throw() { }
size_type
max_size() const throw()
- { return std::allocator<T>().max_size(); }
+ { return std::allocator<value_type>().max_size(); }
pointer
allocate(size_type num, std::allocator<void>::const_pointer hint = 0)
{
throw_conditionally();
- T* const a = std::allocator<T>().allocate(num, hint);
- insert(a, sizeof(T) * num);
+ value_type* const a = std::allocator<value_type>().allocate(num, hint);
+ insert(a, sizeof(value_type) * num);
return a;
}
void
construct(pointer p, const T& val)
- { return std::allocator<T>().construct(p, val); }
+ { return std::allocator<value_type>().construct(p, val); }
void
destroy(pointer p)
- { std::allocator<T>().destroy(p); }
+ { std::allocator<value_type>().destroy(p); }
void
deallocate(pointer p, size_type num)
{
- erase(p, sizeof(T) * num);
- std::allocator<T>().deallocate(p, num);
+ erase(p, sizeof(value_type) * num);
+ std::allocator<value_type>().deallocate(p, num);
}
void
check_allocated(pointer p, size_type num)
- { throw_allocator_base::check_allocated(p, sizeof(T) * num); }
+ { throw_allocator_base::check_allocated(p, sizeof(value_type) * num); }
+
+ void
+ check_allocated(size_type label)
+ { throw_allocator_base::check_allocated(label); }
};
template<typename T>
const_iterator found_it = _S_map.find(p);
if (found_it == _S_map.end())
{
- std::string error("throw_allocator_base::check_allocated");
+ std::string error("throw_allocator_base::check_allocated by value ");
error += "null erase!";
error += '\n';
print_to_string(error, make_entry(p, size));
if (found_it->second.second != size)
{
- std::string error("throw_allocator_base::check_allocated");
+ std::string error("throw_allocator_base::check_allocated by value ");
error += "wrong-size erase!";
error += '\n';
print_to_string(error, make_entry(p, size));
}
void
+ throw_allocator_base::check_allocated(size_t label)
+ {
+ std::string found;
+ const_iterator it = _S_map.begin();
+ while (it != _S_map.end())
+ {
+ if (it->second.first == label)
+ print_to_string(found, *it);
+ ++it;
+ }
+
+ if (!found.empty())
+ {
+ std::string error("throw_allocator_base::check_allocated by label ");
+ error += '\n';
+ error += found;
+ throw std::logic_error(error);
+ }
+ }
+
+ void
throw_allocator_base::throw_conditionally()
{
if (_S_g.get_prob() < _S_throw_prob)
void
throw_allocator_base::print_to_string(std::string& s)
{
- const_iterator it = throw_allocator_base::_S_map.begin();
- const_iterator end_it = throw_allocator_base::_S_map.end();
- for (; it != end_it; ++it)
- print_to_string(s, *it);
- s += '\n';
+ const_iterator begin = throw_allocator_base::_S_map.begin();
+ const_iterator end = throw_allocator_base::_S_map.end();
+ for (; begin != end; ++begin)
+ print_to_string(s, *begin);
}
void
throw_allocator_base::print_to_string(std::string& s, const_reference ref)
{
- s += reinterpret_cast<const unsigned long>(ref.first);
- s += ": ";
- s += ref.second.first ;
- s += ", ";
- s += ref.second.second;
+ char buf[40];
+ const char tab('\t');
+ s += "address: ";
+ sprintf(buf, "%p", ref.first);
+ s += buf;
+ s += tab;
+ s += "label: ";
+ sprintf(buf, "%u", ref.second.first);
+ s += buf;
+ s += tab;
+ s += "size: ";
+ sprintf(buf, "%u", ref.second.second);
+ s += buf;
s += '\n';
}
{
namespace detail
{
- template<typename Type>
- struct type_to_type
- {
- typedef Type type;
- };
-
template<typename Fn, typename Typelist_Chain>
struct apply_;
void
operator() (Fn& f)
{
- f.operator()(type_to_type<Hd>());
+ f.operator()(Hd());
apply_<Fn, Tl> next;
next(f);
}
h.resize(20); // { dg-error "instantiated from" }
}
-// { dg-error "invalid" "" { target *-*-* } 199 }
+// { dg-error "invalid" "" { target *-*-* } 196 }
// { dg-excess-errors "member function" }
{
xml_test_performance_formatter fmt("Size", "Memory (bytes)");
- typedef std::vector< int> vec_t;
+ typedef std::vector<int> vec_t;
vec_t a_v(vm);
twister_rand_gen g;
for (size_t i = 0; i < vm; ++i)
erase_test<vec_t::const_iterator> tst(b, vn, vs, vm);
typedef mem_track_allocator<char> alloc_t;
{
- typedef
- hash_common_types<int, pb_ds::null_mapped_type, int_hash,
- std::equal_to<int>, alloc_t>::performance_tl
- tl_t;
+ typedef hash_common_types<int, pb_ds::null_mapped_type, int_hash, std::equal_to<int>, alloc_t>::performance_tl tl_t;
tl_t tl;
__gnu_cxx::typelist::apply(tst, tl);
}
{
- typedef
- native_hash_set<int, 8, int_hash,
- std::equal_to<int>,
- std::less<int>, alloc_t>
- native_t;
+ typedef native_hash_set<int, 8, int_hash, std::equal_to<int>, std::less<int>, alloc_t> native_t;
- tst(__gnu_cxx::typelist::detail::type_to_type<native_t>());
+ tst(native_t());
}
}
catch (...)
usage()
{
using namespace std;
- cerr << "usage: hash_random_int_erase_if_test <vn> <vs> <vm>" <<
- endl << endl;
-
- cerr <<
- "This test checks the performance of various associative containers "
- "using their erase method. " << endl;
- cerr << "Specifically, it does the following:" << endl;
- cerr << "* Creates a vector of random integers " << endl;
- cerr << "* Inserts the elements into the container" << endl;
- cerr << "* Erases all the elements, except one, from the constainer" << endl;
-
- cerr << endl << endl;
+ cerr << "usage: hash_random_int_erase_if_test <vn> <vs> <vm>"
+ << endl << endl;
+
+ cerr << "This test checks the performance of various associative containers "
+ "using their erase method. " << endl;
+ cerr << "Specifically, it does the following:" << endl;
+ cerr << "* Creates a vector of random integers " << endl;
+ cerr << "* Inserts the elements into the container" << endl;
+ cerr << "* Erases all the elements, except one, from the constainer"
+ << endl << endl;
cerr << "vn = minimum size of the vector" << endl;
cerr << "vs = step size of the vector" << endl;
typedef find_test<vec_t::const_iterator> test_t;
test_t tst(b, b, vn, vs, vm, vn, vs, vm);
{
- typedef native_hash_map< int, char> native_t;
- tst(__gnu_cxx::typelist::detail::type_to_type<native_t>());
+ typedef native_hash_map<int, char> native_t;
+ tst(native_t());
}
{
typedef native_hash_multimap<std::string, int, 8, string_hash_fn> native_t;
typedef multimap_find_test<vec_t::const_iterator, true> test_type;
test_type tst(b, prm* ratio_n, prm* ratio_s, prm* ratio_m);
- tst(__gnu_cxx::typelist::detail::type_to_type<native_t>());
+ tst(native_t());
}
{
typedef native_multimap<std::string, int> native_t;
typedef multimap_find_test<vec_t::const_iterator, true> test_type;
test_type tst(b, prm* ratio_n, prm* ratio_s, prm* ratio_m);
- tst(__gnu_cxx::typelist::detail::type_to_type<native_t>());
+ tst(native_t());
}
}
catch (...)
test_type tst(b, prm* ratio_n, prm* ratio_s, prm* ratio_m);
{
typedef native_multimap<string_t, int, std::less<string_t>, alloc_t> native_t;
- tst(__gnu_cxx::typelist::detail::type_to_type<native_t>());
+ tst(native_t());
}
{
alloc_t>
native_t;
- tst(__gnu_cxx::typelist::detail::type_to_type<native_t>());
+ tst(native_t());
}
}
catch (...)
typedef native_hash_multimap<std::string, int, 8, string_hash_fn> native_t;
typedef multimap_insert_test<vec_t::const_iterator, true> test_type;
test_type tst(b, prm* ratio_n, prm* ratio_s, prm* ratio_m);
- tst(__gnu_cxx::typelist::detail::type_to_type<native_t>());
+ tst(native_t());
}
{
typedef native_multimap<std::string, int> native_t;
typedef multimap_insert_test<vec_t::const_iterator, true> test_type;
test_type tst(b, prm* ratio_n, prm* ratio_s, prm* ratio_m);
- tst(__gnu_cxx::typelist::detail::type_to_type<native_t>());
+ tst(native_t());
}
}
catch (...)
{
typedef native_priority_queue<int, true> native_pq_t;
- tst(__gnu_cxx::typelist::detail::type_to_type<native_pq_t>());
+ tst(native_pq_t());
}
{
typedef native_priority_queue<int, false> native_pq_t;
- tst(__gnu_cxx::typelist::detail::type_to_type<native_pq_t>());
+ tst(native_pq_t());
}
}
catch(...)
{
typedef native_priority_queue<int, true> native_pq_t;
- tst(__gnu_cxx::typelist::detail::type_to_type<native_pq_t>());
+ tst(native_pq_t());
}
{
typedef native_priority_queue<int, false> native_pq_t;
- tst(__gnu_cxx::typelist::detail::type_to_type<native_pq_t>());
+ tst(native_pq_t());
}
}
catch (...)
{
typedef native_priority_queue<std::string, true> native_pq_t;
- tst(__gnu_cxx::typelist::detail::type_to_type<native_pq_t>());
+ tst(native_pq_t());
}
{
typedef native_priority_queue<std::string, false> native_pq_t;
- tst(__gnu_cxx::typelist::detail::type_to_type<native_pq_t>());
+ tst(native_pq_t());
}
}
catch(...)
{
typedef native_priority_queue<std::string, true> native_pq_t;
- tst(__gnu_cxx::typelist::detail::type_to_type<native_pq_t>());
+ tst(native_pq_t());
}
{
typedef native_priority_queue<std::string, false> native_pq_t;
- tst(__gnu_cxx::typelist::detail::type_to_type<native_pq_t>());
+ tst(native_pq_t());
}
}
catch (...)
{
typedef native_priority_queue<string_t, true, std::less<string_t>, mem_track_allocator<string_t> > native_pq_t;
- tst(__gnu_cxx::typelist::detail::type_to_type<native_pq_t>());
+ tst(native_pq_t());
}
{
typedef native_priority_queue<string_t, false, std::less<string_t>, mem_track_allocator<string_t> > native_pq_t;
- tst(__gnu_cxx::typelist::detail::type_to_type<native_pq_t>());
+ tst(native_pq_t());
}
}
catch (...)
{
typedef native_priority_queue<std::string, true> native_pq_t;
- tst(__gnu_cxx::typelist::detail::type_to_type<native_pq_t>());
+ tst(native_pq_t());
}
{
typedef native_priority_queue<std::string, false> native_pq_t;
- tst(__gnu_cxx::typelist::detail::type_to_type<native_pq_t>());
+ tst(native_pq_t());
}
}
catch(...)
{
typedef native_priority_queue<std::string, true> native_pq_t;
- tst(__gnu_cxx::typelist::detail::type_to_type<native_pq_t>());
+ tst(native_pq_t());
}
{
typedef native_priority_queue<std::string, false> native_pq_t;
- tst(__gnu_cxx::typelist::detail::type_to_type<native_pq_t>());
+ tst(native_pq_t());
}
}
catch(...)
test_t tst(b, b, vn, vs, vm, vn, vs, vm);
{
typedef native_hash_map< int, char> native_t;
- tst(__gnu_cxx::typelist::detail::type_to_type<native_t>());
+ tst(native_t());
}
{
typedef native_map< int, char> native_t;
- tst(__gnu_cxx::typelist::detail::type_to_type<native_t>());
+ tst(native_t());
}
{
{
typedef native_hash_map<int, size_t> native_t;
- tst(__gnu_cxx::typelist::detail::type_to_type<native_t>());
+ tst(native_t());
}
{
typedef native_map< int, size_t> native_t;
- tst(__gnu_cxx::typelist::detail::type_to_type<native_t>());
+ tst(native_t());
}
}
catch (...)
{
typedef native_hash_map< int, size_t> native_t;
- tst(__gnu_cxx::typelist::detail::type_to_type<native_t>());
+ tst(native_t());
}
{
typedef native_map< int, size_t> native_t;
- tst(__gnu_cxx::typelist::detail::type_to_type<native_t>());
+ tst(native_t());
}
}
catch(...)
{
typedef native_map<std::string, char> native_map_t;
- tst(__gnu_cxx::typelist::detail::type_to_type<native_map_t>());
+ tst(native_map_t());
#ifdef PB_DS_USE_TR1
typedef native_hash_map<std::string, char, 8, string_hash_fn> native_hash_map_t;
- tst(__gnu_cxx::typelist::detail::type_to_type<native_hash_map_t>());
+ tst(native_hash_map_t());
typedef
native_hash_map<
true>
sth_native_hash_map_t;
- tst(__gnu_cxx::typelist::detail::type_to_type<sth_native_hash_map_t>());
+ tst(sth_native_hash_map_t());
#endif
}
}
typedef tree_order_statistics_test<false> test_t;
test_t tst(vn, vs, vm);
typedef native_set<int> native_set_t;
- tst(__gnu_cxx::typelist::detail::type_to_type<native_set_t>());
+ tst(native_set_t());
}
}
catch(...)
typedef tree_split_join_test<false> test_t;
test_t tst(vn, vs, vm);
typedef native_set<int> native_set_t;
- tst(__gnu_cxx::typelist::detail::type_to_type<native_set_t>());
+ tst(native_set_t());
}
}
catch(...)
{
typedef native_map<std::string, char> native_map_t;
- tst(__gnu_cxx::typelist::detail::type_to_type<native_map_t>());
+ tst(native_map_t());
}
}
catch (...)
test_t tst(b, b, vn, vs, vm, vn, vs, vm);
{
typedef native_map<std::string, char> native_set_t;
- tst(__gnu_cxx::typelist::detail::type_to_type<native_set_t>());
+ tst(native_set_t());
}
{
namespace pb_ds
{
-
namespace test
{
-
template<typename Key,
typename Data,
- class Hash_Fn =
- typename pb_ds::detail::default_hash_fn<
- Key>::type,
- class Eq_Fn =
- std::equal_to<Key>,
- class Allocator =
- std::allocator<std::pair<const Key, Data> > >
+ class Hash_Fn = typename pb_ds::detail::default_hash_fn<Key>::type,
+ class Eq_Fn = std::equal_to<Key>,
+ class Allocator = std::allocator<std::pair<const Key, Data> > >
struct hash_common_types
{
private:
namespace pb_ds
{
-
namespace test
{
-
-#define PB_DS_BASE_C_DEC \
- std::set< \
- Key, \
- Cmp_Fn, \
- typename Allocator::template rebind< \
- Key>::other>
-
template<typename Key, class Cmp_Fn = std::less<Key>,
- class Allocator =
- std::allocator<char> >
+ class Allocator = std::allocator<char> >
class native_set : public PB_DS_BASE_C_DEC
{
private:
- typedef PB_DS_BASE_C_DEC base_type;
+ typedef std::set<Key, Cmp_Fn, typename Allocator::template rebind<Key>::other> base_type;
public:
typedef native_tree_tag container_category;
- typedef typename PB_DS_BASE_C_DEC::const_iterator const_iterator;
+ typedef typename base_type::const_iterator const_iterator;
public:
native_set() : base_type()
static std::string
name()
- {
- return ("n_set");
- }
+ { return ("n_set"); }
static std::string
desc()
- {
- return (make_xml_tag( "type", "value", "std_set"));
- }
+ { return (make_xml_tag("type", "value", "std_set")); }
};
-
-#undef PB_DS_BASE_C_DEC
-
} // namespace test
-
} // namespace pb_ds
-#endif // #ifndef PB_DS_NATIVE_SET_HPP
+#endif
+
namespace pb_ds
{
-
namespace test
{
-
namespace detail
{
-
template<typename Cntnr>
struct pb_ds_string_form
{
private:
template<typename D_Cntnr>
static std::string
- name(__gnu_cxx::typelist::detail::type_to_type<D_Cntnr>)
- {
- return ("mmap_" + pb_ds_string_form<D_Cntnr>::name());
- }
+ name(D_Cntnr)
+ { return ("mmap_" + pb_ds_string_form<D_Cntnr>::name()); }
template<typename D_Cntnr>
static std::string
- desc(__gnu_cxx::typelist::detail::type_to_type<D_Cntnr>)
- {
- return (pb_ds_string_form<D_Cntnr>::desc());
- }
+ desc(D_Cntnr)
+ { return pb_ds_string_form<D_Cntnr>::desc(); }
static std::string
- name(__gnu_cxx::typelist::detail::type_to_type<size_t>)
- {
- return ("map");
- }
+ name(size_t)
+ { return ("map"); }
static std::string
- desc(__gnu_cxx::typelist::detail::type_to_type<size_t>)
- {
- return ("");
- }
+ desc(size_t)
+ { return (""); }
static std::string
- name(__gnu_cxx::typelist::detail::type_to_type<basic_type>)
- {
- return ("map");
- }
+ name(basic_type)
+ { return ("map"); }
static std::string
- desc(__gnu_cxx::typelist::detail::type_to_type<basic_type>)
- {
- return ("");
- }
+ desc(basic_type)
+ { return (""); }
static std::string
- name(__gnu_cxx::typelist::detail::type_to_type<int>)
- {
- return ("map");
- }
+ name(int)
+ { return ("map"); }
static std::string
- desc(__gnu_cxx::typelist::detail::type_to_type<int>)
- {
- return ("");
- }
+ desc(int)
+ { return (""); }
static std::string
- name(__gnu_cxx::typelist::detail::type_to_type<char>)
- {
- return ("map");
- }
+ name(char)
+ { return ("map"); }
static std::string
- desc(__gnu_cxx::typelist::detail::type_to_type<char>)
- {
- return ("");
- }
+ desc(char)
+ { return (""); }
static std::string
- name(__gnu_cxx::typelist::detail::type_to_type<pb_ds::null_mapped_type>)
- {
- return ("set");
- }
+ name(pb_ds::null_mapped_type)
+ { return ("set"); }
static std::string
- desc(__gnu_cxx::typelist::detail::type_to_type<pb_ds::null_mapped_type>)
- {
- return ("");
- }
+ desc(pb_ds::null_mapped_type)
+ { return (""); }
public:
static std::string
name()
- {
- return (name(__gnu_cxx::typelist::detail::type_to_type<mapped_type>()));
- }
+ { return name(mapped_type()); }
static std::string
desc()
- {
- return (desc(__gnu_cxx::typelist::detail::type_to_type<mapped_type>()));
- }
+ { return desc(mapped_type()); }
};
typedef
- detail::ds_string_form<
- Cntnr,
- typename Cntnr::container_category>
+ detail::ds_string_form<Cntnr, typename Cntnr::container_category>
ds_string_form_t;
public:
static std::string
name()
- {
- return (ds_string_form_t::name() + mapped_string_form::name());
- }
+ { return (ds_string_form_t::name() + mapped_string_form::name()); }
static std::string
desc()
- {
- return (ds_string_form_t::desc() + mapped_string_form::desc());
- }
+ { return (ds_string_form_t::desc() + mapped_string_form::desc()); }
};
template<typename Cntnr>
{
static std::string
name()
- {
- return (Cntnr::name());
- }
+ { return Cntnr::name(); }
static std::string
desc()
- {
- return (Cntnr::desc());
- }
+ { return Cntnr::desc(); }
};
template<typename Cntnr, class Tag>
- struct tag_select_string_form : public pb_ds_string_form<
- Cntnr>
+ struct tag_select_string_form : public pb_ds_string_form<Cntnr>
{ };
template<typename Cntnr>
- struct tag_select_string_form<
- Cntnr,
- native_hash_tag> : public native_string_form<
- Cntnr>
+ struct tag_select_string_form<Cntnr, native_hash_tag>
+ : public native_string_form<Cntnr>
{ };
template<typename Cntnr>
- struct tag_select_string_form<
- Cntnr,
- native_tree_tag> : public native_string_form<
- Cntnr>
+ struct tag_select_string_form<Cntnr, native_tree_tag>
+ : public native_string_form<Cntnr>
{ };
-
} // namespace detail
template<typename Cntnr>
- struct string_form : public detail::tag_select_string_form<
- Cntnr,
- typename Cntnr::container_category>
+ struct string_form
+ : public detail::tag_select_string_form<Cntnr,
+ typename Cntnr::container_category>
{ };
-
} // namespace test
-
} // namespace pb_ds
-#endif // #ifndef PB_DS_STRING_FORM_HPP
+#endif
namespace pb_ds
{
-
namespace test
{
-
template<typename Allocator>
- struct direct_mask_range_hashing_t_ : public pb_ds::direct_mask_range_hashing<
- typename Allocator::size_type>
+ struct direct_mask_range_hashing_t_
+ : public pb_ds::direct_mask_range_hashing<typename Allocator::size_type>
{
- typedef
- pb_ds::direct_mask_range_hashing<
- typename Allocator::size_type>
- base_type;
+ typedef typename Allocator::size_type size_type;
+ typedef pb_ds::direct_mask_range_hashing<size_type> base_type;
};
template<typename Allocator>
- struct direct_mod_range_hashing_t_ : public pb_ds::direct_mod_range_hashing<
- typename Allocator::size_type>
+ struct direct_mod_range_hashing_t_
+ : public pb_ds::direct_mod_range_hashing<typename Allocator::size_type>
{
- typedef
- pb_ds::direct_mod_range_hashing<
- typename Allocator::size_type>
- base_type;
+ typedef typename Allocator::size_type size_type;
+ typedef pb_ds::direct_mod_range_hashing<size_type> base_type;
};
template<typename Allocator,
typename Allocator::size_type Max_Load_Nom,
typename Allocator::size_type Max_Load_Denom,
bool External_Access>
- struct hash_load_check_resize_trigger_t_ : public pb_ds::hash_load_check_resize_trigger<
- External_Access,
- typename Allocator::size_type>
+ struct hash_load_check_resize_trigger_t_
+ : public pb_ds::hash_load_check_resize_trigger<External_Access,
+ typename Allocator::size_type>
{
- typedef
- pb_ds::hash_load_check_resize_trigger<
- External_Access,
- typename Allocator::size_type>
- base_type;
+ typedef typename Allocator::size_type size_type;
+ typedef pb_ds::hash_load_check_resize_trigger<External_Access, size_type> base_type;
inline
- hash_load_check_resize_trigger_t_() : base_type(
- static_cast<float>(Min_Load_Nom) /
- static_cast<float>(Min_Load_Denom),
- static_cast<float>(Max_Load_Nom) /
- static_cast<float>(Max_Load_Denom))
+ hash_load_check_resize_trigger_t_()
+ : base_type(static_cast<float>(Min_Load_Nom) / static_cast<float>(Min_Load_Denom), static_cast<float>(Max_Load_Nom) / static_cast<float>(Max_Load_Denom))
{ }
enum
typename Allocator::size_type Load_Nom,
typename Allocator::size_type Load_Denom,
bool External_Access>
- struct cc_hash_max_collision_check_resize_trigger_t_ : public pb_ds::cc_hash_max_collision_check_resize_trigger<
- External_Access,
+ struct cc_hash_max_collision_check_resize_trigger_t_
+ : public pb_ds::cc_hash_max_collision_check_resize_trigger<External_Access,
typename Allocator::size_type>
{
- typedef
- pb_ds::cc_hash_max_collision_check_resize_trigger<
- External_Access,
- typename Allocator::size_type>
- base_type;
+ typedef typename Allocator::size_type size_type;
+ typedef pb_ds::cc_hash_max_collision_check_resize_trigger<External_Access, size_type> base_type;
inline
- cc_hash_max_collision_check_resize_trigger_t_() : base_type(
- static_cast<float>(Load_Nom) /
- static_cast<float>(Load_Denom))
+ cc_hash_max_collision_check_resize_trigger_t_()
+ : base_type(static_cast<float>(Load_Nom) / static_cast<float>(Load_Denom))
{ }
enum
{ };
template<typename Allocator>
- struct hash_exponential_size_policy_t_ : public pb_ds::hash_exponential_size_policy<
- typename Allocator::size_type>
- {
- // Nothing
- };
+ struct hash_exponential_size_policy_t_
+ : public pb_ds::hash_exponential_size_policy<typename Allocator::size_type>
+ { };
template<typename Key, class Allocator>
- struct linear_probe_fn_t_ : public pb_ds::linear_probe_fn<
- typename Allocator::size_type>
+ struct linear_probe_fn_t_
+ : public pb_ds::linear_probe_fn<typename Allocator::size_type>
{ };
template<typename Key, class Allocator>
- struct quadratic_probe_fn_t_ : public pb_ds::quadratic_probe_fn<
- typename Allocator::size_type>
+ struct quadratic_probe_fn_t_
+ : public pb_ds::quadratic_probe_fn<typename Allocator::size_type>
{ };
template<typename Allocator, typename Allocator::size_type Max_Count>
- struct counter_lu_policy_t_ : public pb_ds::counter_lu_policy<
- Max_Count,
- Allocator>
+ struct counter_lu_policy_t_
+ : public pb_ds::counter_lu_policy<Max_Count, Allocator>
{
- typedef pb_ds::counter_lu_policy< Max_Count, Allocator> base_type;
+ typedef pb_ds::counter_lu_policy<Max_Count, Allocator> base_type;
};
- struct move_to_front_lu_policy_t_ : public pb_ds::move_to_front_lu_policy<>
+ struct move_to_front_lu_policy_t_
+ : public pb_ds::move_to_front_lu_policy<>
{ };
-
} // namespace test
-
} // namespace pb_ds
-#endif // #ifndef PB_DS_TEMPLATE_POLICY_HPP
+#endif
namespace pb_ds
{
-
namespace test
{
-
-#define PB_DS_CLASS_T_DEC \
- template<typename It>
-
-#define PB_DS_CLASS_C_DEC \
- erase_test< \
- It>
-
template<typename It>
class erase_test
{
public:
- erase_test(It ins_b, size_t ins_vn, size_t ins_vs, size_t ins_vm);
+ erase_test(It ins_b, size_t ins_vn, size_t ins_vs, size_t ins_vm)
+ : m_ins_b(ins_b), m_ins_vn(ins_vn), m_ins_vs(ins_vs), m_ins_vm(ins_vm)
+ { }
template<typename Cntnr>
- void
- operator()(__gnu_cxx::typelist::detail::type_to_type<Cntnr>);
+ void
+ operator()(Cntnr);
private:
- erase_test(const erase_test& );
+ erase_test(const erase_test&);
- private:
- const It m_ins_b;
-
- const size_t m_ins_vn;
- const size_t m_ins_vs;
- const size_t m_ins_vm;
+ const It m_ins_b;
+ const size_t m_ins_vn;
+ const size_t m_ins_vs;
+ const size_t m_ins_vm;
};
- PB_DS_CLASS_T_DEC
- PB_DS_CLASS_C_DEC::
- erase_test(It ins_b, size_t ins_vn, size_t ins_vs, size_t ins_vm) :
- m_ins_b(ins_b),
- m_ins_vn(ins_vn),
- m_ins_vs(ins_vs),
- m_ins_vm(ins_vm)
- { }
-
- PB_DS_CLASS_T_DEC
+ template<typename It>
template<typename Cntnr>
void
- PB_DS_CLASS_C_DEC::
- operator()(__gnu_cxx::typelist::detail::type_to_type<Cntnr>)
+ erase_test<It>::
+ operator()(Cntnr)
{
- xml_result_set_performance_formatter res_set_fmt(
- string_form<Cntnr>::name(),
- string_form<Cntnr>::desc());
+ typedef string_form<Cntnr> sform_type;
+ typedef xml_result_set_performance_formatter formatter_type;
+ formatter_type res_set_fmt(sform_type::name(), sform_type::desc());
- for (size_t size_i = 0; m_ins_vn + size_i* m_ins_vs < m_ins_vm; ++size_i)
+ for (size_t i = 0; m_ins_vn + i * m_ins_vs < m_ins_vm; ++i)
{
- const size_t ins_size = m_ins_vn + size_i* m_ins_vs;
+ const size_t ins_size = m_ins_vn + i * m_ins_vs;
It ins_it_b = m_ins_b;
It ins_it_e = m_ins_b;
std::advance(ins_it_e, ins_size);
mem_track_allocator<char> alloc;
-
const size_t init_mem = alloc.get_total();
-
Cntnr cntnr(ins_it_b, ins_it_e);
while (cntnr.size() > 1)
cntnr.erase(*cntnr.begin());
const size_t final_mem = alloc.get_total();
-
assert(final_mem > init_mem);
-
const size_t delta_mem = final_mem - init_mem;
-
res_set_fmt.add_res(ins_size, static_cast<double>(delta_mem));
}
}
-
-#undef PB_DS_CLASS_T_DEC
-
-#undef PB_DS_CLASS_C_DEC
-
} // namespace test
-
} // namespace pb_ds
-#endif // #ifndef PB_DS_ERASE_TEST_HPP
+#endif
namespace pb_ds
{
-
namespace test
{
-
-#define PB_DS_CLASS_T_DEC \
- template<typename It, bool Native>
-
-#define PB_DS_CLASS_C_DEC \
- multimap_insert_test< \
- It, \
- Native>
-
template<typename It, bool Native>
class multimap_insert_test
{
public:
- multimap_insert_test(It ins_b, size_t ins_vn, size_t ins_vs, size_t ins_vm);
+ multimap_insert_test(It b, size_t ins_vn, size_t ins_vs, size_t ins_vm):
+ m_ins_b(b), m_ins_vn(ins_vn), m_ins_vs(ins_vs), m_ins_vm(ins_vm)
+ { }
template<typename Cntnr>
void
- operator()(__gnu_cxx::typelist::detail::type_to_type<Cntnr>);
+ operator()(Cntnr);
private:
- multimap_insert_test(const multimap_insert_test& );
+ multimap_insert_test(const multimap_insert_test&);
template<typename Cntnr>
size_t
- insert(__gnu_cxx::typelist::detail::type_to_type<Cntnr>, It ins_it_b, It ins_it_e, pb_ds::detail::true_type);
+ insert(Cntnr, It ins_it_b, It ins_it_e, pb_ds::detail::true_type);
template<typename Cntnr>
size_t
- insert(__gnu_cxx::typelist::detail::type_to_type<Cntnr>, It ins_it_b, It ins_it_e, pb_ds::detail::false_type);
+ insert(Cntnr, It ins_it_b, It ins_it_e, pb_ds::detail::false_type);
- private:
const It m_ins_b;
-
const size_t m_ins_vn;
const size_t m_ins_vs;
const size_t m_ins_vm;
};
- PB_DS_CLASS_T_DEC
- PB_DS_CLASS_C_DEC::
- multimap_insert_test(It ins_b, size_t ins_vn, size_t ins_vs, size_t ins_vm) :
- m_ins_b(ins_b),
- m_ins_vn(ins_vn),
- m_ins_vs(ins_vs),
- m_ins_vm(ins_vm)
- { }
-
- PB_DS_CLASS_T_DEC
+ template<typename It, bool Native>
template<typename Cntnr>
void
- PB_DS_CLASS_C_DEC::
- operator()(__gnu_cxx::typelist::detail::type_to_type<Cntnr>)
+ multimap_insert_test<It, Native>::
+ operator()(Cntnr)
{
- xml_result_set_performance_formatter res_set_fmt(
- string_form<Cntnr>::name(),
- string_form<Cntnr>::desc());
+ typedef xml_result_set_performance_formatter formatter_type;
+ formatter_type res_set_fmt(string_form<Cntnr>::name(),
+ string_form<Cntnr>::desc());
- for (size_t size_i = 0; m_ins_vn + size_i* m_ins_vs < m_ins_vm; ++size_i)
+ for (size_t i = 0; m_ins_vn + i * m_ins_vs < m_ins_vm; ++i)
{
- const size_t ins_size = m_ins_vn + size_i* m_ins_vs;
-
+ const size_t ins_size = m_ins_vn + i * m_ins_vs;
It ins_it_b = m_ins_b;
It ins_it_e = m_ins_b;
std::advance(ins_it_e, ins_size);
- const size_t delta_mem = insert(__gnu_cxx::typelist::detail::type_to_type<Cntnr>(),
- ins_it_b,
- ins_it_e,
+ const size_t delta_mem = insert(Cntnr(), ins_it_b, ins_it_e,
pb_ds::detail::integral_constant<int,Native>());
res_set_fmt.add_res(ins_size, static_cast<double>(delta_mem));
}
}
- PB_DS_CLASS_T_DEC
+ template<typename It, bool Native>
template<typename Cntnr>
size_t
- PB_DS_CLASS_C_DEC::
- insert(__gnu_cxx::typelist::detail::type_to_type<Cntnr>, It ins_it_b, It ins_it_e, pb_ds::detail::true_type)
+ multimap_insert_test<It, Native>::
+ insert(Cntnr, It ins_it_b, It ins_it_e, pb_ds::detail::true_type)
{
mem_track_allocator<char> alloc;
-
const size_t init_mem = alloc.get_total();
-
Cntnr cntnr;
-
for (It ins_it = ins_it_b; ins_it != ins_it_e; ++ins_it)
cntnr.insert((typename Cntnr::const_reference)(*ins_it));
-
const size_t final_mem = alloc.get_total();
-
assert(final_mem > init_mem);
-
return (final_mem - init_mem);
}
- PB_DS_CLASS_T_DEC
+ template<typename It, bool Native>
template<typename Cntnr>
size_t
- PB_DS_CLASS_C_DEC::
- insert(__gnu_cxx::typelist::detail::type_to_type<Cntnr>, It ins_it_b, It ins_it_e, pb_ds::detail::false_type)
+ multimap_insert_test<It, Native>::
+ insert(Cntnr, It ins_it_b, It ins_it_e, pb_ds::detail::false_type)
{
mem_track_allocator<char> alloc;
-
const size_t init_mem = alloc.get_total();
-
Cntnr cntnr;
-
for (It ins_it = ins_it_b; ins_it != ins_it_e; ++ins_it)
cntnr[ins_it->first].insert(ins_it->second);
-
const size_t final_mem = alloc.get_total();
-
assert(final_mem > init_mem);
-
return (final_mem - init_mem);
}
-
-#undef PB_DS_CLASS_T_DEC
-
-#undef PB_DS_CLASS_C_DEC
-
} // namespace test
-
} // namespace pb_ds
-#endif // #ifndef PB_DS_MULTIMAP_INSERT_TEST_HPP
+#endif
namespace pb_ds
{
-
namespace test
{
-
namespace detail
{
-
- struct int_hash : public std::unary_function<
- int,
- size_t>
+ struct int_hash : public std::unary_function<int, size_t>
{
inline size_t
operator()(const int i) const
- {
- return (static_cast<size_t>(i));
- }
+ { return (static_cast<size_t>(i)); }
};
- template<typename Key, class Allocator = std::allocator<char> >
+ template<typename Key, typename Allocator = std::allocator<char> >
struct hash_set_tl_t
{
typedef
Key,
pb_ds::null_mapped_type,
int_hash,
- std::equal_to<
- Key>,
+ std::equal_to<Key>,
Allocator>::performance_min_tl
type;
};
- template<typename Key, class Allocator = std::allocator<char> >
+ template<typename Key, typename Allocator = std::allocator<char> >
struct lu_set_tl_t
{
typedef
template<typename Key,
class Sec_Tl,
- class Allocator = std::allocator<
- char> >
+ typename Allocator = std::allocator<char> >
struct hash_mmap_tl_t
{
private:
template<typename Key,
class Sec_Tl,
- class Allocator = std::allocator<
- char> >
+ typename Allocator = std::allocator<char> >
struct tree_mmap_tl_t
{
private:
type;
};
- template<typename Key, typename Mapped, class Allocator>
+ template<typename Key, typename Mapped, typename Allocator>
struct hash_hash_mmap_tl_t
{
private:
- typedef typename hash_set_tl_t< Mapped, Allocator>::type sec_tl_t;
+ typedef typename hash_set_tl_t<Mapped, Allocator>::type sec_tl_t;
public:
- typedef typename hash_mmap_tl_t< Key, sec_tl_t, Allocator>::type type;
+ typedef typename hash_mmap_tl_t<Key, sec_tl_t, Allocator>::type type;
};
- template<typename Key, typename Mapped, class Allocator>
+ template<typename Key, typename Mapped, typename Allocator>
struct tree_hash_mmap_tl_t
{
private:
- typedef typename hash_set_tl_t< Mapped, Allocator>::type sec_tl_t;
+ typedef typename hash_set_tl_t<Mapped, Allocator>::type sec_tl_t;
public:
- typedef typename tree_mmap_tl_t< Key, sec_tl_t, Allocator>::type type;
+ typedef typename tree_mmap_tl_t<Key, sec_tl_t, Allocator>::type type;
};
- template<typename Key, typename Mapped, class Allocator>
+ template<typename Key, typename Mapped, typename Allocator>
struct tree_lu_mmap_tl_t
{
private:
- typedef typename lu_set_tl_t< Mapped, Allocator>::type sec_tl_t;
+ typedef typename lu_set_tl_t<Mapped, Allocator>::type sec_tl_t;
public:
- typedef typename tree_mmap_tl_t< Key, sec_tl_t, Allocator>::type type;
+ typedef typename tree_mmap_tl_t<Key, sec_tl_t, Allocator>::type type;
};
- template<typename Key, typename Mapped, class Allocator>
+ template<typename Key, typename Mapped, typename Allocator>
struct hash_lu_mmap_tl_t
{
private:
- typedef typename lu_set_tl_t< Mapped, Allocator>::type sec_tl_t;
+ typedef typename lu_set_tl_t<Mapped, Allocator>::type sec_tl_t;
public:
- typedef typename hash_mmap_tl_t< Key, sec_tl_t, Allocator>::type type;
+ typedef typename hash_mmap_tl_t<Key, sec_tl_t, Allocator>::type type;
};
-
} // namespace detail
- template<typename Key, typename Mapped, class Allocator>
+ template<typename Key, typename Mapped, typename Allocator>
struct mmap_tl_t
{
private:
typedef
- typename detail::hash_hash_mmap_tl_t<
- Key,
- Mapped,
- Allocator>::type
+ typename detail::hash_hash_mmap_tl_t<Key, Mapped, Allocator>::type
hh_mmap_tl_t;
typedef
- typename detail::hash_lu_mmap_tl_t<
- Key,
- Mapped,
- Allocator>::type
+ typename detail::hash_lu_mmap_tl_t<Key, Mapped, Allocator>::type
hl_mmap_tl_t;
typedef
- typename detail::tree_hash_mmap_tl_t<
- Key,
- Mapped,
- Allocator>::type
+ typename detail::tree_hash_mmap_tl_t<Key, Mapped, Allocator>::type
th_mmap_tl_t;
typedef
- typename detail::tree_lu_mmap_tl_t<
- Key,
- Mapped,
- Allocator>::type
+ typename detail::tree_lu_mmap_tl_t<Key, Mapped, Allocator>::type
tl_mmap_tl_t;
public:
typedef
- typename __gnu_cxx::typelist::append<
- hl_mmap_tl_t,
- typename __gnu_cxx::typelist::append<
- hh_mmap_tl_t,
- typename __gnu_cxx::typelist::append<
- th_mmap_tl_t,
+ typename __gnu_cxx::typelist::append<hl_mmap_tl_t,
+ typename __gnu_cxx::typelist::append<hh_mmap_tl_t,
+ typename __gnu_cxx::typelist::append<th_mmap_tl_t,
tl_mmap_tl_t>::type>::type>::type
type;
};
} // namespace test
-
} // namespace pb_ds
-#endif // #ifndef PB_DS_MULTIMAP_RANDOM_INT_INSERT_TEST_COMMON_TYPE_HPP
+#endif
namespace pb_ds
{
-
namespace test
{
-
namespace detail
{
-
template<typename It, class Cntnr, bool LOR>
class find_find_functor
{
public:
- find_find_functor(Cntnr& r_container, It fnd_it_b, It fnd_it_e) : m_r_container(r_container),
- m_fnd_it_b(fnd_it_b),
- m_fnd_it_e(fnd_it_e)
+ find_find_functor(Cntnr& contnr, It fnd_it_b, It fnd_it_e)
+ : m_contnr(contnr), m_fnd_it_b(fnd_it_b), m_fnd_it_e(fnd_it_e)
{ }
void
for (std::size_t i = 0; i < resolution; ++i)
{
It fnd_it = m_fnd_it_b;
-
while (fnd_it != m_fnd_it_e)
- ++m_r_container.find((fnd_it++)->first)->second;
+ ++m_contnr.find((fnd_it++)->first)->second;
}
}
private:
- Cntnr& m_r_container;
-
+ Cntnr& m_contnr;
const It m_fnd_it_b;
const It m_fnd_it_e;
};
template<typename It, class Cntnr>
- class find_find_functor<
- It,
- Cntnr,
- true>
+ class find_find_functor<It, Cntnr, true>
{
public:
- find_find_functor(Cntnr& r_container, It fnd_it_b, It fnd_it_e) : m_r_container(r_container),
- m_fnd_it_b(fnd_it_b),
- m_fnd_it_e(fnd_it_e)
+ find_find_functor(Cntnr& contnr, It fnd_it_b, It fnd_it_e)
+ : m_contnr(contnr), m_fnd_it_b(fnd_it_b), m_fnd_it_e(fnd_it_e)
{ }
void
operator()(std::size_t resolution)
{
It fnd_it = m_fnd_it_b;
-
while (fnd_it != m_fnd_it_e)
{
for (std::size_t i = 0; i < resolution; ++i)
- ++m_r_container.find(fnd_it->first)->second;
-
+ ++m_contnr.find(fnd_it->first)->second;
++fnd_it;
}
}
private:
- Cntnr& m_r_container;
-
+ Cntnr& m_contnr;
const It m_fnd_it_b;
const It m_fnd_it_e;
};
-
} // namespace detail
-#define PB_DS_CLASS_T_DEC \
- template<typename It, bool LOR>
-
-#define PB_DS_CLASS_C_DEC \
- find_test< \
- It, \
- LOR>
-
template<typename It, bool LOR = false>
class find_test : private pb_ds::test::detail::timing_test_base
{
public:
- find_test(It ins_b, It fnd_it_b, size_t ins_vn, size_t ins_vs, size_t ins_vm, size_t fnd_vn, size_t fnd_vs, size_t fnd_vm);
+ find_test(It ins_b, It fnd_it_b, size_t ins_vn, size_t ins_vs,
+ size_t ins_vm, size_t fnd_vn, size_t fnd_vs, size_t fnd_vm):
+ m_ins_b(ins_b), m_fnd_it_b(fnd_it_b), m_ins_vn(ins_vn), m_ins_vs(ins_vs),
+ m_ins_vm(ins_vm), m_fnd_vn(fnd_vn), m_fnd_vs(fnd_vs), m_fnd_vm(fnd_vm)
+ { }
template<typename Cntnr>
void
- operator()(__gnu_cxx::typelist::detail::type_to_type<Cntnr>);
+ operator()(Cntnr);
private:
find_test(const find_test& );
private:
- const It m_ins_b;
-
- const It m_fnd_it_b;
-
- const size_t m_ins_vn;
- const size_t m_ins_vs;
- const size_t m_ins_vm;
-
- const size_t m_fnd_vn;
- const size_t m_fnd_vs;
- const size_t m_fnd_vm;
+ const It m_ins_b;
+ const It m_fnd_it_b;
+ const size_t m_ins_vn;
+ const size_t m_ins_vs;
+ const size_t m_ins_vm;
+ const size_t m_fnd_vn;
+ const size_t m_fnd_vs;
+ const size_t m_fnd_vm;
};
- PB_DS_CLASS_T_DEC
- PB_DS_CLASS_C_DEC::
- find_test(It ins_b, It fnd_it_b, size_t ins_vn, size_t ins_vs, size_t ins_vm, size_t fnd_vn, size_t fnd_vs, size_t fnd_vm) :
- m_ins_b(ins_b),
- m_fnd_it_b(fnd_it_b),
- m_ins_vn(ins_vn),
- m_ins_vs(ins_vs),
- m_ins_vm(ins_vm),
- m_fnd_vn(fnd_vn),
- m_fnd_vs(fnd_vs),
- m_fnd_vm(fnd_vm)
- { }
-
- PB_DS_CLASS_T_DEC
+ template<typename It, bool LOR>
template<typename Cntnr>
void
- PB_DS_CLASS_C_DEC::
- operator()(__gnu_cxx::typelist::detail::type_to_type<Cntnr>)
+ find_test<It, LOR>::
+ operator()(Cntnr)
{
- xml_result_set_performance_formatter res_set_fmt(
- string_form<Cntnr>::name(),
- string_form<Cntnr>::desc());
+ typedef string_form<Cntnr> sform_type;
+ typedef xml_result_set_performance_formatter formatter_type;
+ formatter_type res_set_fmt(sform_type::name(), sform_type::desc());
- for (size_t size_i = 0; m_ins_vn + size_i* m_ins_vs < m_ins_vm; ++size_i)
+ for (size_t i = 0; m_ins_vn + i * m_ins_vs < m_ins_vm; ++i)
{
- const size_t v = m_ins_vn + size_i* m_ins_vs;
- const size_t fnd_size = m_fnd_vn + size_i* m_fnd_vs;
-
+ const size_t v = m_ins_vn + i * m_ins_vs;
+ const size_t fnd_size = m_fnd_vn + i * m_fnd_vs;
It ins_it_b = m_ins_b;
It ins_it_e = m_ins_b;
std::advance(ins_it_e, v);
Cntnr test_container(ins_it_b, ins_it_e);
-
It fnd_it_b = m_fnd_it_b;
It fnd_it_e = m_fnd_it_b;
std::advance(fnd_it_e, fnd_size);
const double res =
pb_ds::test::detail::timing_test_base::operator()(fn);
-
res_set_fmt.add_res(v, res / fnd_size);
}
}
-
-#undef PB_DS_CLASS_T_DEC
-
-#undef PB_DS_CLASS_C_DEC
-
} // namespace test
-
} // namespace pb_ds
-#endif // #ifndef PB_DS_FIND_TEST_HPP
+#endif
namespace pb_ds
{
-
namespace test
{
-
namespace detail
{
-
template<typename It, class Cntnr>
class insert_insert_functor
{
public:
- insert_insert_functor(It ins_it_b, It ins_it_e) : m_ins_it_b(ins_it_b),
- m_ins_it_e(ins_it_e)
+ insert_insert_functor(It ins_it_b, It ins_it_e)
+ : m_ins_it_b(ins_it_b), m_ins_it_e(ins_it_e)
{ }
void
for (std::size_t i = 0; i < resolution; ++i)
{
Cntnr cntnr;
-
for (It ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it)
cntnr.insert((typename Cntnr::const_reference)(*ins_it));
}
const It m_ins_it_b;
const It m_ins_it_e;
};
-
} // namespace detail
-#define PB_DS_CLASS_T_DEC \
- template<typename It>
-
-#define PB_DS_CLASS_C_DEC \
- insert_test< \
- It>
-
template<typename It>
class insert_test : private pb_ds::test::detail::timing_test_base
{
public:
- insert_test(It ins_b, size_t ins_vn, size_t ins_vs, size_t ins_vm);
+ insert_test(It ins_b, size_t ins_vn, size_t ins_vs, size_t ins_vm)
+ : m_ins_b(ins_b), m_ins_vn(ins_vn), m_ins_vs(ins_vs), m_ins_vm(ins_vm)
+ { }
template<typename Cntnr>
void
- operator()(__gnu_cxx::typelist::detail::type_to_type<Cntnr>);
+ operator()(Cntnr);
private:
insert_test(const insert_test& );
template<typename Cntnr>
void
- insert(__gnu_cxx::typelist::detail::type_to_type<Cntnr>, It ins_it_b, It ins_it_e);
+ insert(Cntnr, It ins_it_b, It ins_it_e);
- private:
const It m_ins_b;
-
const size_t m_ins_vn;
const size_t m_ins_vs;
const size_t m_ins_vm;
};
- PB_DS_CLASS_T_DEC
- PB_DS_CLASS_C_DEC::
- insert_test(It ins_b, size_t ins_vn, size_t ins_vs, size_t ins_vm) :
- m_ins_b(ins_b),
- m_ins_vn(ins_vn),
- m_ins_vs(ins_vs),
- m_ins_vm(ins_vm)
- { }
-
- PB_DS_CLASS_T_DEC
+ template<typename It>
template<typename Cntnr>
void
- PB_DS_CLASS_C_DEC::
- operator()(__gnu_cxx::typelist::detail::type_to_type<Cntnr>)
+ insert_test<It>::
+ operator()(Cntnr)
{
- xml_result_set_performance_formatter res_set_fmt(
- string_form<Cntnr>::name(),
- string_form<Cntnr>::desc());
+ typedef xml_result_set_performance_formatter formatter_type;
+ formatter_type res_set_fmt(string_form<Cntnr>::name(),
+ string_form<Cntnr>::desc());
- for (size_t size_i = 0; m_ins_vn + size_i* m_ins_vs < m_ins_vm; ++size_i)
+ for (size_t i = 0; m_ins_vn + i* m_ins_vs < m_ins_vm; ++i)
{
- const size_t v = m_ins_vn + size_i* m_ins_vs;
-
+ const size_t v = m_ins_vn + i* m_ins_vs;
It ins_it_b = m_ins_b;
It ins_it_e = m_ins_b;
std::advance(ins_it_e, v);
}
}
- PB_DS_CLASS_T_DEC
+ template<typename It>
template<typename Cntnr>
void
- PB_DS_CLASS_C_DEC::
- insert(__gnu_cxx::typelist::detail::type_to_type<Cntnr>, It ins_it_b, It ins_it_e)
+ insert_test<It>::
+ insert(Cntnr, It ins_it_b, It ins_it_e)
{
Cntnr cntnr;
-
for (It ins_it = ins_it_b; ins_it != ins_it_e; ++ins_it)
cntnr.insert((typename Cntnr::const_reference)(*ins_it));
}
-
-#undef PB_DS_CLASS_T_DEC
-
-#undef PB_DS_CLASS_C_DEC
-
} // namespace test
-
} // namespace pb_ds
-#endif // #ifndef PB_DS_INSERT_TEST_HPP
+#endif
namespace pb_ds
{
-
namespace test
{
-
namespace detail
{
-
template<typename It, class Cntnr, bool Native>
class multimap_find_functor
{
public:
- multimap_find_functor(const Cntnr& r_container, It fnd_it_b, It fnd_it_e) : m_r_container(r_container),
- m_fnd_it_b(fnd_it_b),
- m_fnd_it_e(fnd_it_e)
+ multimap_find_functor(const Cntnr& container, It fnd_it_b, It fnd_it_e)
+ : m_r_container(container), m_fnd_it_b(fnd_it_b), m_fnd_it_e(fnd_it_e)
{ }
void
operator()(std::size_t resolution)
{
size_t not_found_count = 0;
-
+ typedef typename Cntnr::const_point_iterator iterator_type;
for (std::size_t i = 0; i < resolution; ++i)
{
- typename Cntnr::const_point_iterator prm_end_it = m_r_container.end();
-
+ iterator_type end = m_r_container.end();
for (It fnd_it = m_fnd_it_b; fnd_it != m_fnd_it_e; ++fnd_it)
{
- typename Cntnr::const_point_iterator prm_it = m_r_container.find(fnd_it->first);
-
- if (prm_it == prm_end_it ||
- prm_it->second.find(fnd_it->second) == prm_it->second.end())
+ iterator_type it = m_r_container.find(fnd_it->first);
+ if (it == end ||
+ it->second.find(fnd_it->second) == it->second.end())
++not_found_count;
}
}
private:
const Cntnr& m_r_container;
-
const It m_fnd_it_b;
const It m_fnd_it_e;
};
template<typename It, class Cntnr>
- class multimap_find_functor<
- It,
- Cntnr,
- true>
+ class multimap_find_functor<It, Cntnr, true>
{
public:
- multimap_find_functor(const Cntnr& r_container, It fnd_it_b, It fnd_it_e) : m_r_container(r_container),
- m_fnd_it_b(fnd_it_b),
- m_fnd_it_e(fnd_it_e)
+ multimap_find_functor(const Cntnr& container, It fnd_it_b, It fnd_it_e)
+ : m_r_container(container), m_fnd_it_b(fnd_it_b), m_fnd_it_e(fnd_it_e)
{ }
void
operator()(std::size_t resolution)
{
+ typedef typename Cntnr::const_reference const_reference;
size_t not_found_count = 0;
-
for (std::size_t i = 0; i < resolution; ++i)
{
Cntnr cntnr;
-
for (It fnd_it = m_fnd_it_b; fnd_it != m_fnd_it_e; ++fnd_it)
- if (m_r_container.find((typename Cntnr::const_reference)(*fnd_it)) == m_r_container.end())
+ if (m_r_container.find(const_reference(*fnd_it))
+ == m_r_container.end())
++not_found_count;
}
private:
const Cntnr& m_r_container;
-
const It m_fnd_it_b;
const It m_fnd_it_e;
};
-
} // namespace detail
-#define PB_DS_CLASS_T_DEC \
- template<typename It, bool Native>
-
-#define PB_DS_CLASS_C_DEC \
- multimap_find_test< \
- It, \
- Native>
template<typename It, bool Native>
class multimap_find_test : private pb_ds::test::detail::timing_test_base
{
public:
- multimap_find_test(It ins_b, size_t ins_vn, size_t ins_vs, size_t ins_vm);
+ multimap_find_test(It ins_b, size_t ins_vn, size_t vs, size_t ins_vm)
+ : m_ins_b(ins_b), m_ins_vn(ins_vn), m_ins_vs(vs), m_ins_vm(ins_vm)
+ { }
template<typename Cntnr>
void
- operator()(__gnu_cxx::typelist::detail::type_to_type<Cntnr>);
+ operator()(Cntnr);
private:
- multimap_find_test(const multimap_find_test& );
+ multimap_find_test(const multimap_find_test&);
template<typename Cntnr>
Cntnr
- init(It ins_b, It ins_e, __gnu_cxx::typelist::detail::type_to_type<Cntnr>, pb_ds::detail::true_type);
+ init(It ins_b, It ins_e, Cntnr, pb_ds::detail::true_type)
+ { return Cntnr(ins_b, ins_e); }
template<typename Cntnr>
Cntnr
- init(It ins_b, It ins_e, __gnu_cxx::typelist::detail::type_to_type<Cntnr>, pb_ds::detail::false_type);
+ init(It ins_b, It ins_e, Cntnr, pb_ds::detail::false_type)
+ {
+ Cntnr ret;
+ for (It it = ins_b; it != ins_e; ++it)
+ ret[it->first].insert(it->second);
+ return ret;
+ }
- private:
const It m_ins_b;
-
const size_t m_ins_vn;
const size_t m_ins_vs;
const size_t m_ins_vm;
};
- PB_DS_CLASS_T_DEC
- PB_DS_CLASS_C_DEC::
- multimap_find_test(It ins_b, size_t ins_vn, size_t ins_vs, size_t ins_vm) :
- m_ins_b(ins_b),
- m_ins_vn(ins_vn),
- m_ins_vs(ins_vs),
- m_ins_vm(ins_vm)
- { }
- PB_DS_CLASS_T_DEC
+ template<typename It, bool Native>
template<typename Cntnr>
void
- PB_DS_CLASS_C_DEC::
- operator()(__gnu_cxx::typelist::detail::type_to_type<Cntnr>)
+ multimap_find_test<It, Native>::
+ operator()(Cntnr)
{
- xml_result_set_performance_formatter res_set_fmt(
- string_form<Cntnr>::name(),
- string_form<Cntnr>::desc());
+ typedef xml_result_set_performance_formatter formatter_type;
+ formatter_type res_set_fmt(string_form<Cntnr>::name(),
+ string_form<Cntnr>::desc());
- for (size_t size_i = 0; m_ins_vn + size_i* m_ins_vs < m_ins_vm; ++size_i)
+ for (size_t i = 0; m_ins_vn + i * m_ins_vs < m_ins_vm; ++i)
{
- const size_t v = m_ins_vn + size_i* m_ins_vs;
-
+ const size_t v = m_ins_vn + i * m_ins_vs;
It ins_it_b = m_ins_b;
It ins_it_e = m_ins_b;
std::advance(ins_it_e, v);
- Cntnr c = init(ins_it_b,
- ins_it_e,
- __gnu_cxx::typelist::detail::type_to_type<Cntnr>(),
+ Cntnr c = init(ins_it_b, ins_it_e, Cntnr(),
pb_ds::detail::integral_constant<int,Native>());
pb_ds::test::detail::multimap_find_functor<It, Cntnr, Native>
res_set_fmt.add_res(v, res / v);
}
}
-
- PB_DS_CLASS_T_DEC
- template<typename Cntnr>
- Cntnr
- PB_DS_CLASS_C_DEC::
- init(It ins_b, It ins_e, __gnu_cxx::typelist::detail::type_to_type<Cntnr>, pb_ds::detail::true_type)
- {
- return Cntnr(ins_b, ins_e);
- }
-
- PB_DS_CLASS_T_DEC
- template<typename Cntnr>
- Cntnr
- PB_DS_CLASS_C_DEC::
- init(It ins_b, It ins_e, __gnu_cxx::typelist::detail::type_to_type<Cntnr>, pb_ds::detail::false_type)
- {
- Cntnr ret;
-
- for (It it = ins_b; it != ins_e; ++it)
- ret[it->first].insert(it->second);
-
- return ret;
- }
-
-#undef PB_DS_CLASS_T_DEC
-
-#undef PB_DS_CLASS_C_DEC
-
} // namespace test
-
} // namespace pb_ds
-#endif // #ifndef PB_DS_MULTIMAP_INSERT_TEST_HPP
+#endif
namespace pb_ds
{
-
namespace test
{
-
namespace detail
{
-
template<typename It, class Cntnr, bool Native>
class multimap_insert_functor
{
public:
- multimap_insert_functor(It ins_it_b, It ins_it_e) : m_ins_it_b(ins_it_b),
- m_ins_it_e(ins_it_e)
+ multimap_insert_functor(It ins_it_b, It ins_it_e)
+ : m_ins_it_b(ins_it_b), m_ins_it_e(ins_it_e)
{ }
void
for (std::size_t i = 0; i < resolution; ++i)
{
Cntnr cntnr;
-
for (It ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it)
cntnr[ins_it->first].insert(ins_it->second);
}
};
template<typename It, class Cntnr>
- class multimap_insert_functor<
- It,
- Cntnr,
- true>
+ class multimap_insert_functor<It, Cntnr, true>
{
public:
- multimap_insert_functor(It ins_it_b, It ins_it_e) : m_ins_it_b(ins_it_b),
- m_ins_it_e(ins_it_e)
+ multimap_insert_functor(It ins_it_b, It ins_it_e)
+ : m_ins_it_b(ins_it_b), m_ins_it_e(ins_it_e)
{ }
void
for (std::size_t i = 0; i < resolution; ++i)
{
Cntnr cntnr;
-
for (It ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it)
cntnr.insert((typename Cntnr::const_reference)(*ins_it));
}
const It m_ins_it_b;
const It m_ins_it_e;
};
-
} // namespace detail
-#define PB_DS_CLASS_T_DEC \
- template<typename It, bool Native>
-
-#define PB_DS_CLASS_C_DEC \
- multimap_insert_test< \
- It, \
- Native>
-
template<typename It, bool Native>
class multimap_insert_test : private pb_ds::test::detail::timing_test_base
{
public:
- multimap_insert_test(It ins_b, size_t ins_vn, size_t ins_vs, size_t ins_vm);
+ multimap_insert_test(It b, size_t ins_vn, size_t ins_vs, size_t ins_vm)
+ : m_ins_b(b), m_ins_vn(ins_vn), m_ins_vs(ins_vs), m_ins_vm(ins_vm)
+ { }
template<typename Cntnr>
void
- operator()(__gnu_cxx::typelist::detail::type_to_type<Cntnr>);
+ operator()(Cntnr);
private:
- multimap_insert_test(const multimap_insert_test& );
+ multimap_insert_test(const multimap_insert_test&);
private:
const It m_ins_b;
-
const size_t m_ins_vn;
const size_t m_ins_vs;
const size_t m_ins_vm;
};
- PB_DS_CLASS_T_DEC
- PB_DS_CLASS_C_DEC::
- multimap_insert_test(It ins_b, size_t ins_vn, size_t ins_vs, size_t ins_vm) :
- m_ins_b(ins_b),
- m_ins_vn(ins_vn),
- m_ins_vs(ins_vs),
- m_ins_vm(ins_vm)
- { }
-
- PB_DS_CLASS_T_DEC
+ template<typename It, bool Native>
template<typename Cntnr>
void
- PB_DS_CLASS_C_DEC::
- operator()(__gnu_cxx::typelist::detail::type_to_type<Cntnr>)
+ multimap_insert_test<It, Native>::
+ operator()(Cntnr)
{
- xml_result_set_performance_formatter res_set_fmt(
- string_form<Cntnr>::name(),
- string_form<Cntnr>::desc());
+ typedef xml_result_set_performance_formatter formatter_type;
+ formatter_type res_set_fmt(string_form<Cntnr>::name(),
+ string_form<Cntnr>::desc());
- for (size_t size_i = 0; m_ins_vn + size_i* m_ins_vs < m_ins_vm; ++size_i)
+ for (size_t i = 0; m_ins_vn + i * m_ins_vs < m_ins_vm; ++i)
{
- const size_t v = m_ins_vn + size_i* m_ins_vs;
-
+ const size_t v = m_ins_vn + i * m_ins_vs;
It ins_it_b = m_ins_b;
It ins_it_e = m_ins_b;
std::advance(ins_it_e, v);
const double res =
pb_ds::test::detail::timing_test_base::operator()(fn);
-
res_set_fmt.add_res(v, res / v);
}
}
-
-#undef PB_DS_CLASS_T_DEC
-
-#undef PB_DS_CLASS_C_DEC
-
} // namespace test
-
} // namespace pb_ds
-#endif // #ifndef PB_DS_MULTIMAP_INSERT_TEST_HPP
+#endif
namespace pb_ds
{
-
namespace test
{
-
namespace detail
{
-
template<typename It, class Cntnr>
class subscript_find_functor
{
public:
- subscript_find_functor(Cntnr& r_container, It fnd_it_b, It fnd_it_e) : m_r_container(r_container),
- m_fnd_it_b(fnd_it_b),
- m_fnd_it_e(fnd_it_e)
+ subscript_find_functor(Cntnr& container, It fnd_it_b, It fnd_it_e)
+ : m_r_container(container), m_fnd_it_b(fnd_it_b), m_fnd_it_e(fnd_it_e)
{ }
void
for (std::size_t i = 0; i < resolution; ++i)
{
It fnd_it = m_fnd_it_b;
-
while (fnd_it != m_fnd_it_e)
++m_r_container[(fnd_it++)->first];
-
++fnd_it;
}
}
} // namespace detail
-#define PB_DS_CLASS_T_DEC \
- template<typename It>
-
-#define PB_DS_CLASS_C_DEC \
- subscript_find_test< \
- It>
-
template<typename It>
class subscript_find_test : private pb_ds::test::detail::timing_test_base
{
public:
- subscript_find_test(It ins_b, It fnd_b, size_t ins_vn, size_t ins_vs, size_t ins_vm, size_t fnd_vn, size_t fnd_vs, size_t fnd_vm);
+ subscript_find_test(It ins_b, It b, size_t ins_vn, size_t ins_vs,
+ size_t ins_vm, size_t vn, size_t vs, size_t vm)
+ : m_ins_b(ins_b), m_fnd_b(b), m_ins_vn(ins_vn), m_ins_vs(ins_vs),
+ m_ins_vm(ins_vm), m_fnd_vn(vn), m_fnd_vs(vs), m_fnd_vm(vm)
+ { }
template<typename Cntnr>
void
- operator()(__gnu_cxx::typelist::detail::type_to_type<Cntnr>);
+ operator()(Cntnr);
private:
- subscript_find_test(const subscript_find_test& );
+ subscript_find_test(const subscript_find_test&);
private:
const It m_ins_b;
-
const It m_fnd_b;
-
const size_t m_ins_vn;
const size_t m_ins_vs;
const size_t m_ins_vm;
-
const size_t m_fnd_vn;
const size_t m_fnd_vs;
const size_t m_fnd_vm;
};
- PB_DS_CLASS_T_DEC
- PB_DS_CLASS_C_DEC::
- subscript_find_test(It ins_b, It fnd_b, size_t ins_vn, size_t ins_vs, size_t ins_vm, size_t fnd_vn, size_t fnd_vs, size_t fnd_vm) :
- m_ins_b(ins_b),
- m_fnd_b(fnd_b),
- m_ins_vn(ins_vn),
- m_ins_vs(ins_vs),
- m_ins_vm(ins_vm),
- m_fnd_vn(fnd_vn),
- m_fnd_vs(fnd_vs),
- m_fnd_vm(fnd_vm)
- { }
-
- PB_DS_CLASS_T_DEC
- template<typename Cntnr>
+ template<typename It>
+ template<typename Cntnr>
void
- PB_DS_CLASS_C_DEC::
- operator()(__gnu_cxx::typelist::detail::type_to_type<Cntnr>)
+ subscript_find_test<It>::
+ operator()(Cntnr)
{
- xml_result_set_performance_formatter res_set_fmt(
- string_form<Cntnr>::name(),
- string_form<Cntnr>::desc());
+ typedef xml_result_set_performance_formatter formatter_type;
+ formatter_type res_set_fmt(string_form<Cntnr>::name(),
+ string_form<Cntnr>::desc());
- for (size_t size_i = 0; m_ins_vn + size_i* m_ins_vs < m_ins_vm; ++size_i)
+ for (size_t i = 0; m_ins_vn + i* m_ins_vs < m_ins_vm; ++i)
{
- const size_t v = m_ins_vn + size_i* m_ins_vs;
- const size_t fnd_size = m_fnd_vn + size_i* m_fnd_vs;
+ const size_t v = m_ins_vn + i* m_ins_vs;
+ const size_t fnd_size = m_fnd_vn + i* m_fnd_vs;
It ins_it_b = m_ins_b;
It ins_it_e = m_ins_b;
res_set_fmt.add_res(v, res / fnd_size);
}
}
-
-#undef PB_DS_CLASS_T_DEC
-
-#undef PB_DS_CLASS_C_DEC
-
} // namespace test
-
} // namespace pb_ds
-#endif // #ifndef PB_DS_SUBSCRIPT_TEST_HPP
+#endif
namespace pb_ds
{
-
namespace test
{
-
namespace detail
{
-
template<typename It, class Cntnr>
class subscript_insert_functor
{
public:
- subscript_insert_functor(It ins_it_b, It ins_it_e) : m_ins_it_b(ins_it_b),
- m_ins_it_e(ins_it_e)
+ subscript_insert_functor(It ins_it_b, It ins_it_e)
+ : m_ins_it_b(ins_it_b), m_ins_it_e(ins_it_e)
{ }
void
for (std::size_t i = 0; i < resolution; ++i)
{
Cntnr cntnr;
-
for (It ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it)
++cntnr[ins_it->first];
}
} // namespace detail
-#define PB_DS_CLASS_T_DEC \
- template<typename It>
-
-#define PB_DS_CLASS_C_DEC \
- subscript_insert_test< \
- It>
-
template<typename It>
class subscript_insert_test : private pb_ds::test::detail::timing_test_base
{
public:
- subscript_insert_test(It ins_b, It fnd_b, size_t ins_vn, size_t ins_vs, size_t ins_vm, size_t fnd_vn, size_t fnd_vs, size_t fnd_vm);
+ subscript_insert_test(It ins_b, It b, size_t ins_vn, size_t ins_vs,
+ size_t ins_vm, size_t vn, size_t vs, size_t vm)
+ : m_ins_b(ins_b), m_fnd_b(b), m_ins_vn(ins_vn), m_ins_vs(ins_vs),
+ m_ins_vm(ins_vm), m_fnd_vn(vn), m_fnd_vs(vs), m_fnd_vm(vm)
+ { }
template<typename Cntnr>
void
- operator()(__gnu_cxx::typelist::detail::type_to_type<Cntnr>);
+ operator()(Cntnr);
private:
subscript_insert_test(const subscript_insert_test& );
private:
const It m_ins_b;
-
const It m_fnd_b;
-
const size_t m_ins_vn;
const size_t m_ins_vs;
const size_t m_ins_vm;
-
const size_t m_fnd_vn;
const size_t m_fnd_vs;
const size_t m_fnd_vm;
};
- PB_DS_CLASS_T_DEC
- PB_DS_CLASS_C_DEC::
- subscript_insert_test(It ins_b, It fnd_b, size_t ins_vn, size_t ins_vs, size_t ins_vm, size_t fnd_vn, size_t fnd_vs, size_t fnd_vm) :
- m_ins_b(ins_b),
- m_fnd_b(fnd_b),
- m_ins_vn(ins_vn),
- m_ins_vs(ins_vs),
- m_ins_vm(ins_vm),
- m_fnd_vn(fnd_vn),
- m_fnd_vs(fnd_vs),
- m_fnd_vm(fnd_vm)
- { }
-
- PB_DS_CLASS_T_DEC
+ template<typename It>
template<typename Cntnr>
void
- PB_DS_CLASS_C_DEC::
- operator()(__gnu_cxx::typelist::detail::type_to_type<Cntnr>)
+ subscript_insert_test<It>::
+ operator()(Cntnr)
{
- xml_result_set_performance_formatter res_set_fmt(
- string_form<Cntnr>::name(),
- string_form<Cntnr>::desc());
+ typedef xml_result_set_performance_formatter formatter_type;
+ formatter_type res_set_fmt(string_form<Cntnr>::name(),
+ string_form<Cntnr>::desc());
- for (size_t size_i = 0; m_ins_vn + size_i* m_ins_vs < m_ins_vm; ++size_i)
+ for (size_t i = 0; m_ins_vn + i * m_ins_vs < m_ins_vm; ++i)
{
- const size_t v = m_ins_vn + size_i* m_ins_vs;
-
+ const size_t v = m_ins_vn + i * m_ins_vs;
It ins_it_b = m_ins_b;
It ins_it_e = m_ins_b;
std::advance(ins_it_e, v);
-
pb_ds::test::detail::subscript_insert_functor<It, Cntnr>
fn(ins_it_b, ins_it_e);
res_set_fmt.add_res(v, res / v);
}
}
-
-#undef PB_DS_CLASS_T_DEC
-
-#undef PB_DS_CLASS_C_DEC
-
} // namespace test
-
} // namespace pb_ds
-#endif // #ifndef PB_DS_SUBSCRIPT_TEST_HPP
+#endif
namespace pb_ds
{
-
namespace test
{
-
namespace detail
{
-
-#define PB_DS_STATIC_ASSERT(UNIQUE, E) \
- typedef \
- pb_ds::detail::static_assert_dumclass< \
- sizeof(pb_ds::detail::static_assert<(bool)(E)>)> \
- UNIQUE##static_assert_type
+#define PB_DS_STATIC_ASSERT(UNIQUE, E) \
+ typedef \
+ pb_ds::detail::static_assert_dumclass<sizeof(pb_ds::detail::static_assert<(bool)(E)>)> UNIQUE##static_assert_type
template<typename Cntnr, bool Native>
class order_statistics_functor
{
public:
- order_statistics_functor(Cntnr& r_container) : m_r_container(r_container)
+ order_statistics_functor(Cntnr& container) : m_r_container(container)
{ }
void
enum
{
support_detected =
- pb_ds::test::detail::tree_supports_order_statistics<
- Cntnr>::value
+ pb_ds::test::detail::tree_supports_order_statistics<Cntnr>::value
};
PB_DS_STATIC_ASSERT(correct_type, support_detected);
for (std::size_t i = 0; i < resolution; ++i)
{
typename Cntnr::const_iterator it = m_r_container.begin();
-
typename Cntnr::const_iterator e = m_r_container.end();
-
const size_t max_size = m_r_container.size();
-
while (it != e)
if (m_r_container.order_of_key(*(it++)) > max_size)
abort();
};
template<typename Cntnr>
- class order_statistics_functor<
- Cntnr,
- false>
+ class order_statistics_functor<Cntnr, false>
{
public:
- order_statistics_functor(Cntnr& r_container) : m_r_container(r_container)
+ order_statistics_functor(Cntnr& container) : m_r_container(container)
{ }
void
{
for (std::size_t i = 0; i < resolution; ++i)
{
- typename Cntnr::const_iterator b = m_r_container.begin();
-
- typename Cntnr::const_iterator e = m_r_container.end();
-
- typename Cntnr::const_iterator it = b;
-
+ typedef typename Cntnr::const_iterator const_iterator;
+ const_iterator b = m_r_container.begin();
+ const_iterator e = m_r_container.end();
+ const_iterator it = b;
const size_t max_size = m_r_container.size();
-
while (it != e)
{
- typename Cntnr::const_iterator f_it = m_r_container.find(*(it++));
-
+ const_iterator f_it = m_r_container.find(*(it++));
if (static_cast<size_t>(std::distance(b, f_it)) > max_size)
abort();
}
private:
Cntnr& m_r_container;
};
-
} // namespace detail
-#define PB_DS_CLASS_T_DEC \
- template<bool Support_Order_Statistics>
-
-#define PB_DS_CLASS_C_DEC \
- tree_order_statistics_test< \
- Support_Order_Statistics>
-
template<bool Support_Order_Statistics>
- class tree_order_statistics_test : private pb_ds::test::detail::timing_test_base
+ class tree_order_statistics_test
+ : private pb_ds::test::detail::timing_test_base
{
public:
- tree_order_statistics_test(size_t vn, size_t vs, size_t vm);
+ tree_order_statistics_test(size_t vn, size_t vs, size_t vm)
+ : m_vn(vn), m_vs(vs), m_vm(vm)
+ { }
template<typename Cntnr>
void
- operator()(__gnu_cxx::typelist::detail::type_to_type<Cntnr>);
+ operator()(Cntnr);
private:
tree_order_statistics_test(const tree_order_statistics_test& );
const size_t m_vm;
};
- PB_DS_CLASS_T_DEC
- PB_DS_CLASS_C_DEC::
- tree_order_statistics_test(size_t vn, size_t vs, size_t vm) :
- m_vn(vn),
- m_vs(vs),
- m_vm(vm)
- { }
-
- PB_DS_CLASS_T_DEC
+ template<bool Support_Order_Statistics>
template<typename Cntnr>
void
- PB_DS_CLASS_C_DEC::
- operator()(__gnu_cxx::typelist::detail::type_to_type<Cntnr>)
+ tree_order_statistics_test<Support_Order_Statistics>::
+ operator()(Cntnr)
{
- xml_result_set_performance_formatter res_set_fmt(
- string_form<Cntnr>::name(),
- string_form<Cntnr>::desc());
+ typedef xml_result_set_performance_formatter formatter_type;
+ formatter_type res_set_fmt(string_form<Cntnr>::name(),
+ string_form<Cntnr>::desc());
for (size_t v = m_vn; v < m_vm; v += m_vs)
{
Cntnr cntnr;
-
for (size_t ins = 0; ins < v; ++ ins)
cntnr.insert((typename Cntnr::value_type)ins);
res_set_fmt.add_res(v, res / v);
}
}
-
-#undef PB_DS_CLASS_T_DEC
-
-#undef PB_DS_CLASS_C_DEC
-
-#undef PB_DS_STATIC_ASSERT
-
} // namespace test
-
} // namespace pb_ds
-#endif // #ifndef PB_DS_TREE_ORDER_STATISTICS_TEST_HPP
+#endif
namespace pb_ds
{
-
namespace test
{
-
namespace detail
{
-
template<typename Cntnr, bool Support_Split_Join>
class split_join_functor
{
{
typename Cntnr::const_iterator mid_it = m_r_container.begin();
std::advance(mid_it, m_r_container.size() / 2);
-
Cntnr other;
-
m_r_container.split(*mid_it, other);
-
m_r_container.join(other);
}
}
};
template<typename Cntnr>
- class split_join_functor<
- Cntnr,
- false>
+ class split_join_functor<Cntnr, false>
{
public:
split_join_functor(Cntnr& r_container) : m_r_container(r_container)
private:
Cntnr& m_r_container;
};
-
} // namespace detail
-#define PB_DS_CLASS_T_DEC \
- template<bool Support_Split_Join>
-
-#define PB_DS_CLASS_C_DEC \
- tree_split_join_test< \
- Support_Split_Join>
-
template<bool Support_Split_Join>
class tree_split_join_test : private pb_ds::test::detail::timing_test_base
{
template<typename Cntnr>
void
- operator()(__gnu_cxx::typelist::detail::type_to_type<Cntnr>);
+ operator()(Cntnr);
private:
tree_split_join_test(const tree_split_join_test& );
const size_t m_vm;
};
- PB_DS_CLASS_T_DEC
- PB_DS_CLASS_C_DEC::
+ template<bool Support_Split_Join>
+ tree_split_join_test<Support_Split_Join>::
tree_split_join_test(size_t vn, size_t vs, size_t vm) :
m_vn(vn),
m_vs(vs),
m_vm(vm)
{ }
- PB_DS_CLASS_T_DEC
+ template<bool Support_Split_Join>
template<typename Cntnr>
void
- PB_DS_CLASS_C_DEC::
- operator()(__gnu_cxx::typelist::detail::type_to_type<Cntnr>)
+ tree_split_join_test<Support_Split_Join>::
+ operator()(Cntnr)
{
- xml_result_set_performance_formatter res_set_fmt(
- string_form<Cntnr>::name(),
- string_form<Cntnr>::desc());
+ typedef xml_result_set_performance_formatter formatter_type;
+ formatter_type res_set_fmt(string_form<Cntnr>::name(),
+ string_form<Cntnr>::desc());
for (size_t v = m_vn; v < m_vm; v += m_vs)
{
Cntnr cntnr;
-
for (size_t ins = 0; ins < v; ++ ins)
cntnr.insert((typename Cntnr::value_type)ins);
const double res =
pb_ds::test::detail::timing_test_base::operator()(fn);
-
res_set_fmt.add_res(v, res);
}
}
-
-#undef PB_DS_CLASS_T_DEC
-
-#undef PB_DS_CLASS_C_DEC
-
} // namespace test
-
} // namespace pb_ds
-#endif // #ifndef PB_DS_TREE_SPLIT_JOIN_TEST_HPP
+#endif
namespace pb_ds
{
-
namespace test
{
-
-#define PB_DS_CLASS_T_DEC \
- template<typename It>
-
-#define PB_DS_CLASS_C_DEC \
- pop_test< \
- It>
-
template<typename It>
class pop_test
{
public:
- pop_test(It ins_b, size_t ins_vn, size_t ins_vs, size_t ins_vm);
+ pop_test(It ins_b, size_t ins_vn, size_t ins_vs, size_t ins_vm)
+ : m_ins_b(ins_b), m_ins_vn(ins_vn), m_ins_vs(ins_vs), m_ins_vm(ins_vm)
+ { }
template<typename Cntnr>
void
- operator()(__gnu_cxx::typelist::detail::type_to_type<Cntnr>);
+ operator()(Cntnr);
private:
- pop_test(const pop_test& );
+ pop_test(const pop_test&);
- private:
const It m_ins_b;
-
const size_t m_ins_vn;
const size_t m_ins_vs;
const size_t m_ins_vm;
};
- PB_DS_CLASS_T_DEC
- PB_DS_CLASS_C_DEC::
- pop_test(It ins_b, size_t ins_vn, size_t ins_vs, size_t ins_vm) :
- m_ins_b(ins_b),
- m_ins_vn(ins_vn),
- m_ins_vs(ins_vs),
- m_ins_vm(ins_vm)
- { }
-
- PB_DS_CLASS_T_DEC
+ template<typename It>
template<typename Cntnr>
void
- PB_DS_CLASS_C_DEC::
- operator()(__gnu_cxx::typelist::detail::type_to_type<Cntnr>)
+ pop_test<It>::
+ operator()(Cntnr)
{
- xml_result_set_performance_formatter res_set_fmt(
- string_form<Cntnr>::name(),
- string_form<Cntnr>::desc());
+ typedef xml_result_set_performance_formatter formatter_type;
+ formatter_type res_set_fmt(string_form<Cntnr>::name(),
+ string_form<Cntnr>::desc());
- for (size_t size_i = 0; m_ins_vn + size_i* m_ins_vs < m_ins_vm; ++size_i)
+ for (size_t i = 0; m_ins_vn + i * m_ins_vs < m_ins_vm; ++i)
{
- const size_t ins_size = m_ins_vn + size_i* m_ins_vs;
-
+ const size_t ins_size = m_ins_vn + i * m_ins_vs;
It ins_it_b = m_ins_b;
It ins_it_e = m_ins_b;
std::advance(ins_it_e, ins_size);
mem_track_allocator<char> alloc;
const size_t init_mem = alloc.get_total();
-
Cntnr cntnr;
-
for (It ins_it = ins_it_b; ins_it != ins_it_e; ++ins_it)
cntnr.push(ins_it->first);
cntnr.pop();
const size_t final_mem = alloc.get_total();
-
assert(final_mem > init_mem);
-
const size_t delta_mem = final_mem - init_mem;
-
res_set_fmt.add_res(ins_size, static_cast<double>(delta_mem));
}
}
-
-#undef PB_DS_CLASS_T_DEC
-
-#undef PB_DS_CLASS_C_DEC
-
} // namespace test
-
} // namespace pb_ds
#endif // #ifndef PB_DS_POP_TEST_HPP
template<typename It>
class join_test : private pb_ds::test::detail::timing_test_base
{
- const It m_ins_b;
- const size_t m_ins_vn;
- const size_t m_ins_vs;
- const size_t m_ins_vm;
-
public:
join_test(It ins_b, size_t ins_vn, size_t ins_vs, size_t ins_vm)
- : m_ins_b(ins_b), m_ins_vn(ins_vn), m_ins_vs(ins_vs), m_ins_vm(ins_vm)
+ : m_ins_b(ins_b), m_ins_vn(ins_vn), m_ins_vs(ins_vs), m_ins_vm(ins_vm)
{ }
template<typename Cntnr>
void
- operator()(__gnu_cxx::typelist::detail::type_to_type<Cntnr>)
+ operator()(Cntnr)
{
using pb_ds::test::detail::double_push_functor;
using pb_ds::test::detail::double_push_join_functor;
typedef pb_ds::test::detail::timing_test_base base_type;
- typedef xml_result_set_performance_formatter result_type;
- result_type res(string_form<Cntnr>::name(), string_form<Cntnr>::desc());
+ typedef xml_result_set_performance_formatter formatter_type;
+ formatter_type res(string_form<Cntnr>::name(),
+ string_form<Cntnr>::desc());
for (size_t n = 0; m_ins_vn + n* m_ins_vs < m_ins_vm; ++n)
{
double_push_join_functor<It, Cntnr> double_push_join_fn(b, e);
const double double_push_join_res = base_type::operator()(double_push_join_fn);
- const double effective_delta = std::max(double_push_join_res - double_push_res,
- base_type::min_time_res());
+ const double effective_delta = std::max(double_push_join_res - double_push_res, base_type::min_time_res());
res.add_res(v, effective_delta / v);
}
}
template<typename Cntnr>
void
- join(__gnu_cxx::typelist::detail::type_to_type<Cntnr>, It b, It e)
+ join(Cntnr, It b, It e)
{
Cntnr cntnr;
typedef typename Cntnr::const_reference const_reference;
for (It it = b; it != e; ++it)
cntnr.join(const_reference(*it));
}
+
+ const It m_ins_b;
+ const size_t m_ins_vn;
+ const size_t m_ins_vs;
+ const size_t m_ins_vm;
};
} // namespace test
} // namespace pb_ds
-#endif // #ifndef PB_DS_JOIN_TEST_HPP
+#endif
namespace pb_ds
{
-
namespace test
{
-
namespace detail
{
-
template<typename It, class Cntnr, class Tag>
class push_functor
{
public:
- push_functor(It ins_it_b, It ins_it_e) : m_ins_it_b(ins_it_b),
- m_ins_it_e(ins_it_e)
+ push_functor(It ins_it_b, It ins_it_e)
+ : m_ins_it_b(ins_it_b), m_ins_it_e(ins_it_e)
{ }
void
operator()(std::size_t resolution)
{
+ typedef typename Cntnr::point_iterator point_iterator;
+ typedef typename Cntnr::const_reference const_reference;
for (std::size_t i = 0; i < resolution; ++i)
{
Cntnr c;
-
- typedef std::vector< typename Cntnr::point_iterator> it_vec_t;
-
+ typedef std::vector<point_iterator> it_vec_t;
it_vec_t m_a_its;
-
for (It ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it)
- m_a_its.push_back(c.push((typename Cntnr::const_reference)(ins_it->first)));
+ m_a_its.push_back(c.push(const_reference(ins_it->first)));
}
}
template<typename It, class Cntnr, class Tag>
class push_modify_functor
{
+ private:
+ typedef typename Cntnr::point_iterator point_iterator;
+ typedef typename Cntnr::const_reference const_reference;
+ typedef typename Cntnr::value_type value_type;
+
public:
- push_modify_functor(It ins_it_b, It ins_it_e, typename Cntnr::value_type mod_val) : m_ins_it_b(ins_it_b),
- m_ins_it_e(ins_it_e),
- m_mod_val(mod_val)
+ push_modify_functor(It ins_it_b, It ins_it_e, value_type mod_val)
+ : m_ins_it_b(ins_it_b), m_ins_it_e(ins_it_e), m_mod_val(mod_val)
{ }
void
for (std::size_t i = 0; i < resolution; ++i)
{
Cntnr c;
-
- typedef std::vector< typename Cntnr::point_iterator> it_vec_t;
-
+ typedef std::vector<typename Cntnr::point_iterator> it_vec_t;
it_vec_t m_a_its;
-
for (It ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it)
- m_a_its.push_back(c.push((typename Cntnr::const_reference)(ins_it->first)));
+ m_a_its.push_back(c.push(const_reference(ins_it->first)));
typename it_vec_t::iterator mod_it = m_a_its.begin();
-
while (mod_it != m_a_its.end())
c.modify(*mod_it++, m_mod_val);
}
private:
const It m_ins_it_b;
const It m_ins_it_e;
-
- const typename Cntnr::value_type m_mod_val;
+ const value_type m_mod_val;
};
template<typename It, class Cntnr>
- class push_functor<
- It,
- Cntnr,
- pb_ds::binary_heap_tag>
+ class push_functor<It, Cntnr, pb_ds::binary_heap_tag>
{
public:
- push_functor(It ins_it_b, It ins_it_e) : m_ins_it_b(ins_it_b),
- m_ins_it_e(ins_it_e)
+ push_functor(It ins_it_b, It ins_it_e)
+ : m_ins_it_b(ins_it_b), m_ins_it_e(ins_it_e)
{ }
void
operator()(std::size_t resolution)
{
+ typedef typename Cntnr::const_reference const_reference;
for (std::size_t i = 0; i < resolution; ++i)
{
Cntnr c;
-
for (It ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it)
- c.push((typename Cntnr::const_reference)(ins_it->first));
+ c.push(const_reference(ins_it->first));
}
}
};
template<typename It, class Cntnr>
- class push_modify_functor<
- It,
- Cntnr,
- pb_ds::binary_heap_tag>
+ class push_modify_functor<It, Cntnr, pb_ds::binary_heap_tag>
{
+ private:
+ typedef typename Cntnr::iterator iterator;
+ typedef typename Cntnr::const_reference const_reference;
+ typedef typename Cntnr::value_type value_type;
+
public:
- push_modify_functor(It ins_it_b, It ins_it_e, typename Cntnr::value_type mod_val) : m_ins_it_b(ins_it_b),
- m_ins_it_e(ins_it_e),
- m_mod_val(mod_val)
+ push_modify_functor(It ins_it_b, It ins_it_e, value_type mod_val)
+ : m_ins_it_b(ins_it_b), m_ins_it_e(ins_it_e), m_mod_val(mod_val)
{ }
void
for (std::size_t i = 0; i < resolution; ++i)
{
Cntnr c;
-
It ins_it;
-
for (ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it)
- c.push((typename Cntnr::const_reference)(ins_it->first));
+ c.push(const_reference(ins_it->first));
for (ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it)
{
bool modified = false;
-
- for (typename Cntnr::iterator it = c.begin(); !modified&& it != c.end(); ++it)
+ for (iterator it = c.begin(); !modified && it != c.end(); ++it)
if (*it == ins_it->first)
{
c.modify(it, m_mod_val);
-
modified = true;
}
}
private:
const It m_ins_it_b;
const It m_ins_it_e;
-
- const typename Cntnr::value_type m_mod_val;
+ const value_type m_mod_val;
};
template<typename It, class Cntnr>
- class push_functor<
- It,
- Cntnr,
- pb_ds::test::native_pq_tag>
+ class push_functor<It, Cntnr, pb_ds::test::native_pq_tag>
{
public:
- push_functor(It ins_it_b, It ins_it_e) : m_ins_it_b(ins_it_b),
- m_ins_it_e(ins_it_e)
+ push_functor(It ins_it_b, It ins_it_e)
+ : m_ins_it_b(ins_it_b), m_ins_it_e(ins_it_e)
{ }
void
operator()(std::size_t resolution)
{
+ typedef typename Cntnr::const_reference const_reference;
for (std::size_t i = 0; i < resolution; ++i)
{
Cntnr c;
for (It ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it)
- c.push((typename Cntnr::const_reference)(ins_it->first));
+ c.push(const_reference(ins_it->first));
}
}
};
template<typename It, class Cntnr>
- class push_modify_functor<
- It,
- Cntnr,
- pb_ds::test::native_pq_tag>
+ class push_modify_functor<It, Cntnr, pb_ds::test::native_pq_tag>
{
+ private:
+ typedef typename Cntnr::value_type value_type;
+ typedef typename Cntnr::const_reference const_reference;
+
public:
- push_modify_functor(It ins_it_b, It ins_it_e, typename Cntnr::value_type mod_val) : m_ins_it_b(ins_it_b),
- m_ins_it_e(ins_it_e),
- m_mod_val(mod_val)
+ push_modify_functor(It ins_it_b, It ins_it_e, value_type mod_val)
+ : m_ins_it_b(ins_it_b), m_ins_it_e(ins_it_e), m_mod_val(mod_val)
{ }
void
for (std::size_t i = 0; i < resolution; ++i)
{
Cntnr c;
-
It ins_it;
-
for (ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it)
- c.push((typename Cntnr::const_reference)(ins_it->first));
-
+ c.push(const_reference(ins_it->first));
for (ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it)
c.modify(ins_it->first, m_mod_val);
}
private:
const It m_ins_it_b;
const It m_ins_it_e;
-
- const typename Cntnr::value_type m_mod_val;
+ const value_type m_mod_val;
};
-
} // namespace detail
-#define PB_DS_CLASS_T_DEC \
- template<typename It>
-
-#define PB_DS_CLASS_C_DEC \
- modify_test< \
- It>
-
template<typename It>
class modify_test : private pb_ds::test::detail::timing_test_base
{
public:
- modify_test(It ins_b, size_t ins_vn, size_t ins_vs, size_t ins_vm, bool m_modify_up);
+ modify_test(It b, size_t vn, size_t vs, size_t vm, bool modify_up)
+ : m_ins_b(b), m_ins_vn(vn), m_ins_vs(vs), m_ins_vm(vm),
+ m_modify_up(modify_up)
+ { }
template<typename Cntnr>
void
- operator()(__gnu_cxx::typelist::detail::type_to_type<Cntnr>);
+ operator()(Cntnr);
private:
- modify_test(const modify_test& );
+ modify_test(const modify_test&);
template<typename Cntnr>
void
- modify(__gnu_cxx::typelist::detail::type_to_type<Cntnr>, It ins_it_b, It ins_it_e);
+ modify(Cntnr, It ins_it_b, It ins_it_e)
+ {
+ typedef typename Cntnr::const_reference const_reference;
+ Cntnr cntnr;
+ for (It ins_it = ins_it_b; ins_it != ins_it_e; ++ins_it)
+ cntnr.modify(const_reference(*ins_it));
+ }
- private:
const It m_ins_b;
-
const size_t m_ins_vn;
const size_t m_ins_vs;
const size_t m_ins_vm;
-
const bool m_modify_up;
};
- PB_DS_CLASS_T_DEC
- PB_DS_CLASS_C_DEC::
- modify_test(It ins_b, size_t ins_vn, size_t ins_vs, size_t ins_vm, bool modify_up) :
- m_ins_b(ins_b),
- m_ins_vn(ins_vn),
- m_ins_vs(ins_vs),
- m_ins_vm(ins_vm),
- m_modify_up(modify_up)
- { }
-
- PB_DS_CLASS_T_DEC
+ template<typename It>
template<typename Cntnr>
void
- PB_DS_CLASS_C_DEC::
- operator()(__gnu_cxx::typelist::detail::type_to_type<Cntnr>)
+ modify_test<It>::
+ operator()(Cntnr)
{
- xml_result_set_performance_formatter res_set_fmt(
- string_form<Cntnr>::name(),
- string_form<Cntnr>::desc());
-
- for (size_t size_i = 0; m_ins_vn + size_i* m_ins_vs < m_ins_vm; ++size_i)
- {
- const size_t v = m_ins_vn + size_i* m_ins_vs;
+ typedef typename Cntnr::value_type value_type;
+ typedef typename Cntnr::container_category container_category;
+ typedef typename Cntnr::const_reference const_reference;
+ typedef pb_ds::test::detail::timing_test_base timing_test_base;
- It ins_it_b = m_ins_b;
- It ins_it_e = m_ins_b;
- std::advance(ins_it_e, v);
+ typedef xml_result_set_performance_formatter formatter_type;
+ formatter_type res_set_fmt(string_form<Cntnr>::name(),
+ string_form<Cntnr>::desc());
- pb_ds::test::detail::push_functor<It, Cntnr, typename Cntnr::container_category>
- push_fn(ins_it_b, ins_it_e);
+ for (size_t i = 0; m_ins_vn + i * m_ins_vs < m_ins_vm; ++i)
+ {
+ const size_t v = m_ins_vn + i * m_ins_vs;
+ It b = m_ins_b;
+ It e = m_ins_b;
+ std::advance(e, v);
- const double push_res =
- pb_ds::test::detail::timing_test_base::operator()(push_fn);
+ pb_ds::test::detail::push_functor<It, Cntnr, container_category>
+ push_fn( b, e);
- typename Cntnr::value_type mod_val = ins_it_b->first;
+ const double push_res = timing_test_base::operator()(push_fn);
+ value_type val = b->first;
{
Cntnr mod_val_container;
- for (It mod_val_it = ins_it_b; mod_val_it != ins_it_e; ++mod_val_it)
+ for (It mod_val_it = b; mod_val_it != e; ++mod_val_it)
{
- typename Cntnr::value_type pot = mod_val_it->first;
-
- if (m_modify_up == mod_val_container.get_cmp_fn()(mod_val, pot))
- mod_val = pot;
+ value_type pot = mod_val_it->first;
+ if (m_modify_up == mod_val_container.get_cmp_fn()(val, pot))
+ val = pot;
}
}
- pb_ds::test::detail::push_modify_functor<It, Cntnr, typename Cntnr::container_category>
- push_modify_fn(ins_it_b, ins_it_e, mod_val);
+ pb_ds::test::detail::push_modify_functor<It, Cntnr, container_category>
+ push_modify_fn(b, e, val);
- const double push_modify_res =
- pb_ds::test::detail::timing_test_base::operator()(push_modify_fn);
+ const double push_modify_res = timing_test_base::operator()(push_modify_fn);
- const double effective_delta = std::max(
- push_modify_res - push_res,
- pb_ds::test::detail::timing_test_base::min_time_res());
+ const double effective_delta = std::max(push_modify_res - push_res,
+ timing_test_base::min_time_res());
res_set_fmt.add_res(v, effective_delta / v);
}
}
-
- PB_DS_CLASS_T_DEC
- template<typename Cntnr>
- void
- PB_DS_CLASS_C_DEC::
- modify(__gnu_cxx::typelist::detail::type_to_type<Cntnr>, It ins_it_b, It ins_it_e)
- {
- Cntnr cntnr;
-
- for (It ins_it = ins_it_b; ins_it != ins_it_e; ++ins_it)
- cntnr.modify((typename Cntnr::const_reference)(*ins_it));
- }
-
-#undef PB_DS_CLASS_T_DEC
-
-#undef PB_DS_CLASS_C_DEC
-
} // namespace test
-
} // namespace pb_ds
-#endif // #ifndef PB_DS_JOIN_TEST_HPP
+#endif
namespace pb_ds
{
-
namespace test
{
-
namespace detail
{
-
template<typename It, class Cntnr>
class push_pop_push_pop_functor
{
public:
- push_pop_push_pop_functor(It ins_it_b, It ins_it_e) : m_ins_it_b(ins_it_b),
- m_ins_it_e(ins_it_e)
+ push_pop_push_pop_functor(It ins_it_b, It ins_it_e)
+ : m_ins_it_b(ins_it_b), m_ins_it_e(ins_it_e)
{ }
void
for (std::size_t i = 0; i < resolution; ++i)
{
Cntnr cntnr;
-
for (It ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it)
cntnr.push((typename Cntnr::const_reference)(ins_it->first));
-
while (!cntnr.empty())
cntnr.pop();
}
} // namespace detail
-#define PB_DS_CLASS_T_DEC \
- template<typename It>
-
-#define PB_DS_CLASS_C_DEC \
- push_pop_test< \
- It>
-
template<typename It>
class push_pop_test : private pb_ds::test::detail::timing_test_base
{
public:
- push_pop_test(It ins_b, size_t ins_vn, size_t ins_vs, size_t ins_vm);
+ push_pop_test(It ins_b, size_t ins_vn, size_t ins_vs, size_t ins_vm)
+ : m_ins_b(ins_b), m_ins_vn(ins_vn), m_ins_vs(ins_vs), m_ins_vm(ins_vm)
+ { }
template<typename Cntnr>
void
- operator()(__gnu_cxx::typelist::detail::type_to_type<Cntnr>);
+ operator()(Cntnr);
private:
- push_pop_test(const push_pop_test& );
+ push_pop_test(const push_pop_test&);
template<typename Cntnr>
void
- push(__gnu_cxx::typelist::detail::type_to_type<Cntnr>, It ins_it_b, It ins_it_e);
+ push(Cntnr, It ins_it_b, It ins_it_e)
+ {
+ Cntnr cntnr;
+ for (It ins_it = ins_it_b; ins_it != ins_it_e; ++ins_it)
+ cntnr.push((typename Cntnr::const_reference)(*ins_it));
+ }
- private:
const It m_ins_b;
-
const size_t m_ins_vn;
const size_t m_ins_vs;
const size_t m_ins_vm;
};
- PB_DS_CLASS_T_DEC
- PB_DS_CLASS_C_DEC::
- push_pop_test(It ins_b, size_t ins_vn, size_t ins_vs, size_t ins_vm) :
- m_ins_b(ins_b),
- m_ins_vn(ins_vn),
- m_ins_vs(ins_vs),
- m_ins_vm(ins_vm)
- { }
-
- PB_DS_CLASS_T_DEC
+
+ template<typename It>
template<typename Cntnr>
void
- PB_DS_CLASS_C_DEC::
- operator()(__gnu_cxx::typelist::detail::type_to_type<Cntnr>)
+ push_pop_test<It>::
+ operator()(Cntnr)
{
- xml_result_set_performance_formatter res_set_fmt(
- string_form<Cntnr>::name(),
- string_form<Cntnr>::desc());
-
- for (size_t size_i = 0; m_ins_vn + size_i* m_ins_vs < m_ins_vm; ++size_i)
+ typedef xml_result_set_performance_formatter formatter_type;
+ formatter_type res_set_fmt(string_form<Cntnr>::name(),
+ string_form<Cntnr>::desc());
+
+ for (size_t i = 0; m_ins_vn + i * m_ins_vs < m_ins_vm; ++i)
{
- const size_t v = m_ins_vn + size_i* m_ins_vs;
-
+ const size_t v = m_ins_vn + i * m_ins_vs;
It ins_it_b = m_ins_b;
It ins_it_e = m_ins_b;
std::advance(ins_it_e, v);
res_set_fmt.add_res(v, res / v);
}
}
-
- PB_DS_CLASS_T_DEC
- template<typename Cntnr>
- void
- PB_DS_CLASS_C_DEC::
- push(__gnu_cxx::typelist::detail::type_to_type<Cntnr>, It ins_it_b, It ins_it_e)
- {
- Cntnr cntnr;
-
- for (It ins_it = ins_it_b; ins_it != ins_it_e; ++ins_it)
- cntnr.push((typename Cntnr::const_reference)(*ins_it));
- }
-
-#undef PB_DS_CLASS_T_DEC
-
-#undef PB_DS_CLASS_C_DEC
-
} // namespace test
-
} // namespace pb_ds
-#endif // #ifndef PB_DS_PUSH_TEST_HPP
+#endif
namespace pb_ds
{
-
namespace test
{
-
namespace detail
{
-
template<typename It, class Cntnr>
class push_push_functor
{
public:
- push_push_functor(It ins_it_b, It ins_it_e) : m_ins_it_b(ins_it_b),
- m_ins_it_e(ins_it_e)
+ push_push_functor(It ins_it_b, It ins_it_e)
+ : m_ins_it_b(ins_it_b), m_ins_it_e(ins_it_e)
{ }
void
for (std::size_t i = 0; i < resolution; ++i)
{
Cntnr cntnr;
-
for (It ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it)
cntnr.push((typename Cntnr::const_reference)(ins_it->first));
}
const It m_ins_it_b;
const It m_ins_it_e;
};
-
} // namespace detail
-#define PB_DS_CLASS_T_DEC \
- template<typename It>
-
-#define PB_DS_CLASS_C_DEC \
- push_test< \
- It>
-
template<typename It>
class push_test : private pb_ds::test::detail::timing_test_base
{
public:
- push_test(It ins_b, size_t ins_vn, size_t ins_vs, size_t ins_vm);
+ push_test(It ins_b, size_t ins_vn, size_t ins_vs, size_t ins_vm)
+ : m_ins_b(ins_b), m_ins_vn(ins_vn), m_ins_vs(ins_vs), m_ins_vm(ins_vm)
+ { }
template<typename Cntnr>
void
- operator()(__gnu_cxx::typelist::detail::type_to_type<Cntnr>);
+ operator()(Cntnr);
private:
push_test(const push_test& );
template<typename Cntnr>
void
- push(__gnu_cxx::typelist::detail::type_to_type<Cntnr>, It ins_it_b, It ins_it_e);
+ push(Cntnr, It ins_it_b, It ins_it_e);
- private:
const It m_ins_b;
-
const size_t m_ins_vn;
const size_t m_ins_vs;
const size_t m_ins_vm;
};
- PB_DS_CLASS_T_DEC
- PB_DS_CLASS_C_DEC::
- push_test(It ins_b, size_t ins_vn, size_t ins_vs, size_t ins_vm) :
- m_ins_b(ins_b),
- m_ins_vn(ins_vn),
- m_ins_vs(ins_vs),
- m_ins_vm(ins_vm)
- { }
- PB_DS_CLASS_T_DEC
+ template<typename It>
template<typename Cntnr>
void
- PB_DS_CLASS_C_DEC::
- operator()(__gnu_cxx::typelist::detail::type_to_type<Cntnr>)
+ push_test<It>::
+ operator()(Cntnr)
{
- xml_result_set_performance_formatter res_set_fmt(
- string_form<Cntnr>::name(),
- string_form<Cntnr>::desc());
+ typedef xml_result_set_performance_formatter formatter_type;
+ formatter_type res_set_fmt(string_form<Cntnr>::name(),
+ string_form<Cntnr>::desc());
- for (size_t size_i = 0; m_ins_vn + size_i* m_ins_vs < m_ins_vm; ++size_i)
+ for (size_t i = 0; m_ins_vn + i * m_ins_vs < m_ins_vm; ++i)
{
- const size_t v = m_ins_vn + size_i* m_ins_vs;
-
+ const size_t v = m_ins_vn + i * m_ins_vs;
It ins_it_b = m_ins_b;
It ins_it_e = m_ins_b;
std::advance(ins_it_e, v);
}
}
- PB_DS_CLASS_T_DEC
+ template<typename It>
template<typename Cntnr>
void
- PB_DS_CLASS_C_DEC::
- push(__gnu_cxx::typelist::detail::type_to_type<Cntnr>, It ins_it_b, It ins_it_e)
+ push_test<It>::
+ push(Cntnr, It ins_it_b, It ins_it_e)
{
Cntnr cntnr;
-
for (It ins_it = ins_it_b; ins_it != ins_it_e; ++ins_it)
cntnr.push((typename Cntnr::const_reference)(*ins_it));
}
-
-#undef PB_DS_CLASS_T_DEC
-
-#undef PB_DS_CLASS_C_DEC
-
} // namespace test
-
} // namespace pb_ds
-#endif // #ifndef PB_DS_PUSH_TEST_HPP
+#endif
struct hash
{
- typedef alloc_type::rebind<basic_type>::other::const_reference const_key_reference;
+ typedef alloc_type::rebind<basic_type>::other basic_type_rebind;
+ typedef basic_type_rebind::const_reference const_reference;
+ typedef basic_type::const_iterator const_iterator;
size_t
- operator()(const_key_reference r_key) const
+ operator()(const_reference r_key) const
{
size_t ret = 0;
- typedef basic_type::const_iterator const_iterator;
for (const_iterator it = r_key.begin(); it != r_key.end(); ++it)
ret = ret * 5 + static_cast<size_t>(*it);
return ret;
} // namespace test
} // namespace pb_ds
-#endif // #ifndef PB_DS_RAND_REGRESSION_TEST_COMMON_TYPE_HPP
+#endif
} // namespace test
} // namespace pb_ds
-#endif // #ifndef PB_DS_BASIC_TYPE_HPP
+#endif
operator()();
private:
- typedef Cntnr cntnr;
-
- typedef typename cntnr::allocator allocator;
-
- typedef typename cntnr::size_type size_type;
-
- typedef twister_rand_gen gen;
-
- typedef regression_test_traits<Cntnr> test_traits;
-
- typedef pb_ds::container_traits<Cntnr> container_traits;
-
- typedef typename test_traits::key_type key_type;
-
- typedef typename test_traits::const_key_reference const_key_reference;
-
- typedef typename test_traits::value_type value_type;
-
- typedef typename test_traits::native_type native_type;
+ typedef Cntnr cntnr;
+ typedef typename cntnr::allocator allocator;
+ typedef typename cntnr::size_type size_type;
+ typedef regression_test_traits<Cntnr> test_traits;
+ typedef typename test_traits::key_type key_type;
+ typedef typename test_traits::const_key_reference const_key_reference;
+ typedef typename test_traits::value_type value_type;
+ typedef typename test_traits::native_type native_type;
+ typedef twister_rand_gen gen;
+ typedef pb_ds::container_traits<Cntnr> container_traits;
+ typedef __gnu_cxx::throw_allocator<char> alloc_t;
enum op
{
other_op
};
- typedef __gnu_cxx::throw_allocator<char> alloc_t;
-
- private:
-
op
get_next_op();
void
print_container(const cntnr&, std::ostream& r_os = std::cerr) const;
- private:
struct destructor_printer
{
destructor_printer(const std::string& r_msg)
bool m_print;
};
- private:
- const unsigned long m_seed;
-
- const size_t m_n;
- const size_t m_m;
- const double m_tp;
- const double m_ip;
- const double m_ep;
- const double m_cp;
- const double m_mp;
- const bool m_disp;
-
- twister_rand_gen m_g;
-
- Cntnr* m_p_c;
-
- native_type m_native_c;
-
- alloc_t m_alloc;
-
- size_t m_i;
+ const unsigned long m_seed;
+ const size_t m_n;
+ const size_t m_m;
+ const double m_tp;
+ const double m_ip;
+ const double m_ep;
+ const double m_cp;
+ const double m_mp;
+ const bool m_disp;
+ twister_rand_gen m_g;
+ Cntnr* m_p_c;
+ native_type m_native_c;
+ alloc_t m_alloc;
+ size_t m_i;
};
#include <regression/rand/assoc/detail/constructor_destructor_fn_imps.hpp>
PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
-container_rand_regression_test(unsigned long seed, size_t n, size_t m, double tp, double ip, double ep, double cp, double mp, bool disp) :
- m_seed((seed == 0)?
- twister_rand_gen::get_time_determined_seed():
- seed),
- m_n(n),
- m_m(m),
- m_tp(tp),
- m_ip(ip),
- m_ep(ep),
- m_cp(cp),
- m_mp(mp),
- m_disp(disp),
- m_p_c(NULL)
+container_rand_regression_test(unsigned long seed, size_t n, size_t m,
+ double tp, double ip, double ep, double cp,
+ double mp, bool disp)
+: m_seed((seed == 0) ? twister_rand_gen::get_time_determined_seed() : seed),
+ m_n(n), m_m(m), m_tp(tp), m_ip(ip), m_ep(ep), m_cp(cp), m_mp(mp),
+ m_disp(disp), m_p_c(NULL)
{ }
PB_DS_CLASS_T_DEC
default_constructor()
{
PB_DS_TRACE("default_constructor");
-
bool done = true;
-
m_alloc.set_throw_prob(m_tp);
try
{
m_p_c = new Cntnr;
}
- catch(__gnu_cxx::forced_exception_error& )
+ catch(__gnu_cxx::forced_exception_error&)
{
done = false;
}
if (m_p_c != NULL)
PB_DS_COND_COMPARE(*m_p_c, m_native_c);
-
- return (done);
+ return done;
}
PB_DS_CLASS_T_DEC
swap()
{
PB_DS_TRACE("swap");
-
m_alloc.set_throw_prob(0);
-
Cntnr* p_c = new Cntnr;
-
m_alloc.set_throw_prob(1);
-
p_c->swap(*m_p_c);
-
std::swap(p_c, m_p_c);
-
delete p_c;
-
PB_DS_COND_COMPARE(*m_p_c, m_native_c);
}
copy_constructor()
{
PB_DS_TRACE("copy_constructor");
-
bool done = true;
-
Cntnr* p_c = NULL;
-
m_alloc.set_throw_prob(m_tp);
-
- typename alloc_t::group_throw_prob_adjustor
- adjust(m_p_c->size());
+ typename alloc_t::group_throw_prob_adjustor adjust(m_p_c->size());
try
{
p_c = new Cntnr(*m_p_c);
-
std::swap(p_c, m_p_c);
}
catch(__gnu_cxx::forced_exception_error& )
}
delete p_c;
-
PB_DS_COND_COMPARE(*m_p_c, m_native_c);
-
- return (done);
+ return done;
}
PB_DS_CLASS_T_DEC
assignment_operator()
{
PB_DS_TRACE("assignment operator");
-
bool done = true;
-
Cntnr* p_c = NULL;
-
m_alloc.set_throw_prob(m_tp);
-
- typename alloc_t::group_throw_prob_adjustor
- adjust(m_p_c->size());
+ typename alloc_t::group_throw_prob_adjustor adjust(m_p_c->size());
try
{
p_c = new Cntnr();
-
* p_c =* m_p_c;
-
std::swap(p_c, m_p_c);
}
catch(__gnu_cxx::forced_exception_error& )
}
delete p_c;
-
PB_DS_COND_COMPARE(*m_p_c, m_native_c);
-
- return (done);
+ return done;
}
PB_DS_CLASS_T_DEC
it_constructor()
{
PB_DS_TRACE("it_constructor");
-
- return (it_constructor_imp(typename Cntnr::container_category()));
+ return it_constructor_imp(typename Cntnr::container_category());
}
PB_DS_CLASS_T_DEC
it_constructor_imp(pb_ds::cc_hash_tag)
{
bool done = true;
-
Cntnr* p_c = NULL;
-
m_alloc.set_throw_prob(m_tp);
-
- typename alloc_t::group_throw_prob_adjustor
- adjust(m_p_c->size());
+ typename alloc_t::group_throw_prob_adjustor adjust(m_p_c->size());
try
{
m_native_c.clear();
break;
case 1:
- p_c = new Cntnr(m_p_c->get_hash_fn(),
- m_p_c->get_eq_fn());
+ p_c = new Cntnr(m_p_c->get_hash_fn(), m_p_c->get_eq_fn());
m_native_c.clear();
break;
case 2:
- p_c = new Cntnr(m_p_c->get_hash_fn(),
- m_p_c->get_eq_fn(),
+ p_c = new Cntnr(m_p_c->get_hash_fn(), m_p_c->get_eq_fn(),
m_p_c->get_comb_hash_fn());
m_native_c.clear();
break;
case 3:
- p_c = new Cntnr(m_p_c->get_hash_fn(),
- m_p_c->get_eq_fn(),
+ p_c = new Cntnr(m_p_c->get_hash_fn(), m_p_c->get_eq_fn(),
m_p_c->get_comb_hash_fn(),
m_p_c->get_resize_policy());
m_native_c.clear();
break;
case 4:
- p_c = new Cntnr(m_p_c->begin(),
- m_p_c->end());
+ p_c = new Cntnr(m_p_c->begin(), m_p_c->end());
break;
case 5:
- p_c = new Cntnr(m_p_c->begin(),
- m_p_c->end(),
- m_p_c->get_hash_fn());
+ p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn());
break;
case 6:
- p_c = new Cntnr(m_p_c->begin(),
- m_p_c->end(),
- m_p_c->get_hash_fn(),
+ p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn(),
m_p_c->get_eq_fn());
break;
case 7:
- p_c = new Cntnr(m_p_c->begin(),
- m_p_c->end(),
- m_p_c->get_hash_fn(),
- m_p_c->get_eq_fn(),
- m_p_c->get_comb_hash_fn());
+ p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn(),
+ m_p_c->get_eq_fn(), m_p_c->get_comb_hash_fn());
break;
case 8:
- p_c = new Cntnr(m_p_c->begin(),
- m_p_c->end(),
- m_p_c->get_hash_fn(),
- m_p_c->get_eq_fn(),
- m_p_c->get_comb_hash_fn(),
+ p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn(),
+ m_p_c->get_eq_fn(), m_p_c->get_comb_hash_fn(),
m_p_c->get_resize_policy());
break;
default:
- PB_DS_THROW_IF_FAILED( false, "", m_p_c, & m_native_c);
+ PB_DS_THROW_IF_FAILED(false, "", m_p_c, & m_native_c);
};
-
std::swap(p_c, m_p_c);
}
- catch(__gnu_cxx::forced_exception_error& )
+ catch (__gnu_cxx::forced_exception_error&)
{
done = false;
}
delete p_c;
-
PB_DS_COND_COMPARE(*m_p_c, m_native_c);
-
- return (done);
+ return done;
}
PB_DS_CLASS_T_DEC
it_constructor_imp(pb_ds::gp_hash_tag)
{
bool done = true;
-
Cntnr* p_c = NULL;
-
m_alloc.set_throw_prob(m_tp);
-
- typename alloc_t::group_throw_prob_adjustor
- adjust(m_p_c->size());
+ typename alloc_t::group_throw_prob_adjustor adjust(m_p_c->size());
try
{
m_native_c.clear();
break;
case 1:
- p_c = new Cntnr(m_p_c->get_hash_fn(),
- m_p_c->get_eq_fn());
+ p_c = new Cntnr(m_p_c->get_hash_fn(), m_p_c->get_eq_fn());
m_native_c.clear();
break;
case 2:
- p_c = new Cntnr(m_p_c->get_hash_fn(),
- m_p_c->get_eq_fn(),
+ p_c = new Cntnr(m_p_c->get_hash_fn(), m_p_c->get_eq_fn(),
m_p_c->get_comb_probe_fn());
m_native_c.clear();
break;
case 3:
- p_c = new Cntnr(m_p_c->get_hash_fn(),
- m_p_c->get_eq_fn(),
+ p_c = new Cntnr(m_p_c->get_hash_fn(), m_p_c->get_eq_fn(),
m_p_c->get_comb_probe_fn());
m_native_c.clear();
break;
case 4:
- p_c = new Cntnr(m_p_c->get_hash_fn(),
- m_p_c->get_eq_fn(),
- m_p_c->get_comb_probe_fn(),
- m_p_c->get_probe_fn());
+ p_c = new Cntnr(m_p_c->get_hash_fn(), m_p_c->get_eq_fn(),
+ m_p_c->get_comb_probe_fn(), m_p_c->get_probe_fn());
m_native_c.clear();
break;
case 5:
- p_c = new Cntnr(m_p_c->get_hash_fn(),
- m_p_c->get_eq_fn(),
- m_p_c->get_comb_probe_fn(),
- m_p_c->get_probe_fn(),
+ p_c = new Cntnr(m_p_c->get_hash_fn(), m_p_c->get_eq_fn(),
+ m_p_c->get_comb_probe_fn(), m_p_c->get_probe_fn(),
m_p_c->get_resize_policy());
m_native_c.clear();
break;
case 6:
- p_c = new Cntnr(m_p_c->begin(),
- m_p_c->end(),
- m_p_c->get_hash_fn());
+ p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn());
break;
case 7:
- p_c = new Cntnr(m_p_c->begin(),
- m_p_c->end(),
- m_p_c->get_hash_fn(),
+ p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn(),
m_p_c->get_eq_fn());
break;
case 8:
- p_c = new Cntnr(m_p_c->begin(),
- m_p_c->end(),
- m_p_c->get_hash_fn(),
- m_p_c->get_eq_fn(),
- m_p_c->get_comb_probe_fn());
+ p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn(),
+ m_p_c->get_eq_fn(), m_p_c->get_comb_probe_fn());
break;
case 9:
- p_c = new Cntnr(m_p_c->begin(),
- m_p_c->end(),
- m_p_c->get_hash_fn(),
- m_p_c->get_eq_fn(),
- m_p_c->get_comb_probe_fn());
+ p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn(),
+ m_p_c->get_eq_fn(), m_p_c->get_comb_probe_fn());
break;
case 10:
- p_c = new Cntnr(m_p_c->begin(),
- m_p_c->end(),
- m_p_c->get_hash_fn(),
- m_p_c->get_eq_fn(),
- m_p_c->get_comb_probe_fn(),
+ p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn(),
+ m_p_c->get_eq_fn(), m_p_c->get_comb_probe_fn(),
m_p_c->get_probe_fn());
break;
case 11:
- p_c = new Cntnr(m_p_c->begin(),
- m_p_c->end(),
- m_p_c->get_hash_fn(),
- m_p_c->get_eq_fn(),
- m_p_c->get_comb_probe_fn(),
- m_p_c->get_probe_fn(),
- m_p_c->get_resize_policy());
+ p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_hash_fn(),
+ m_p_c->get_eq_fn(), m_p_c->get_comb_probe_fn(),
+ m_p_c->get_probe_fn(), m_p_c->get_resize_policy());
break;
default:
- PB_DS_THROW_IF_FAILED( false, "", m_p_c, & m_native_c);
+ PB_DS_THROW_IF_FAILED(false, "", m_p_c, & m_native_c);
};
-
std::swap(p_c, m_p_c);
}
- catch(__gnu_cxx::forced_exception_error& )
+ catch (__gnu_cxx::forced_exception_error&)
{
done = false;
}
delete p_c;
-
PB_DS_COND_COMPARE(*m_p_c, m_native_c);
-
- return (done);
+ return done;
}
PB_DS_CLASS_T_DEC
it_constructor_imp(pb_ds::tree_tag)
{
bool done = true;
-
Cntnr* p_c = NULL;
-
m_alloc.set_throw_prob(m_tp);
-
- typename alloc_t::group_throw_prob_adjustor
- adjust(m_p_c->size());
+ typename alloc_t::group_throw_prob_adjustor adjust(m_p_c->size());
try
{
m_native_c.clear();
break;
case 1:
- p_c = new Cntnr(m_p_c->begin(),
- m_p_c->end(),
- m_p_c->get_cmp_fn());
+ p_c = new Cntnr(m_p_c->begin(), m_p_c->end(), m_p_c->get_cmp_fn());
break;
default:
- PB_DS_THROW_IF_FAILED( false, "", m_p_c, & m_native_c);
+ PB_DS_THROW_IF_FAILED(false, "", m_p_c, &m_native_c);
};
-
std::swap(p_c, m_p_c);
}
- catch(__gnu_cxx::forced_exception_error& )
+ catch (__gnu_cxx::forced_exception_error&)
{
done = false;
}
delete p_c;
-
PB_DS_COND_COMPARE(*m_p_c, m_native_c);
-
- return (done);
+ return done;
}
PB_DS_CLASS_T_DEC
it_constructor_imp(pb_ds::list_update_tag)
{
bool done = true;
-
Cntnr* p_c = NULL;
-
m_alloc.set_throw_prob(m_tp);
-
- typename alloc_t::group_throw_prob_adjustor
- adjust(m_p_c->size());
+ typename alloc_t::group_throw_prob_adjustor adjust(m_p_c->size());
try
{
- p_c = new Cntnr(m_p_c->begin(),
- m_p_c->end());
-
+ p_c = new Cntnr(m_p_c->begin(), m_p_c->end());
std::swap(p_c, m_p_c);
}
- catch(__gnu_cxx::forced_exception_error& )
+ catch (__gnu_cxx::forced_exception_error&)
{
done = false;
}
delete p_c;
-
PB_DS_COND_COMPARE(*m_p_c, m_native_c);
-
- return (done);
+ return done;
}
PB_DS_CLASS_T_DEC
it_constructor_imp(pb_ds::pat_trie_tag)
{
bool done = true;
-
Cntnr* p_c = NULL;
-
m_alloc.set_throw_prob(m_tp);
-
- typename alloc_t::group_throw_prob_adjustor
- adjust(m_p_c->size());
+ typename alloc_t::group_throw_prob_adjustor adjust(m_p_c->size());
try
{
m_native_c.clear();
break;
case 1:
- p_c = new Cntnr(m_p_c->begin(),
- m_p_c->end(),
+ p_c = new Cntnr(m_p_c->begin(), m_p_c->end(),
m_p_c->get_e_access_traits());
break;
default:
- PB_DS_THROW_IF_FAILED( false, "", m_p_c, & m_native_c);
+ PB_DS_THROW_IF_FAILED(false, "", m_p_c, & m_native_c);
};
std::swap(p_c, m_p_c);
}
- catch(__gnu_cxx::forced_exception_error& )
+ catch (__gnu_cxx::forced_exception_error&)
{
done = false;
}
delete p_c;
-
PB_DS_COND_COMPARE(*m_p_c, m_native_c);
-
- return (done);
+ return done;
}
if (ins_ret.second)
{
- PB_DS_THROW_IF_FAILED(!existed, "", m_p_c, & m_native_c);
+ PB_DS_THROW_IF_FAILED(!existed, "", m_p_c, &m_native_c);
}
else
{
- PB_DS_THROW_IF_FAILED(existed, "", m_p_c, & m_native_c);
- PB_DS_THROW_IF_FAILED(found_it == ins_ret.first, "", m_p_c, & m_native_c);
+ PB_DS_THROW_IF_FAILED(existed, "", m_p_c, &m_native_c);
+ PB_DS_THROW_IF_FAILED(found_it == ins_ret.first, "", m_p_c, &m_native_c);
}
m_native_c.insert(test_traits::native_value(v));
}
- catch(__gnu_cxx::forced_exception_error& )
+ catch(__gnu_cxx::forced_exception_error&)
{
done = false;
}
- catch(pb_ds::insert_error& )
+ catch(pb_ds::insert_error&)
{
- PB_DS_THROW_IF_FAILED(false, "", m_p_c, & m_native_c);
+ PB_DS_THROW_IF_FAILED(false, "", m_p_c, &m_native_c);
}
PB_DS_COND_COMPARE(*m_p_c, m_native_c);
/**
* @file operator_fn_imps.hpp
- * Containsert a random regression test for a specific container type.
+ * Contains a random regression test for a specific container type.
*/
PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
operator()()
{
- xml_result_set_regression_formatter* p_fmt = NULL;
+ typedef xml_result_set_regression_formatter formatter_type;
+ formatter_type* p_fmt = NULL;
if (m_disp)
- p_fmt = new xml_result_set_regression_formatter(string_form<Cntnr>::name(),
- string_form<Cntnr>::desc());
+ p_fmt = new formatter_type(string_form<Cntnr>::name(),
+ string_form<Cntnr>::desc());
m_g.init(m_seed);
+
+ // Track allocation from this point only.
+ const size_t memory_label = 775;
m_alloc.init(m_seed);
+ m_alloc.set_label(memory_label);
+
prog_bar pb(m_n, std::cout, m_disp);
m_i = 0;
for (m_i = 0; m_i < m_n; ++m_i)
{
PB_DS_TRACE("Op #" << static_cast<unsigned long>(m_i));
-
allocator::set_label(m_i);
-
- switch(m_i)
+ switch (m_i)
{
case 0:
PB_DS_RUN_MTHD(default_constructor);
get_set_loads();
break;
default:
- PB_DS_THROW_IF_FAILED(false, "", m_p_c, & m_native_c);
+ PB_DS_THROW_IF_FAILED(false, "", m_p_c, &m_native_c);
}
break;
default:
- PB_DS_THROW_IF_FAILED(false, "", m_p_c, & m_native_c);
+ PB_DS_THROW_IF_FAILED(false, "", m_p_c, &m_native_c);
};
}
pb.inc();
}
}
- catch(...)
+ catch (...)
{
std::cerr << "Failed at index " << static_cast<unsigned long>(m_i)
<< std::endl;
throw;
}
+ // Clean up, then check for allocation by special label, set above.
delete m_p_c;
- if (!m_alloc.throw_allocator<char>::empty())
+ try
+ { m_alloc.check_allocated(memory_label); }
+ catch (...)
{
std::cerr << "detected leaks!" << std::endl;
std::cerr << m_alloc << std::endl;
PB_DS_THROW_IF_FAILED(false, "", m_p_c, &m_native_c);
}
+ // Reset throw probability.
+ m_alloc.set_throw_prob(0);
+
if (m_disp)
{
std::cout << std::endl;
const double prob = m_g.get_prob();
if (prob < m_ip)
- return (insert_op);
+ return insert_op;
if (prob < m_ip + m_ep)
- return (erase_op);
+ return erase_op;
if (prob < m_ip + m_ep + m_cp)
- return (clear_op);
+ return clear_op;
PB_DS_THROW_IF_FAILED(prob <= 1, prob, m_p_c, &m_native_c);
- return (other_op);
+ return other_op;
}
PB_DS_CLASS_T_DEC
const double delta = 1 / static_cast<double>(max);
size_t i = 0;
while (true)
- if (p <= (i + 1)* delta)
+ if (p <= (i + 1) * delta)
{
PB_DS_THROW_IF_FAILED(i < max,
static_cast<unsigned long>(i) << " " <<
static_cast<unsigned long>(max),
- m_p_c,
- & m_native_c);
+ m_p_c, &m_native_c);
- return (i);
+ return i;
}
else
++i;
template<typename Cntnr>
void
- operator()(__gnu_cxx::typelist::detail::type_to_type<Cntnr>)
+ operator()(Cntnr)
{
unsigned long ul = static_cast<unsigned long>(m_sd);
container_rand_regression_test<Cntnr> t(ul, m_n, m_n, m_tp, m_ip,
detail::rand_reg_test tst(sd, n, m, tp, ip, ep, cp, mp, disp);
__gnu_cxx::typelist::apply(tst, tl);
}
- catch(...)
+ catch (...)
{
std::cerr << "Test failed with seed " << sd << std::endl;
if (disp)
delete p_fmt;
- return -1;
+ throw;
}
if (disp)
PB_DS_CLASS_C_DEC::
operator()()
{
- xml_result_set_regression_formatter* p_fmt = NULL;
+ typedef xml_result_set_regression_formatter formatter_type;
+ formatter_type* p_fmt = NULL;
if (m_disp)
- p_fmt = new xml_result_set_regression_formatter(string_form<Cntnr>::name(),
- string_form<Cntnr>::desc());
+ p_fmt = new formatter_type(string_form<Cntnr>::name(),
+ string_form<Cntnr>::desc());
m_g.init(m_seed);
+
+ // Track allocation from this point only.
+ const size_t memory_label = 775;
m_alloc.init(m_seed);
+ m_alloc.set_label(memory_label);
+
prog_bar pb(m_n, std::cout, m_disp);
m_i = 0;
pb.inc();
}
}
- catch(...)
+ catch (...)
{
std::cerr << "Failed at index " << static_cast<unsigned long>(m_i)
<< std::endl;
delete m_p_c;
throw;
}
+
+ // Clean up, then check for allocation by special label, set above.
delete m_p_c;
- if (!m_alloc.throw_allocator<char>::empty())
+ try
+ { m_alloc.check_allocated(memory_label); }
+ catch (...)
{
std::cerr << "detected leaks!" << std::endl;
std::cerr << m_alloc << std::endl;
PB_DS_THROW_IF_FAILED(false, "", m_p_c, &m_native_c);
}
+ // Reset throw probability.
+ m_alloc.set_throw_prob(0);
+
if (m_disp)
{
std::cout << std::endl;
template<typename Cntnr>
void
- operator()(__gnu_cxx::typelist::detail::type_to_type<Cntnr>)
+ operator()(Cntnr)
{
unsigned long ul = static_cast<unsigned long>(m_sd);
container_rand_regression_test<Cntnr> t(ul, m_n, m_n, m_tp, m_ip, m_dp,
namespace pb_ds
{
-
namespace test
{
-
namespace detail
{
-
template<typename Cntnr>
struct regression_test_type_traits
{
-
- public:
-
typedef Cntnr cntnr;
-
typedef typename cntnr::key_type key_type;
-
typedef typename cntnr::const_key_reference const_key_reference;
-
typedef typename cntnr::value_type value_type;
-
typedef typename cntnr::const_reference const_reference;
-
typedef typename cntnr::mapped_type mapped_type;
-
typedef typename cntnr::const_mapped_reference const_mapped_reference;
- public:
-
template<typename Gen>
static key_type
generate_key(Gen& r_gen, size_t max)
- {
- return (basic_type(r_gen, max));
- }
+ { return basic_type(r_gen, max); }
template<typename Gen>
static value_type
generate_value(Gen& r_gen, size_t max)
- {
- return (generate_value(r_gen, max,
- __gnu_cxx::typelist::detail::type_to_type<value_type>()));
- }
+ { return generate_value(r_gen, max, value_type()); }
static const_key_reference
extract_key(const_reference r_val)
- {
- return extract_key_imp(r_val);
- }
+ { return extract_key_imp(r_val); }
private:
- typedef
- typename Cntnr::allocator::template rebind<
- basic_type>::other::const_reference
- basic_type_const_reference;
-
- typedef
- typename Cntnr::allocator::template rebind<
- std::pair<
- basic_type,
- basic_type> >::other::const_reference
- basic_type_pair_const_reference;
+ typedef typename cntnr::allocator::template rebind<basic_type>::other
+ basic_type_rebind;
+
+ typedef typename basic_type_rebind::const_reference basic_type_const_reference;
+
+ typedef typename cntnr::allocator::template rebind<std::pair<basic_type, basic_type> >::other pair_type_rebind;
+ typedef typename pair_type_rebind::const_reference pair_type_const_reference;
- private:
template<typename Gen>
static value_type
- generate_value(Gen& r_gen, size_t max, __gnu_cxx::typelist::detail::type_to_type<pb_ds::null_mapped_type>)
- {
- return (basic_type(r_gen, max));
- }
+ generate_value(Gen& r_gen, size_t max, pb_ds::null_mapped_type)
+ { return basic_type(r_gen, max); }
template<typename Gen>
static value_type
- generate_value(Gen& r_gen, size_t max, __gnu_cxx::typelist::detail::type_to_type<basic_type>)
- {
- return (basic_type(r_gen, max));
- }
+ generate_value(Gen& r_gen, size_t max, basic_type)
+ { return basic_type(r_gen, max); }
template<typename Gen>
static value_type
- generate_value(Gen& r_gen, size_t max, __gnu_cxx::typelist::detail::type_to_type<std::pair<const basic_type, basic_type> >)
- {
- return (std::make_pair(basic_type(r_gen, max), basic_type(r_gen, max)));
- }
+ generate_value(Gen& gen, size_t max,
+ std::pair<const basic_type, basic_type>)
+ { return std::make_pair(basic_type(gen, max), basic_type(gen, max)); }
static const_key_reference
extract_key_imp(basic_type_const_reference r_val)
- {
- return r_val;
- }
+ { return r_val; }
static const_key_reference
- extract_key_imp(basic_type_pair_const_reference r_val)
- {
- return r_val.first;
- }
+ extract_key_imp(pair_type_const_reference r_val)
+ { return r_val.first; }
};
-
-#undef PB_DS_BASE_C_DEC
-
} // namespace detail
-
} // namespace test
-
} // namespace pb_ds
-#endif // #ifndef PB_DS_REGRESSION_TEST_TYPE_TRAIT_HPP
+#endif
template<class Container>
void
- operator()(__gnu_cxx::typelist::detail::type_to_type<Container>)
+ operator()(Container)
{
const int i = 20000;
test_container<Container, i, Thread>(_M_filename);
OSDN Git Service
