ReactOS  0.4.13-dev-464-g6b95727
_hashtable.h
Go to the documentation of this file.
1 /*
2  *
3  * Copyright (c) 1994
4  * Hewlett-Packard Company
5  *
6  * Copyright (c) 1996,1997
7  * Silicon Graphics Computer Systems, Inc.
8  *
9  * Copyright (c) 1997
10  * Moscow Center for SPARC Technology
11  *
12  * Copyright (c) 1999
13  * Boris Fomitchev
14  *
15  * This material is provided "as is", with absolutely no warranty expressed
16  * or implied. Any use is at your own risk.
17  *
18  * Permission to use or copy this software for any purpose is hereby granted
19  * without fee, provided the above notices are retained on all copies.
20  * Permission to modify the code and to distribute modified code is granted,
21  * provided the above notices are retained, and a notice that the code was
22  * modified is included with the above copyright notice.
23  *
24  */
25 
26 /* NOTE: This is an internal header file, included by other STL headers.
27  * You should not attempt to use it directly.
28  */
29 
30 #ifndef _STLP_INTERNAL_HASHTABLE_H
31 #define _STLP_INTERNAL_HASHTABLE_H
32 
33 #ifndef _STLP_INTERNAL_VECTOR_H
34 # include <stl/_vector.h>
35 #endif
36 
37 #ifndef _STLP_INTERNAL_SLIST_H
38 # include <stl/_slist.h>
39 #endif
40 
41 #ifndef _STLP_INTERNAL_ITERATOR_H
42 # include <stl/_iterator.h>
43 #endif
44 
45 #ifndef _STLP_INTERNAL_FUNCTION_BASE_H
46 # include <stl/_function_base.h>
47 #endif
48 
49 #ifndef _STLP_INTERNAL_ALGOBASE_H
50 # include <stl/_algobase.h>
51 #endif
52 
53 #ifndef _STLP_HASH_FUN_H
54 # include <stl/_hash_fun.h>
55 #endif
56 
57 /*
58  * Hashtable class, used to implement the hashed associative containers
59  * hash_set, hash_map, hash_multiset, hash_multimap,
60  * unordered_set, unordered_map, unordered_multiset, unordered_multimap.
61  */
62 
64 
65 #if defined (_STLP_USE_TEMPLATE_EXPORT)
66 //Export of the classes used to represent buckets in the hashtable implementation.
67 # if !defined (_STLP_USE_PTR_SPECIALIZATIONS)
68 //If pointer specialization is enabled vector<_Slist_node_base*> will use the void*
69 //storage type for which internal classes have already been exported.
71 
78 # endif
79 
80 # if defined (_STLP_DEBUG)
82 # define _STLP_NON_DBG_VECTOR _STLP_NON_DBG_NAME(vector)
84 _STLP_EXPORT_TEMPLATE_CLASS _STLP_NON_DBG_VECTOR<_Slist_node_base*, allocator<_Slist_node_base*> >;
85 # undef _STLP_NON_DBG_VECTOR
87 # endif
88 
91 #endif
92 
93 #if defined (_STLP_DEBUG)
94 # define hashtable _STLP_NON_DBG_NAME(hashtable)
96 #endif
97 
98 // some compilers require the names of template parameters to be the same
99 template <class _Val, class _Key, class _HF,
100  class _Traits, class _ExK, class _EqK, class _All>
101 class hashtable;
102 
103 #if !defined (_STLP_DEBUG)
105 #endif
106 
107 template <class _BaseIte, class _Traits>
108 struct _Ht_iterator {
109  typedef typename _Traits::_ConstTraits _ConstTraits;
110  typedef typename _Traits::_NonConstTraits _NonConstTraits;
111 
113 
114  typedef typename _Traits::value_type value_type;
115  typedef typename _Traits::pointer pointer;
116  typedef typename _Traits::reference reference;
119  typedef size_t size_type;
120 
123 
125  //copy constructor for iterator and constructor from iterator for const_iterator
127  _Ht_iterator(_BaseIte __it) : _M_ite(__it) {}
128 
130  return *_M_ite;
131  }
133 
135  ++_M_ite;
136  return *this;
137  }
139  _Self __tmp = *this;
140  ++*this;
141  return __tmp;
142  }
143 
144  bool operator == (const_iterator __rhs) const {
145  return _M_ite == __rhs._M_ite;
146  }
147  bool operator != (const_iterator __rhs) const {
148  return _M_ite != __rhs._M_ite;
149  }
150 
151  _BaseIte _M_ite;
152 };
153 
155 
156 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
157 template <class _BaseIte, class _Traits>
158 struct __type_traits<_STLP_PRIV _Ht_iterator<_BaseIte, _Traits> > {
163  typedef __false_type is_POD_type;
164 };
165 #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
166 
167 #if defined (_STLP_USE_OLD_HP_ITERATOR_QUERIES)
168 template <class _BaseIte, class _Traits>
169 inline
170 # if defined (_STLP_NESTED_TYPE_PARAM_BUG)
171 _STLP_TYPENAME_ON_RETURN_TYPE _Traits::value_type *
172 # else
174 # endif
175 value_type(const _STLP_PRIV _Ht_iterator<_BaseIte,_Traits>&) {
177  return (_Val*) 0;
178 }
179 template <class _BaseIte, class _Traits>
180 inline forward_iterator_tag iterator_category(const _STLP_PRIV _Ht_iterator<_BaseIte,_Traits>&)
181 { return forward_iterator_tag(); }
182 template <class _BaseIte, class _Traits>
183 inline ptrdiff_t* distance_type(const _STLP_PRIV _Ht_iterator<_BaseIte,_Traits>&)
184 { return (ptrdiff_t*) 0; }
185 #endif
186 
188 
189 template <class _Dummy>
190 class _Stl_prime {
191  // Returns begining of primes list and size by reference.
192  static const size_t* _S_primes(size_t&);
193 public:
194  //Returns the maximum number of buckets handled by the hashtable implementation
195  static size_t _STLP_CALL _S_max_nb_buckets();
196 
197  //Returns the bucket size next to a required size
198  static size_t _STLP_CALL _S_next_size(size_t);
199 
200  // Returns the bucket range containing sorted list of prime numbers <= __hint.
201  static void _STLP_CALL _S_prev_sizes(size_t __hint, const size_t *&__begin, const size_t *&__end);
202 };
203 
204 #if defined (_STLP_USE_TEMPLATE_EXPORT)
206 #endif
207 
209 
210 #if !defined (_STLP_DEBUG)
212 #endif
213 
214 /*
215  * Hashtables handle allocators a bit differently than other containers
216  * do. If we're using standard-conforming allocators, then a hashtable
217  * unconditionally has a member variable to hold its allocator, even if
218  * it so happens that all instances of the allocator type are identical.
219  * This is because, for hashtables, this extra storage is negligible.
220  * Additionally, a base class wouldn't serve any other purposes; it
221  * wouldn't, for example, simplify the exception-handling code.
222  */
223 template <class _Val, class _Key, class _HF,
224  class _Traits, class _ExK, class _EqK, class _All>
225 class hashtable {
227  typedef typename _Traits::_NonConstTraits _NonConstTraits;
228  typedef typename _Traits::_ConstTraits _ConstTraits;
229  typedef typename _Traits::_NonConstLocalTraits _NonConstLocalTraits;
230  typedef typename _Traits::_ConstLocalTraits _ConstLocalTraits;
231 
232 public:
233  typedef _Key key_type;
234  typedef _Val value_type;
235  typedef _HF hasher;
236  typedef _EqK key_equal;
237 
238  typedef size_t size_type;
241  typedef const value_type* const_pointer;
243  typedef const value_type& const_reference;
245 
246  hasher hash_funct() const { return _M_hash; }
247  key_equal key_eq() const { return _M_equals; }
248 
249 private:
251 #if defined (_STLP_DEBUG)
252  typedef _STLP_PRIV _STLP_NON_DBG_NAME(slist)<value_type, _All> _ElemsCont;
253 #else
255 #endif
256  typedef typename _ElemsCont::iterator _ElemsIte;
260  /*
261  * We are going to use vector of _Slist_node_base pointers for 2 reasons:
262  * - limit code bloat, all hashtable instanciation use the same buckets representation.
263  * - avoid _STLP_DEBUG performance trouble: with a vector of iterator on slist the resize
264  * method would be too slow because the slist::splice_after method become linear on
265  * the number of iterators in the buckets rather than constant in time as the iterator
266  * has to be move from a slist to the other.
267  */
268 #if defined (_STLP_DEBUG)
269  typedef _STLP_PRIV _STLP_NON_DBG_NAME(vector)<_BucketType*, _BucketAllocType> _BucketVector;
270 #else
272 #endif
273 
281 
283  _ExK k;
284  return k(__val);
285  }
286 public:
289  //TODO: Avoids this debug check and make the local_iterator different from
290  //iterator in debug mode too.
291 #if !defined (_STLP_DEBUG)
294 #else
295  typedef iterator local_iterator;
297 #endif
298 
299  typedef _All allocator_type;
301 
302 #if !defined (_STLP_DONT_SUP_DFLT_PARAM)
304  const _HF& __hf,
305  const _EqK& __eql,
306  const allocator_type& __a = allocator_type())
307 #else
309  const _HF& __hf,
310  const _EqK& __eql)
311  : _M_hash(__hf),
312  _M_equals(__eql),
315  _M_num_elements(0),
318 
320  const _HF& __hf,
321  const _EqK& __eql,
322  const allocator_type& __a)
323 #endif
324  : _M_hash(__hf),
325  _M_equals(__eql),
326  _M_elems(__a),
328  _M_num_elements(0),
331 
332  hashtable(const _Self& __ht)
333  : _M_hash(__ht._M_hash),
334  _M_equals(__ht._M_equals),
335  _M_elems(__ht.get_allocator()),
337  _M_num_elements(0),
339  { _M_copy_from(__ht); }
340 
341 #if !defined (_STLP_NO_MOVE_SEMANTIC)
349 #endif
350 
351  _Self& operator= (const _Self& __ht) {
352  if (&__ht != this) {
353  clear();
354  _M_hash = __ht._M_hash;
355  _M_equals = __ht._M_equals;
356  _M_copy_from(__ht);
357  }
358  return *this;
359  }
360 
361  ~hashtable() { clear(); }
362 
363  size_type size() const { return _M_num_elements; }
364  size_type max_size() const { return size_type(-1); }
365  bool empty() const { return size() == 0; }
366 
367  void swap(_Self& __ht) {
370  _M_elems.swap(__ht._M_elems);
371  _M_buckets.swap(__ht._M_buckets);
374  }
375 
376  iterator begin() { return _M_elems.begin(); }
377  iterator end() { return _M_elems.end(); }
380 
381  const_iterator begin() const { return __CONST_CAST(_ElemsCont&, _M_elems).begin(); }
382  const_iterator end() const { return __CONST_CAST(_ElemsCont&, _M_elems).end(); }
385 
386  //static bool _STLP_CALL _M_equal (const _Self&, const _Self&);
387 
388 public:
389  //The number of buckets is size() - 1 because the last bucket always contains
390  //_M_elems.end() to make algo easier to implement.
391  size_type bucket_count() const { return _M_buckets.size() - 1; }
394  { return _STLP_STD::distance(_ElemsIte(_M_buckets[__bucket]), _ElemsIte(_M_buckets[__bucket + 1])); }
395 
397  size_type bucket(const _KT& __k) const { return _M_bkt_num_key(__k); }
398 
399  // hash policy
400  float load_factor() const { return (float)size() / (float)bucket_count(); }
401  float max_load_factor() const { return _M_max_load_factor; }
402  void max_load_factor(float __z) {
403  _M_max_load_factor = __z;
404  _M_resize();
405  }
406 
409  return insert_unique_noresize(__obj);
410  }
411 
414  return insert_equal_noresize(__obj);
415  }
416 
417 protected:
419 public:
422 
423 #if defined (_STLP_MEMBER_TEMPLATES)
424  template <class _InputIterator>
425  void insert_unique(_InputIterator __f, _InputIterator __l)
426  { insert_unique(__f, __l, _STLP_ITERATOR_CATEGORY(__f, _InputIterator)); }
427 
428  template <class _InputIterator>
429  void insert_equal(_InputIterator __f, _InputIterator __l)
430  { insert_equal(__f, __l, _STLP_ITERATOR_CATEGORY(__f, _InputIterator)); }
431 
432  template <class _InputIterator>
433  void insert_unique(_InputIterator __f, _InputIterator __l,
434  const input_iterator_tag &) {
435  for ( ; __f != __l; ++__f)
436  insert_unique(*__f);
437  }
438 
439  template <class _InputIterator>
440  void insert_equal(_InputIterator __f, _InputIterator __l,
441  const input_iterator_tag &) {
442  for ( ; __f != __l; ++__f)
443  insert_equal(*__f);
444  }
445 
446  template <class _ForwardIterator>
447  void insert_unique(_ForwardIterator __f, _ForwardIterator __l,
448  const forward_iterator_tag &) {
449  size_type __n = _STLP_STD::distance(__f, __l);
451  for ( ; __n > 0; --__n, ++__f)
453  }
454 
455  template <class _ForwardIterator>
456  void insert_equal(_ForwardIterator __f, _ForwardIterator __l,
457  const forward_iterator_tag &) {
458  size_type __n = _STLP_STD::distance(__f, __l);
460  for ( ; __n > 0; --__n, ++__f)
461  insert_equal_noresize(*__f);
462  }
463 
464 #else /* _STLP_MEMBER_TEMPLATES */
465  void insert_unique(const value_type* __f, const value_type* __l) {
466  size_type __n = __l - __f;
468  for ( ; __n > 0; --__n, ++__f)
470  }
471 
472  void insert_equal(const value_type* __f, const value_type* __l) {
473  size_type __n = __l - __f;
475  for ( ; __n > 0; --__n, ++__f)
476  insert_equal_noresize(*__f);
477  }
478 
480  size_type __n = _STLP_STD::distance(__f, __l);
482  for ( ; __n > 0; --__n, ++__f)
484  }
485 
487  size_type __n = _STLP_STD::distance(__f, __l);
489  for ( ; __n > 0; --__n, ++__f)
490  insert_equal_noresize(*__f);
491  }
492 #endif /*_STLP_MEMBER_TEMPLATES */
493 
494  //reference find_or_insert(const value_type& __obj);
495 
496 private:
498  _ElemsIte _M_find(const _KT& __key) const {
499  size_type __n = _M_bkt_num_key(__key);
500  _ElemsIte __first(_M_buckets[__n]);
502  for ( ; (__first != __last) && !_M_equals(_M_get_key(*__first), __key); ++__first);
503  if (__first != __last)
504  return __first;
505  else
506  return __CONST_CAST(_ElemsCont&, _M_elems).end();
507  }
508 
509 public:
511  iterator find(const _KT& __key) { return _M_find(__key); }
513  const_iterator find(const _KT& __key) const { return _M_find(__key); }
514 
516  size_type count(const _KT& __key) const {
517  const size_type __n = _M_bkt_num_key(__key);
518 
519  _ElemsIte __cur(_M_buckets[__n]);
521  for (; __cur != __last; ++__cur) {
522  if (_M_equals(_M_get_key(*__cur), __key)) {
523  size_type __result = 1;
524  for (++__cur;
525  __cur != __last && _M_equals(_M_get_key(*__cur), __key);
526  ++__result, ++__cur);
527  return __result;
528  }
529  }
530  return 0;
531  }
532 
535  typedef pair<iterator, iterator> _Pii;
536  const size_type __n = _M_bkt_num_key(__key);
537 
538  for (_ElemsIte __first(_M_buckets[__n]), __last(_M_buckets[__n + 1]);
539  __first != __last; ++__first) {
540  if (_M_equals(_M_get_key(*__first), __key)) {
541  _ElemsIte __cur(__first);
542  for (++__cur; (__cur != __last) && _M_equals(_M_get_key(*__cur), __key); ++__cur);
543  return _Pii(__first, __cur);
544  }
545  }
546  return _Pii(end(), end());
547  }
548 
552  const size_type __n = _M_bkt_num_key(__key);
553 
554  for (_ElemsIte __first(_M_buckets[__n]), __last(_M_buckets[__n + 1]);
555  __first != __last; ++__first) {
556  if (_M_equals(_M_get_key(*__first), __key)) {
557  _ElemsIte __cur(__first);
558  for (++__cur; (__cur != __last) && _M_equals(_M_get_key(*__cur), __key); ++__cur);
559  return _Pii(__first, __cur);
560  }
561  }
562  return _Pii(end(), end());
563  }
564 
565  size_type erase(const key_type& __key);
566  void erase(const_iterator __it);
567  void erase(const_iterator __first, const_iterator __last);
568 
569 private:
570  void _M_enlarge(size_type __n);
571  void _M_reduce();
572  void _M_resize();
573  void _M_rehash(size_type __num_buckets);
574 #if defined (_STLP_DEBUG)
575  void _M_check() const;
576 #endif
577 
578 public:
579  void rehash(size_type __num_buckets_hint);
580  void resize(size_type __num_buckets_hint)
581  { rehash(__num_buckets_hint); }
582  void clear();
583 
584  // this is for hash_map::operator[]
585  reference _M_insert(const value_type& __obj);
586 
587 private:
588  //__n is set to the first bucket that has to be modified if any
589  //erase/insert operation is done after the returned iterator.
591 
592  static iterator _S_before_begin(const _ElemsCont& __elems, const _BucketVector& __buckets,
593  size_type &__n);
594 
596  const size_type __n_buckets = _STLP_PRIV _Stl_prime_type::_S_next_size(__n) + 1;
597  _M_buckets.reserve(__n_buckets);
598  _M_buckets.assign(__n_buckets, __STATIC_CAST(_BucketType*, 0));
599  }
600 
602  size_type _M_bkt_num_key(const _KT& __key) const
603  { return _M_bkt_num_key(__key, bucket_count()); }
604 
605  size_type _M_bkt_num(const value_type& __obj) const
606  { return _M_bkt_num_key(_M_get_key(__obj)); }
607 
609  size_type _M_bkt_num_key(const _KT& __key, size_type __n) const
610  { return _M_hash(__key) % __n; }
611 
612  size_type _M_bkt_num(const value_type& __obj, size_t __n) const
613  { return _M_bkt_num_key(_M_get_key(__obj), __n); }
614 
615  void _M_copy_from(const _Self& __ht);
616 };
617 
618 #if defined (_STLP_DEBUG)
619 # undef hashtable
621 #endif
622 
624 
625 #if !defined (_STLP_LINK_TIME_INSTANTIATION)
626 # include <stl/_hashtable.c>
627 #endif
628 
629 #if defined (_STLP_DEBUG)
630 # include <stl/debug/_hashtable.h>
631 #endif
632 
634 
635 #define _STLP_TEMPLATE_HEADER template <class _Val, class _Key, class _HF, class _Traits, class _ExK, class _EqK, class _All>
636 #define _STLP_TEMPLATE_CONTAINER hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
637 #include <stl/_relops_hash_cont.h>
638 #undef _STLP_TEMPLATE_CONTAINER
639 #undef _STLP_TEMPLATE_HEADER
640 
641 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) && !defined (_STLP_NO_MOVE_SEMANTIC)
642 template <class _Val, class _Key, class _HF, class _Traits, class _ExK, class _EqK, class _All>
643 struct __move_traits<hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All> > {
644  //Hashtables are movable:
645  typedef __true_type implemented;
646 
647  //Completeness depends on many template parameters, for the moment we consider it not complete:
648  typedef __false_type complete;
649 };
650 #endif
651 
653 
654 #endif /* _STLP_INTERNAL_HASHTABLE_H */
655 
656 // Local Variables:
657 // mode:C++
658 // End:
#define _STLP_CONVERT_ALLOCATOR(__a, _Tp)
Definition: _alloc.h:183
ptrdiff_t difference_type
Definition: _hashtable.h:118
size_t size_type
Definition: _hashtable.h:119
_Ht_iterator< _BaseIte, _NonConstTraits > iterator
Definition: _hashtable.h:121
forward_iterator_tag iterator_category
Definition: _hashtable.h:117
_ElemsCont::iterator _ElemsIte
Definition: _hashtable.h:256
#define swap(a, b)
Definition: qsort.c:63
return __n
Definition: _algo.h:75
void _M_reduce()
Definition: _hashtable.c:396
size_type _M_bkt_num(const value_type &__obj) const
Definition: _hashtable.h:605
iterator begin()
Definition: _hashtable.h:376
_Ht_iterator< _BaseIte, _ConstTraits > const_iterator
Definition: _hashtable.h:122
_HF hasher
Definition: _hashtable.h:235
const_local_iterator end(size_type __n) const
Definition: _hashtable.h:384
ptrdiff_t difference_type
Definition: _hashtable.h:239
GLsizei const GLvoid * pointer
Definition: glext.h:5848
__bool2type< pod >::_Ret is_POD_type
__false_type implemented
#define _STLP_TYPENAME
Definition: features.h:612
_Traits::pointer pointer
Definition: _hashtable.h:115
#define __STATIC_CAST(__x, __y)
Definition: features.h:585
float max_load_factor() const
Definition: _hashtable.h:401
Definition: _slist.h:198
_Alloc_traits< _BucketType *, _All >::allocator_type _BucketAllocType
Definition: _hashtable.h:259
_STLP_PRIV _Slist_node_base _BucketType
Definition: _hashtable.h:258
#define _STLP_TEMPLATE_FOR_CONT_EXT
Definition: features.h:623
_Traits::_ConstLocalTraits _ConstLocalTraits
Definition: _hashtable.h:230
_Self & operator=(const _Self &__ht)
Definition: _hashtable.h:351
forward_iterator_tag _Iterator_category
Definition: _hashtable.h:244
float _M_max_load_factor
Definition: _hashtable.h:279
_STLP_PRIV _Ht_iterator< _ElemsIte, _NonConstLocalTraits > local_iterator
Definition: _hashtable.h:292
_STLP_TEMPLATE_FOR_CONT_EXT const_iterator find(const _KT &__key) const
Definition: _hashtable.h:513
_STLP_TEMPLATE_FOR_CONT_EXT pair< const_iterator, const_iterator > equal_range(const _KT &__key) const
Definition: _hashtable.h:550
_Ht_iterator(_BaseIte __it)
Definition: _hashtable.h:127
void resize(size_type __num_buckets_hint)
Definition: _hashtable.h:580
_STLP_PRIV _Ht_iterator< _ElemsIte, _ConstLocalTraits > const_local_iterator
Definition: _hashtable.h:293
_STLP_PRIV _Slist_iterator< value_type, _Const_traits< value_type > > const_iterator
Definition: _slist.h:240
_Traits::_NonConstTraits _NonConstTraits
Definition: _hashtable.h:110
local_iterator end(size_type __n)
Definition: _hashtable.h:379
iterator begin()
Definition: _slist.h:416
#define _STLP_ITERATOR_CATEGORY(_It, _Tp)
_STLP_PRIV _Ht_iterator< _ElemsIte, _ConstTraits > const_iterator
Definition: _hashtable.h:288
GLsizei GLsizei GLfloat distance
Definition: glext.h:11755
#define _STLP_MOVE_TO_PRIV_NAMESPACE
Definition: features.h:524
_STLP_TEMPLATE_FOR_CONT_EXT size_type _M_bkt_num_key(const _KT &__key) const
Definition: _hashtable.h:602
void _M_resize()
Definition: _hashtable.c:440
static iterator _S_before_begin(const _ElemsCont &__elems, const _BucketVector &__buckets, size_type &__n)
Definition: _hashtable.c:156
void insert_equal(const_iterator __f, const_iterator __l)
Definition: _hashtable.h:486
allocator_type get_allocator() const
Definition: _hashtable.h:300
void swap(_Self &__ht)
Definition: _hashtable.h:367
iterator end()
Definition: _hashtable.h:377
_ElemsCont::const_iterator _ElemsConstIte
Definition: _hashtable.h:257
_BaseIte _M_ite
Definition: _hashtable.h:151
const value_type * const_pointer
Definition: _hashtable.h:241
size_type max_bucket_count() const
Definition: _hashtable.h:392
static void _STLP_CALL _S_prev_sizes(size_t __hint, const size_t *&__begin, const size_t *&__end)
void insert_unique(const_iterator __f, const_iterator __l)
Definition: _hashtable.h:479
iterator _M_insert_noresize(size_type __n, const value_type &__obj)
Definition: _hashtable.c:183
hasher hash_funct() const
Definition: _hashtable.h:246
const_iterator begin() const
Definition: _hashtable.h:381
_Traits::_ConstTraits _ConstTraits
Definition: _hashtable.h:109
iterator insert_equal(const value_type &__obj)
Definition: _hashtable.h:412
_EqK key_equal
Definition: _hashtable.h:236
__type_traits< _Tp >::has_trivial_destructor complete
void clear()
Definition: _hashtable.c:501
_STLP_INLINE_LOOP _InputIter __last
Definition: _algo.h:68
_Self operator++(int)
Definition: _hashtable.h:138
_Traits::_NonConstLocalTraits _NonConstLocalTraits
Definition: _hashtable.h:229
bool operator==(const_iterator __rhs) const
Definition: _hashtable.h:144
const_local_iterator begin(size_type __n) const
Definition: _hashtable.h:383
size_type bucket_count() const
Definition: _hashtable.h:391
#define _STLP_MOVE_TO_STD_NAMESPACE
Definition: features.h:525
GLfloat f
Definition: glext.h:7540
void get(int argc, const char *argv[])
Definition: cmds.c:480
_NonConstTraits::reference reference
Definition: _hashtable.h:242
key_equal key_eq() const
Definition: _hashtable.h:247
void max_load_factor(float __z)
Definition: _hashtable.h:402
_Traits::_ConstTraits _ConstTraits
Definition: _hashtable.h:228
_STLP_TEMPLATE_FOR_CONT_EXT _ElemsIte _M_find(const _KT &__key) const
Definition: _hashtable.h:498
size_t size_type
Definition: _hashtable.h:238
_STLP_INLINE_LOOP _InputIter const _Tp & __val
Definition: _algobase.h:656
void rehash(size_type __num_buckets_hint)
Definition: _hashtable.c:365
float load_factor() const
Definition: _hashtable.h:400
_BucketVector _M_buckets
Definition: _hashtable.h:277
iterator _M_before_begin(size_type &__n) const
Definition: _hashtable.c:148
#define _STLP_EXPORT_TEMPLATE_CLASS
Definition: features.h:987
static const key_type & _M_get_key(const value_type &__val)
Definition: _hashtable.h:282
hashtable(const _Self &__ht)
Definition: _hashtable.h:332
pair< iterator, bool > insert_unique_noresize(const value_type &__obj)
Definition: _hashtable.c:199
_STLP_PRIV _Ht_iterator< _ElemsIte, _NonConstTraits > iterator
Definition: _hashtable.h:287
__bool2type< trivial_constructor >::_Ret has_trivial_default_constructor
size_type size() const
Definition: _hashtable.h:363
_STLP_MOVE_TO_PRIV_NAMESPACE const _InputIterator const input_iterator_tag &_InputIterator __it(__first)
_STLP_DEFINE_ARROW_OPERATOR _Self & operator++()
Definition: _hashtable.h:134
void _M_rehash(size_type __num_buckets)
Definition: _hashtable.c:454
size_type elems_in_bucket(size_type __bucket) const
Definition: _hashtable.h:393
_ElemsCont _M_elems
Definition: _hashtable.h:276
_NonConstTraits::pointer pointer
Definition: _hashtable.h:240
_Key key_type
Definition: _hashtable.h:233
GLint reference
Definition: glext.h:11729
#define _STLP_PRIV
Definition: _dm.h:70
hasher _M_hash
Definition: _hashtable.h:274
static size_t _STLP_CALL _S_max_nb_buckets()
_Rebind_type::other allocator_type
Definition: _alloc.h:201
iterator insert_equal_noresize(const value_type &__obj)
Definition: _hashtable.c:230
_STLP_TYPENAME_ON_RETURN_TYPE _MoveSourceTraits< _Tp >::_Type _AsMoveSource(_Tp &src)
GLenum src
Definition: glext.h:6340
void insert_unique(const value_type *__f, const value_type *__l)
Definition: _hashtable.h:465
size_type max_size() const
Definition: _hashtable.h:364
#define _STLP_KEY_TYPE_FOR_CONT_EXT(type)
Definition: features.h:622
_STLP_PRIV _Slist_iterator< value_type, _Nonconst_traits< value_type > > iterator
Definition: _slist.h:239
allocator_type get_allocator() const
Definition: _slist.h:277
void swap(_Self &__x)
Definition: _slist.h:430
_In_ int _Val
Definition: memory.h:91
_STLP_TEMPLATE_FOR_CONT_EXT iterator find(const _KT &__key)
Definition: _hashtable.h:511
void assign(size_type __n, const _Tp &__val)
Definition: _vector.h:315
void insert_equal(const value_type *__f, const value_type *__l)
Definition: _hashtable.h:472
iterator end()
Definition: _slist.h:420
vector< _BucketType *, _BucketAllocType > _BucketVector
Definition: _hashtable.h:271
hashtable(size_type __n, const _HF &__hf, const _EqK &__eql, const allocator_type &__a=allocator_type())
Definition: _hashtable.h:303
#define __CONST_CAST(__x, __y)
Definition: features.h:584
reference operator *() const
Definition: _hashtable.h:129
static size_t _STLP_CALL _S_next_size(size_t)
__bool2type< trivial_assign >::_Ret has_trivial_assignment_operator
bool empty() const
Definition: _hashtable.h:365
#define _STLP_END_NAMESPACE
Definition: features.h:503
const_iterator end() const
Definition: _hashtable.h:382
local_iterator begin(size_type __n)
Definition: _hashtable.h:378
_STLP_TEMPLATE_FOR_CONT_EXT size_type _M_bkt_num_key(const _KT &__key, size_type __n) const
Definition: _hashtable.h:609
__bool2type< trivial_copy >::_Ret has_trivial_copy_constructor
Definition: _pair.h:47
hashtable(__move_source< _Self > src)
Definition: _hashtable.h:342
__kernel_ptrdiff_t ptrdiff_t
Definition: linux.h:247
void _M_copy_from(const _Self &__ht)
Definition: _hashtable.c:510
_Traits::_NonConstTraits _NonConstTraits
Definition: _hashtable.h:227
_STLP_TEMPLATE_FOR_CONT_EXT size_type count(const _KT &__key) const
Definition: _hashtable.h:516
key_equal _M_equals
Definition: _hashtable.h:275
#define _STLP_DEFINE_ARROW_OPERATOR
#define _STLP_TYPENAME_ON_RETURN_TYPE
Definition: features.h:600
static const size_t * _S_primes(size_t &)
_Traits::reference reference
Definition: _hashtable.h:116
size_type size() const
Definition: _vector.h:192
#define const
Definition: zconf.h:230
size_type _M_bkt_num(const value_type &__obj, size_t __n) const
Definition: _hashtable.h:612
_STLP_TEMPLATE_FOR_CONT_EXT pair< iterator, iterator > equal_range(const _KT &__key)
Definition: _hashtable.h:534
bool operator !=(const_iterator __rhs) const
Definition: _hashtable.h:147
void _M_initialize_buckets(size_type __n)
Definition: _hashtable.h:595
slist< value_type, _All > _ElemsCont
Definition: _hashtable.h:254
#define _STLP_BEGIN_NAMESPACE
Definition: features.h:501
pair< iterator, bool > insert_unique(const value_type &__obj)
Definition: _hashtable.h:407
_STLP_TEMPLATE_FOR_CONT_EXT size_type bucket(const _KT &__k) const
Definition: _hashtable.h:397
_Ht_iterator< _BaseIte, _Traits > _Self
Definition: _hashtable.h:112
_Val value_type
Definition: _hashtable.h:234
void swap(_Self &__x)
Definition: _vector.h:401
_Ht_iterator(const iterator &__it)
Definition: _hashtable.h:126
void _M_enlarge(size_type __n)
Definition: _hashtable.c:382
reference _M_insert(const value_type &__obj)
Definition: _hashtable.c:254
#define _STLP_CALL
Definition: _bc.h:131
hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All > _Self
Definition: _hashtable.h:226
_Traits::value_type value_type
Definition: _hashtable.h:114
int k
Definition: mpi.c:3369
__bool2type< trivial_destructor >::_Ret has_trivial_destructor
void reserve(size_type __n)
Definition: _vector.c:62
_All allocator_type
Definition: _hashtable.h:299
size_type erase(const key_type &__key)
Definition: _hashtable.c:263
const value_type & const_reference
Definition: _hashtable.h:243
size_type _M_num_elements
Definition: _hashtable.h:278
#define _STLP_FORCE_ALLOCATORS(a, y)
Definition: _alloc.h:436
_Stl_prime< bool > _Stl_prime_type
Definition: _hashtable.h:208