diff options
Diffstat (limited to 'sources/shiboken2/ext/sparsehash/google/dense_hash_set')
| -rw-r--r-- | sources/shiboken2/ext/sparsehash/google/dense_hash_set | 287 |
1 files changed, 0 insertions, 287 deletions
diff --git a/sources/shiboken2/ext/sparsehash/google/dense_hash_set b/sources/shiboken2/ext/sparsehash/google/dense_hash_set deleted file mode 100644 index faa21dc59..000000000 --- a/sources/shiboken2/ext/sparsehash/google/dense_hash_set +++ /dev/null @@ -1,287 +0,0 @@ -// 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 -// -// This is just a very thin wrapper over densehashtable.h, just -// like sgi stl's stl_hash_set is a very thin wrapper over -// stl_hashtable. The major thing we define is operator[], because -// we have a concept of a data_type which stl_hashtable doesn't -// (it only has a key and a value). -// -// This is more different from dense_hash_map than you might think, -// because all iterators for sets are const (you obviously can't -// change the key, and for sets there is no value). -// -// NOTE: this is exactly like sparse_hash_set.h, with the word -// "sparse" replaced by "dense", except for the addition of -// set_empty_key(). -// -// YOU MUST CALL SET_EMPTY_KEY() IMMEDIATELY AFTER CONSTRUCTION. -// -// Otherwise your program will die in mysterious ways. -// -// In other respects, we adhere mostly to the STL semantics for -// hash-set. One important exception is that insert() invalidates -// iterators entirely. On the plus side, though, erase() doesn't -// invalidate iterators at all, or even change the ordering of elements. -// -// Here are a few "power user" tips: -// -// 1) set_deleted_key(): -// If you want to use erase() you must call set_deleted_key(), -// in addition to set_empty_key(), after construction. -// The deleted and empty keys must differ. -// -// 2) resize(0): -// When an item is deleted, its memory isn't freed right -// away. This allows you to iterate over a hashtable, -// and call erase(), without invalidating the iterator. -// To force the memory to be freed, call resize(0). -// For tr1 compatibility, this can also be called as rehash(0). -// -// 3) min_load_factor(0.0) -// Setting the minimum load factor to 0.0 guarantees that -// the hash table will never shrink. -// -// Guide to what kind of hash_set to use: -// (1) dense_hash_set: fastest, uses the most memory -// (2) sparse_hash_set: slowest, uses the least memory -// (3) hash_set (STL): in the middle -// Typically I use sparse_hash_set when I care about space and/or when -// I need to save the hashtable on disk. I use hash_set otherwise. I -// don't personally use dense_hash_set ever; some people use it for -// small sets with lots of lookups. -// -// - dense_hash_set has, typically, a factor of 2 memory overhead (if your -// data takes up X bytes, the hash_set uses X more bytes in overhead). -// - sparse_hash_set has about 2 bits overhead per entry. -// - sparse_hash_map can be 3-7 times slower than the others for lookup and, -// especially, inserts. See time_hash_map.cc for details. -// -// See /usr/(local/)?doc/sparsehash-*/dense_hash_set.html -// for information about how to use this class. - -#ifndef _DENSE_HASH_SET_H_ -#define _DENSE_HASH_SET_H_ - -#include <google/sparsehash/sparseconfig.h> -#include <stdio.h> // for FILE * in read()/write() -#include <algorithm> // for the default template args -#include <functional> // for equal_to -#include <memory> // for alloc<> -#include <utility> // for pair<> -#include HASH_FUN_H // defined in config.h -#include <google/sparsehash/densehashtable.h> - - -_START_GOOGLE_NAMESPACE_ - -using STL_NAMESPACE::pair; - -template <class Value, - class HashFcn = SPARSEHASH_HASH<Value>, // defined in sparseconfig.h - class EqualKey = STL_NAMESPACE::equal_to<Value>, - class Alloc = STL_NAMESPACE::allocator<Value> > -class dense_hash_set { - private: - // Apparently identity is not stl-standard, so we define our own - struct Identity { - Value& operator()(Value& v) const { return v; } - const Value& operator()(const Value& v) const { return v; } - }; - struct SetKey { - void operator()(Value* value, const Value& new_key) const { - *value = new_key; - } - }; - - // The actual data - typedef dense_hashtable<Value, Value, HashFcn, - Identity, SetKey, EqualKey, Alloc> ht; - ht rep; - - public: - typedef typename ht::key_type key_type; - typedef typename ht::value_type value_type; - typedef typename ht::hasher hasher; - typedef typename ht::key_equal key_equal; - typedef Alloc allocator_type; - - typedef typename ht::size_type size_type; - typedef typename ht::difference_type difference_type; - typedef typename ht::const_pointer pointer; - typedef typename ht::const_pointer const_pointer; - typedef typename ht::const_reference reference; - typedef typename ht::const_reference const_reference; - - typedef typename ht::const_iterator iterator; - typedef typename ht::const_iterator const_iterator; - typedef typename ht::const_local_iterator local_iterator; - typedef typename ht::const_local_iterator const_local_iterator; - - - // Iterator functions -- recall all iterators are const - iterator begin() const { return rep.begin(); } - iterator end() const { return rep.end(); } - - // These come from tr1's unordered_set. For us, a bucket has 0 or 1 elements. - local_iterator begin(size_type i) const { return rep.begin(i); } - local_iterator end(size_type i) const { return rep.end(i); } - - - // Accessor functions - hasher hash_funct() const { return rep.hash_funct(); } - key_equal key_eq() const { return rep.key_eq(); } - - - // Constructors - explicit dense_hash_set(size_type expected_max_items_in_table = 0, - const hasher& hf = hasher(), - const key_equal& eql = key_equal()) - : rep(expected_max_items_in_table, hf, eql) { } - - template <class InputIterator> - dense_hash_set(InputIterator f, InputIterator l, - size_type expected_max_items_in_table = 0, - const hasher& hf = hasher(), - const key_equal& eql = key_equal()) - : rep(expected_max_items_in_table, hf, eql) { - rep.insert(f, l); - } - // We use the default copy constructor - // We use the default operator=() - // We use the default destructor - - void clear() { rep.clear(); } - // This clears the hash set without resizing it down to the minimum - // bucket count, but rather keeps the number of buckets constant - void clear_no_resize() { rep.clear_no_resize(); } - void swap(dense_hash_set& hs) { rep.swap(hs.rep); } - - - // Functions concerning size - size_type size() const { return rep.size(); } - size_type max_size() const { return rep.max_size(); } - bool empty() const { return rep.empty(); } - size_type bucket_count() const { return rep.bucket_count(); } - size_type max_bucket_count() const { return rep.max_bucket_count(); } - - // These are tr1 methods. bucket() is the bucket the key is or would be in. - size_type bucket_size(size_type i) const { return rep.bucket_size(i); } - size_type bucket(const key_type& key) const { return rep.bucket(key); } - float load_factor() const { - return size() * 1.0f / bucket_count(); - } - float max_load_factor() const { - float shrink, grow; - rep.get_resizing_parameters(&shrink, &grow); - return grow; - } - void max_load_factor(float new_grow) { - float shrink, grow; - rep.get_resizing_parameters(&shrink, &grow); - rep.set_resizing_parameters(shrink, new_grow); - } - // These aren't tr1 methods but perhaps ought to be. - float min_load_factor() const { - float shrink, grow; - rep.get_resizing_parameters(&shrink, &grow); - return shrink; - } - void min_load_factor(float new_shrink) { - float shrink, grow; - rep.get_resizing_parameters(&shrink, &grow); - rep.set_resizing_parameters(new_shrink, grow); - } - // Deprecated; use min_load_factor() or max_load_factor() instead. - void set_resizing_parameters(float shrink, float grow) { - return rep.set_resizing_parameters(shrink, grow); - } - - void resize(size_type hint) { rep.resize(hint); } - void rehash(size_type hint) { resize(hint); } // the tr1 name - - // Lookup routines - iterator find(const key_type& key) const { return rep.find(key); } - - size_type count(const key_type& key) const { return rep.count(key); } - - pair<iterator, iterator> equal_range(const key_type& key) const { - return rep.equal_range(key); - } - - // Insertion routines - pair<iterator, bool> insert(const value_type& obj) { - pair<typename ht::iterator, bool> p = rep.insert(obj); - return pair<iterator, bool>(p.first, p.second); // const to non-const - } - template <class InputIterator> - void insert(InputIterator f, InputIterator l) { rep.insert(f, l); } - void insert(const_iterator f, const_iterator l) { rep.insert(f, l); } - // required for std::insert_iterator; the passed-in iterator is ignored - iterator insert(iterator, const value_type& obj) { return insert(obj).first; } - - - // Deletion and empty routines - // THESE ARE NON-STANDARD! I make you specify an "impossible" key - // value to identify deleted and empty buckets. You can change the - // deleted key as time goes on, or get rid of it entirely to be insert-only. - void set_empty_key(const key_type& key) { rep.set_empty_key(key); } - void set_deleted_key(const key_type& key) { rep.set_deleted_key(key); } - void clear_deleted_key() { rep.clear_deleted_key(); } - - // These are standard - size_type erase(const key_type& key) { return rep.erase(key); } - void erase(iterator it) { rep.erase(it); } - void erase(iterator f, iterator l) { rep.erase(f, l); } - - - // Comparison - bool operator==(const dense_hash_set& hs) const { return rep == hs.rep; } - bool operator!=(const dense_hash_set& hs) const { return rep != hs.rep; } - - - // I/O -- this is an add-on for writing metainformation to disk - bool write_metadata(FILE *fp) { return rep.write_metadata(fp); } - bool read_metadata(FILE *fp) { return rep.read_metadata(fp); } - bool write_nopointer_data(FILE *fp) { return rep.write_nopointer_data(fp); } - bool read_nopointer_data(FILE *fp) { return rep.read_nopointer_data(fp); } -}; - -template <class Val, class HashFcn, class EqualKey, class Alloc> -inline void swap(dense_hash_set<Val, HashFcn, EqualKey, Alloc>& hs1, - dense_hash_set<Val, HashFcn, EqualKey, Alloc>& hs2) { - hs1.swap(hs2); -} - -_END_GOOGLE_NAMESPACE_ - -#endif /* _DENSE_HASH_SET_H_ */ |