Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Copyright (c) 2005, Google Inc.
- // All rights reserved.
- //
- // Redistribution and use in source and binary forms, with or without
- // modification, are permitted provided that the following conditions are
- // met:
- //
- // * Redistributions of source code must retain the above copyright
- // notice, this list of conditions and the following disclaimer.
- // * Redistributions in binary form must reproduce the above
- // copyright notice, this list of conditions and the following disclaimer
- // in the documentation and/or other materials provided with the
- // distribution.
- // * Neither the name of Google Inc. nor the names of its
- // contributors may be used to endorse or promote products derived from
- // this software without specific prior written permission.
- //
- // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
- // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
- // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
- // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
- // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
- // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
- // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
- // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
- // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
- // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
- // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- // ---
- // Author: Giao Nguyen
- #ifndef UTIL_GTL_HASHTABLE_COMMON_H_
- #define UTIL_GTL_HASHTABLE_COMMON_H_
- #include <assert.h>
- // Settings contains parameters for growing and shrinking the table.
- // It also packages zero-size functor (ie. hasher).
- template<typename Key, typename HashFunc,
- typename SizeType, int HT_MIN_BUCKETS>
- class sh_hashtable_settings : public HashFunc {
- public:
- typedef Key key_type;
- typedef HashFunc hasher;
- typedef SizeType size_type;
- public:
- sh_hashtable_settings(const hasher& hf,
- const float ht_occupancy_flt,
- const float ht_empty_flt)
- : hasher(hf),
- enlarge_threshold_(0),
- shrink_threshold_(0),
- consider_shrink_(false),
- use_empty_(false),
- use_deleted_(false),
- num_ht_copies_(0) {
- set_enlarge_factor(ht_occupancy_flt);
- set_shrink_factor(ht_empty_flt);
- }
- size_type hash(const key_type& v) const {
- return hasher::operator()(v);
- }
- float enlarge_factor() const {
- return enlarge_factor_;
- }
- void set_enlarge_factor(float f) {
- enlarge_factor_ = f;
- }
- float shrink_factor() const {
- return shrink_factor_;
- }
- void set_shrink_factor(float f) {
- shrink_factor_ = f;
- }
- size_type enlarge_threshold() const {
- return enlarge_threshold_;
- }
- void set_enlarge_threshold(size_type t) {
- enlarge_threshold_ = t;
- }
- size_type shrink_threshold() const {
- return shrink_threshold_;
- }
- void set_shrink_threshold(size_type t) {
- shrink_threshold_ = t;
- }
- size_type enlarge_size(size_type x) const {
- return static_cast<size_type>(x * enlarge_factor_);
- }
- size_type shrink_size(size_type x) const {
- return static_cast<size_type>(x * shrink_factor_);
- }
- bool consider_shrink() const {
- return consider_shrink_;
- }
- void set_consider_shrink(bool t) {
- consider_shrink_ = t;
- }
- bool use_empty() const {
- return use_empty_;
- }
- void set_use_empty(bool t) {
- use_empty_ = t;
- }
- bool use_deleted() const {
- return use_deleted_;
- }
- void set_use_deleted(bool t) {
- use_deleted_ = t;
- }
- size_type num_ht_copies() const {
- return static_cast<size_type>(num_ht_copies_);
- }
- void inc_num_ht_copies() {
- ++num_ht_copies_;
- }
- // Reset the enlarge and shrink thresholds
- void reset_thresholds(size_type num_buckets) {
- set_enlarge_threshold(enlarge_size(num_buckets));
- set_shrink_threshold(shrink_size(num_buckets));
- // whatever caused us to reset already considered
- set_consider_shrink(false);
- }
- // Caller is resposible for calling reset_threshold right after
- // set_resizing_parameters.
- void set_resizing_parameters(float shrink, float grow) {
- assert(shrink >= 0.0);
- assert(grow <= 1.0);
- if (shrink > grow/2.0f)
- shrink = grow / 2.0f; // otherwise we thrash hashtable size
- set_shrink_factor(shrink);
- set_enlarge_factor(grow);
- }
- // This is the smallest size a hashtable can be without being too crowded
- // If you like, you can give a min #buckets as well as a min #elts
- size_type min_buckets(size_type num_elts, size_type min_buckets_wanted) {
- float enlarge = enlarge_factor();
- size_type sz = HT_MIN_BUCKETS; // min buckets allowed
- while ( sz < min_buckets_wanted ||
- num_elts >= static_cast<size_type>(sz * enlarge) ) {
- // This just prevents overflowing size_type, since sz can exceed
- // max_size() here.
- if (static_cast<size_type>(sz * 2) < sz) {
- throw std::length_error("resize overflow"); // protect against overflow
- }
- sz *= 2;
- }
- return sz;
- }
- private:
- size_type enlarge_threshold_; // table.size() * enlarge_factor
- size_type shrink_threshold_; // table.size() * shrink_factor
- float enlarge_factor_; // how full before resize
- float shrink_factor_; // how empty before resize
- // consider_shrink=true if we should try to shrink before next insert
- bool consider_shrink_;
- bool use_empty_; // used only by densehashtable, not sparsehashtable
- bool use_deleted_; // false until delkey has been set
- // num_ht_copies is a counter incremented every Copy/Move
- unsigned int num_ht_copies_;
- };
- #endif // UTIL_GTL_HASHTABLE_COMMON_H_
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement