// 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: Craig Silverstein//// A dense hashtable is a particular implementation of// a hashtable: one that is meant to minimize memory allocation.// It does this by using an array to store all the data.  We// steal a value from the key space to indicate "empty" array// elements (ie indices where no item lives) and another to indicate// "deleted" elements.//// (Note it is possible to change the value of the delete key// on the fly; you can even remove it, though after that point// the hashtable is insert_only until you set it again.  The empty// value however can't be changed.)//// To minimize allocation and pointer overhead, we use internal// probing, in which the hashtable is a single table, and collisions// are resolved by trying to insert again in another bucket.  The// most cache-efficient internal probing schemes are linear probing// (which suffers, alas, from clumping) and quadratic probing, which// is what we implement by default.//// Type requirements: value_type is required to be Copy Constructible// and Default Constructible. It is not required to be (and commonly// isn't) Assignable.//// You probably shouldn't use this code directly.  Use// <google/dense_hash_map> or <google/dense_hash_set> instead.// You can change the following below:// HT_OCCUPANCY_FLT      -- how full before we double size// HT_EMPTY_FLT          -- how empty before we halve size// HT_MIN_BUCKETS        -- default smallest bucket size//// You can also change enlarge_resize_percent (which defaults to// HT_OCCUPANCY_FLT), and shrink_resize_percent (which defaults to// HT_EMPTY_FLT) with set_resizing_parameters().//// How to decide what values to use?// shrink_resize_percent's default of .4 * OCCUPANCY_FLT, is probably good.// HT_MIN_BUCKETS is probably unnecessary since you can specify// (indirectly) the starting number of buckets at construct-time.// For enlarge_resize_percent, you can use this chart to try to trade-off// expected lookup time to the space taken up.  By default, this// code uses quadratic probing, though you can change it to linear// via _JUMP below if you really want to.//// From http://www.augustana.ca/~mohrj/courses/1999.fall/csc210/lecture_notes/hashing.html// NUMBER OF PROBES / LOOKUP       Successful            Unsuccessful// Quadratic collision resolution   1 - ln(1-L) - L/2    1/(1-L) - L - ln(1-L)// Linear collision resolution     [1+1/(1-L)]/2         [1+1/(1-L)2]/2//// -- enlarge_resize_percent --         0.10  0.50  0.60  0.75  0.80  0.90  0.99// QUADRATIC COLLISION RES.//    probes/successful lookup    1.05  1.44  1.62  2.01  2.21  2.85  5.11//    probes/unsuccessful lookup  1.11  2.19  2.82  4.64  5.81  11.4  103.6// LINEAR COLLISION RES.//    probes/successful lookup    1.06  1.5   1.75  2.5   3.0   5.5   50.5//    probes/unsuccessful lookup  1.12  2.5   3.6   8.5   13.0  50.0  5000.0#ifndef _DENSEHASHTABLE_H_#define _DENSEHASHTABLE_H_// The probing method// Linear probing// #define JUMP_(key, num_probes)    ( 1 )// Quadratic-ish probing#define JUMP_(key, num_probes)    ( num_probes )// Hashtable class, used to implement the hashed associative containers// hash_set and hash_map.#include <google/sparsehash/sparseconfig.h>#include <assert.h>#include <stdlib.h>             // for abort()#include <algorithm>            // For swap(), eg#include <iostream>             // For cerr#include <memory>               // For uninitialized_fill, uninitialized_copy#include <utility>              // for pair<>#include <iterator>             // for facts about iterator tags#include <google/type_traits.h> // for true_type, integral_constant, etc._START_GOOGLE_NAMESPACE_using STL_NAMESPACE::pair;template <class Value, class Key, class HashFcn,          class ExtractKey, class EqualKey, class Alloc>class dense_hashtable;template <class V, class K, class HF, class ExK, class EqK, class A>struct dense_hashtable_iterator;template <class V, class K, class HF, class ExK, class EqK, class A>struct dense_hashtable_const_iterator;// We're just an array, but we need to skip over empty and deleted elementstemplate <class V, class K, class HF, class ExK, class EqK, class A>struct dense_hashtable_iterator { public:  typedef dense_hashtable_iterator<V,K,HF,ExK,EqK,A>       iterator;  typedef dense_hashtable_const_iterator<V,K,HF,ExK,EqK,A> const_iterator;  typedef STL_NAMESPACE::forward_iterator_tag iterator_category;  typedef V value_type;  typedef ptrdiff_t difference_type;  typedef size_t size_type;  typedef V& reference;                // Value  typedef V* pointer;  // "Real" constructor and default constructor  dense_hashtable_iterator(const dense_hashtable<V,K,HF,ExK,EqK,A> *h,                           pointer it, pointer it_end, bool advance)    : ht(h), pos(it), end(it_end)   {    if (advance)  advance_past_empty_and_deleted();  }  dense_hashtable_iterator() { }  // The default destructor is fine; we don't define one  // The default operator= is fine; we don't define one  // Happy dereferencer  reference operator*() const { return *pos; }  pointer operator->() const { return &(operator*()); }  // Arithmetic.  The only hard part is making sure that  // we're not on an empty or marked-deleted array element  void advance_past_empty_and_deleted() {    while ( pos != end && (ht->test_empty(*this) || ht->test_deleted(*this)) )      ++pos;  }  iterator& operator++()   {    assert(pos != end); ++pos; advance_past_empty_and_deleted(); return *this;  }  iterator operator++(int) { iterator tmp(*this); ++*this; return tmp; }  // Comparison.  bool operator==(const iterator& it) const { return pos == it.pos; }  bool operator!=(const iterator& it) const { return pos != it.pos; }  // The actual data  const dense_hashtable<V,K,HF,ExK,EqK,A> *ht;  pointer pos, end;};// Now do it all again, but with const-ness!template <class V, class K, class HF, class ExK, class EqK, class A>struct dense_hashtable_const_iterator { public:  typedef dense_hashtable_iterator<V,K,HF,ExK,EqK,A>       iterator;  typedef dense_hashtable_const_iterator<V,K,HF,ExK,EqK,A> const_iterator;  typedef STL_NAMESPACE::forward_iterator_tag iterator_category;  typedef V value_type;  typedef ptrdiff_t difference_type;  typedef size_t size_type;  typedef const V& reference;                // Value  typedef const V* pointer;  // "Real" constructor and default constructor  dense_hashtable_const_iterator(const dense_hashtable<V,K,HF,ExK,EqK,A> *h,                                 pointer it, pointer it_end, bool advance)    : ht(h), pos(it), end(it_end)   {    if (advance)  advance_past_empty_and_deleted();  }  dense_hashtable_const_iterator() { }  // This lets us convert regular iterators to const iterators  dense_hashtable_const_iterator(const iterator &it)    : ht(it.ht), pos(it.pos), end(it.end) { }  // The default destructor is fine; we don't define one  // The default operator= is fine; we don't define one  // Happy dereferencer  reference operator*() const { return *pos; }  pointer operator->() const { return &(operator*()); }  // Arithmetic.  The only hard part is making sure that  // we're not on an empty or marked-deleted array element  void advance_past_empty_and_deleted() {    while ( pos != end && (ht->test_empty(*this) || ht->test_deleted(*this)) )      ++pos;  }  const_iterator& operator++()   {    assert(pos != end); ++pos; advance_past_empty_and_deleted(); return *this;  }  const_iterator operator++(int) { const_iterator tmp(*this); ++*this; return tmp; }  // Comparison.  bool operator==(const const_iterator& it) const { return pos == it.pos; }  bool operator!=(const const_iterator& it) const { return pos != it.pos; }  // The actual data  const dense_hashtable<V,K,HF,ExK,EqK,A> *ht;  pointer pos, end;};template <class Value, class Key, class HashFcn,          class ExtractKey, class EqualKey, class Alloc>class dense_hashtable { public:  typedef Key key_type;  typedef Value value_type;  typedef HashFcn hasher;  typedef EqualKey key_equal;  typedef size_t            size_type;  typedef ptrdiff_t         difference_type;  typedef value_type*       pointer;  typedef const value_type* const_pointer;  typedef value_type&       reference;  typedef const value_type& const_reference;  typedef dense_hashtable_iterator<Value, Key, HashFcn,                                   ExtractKey, EqualKey, Alloc>  iterator;  typedef dense_hashtable_const_iterator<Value, Key, HashFcn,                                          ExtractKey, EqualKey, Alloc>  const_iterator;  // How full we let the table get before we resize.  Knuth says .8 is  // good -- higher causes us to probe too much, though saves memory  static const float HT_OCCUPANCY_FLT; // = 0.8;  // How empty we let the table get before we resize lower.  // (0.0 means never resize lower.)  // It should be less than OCCUPANCY_FLT / 2 or we thrash resizing  static const float HT_EMPTY_FLT; // = 0.4 * HT_OCCUPANCY_FLT  // Minimum size we're willing to let hashtables be.  // Must be a power of two, and at least 4.  // Note, however, that for a given hashtable, the initial size is a  // function of the first constructor arg, and may be >HT_MIN_BUCKETS.  static const size_t HT_MIN_BUCKETS  = 32;  // ITERATOR FUNCTIONS  iterator begin()             { return iterator(this, table,                                                 table + num_buckets, true); }  iterator end()               { return iterator(this, table + num_buckets,                                                 table + num_buckets, true); }  const_iterator begin() const { return const_iterator(this, table,                                                       table+num_buckets,true);}  const_iterator end() const   { return const_iterator(this, table + num_buckets,                                                       table+num_buckets,true);}  // ACCESSOR FUNCTIONS for the things we templatize on, basically  hasher hash_funct() const { return hash; }  key_equal key_eq() const  { return equals; }  // Annoyingly, we can't copy values around, because they might have  // const components (they're probably pair<const X, Y>).  We use  // explicit destructor invocation and placement new to get around  // this.  Arg. private:  void set_value(value_type* dst, const value_type& src) {    dst->~value_type();    new(dst) value_type(src);  }  void destroy_buckets(size_type first, size_type last) {    for ( ; first != last; ++first)      table[first].~value_type();  }  // DELETE HELPER FUNCTIONS  // This lets the user describe a key that will indicate deleted  // table entries.  This key should be an "impossible" entry --  // if you try to insert it for real, you won't be able to retrieve it!  // (NB: while you pass in an entire value, only the key part is looked  // at.  This is just because I don't know how to assign just a key.) private:  void squash_deleted() {           // gets rid of any deleted entries we have    if ( num_deleted ) {            // get rid of deleted before writing      dense_hashtable tmp(*this);   // copying will get rid of deleted      swap(tmp);                    // now we are tmp    }    assert(num_deleted == 0);  } public:  void set_deleted_key(const value_type &val) {    // the empty indicator (if specified) and the deleted indicator    // must be different    assert(!use_empty || !equals(get_key(val), get_key(emptyval)));    // It's only safe to change what "deleted" means if we purge deleted guys    squash_deleted();    use_deleted = true;    set_value(&delval, val);  }  void clear_deleted_key() {    squash_deleted();