1 // Copyright (c) 2010, Google Inc.
2 // All rights reserved.
3 //
4 // Redistribution and use in source and binary forms, with or without
5 // modification, are permitted provided that the following conditions are
6 // met:
7 //
8 // * Redistributions of source code must retain the above copyright
9 // notice, this list of conditions and the following disclaimer.
10 // * Redistributions in binary form must reproduce the above
11 // copyright notice, this list of conditions and the following disclaimer
12 // in the documentation and/or other materials provided with the
13 // distribution.
14 // * Neither the name of Google Inc. nor the names of its
15 // contributors may be used to endorse or promote products derived from
16 // this software without specific prior written permission.
17 //
18 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29
30 // ---
31 //
32 // This implements a uniform interface for all 6 hash implementations:
33 // dense_hashtable, dense_hash_map, dense_hash_set
34 // sparse_hashtable, sparse_hash_map, sparse_hash_set
35 // This is intended to be used for testing, to provide a single routine
36 // that can easily test all 6 implementations.
37 //
38 // The main reasons to specialize are to (1) provide dummy
39 // implementations for methods that are only needed for some of the
40 // implementations (for instance, set_empty_key()), and (2) provide a
41 // uniform interface to just the keys -- for instance, we provide
42 // wrappers around the iterators that define it.key, which gives the
43 // "key" part of the bucket (*it or it->first, depending on the class).
44
45 #ifndef UTIL_GTL_HASH_TEST_INTERFACE_H_
46 #define UTIL_GTL_HASH_TEST_INTERFACE_H_
47
48 #include <sparsehash/internal/sparseconfig.h>
49 #include <functional> // for equal_to<>
50 #include <sparsehash/internal/sparsehashtable.h>
51 #include <sparsehash/sparse_hash_map>
52 #include <sparsehash/sparse_hash_set>
53 #include <sparsehash/internal/densehashtable.h>
54 #include <sparsehash/dense_hash_map>
55 #include <sparsehash/dense_hash_set>
56 #include HASH_FUN_H // for hash<>
57
58 _START_GOOGLE_NAMESPACE_
59
60 // This is the "default" interface, which just passes everything
61 // through to the underlying hashtable. You'll need to subclass it to
62 // specialize behavior for an individual hashtable.
63 template <class HT>
64 class BaseHashtableInterface {
65 public:
~BaseHashtableInterface()66 virtual ~BaseHashtableInterface() {}
67
68 typedef typename HT::key_type key_type;
69 typedef typename HT::value_type value_type;
70 typedef typename HT::hasher hasher;
71 typedef typename HT::key_equal key_equal;
72 typedef typename HT::allocator_type allocator_type;
73
74 typedef typename HT::size_type size_type;
75 typedef typename HT::difference_type difference_type;
76 typedef typename HT::pointer pointer;
77 typedef typename HT::const_pointer const_pointer;
78 typedef typename HT::reference reference;
79 typedef typename HT::const_reference const_reference;
80
81 class const_iterator;
82
83 class iterator : public HT::iterator {
84 public:
iterator()85 iterator() : parent_(NULL) { } // this allows code like "iterator it;"
iterator(typename HT::iterator it,const BaseHashtableInterface * parent)86 iterator(typename HT::iterator it,
87 const BaseHashtableInterface* parent)
88 : HT::iterator(it), parent_(parent) { }
key()89 key_type key() { return parent_->it_to_key(*this); }
90 private:
91 friend class BaseHashtableInterface::const_iterator; // for its ctor
92 const BaseHashtableInterface* parent_;
93 };
94
95 class const_iterator : public HT::const_iterator {
96 public:
const_iterator()97 const_iterator() : parent_(NULL) { }
const_iterator(typename HT::const_iterator it,const BaseHashtableInterface * parent)98 const_iterator(typename HT::const_iterator it,
99 const BaseHashtableInterface* parent)
100 : HT::const_iterator(it), parent_(parent) { }
const_iterator(typename HT::iterator it,BaseHashtableInterface * parent)101 const_iterator(typename HT::iterator it,
102 BaseHashtableInterface* parent)
103 : HT::const_iterator(it), parent_(parent) { }
104 // The parameter type here *should* just be "iterator", but MSVC
105 // gets confused by that, so I'm overly specific.
const_iterator(typename BaseHashtableInterface<HT>::iterator it)106 const_iterator(typename BaseHashtableInterface<HT>::iterator it)
107 : HT::const_iterator(it), parent_(it.parent_) { }
key()108 key_type key() { return parent_->it_to_key(*this); }
109 private:
110 const BaseHashtableInterface* parent_;
111 };
112
113 class const_local_iterator;
114
115 class local_iterator : public HT::local_iterator {
116 public:
local_iterator()117 local_iterator() : parent_(NULL) { }
local_iterator(typename HT::local_iterator it,const BaseHashtableInterface * parent)118 local_iterator(typename HT::local_iterator it,
119 const BaseHashtableInterface* parent)
120 : HT::local_iterator(it), parent_(parent) { }
key()121 key_type key() { return parent_->it_to_key(*this); }
122 private:
123 friend class BaseHashtableInterface::const_local_iterator; // for its ctor
124 const BaseHashtableInterface* parent_;
125 };
126
127 class const_local_iterator : public HT::const_local_iterator {
128 public:
const_local_iterator()129 const_local_iterator() : parent_(NULL) { }
const_local_iterator(typename HT::const_local_iterator it,const BaseHashtableInterface * parent)130 const_local_iterator(typename HT::const_local_iterator it,
131 const BaseHashtableInterface* parent)
132 : HT::const_local_iterator(it), parent_(parent) { }
const_local_iterator(typename HT::local_iterator it,BaseHashtableInterface * parent)133 const_local_iterator(typename HT::local_iterator it,
134 BaseHashtableInterface* parent)
135 : HT::const_local_iterator(it), parent_(parent) { }
const_local_iterator(local_iterator it)136 const_local_iterator(local_iterator it)
137 : HT::const_local_iterator(it), parent_(it.parent_) { }
key()138 key_type key() { return parent_->it_to_key(*this); }
139 private:
140 const BaseHashtableInterface* parent_;
141 };
142
begin()143 iterator begin() {
144 return iterator(ht_.begin(), this);
145 }
end()146 iterator end() {
147 return iterator(ht_.end(), this);
148 }
begin()149 const_iterator begin() const {
150 return const_iterator(ht_.begin(), this);
151 }
end()152 const_iterator end() const {
153 return const_iterator(ht_.end(), this);
154 }
begin(size_type i)155 local_iterator begin(size_type i) {
156 return local_iterator(ht_.begin(i), this);
157 }
end(size_type i)158 local_iterator end(size_type i) {
159 return local_iterator(ht_.end(i), this);
160 }
begin(size_type i)161 const_local_iterator begin(size_type i) const {
162 return const_local_iterator(ht_.begin(i), this);
163 }
end(size_type i)164 const_local_iterator end(size_type i) const {
165 return const_local_iterator(ht_.end(i), this);
166 }
167
hash_funct()168 hasher hash_funct() const { return ht_.hash_funct(); }
hash_function()169 hasher hash_function() const { return ht_.hash_function(); }
key_eq()170 key_equal key_eq() const { return ht_.key_eq(); }
get_allocator()171 allocator_type get_allocator() const { return ht_.get_allocator(); }
172
BaseHashtableInterface(size_type expected_max_items_in_table,const hasher & hf,const key_equal & eql,const allocator_type & alloc)173 BaseHashtableInterface(size_type expected_max_items_in_table,
174 const hasher& hf,
175 const key_equal& eql,
176 const allocator_type& alloc)
177 : ht_(expected_max_items_in_table, hf, eql, alloc) { }
178
179 // Not all ht_'s support this constructor: you should only call it
180 // from a subclass if you know your ht supports it. Otherwise call
181 // the previous constructor, followed by 'insert(f, l);'.
182 template <class InputIterator>
BaseHashtableInterface(InputIterator f,InputIterator l,size_type expected_max_items_in_table,const hasher & hf,const key_equal & eql,const allocator_type & alloc)183 BaseHashtableInterface(InputIterator f, InputIterator l,
184 size_type expected_max_items_in_table,
185 const hasher& hf,
186 const key_equal& eql,
187 const allocator_type& alloc)
188 : ht_(f, l, expected_max_items_in_table, hf, eql, alloc) {
189 }
190
191 // This is the version of the constructor used by dense_*, which
192 // requires an empty key in the constructor.
193 template <class InputIterator>
BaseHashtableInterface(InputIterator f,InputIterator l,key_type empty_k,size_type expected_max_items_in_table,const hasher & hf,const key_equal & eql,const allocator_type & alloc)194 BaseHashtableInterface(InputIterator f, InputIterator l, key_type empty_k,
195 size_type expected_max_items_in_table,
196 const hasher& hf,
197 const key_equal& eql,
198 const allocator_type& alloc)
199 : ht_(f, l, empty_k, expected_max_items_in_table, hf, eql, alloc) {
200 }
201
202 // This is the constructor appropriate for {dense,sparse}hashtable.
203 template <class ExtractKey, class SetKey>
BaseHashtableInterface(size_type expected_max_items_in_table,const hasher & hf,const key_equal & eql,const ExtractKey & ek,const SetKey & sk,const allocator_type & alloc)204 BaseHashtableInterface(size_type expected_max_items_in_table,
205 const hasher& hf,
206 const key_equal& eql,
207 const ExtractKey& ek,
208 const SetKey& sk,
209 const allocator_type& alloc)
210 : ht_(expected_max_items_in_table, hf, eql, ek, sk, alloc) { }
211
212
clear()213 void clear() { ht_.clear(); }
swap(BaseHashtableInterface & other)214 void swap(BaseHashtableInterface& other) { ht_.swap(other.ht_); }
215
216 // Only part of the API for some hashtable implementations.
clear_no_resize()217 void clear_no_resize() { clear(); }
218
size()219 size_type size() const { return ht_.size(); }
max_size()220 size_type max_size() const { return ht_.max_size(); }
empty()221 bool empty() const { return ht_.empty(); }
bucket_count()222 size_type bucket_count() const { return ht_.bucket_count(); }
max_bucket_count()223 size_type max_bucket_count() const { return ht_.max_bucket_count(); }
224
bucket_size(size_type i)225 size_type bucket_size(size_type i) const {
226 return ht_.bucket_size(i);
227 }
bucket(const key_type & key)228 size_type bucket(const key_type& key) const {
229 return ht_.bucket(key);
230 }
231
load_factor()232 float load_factor() const { return ht_.load_factor(); }
max_load_factor()233 float max_load_factor() const { return ht_.max_load_factor(); }
max_load_factor(float grow)234 void max_load_factor(float grow) { ht_.max_load_factor(grow); }
min_load_factor()235 float min_load_factor() const { return ht_.min_load_factor(); }
min_load_factor(float shrink)236 void min_load_factor(float shrink) { ht_.min_load_factor(shrink); }
set_resizing_parameters(float shrink,float grow)237 void set_resizing_parameters(float shrink, float grow) {
238 ht_.set_resizing_parameters(shrink, grow);
239 }
240
resize(size_type hint)241 void resize(size_type hint) { ht_.resize(hint); }
rehash(size_type hint)242 void rehash(size_type hint) { ht_.rehash(hint); }
243
find(const key_type & key)244 iterator find(const key_type& key) {
245 return iterator(ht_.find(key), this);
246 }
find(const key_type & key)247 const_iterator find(const key_type& key) const {
248 return const_iterator(ht_.find(key), this);
249 }
250
251 // Rather than try to implement operator[], which doesn't make much
252 // sense for set types, we implement two methods: bracket_equal and
253 // bracket_assign. By default, bracket_equal(a, b) returns true if
254 // ht[a] == b, and false otherwise. (Note that this follows
255 // operator[] semantics exactly, including inserting a if it's not
256 // already in the hashtable, before doing the equality test.) For
257 // sets, which have no operator[], b is ignored, and bracket_equal
258 // returns true if key is in the set and false otherwise.
259 // bracket_assign(a, b) is equivalent to ht[a] = b. For sets, b is
260 // ignored, and bracket_assign is equivalent to ht.insert(a).
261 template<typename AssignValue>
bracket_equal(const key_type & key,const AssignValue & expected)262 bool bracket_equal(const key_type& key, const AssignValue& expected) {
263 return ht_[key] == expected;
264 }
265
266 template<typename AssignValue>
bracket_assign(const key_type & key,const AssignValue & value)267 void bracket_assign(const key_type& key, const AssignValue& value) {
268 ht_[key] = value;
269 }
270
count(const key_type & key)271 size_type count(const key_type& key) const { return ht_.count(key); }
272
equal_range(const key_type & key)273 std::pair<iterator, iterator> equal_range(const key_type& key) {
274 std::pair<typename HT::iterator, typename HT::iterator> r
275 = ht_.equal_range(key);
276 return std::pair<iterator, iterator>(iterator(r.first, this),
277 iterator(r.second, this));
278 }
equal_range(const key_type & key)279 std::pair<const_iterator, const_iterator> equal_range(const key_type& key)
280 const {
281 std::pair<typename HT::const_iterator, typename HT::const_iterator> r
282 = ht_.equal_range(key);
283 return std::pair<const_iterator, const_iterator>(
284 const_iterator(r.first, this), const_iterator(r.second, this));
285 }
286
random_element(class ACMRandom * r)287 const_iterator random_element(class ACMRandom* r) const {
288 return const_iterator(ht_.random_element(r), this);
289 }
random_element(class ACMRandom * r)290 iterator random_element(class ACMRandom* r) {
291 return iterator(ht_.random_element(r), this);
292 }
293
insert(const value_type & obj)294 std::pair<iterator, bool> insert(const value_type& obj) {
295 std::pair<typename HT::iterator, bool> r = ht_.insert(obj);
296 return std::pair<iterator, bool>(iterator(r.first, this), r.second);
297 }
298 template <class InputIterator>
insert(InputIterator f,InputIterator l)299 void insert(InputIterator f, InputIterator l) {
300 ht_.insert(f, l);
301 }
insert(typename HT::const_iterator f,typename HT::const_iterator l)302 void insert(typename HT::const_iterator f, typename HT::const_iterator l) {
303 ht_.insert(f, l);
304 }
insert(typename HT::iterator,const value_type & obj)305 iterator insert(typename HT::iterator, const value_type& obj) {
306 return iterator(insert(obj).first, this);
307 }
308
309 // These will commonly need to be overridden by the child.
set_empty_key(const key_type & k)310 void set_empty_key(const key_type& k) { ht_.set_empty_key(k); }
clear_empty_key()311 void clear_empty_key() { ht_.clear_empty_key(); }
empty_key()312 key_type empty_key() const { return ht_.empty_key(); }
313
set_deleted_key(const key_type & k)314 void set_deleted_key(const key_type& k) { ht_.set_deleted_key(k); }
clear_deleted_key()315 void clear_deleted_key() { ht_.clear_deleted_key(); }
deleted_key()316 key_type deleted_key() const { return ht_.deleted_key(); }
317
erase(const key_type & key)318 size_type erase(const key_type& key) { return ht_.erase(key); }
erase(typename HT::iterator it)319 void erase(typename HT::iterator it) { ht_.erase(it); }
erase(typename HT::iterator f,typename HT::iterator l)320 void erase(typename HT::iterator f, typename HT::iterator l) {
321 ht_.erase(f, l);
322 }
323
324 bool operator==(const BaseHashtableInterface& other) const {
325 return ht_ == other.ht_;
326 }
327 bool operator!=(const BaseHashtableInterface& other) const {
328 return ht_ != other.ht_;
329 }
330
331 template <typename ValueSerializer, typename OUTPUT>
serialize(ValueSerializer serializer,OUTPUT * fp)332 bool serialize(ValueSerializer serializer, OUTPUT *fp) {
333 return ht_.serialize(serializer, fp);
334 }
335 template <typename ValueSerializer, typename INPUT>
unserialize(ValueSerializer serializer,INPUT * fp)336 bool unserialize(ValueSerializer serializer, INPUT *fp) {
337 return ht_.unserialize(serializer, fp);
338 }
339
340 template <typename OUTPUT>
write_metadata(OUTPUT * fp)341 bool write_metadata(OUTPUT *fp) {
342 return ht_.write_metadata(fp);
343 }
344 template <typename INPUT>
read_metadata(INPUT * fp)345 bool read_metadata(INPUT *fp) {
346 return ht_.read_metadata(fp);
347 }
348 template <typename OUTPUT>
write_nopointer_data(OUTPUT * fp)349 bool write_nopointer_data(OUTPUT *fp) {
350 return ht_.write_nopointer_data(fp);
351 }
352 template <typename INPUT>
read_nopointer_data(INPUT * fp)353 bool read_nopointer_data(INPUT *fp) {
354 return ht_.read_nopointer_data(fp);
355 }
356
357 // low-level stats
num_table_copies()358 int num_table_copies() const { return ht_.num_table_copies(); }
359
360 // Not part of the hashtable API, but is provided to make testing easier.
361 virtual key_type get_key(const value_type& value) const = 0;
362 // All subclasses should define get_data(value_type) as well. I don't
363 // provide an abstract-virtual definition here, because the return type
364 // differs between subclasses (not all subclasses define data_type).
365 //virtual data_type get_data(const value_type& value) const = 0;
366 //virtual data_type default_data() const = 0;
367
368 // These allow introspection into the interface. "Supports" means
369 // that the implementation of this functionality isn't a noop.
370 virtual bool supports_clear_no_resize() const = 0;
371 virtual bool supports_empty_key() const = 0;
372 virtual bool supports_deleted_key() const = 0;
373 virtual bool supports_brackets() const = 0; // has a 'real' operator[]
374 virtual bool supports_readwrite() const = 0;
375 virtual bool supports_num_table_copies() const = 0;
376 virtual bool supports_serialization() const = 0;
377
378 protected:
379 HT ht_;
380
381 // These are what subclasses have to define to get class-specific behavior
382 virtual key_type it_to_key(const iterator& it) const = 0;
383 virtual key_type it_to_key(const const_iterator& it) const = 0;
384 virtual key_type it_to_key(const local_iterator& it) const = 0;
385 virtual key_type it_to_key(const const_local_iterator& it) const = 0;
386 };
387
388 // ---------------------------------------------------------------------
389
390 template <class Key, class T,
391 class HashFcn = SPARSEHASH_HASH<Key>,
392 class EqualKey = std::equal_to<Key>,
393 class Alloc = libc_allocator_with_realloc<std::pair<const Key, T> > >
394 class HashtableInterface_SparseHashMap
395 : public BaseHashtableInterface< sparse_hash_map<Key, T, HashFcn,
396 EqualKey, Alloc> > {
397 private:
398 typedef sparse_hash_map<Key, T, HashFcn, EqualKey, Alloc> ht;
399 typedef BaseHashtableInterface<ht> p; // parent
400
401 public:
402 explicit HashtableInterface_SparseHashMap(
403 typename p::size_type expected_max_items = 0,
404 const typename p::hasher& hf = typename p::hasher(),
405 const typename p::key_equal& eql = typename p::key_equal(),
406 const typename p::allocator_type& alloc = typename p::allocator_type())
407 : BaseHashtableInterface<ht>(expected_max_items, hf, eql, alloc) { }
408
409 template <class InputIterator>
410 HashtableInterface_SparseHashMap(
411 InputIterator f, InputIterator l,
412 typename p::size_type expected_max_items = 0,
413 const typename p::hasher& hf = typename p::hasher(),
414 const typename p::key_equal& eql = typename p::key_equal(),
415 const typename p::allocator_type& alloc = typename p::allocator_type())
416 : BaseHashtableInterface<ht>(f, l, expected_max_items, hf, eql, alloc) { }
417
get_key(const typename p::value_type & value)418 typename p::key_type get_key(const typename p::value_type& value) const {
419 return value.first;
420 }
get_data(const typename p::value_type & value)421 typename ht::data_type get_data(const typename p::value_type& value) const {
422 return value.second;
423 }
default_data()424 typename ht::data_type default_data() const {
425 return typename ht::data_type();
426 }
427
supports_clear_no_resize()428 bool supports_clear_no_resize() const { return false; }
supports_empty_key()429 bool supports_empty_key() const { return false; }
supports_deleted_key()430 bool supports_deleted_key() const { return true; }
supports_brackets()431 bool supports_brackets() const { return true; }
supports_readwrite()432 bool supports_readwrite() const { return true; }
supports_num_table_copies()433 bool supports_num_table_copies() const { return false; }
supports_serialization()434 bool supports_serialization() const { return true; }
435
set_empty_key(const typename p::key_type &)436 void set_empty_key(const typename p::key_type&) { }
clear_empty_key()437 void clear_empty_key() { }
empty_key()438 typename p::key_type empty_key() const { return typename p::key_type(); }
439
num_table_copies()440 int num_table_copies() const { return 0; }
441
442 typedef typename ht::NopointerSerializer NopointerSerializer;
443
444 protected:
445 template <class K2, class T2, class H2, class E2, class A2>
446 friend void swap(HashtableInterface_SparseHashMap<K2,T2,H2,E2,A2>& a,
447 HashtableInterface_SparseHashMap<K2,T2,H2,E2,A2>& b);
448
it_to_key(const typename p::iterator & it)449 typename p::key_type it_to_key(const typename p::iterator& it) const {
450 return it->first;
451 }
it_to_key(const typename p::const_iterator & it)452 typename p::key_type it_to_key(const typename p::const_iterator& it) const {
453 return it->first;
454 }
it_to_key(const typename p::local_iterator & it)455 typename p::key_type it_to_key(const typename p::local_iterator& it) const {
456 return it->first;
457 }
it_to_key(const typename p::const_local_iterator & it)458 typename p::key_type it_to_key(const typename p::const_local_iterator& it)
459 const {
460 return it->first;
461 }
462 };
463
464 template <class K, class T, class H, class E, class A>
swap(HashtableInterface_SparseHashMap<K,T,H,E,A> & a,HashtableInterface_SparseHashMap<K,T,H,E,A> & b)465 void swap(HashtableInterface_SparseHashMap<K,T,H,E,A>& a,
466 HashtableInterface_SparseHashMap<K,T,H,E,A>& b) {
467 swap(a.ht_, b.ht_);
468 }
469
470 // ---------------------------------------------------------------------
471
472 template <class Value,
473 class HashFcn = SPARSEHASH_HASH<Value>,
474 class EqualKey = std::equal_to<Value>,
475 class Alloc = libc_allocator_with_realloc<Value> >
476 class HashtableInterface_SparseHashSet
477 : public BaseHashtableInterface< sparse_hash_set<Value, HashFcn,
478 EqualKey, Alloc> > {
479 private:
480 typedef sparse_hash_set<Value, HashFcn, EqualKey, Alloc> ht;
481 typedef BaseHashtableInterface<ht> p; // parent
482
483 public:
484 // Bizarrely, MSVC 8.0 has trouble with the (perfectly fine)
485 // typename's in this constructor, and this constructor alone, out
486 // of all the ones in the file. So for MSVC, we take some typenames
487 // out, which is technically invalid C++, but MSVC doesn't seem to
488 // mind.
489 #ifdef _MSC_VER
490 explicit HashtableInterface_SparseHashSet(
491 typename p::size_type expected_max_items = 0,
492 const typename p::hasher& hf = p::hasher(),
493 const typename p::key_equal& eql = p::key_equal(),
494 const typename p::allocator_type& alloc = p::allocator_type())
495 : BaseHashtableInterface<ht>(expected_max_items, hf, eql, alloc) { }
496 #else
497 explicit HashtableInterface_SparseHashSet(
498 typename p::size_type expected_max_items = 0,
499 const typename p::hasher& hf = typename p::hasher(),
500 const typename p::key_equal& eql = typename p::key_equal(),
501 const typename p::allocator_type& alloc = typename p::allocator_type())
502 : BaseHashtableInterface<ht>(expected_max_items, hf, eql, alloc) { }
503 #endif
504
505 template <class InputIterator>
506 HashtableInterface_SparseHashSet(
507 InputIterator f, InputIterator l,
508 typename p::size_type expected_max_items = 0,
509 const typename p::hasher& hf = typename p::hasher(),
510 const typename p::key_equal& eql = typename p::key_equal(),
511 const typename p::allocator_type& alloc = typename p::allocator_type())
512 : BaseHashtableInterface<ht>(f, l, expected_max_items, hf, eql, alloc) { }
513
514 template<typename AssignValue>
bracket_equal(const typename p::key_type & key,const AssignValue &)515 bool bracket_equal(const typename p::key_type& key, const AssignValue&) {
516 return this->ht_.find(key) != this->ht_.end();
517 }
518
519 template<typename AssignValue>
bracket_assign(const typename p::key_type & key,const AssignValue &)520 void bracket_assign(const typename p::key_type& key, const AssignValue&) {
521 this->ht_.insert(key);
522 }
523
get_key(const typename p::value_type & value)524 typename p::key_type get_key(const typename p::value_type& value) const {
525 return value;
526 }
527 // For sets, the only 'data' is that an item is actually inserted.
get_data(const typename p::value_type &)528 bool get_data(const typename p::value_type&) const {
529 return true;
530 }
default_data()531 bool default_data() const {
532 return true;
533 }
534
supports_clear_no_resize()535 bool supports_clear_no_resize() const { return false; }
supports_empty_key()536 bool supports_empty_key() const { return false; }
supports_deleted_key()537 bool supports_deleted_key() const { return true; }
supports_brackets()538 bool supports_brackets() const { return false; }
supports_readwrite()539 bool supports_readwrite() const { return true; }
supports_num_table_copies()540 bool supports_num_table_copies() const { return false; }
supports_serialization()541 bool supports_serialization() const { return true; }
542
set_empty_key(const typename p::key_type &)543 void set_empty_key(const typename p::key_type&) { }
clear_empty_key()544 void clear_empty_key() { }
empty_key()545 typename p::key_type empty_key() const { return typename p::key_type(); }
546
num_table_copies()547 int num_table_copies() const { return 0; }
548
549 typedef typename ht::NopointerSerializer NopointerSerializer;
550
551 protected:
552 template <class K2, class H2, class E2, class A2>
553 friend void swap(HashtableInterface_SparseHashSet<K2,H2,E2,A2>& a,
554 HashtableInterface_SparseHashSet<K2,H2,E2,A2>& b);
555
it_to_key(const typename p::iterator & it)556 typename p::key_type it_to_key(const typename p::iterator& it) const {
557 return *it;
558 }
it_to_key(const typename p::const_iterator & it)559 typename p::key_type it_to_key(const typename p::const_iterator& it) const {
560 return *it;
561 }
it_to_key(const typename p::local_iterator & it)562 typename p::key_type it_to_key(const typename p::local_iterator& it) const {
563 return *it;
564 }
it_to_key(const typename p::const_local_iterator & it)565 typename p::key_type it_to_key(const typename p::const_local_iterator& it)
566 const {
567 return *it;
568 }
569 };
570
571 template <class K, class H, class E, class A>
swap(HashtableInterface_SparseHashSet<K,H,E,A> & a,HashtableInterface_SparseHashSet<K,H,E,A> & b)572 void swap(HashtableInterface_SparseHashSet<K,H,E,A>& a,
573 HashtableInterface_SparseHashSet<K,H,E,A>& b) {
574 swap(a.ht_, b.ht_);
575 }
576
577 // ---------------------------------------------------------------------
578
579 template <class Value, class Key, class HashFcn, class ExtractKey,
580 class SetKey, class EqualKey, class Alloc>
581 class HashtableInterface_SparseHashtable
582 : public BaseHashtableInterface< sparse_hashtable<Value, Key, HashFcn,
583 ExtractKey, SetKey,
584 EqualKey, Alloc> > {
585 private:
586 typedef sparse_hashtable<Value, Key, HashFcn, ExtractKey, SetKey,
587 EqualKey, Alloc> ht;
588 typedef BaseHashtableInterface<ht> p; // parent
589
590 public:
591 explicit HashtableInterface_SparseHashtable(
592 typename p::size_type expected_max_items = 0,
593 const typename p::hasher& hf = typename p::hasher(),
594 const typename p::key_equal& eql = typename p::key_equal(),
595 const typename p::allocator_type& alloc = typename p::allocator_type())
596 : BaseHashtableInterface<ht>(expected_max_items, hf, eql,
597 ExtractKey(), SetKey(), alloc) { }
598
599 template <class InputIterator>
600 HashtableInterface_SparseHashtable(
601 InputIterator f, InputIterator l,
602 typename p::size_type expected_max_items = 0,
603 const typename p::hasher& hf = typename p::hasher(),
604 const typename p::key_equal& eql = typename p::key_equal(),
605 const typename p::allocator_type& alloc = typename p::allocator_type())
606 : BaseHashtableInterface<ht>(expected_max_items, hf, eql,
607 ExtractKey(), SetKey(), alloc) {
608 this->insert(f, l);
609 }
610
max_load_factor()611 float max_load_factor() const {
612 float shrink, grow;
613 this->ht_.get_resizing_parameters(&shrink, &grow);
614 return grow;
615 }
max_load_factor(float new_grow)616 void max_load_factor(float new_grow) {
617 float shrink, grow;
618 this->ht_.get_resizing_parameters(&shrink, &grow);
619 this->ht_.set_resizing_parameters(shrink, new_grow);
620 }
min_load_factor()621 float min_load_factor() const {
622 float shrink, grow;
623 this->ht_.get_resizing_parameters(&shrink, &grow);
624 return shrink;
625 }
min_load_factor(float new_shrink)626 void min_load_factor(float new_shrink) {
627 float shrink, grow;
628 this->ht_.get_resizing_parameters(&shrink, &grow);
629 this->ht_.set_resizing_parameters(new_shrink, grow);
630 }
631
632 template<typename AssignValue>
bracket_equal(const typename p::key_type &,const AssignValue &)633 bool bracket_equal(const typename p::key_type&, const AssignValue&) {
634 return false;
635 }
636
637 template<typename AssignValue>
bracket_assign(const typename p::key_type &,const AssignValue &)638 void bracket_assign(const typename p::key_type&, const AssignValue&) {
639 }
640
get_key(const typename p::value_type & value)641 typename p::key_type get_key(const typename p::value_type& value) const {
642 return extract_key(value);
643 }
get_data(const typename p::value_type & value)644 typename p::value_type get_data(const typename p::value_type& value) const {
645 return value;
646 }
default_data()647 typename p::value_type default_data() const {
648 return typename p::value_type();
649 }
650
supports_clear_no_resize()651 bool supports_clear_no_resize() const { return false; }
supports_empty_key()652 bool supports_empty_key() const { return false; }
supports_deleted_key()653 bool supports_deleted_key() const { return true; }
supports_brackets()654 bool supports_brackets() const { return false; }
supports_readwrite()655 bool supports_readwrite() const { return true; }
supports_num_table_copies()656 bool supports_num_table_copies() const { return true; }
supports_serialization()657 bool supports_serialization() const { return true; }
658
set_empty_key(const typename p::key_type &)659 void set_empty_key(const typename p::key_type&) { }
clear_empty_key()660 void clear_empty_key() { }
empty_key()661 typename p::key_type empty_key() const { return typename p::key_type(); }
662
663 // These tr1 names aren't defined for sparse_hashtable.
hash_function()664 typename p::hasher hash_function() { return this->hash_funct(); }
rehash(typename p::size_type hint)665 void rehash(typename p::size_type hint) { this->resize(hint); }
666
667 // TODO(csilvers): also support/test destructive_begin()/destructive_end()?
668
669 typedef typename ht::NopointerSerializer NopointerSerializer;
670
671 protected:
672 template <class V2, class K2, class HF2, class EK2, class SK2, class Eq2,
673 class A2>
674 friend void swap(
675 HashtableInterface_SparseHashtable<V2,K2,HF2,EK2,SK2,Eq2,A2>& a,
676 HashtableInterface_SparseHashtable<V2,K2,HF2,EK2,SK2,Eq2,A2>& b);
677
it_to_key(const typename p::iterator & it)678 typename p::key_type it_to_key(const typename p::iterator& it) const {
679 return extract_key(*it);
680 }
it_to_key(const typename p::const_iterator & it)681 typename p::key_type it_to_key(const typename p::const_iterator& it) const {
682 return extract_key(*it);
683 }
it_to_key(const typename p::local_iterator & it)684 typename p::key_type it_to_key(const typename p::local_iterator& it) const {
685 return extract_key(*it);
686 }
it_to_key(const typename p::const_local_iterator & it)687 typename p::key_type it_to_key(const typename p::const_local_iterator& it)
688 const {
689 return extract_key(*it);
690 }
691
692 private:
693 ExtractKey extract_key;
694 };
695
696 template <class V, class K, class HF, class EK, class SK, class Eq, class A>
swap(HashtableInterface_SparseHashtable<V,K,HF,EK,SK,Eq,A> & a,HashtableInterface_SparseHashtable<V,K,HF,EK,SK,Eq,A> & b)697 void swap(HashtableInterface_SparseHashtable<V,K,HF,EK,SK,Eq,A>& a,
698 HashtableInterface_SparseHashtable<V,K,HF,EK,SK,Eq,A>& b) {
699 swap(a.ht_, b.ht_);
700 }
701
702 // ---------------------------------------------------------------------
703
704 // Unlike dense_hash_map, the wrapper class takes an extra template
705 // value saying what the empty key is.
706
707 template <class Key, class T, const Key& EMPTY_KEY,
708 class HashFcn = SPARSEHASH_HASH<Key>,
709 class EqualKey = std::equal_to<Key>,
710 class Alloc = libc_allocator_with_realloc<std::pair<const Key, T> > >
711 class HashtableInterface_DenseHashMap
712 : public BaseHashtableInterface< dense_hash_map<Key, T, HashFcn,
713 EqualKey, Alloc> > {
714 private:
715 typedef dense_hash_map<Key, T, HashFcn, EqualKey, Alloc> ht;
716 typedef BaseHashtableInterface<ht> p; // parent
717
718 public:
719 explicit HashtableInterface_DenseHashMap(
720 typename p::size_type expected_max_items = 0,
721 const typename p::hasher& hf = typename p::hasher(),
722 const typename p::key_equal& eql = typename p::key_equal(),
723 const typename p::allocator_type& alloc = typename p::allocator_type())
724 : BaseHashtableInterface<ht>(expected_max_items, hf, eql, alloc) {
725 this->set_empty_key(EMPTY_KEY);
726 }
727
728 template <class InputIterator>
729 HashtableInterface_DenseHashMap(
730 InputIterator f, InputIterator l,
731 typename p::size_type expected_max_items = 0,
732 const typename p::hasher& hf = typename p::hasher(),
733 const typename p::key_equal& eql = typename p::key_equal(),
734 const typename p::allocator_type& alloc = typename p::allocator_type())
735 : BaseHashtableInterface<ht>(f, l, EMPTY_KEY,
736 expected_max_items, hf, eql, alloc) {
737 }
738
clear_no_resize()739 void clear_no_resize() { this->ht_.clear_no_resize(); }
740
get_key(const typename p::value_type & value)741 typename p::key_type get_key(const typename p::value_type& value) const {
742 return value.first;
743 }
get_data(const typename p::value_type & value)744 typename ht::data_type get_data(const typename p::value_type& value) const {
745 return value.second;
746 }
default_data()747 typename ht::data_type default_data() const {
748 return typename ht::data_type();
749 }
750
supports_clear_no_resize()751 bool supports_clear_no_resize() const { return true; }
supports_empty_key()752 bool supports_empty_key() const { return true; }
supports_deleted_key()753 bool supports_deleted_key() const { return true; }
supports_brackets()754 bool supports_brackets() const { return true; }
supports_readwrite()755 bool supports_readwrite() const { return false; }
supports_num_table_copies()756 bool supports_num_table_copies() const { return false; }
supports_serialization()757 bool supports_serialization() const { return true; }
758
759 typedef typename ht::NopointerSerializer NopointerSerializer;
write_metadata(OUTPUT *)760 template <typename OUTPUT> bool write_metadata(OUTPUT *) { return false; }
read_metadata(INPUT *)761 template <typename INPUT> bool read_metadata(INPUT *) { return false; }
write_nopointer_data(OUTPUT *)762 template <typename OUTPUT> bool write_nopointer_data(OUTPUT *) {
763 return false;
764 }
read_nopointer_data(INPUT *)765 template <typename INPUT> bool read_nopointer_data(INPUT *) {
766 return false;
767 }
num_table_copies()768 int num_table_copies() const { return 0; }
769
770 protected:
771 template <class K2, class T2, const K2& Empty2, class H2, class E2, class A2>
772 friend void swap(HashtableInterface_DenseHashMap<K2,T2,Empty2,H2,E2,A2>& a,
773 HashtableInterface_DenseHashMap<K2,T2,Empty2,H2,E2,A2>& b);
774
it_to_key(const typename p::iterator & it)775 typename p::key_type it_to_key(const typename p::iterator& it) const {
776 return it->first;
777 }
it_to_key(const typename p::const_iterator & it)778 typename p::key_type it_to_key(const typename p::const_iterator& it) const {
779 return it->first;
780 }
it_to_key(const typename p::local_iterator & it)781 typename p::key_type it_to_key(const typename p::local_iterator& it) const {
782 return it->first;
783 }
it_to_key(const typename p::const_local_iterator & it)784 typename p::key_type it_to_key(const typename p::const_local_iterator& it)
785 const {
786 return it->first;
787 }
788 };
789
790 template <class K, class T, const K& Empty, class H, class E, class A>
swap(HashtableInterface_DenseHashMap<K,T,Empty,H,E,A> & a,HashtableInterface_DenseHashMap<K,T,Empty,H,E,A> & b)791 void swap(HashtableInterface_DenseHashMap<K,T,Empty,H,E,A>& a,
792 HashtableInterface_DenseHashMap<K,T,Empty,H,E,A>& b) {
793 swap(a.ht_, b.ht_);
794 }
795
796 // ---------------------------------------------------------------------
797
798 // Unlike dense_hash_set, the wrapper class takes an extra template
799 // value saying what the empty key is.
800
801 template <class Value, const Value& EMPTY_KEY,
802 class HashFcn = SPARSEHASH_HASH<Value>,
803 class EqualKey = std::equal_to<Value>,
804 class Alloc = libc_allocator_with_realloc<Value> >
805 class HashtableInterface_DenseHashSet
806 : public BaseHashtableInterface< dense_hash_set<Value, HashFcn,
807 EqualKey, Alloc> > {
808 private:
809 typedef dense_hash_set<Value, HashFcn, EqualKey, Alloc> ht;
810 typedef BaseHashtableInterface<ht> p; // parent
811
812 public:
813 explicit HashtableInterface_DenseHashSet(
814 typename p::size_type expected_max_items = 0,
815 const typename p::hasher& hf = typename p::hasher(),
816 const typename p::key_equal& eql = typename p::key_equal(),
817 const typename p::allocator_type& alloc = typename p::allocator_type())
818 : BaseHashtableInterface<ht>(expected_max_items, hf, eql, alloc) {
819 this->set_empty_key(EMPTY_KEY);
820 }
821
822 template <class InputIterator>
823 HashtableInterface_DenseHashSet(
824 InputIterator f, InputIterator l,
825 typename p::size_type expected_max_items = 0,
826 const typename p::hasher& hf = typename p::hasher(),
827 const typename p::key_equal& eql = typename p::key_equal(),
828 const typename p::allocator_type& alloc = typename p::allocator_type())
829 : BaseHashtableInterface<ht>(f, l, EMPTY_KEY,
830 expected_max_items, hf, eql, alloc) {
831 }
832
clear_no_resize()833 void clear_no_resize() { this->ht_.clear_no_resize(); }
834
835 template<typename AssignValue>
bracket_equal(const typename p::key_type & key,const AssignValue &)836 bool bracket_equal(const typename p::key_type& key, const AssignValue&) {
837 return this->ht_.find(key) != this->ht_.end();
838 }
839
840 template<typename AssignValue>
bracket_assign(const typename p::key_type & key,const AssignValue &)841 void bracket_assign(const typename p::key_type& key, const AssignValue&) {
842 this->ht_.insert(key);
843 }
844
get_key(const typename p::value_type & value)845 typename p::key_type get_key(const typename p::value_type& value) const {
846 return value;
847 }
get_data(const typename p::value_type &)848 bool get_data(const typename p::value_type&) const {
849 return true;
850 }
default_data()851 bool default_data() const {
852 return true;
853 }
854
supports_clear_no_resize()855 bool supports_clear_no_resize() const { return true; }
supports_empty_key()856 bool supports_empty_key() const { return true; }
supports_deleted_key()857 bool supports_deleted_key() const { return true; }
supports_brackets()858 bool supports_brackets() const { return false; }
supports_readwrite()859 bool supports_readwrite() const { return false; }
supports_num_table_copies()860 bool supports_num_table_copies() const { return false; }
supports_serialization()861 bool supports_serialization() const { return true; }
862
863 typedef typename ht::NopointerSerializer NopointerSerializer;
write_metadata(OUTPUT *)864 template <typename OUTPUT> bool write_metadata(OUTPUT *) { return false; }
read_metadata(INPUT *)865 template <typename INPUT> bool read_metadata(INPUT *) { return false; }
write_nopointer_data(OUTPUT *)866 template <typename OUTPUT> bool write_nopointer_data(OUTPUT *) {
867 return false;
868 }
read_nopointer_data(INPUT *)869 template <typename INPUT> bool read_nopointer_data(INPUT *) {
870 return false;
871 }
num_table_copies()872 int num_table_copies() const { return 0; }
873
874 protected:
875 template <class K2, const K2& Empty2, class H2, class E2, class A2>
876 friend void swap(HashtableInterface_DenseHashSet<K2,Empty2,H2,E2,A2>& a,
877 HashtableInterface_DenseHashSet<K2,Empty2,H2,E2,A2>& b);
878
it_to_key(const typename p::iterator & it)879 typename p::key_type it_to_key(const typename p::iterator& it) const {
880 return *it;
881 }
it_to_key(const typename p::const_iterator & it)882 typename p::key_type it_to_key(const typename p::const_iterator& it) const {
883 return *it;
884 }
it_to_key(const typename p::local_iterator & it)885 typename p::key_type it_to_key(const typename p::local_iterator& it) const {
886 return *it;
887 }
it_to_key(const typename p::const_local_iterator & it)888 typename p::key_type it_to_key(const typename p::const_local_iterator& it)
889 const {
890 return *it;
891 }
892 };
893
894 template <class K, const K& Empty, class H, class E, class A>
swap(HashtableInterface_DenseHashSet<K,Empty,H,E,A> & a,HashtableInterface_DenseHashSet<K,Empty,H,E,A> & b)895 void swap(HashtableInterface_DenseHashSet<K,Empty,H,E,A>& a,
896 HashtableInterface_DenseHashSet<K,Empty,H,E,A>& b) {
897 swap(a.ht_, b.ht_);
898 }
899
900 // ---------------------------------------------------------------------
901
902 // Unlike dense_hashtable, the wrapper class takes an extra template
903 // value saying what the empty key is.
904
905 template <class Value, class Key, const Key& EMPTY_KEY, class HashFcn,
906 class ExtractKey, class SetKey, class EqualKey, class Alloc>
907 class HashtableInterface_DenseHashtable
908 : public BaseHashtableInterface< dense_hashtable<Value, Key, HashFcn,
909 ExtractKey, SetKey,
910 EqualKey, Alloc> > {
911 private:
912 typedef dense_hashtable<Value, Key, HashFcn, ExtractKey, SetKey,
913 EqualKey, Alloc> ht;
914 typedef BaseHashtableInterface<ht> p; // parent
915
916 public:
917 explicit HashtableInterface_DenseHashtable(
918 typename p::size_type expected_max_items = 0,
919 const typename p::hasher& hf = typename p::hasher(),
920 const typename p::key_equal& eql = typename p::key_equal(),
921 const typename p::allocator_type& alloc = typename p::allocator_type())
922 : BaseHashtableInterface<ht>(expected_max_items, hf, eql,
923 ExtractKey(), SetKey(), alloc) {
924 this->set_empty_key(EMPTY_KEY);
925 }
926
927 template <class InputIterator>
928 HashtableInterface_DenseHashtable(
929 InputIterator f, InputIterator l,
930 typename p::size_type expected_max_items = 0,
931 const typename p::hasher& hf = typename p::hasher(),
932 const typename p::key_equal& eql = typename p::key_equal(),
933 const typename p::allocator_type& alloc = typename p::allocator_type())
934 : BaseHashtableInterface<ht>(expected_max_items, hf, eql,
935 ExtractKey(), SetKey(), alloc) {
936 this->set_empty_key(EMPTY_KEY);
937 this->insert(f, l);
938 }
939
clear_no_resize()940 void clear_no_resize() { this->ht_.clear_no_resize(); }
941
max_load_factor()942 float max_load_factor() const {
943 float shrink, grow;
944 this->ht_.get_resizing_parameters(&shrink, &grow);
945 return grow;
946 }
max_load_factor(float new_grow)947 void max_load_factor(float new_grow) {
948 float shrink, grow;
949 this->ht_.get_resizing_parameters(&shrink, &grow);
950 this->ht_.set_resizing_parameters(shrink, new_grow);
951 }
min_load_factor()952 float min_load_factor() const {
953 float shrink, grow;
954 this->ht_.get_resizing_parameters(&shrink, &grow);
955 return shrink;
956 }
min_load_factor(float new_shrink)957 void min_load_factor(float new_shrink) {
958 float shrink, grow;
959 this->ht_.get_resizing_parameters(&shrink, &grow);
960 this->ht_.set_resizing_parameters(new_shrink, grow);
961 }
962
963 template<typename AssignValue>
bracket_equal(const typename p::key_type &,const AssignValue &)964 bool bracket_equal(const typename p::key_type&, const AssignValue&) {
965 return false;
966 }
967
968 template<typename AssignValue>
bracket_assign(const typename p::key_type &,const AssignValue &)969 void bracket_assign(const typename p::key_type&, const AssignValue&) {
970 }
971
get_key(const typename p::value_type & value)972 typename p::key_type get_key(const typename p::value_type& value) const {
973 return extract_key(value);
974 }
get_data(const typename p::value_type & value)975 typename p::value_type get_data(const typename p::value_type& value) const {
976 return value;
977 }
default_data()978 typename p::value_type default_data() const {
979 return typename p::value_type();
980 }
981
supports_clear_no_resize()982 bool supports_clear_no_resize() const { return true; }
supports_empty_key()983 bool supports_empty_key() const { return true; }
supports_deleted_key()984 bool supports_deleted_key() const { return true; }
supports_brackets()985 bool supports_brackets() const { return false; }
supports_readwrite()986 bool supports_readwrite() const { return false; }
supports_num_table_copies()987 bool supports_num_table_copies() const { return true; }
supports_serialization()988 bool supports_serialization() const { return true; }
989
990 typedef typename ht::NopointerSerializer NopointerSerializer;
write_metadata(OUTPUT *)991 template <typename OUTPUT> bool write_metadata(OUTPUT *) { return false; }
read_metadata(INPUT *)992 template <typename INPUT> bool read_metadata(INPUT *) { return false; }
write_nopointer_data(OUTPUT *)993 template <typename OUTPUT> bool write_nopointer_data(OUTPUT *) {
994 return false;
995 }
read_nopointer_data(INPUT *)996 template <typename INPUT> bool read_nopointer_data(INPUT *) {
997 return false;
998 }
999
1000 // These tr1 names aren't defined for dense_hashtable.
hash_function()1001 typename p::hasher hash_function() { return this->hash_funct(); }
rehash(typename p::size_type hint)1002 void rehash(typename p::size_type hint) { this->resize(hint); }
1003
1004 protected:
1005 template <class V2, class K2, const K2& Empty2,
1006 class HF2, class EK2, class SK2, class Eq2, class A2>
1007 friend void swap(
1008 HashtableInterface_DenseHashtable<V2,K2,Empty2,HF2,EK2,SK2,Eq2,A2>& a,
1009 HashtableInterface_DenseHashtable<V2,K2,Empty2,HF2,EK2,SK2,Eq2,A2>& b);
1010
it_to_key(const typename p::iterator & it)1011 typename p::key_type it_to_key(const typename p::iterator& it) const {
1012 return extract_key(*it);
1013 }
it_to_key(const typename p::const_iterator & it)1014 typename p::key_type it_to_key(const typename p::const_iterator& it) const {
1015 return extract_key(*it);
1016 }
it_to_key(const typename p::local_iterator & it)1017 typename p::key_type it_to_key(const typename p::local_iterator& it) const {
1018 return extract_key(*it);
1019 }
it_to_key(const typename p::const_local_iterator & it)1020 typename p::key_type it_to_key(const typename p::const_local_iterator& it)
1021 const {
1022 return extract_key(*it);
1023 }
1024
1025 private:
1026 ExtractKey extract_key;
1027 };
1028
1029 template <class V, class K, const K& Empty,
1030 class HF, class EK, class SK, class Eq, class A>
swap(HashtableInterface_DenseHashtable<V,K,Empty,HF,EK,SK,Eq,A> & a,HashtableInterface_DenseHashtable<V,K,Empty,HF,EK,SK,Eq,A> & b)1031 void swap(HashtableInterface_DenseHashtable<V,K,Empty,HF,EK,SK,Eq,A>& a,
1032 HashtableInterface_DenseHashtable<V,K,Empty,HF,EK,SK,Eq,A>& b) {
1033 swap(a.ht_, b.ht_);
1034 }
1035
1036 _END_GOOGLE_NAMESPACE_
1037
1038 #endif // UTIL_GTL_HASH_TEST_INTERFACE_H_
1039