1/*
2 * Copyright (c) 2004
3 * Francois Dumont
4 *
5 * This material is provided "as is", with absolutely no warranty expressed
6 * or implied. Any use is at your own risk.
7 *
8 * Permission to use or copy this software for any purpose is hereby granted
9 * without fee, provided the above notices are retained on all copies.
10 * Permission to modify the code and to distribute modified code is granted,
11 * provided the above notices are retained, and a notice that the code was
12 * modified is included with the above copyright notice.
13 *
14 */
15
16/* NOTE: This is an internal header file, included by other STL headers.
17 *   You should not attempt to use it directly.
18 */
19
20#ifndef _STLP_INTERNAL_UNORDERED_MAP_H
21#define _STLP_INTERNAL_UNORDERED_MAP_H
22
23#ifndef _STLP_INTERNAL_HASHTABLE_H
24#  include <stl/_hashtable.h>
25#endif
26
27_STLP_BEGIN_NAMESPACE
28
29//Specific iterator traits creation
30_STLP_CREATE_HASH_ITERATOR_TRAITS(UnorderedMapTraitsT, traits)
31
32_STLP_BEGIN_TR1_NAMESPACE
33
34template <class _Key, class _Tp, _STLP_DFL_TMPL_PARAM(_HashFcn,hash<_Key>),
35          _STLP_DFL_TMPL_PARAM(_EqualKey, equal_to<_Key>),
36          _STLP_DEFAULT_PAIR_ALLOCATOR_SELECT(_STLP_CONST _Key, _Tp) >
37class unordered_map
38#if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND)
39               : public __stlport_class<unordered_map<_Key, _Tp, _HashFcn, _EqualKey, _Alloc> >
40#endif
41{
42private:
43  typedef unordered_map<_Key, _Tp, _HashFcn, _EqualKey, _Alloc> _Self;
44public:
45  typedef _Key key_type;
46  typedef _Tp data_type;
47  typedef _Tp mapped_type;
48  typedef pair<_STLP_CONST key_type, data_type> value_type;
49private:
50  //Specific iterator traits creation
51  typedef _STLP_PRIV _UnorderedMapTraitsT<value_type> _UnorderedMapTraits;
52
53public:
54  typedef hashtable<value_type, key_type, _HashFcn, _UnorderedMapTraits,
55                    _STLP_SELECT1ST(value_type,  _Key), _EqualKey, _Alloc > _Ht;
56
57  typedef typename _Ht::hasher hasher;
58  typedef typename _Ht::key_equal key_equal;
59
60  typedef typename _Ht::size_type size_type;
61  typedef typename _Ht::difference_type difference_type;
62  typedef typename _Ht::pointer pointer;
63  typedef typename _Ht::const_pointer const_pointer;
64  typedef typename _Ht::reference reference;
65  typedef typename _Ht::const_reference const_reference;
66
67  typedef typename _Ht::iterator iterator;
68  typedef typename _Ht::const_iterator const_iterator;
69  typedef typename _Ht::local_iterator local_iterator;
70  typedef typename _Ht::const_local_iterator const_local_iterator;
71
72  typedef typename _Ht::allocator_type allocator_type;
73
74  hasher hash_function() const { return _M_ht.hash_funct(); }
75  key_equal key_eq() const { return _M_ht.key_eq(); }
76  allocator_type get_allocator() const { return _M_ht.get_allocator(); }
77
78private:
79  _Ht _M_ht;
80  _STLP_KEY_TYPE_FOR_CONT_EXT(key_type)
81
82public:
83  explicit unordered_map(size_type __n = 0, const hasher& __hf = hasher(),
84                         const key_equal& __eql = key_equal(),
85                         const allocator_type& __a = allocator_type())
86    : _M_ht(__n, __hf, __eql, __a) {}
87
88#if !defined (_STLP_NO_MOVE_SEMANTIC)
89  unordered_map(__move_source<_Self> src)
90    : _M_ht(__move_source<_Ht>(src.get()._M_ht)) {}
91#endif
92
93#if defined (_STLP_MEMBER_TEMPLATES)
94  template <class _InputIterator>
95  unordered_map(_InputIterator __f, _InputIterator __l,
96                size_type __n = 0, const hasher& __hf = hasher(),
97                const key_equal& __eql = key_equal(),
98                const allocator_type& __a = allocator_type())
99    : _M_ht(__n, __hf, __eql, __a)
100  { _M_ht.insert_unique(__f, __l); }
101#else
102  unordered_map(const value_type* __f, const value_type* __l,
103                size_type __n = 0, const hasher& __hf = hasher(),
104                const key_equal& __eql = key_equal(),
105                const allocator_type& __a = allocator_type())
106    : _M_ht(__n, __hf, __eql, __a)
107  { _M_ht.insert_unique(__f, __l); }
108
109  unordered_map(const_iterator __f, const_iterator __l,
110                size_type __n = 0, const hasher& __hf = hasher(),
111                const key_equal& __eql = key_equal(),
112                const allocator_type& __a = allocator_type())
113    : _M_ht(__n, __hf, __eql, __a)
114  { _M_ht.insert_unique(__f, __l); }
115#endif /*_STLP_MEMBER_TEMPLATES */
116
117  _Self& operator = (const _Self& __other)
118  { _M_ht = __other._M_ht; return *this; }
119
120  size_type size() const { return _M_ht.size(); }
121  size_type max_size() const { return _M_ht.max_size(); }
122  bool empty() const { return _M_ht.empty(); }
123  void swap(_Self& __hs) { _M_ht.swap(__hs._M_ht); }
124#if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER)
125  void _M_swap_workaround(_Self& __x) { swap(__x); }
126#endif
127
128  iterator begin() { return _M_ht.begin(); }
129  iterator end() { return _M_ht.end(); }
130  const_iterator begin() const { return _M_ht.begin(); }
131  const_iterator end() const { return _M_ht.end(); }
132
133  pair<iterator,bool> insert(const value_type& __obj)
134  { return _M_ht.insert_unique(__obj); }
135  iterator insert(const_iterator /*__hint*/, const value_type& __obj)
136  { return _M_ht.insert_unique(__obj); }
137#if defined (_STLP_MEMBER_TEMPLATES)
138  template <class _InputIterator>
139  void insert(_InputIterator __f, _InputIterator __l)
140#else
141  void insert(const value_type* __f, const value_type* __l)
142  { _M_ht.insert_unique(__f,__l); }
143  void insert(const_iterator __f, const_iterator __l)
144#endif /*_STLP_MEMBER_TEMPLATES */
145  { _M_ht.insert_unique(__f, __l); }
146
147  _STLP_TEMPLATE_FOR_CONT_EXT
148  iterator find(const _KT& __key) { return _M_ht.find(__key); }
149  _STLP_TEMPLATE_FOR_CONT_EXT
150  const_iterator find(const _KT& __key) const { return _M_ht.find(__key); }
151
152  _STLP_TEMPLATE_FOR_CONT_EXT
153  _Tp& operator[](const _KT& __key) {
154    iterator __it = _M_ht.find(__key);
155    return (__it == _M_ht.end() ?
156      _M_ht._M_insert(value_type(__key, _STLP_DEFAULT_CONSTRUCTED(_Tp))).second :
157      (*__it).second );
158  }
159
160  _STLP_TEMPLATE_FOR_CONT_EXT
161  size_type count(const _KT& __key) const { return _M_ht.count(__key); }
162
163  _STLP_TEMPLATE_FOR_CONT_EXT
164  pair<iterator, iterator> equal_range(const _KT& __key)
165  { return _M_ht.equal_range(__key); }
166  _STLP_TEMPLATE_FOR_CONT_EXT
167  pair<const_iterator, const_iterator> equal_range(const _KT& __key) const
168  { return _M_ht.equal_range(__key); }
169
170  size_type erase(const key_type& __key) {return _M_ht.erase(__key); }
171  void erase(const_iterator __it) { _M_ht.erase(__it); }
172  void erase(const_iterator __f, const_iterator __l) { _M_ht.erase(__f, __l); }
173  void clear() { _M_ht.clear(); }
174
175  size_type bucket_count() const { return _M_ht.bucket_count(); }
176  size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
177  size_type bucket_size(size_type __n) const { return _M_ht.elems_in_bucket(__n); }
178  _STLP_TEMPLATE_FOR_CONT_EXT
179  size_type bucket(const _KT& __k) const { return _M_ht.bucket(__k); }
180  local_iterator begin(size_type __n) { return _M_ht.begin(__n); }
181  local_iterator end(size_type __n) { return _M_ht.end(__n); }
182  const_local_iterator begin(size_type __n) const { return _M_ht.begin(__n); }
183  const_local_iterator end(size_type __n) const { return _M_ht.end(__n); }
184
185  float load_factor() const { return _M_ht.load_factor(); }
186  float max_load_factor() const { return _M_ht.max_load_factor(); }
187  void max_load_factor(float __val) { _M_ht.max_load_factor(__val); }
188  void rehash(size_type __hint) { _M_ht.rehash(__hint); }
189
190#if defined (__DMC__) // disable operator==(pair<x,unordered_map>, pair<x,unordered_map>)
191  bool operator==(const _Self&) const;
192#endif
193};
194
195_STLP_END_NAMESPACE
196
197//Specific iterator traits creation
198_STLP_CREATE_HASH_ITERATOR_TRAITS(UnorderedMultimapTraitsT, traits)
199
200_STLP_BEGIN_TR1_NAMESPACE
201
202template <class _Key, class _Tp, _STLP_DFL_TMPL_PARAM(_HashFcn,hash<_Key>),
203          _STLP_DFL_TMPL_PARAM(_EqualKey, equal_to<_Key>),
204          _STLP_DEFAULT_PAIR_ALLOCATOR_SELECT(_STLP_CONST _Key, _Tp) >
205class unordered_multimap
206#if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND)
207                    : public __stlport_class<unordered_multimap<_Key, _Tp, _HashFcn, _EqualKey, _Alloc> >
208#endif
209{
210private:
211  typedef unordered_multimap<_Key, _Tp, _HashFcn, _EqualKey, _Alloc> _Self;
212public:
213  typedef _Key key_type;
214  typedef _Tp data_type;
215  typedef _Tp mapped_type;
216  typedef pair<_STLP_CONST key_type, data_type> value_type;
217private:
218  //Specific iterator traits creation
219  typedef _STLP_PRIV _UnorderedMultimapTraitsT<value_type> _UnorderedMultimapTraits;
220
221public:
222  typedef hashtable<value_type, key_type, _HashFcn, _UnorderedMultimapTraits,
223                    _STLP_SELECT1ST(value_type,  _Key), _EqualKey, _Alloc > _Ht;
224
225  typedef typename _Ht::hasher hasher;
226  typedef typename _Ht::key_equal key_equal;
227
228  typedef typename _Ht::size_type size_type;
229  typedef typename _Ht::difference_type difference_type;
230  typedef typename _Ht::pointer pointer;
231  typedef typename _Ht::const_pointer const_pointer;
232  typedef typename _Ht::reference reference;
233  typedef typename _Ht::const_reference const_reference;
234
235  typedef typename _Ht::iterator iterator;
236  typedef typename _Ht::const_iterator const_iterator;
237  typedef typename _Ht::local_iterator local_iterator;
238  typedef typename _Ht::const_local_iterator const_local_iterator;
239
240  typedef typename _Ht::allocator_type allocator_type;
241
242  hasher hash_function() const { return _M_ht.hash_funct(); }
243  key_equal key_eq() const { return _M_ht.key_eq(); }
244  allocator_type get_allocator() const { return _M_ht.get_allocator(); }
245
246private:
247  _Ht _M_ht;
248  _STLP_KEY_TYPE_FOR_CONT_EXT(key_type)
249
250public:
251  explicit unordered_multimap(size_type __n = 0, const hasher& __hf = hasher(),
252                              const key_equal& __eql = key_equal(),
253                              const allocator_type& __a = allocator_type())
254    : _M_ht(__n, __hf, __eql, __a) {}
255
256#if !defined (_STLP_NO_MOVE_SEMANTIC)
257  unordered_multimap(__move_source<_Self> src)
258    : _M_ht(__move_source<_Ht>(src.get()._M_ht)) {}
259#endif
260
261#if defined (_STLP_MEMBER_TEMPLATES)
262  template <class _InputIterator>
263  unordered_multimap(_InputIterator __f, _InputIterator __l,
264                     size_type __n = 0, const hasher& __hf = hasher(),
265                     const key_equal& __eql = key_equal(),
266                     const allocator_type& __a = allocator_type())
267    : _M_ht(__n, __hf, __eql, __a)
268  { _M_ht.insert_equal(__f, __l); }
269#else
270  unordered_multimap(const value_type* __f, const value_type* __l,
271                     size_type __n = 0, const hasher& __hf = hasher(),
272                     const key_equal& __eql = key_equal(),
273                     const allocator_type& __a = allocator_type())
274    : _M_ht(__n, __hf, __eql, __a)
275  { _M_ht.insert_equal(__f, __l); }
276
277  unordered_multimap(const_iterator __f, const_iterator __l,
278                     size_type __n = 0, const hasher& __hf = hasher(),
279                     const key_equal& __eql = key_equal(),
280                     const allocator_type& __a = allocator_type())
281    : _M_ht(__n, __hf, __eql, __a)
282  { _M_ht.insert_equal(__f, __l); }
283#endif /*_STLP_MEMBER_TEMPLATES */
284
285  _Self& operator = (const _Self& __other)
286  { _M_ht = __other._M_ht; return *this; }
287
288  size_type size() const { return _M_ht.size(); }
289  size_type max_size() const { return _M_ht.max_size(); }
290  bool empty() const { return _M_ht.empty(); }
291  void swap(_Self& __hs) { _M_ht.swap(__hs._M_ht); }
292#if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER)
293  void _M_swap_workaround(_Self& __x) { swap(__x); }
294#endif
295
296  iterator begin() { return _M_ht.begin(); }
297  iterator end() { return _M_ht.end(); }
298  const_iterator begin() const { return _M_ht.begin(); }
299  const_iterator end() const { return _M_ht.end(); }
300
301  iterator insert(const value_type& __obj)
302  { return _M_ht.insert_equal(__obj); }
303  iterator insert(const_iterator /*__hint*/, const value_type& __obj)
304  { return _M_ht.insert_equal(__obj); }
305#if defined (_STLP_MEMBER_TEMPLATES)
306  template <class _InputIterator>
307  void insert(_InputIterator __f, _InputIterator __l)
308#else
309  void insert(const value_type* __f, const value_type* __l)
310  { _M_ht.insert_equal(__f,__l); }
311  void insert(const_iterator __f, const_iterator __l)
312#endif /*_STLP_MEMBER_TEMPLATES */
313  { _M_ht.insert_equal(__f, __l); }
314
315  _STLP_TEMPLATE_FOR_CONT_EXT
316  iterator find(const _KT& __key) { return _M_ht.find(__key); }
317  _STLP_TEMPLATE_FOR_CONT_EXT
318  const_iterator find(const _KT& __key) const { return _M_ht.find(__key); }
319
320  _STLP_TEMPLATE_FOR_CONT_EXT
321  size_type count(const _KT& __key) const { return _M_ht.count(__key); }
322
323  _STLP_TEMPLATE_FOR_CONT_EXT
324  pair<iterator, iterator> equal_range(const _KT& __key)
325  { return _M_ht.equal_range(__key); }
326  _STLP_TEMPLATE_FOR_CONT_EXT
327  pair<const_iterator, const_iterator> equal_range(const _KT& __key) const
328  { return _M_ht.equal_range(__key); }
329
330  size_type erase(const key_type& __key) {return _M_ht.erase(__key); }
331  void erase(const_iterator __it) { _M_ht.erase(__it); }
332  void erase(const_iterator __f, const_iterator __l) { _M_ht.erase(__f, __l); }
333  void clear() { _M_ht.clear(); }
334
335  size_type bucket_count() const { return _M_ht.bucket_count(); }
336  size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
337  size_type bucket_size(size_type __n) const { return _M_ht.elems_in_bucket(__n); }
338  _STLP_TEMPLATE_FOR_CONT_EXT
339  size_type bucket(const _KT& __k) const { return _M_ht.bucket(__k); }
340  local_iterator begin(size_type __n) { return _M_ht.begin(__n); }
341  local_iterator end(size_type __n) { return _M_ht.end(__n); }
342  const_local_iterator begin(size_type __n) const { return _M_ht.begin(__n); }
343  const_local_iterator end(size_type __n) const { return _M_ht.end(__n); }
344
345  float load_factor() const { return _M_ht.load_factor(); }
346  float max_load_factor() const { return _M_ht.max_load_factor(); }
347  void max_load_factor(float __val) { _M_ht.max_load_factor(__val); }
348  void rehash(size_type __hint) { _M_ht.rehash(__hint); }
349};
350
351#define _STLP_TEMPLATE_HEADER template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc>
352#define _STLP_TEMPLATE_CONTAINER unordered_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>
353
354#include <stl/_relops_hash_cont.h>
355
356#undef _STLP_TEMPLATE_CONTAINER
357#define _STLP_TEMPLATE_CONTAINER unordered_multimap<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>
358
359#include <stl/_relops_hash_cont.h>
360
361#undef _STLP_TEMPLATE_CONTAINER
362#undef _STLP_TEMPLATE_HEADER
363
364_STLP_END_NAMESPACE
365
366// Specialization of insert_iterator so that it will work for unordered_map
367// and unordered_multimap.
368
369#if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
370#  if !defined (_STLP_NO_MOVE_SEMANTIC)
371template <class _Key, class _Tp, class _HashFn,  class _EqKey, class _Alloc>
372struct __move_traits<_STLP_TR1 unordered_map<_Key, _Tp, _HashFn, _EqKey, _Alloc> > :
373  _STLP_PRIV __move_traits_help<typename _STLP_TR1 unordered_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>::_Ht>
374{};
375
376template <class _Key, class _Tp, class _HashFn,  class _EqKey, class _Alloc>
377struct __move_traits<_STLP_TR1 unordered_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc> > :
378  _STLP_PRIV __move_traits_help<typename _STLP_TR1 unordered_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>::_Ht>
379{};
380#  endif
381
382template <class _Key, class _Tp, class _HashFn,  class _EqKey, class _Alloc>
383class insert_iterator<_STLP_TR1 unordered_map<_Key, _Tp, _HashFn, _EqKey, _Alloc> > {
384protected:
385  typedef _STLP_TR1 unordered_map<_Key, _Tp, _HashFn, _EqKey, _Alloc> _Container;
386  _Container* container;
387public:
388  typedef _Container          container_type;
389  typedef output_iterator_tag iterator_category;
390  typedef void                value_type;
391  typedef void                difference_type;
392  typedef void                pointer;
393  typedef void                reference;
394
395  insert_iterator(_Container& __x) : container(&__x) {}
396  insert_iterator(_Container& __x, typename _Container::iterator)
397    : container(&__x) {}
398  insert_iterator<_Container>&
399  operator=(const typename _Container::value_type& __val) {
400    container->insert(__val);
401    return *this;
402  }
403  insert_iterator<_Container>& operator*() { return *this; }
404  insert_iterator<_Container>& operator++() { return *this; }
405  insert_iterator<_Container>& operator++(int) { return *this; }
406};
407
408template <class _Key, class _Tp, class _HashFn,  class _EqKey, class _Alloc>
409class insert_iterator<_STLP_TR1 unordered_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc> > {
410protected:
411  typedef _STLP_TR1 unordered_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc> _Container;
412  _Container* container;
413  typename _Container::iterator iter;
414public:
415  typedef _Container          container_type;
416  typedef output_iterator_tag iterator_category;
417  typedef void                value_type;
418  typedef void                difference_type;
419  typedef void                pointer;
420  typedef void                reference;
421
422  insert_iterator(_Container& __x) : container(&__x) {}
423  insert_iterator(_Container& __x, typename _Container::iterator)
424    : container(&__x) {}
425  insert_iterator<_Container>&
426  operator=(const typename _Container::value_type& __val) {
427    container->insert(__val);
428    return *this;
429  }
430  insert_iterator<_Container>& operator*() { return *this; }
431  insert_iterator<_Container>& operator++() { return *this; }
432  insert_iterator<_Container>& operator++(int) { return *this; }
433};
434
435#endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
436
437_STLP_END_NAMESPACE
438
439#endif /* _STLP_INTERNAL_UNORDERED_MAP_H */
440
441// Local Variables:
442// mode:C++
443// End:
444