1 /*
2 * Copyright (c) 1996
3 * Silicon Graphics Computer Systems, Inc.
4 *
5 * Permission to use, copy, modify, distribute and sell this software
6 * and its documentation for any purpose is hereby granted without fee,
7 * provided that the above copyright notice appear in all copies and
8 * that both that copyright notice and this permission notice appear
9 * in supporting documentation. Silicon Graphics makes no
10 * representations about the suitability of this software for any
11 * purpose. It is provided "as is" without express or implied warranty.
12 *
13 *
14 * Copyright (c) 1994
15 * Hewlett-Packard Company
16 *
17 * Permission to use, copy, modify, distribute and sell this software
18 * and its documentation for any purpose is hereby granted without fee,
19 * provided that the above copyright notice appear in all copies and
20 * that both that copyright notice and this permission notice appear
21 * in supporting documentation. Hewlett-Packard Company makes no
22 * representations about the suitability of this software for any
23 * purpose. It is provided "as is" without express or implied warranty.
24 *
25 */
26
27 /* NOTE: This is an internal header file, included by other STL headers.
28 * You should not attempt to use it directly.
29 */
30
31 #ifndef __SGI_STL_INTERNAL_HASH_MAP_H
32 #define __SGI_STL_INTERNAL_HASH_MAP_H
33
34
35 __STL_BEGIN_NAMESPACE
36
37 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
38 #pragma set woff 1174
39 #pragma set woff 1375
40 #endif
41
42 #ifndef __STL_LIMITED_DEFAULT_TEMPLATES
43 template <class _Key, class _Tp, class _HashFcn = hash<_Key>,
44 class _EqualKey = equal_to<_Key>,
45 class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
46 #else
47 template <class _Key, class _Tp, class _HashFcn, class _EqualKey,
48 class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
49 #endif
50 class hash_map
51 {
52 private:
53 typedef hashtable<pair<const _Key,_Tp>,_Key,_HashFcn,
54 _Select1st<pair<const _Key,_Tp> >,_EqualKey,_Alloc> _Ht;
55 _Ht _M_ht;
56
57 public:
58 typedef typename _Ht::key_type key_type;
59 typedef _Tp data_type;
60 typedef _Tp mapped_type;
61 typedef typename _Ht::value_type value_type;
62 typedef typename _Ht::hasher hasher;
63 typedef typename _Ht::key_equal key_equal;
64
65 typedef typename _Ht::size_type size_type;
66 typedef typename _Ht::difference_type difference_type;
67 typedef typename _Ht::pointer pointer;
68 typedef typename _Ht::const_pointer const_pointer;
69 typedef typename _Ht::reference reference;
70 typedef typename _Ht::const_reference const_reference;
71
72 typedef typename _Ht::iterator iterator;
73 typedef typename _Ht::const_iterator const_iterator;
74
75 typedef typename _Ht::allocator_type allocator_type;
76
hash_funct()77 hasher hash_funct() const { return _M_ht.hash_funct(); }
key_eq()78 key_equal key_eq() const { return _M_ht.key_eq(); }
get_allocator()79 allocator_type get_allocator() const { return _M_ht.get_allocator(); }
80
81 public:
hash_map()82 hash_map() : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
hash_map(size_type __n)83 explicit hash_map(size_type __n)
84 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
hash_map(size_type __n,const hasher & __hf)85 hash_map(size_type __n, const hasher& __hf)
86 : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
87 hash_map(size_type __n, const hasher& __hf, const key_equal& __eql,
88 const allocator_type& __a = allocator_type())
_M_ht(__n,__hf,__eql,__a)89 : _M_ht(__n, __hf, __eql, __a) {}
90
91 #ifdef __STL_MEMBER_TEMPLATES
92 template <class _InputIterator>
hash_map(_InputIterator __f,_InputIterator __l)93 hash_map(_InputIterator __f, _InputIterator __l)
94 : _M_ht(100, hasher(), key_equal(), allocator_type())
95 { _M_ht.insert_unique(__f, __l); }
96 template <class _InputIterator>
hash_map(_InputIterator __f,_InputIterator __l,size_type __n)97 hash_map(_InputIterator __f, _InputIterator __l, size_type __n)
98 : _M_ht(__n, hasher(), key_equal(), allocator_type())
99 { _M_ht.insert_unique(__f, __l); }
100 template <class _InputIterator>
hash_map(_InputIterator __f,_InputIterator __l,size_type __n,const hasher & __hf)101 hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
102 const hasher& __hf)
103 : _M_ht(__n, __hf, key_equal(), allocator_type())
104 { _M_ht.insert_unique(__f, __l); }
105 template <class _InputIterator>
106 hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
107 const hasher& __hf, const key_equal& __eql,
108 const allocator_type& __a = allocator_type())
_M_ht(__n,__hf,__eql,__a)109 : _M_ht(__n, __hf, __eql, __a)
110 { _M_ht.insert_unique(__f, __l); }
111
112 #else
hash_map(const value_type * __f,const value_type * __l)113 hash_map(const value_type* __f, const value_type* __l)
114 : _M_ht(100, hasher(), key_equal(), allocator_type())
115 { _M_ht.insert_unique(__f, __l); }
hash_map(const value_type * __f,const value_type * __l,size_type __n)116 hash_map(const value_type* __f, const value_type* __l, size_type __n)
117 : _M_ht(__n, hasher(), key_equal(), allocator_type())
118 { _M_ht.insert_unique(__f, __l); }
hash_map(const value_type * __f,const value_type * __l,size_type __n,const hasher & __hf)119 hash_map(const value_type* __f, const value_type* __l, size_type __n,
120 const hasher& __hf)
121 : _M_ht(__n, __hf, key_equal(), allocator_type())
122 { _M_ht.insert_unique(__f, __l); }
123 hash_map(const value_type* __f, const value_type* __l, size_type __n,
124 const hasher& __hf, const key_equal& __eql,
125 const allocator_type& __a = allocator_type())
_M_ht(__n,__hf,__eql,__a)126 : _M_ht(__n, __hf, __eql, __a)
127 { _M_ht.insert_unique(__f, __l); }
128
hash_map(const_iterator __f,const_iterator __l)129 hash_map(const_iterator __f, const_iterator __l)
130 : _M_ht(100, hasher(), key_equal(), allocator_type())
131 { _M_ht.insert_unique(__f, __l); }
hash_map(const_iterator __f,const_iterator __l,size_type __n)132 hash_map(const_iterator __f, const_iterator __l, size_type __n)
133 : _M_ht(__n, hasher(), key_equal(), allocator_type())
134 { _M_ht.insert_unique(__f, __l); }
hash_map(const_iterator __f,const_iterator __l,size_type __n,const hasher & __hf)135 hash_map(const_iterator __f, const_iterator __l, size_type __n,
136 const hasher& __hf)
137 : _M_ht(__n, __hf, key_equal(), allocator_type())
138 { _M_ht.insert_unique(__f, __l); }
139 hash_map(const_iterator __f, const_iterator __l, size_type __n,
140 const hasher& __hf, const key_equal& __eql,
141 const allocator_type& __a = allocator_type())
_M_ht(__n,__hf,__eql,__a)142 : _M_ht(__n, __hf, __eql, __a)
143 { _M_ht.insert_unique(__f, __l); }
144 #endif /*__STL_MEMBER_TEMPLATES */
145
146 public:
size()147 size_type size() const { return _M_ht.size(); }
max_size()148 size_type max_size() const { return _M_ht.max_size(); }
empty()149 bool empty() const { return _M_ht.empty(); }
swap(hash_map & __hs)150 void swap(hash_map& __hs) { _M_ht.swap(__hs._M_ht); }
151 friend bool
152 operator== __STL_NULL_TMPL_ARGS (const hash_map&, const hash_map&);
153
begin()154 iterator begin() { return _M_ht.begin(); }
end()155 iterator end() { return _M_ht.end(); }
begin()156 const_iterator begin() const { return _M_ht.begin(); }
end()157 const_iterator end() const { return _M_ht.end(); }
158
159 public:
insert(const value_type & __obj)160 pair<iterator,bool> insert(const value_type& __obj)
161 { return _M_ht.insert_unique(__obj); }
162 #ifdef __STL_MEMBER_TEMPLATES
163 template <class _InputIterator>
insert(_InputIterator __f,_InputIterator __l)164 void insert(_InputIterator __f, _InputIterator __l)
165 { _M_ht.insert_unique(__f,__l); }
166 #else
insert(const value_type * __f,const value_type * __l)167 void insert(const value_type* __f, const value_type* __l) {
168 _M_ht.insert_unique(__f,__l);
169 }
insert(const_iterator __f,const_iterator __l)170 void insert(const_iterator __f, const_iterator __l)
171 { _M_ht.insert_unique(__f, __l); }
172 #endif /*__STL_MEMBER_TEMPLATES */
insert_noresize(const value_type & __obj)173 pair<iterator,bool> insert_noresize(const value_type& __obj)
174 { return _M_ht.insert_unique_noresize(__obj); }
175
find(const key_type & __key)176 iterator find(const key_type& __key) { return _M_ht.find(__key); }
find(const key_type & __key)177 const_iterator find(const key_type& __key) const
178 { return _M_ht.find(__key); }
179
180 _Tp& operator[](const key_type& __key) {
181 return _M_ht.find_or_insert(value_type(__key, _Tp())).second;
182 }
183
count(const key_type & __key)184 size_type count(const key_type& __key) const { return _M_ht.count(__key); }
185
equal_range(const key_type & __key)186 pair<iterator, iterator> equal_range(const key_type& __key)
187 { return _M_ht.equal_range(__key); }
188 pair<const_iterator, const_iterator>
equal_range(const key_type & __key)189 equal_range(const key_type& __key) const
190 { return _M_ht.equal_range(__key); }
191
erase(const key_type & __key)192 size_type erase(const key_type& __key) {return _M_ht.erase(__key); }
erase(iterator __it)193 void erase(iterator __it) { _M_ht.erase(__it); }
erase(iterator __f,iterator __l)194 void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
clear()195 void clear() { _M_ht.clear(); }
196
resize(size_type __hint)197 void resize(size_type __hint) { _M_ht.resize(__hint); }
bucket_count()198 size_type bucket_count() const { return _M_ht.bucket_count(); }
max_bucket_count()199 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
elems_in_bucket(size_type __n)200 size_type elems_in_bucket(size_type __n) const
201 { return _M_ht.elems_in_bucket(__n); }
202 };
203
204 template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc>
205 inline bool
206 operator==(const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1,
207 const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2)
208 {
209 return __hm1._M_ht == __hm2._M_ht;
210 }
211
212 #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
213
214 template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc>
215 inline void
swap(hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc> & __hm1,hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc> & __hm2)216 swap(hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1,
217 hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2)
218 {
219 __hm1.swap(__hm2);
220 }
221
222 #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
223
224 #ifndef __STL_LIMITED_DEFAULT_TEMPLATES
225 template <class _Key, class _Tp, class _HashFcn = hash<_Key>,
226 class _EqualKey = equal_to<_Key>,
227 class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
228 #else
229 template <class _Key, class _Tp, class _HashFcn, class _EqualKey,
230 class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
231 #endif
232 class hash_multimap
233 {
234 private:
235 typedef hashtable<pair<const _Key, _Tp>, _Key, _HashFcn,
236 _Select1st<pair<const _Key, _Tp> >, _EqualKey, _Alloc>
237 _Ht;
238 _Ht _M_ht;
239
240 public:
241 typedef typename _Ht::key_type key_type;
242 typedef _Tp data_type;
243 typedef _Tp mapped_type;
244 typedef typename _Ht::value_type value_type;
245 typedef typename _Ht::hasher hasher;
246 typedef typename _Ht::key_equal key_equal;
247
248 typedef typename _Ht::size_type size_type;
249 typedef typename _Ht::difference_type difference_type;
250 typedef typename _Ht::pointer pointer;
251 typedef typename _Ht::const_pointer const_pointer;
252 typedef typename _Ht::reference reference;
253 typedef typename _Ht::const_reference const_reference;
254
255 typedef typename _Ht::iterator iterator;
256 typedef typename _Ht::const_iterator const_iterator;
257
258 typedef typename _Ht::allocator_type allocator_type;
259
hash_funct()260 hasher hash_funct() const { return _M_ht.hash_funct(); }
key_eq()261 key_equal key_eq() const { return _M_ht.key_eq(); }
get_allocator()262 allocator_type get_allocator() const { return _M_ht.get_allocator(); }
263
264 public:
hash_multimap()265 hash_multimap() : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
hash_multimap(size_type __n)266 explicit hash_multimap(size_type __n)
267 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
hash_multimap(size_type __n,const hasher & __hf)268 hash_multimap(size_type __n, const hasher& __hf)
269 : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
270 hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql,
271 const allocator_type& __a = allocator_type())
_M_ht(__n,__hf,__eql,__a)272 : _M_ht(__n, __hf, __eql, __a) {}
273
274 #ifdef __STL_MEMBER_TEMPLATES
275 template <class _InputIterator>
hash_multimap(_InputIterator __f,_InputIterator __l)276 hash_multimap(_InputIterator __f, _InputIterator __l)
277 : _M_ht(100, hasher(), key_equal(), allocator_type())
278 { _M_ht.insert_equal(__f, __l); }
279 template <class _InputIterator>
hash_multimap(_InputIterator __f,_InputIterator __l,size_type __n)280 hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n)
281 : _M_ht(__n, hasher(), key_equal(), allocator_type())
282 { _M_ht.insert_equal(__f, __l); }
283 template <class _InputIterator>
hash_multimap(_InputIterator __f,_InputIterator __l,size_type __n,const hasher & __hf)284 hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
285 const hasher& __hf)
286 : _M_ht(__n, __hf, key_equal(), allocator_type())
287 { _M_ht.insert_equal(__f, __l); }
288 template <class _InputIterator>
289 hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
290 const hasher& __hf, const key_equal& __eql,
291 const allocator_type& __a = allocator_type())
_M_ht(__n,__hf,__eql,__a)292 : _M_ht(__n, __hf, __eql, __a)
293 { _M_ht.insert_equal(__f, __l); }
294
295 #else
hash_multimap(const value_type * __f,const value_type * __l)296 hash_multimap(const value_type* __f, const value_type* __l)
297 : _M_ht(100, hasher(), key_equal(), allocator_type())
298 { _M_ht.insert_equal(__f, __l); }
hash_multimap(const value_type * __f,const value_type * __l,size_type __n)299 hash_multimap(const value_type* __f, const value_type* __l, size_type __n)
300 : _M_ht(__n, hasher(), key_equal(), allocator_type())
301 { _M_ht.insert_equal(__f, __l); }
hash_multimap(const value_type * __f,const value_type * __l,size_type __n,const hasher & __hf)302 hash_multimap(const value_type* __f, const value_type* __l, size_type __n,
303 const hasher& __hf)
304 : _M_ht(__n, __hf, key_equal(), allocator_type())
305 { _M_ht.insert_equal(__f, __l); }
306 hash_multimap(const value_type* __f, const value_type* __l, size_type __n,
307 const hasher& __hf, const key_equal& __eql,
308 const allocator_type& __a = allocator_type())
_M_ht(__n,__hf,__eql,__a)309 : _M_ht(__n, __hf, __eql, __a)
310 { _M_ht.insert_equal(__f, __l); }
311
hash_multimap(const_iterator __f,const_iterator __l)312 hash_multimap(const_iterator __f, const_iterator __l)
313 : _M_ht(100, hasher(), key_equal(), allocator_type())
314 { _M_ht.insert_equal(__f, __l); }
hash_multimap(const_iterator __f,const_iterator __l,size_type __n)315 hash_multimap(const_iterator __f, const_iterator __l, size_type __n)
316 : _M_ht(__n, hasher(), key_equal(), allocator_type())
317 { _M_ht.insert_equal(__f, __l); }
hash_multimap(const_iterator __f,const_iterator __l,size_type __n,const hasher & __hf)318 hash_multimap(const_iterator __f, const_iterator __l, size_type __n,
319 const hasher& __hf)
320 : _M_ht(__n, __hf, key_equal(), allocator_type())
321 { _M_ht.insert_equal(__f, __l); }
322 hash_multimap(const_iterator __f, const_iterator __l, size_type __n,
323 const hasher& __hf, const key_equal& __eql,
324 const allocator_type& __a = allocator_type())
_M_ht(__n,__hf,__eql,__a)325 : _M_ht(__n, __hf, __eql, __a)
326 { _M_ht.insert_equal(__f, __l); }
327 #endif /*__STL_MEMBER_TEMPLATES */
328
329 public:
size()330 size_type size() const { return _M_ht.size(); }
max_size()331 size_type max_size() const { return _M_ht.max_size(); }
empty()332 bool empty() const { return _M_ht.empty(); }
swap(hash_multimap & __hs)333 void swap(hash_multimap& __hs) { _M_ht.swap(__hs._M_ht); }
334 friend bool
335 operator== __STL_NULL_TMPL_ARGS (const hash_multimap&,
336 const hash_multimap&);
337
begin()338 iterator begin() { return _M_ht.begin(); }
end()339 iterator end() { return _M_ht.end(); }
begin()340 const_iterator begin() const { return _M_ht.begin(); }
end()341 const_iterator end() const { return _M_ht.end(); }
342
343 public:
insert(const value_type & __obj)344 iterator insert(const value_type& __obj)
345 { return _M_ht.insert_equal(__obj); }
346 #ifdef __STL_MEMBER_TEMPLATES
347 template <class _InputIterator>
insert(_InputIterator __f,_InputIterator __l)348 void insert(_InputIterator __f, _InputIterator __l)
349 { _M_ht.insert_equal(__f,__l); }
350 #else
insert(const value_type * __f,const value_type * __l)351 void insert(const value_type* __f, const value_type* __l) {
352 _M_ht.insert_equal(__f,__l);
353 }
insert(const_iterator __f,const_iterator __l)354 void insert(const_iterator __f, const_iterator __l)
355 { _M_ht.insert_equal(__f, __l); }
356 #endif /*__STL_MEMBER_TEMPLATES */
insert_noresize(const value_type & __obj)357 iterator insert_noresize(const value_type& __obj)
358 { return _M_ht.insert_equal_noresize(__obj); }
359
find(const key_type & __key)360 iterator find(const key_type& __key) { return _M_ht.find(__key); }
find(const key_type & __key)361 const_iterator find(const key_type& __key) const
362 { return _M_ht.find(__key); }
363
count(const key_type & __key)364 size_type count(const key_type& __key) const { return _M_ht.count(__key); }
365
equal_range(const key_type & __key)366 pair<iterator, iterator> equal_range(const key_type& __key)
367 { return _M_ht.equal_range(__key); }
368 pair<const_iterator, const_iterator>
equal_range(const key_type & __key)369 equal_range(const key_type& __key) const
370 { return _M_ht.equal_range(__key); }
371
erase(const key_type & __key)372 size_type erase(const key_type& __key) {return _M_ht.erase(__key); }
erase(iterator __it)373 void erase(iterator __it) { _M_ht.erase(__it); }
erase(iterator __f,iterator __l)374 void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
clear()375 void clear() { _M_ht.clear(); }
376
377 public:
resize(size_type __hint)378 void resize(size_type __hint) { _M_ht.resize(__hint); }
bucket_count()379 size_type bucket_count() const { return _M_ht.bucket_count(); }
max_bucket_count()380 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
elems_in_bucket(size_type __n)381 size_type elems_in_bucket(size_type __n) const
382 { return _M_ht.elems_in_bucket(__n); }
383 };
384
385 template <class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
386 inline bool
387 operator==(const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm1,
388 const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm2)
389 {
390 return __hm1._M_ht == __hm2._M_ht;
391 }
392
393 #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
394
395 template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc>
396 inline void
swap(hash_multimap<_Key,_Tp,_HashFcn,_EqlKey,_Alloc> & __hm1,hash_multimap<_Key,_Tp,_HashFcn,_EqlKey,_Alloc> & __hm2)397 swap(hash_multimap<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1,
398 hash_multimap<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2)
399 {
400 __hm1.swap(__hm2);
401 }
402
403 #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
404
405 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
406 #pragma reset woff 1174
407 #pragma reset woff 1375
408 #endif
409
410 __STL_END_NAMESPACE
411
412 #endif /* __SGI_STL_INTERNAL_HASH_MAP_H */
413
414 // Local Variables:
415 // mode:C++
416 // End:
417