/[pcsx2_0.9.7]/trunk/3rdparty/google/sparse_hash_map
ViewVC logotype

Annotation of /trunk/3rdparty/google/sparse_hash_map

Parent Directory Parent Directory | Revision Log Revision Log


Revision 10 - (hide annotations) (download)
Mon Sep 6 11:40:06 2010 UTC (9 years, 5 months ago) by william
File size: 10045 byte(s)
exported r3113 from ./upstream/trunk
1 william 10 // 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     // 3) set_resizing_parameters(0.0, 0.8):
57     // Setting the shrink_resize_percent to 0.0 guarantees
58     // that the hash table will never shrink.
59     //
60     // Guide to what kind of hash_map to use:
61     // (1) dense_hash_map: fastest, uses the most memory
62     // (2) sparse_hash_map: slowest, uses the least memory
63     // (3) hash_map (STL): in the middle
64     // Typically I use sparse_hash_map when I care about space and/or when
65     // I need to save the hashtable on disk. I use hash_map otherwise. I
66     // don't personally use dense_hash_map ever; the only use of
67     // dense_hash_map I know of is to work around malloc() bugs in some
68     // systems (dense_hash_map has a particularly simple allocation scheme).
69     //
70     // - dense_hash_map has, typically, a factor of 2 memory overhead (if your
71     // data takes up X bytes, the hash_map uses X more bytes in overhead).
72     // - sparse_hash_map has about 2 bits overhead per entry.
73     // - sparse_hash_map can be 3-7 times slower than the others for lookup and,
74     // especially, inserts. See time_hash_map.cc for details.
75     //
76     // See /usr/(local/)?doc/sparsehash-0.1/sparse_hash_map.html
77     // for information about how to use this class.
78    
79     #ifndef _SPARSE_HASH_MAP_H_
80     #define _SPARSE_HASH_MAP_H_
81    
82     #include <google/sparsehash/sparseconfig.h>
83     #include <stdio.h> // for FILE * in read()/write()
84     #include <algorithm> // for the default template args
85     #include <functional> // for equal_to
86     #include <memory> // for alloc<>
87     #include <utility> // for pair<>
88     #include HASH_FUN_H // defined in config.h
89     #include <google/sparsehash/sparsehashtable.h>
90    
91    
92     _START_GOOGLE_NAMESPACE_
93    
94     using STL_NAMESPACE::pair;
95    
96     template <class Key, class T,
97     class HashFcn = SPARSEHASH_HASH<Key>, // defined in sparseconfig.h
98     class EqualKey = STL_NAMESPACE::equal_to<Key>,
99     class Alloc = STL_NAMESPACE::allocator<T> >
100     class sparse_hash_map {
101     private:
102     // Apparently select1st is not stl-standard, so we define our own
103     struct SelectKey {
104     const Key& operator()(const pair<const Key, T>& p) const {
105     return p.first;
106     }
107     };
108    
109     // The actual data
110     typedef sparse_hashtable<pair<const Key, T>, Key, HashFcn,
111     SelectKey, EqualKey, Alloc> ht;
112     ht rep;
113    
114     public:
115     typedef typename ht::key_type key_type;
116     typedef T data_type;
117     typedef T mapped_type;
118     typedef typename ht::value_type value_type;
119     typedef typename ht::hasher hasher;
120     typedef typename ht::key_equal key_equal;
121    
122     typedef typename ht::size_type size_type;
123     typedef typename ht::difference_type difference_type;
124     typedef typename ht::pointer pointer;
125     typedef typename ht::const_pointer const_pointer;
126     typedef typename ht::reference reference;
127     typedef typename ht::const_reference const_reference;
128    
129     typedef typename ht::iterator iterator;
130     typedef typename ht::const_iterator const_iterator;
131    
132     // Iterator functions
133     iterator begin() { return rep.begin(); }
134     iterator end() { return rep.end(); }
135     const_iterator begin() const { return rep.begin(); }
136     const_iterator end() const { return rep.end(); }
137    
138    
139     // Accessor functions
140     hasher hash_funct() const { return rep.hash_funct(); }
141     key_equal key_eq() const { return rep.key_eq(); }
142    
143    
144     // Constructors
145     explicit sparse_hash_map(size_type expected_max_items_in_table = 0,
146     const hasher& hf = hasher(),
147     const key_equal& eql = key_equal())
148     : rep(expected_max_items_in_table, hf, eql) { }
149    
150     template <class InputIterator>
151     sparse_hash_map(InputIterator f, InputIterator l,
152     size_type expected_max_items_in_table = 0,
153     const hasher& hf = hasher(),
154     const key_equal& eql = key_equal())
155     : rep(expected_max_items_in_table, hf, eql) {
156     rep.insert(f, l);
157     }
158     // We use the default copy constructor
159     // We use the default operator=()
160     // We use the default destructor
161    
162     void clear() { rep.clear(); }
163     void swap(sparse_hash_map& hs) { rep.swap(hs.rep); }
164    
165    
166     // Functions concerning size
167     size_type size() const { return rep.size(); }
168     size_type max_size() const { return rep.max_size(); }
169     bool empty() const { return rep.empty(); }
170     size_type bucket_count() const { return rep.bucket_count(); }
171     size_type max_bucket_count() const { return rep.max_bucket_count(); }
172    
173     void resize(size_type hint) { rep.resize(hint); }
174    
175     void set_resizing_parameters(float shrink, float grow) {
176     return rep.set_resizing_parameters(shrink, grow);
177     }
178    
179     // Lookup routines
180     iterator find(const key_type& key) { return rep.find(key); }
181     const_iterator find(const key_type& key) const { return rep.find(key); }
182    
183     data_type& operator[](const key_type& key) { // This is our value-add!
184     iterator it = find(key);
185     if (it != end()) {
186     return it->second;
187     } else {
188     return insert(value_type(key, data_type())).first->second;
189     }
190     }
191    
192     size_type count(const key_type& key) const { return rep.count(key); }
193    
194     pair<iterator, iterator> equal_range(const key_type& key) {
195     return rep.equal_range(key);
196     }
197     pair<const_iterator, const_iterator> equal_range(const key_type& key) const {
198     return rep.equal_range(key);
199     }
200    
201     // Insertion routines
202     pair<iterator, bool> insert(const value_type& obj) { return rep.insert(obj); }
203     template <class InputIterator>
204     void insert(InputIterator f, InputIterator l) { rep.insert(f, l); }
205     void insert(const_iterator f, const_iterator l) { rep.insert(f, l); }
206     // required for std::insert_iterator; the passed-in iterator is ignored
207     iterator insert(iterator, const value_type& obj) { return insert(obj).first; }
208    
209    
210     // Deletion routines
211     // THESE ARE NON-STANDARD! I make you specify an "impossible" key
212     // value to identify deleted buckets. You can change the key as
213     // time goes on, or get rid of it entirely to be insert-only.
214     void set_deleted_key(const key_type& key) {
215     rep.set_deleted_key(value_type(key, data_type())); // rep wants a value
216     }
217     void clear_deleted_key() { rep.clear_deleted_key(); }
218    
219     // These are standard
220     size_type erase(const key_type& key) { return rep.erase(key); }
221     void erase(iterator it) { rep.erase(it); }
222     void erase(iterator f, iterator l) { rep.erase(f, l); }
223    
224    
225     // Comparison
226     bool operator==(const sparse_hash_map& hs) const { return rep == hs.rep; }
227     bool operator!=(const sparse_hash_map& hs) const { return rep != hs.rep; }
228    
229    
230     // I/O -- this is an add-on for writing metainformation to disk
231     bool write_metadata(FILE *fp) { return rep.write_metadata(fp); }
232     bool read_metadata(FILE *fp) { return rep.read_metadata(fp); }
233     bool write_nopointer_data(FILE *fp) { return rep.write_nopointer_data(fp); }
234     bool read_nopointer_data(FILE *fp) { return rep.read_nopointer_data(fp); }
235     };
236    
237     // We need a global swap as well
238     template <class Key, class T, class HashFcn, class EqualKey, class Alloc>
239     inline void swap(sparse_hash_map<Key, T, HashFcn, EqualKey, Alloc>& hm1,
240     sparse_hash_map<Key, T, HashFcn, EqualKey, Alloc>& hm2) {
241     hm1.swap(hm2);
242     }
243    
244     _END_GOOGLE_NAMESPACE_
245    
246     #endif /* _SPARSE_HASH_MAP_H_ */

  ViewVC Help
Powered by ViewVC 1.1.22