This is an automated email from the ASF dual-hosted git repository. wlauer pushed a commit to branch inplace in repository https://gitbox.apache.org/repos/asf/datasketches-cpp.git
commit 5d918d059d97ce07048303975f1db5ea7b32e318 Author: Will Lauer <[email protected]> AuthorDate: Fri Jun 2 12:40:39 2023 -0500 Parameterizing underlying hash table in tuple and theta sketches --- theta/include/theta_sketch.hpp | 14 +-- theta/include/theta_sketch_impl.hpp | 129 +++++++++++++------------- theta/include/theta_union.hpp | 17 ++-- theta/include/theta_union_base.hpp | 7 +- theta/include/theta_union_base_impl.hpp | 23 +++-- theta/include/theta_union_impl.hpp | 30 +++--- tuple/include/array_of_doubles_union_impl.hpp | 2 +- tuple/include/tuple_sketch.hpp | 18 ++-- tuple/include/tuple_sketch_impl.hpp | 124 ++++++++++++------------- tuple/include/tuple_union.hpp | 14 ++- tuple/include/tuple_union_impl.hpp | 28 +++--- 11 files changed, 211 insertions(+), 195 deletions(-) diff --git a/theta/include/theta_sketch.hpp b/theta/include/theta_sketch.hpp index 4bc1c2e..36e8721 100644 --- a/theta/include/theta_sketch.hpp +++ b/theta/include/theta_sketch.hpp @@ -149,7 +149,8 @@ protected: // forward declaration template<typename A> class compact_theta_sketch_alloc; -template<typename Allocator = std::allocator<uint64_t>> +template<typename Allocator = std::allocator<uint64_t>, + template<typename, typename, typename> class Table = theta_update_sketch_base> class update_theta_sketch_alloc: public theta_sketch_alloc<Allocator> { public: using Base = theta_sketch_alloc<Allocator>; @@ -157,7 +158,7 @@ public: using ExtractKey = typename Base::ExtractKey; using iterator = typename Base::iterator; using const_iterator = typename Base::const_iterator; - using theta_table = theta_update_sketch_base<Entry, ExtractKey, Allocator>; + using theta_table = Table<Entry, ExtractKey, Allocator>; using resize_factor = typename theta_table::resize_factor; // No constructor here. Use builder instead. @@ -301,8 +302,7 @@ private: theta_table table_; // for builder - update_theta_sketch_alloc(uint8_t lg_cur_size, uint8_t lg_nom_size, resize_factor rf, float p, - uint64_t theta, uint64_t seed, const Allocator& allocator); + update_theta_sketch_alloc(theta_table&& table); virtual void print_specifics(std::ostringstream& os) const; }; @@ -425,9 +425,11 @@ private: virtual void print_specifics(std::ostringstream& os) const; }; -template<typename Allocator> -class update_theta_sketch_alloc<Allocator>::builder: public theta_base_builder<builder, Allocator> { +template<typename Allocator,template<typename, typename, typename> class Table> +class update_theta_sketch_alloc<Allocator, Table>::builder: public theta_base_builder<builder, Allocator> { public: + using ThetaTable = update_theta_sketch_alloc::theta_table; + builder(const Allocator& allocator = Allocator()); update_theta_sketch_alloc build() const; }; diff --git a/theta/include/theta_sketch_impl.hpp b/theta/include/theta_sketch_impl.hpp index e5e5050..175b788 100644 --- a/theta/include/theta_sketch_impl.hpp +++ b/theta/include/theta_sketch_impl.hpp @@ -96,110 +96,109 @@ void theta_sketch_alloc<A>::print_items(std::ostringstream& os) const { // update sketch -template<typename A> -update_theta_sketch_alloc<A>::update_theta_sketch_alloc(uint8_t lg_cur_size, uint8_t lg_nom_size, resize_factor rf, - float p, uint64_t theta, uint64_t seed, const A& allocator): -table_(lg_cur_size, lg_nom_size, rf, p, theta, seed, allocator) +template<typename A, template<typename, typename, typename> class T> +update_theta_sketch_alloc<A,T>::update_theta_sketch_alloc(theta_table&& table): +table_{table} {} -template<typename A> -A update_theta_sketch_alloc<A>::get_allocator() const { +template<typename A, template<typename, typename, typename> class T> +A update_theta_sketch_alloc<A,T>::get_allocator() const { return table_.allocator_; } -template<typename A> -bool update_theta_sketch_alloc<A>::is_empty() const { +template<typename A, template<typename, typename, typename> class T> +bool update_theta_sketch_alloc<A,T>::is_empty() const { return table_.is_empty_; } -template<typename A> -bool update_theta_sketch_alloc<A>::is_ordered() const { +template<typename A, template<typename, typename, typename> class T> +bool update_theta_sketch_alloc<A,T>::is_ordered() const { return table_.num_entries_ > 1 ? false : true; } -template<typename A> -uint64_t update_theta_sketch_alloc<A>::get_theta64() const { +template<typename A, template<typename, typename, typename> class T> +uint64_t update_theta_sketch_alloc<A,T>::get_theta64() const { return is_empty() ? theta_constants::MAX_THETA : table_.theta_; } -template<typename A> -uint32_t update_theta_sketch_alloc<A>::get_num_retained() const { +template<typename A, template<typename, typename, typename> class T> +uint32_t update_theta_sketch_alloc<A,T>::get_num_retained() const { return table_.num_entries_; } -template<typename A> -uint16_t update_theta_sketch_alloc<A>::get_seed_hash() const { +template<typename A, template<typename, typename, typename> class T> +uint16_t update_theta_sketch_alloc<A,T>::get_seed_hash() const { return compute_seed_hash(table_.seed_); } -template<typename A> -uint8_t update_theta_sketch_alloc<A>::get_lg_k() const { +template<typename A, template<typename, typename, typename> class T> +uint8_t update_theta_sketch_alloc<A,T>::get_lg_k() const { return table_.lg_nom_size_; } -template<typename A> -auto update_theta_sketch_alloc<A>::get_rf() const -> resize_factor { +template<typename A, template<typename, typename, typename> class T> +auto update_theta_sketch_alloc<A,T>::get_rf() const -> resize_factor { return table_.rf_; } -template<typename A> -void update_theta_sketch_alloc<A>::update(uint64_t value) { +template<typename A, template<typename, typename, typename> class T> +void update_theta_sketch_alloc<A,T>::update(uint64_t value) { update(&value, sizeof(value)); } -template<typename A> -void update_theta_sketch_alloc<A>::update(int64_t value) { +template<typename A, template<typename, typename, typename> class T> +void update_theta_sketch_alloc<A,T>::update(int64_t value) { update(&value, sizeof(value)); } -template<typename A> -void update_theta_sketch_alloc<A>::update(uint32_t value) { +template<typename A, template<typename, typename, typename> class T> +void update_theta_sketch_alloc<A,T>::update(uint32_t value) { update(static_cast<int32_t>(value)); } -template<typename A> -void update_theta_sketch_alloc<A>::update(int32_t value) { +template<typename A, template<typename, typename, typename> class T> +void update_theta_sketch_alloc<A,T>::update(int32_t value) { update(static_cast<int64_t>(value)); } -template<typename A> -void update_theta_sketch_alloc<A>::update(uint16_t value) { +template<typename A, template<typename, typename, typename> class T> +void update_theta_sketch_alloc<A,T>::update(uint16_t value) { update(static_cast<int16_t>(value)); } -template<typename A> -void update_theta_sketch_alloc<A>::update(int16_t value) { +template<typename A, template<typename, typename, typename> class T> +void update_theta_sketch_alloc<A,T>::update(int16_t value) { update(static_cast<int64_t>(value)); } -template<typename A> -void update_theta_sketch_alloc<A>::update(uint8_t value) { +template<typename A, template<typename, typename, typename> class T> +void update_theta_sketch_alloc<A,T>::update(uint8_t value) { update(static_cast<int8_t>(value)); } -template<typename A> -void update_theta_sketch_alloc<A>::update(int8_t value) { +template<typename A, template<typename, typename, typename> class T> +void update_theta_sketch_alloc<A,T>::update(int8_t value) { update(static_cast<int64_t>(value)); } -template<typename A> -void update_theta_sketch_alloc<A>::update(double value) { +template<typename A, template<typename, typename, typename> class T> +void update_theta_sketch_alloc<A,T>::update(double value) { update(canonical_double(value)); } -template<typename A> -void update_theta_sketch_alloc<A>::update(float value) { +template<typename A, template<typename, typename, typename> class T> +void update_theta_sketch_alloc<A,T>::update(float value) { update(static_cast<double>(value)); } -template<typename A> -void update_theta_sketch_alloc<A>::update(const std::string& value) { +template<typename A, template<typename, typename, typename> class T> +void update_theta_sketch_alloc<A,T>::update(const std::string& value) { if (value.empty()) return; update(value.c_str(), value.length()); } -template<typename A> -void update_theta_sketch_alloc<A>::update(const void* data, size_t length) { +template<typename A, template<typename, typename, typename> class T> +void update_theta_sketch_alloc<A,T>::update(const void* data, size_t length) { const uint64_t hash = table_.hash_and_screen(data, length); if (hash == 0) return; auto result = table_.find(hash); @@ -208,43 +207,43 @@ void update_theta_sketch_alloc<A>::update(const void* data, size_t length) { } } -template<typename A> -void update_theta_sketch_alloc<A>::trim() { +template<typename A, template<typename, typename, typename> class T> +void update_theta_sketch_alloc<A,T>::trim() { table_.trim(); } -template<typename A> -void update_theta_sketch_alloc<A>::reset() { +template<typename A, template<typename, typename, typename> class T> +void update_theta_sketch_alloc<A,T>::reset() { table_.reset(); } -template<typename A> -auto update_theta_sketch_alloc<A>::begin() -> iterator { +template<typename A, template<typename, typename, typename> class T> +auto update_theta_sketch_alloc<A,T>::begin() -> iterator { return iterator(table_.entries_, 1 << table_.lg_cur_size_, 0); } -template<typename A> -auto update_theta_sketch_alloc<A>::end() -> iterator { +template<typename A, template<typename, typename, typename> class T> +auto update_theta_sketch_alloc<A,T>::end() -> iterator { return iterator(nullptr, 0, 1 << table_.lg_cur_size_); } -template<typename A> -auto update_theta_sketch_alloc<A>::begin() const -> const_iterator { +template<typename A, template<typename, typename, typename> class T> +auto update_theta_sketch_alloc<A,T>::begin() const -> const_iterator { return const_iterator(table_.entries_, 1 << table_.lg_cur_size_, 0); } -template<typename A> -auto update_theta_sketch_alloc<A>::end() const -> const_iterator { +template<typename A, template<typename, typename, typename> class T> +auto update_theta_sketch_alloc<A,T>::end() const -> const_iterator { return const_iterator(nullptr, 0, 1 << table_.lg_cur_size_); } -template<typename A> -compact_theta_sketch_alloc<A> update_theta_sketch_alloc<A>::compact(bool ordered) const { +template<typename A, template<typename, typename, typename> class T> +compact_theta_sketch_alloc<A> update_theta_sketch_alloc<A,T>::compact(bool ordered) const { return compact_theta_sketch_alloc<A>(*this, ordered); } -template<typename A> -void update_theta_sketch_alloc<A>::print_specifics(std::ostringstream& os) const { +template<typename A, template<typename, typename, typename> class T> +void update_theta_sketch_alloc<A,T>::print_specifics(std::ostringstream& os) const { os << " lg nominal size : " << static_cast<int>(table_.lg_nom_size_) << std::endl; os << " lg current size : " << static_cast<int>(table_.lg_cur_size_) << std::endl; os << " resize factor : " << (1 << table_.rf_) << std::endl; @@ -252,12 +251,12 @@ void update_theta_sketch_alloc<A>::print_specifics(std::ostringstream& os) const // builder -template<typename A> -update_theta_sketch_alloc<A>::builder::builder(const A& allocator): theta_base_builder<builder, A>(allocator) {} +template<typename A, template<typename, typename, typename> class T> +update_theta_sketch_alloc<A,T>::builder::builder(const A& allocator): theta_base_builder<builder, A>(allocator) {} -template<typename A> -update_theta_sketch_alloc<A> update_theta_sketch_alloc<A>::builder::build() const { - return update_theta_sketch_alloc(this->starting_lg_size(), this->lg_k_, this->rf_, this->p_, this->starting_theta(), this->seed_, this->allocator_); +template<typename A, template<typename, typename, typename> class T> +update_theta_sketch_alloc<A,T> update_theta_sketch_alloc<A,T>::builder::build() const { + return update_theta_sketch_alloc(ThetaTable(this->starting_lg_size(), this->lg_k_, this->rf_, this->p_, this->starting_theta(), this->seed_, this->allocator_)); } // compact sketch diff --git a/theta/include/theta_union.hpp b/theta/include/theta_union.hpp index d90c53a..4c7019f 100644 --- a/theta/include/theta_union.hpp +++ b/theta/include/theta_union.hpp @@ -26,7 +26,8 @@ namespace datasketches { -template<typename Allocator = std::allocator<uint64_t>> +template<typename Allocator = std::allocator<uint64_t>, + template<typename, typename, typename> class Table = theta_update_sketch_base> class theta_union_alloc { public: using Entry = uint64_t; @@ -34,6 +35,8 @@ public: using Sketch = theta_sketch_alloc<Allocator>; using CompactSketch = compact_theta_sketch_alloc<Allocator>; using resize_factor = theta_constants::resize_factor; + using theta_table = Table<Entry, ExtractKey, Allocator>; + struct nop_policy { void operator()(uint64_t internal_entry, uint64_t incoming_entry) const { @@ -41,7 +44,7 @@ public: unused(incoming_entry); } }; - using State = theta_union_base<Entry, ExtractKey, nop_policy, Sketch, CompactSketch, Allocator>; + using State = theta_union_base<Entry, ExtractKey, nop_policy, Sketch, CompactSketch, Allocator, Table>; // No constructor here. Use builder instead. class builder; @@ -69,19 +72,21 @@ private: State state_; // for builder - theta_union_alloc(uint8_t lg_cur_size, uint8_t lg_nom_size, resize_factor rf, float p, uint64_t theta, uint64_t seed, const Allocator& allocator); + theta_union_alloc(theta_table&& table); }; -template<typename A> -class theta_union_alloc<A>::builder: public theta_base_builder<builder, A> { +template<typename A, template<typename, typename, typename> class T> +class theta_union_alloc<A, T>::builder: public theta_base_builder<builder, A> { public: + using Table = theta_union_alloc::theta_table; + builder(const A& allocator = A()); /** * This is to create an instance of the union with predefined parameters. * @return an instance of the union */ - theta_union_alloc<A> build() const; + theta_union_alloc<A, T> build() const; }; // alias with default allocator for convenience diff --git a/theta/include/theta_union_base.hpp b/theta/include/theta_union_base.hpp index 6da10b2..1a2d47b 100644 --- a/theta/include/theta_union_base.hpp +++ b/theta/include/theta_union_base.hpp @@ -30,15 +30,16 @@ template< typename Policy, typename Sketch, typename CompactSketch, - typename Allocator + typename Allocator, + template<typename, typename, typename> class Table = theta_update_sketch_base > class theta_union_base { public: - using hash_table = theta_update_sketch_base<Entry, ExtractKey, Allocator>; + using hash_table = Table<Entry, ExtractKey, Allocator>; using resize_factor = typename hash_table::resize_factor; using comparator = compare_by_key<ExtractKey>; - theta_union_base(uint8_t lg_cur_size, uint8_t lg_nom_size, resize_factor rf, float p, uint64_t theta, uint64_t seed, const Policy& policy, const Allocator& allocator); + theta_union_base(const Policy& policy, hash_table&& table); template<typename FwdSketch> void update(FwdSketch&& sketch); diff --git a/theta/include/theta_union_base_impl.hpp b/theta/include/theta_union_base_impl.hpp index 99a5bbf..c56a9a3 100644 --- a/theta/include/theta_union_base_impl.hpp +++ b/theta/include/theta_union_base_impl.hpp @@ -27,17 +27,16 @@ namespace datasketches { -template<typename EN, typename EK, typename P, typename S, typename CS, typename A> -theta_union_base<EN, EK, P, S, CS, A>::theta_union_base(uint8_t lg_cur_size, uint8_t lg_nom_size, resize_factor rf, - float p, uint64_t theta, uint64_t seed, const P& policy, const A& allocator): +template<typename EN, typename EK, typename P, typename S, typename CS, typename A, template<typename, typename, typename> class T> +theta_union_base<EN, EK, P, S, CS, A, T>::theta_union_base(const P& policy, hash_table&& table): policy_(policy), -table_(lg_cur_size, lg_nom_size, rf, p, theta, seed, allocator), +table_(table), union_theta_(table_.theta_) {} -template<typename EN, typename EK, typename P, typename S, typename CS, typename A> +template<typename EN, typename EK, typename P, typename S, typename CS, typename A, template<typename, typename, typename> class T> template<typename SS> -void theta_union_base<EN, EK, P, S, CS, A>::update(SS&& sketch) { +void theta_union_base<EN, EK, P, S, CS, A, T>::update(SS&& sketch) { if (sketch.is_empty()) return; if (sketch.get_seed_hash() != compute_seed_hash(table_.seed_)) throw std::invalid_argument("seed hash mismatch"); table_.is_empty_ = false; @@ -58,8 +57,8 @@ void theta_union_base<EN, EK, P, S, CS, A>::update(SS&& sketch) { union_theta_ = std::min(union_theta_, table_.theta_); } -template<typename EN, typename EK, typename P, typename S, typename CS, typename A> -CS theta_union_base<EN, EK, P, S, CS, A>::get_result(bool ordered) const { +template<typename EN, typename EK, typename P, typename S, typename CS, typename A, template<typename, typename, typename> class T> +CS theta_union_base<EN, EK, P, S, CS, A, T>::get_result(bool ordered) const { std::vector<EN, A> entries(table_.allocator_); if (table_.is_empty_) return CS(true, true, compute_seed_hash(table_.seed_), union_theta_, std::move(entries)); entries.reserve(table_.num_entries_); @@ -80,13 +79,13 @@ CS theta_union_base<EN, EK, P, S, CS, A>::get_result(bool ordered) const { return CS(table_.is_empty_, ordered, compute_seed_hash(table_.seed_), theta, std::move(entries)); } -template<typename EN, typename EK, typename P, typename S, typename CS, typename A> -const P& theta_union_base<EN, EK, P, S, CS, A>::get_policy() const { +template<typename EN, typename EK, typename P, typename S, typename CS, typename A, template<typename, typename, typename> class T> +const P& theta_union_base<EN, EK, P, S, CS, A, T>::get_policy() const { return policy_; } -template<typename EN, typename EK, typename P, typename S, typename CS, typename A> -void theta_union_base<EN, EK, P, S, CS, A>::reset() { +template<typename EN, typename EK, typename P, typename S, typename CS, typename A, template<typename, typename, typename> class T> +void theta_union_base<EN, EK, P, S, CS, A, T>::reset() { table_.reset(); union_theta_ = table_.theta_; } diff --git a/theta/include/theta_union_impl.hpp b/theta/include/theta_union_impl.hpp index 8618618..f444a9f 100644 --- a/theta/include/theta_union_impl.hpp +++ b/theta/include/theta_union_impl.hpp @@ -20,35 +20,37 @@ #ifndef THETA_UNION_IMPL_HPP_ #define THETA_UNION_IMPL_HPP_ +#include <utility> + namespace datasketches { -template<typename A> -theta_union_alloc<A>::theta_union_alloc(uint8_t lg_cur_size, uint8_t lg_nom_size, resize_factor rf, float p, uint64_t theta, uint64_t seed, const A& allocator): -state_(lg_cur_size, lg_nom_size, rf, p, theta, seed, nop_policy(), allocator) +template<typename A, template<typename, typename, typename> class T> +theta_union_alloc<A, T>::theta_union_alloc(theta_table&& table): +state_{nop_policy(), std::forward<T<Entry,ExtractKey,A>>(table)} {} -template<typename A> +template<typename A, template<typename, typename, typename> class T> template<typename SS> -void theta_union_alloc<A>::update(SS&& sketch) { +void theta_union_alloc<A, T>::update(SS&& sketch) { state_.update(std::forward<SS>(sketch)); } -template<typename A> -auto theta_union_alloc<A>::get_result(bool ordered) const -> CompactSketch { +template<typename A, template<typename, typename, typename> class T> +auto theta_union_alloc<A, T>::get_result(bool ordered) const -> CompactSketch { return state_.get_result(ordered); } -template<typename A> -void theta_union_alloc<A>::reset() { +template<typename A, template<typename, typename, typename> class T> +void theta_union_alloc<A, T>::reset() { state_.reset(); } -template<typename A> -theta_union_alloc<A>::builder::builder(const A& allocator): theta_base_builder<builder, A>(allocator) {} +template<typename A, template<typename, typename, typename> class T> +theta_union_alloc<A, T>::builder::builder(const A& allocator): theta_base_builder<builder, A>(allocator) {} -template<typename A> -auto theta_union_alloc<A>::builder::build() const -> theta_union_alloc { - return theta_union_alloc(this->starting_lg_size(), this->lg_k_, this->rf_, this->p_, this->starting_theta(), this->seed_, this->allocator_); +template<typename A, template<typename, typename, typename> class T> +auto theta_union_alloc<A, T>::builder::build() const -> theta_union_alloc { + return theta_union_alloc(Table(this->starting_lg_size(), this->lg_k_, this->rf_, this->p_, this->starting_theta(), this->seed_, this->allocator_)); } } /* namespace datasketches */ diff --git a/tuple/include/array_of_doubles_union_impl.hpp b/tuple/include/array_of_doubles_union_impl.hpp index c3fabf0..6d4fc7e 100644 --- a/tuple/include/array_of_doubles_union_impl.hpp +++ b/tuple/include/array_of_doubles_union_impl.hpp @@ -21,7 +21,7 @@ namespace datasketches { template<typename A> array_of_doubles_union_alloc<A>::array_of_doubles_union_alloc(uint8_t lg_cur_size, uint8_t lg_nom_size, resize_factor rf, float p, uint64_t theta, uint64_t seed, const Policy& policy, const A& allocator): -Base(lg_cur_size, lg_nom_size, rf, p, theta, seed, policy, allocator) +Base(policy, typename Base::theta_table(lg_cur_size, lg_nom_size, rf, p, theta, seed, allocator)) {} template<typename A> diff --git a/tuple/include/tuple_sketch.hpp b/tuple/include/tuple_sketch.hpp index 70571df..c44e564 100644 --- a/tuple/include/tuple_sketch.hpp +++ b/tuple/include/tuple_sketch.hpp @@ -29,7 +29,7 @@ namespace datasketches { // forward-declarations template<typename S, typename A> class tuple_sketch; -template<typename S, typename U, typename P, typename A> class update_tuple_sketch; +template<typename S, typename U, typename P, typename A, template<typename, typename, typename> class T> class update_tuple_sketch; template<typename S, typename A> class compact_tuple_sketch; template<typename A> class theta_sketch_alloc; @@ -203,7 +203,8 @@ template< typename Summary, typename Update = Summary, typename Policy = default_update_policy<Summary, Update>, - typename Allocator = std::allocator<Summary> + typename Allocator = std::allocator<Summary>, + template<typename, typename, typename> class Table = theta_update_sketch_base > class update_tuple_sketch: public tuple_sketch<Summary, Allocator> { public: @@ -213,7 +214,7 @@ public: using iterator = typename Base::iterator; using const_iterator = typename Base::const_iterator; using AllocEntry = typename std::allocator_traits<Allocator>::template rebind_alloc<Entry>; - using tuple_map = theta_update_sketch_base<Entry, ExtractKey, AllocEntry>; + using tuple_map = Table<Entry, ExtractKey, AllocEntry>; using resize_factor = typename tuple_map::resize_factor; // No constructor here. Use builder instead. @@ -524,7 +525,10 @@ protected: // builder -template<typename Derived, typename Policy, typename Allocator> +template< + typename Derived, + typename Policy, + typename Allocator> class tuple_base_builder: public theta_base_builder<Derived, Allocator> { public: tuple_base_builder(const Policy& policy, const Allocator& allocator); @@ -533,8 +537,8 @@ protected: Policy policy_; }; -template<typename S, typename U, typename P, typename A> -class update_tuple_sketch<S, U, P, A>::builder: public tuple_base_builder<builder, P, A> { +template<typename S, typename U, typename P, typename A, template<typename, typename, typename> class T> +class update_tuple_sketch<S, U, P, A, T>::builder: public tuple_base_builder<builder, P, A> { public: /** * Creates and instance of the builder with default parameters. @@ -545,7 +549,7 @@ public: * This is to create an instance of the sketch with predefined parameters. * @return an instance of the sketch */ - update_tuple_sketch<S, U, P, A> build() const; + update_tuple_sketch<S, U, P, A, T> build() const; }; } /* namespace datasketches */ diff --git a/tuple/include/tuple_sketch_impl.hpp b/tuple/include/tuple_sketch_impl.hpp index 0766e4d..149a481 100644 --- a/tuple/include/tuple_sketch_impl.hpp +++ b/tuple/include/tuple_sketch_impl.hpp @@ -95,122 +95,122 @@ string<A> tuple_sketch<S, A>::to_string(bool detail) const { // update sketch -template<typename S, typename U, typename P, typename A> -update_tuple_sketch<S, U, P, A>::update_tuple_sketch(uint8_t lg_cur_size, uint8_t lg_nom_size, resize_factor rf, float p, uint64_t theta, uint64_t seed, const P& policy, const A& allocator): +template<typename S, typename U, typename P, typename A, template<typename, typename, typename> class T> +update_tuple_sketch<S, U, P, A, T>::update_tuple_sketch(uint8_t lg_cur_size, uint8_t lg_nom_size, resize_factor rf, float p, uint64_t theta, uint64_t seed, const P& policy, const A& allocator): policy_(policy), map_(lg_cur_size, lg_nom_size, rf, p, theta, seed, allocator) {} -template<typename S, typename U, typename P, typename A> -A update_tuple_sketch<S, U, P, A>::get_allocator() const { +template<typename S, typename U, typename P, typename A, template<typename, typename, typename> class T> +A update_tuple_sketch<S, U, P, A, T>::get_allocator() const { return map_.allocator_; } -template<typename S, typename U, typename P, typename A> -bool update_tuple_sketch<S, U, P, A>::is_empty() const { +template<typename S, typename U, typename P, typename A, template<typename, typename, typename> class T> +bool update_tuple_sketch<S, U, P, A, T>::is_empty() const { return map_.is_empty_; } -template<typename S, typename U, typename P, typename A> -bool update_tuple_sketch<S, U, P, A>::is_ordered() const { +template<typename S, typename U, typename P, typename A, template<typename, typename, typename> class T> +bool update_tuple_sketch<S, U, P, A, T>::is_ordered() const { return map_.num_entries_ > 1 ? false : true;; } -template<typename S, typename U, typename P, typename A> -uint64_t update_tuple_sketch<S, U, P, A>::get_theta64() const { +template<typename S, typename U, typename P, typename A, template<typename, typename, typename> class T> +uint64_t update_tuple_sketch<S, U, P, A, T>::get_theta64() const { return is_empty() ? theta_constants::MAX_THETA : map_.theta_; } -template<typename S, typename U, typename P, typename A> -uint32_t update_tuple_sketch<S, U, P, A>::get_num_retained() const { +template<typename S, typename U, typename P, typename A, template<typename, typename, typename> class T> +uint32_t update_tuple_sketch<S, U, P, A, T>::get_num_retained() const { return map_.num_entries_; } -template<typename S, typename U, typename P, typename A> -uint16_t update_tuple_sketch<S, U, P, A>::get_seed_hash() const { +template<typename S, typename U, typename P, typename A, template<typename, typename, typename> class T> +uint16_t update_tuple_sketch<S, U, P, A, T>::get_seed_hash() const { return compute_seed_hash(map_.seed_); } -template<typename S, typename U, typename P, typename A> -uint8_t update_tuple_sketch<S, U, P, A>::get_lg_k() const { +template<typename S, typename U, typename P, typename A, template<typename, typename, typename> class T> +uint8_t update_tuple_sketch<S, U, P, A, T>::get_lg_k() const { return map_.lg_nom_size_; } -template<typename S, typename U, typename P, typename A> -auto update_tuple_sketch<S, U, P, A>::get_rf() const -> resize_factor { +template<typename S, typename U, typename P, typename A, template<typename, typename, typename> class T> +auto update_tuple_sketch<S, U, P, A, T>::get_rf() const -> resize_factor { return map_.rf_; } -template<typename S, typename U, typename P, typename A> +template<typename S, typename U, typename P, typename A, template<typename, typename, typename> class T> template<typename UU> -void update_tuple_sketch<S, U, P, A>::update(uint64_t key, UU&& value) { +void update_tuple_sketch<S, U, P, A, T>::update(uint64_t key, UU&& value) { update(&key, sizeof(key), std::forward<UU>(value)); } -template<typename S, typename U, typename P, typename A> +template<typename S, typename U, typename P, typename A, template<typename, typename, typename> class T> template<typename UU> -void update_tuple_sketch<S, U, P, A>::update(int64_t key, UU&& value) { +void update_tuple_sketch<S, U, P, A, T>::update(int64_t key, UU&& value) { update(&key, sizeof(key), std::forward<UU>(value)); } -template<typename S, typename U, typename P, typename A> +template<typename S, typename U, typename P, typename A, template<typename, typename, typename> class T> template<typename UU> -void update_tuple_sketch<S, U, P, A>::update(uint32_t key, UU&& value) { +void update_tuple_sketch<S, U, P, A, T>::update(uint32_t key, UU&& value) { update(static_cast<int32_t>(key), std::forward<UU>(value)); } -template<typename S, typename U, typename P, typename A> +template<typename S, typename U, typename P, typename A, template<typename, typename, typename> class T> template<typename UU> -void update_tuple_sketch<S, U, P, A>::update(int32_t key, UU&& value) { +void update_tuple_sketch<S, U, P, A, T>::update(int32_t key, UU&& value) { update(static_cast<int64_t>(key), std::forward<UU>(value)); } -template<typename S, typename U, typename P, typename A> +template<typename S, typename U, typename P, typename A, template<typename, typename, typename> class T> template<typename UU> -void update_tuple_sketch<S, U, P, A>::update(uint16_t key, UU&& value) { +void update_tuple_sketch<S, U, P, A, T>::update(uint16_t key, UU&& value) { update(static_cast<int16_t>(key), std::forward<UU>(value)); } -template<typename S, typename U, typename P, typename A> +template<typename S, typename U, typename P, typename A, template<typename, typename, typename> class T> template<typename UU> -void update_tuple_sketch<S, U, P, A>::update(int16_t key, UU&& value) { +void update_tuple_sketch<S, U, P, A, T>::update(int16_t key, UU&& value) { update(static_cast<int64_t>(key), std::forward<UU>(value)); } -template<typename S, typename U, typename P, typename A> +template<typename S, typename U, typename P, typename A, template<typename, typename, typename> class T> template<typename UU> -void update_tuple_sketch<S, U, P, A>::update(uint8_t key, UU&& value) { +void update_tuple_sketch<S, U, P, A, T>::update(uint8_t key, UU&& value) { update(static_cast<int8_t>(key), std::forward<UU>(value)); } -template<typename S, typename U, typename P, typename A> +template<typename S, typename U, typename P, typename A, template<typename, typename, typename> class T> template<typename UU> -void update_tuple_sketch<S, U, P, A>::update(int8_t key, UU&& value) { +void update_tuple_sketch<S, U, P, A, T>::update(int8_t key, UU&& value) { update(static_cast<int64_t>(key), std::forward<UU>(value)); } -template<typename S, typename U, typename P, typename A> +template<typename S, typename U, typename P, typename A, template<typename, typename, typename> class T> template<typename UU> -void update_tuple_sketch<S, U, P, A>::update(const std::string& key, UU&& value) { +void update_tuple_sketch<S, U, P, A, T>::update(const std::string& key, UU&& value) { if (key.empty()) return; update(key.c_str(), key.length(), std::forward<UU>(value)); } -template<typename S, typename U, typename P, typename A> +template<typename S, typename U, typename P, typename A, template<typename, typename, typename> class T> template<typename UU> -void update_tuple_sketch<S, U, P, A>::update(double key, UU&& value) { +void update_tuple_sketch<S, U, P, A, T>::update(double key, UU&& value) { update(canonical_double(key), std::forward<UU>(value)); } -template<typename S, typename U, typename P, typename A> +template<typename S, typename U, typename P, typename A, template<typename, typename, typename> class T> template<typename UU> -void update_tuple_sketch<S, U, P, A>::update(float key, UU&& value) { +void update_tuple_sketch<S, U, P, A, T>::update(float key, UU&& value) { update(static_cast<double>(key), std::forward<UU>(value)); } -template<typename S, typename U, typename P, typename A> +template<typename S, typename U, typename P, typename A, template<typename, typename, typename> class T> template<typename UU> -void update_tuple_sketch<S, U, P, A>::update(const void* key, size_t length, UU&& value) { +void update_tuple_sketch<S, U, P, A, T>::update(const void* key, size_t length, UU&& value) { const uint64_t hash = map_.hash_and_screen(key, length); if (hash == 0) return; auto result = map_.find(hash); @@ -223,43 +223,43 @@ void update_tuple_sketch<S, U, P, A>::update(const void* key, size_t length, UU& } } -template<typename S, typename U, typename P, typename A> -void update_tuple_sketch<S, U, P, A>::trim() { +template<typename S, typename U, typename P, typename A, template<typename, typename, typename> class T> +void update_tuple_sketch<S, U, P, A, T>::trim() { map_.trim(); } -template<typename S, typename U, typename P, typename A> -void update_tuple_sketch<S, U, P, A>::reset() { +template<typename S, typename U, typename P, typename A, template<typename, typename, typename> class T> +void update_tuple_sketch<S, U, P, A, T>::reset() { map_.reset(); } -template<typename S, typename U, typename P, typename A> -auto update_tuple_sketch<S, U, P, A>::begin() -> iterator { +template<typename S, typename U, typename P, typename A, template<typename, typename, typename> class T> +auto update_tuple_sketch<S, U, P, A, T>::begin() -> iterator { return iterator(map_.entries_, 1 << map_.lg_cur_size_, 0); } -template<typename S, typename U, typename P, typename A> -auto update_tuple_sketch<S, U, P, A>::end() -> iterator { +template<typename S, typename U, typename P, typename A, template<typename, typename, typename> class T> +auto update_tuple_sketch<S, U, P, A, T>::end() -> iterator { return iterator(nullptr, 0, 1 << map_.lg_cur_size_); } -template<typename S, typename U, typename P, typename A> -auto update_tuple_sketch<S, U, P, A>::begin() const -> const_iterator { +template<typename S, typename U, typename P, typename A, template<typename, typename, typename> class T> +auto update_tuple_sketch<S, U, P, A, T>::begin() const -> const_iterator { return const_iterator(map_.entries_, 1 << map_.lg_cur_size_, 0); } -template<typename S, typename U, typename P, typename A> -auto update_tuple_sketch<S, U, P, A>::end() const -> const_iterator { +template<typename S, typename U, typename P, typename A, template<typename, typename, typename> class T> +auto update_tuple_sketch<S, U, P, A, T>::end() const -> const_iterator { return const_iterator(nullptr, 0, 1 << map_.lg_cur_size_); } -template<typename S, typename U, typename P, typename A> -compact_tuple_sketch<S, A> update_tuple_sketch<S, U, P, A>::compact(bool ordered) const { +template<typename S, typename U, typename P, typename A, template<typename, typename, typename> class T> +compact_tuple_sketch<S, A> update_tuple_sketch<S, U, P, A, T>::compact(bool ordered) const { return compact_tuple_sketch<S, A>(*this, ordered); } -template<typename S, typename U, typename P, typename A> -void update_tuple_sketch<S, U, P, A>::print_specifics(std::ostringstream& os) const { +template<typename S, typename U, typename P, typename A, template<typename, typename, typename> class T> +void update_tuple_sketch<S, U, P, A, T>::print_specifics(std::ostringstream& os) const { os << " lg nominal size : " << (int) map_.lg_nom_size_ << std::endl; os << " lg current size : " << (int) map_.lg_cur_size_ << std::endl; os << " resize factor : " << (1 << map_.rf_) << std::endl; @@ -589,12 +589,12 @@ template<typename D, typename P, typename A> tuple_base_builder<D, P, A>::tuple_base_builder(const P& policy, const A& allocator): theta_base_builder<D, A>(allocator), policy_(policy) {} -template<typename S, typename U, typename P, typename A> -update_tuple_sketch<S, U, P, A>::builder::builder(const P& policy, const A& allocator): +template<typename S, typename U, typename P, typename A, template<typename, typename, typename> class T> +update_tuple_sketch<S, U, P, A, T>::builder::builder(const P& policy, const A& allocator): tuple_base_builder<builder, P, A>(policy, allocator) {} -template<typename S, typename U, typename P, typename A> -auto update_tuple_sketch<S, U, P, A>::builder::build() const -> update_tuple_sketch { +template<typename S, typename U, typename P, typename A, template<typename, typename, typename> class T> +auto update_tuple_sketch<S, U, P, A, T>::builder::build() const -> update_tuple_sketch { return update_tuple_sketch(this->starting_lg_size(), this->lg_k_, this->rf_, this->p_, this->starting_theta(), this->seed_, this->policy_, this->allocator_); } diff --git a/tuple/include/tuple_union.hpp b/tuple/include/tuple_union.hpp index 1c518da..4a71748 100644 --- a/tuple/include/tuple_union.hpp +++ b/tuple/include/tuple_union.hpp @@ -36,7 +36,8 @@ struct default_union_policy { template< typename Summary, typename Policy = default_union_policy<Summary>, - typename Allocator = std::allocator<Summary> + typename Allocator = std::allocator<Summary>, + template<typename, typename, typename> class Table = theta_update_sketch_base > class tuple_union { public: @@ -46,6 +47,7 @@ public: using CompactSketch = compact_tuple_sketch<Summary, Allocator>; using AllocEntry = typename std::allocator_traits<Allocator>::template rebind_alloc<Entry>; using resize_factor = theta_constants::resize_factor; + using theta_table = Table<Entry, ExtractKey, AllocEntry>; // reformulate the external policy that operates on Summary // in terms of operations on Entry @@ -61,7 +63,7 @@ public: Policy policy_; }; - using State = theta_union_base<Entry, ExtractKey, internal_policy, Sketch, CompactSketch, AllocEntry>; + using State = theta_union_base<Entry, ExtractKey, internal_policy, Sketch, CompactSketch, AllocEntry, Table>; // No constructor here. Use builder instead. class builder; @@ -89,12 +91,14 @@ protected: State state_; // for builder - tuple_union(uint8_t lg_cur_size, uint8_t lg_nom_size, resize_factor rf, float p, uint64_t theta, uint64_t seed, const Policy& policy, const Allocator& allocator); + tuple_union(const Policy& policy, theta_table&& table); }; -template<typename S, typename P, typename A> -class tuple_union<S, P, A>::builder: public tuple_base_builder<builder, P, A> { +template<typename S, typename P, typename A, template<typename, typename, typename> class T> +class tuple_union<S, P, A, T>::builder: public tuple_base_builder<builder, P, A> { public: + using Table = tuple_union::theta_table; + /** * Creates and instance of the builder with default parameters. */ diff --git a/tuple/include/tuple_union_impl.hpp b/tuple/include/tuple_union_impl.hpp index 98ea8a5..4ad79e9 100644 --- a/tuple/include/tuple_union_impl.hpp +++ b/tuple/include/tuple_union_impl.hpp @@ -19,34 +19,34 @@ namespace datasketches { -template<typename S, typename P, typename A> -tuple_union<S, P, A>::tuple_union(uint8_t lg_cur_size, uint8_t lg_nom_size, resize_factor rf, float p, uint64_t theta, uint64_t seed, const P& policy, const A& allocator): -state_(lg_cur_size, lg_nom_size, rf, p, theta, seed, internal_policy(policy), allocator) +template<typename S, typename P, typename A, template<typename, typename, typename> class T> +tuple_union<S, P, A, T>::tuple_union(const P& policy, theta_table&& table): +state_{internal_policy(policy), std::forward<T<Entry,ExtractKey,AllocEntry>>(table)} {} -template<typename S, typename P, typename A> +template<typename S, typename P, typename A, template<typename, typename, typename> class T> template<typename SS> -void tuple_union<S, P, A>::update(SS&& sketch) { +void tuple_union<S, P, A, T>::update(SS&& sketch) { state_.update(std::forward<SS>(sketch)); } -template<typename S, typename P, typename A> -auto tuple_union<S, P, A>::get_result(bool ordered) const -> CompactSketch { +template<typename S, typename P, typename A, template<typename, typename, typename> class T> +auto tuple_union<S, P, A, T>::get_result(bool ordered) const -> CompactSketch { return state_.get_result(ordered); } -template<typename S, typename P, typename A> -void tuple_union<S, P, A>::reset() { +template<typename S, typename P, typename A, template<typename, typename, typename> class T> +void tuple_union<S, P, A, T>::reset() { return state_.reset(); } -template<typename S, typename P, typename A> -tuple_union<S, P, A>::builder::builder(const P& policy, const A& allocator): +template<typename S, typename P, typename A, template<typename, typename, typename> class T> +tuple_union<S, P, A, T>::builder::builder(const P& policy, const A& allocator): tuple_base_builder<builder, P, A>(policy, allocator) {} -template<typename S, typename P, typename A> -auto tuple_union<S, P, A>::builder::build() const -> tuple_union { - return tuple_union(this->starting_lg_size(), this->lg_k_, this->rf_, this->p_, this->starting_theta(), this->seed_, this->policy_, this->allocator_); +template<typename S, typename P, typename A, template<typename, typename, typename> class T> +auto tuple_union<S, P, A, T>::builder::build() const -> tuple_union { + return tuple_union(this->policy_, Table(this->starting_lg_size(), this->lg_k_, this->rf_, this->p_, this->starting_theta(), this->seed_, this->allocator_)); } } /* namespace datasketches */ --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
