sparsehash/dense_hash_map

filter: Statementstmt 0.0% 0 / 3 Branchbran 0.0% 0 / 2 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 0.0% 0 / 5 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« fastq-lib.cpp ↑ Summary sparsehash/internal/densehashtable.h »
1 // Copyright (c) 2005, 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 is just a very thin wrapper over densehashtable.h, just
33 // like sgi stl's stl_hash_map is a very thin wrapper over
34 // stl_hashtable. The major thing we define is operator[], because
35 // we have a concept of a data_type which stl_hashtable doesn't
36 // (it only has a key and a value).
37 //
38 // NOTE: this is exactly like sparse_hash_map.h, with the word
39 // "sparse" replaced by "dense", except for the addition of
40 // set_empty_key().
41 //
42 // YOU MUST CALL SET_EMPTY_KEY() IMMEDIATELY AFTER CONSTRUCTION.
43 //
44 // Otherwise your program will die in mysterious ways. (Note if you
45 // use the constructor that takes an InputIterator range, you pass in
46 // the empty key in the constructor, rather than after. As a result,
47 // this constructor differs from the standard STL version.)
48 //
49 // In other respects, we adhere mostly to the STL semantics for
50 // hash-map. One important exception is that insert() may invalidate
51 // iterators entirely -- STL semantics are that insert() may reorder
52 // iterators, but they all still refer to something valid in the
53 // hashtable. Not so for us. Likewise, insert() may invalidate
54 // pointers into the hashtable. (Whether insert invalidates iterators
55 // and pointers depends on whether it results in a hashtable resize).
56 // On the plus side, delete() doesn't invalidate iterators or pointers
57 // at all, or even change the ordering of elements.
58 //
59 // Here are a few "power user" tips:
60 //
61 // 1) set_deleted_key():
62 // If you want to use erase() you *must* call set_deleted_key(),
63 // in addition to set_empty_key(), after construction.
64 // The deleted and empty keys must differ.
65 //
66 // 2) resize(0):
67 // When an item is deleted, its memory isn't freed right
68 // away. This allows you to iterate over a hashtable,
69 // and call erase(), without invalidating the iterator.
70 // To force the memory to be freed, call resize(0).
71 // For tr1 compatibility, this can also be called as rehash(0).
72 //
73 // 3) min_load_factor(0.0)
74 // Setting the minimum load factor to 0.0 guarantees that
75 // the hash table will never shrink.
76 //
77 // Roughly speaking:
78 // (1) dense_hash_map: fastest, uses the most memory unless entries are small
79 // (2) sparse_hash_map: slowest, uses the least memory
80 // (3) hash_map / unordered_map (STL): in the middle
81 //
82 // Typically I use sparse_hash_map when I care about space and/or when
83 // I need to save the hashtable on disk. I use hash_map otherwise. I
84 // don't personally use dense_hash_set ever; some people use it for
85 // small sets with lots of lookups.
86 //
87 // - dense_hash_map has, typically, about 78% memory overhead (if your
88 // data takes up X bytes, the hash_map uses .78X more bytes in overhead).
89 // - sparse_hash_map has about 4 bits overhead per entry.
90 // - sparse_hash_map can be 3-7 times slower than the others for lookup and,
91 // especially, inserts. See time_hash_map.cc for details.
92 //
93 // See /usr/(local/)?doc/sparsehash-*/dense_hash_map.html
94 // for information about how to use this class.
95  
96 #ifndef _DENSE_HASH_MAP_H_
97 #define _DENSE_HASH_MAP_H_
98  
99 #include <sparsehash/internal/sparseconfig.h>
100 #include <algorithm> // needed by stl_alloc
101 #include <functional> // for equal_to<>, select1st<>, etc
102 #include <memory> // for alloc
103 #include <utility> // for pair<>
104 #include <sparsehash/internal/densehashtable.h> // IWYU pragma: export
105 #include <sparsehash/internal/libc_allocator_with_realloc.h>
106 #include HASH_FUN_H // for hash<>
107 _START_GOOGLE_NAMESPACE_
108  
109 template <class Key, class T,
110 class HashFcn = SPARSEHASH_HASH<Key>, // defined in sparseconfig.h
111 class EqualKey = std::equal_to<Key>,
112 class Alloc = libc_allocator_with_realloc<std::pair<const Key, T> > >
113 class dense_hash_map {
114 private:
115 // Apparently select1st is not stl-standard, so we define our own
116 struct SelectKey {
117 typedef const Key& result_type;
118 const Key& operator()(const std::pair<const Key, T>& p) const {
119 return p.first;
120 }
121 };
122 struct SetKey {
123 void operator()(std::pair<const Key, T>* value, const Key& new_key) const {
124 *const_cast<Key*>(&value->first) = new_key;
125 // It would be nice to clear the rest of value here as well, in
126 // case it's taking up a lot of memory. We do this by clearing
127 // the value. This assumes T has a zero-arg constructor!
128 value->second = T();
129 }
130 };
131 // For operator[].
132 struct DefaultValue {
133 std::pair<const Key, T> operator()(const Key& key) {
134 return std::make_pair(key, T());
135 }
136 };
137  
138 // The actual data
139 typedef dense_hashtable<std::pair<const Key, T>, Key, HashFcn, SelectKey,
140 SetKey, EqualKey, Alloc> ht;
141 ht rep;
142  
143 public:
144 typedef typename ht::key_type key_type;
145 typedef T data_type;
146 typedef T mapped_type;
147 typedef typename ht::value_type value_type;
148 typedef typename ht::hasher hasher;
149 typedef typename ht::key_equal key_equal;
150 typedef Alloc allocator_type;
151  
152 typedef typename ht::size_type size_type;
153 typedef typename ht::difference_type difference_type;
154 typedef typename ht::pointer pointer;
155 typedef typename ht::const_pointer const_pointer;
156 typedef typename ht::reference reference;
157 typedef typename ht::const_reference const_reference;
158  
159 typedef typename ht::iterator iterator;
160 typedef typename ht::const_iterator const_iterator;
161 typedef typename ht::local_iterator local_iterator;
162 typedef typename ht::const_local_iterator const_local_iterator;
163  
164 // Iterator functions
165 iterator begin() { return rep.begin(); }
166 iterator end() { return rep.end(); }
167 const_iterator begin() const { return rep.begin(); }
168 const_iterator end() const { return rep.end(); }
169  
170  
171 // These come from tr1's unordered_map. For us, a bucket has 0 or 1 elements.
172 local_iterator begin(size_type i) { return rep.begin(i); }
173 local_iterator end(size_type i) { return rep.end(i); }
174 const_local_iterator begin(size_type i) const { return rep.begin(i); }
175 const_local_iterator end(size_type i) const { return rep.end(i); }
176  
177 // Accessor functions
178 allocator_type get_allocator() const { return rep.get_allocator(); }
179 hasher hash_funct() const { return rep.hash_funct(); }
180 hasher hash_function() const { return hash_funct(); }
181 key_equal key_eq() const { return rep.key_eq(); }
182  
183  
184 // Constructors
185 0 explicit dense_hash_map(size_type expected_max_items_in_table = 0,
186 const hasher& hf = hasher(),
187 const key_equal& eql = key_equal(),
188 const allocator_type& alloc = allocator_type())
189 0 ▶ : rep(expected_max_items_in_table, hf, eql, SelectKey(), SetKey(), alloc) {
Branch: 1 branch
BranchTrueFalseTotal
: rep(expected_max_items_in_table, hf, eql, SelectKey(), SetKey(), alloc) { 0 0 0
190 0 }
191  
192 template <class InputIterator>
193 dense_hash_map(InputIterator f, InputIterator l,
194 const key_type& empty_key_val,
195 size_type expected_max_items_in_table = 0,
196 const hasher& hf = hasher(),
197 const key_equal& eql = key_equal(),
198 const allocator_type& alloc = allocator_type())
199 : rep(expected_max_items_in_table, hf, eql, SelectKey(), SetKey(), alloc) {
200 set_empty_key(empty_key_val);
201 rep.insert(f, l);
202 }
203 // We use the default copy constructor
204 // We use the default operator=()
205 // We use the default destructor
206  
207 void clear() { rep.clear(); }
208 // This clears the hash map without resizing it down to the minimum
209 // bucket count, but rather keeps the number of buckets constant
210 void clear_no_resize() { rep.clear_no_resize(); }
211 void swap(dense_hash_map& hs) { rep.swap(hs.rep); }
212  
213  
214 // Functions concerning size
215 size_type size() const { return rep.size(); }
216 size_type max_size() const { return rep.max_size(); }
217 bool empty() const { return rep.empty(); }
218 size_type bucket_count() const { return rep.bucket_count(); }
219 size_type max_bucket_count() const { return rep.max_bucket_count(); }
220  
221 // These are tr1 methods. bucket() is the bucket the key is or would be in.
222 size_type bucket_size(size_type i) const { return rep.bucket_size(i); }
223 size_type bucket(const key_type& key) const { return rep.bucket(key); }
224 float load_factor() const {
225 return size() * 1.0f / bucket_count();
226 }
227 float max_load_factor() const {
228 float shrink, grow;
229 rep.get_resizing_parameters(&shrink, &grow);
230 return grow;
231 }
232 void max_load_factor(float new_grow) {
233 float shrink, grow;
234 rep.get_resizing_parameters(&shrink, &grow);
235 rep.set_resizing_parameters(shrink, new_grow);
236 }
237 // These aren't tr1 methods but perhaps ought to be.
238 float min_load_factor() const {
239 float shrink, grow;
240 rep.get_resizing_parameters(&shrink, &grow);
241 return shrink;
242 }
243 void min_load_factor(float new_shrink) {
244 float shrink, grow;
245 rep.get_resizing_parameters(&shrink, &grow);
246 rep.set_resizing_parameters(new_shrink, grow);
247 }
248 // Deprecated; use min_load_factor() or max_load_factor() instead.
249 void set_resizing_parameters(float shrink, float grow) {
250 rep.set_resizing_parameters(shrink, grow);
251 }
252  
253 void resize(size_type hint) { rep.resize(hint); }
254 void rehash(size_type hint) { resize(hint); } // the tr1 name
255  
256 // Lookup routines
257 iterator find(const key_type& key) { return rep.find(key); }
258 const_iterator find(const key_type& key) const { return rep.find(key); }
259  
260 data_type& operator[](const key_type& key) { // This is our value-add!
261 // If key is in the hashtable, returns find(key)->second,
262 // otherwise returns insert(value_type(key, T()).first->second.
263 // Note it does not create an empty T unless the find fails.
264 return rep.template find_or_insert<DefaultValue>(key).second;
265 }
266  
267 size_type count(const key_type& key) const { return rep.count(key); }
268  
269 std::pair<iterator, iterator> equal_range(const key_type& key) {
270 return rep.equal_range(key);
271 }
272 std::pair<const_iterator, const_iterator> equal_range(const key_type& key)
273 const {
274 return rep.equal_range(key);
275 }
276  
277  
278 // Insertion routines
279 std::pair<iterator, bool> insert(const value_type& obj) {
280 return rep.insert(obj);
281 }
282 template <class InputIterator> void insert(InputIterator f, InputIterator l) {
283 rep.insert(f, l);
284 }
285 void insert(const_iterator f, const_iterator l) {
286 rep.insert(f, l);
287 }
288 // Required for std::insert_iterator; the passed-in iterator is ignored.
289 iterator insert(iterator, const value_type& obj) {
290 return insert(obj).first;
291 }
292  
293 // Deletion and empty routines
294 // THESE ARE NON-STANDARD! I make you specify an "impossible" key
295 // value to identify deleted and empty buckets. You can change the
296 // deleted key as time goes on, or get rid of it entirely to be insert-only.
297 void set_empty_key(const key_type& key) { // YOU MUST CALL THIS!
298 rep.set_empty_key(value_type(key, data_type())); // rep wants a value
299 }
300 key_type empty_key() const {
301 return rep.empty_key().first; // rep returns a value
302 }
303  
304 void set_deleted_key(const key_type& key) { rep.set_deleted_key(key); }
305 void clear_deleted_key() { rep.clear_deleted_key(); }
306 key_type deleted_key() const { return rep.deleted_key(); }
307  
308 // These are standard
309 size_type erase(const key_type& key) { return rep.erase(key); }
310 void erase(iterator it) { rep.erase(it); }
311 void erase(iterator f, iterator l) { rep.erase(f, l); }
312  
313  
314 // Comparison
315 bool operator==(const dense_hash_map& hs) const { return rep == hs.rep; }
316 bool operator!=(const dense_hash_map& hs) const { return rep != hs.rep; }
317  
318  
319 // I/O -- this is an add-on for writing hash map to disk
320 //
321 // For maximum flexibility, this does not assume a particular
322 // file type (though it will probably be a FILE *). We just pass
323 // the fp through to rep.
324  
325 // If your keys and values are simple enough, you can pass this
326 // serializer to serialize()/unserialize(). "Simple enough" means
327 // value_type is a POD type that contains no pointers. Note,
328 // however, we don't try to normalize endianness.
329 typedef typename ht::NopointerSerializer NopointerSerializer;
330  
331 // serializer: a class providing operator()(OUTPUT*, const value_type&)
332 // (writing value_type to OUTPUT). You can specify a
333 // NopointerSerializer object if appropriate (see above).
334 // fp: either a FILE*, OR an ostream*/subclass_of_ostream*, OR a
335 // pointer to a class providing size_t Write(const void*, size_t),
336 // which writes a buffer into a stream (which fp presumably
337 // owns) and returns the number of bytes successfully written.
338 // Note basic_ostream<not_char> is not currently supported.
339 template <typename ValueSerializer, typename OUTPUT>
340 bool serialize(ValueSerializer serializer, OUTPUT* fp) {
341 return rep.serialize(serializer, fp);
342 }
343  
344 // serializer: a functor providing operator()(INPUT*, value_type*)
345 // (reading from INPUT and into value_type). You can specify a
346 // NopointerSerializer object if appropriate (see above).
347 // fp: either a FILE*, OR an istream*/subclass_of_istream*, OR a
348 // pointer to a class providing size_t Read(void*, size_t),
349 // which reads into a buffer from a stream (which fp presumably
350 // owns) and returns the number of bytes successfully read.
351 // Note basic_istream<not_char> is not currently supported.
352 // NOTE: Since value_type is std::pair<const Key, T>, ValueSerializer
353 // may need to do a const cast in order to fill in the key.
354 template <typename ValueSerializer, typename INPUT>
355 bool unserialize(ValueSerializer serializer, INPUT* fp) {
356 return rep.unserialize(serializer, fp);
357 }
358 };
359  
360 // We need a global swap as well
361 template <class Key, class T, class HashFcn, class EqualKey, class Alloc>
362 inline void swap(dense_hash_map<Key, T, HashFcn, EqualKey, Alloc>& hm1,
363 dense_hash_map<Key, T, HashFcn, EqualKey, Alloc>& hm2) {
364 hm1.swap(hm2);
365 }
366  
367 _END_GOOGLE_NAMESPACE_
368  
369 #endif /* _DENSE_HASH_MAP_H_ */
« fastq-lib.cpp ↑ Summary sparsehash/internal/densehashtable.h »