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 | // Author: Craig Silverstein
|
---|
32 | //
|
---|
33 | // This is just a very thin wrapper over sparsehashtable.h, just
|
---|
34 | // like sgi stl's stl_hash_map is a very thin wrapper over
|
---|
35 | // stl_hashtable. The major thing we define is operator[], because
|
---|
36 | // we have a concept of a data_type which stl_hashtable doesn't
|
---|
37 | // (it only has a key and a value).
|
---|
38 | //
|
---|
39 | // We adhere mostly to the STL semantics for hash-map. One important
|
---|
40 | // exception is that insert() invalidates iterators entirely. On the
|
---|
41 | // plus side, though, delete() doesn't invalidate iterators at all, or
|
---|
42 | // even change the ordering of elements.
|
---|
43 | //
|
---|
44 | // Here are a few "power user" tips:
|
---|
45 | //
|
---|
46 | // 1) set_deleted_key():
|
---|
47 | // Unlike STL's hash_map, if you want to use erase() you
|
---|
48 | // must call set_deleted_key() after construction.
|
---|
49 | //
|
---|
50 | // 2) resize(0):
|
---|
51 | // When an item is deleted, its memory isn't freed right
|
---|
52 | // away. This is what allows you to iterate over a hashtable
|
---|
53 | // and call erase() without invalidating the iterator.
|
---|
54 | // To force the memory to be freed, call resize(0).
|
---|
55 | //
|
---|
56 | // Guide to what kind of hash_map to use:
|
---|
57 | // (1) dense_hash_map: fastest, uses the most memory
|
---|
58 | // (2) sparse_hash_map: slowest, uses the least memory
|
---|
59 | // (3) hash_map (STL): in the middle
|
---|
60 | // Typically I use sparse_hash_map when I care about space and/or when
|
---|
61 | // I need to save the hashtable on disk. I use hash_map otherwise. I
|
---|
62 | // don't personally use dense_hash_map ever; the only use of
|
---|
63 | // dense_hash_map I know of is to work around malloc() bugs in some
|
---|
64 | // systems (dense_hash_map has a particularly simple allocation scheme).
|
---|
65 | //
|
---|
66 | // - dense_hash_map has, typically, a factor of 2 memory overhead (if your
|
---|
67 | // data takes up X bytes, the hash_map uses X more bytes in overhead).
|
---|
68 | // - sparse_hash_map has about 2 bits overhead per entry.
|
---|
69 | // - sparse_hash_map can be 3-7 times slower than the others for lookup and,
|
---|
70 | // especially, inserts. See time_hash_map.cc for details.
|
---|
71 | //
|
---|
72 | // See /usr/(local/)?doc/sparsehash-0.1/sparse_hash_map.html
|
---|
73 | // for information about how to use this class.
|
---|
74 |
|
---|
75 | #ifndef _SPARSE_HASH_MAP_H_
|
---|
76 | #define _SPARSE_HASH_MAP_H_
|
---|
77 |
|
---|
78 | #include <google/sparsehash/config.h>
|
---|
79 | #include <stdio.h> // for FILE * in read()/write()
|
---|
80 | #include <algorithm> // for the default template args
|
---|
81 | #include <functional> // for equal_to
|
---|
82 | #include <memory> // for alloc<>
|
---|
83 | #include <google/sparsehash/hash_fun.h>
|
---|
84 | #include <google/sparsehash/sparsehashtable.h>
|
---|
85 |
|
---|
86 |
|
---|
87 | // Lots of STLs don't support type traits, so we might well do without.
|
---|
88 | // We also have a guard to make sure we don't include this code twice:
|
---|
89 | // once for sparse_hash_map and once for dense_hash_map.
|
---|
90 | #if defined(UNDERSTANDS_TYPE_TRAITS) && !defined(_ANDED_TRAITS_)
|
---|
91 | #define _ANDED_TRAITS_
|
---|
92 |
|
---|
93 | #if defined HAVE_TYPE_TRAITS
|
---|
94 | #include <type_traits.h>
|
---|
95 | #elif defined HAVE_BITS_TYPE_TRAITS
|
---|
96 | #include <bits/type_traits.h>
|
---|
97 | #endif
|
---|
98 |
|
---|
99 | // We need to let the densetable know that our pair<Key,Data> is
|
---|
100 | // a Plain Old Data type if both the Key and Data are.
|
---|
101 | template <class Key, class T>
|
---|
102 | struct __and_trait { // by default x & y == false
|
---|
103 | typedef __false_type tp;
|
---|
104 | };
|
---|
105 |
|
---|
106 | template <> struct __and_trait<__true_type, __true_type> { // but true & true == true
|
---|
107 | typedef __true_type tp;
|
---|
108 | };
|
---|
109 |
|
---|
110 | #define AND_(trait) \
|
---|
111 | typedef typename __and_trait<typename __type_traits<Key>::trait, \
|
---|
112 | typename __type_traits< T >::trait>::tp \
|
---|
113 | trait
|
---|
114 |
|
---|
115 | template <class Key, class T>
|
---|
116 | struct __type_traits< STL_NAMESPACE::pair<const Key, T> > {
|
---|
117 | AND_(has_trivial_default_constructor);
|
---|
118 | AND_(has_trivial_copy_constructor);
|
---|
119 | AND_(has_trivial_assignment_operator);
|
---|
120 | AND_(has_trivial_destructor);
|
---|
121 | AND_(is_POD_type);
|
---|
122 | };
|
---|
123 |
|
---|
124 | #undef AND_
|
---|
125 |
|
---|
126 | #endif /* #defined UNDERSTANDS_TYPE_TRAITS && _ANDED_TRAITS_ */
|
---|
127 |
|
---|
128 |
|
---|
129 | _START_GOOGLE_NAMESPACE_
|
---|
130 |
|
---|
131 | using STL_NAMESPACE::pair;
|
---|
132 |
|
---|
133 | template <class Key, class T,
|
---|
134 | class HashFcn = HASH_NAMESPACE::hash<Key>,
|
---|
135 | class EqualKey = STL_NAMESPACE::equal_to<Key>,
|
---|
136 | class Alloc = STL_NAMESPACE::allocator<T> >
|
---|
137 | class sparse_hash_map {
|
---|
138 |
|
---|
139 | private:
|
---|
140 | // Apparently select1st is not stl-standard, so we define our own
|
---|
141 | struct SelectKey {
|
---|
142 | const Key& operator()(const pair<const Key, T>& p) const {
|
---|
143 | return p.first;
|
---|
144 | }
|
---|
145 | };
|
---|
146 |
|
---|
147 | // The actual data
|
---|
148 | typedef sparse_hashtable<pair<const Key, T>, Key, HashFcn,
|
---|
149 | SelectKey, EqualKey, Alloc> ht;
|
---|
150 | ht rep;
|
---|
151 |
|
---|
152 | public:
|
---|
153 | typedef typename ht::key_type key_type;
|
---|
154 | typedef T data_type;
|
---|
155 | typedef T mapped_type;
|
---|
156 | typedef typename ht::value_type value_type;
|
---|
157 | typedef typename ht::hasher hasher;
|
---|
158 | typedef typename ht::key_equal key_equal;
|
---|
159 |
|
---|
160 | typedef typename ht::size_type size_type;
|
---|
161 | typedef typename ht::difference_type difference_type;
|
---|
162 | typedef typename ht::pointer pointer;
|
---|
163 | typedef typename ht::const_pointer const_pointer;
|
---|
164 | typedef typename ht::reference reference;
|
---|
165 | typedef typename ht::const_reference const_reference;
|
---|
166 |
|
---|
167 | typedef typename ht::iterator iterator;
|
---|
168 | typedef typename ht::const_iterator const_iterator;
|
---|
169 |
|
---|
170 | // Iterator functions
|
---|
171 | iterator begin() { return rep.begin(); }
|
---|
172 | iterator end() { return rep.end(); }
|
---|
173 | const_iterator begin() const { return rep.begin(); }
|
---|
174 | const_iterator end() const { return rep.end(); }
|
---|
175 |
|
---|
176 |
|
---|
177 | // Accessor functions
|
---|
178 | hasher hash_funct() const { return rep.hash_funct(); }
|
---|
179 | key_equal key_eq() const { return rep.key_eq(); }
|
---|
180 |
|
---|
181 |
|
---|
182 | // Constructors
|
---|
183 | explicit sparse_hash_map(size_type n = 0,
|
---|
184 | const hasher& hf = hasher(),
|
---|
185 | const key_equal& eql = key_equal())
|
---|
186 | : rep(n, hf, eql) { }
|
---|
187 |
|
---|
188 | template <class InputIterator>
|
---|
189 | sparse_hash_map(InputIterator f, InputIterator l,
|
---|
190 | size_type n = 0,
|
---|
191 | const hasher& hf = hasher(),
|
---|
192 | const key_equal& eql = key_equal()) {
|
---|
193 | rep.insert(f, l);
|
---|
194 | }
|
---|
195 | // We use the default copy constructor
|
---|
196 | // We use the default operator=()
|
---|
197 | // We use the default destructor
|
---|
198 |
|
---|
199 | void clear() { rep.clear(); }
|
---|
200 | void swap(sparse_hash_map& hs) { rep.swap(hs.rep); }
|
---|
201 |
|
---|
202 |
|
---|
203 | // Functions concerning size
|
---|
204 | size_type size() const { return rep.size(); }
|
---|
205 | size_type max_size() const { return rep.max_size(); }
|
---|
206 | bool empty() const { return rep.empty(); }
|
---|
207 | size_type bucket_count() const { return rep.bucket_count(); }
|
---|
208 | size_type max_bucket_count() const { return rep.max_bucket_count(); }
|
---|
209 |
|
---|
210 | void resize(size_type hint) { rep.resize(hint); }
|
---|
211 |
|
---|
212 |
|
---|
213 | // Lookup routines
|
---|
214 | iterator find(const key_type& key) { return rep.find(key); }
|
---|
215 | const_iterator find(const key_type& key) const { return rep.find(key); }
|
---|
216 |
|
---|
217 | data_type& operator[](const key_type& key) { // This is our value-add!
|
---|
218 | return (*((rep.insert(value_type(key, data_type()))).first)).second;
|
---|
219 | }
|
---|
220 |
|
---|
221 | size_type count(const key_type& key) const { return rep.count(key); }
|
---|
222 |
|
---|
223 | pair<iterator, iterator> equal_range(const key_type& key) {
|
---|
224 | return rep.equal_range(key);
|
---|
225 | }
|
---|
226 | pair<const_iterator, const_iterator> equal_range(const key_type& key) const {
|
---|
227 | return rep.equal_range(key);
|
---|
228 | }
|
---|
229 |
|
---|
230 | // Insertion routines
|
---|
231 | pair<iterator, bool> insert(const value_type& obj) { return rep.insert(obj); }
|
---|
232 | template <class InputIterator>
|
---|
233 | void insert(InputIterator f, InputIterator l) { rep.insert(f, l); }
|
---|
234 | void insert(const_iterator f, const_iterator l) { rep.insert(f, l); }
|
---|
235 | // required for std::insert_iterator; the passed-in iterator is ignored
|
---|
236 | iterator insert(iterator, const value_type& obj) { return insert(obj).first; }
|
---|
237 |
|
---|
238 |
|
---|
239 | // Deletion routines
|
---|
240 | // THESE ARE NON-STANDARD! I make you specify an "impossible" key
|
---|
241 | // value to identify deleted buckets. You can change the key as
|
---|
242 | // time goes on, or get rid of it entirely to be insert-only.
|
---|
243 | void set_deleted_key(const key_type& key) {
|
---|
244 | rep.set_deleted_key(key);
|
---|
245 | }
|
---|
246 | void clear_deleted_key() { rep.clear_deleted_key(); }
|
---|
247 |
|
---|
248 | // These are standard
|
---|
249 | size_type erase(const key_type& key) { return rep.erase(key); }
|
---|
250 | void erase(iterator it) { rep.erase(it); }
|
---|
251 | void erase(iterator f, iterator l) { rep.erase(f, l); }
|
---|
252 |
|
---|
253 |
|
---|
254 | // Comparison
|
---|
255 | bool operator==(const sparse_hash_map& hs) const { return rep == hs.rep; }
|
---|
256 | bool operator!=(const sparse_hash_map& hs) const { return rep != hs.rep; }
|
---|
257 |
|
---|
258 |
|
---|
259 | // I/O -- this is an add-on for writing metainformation to disk
|
---|
260 | bool write_metadata(FILE *fp) { return rep.write_metadata(fp); }
|
---|
261 | bool read_metadata(FILE *fp) { return rep.read_metadata(fp); }
|
---|
262 | bool write_nopointer_data(FILE *fp) { return rep.write_nopointer_data(fp); }
|
---|
263 | bool read_nopointer_data(FILE *fp) { return rep.read_nopointer_data(fp); }
|
---|
264 | };
|
---|
265 |
|
---|
266 | // We need a global swap as well
|
---|
267 | template <class Key, class T, class HashFcn, class EqualKey, class Alloc>
|
---|
268 | inline void swap(sparse_hash_map<Key, T, HashFcn, EqualKey, Alloc>& hm1,
|
---|
269 | sparse_hash_map<Key, T, HashFcn, EqualKey, Alloc>& hm2) {
|
---|
270 | hm1.swap(hm2);
|
---|
271 | }
|
---|
272 |
|
---|
273 | _END_GOOGLE_NAMESPACE_
|
---|
274 |
|
---|
275 | #endif /* _SPARSE_HASH_MAP_H_ */
|
---|