ReactOS 0.4.15-dev-5669-g09dde2c
_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
99template <class _Val, class _Key, class _HF,
100 class _Traits, class _ExK, class _EqK, class _All>
101class hashtable;
102
103#if !defined (_STLP_DEBUG)
105#endif
106
107template <class _BaseIte, class _Traits>
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)
157template <class _BaseIte, class _Traits>
158struct __type_traits<_STLP_PRIV _Ht_iterator<_BaseIte, _Traits> > {
164};
165#endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
166
167#if defined (_STLP_USE_OLD_HP_ITERATOR_QUERIES)
168template <class _BaseIte, class _Traits>
169inline
170# if defined (_STLP_NESTED_TYPE_PARAM_BUG)
171_STLP_TYPENAME_ON_RETURN_TYPE _Traits::value_type *
172# else
174# endif
177 return (_Val*) 0;
178}
179template <class _BaseIte, class _Traits>
181{ return forward_iterator_tag(); }
182template <class _BaseIte, class _Traits>
183inline ptrdiff_t* distance_type(const _STLP_PRIV _Ht_iterator<_BaseIte,_Traits>&)
184{ return (ptrdiff_t*) 0; }
185#endif
186
188
189template <class _Dummy>
191 // Returns begining of primes list and size by reference.
192 static const size_t* _S_primes(size_t&);
193public:
194 //Returns the maximum number of buckets handled by the hashtable implementation
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 */
223template <class _Val, class _Key, class _HF,
224 class _Traits, class _ExK, class _EqK, class _All>
225class 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
232public:
233 typedef _Key key_type;
235 typedef _HF hasher;
236 typedef _EqK key_equal;
237
238 typedef size_t size_type;
240 typedef typename _NonConstTraits::pointer pointer;
241 typedef const value_type* const_pointer;
242 typedef typename _NonConstTraits::reference reference;
245
246 hasher hash_funct() const { return _M_hash; }
247 key_equal key_eq() const { return _M_equals; }
248
249private:
251#if defined (_STLP_DEBUG)
252 typedef _STLP_PRIV _STLP_NON_DBG_NAME(slist)<value_type, _All> _ElemsCont;
253#else
255#endif
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 }
286public:
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),
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),
331
332 hashtable(const _Self& __ht)
333 : _M_hash(__ht._M_hash),
334 _M_equals(__ht._M_equals),
335 _M_elems(__ht.get_allocator()),
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
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) {
368 _STLP_STD::swap(_M_hash, __ht._M_hash);
369 _STLP_STD::swap(_M_equals, __ht._M_equals);
370 _M_elems.swap(__ht._M_elems);
372 _STLP_STD::swap(_M_num_elements, __ht._M_num_elements);
373 _STLP_STD::swap(_M_max_load_factor, __ht._M_max_load_factor);
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
388public:
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
417protected:
419public:
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)
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)
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)
491 }
492#endif /*_STLP_MEMBER_TEMPLATES */
493
494 //reference find_or_insert(const value_type& __obj);
495
496private:
498 _ElemsIte _M_find(const _KT& __key) const {
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
509public:
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);
568
569private:
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
578public:
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
587private:
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>
638#undef _STLP_TEMPLATE_CONTAINER
639#undef _STLP_TEMPLATE_HEADER
640
641#if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) && !defined (_STLP_NO_MOVE_SEMANTIC)
642template <class _Val, class _Key, class _HF, class _Traits, class _ExK, class _EqK, class _All>
643struct __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:
_STLP_INLINE_LOOP _InputIter __last
Definition: _algo.h:68
return __n
Definition: _algo.h:75
_STLP_INLINE_LOOP _InputIter const _Tp & __val
Definition: _algobase.h:656
#define _STLP_CONVERT_ALLOCATOR(__a, _Tp)
Definition: _alloc.h:183
#define _STLP_FORCE_ALLOCATORS(a, y)
Definition: _alloc.h:436
bool _STLP_CALL operator!=(const allocator< _T1 > &, const allocator< _T2 > &) _STLP_NOTHROW
Definition: _alloc.h:384
#define _STLP_CALL
Definition: _bc.h:131
#define _STLP_PRIV
Definition: _dm.h:70
_Stl_prime< bool > _Stl_prime_type
Definition: _hashtable.h:208
#define _STLP_ITERATOR_CATEGORY(_It, _Tp)
_STLP_MOVE_TO_PRIV_NAMESPACE const _InputIterator const input_iterator_tag &_InputIterator __it(__first)
_STLP_TYPENAME_ON_RETURN_TYPE _MoveSourceTraits< _Tp >::_Type _AsMoveSource(_Tp &src)
#define _STLP_DEFINE_ARROW_OPERATOR
void get(int argc, const char *argv[])
Definition: cmds.c:480
static void _STLP_CALL _S_prev_sizes(size_t __hint, const size_t *&__begin, const size_t *&__end)
static size_t _STLP_CALL _S_max_nb_buckets()
static size_t _STLP_CALL _S_next_size(size_t)
static const size_t * _S_primes(size_t &)
reference _M_insert(const value_type &__obj)
Definition: _hashtable.c:254
hasher _M_hash
Definition: _hashtable.h:274
local_iterator begin(size_type __n)
Definition: _hashtable.h:378
_NonConstTraits::reference reference
Definition: _hashtable.h:242
_HF hasher
Definition: _hashtable.h:235
_STLP_TEMPLATE_FOR_CONT_EXT const_iterator find(const _KT &__key) const
Definition: _hashtable.h:513
_Traits::_NonConstLocalTraits _NonConstLocalTraits
Definition: _hashtable.h:229
_STLP_PRIV _Ht_iterator< _ElemsIte, _ConstTraits > const_iterator
Definition: _hashtable.h:288
size_type erase(const key_type &__key)
Definition: _hashtable.c:263
const_local_iterator begin(size_type __n) const
Definition: _hashtable.h:383
hashtable(__move_source< _Self > src)
Definition: _hashtable.h:342
_Val value_type
Definition: _hashtable.h:234
hashtable(size_type __n, const _HF &__hf, const _EqK &__eql, const allocator_type &__a=allocator_type())
Definition: _hashtable.h:303
float _M_max_load_factor
Definition: _hashtable.h:279
const value_type & const_reference
Definition: _hashtable.h:243
const value_type * const_pointer
Definition: _hashtable.h:241
void insert_equal(const_iterator __f, const_iterator __l)
Definition: _hashtable.h:486
_EqK key_equal
Definition: _hashtable.h:236
void _M_rehash(size_type __num_buckets)
Definition: _hashtable.c:454
size_type _M_bkt_num(const value_type &__obj, size_t __n) const
Definition: _hashtable.h:612
_Key key_type
Definition: _hashtable.h:233
allocator_type get_allocator() const
Definition: _hashtable.h:300
hashtable< _Val, _Key, _HF, _Traits, _ExK, _EqK, _All > _Self
Definition: _hashtable.h:226
void _M_copy_from(const _Self &__ht)
Definition: _hashtable.c:510
ptrdiff_t difference_type
Definition: _hashtable.h:239
local_iterator end(size_type __n)
Definition: _hashtable.h:379
void max_load_factor(float __z)
Definition: _hashtable.h:402
key_equal key_eq() const
Definition: _hashtable.h:247
_Traits::_ConstTraits _ConstTraits
Definition: _hashtable.h:228
size_type _M_bkt_num(const value_type &__obj) const
Definition: _hashtable.h:605
static const key_type & _M_get_key(const value_type &__val)
Definition: _hashtable.h:282
iterator _M_insert_noresize(size_type __n, const value_type &__obj)
Definition: _hashtable.c:183
void _M_reduce()
Definition: _hashtable.c:396
iterator insert_equal(const value_type &__obj)
Definition: _hashtable.h:412
const_iterator begin() const
Definition: _hashtable.h:381
pair< iterator, bool > insert_unique(const value_type &__obj)
Definition: _hashtable.h:407
_STLP_PRIV _Ht_iterator< _ElemsIte, _NonConstTraits > iterator
Definition: _hashtable.h:287
_Alloc_traits< _BucketType *, _All >::allocator_type _BucketAllocType
Definition: _hashtable.h:259
iterator end()
Definition: _hashtable.h:377
_Traits::_ConstLocalTraits _ConstLocalTraits
Definition: _hashtable.h:230
hashtable(const _Self &__ht)
Definition: _hashtable.h:332
size_type _M_num_elements
Definition: _hashtable.h:278
iterator insert_equal_noresize(const value_type &__obj)
Definition: _hashtable.c:230
_All allocator_type
Definition: _hashtable.h:299
bool empty() const
Definition: _hashtable.h:365
void insert_unique(const_iterator __f, const_iterator __l)
Definition: _hashtable.h:479
size_type bucket_count() const
Definition: _hashtable.h:391
float max_load_factor() const
Definition: _hashtable.h:401
iterator _M_before_begin(size_type &__n) const
Definition: _hashtable.c:148
size_type max_bucket_count() const
Definition: _hashtable.h:392
_ElemsCont _M_elems
Definition: _hashtable.h:276
void _M_initialize_buckets(size_type __n)
Definition: _hashtable.h:595
void insert_equal(const value_type *__f, const value_type *__l)
Definition: _hashtable.h:472
_STLP_TEMPLATE_FOR_CONT_EXT size_type _M_bkt_num_key(const _KT &__key) const
Definition: _hashtable.h:602
_STLP_TEMPLATE_FOR_CONT_EXT pair< iterator, iterator > equal_range(const _KT &__key)
Definition: _hashtable.h:534
_ElemsCont::iterator _ElemsIte
Definition: _hashtable.h:256
_STLP_TEMPLATE_FOR_CONT_EXT _ElemsIte _M_find(const _KT &__key) const
Definition: _hashtable.h:498
_STLP_TEMPLATE_FOR_CONT_EXT iterator find(const _KT &__key)
Definition: _hashtable.h:511
_BucketVector _M_buckets
Definition: _hashtable.h:277
static iterator _S_before_begin(const _ElemsCont &__elems, const _BucketVector &__buckets, size_type &__n)
Definition: _hashtable.c:156
slist< value_type, _All > _ElemsCont
Definition: _hashtable.h:254
void _M_enlarge(size_type __n)
Definition: _hashtable.c:382
size_type max_size() const
Definition: _hashtable.h:364
const_iterator end() const
Definition: _hashtable.h:382
void swap(_Self &__ht)
Definition: _hashtable.h:367
_Traits::_NonConstTraits _NonConstTraits
Definition: _hashtable.h:227
forward_iterator_tag _Iterator_category
Definition: _hashtable.h:244
_NonConstTraits::pointer pointer
Definition: _hashtable.h:240
void insert_unique(const value_type *__f, const value_type *__l)
Definition: _hashtable.h:465
_Self & operator=(const _Self &__ht)
Definition: _hashtable.h:351
_STLP_PRIV _Slist_node_base _BucketType
Definition: _hashtable.h:258
size_type elems_in_bucket(size_type __bucket) const
Definition: _hashtable.h:393
size_type size() const
Definition: _hashtable.h:363
_ElemsCont::const_iterator _ElemsConstIte
Definition: _hashtable.h:257
_STLP_PRIV _Ht_iterator< _ElemsIte, _ConstLocalTraits > const_local_iterator
Definition: _hashtable.h:293
const_local_iterator end(size_type __n) const
Definition: _hashtable.h:384
void rehash(size_type __num_buckets_hint)
Definition: _hashtable.c:365
void clear()
Definition: _hashtable.c:501
iterator begin()
Definition: _hashtable.h:376
void _M_resize()
Definition: _hashtable.c:440
void resize(size_type __num_buckets_hint)
Definition: _hashtable.h:580
float load_factor() const
Definition: _hashtable.h:400
_STLP_TEMPLATE_FOR_CONT_EXT pair< const_iterator, const_iterator > equal_range(const _KT &__key) const
Definition: _hashtable.h:550
_STLP_PRIV _Ht_iterator< _ElemsIte, _NonConstLocalTraits > local_iterator
Definition: _hashtable.h:292
hasher hash_funct() const
Definition: _hashtable.h:246
_STLP_TEMPLATE_FOR_CONT_EXT size_type bucket(const _KT &__k) const
Definition: _hashtable.h:397
_STLP_TEMPLATE_FOR_CONT_EXT size_type _M_bkt_num_key(const _KT &__key, size_type __n) const
Definition: _hashtable.h:609
vector< _BucketType *, _BucketAllocType > _BucketVector
Definition: _hashtable.h:271
_STLP_TEMPLATE_FOR_CONT_EXT size_type count(const _KT &__key) const
Definition: _hashtable.h:516
key_equal _M_equals
Definition: _hashtable.h:275
size_t size_type
Definition: _hashtable.h:238
pair< iterator, bool > insert_unique_noresize(const value_type &__obj)
Definition: _hashtable.c:199
Definition: _slist.h:57
void swap(_Self &__x)
Definition: _slist.h:430
_STLP_PRIV _Slist_iterator< value_type, _Nonconst_traits< value_type > > iterator
Definition: _slist.h:239
iterator end()
Definition: _slist.h:420
allocator_type get_allocator() const
Definition: _slist.h:277
_STLP_PRIV _Slist_iterator< value_type, _Const_traits< value_type > > const_iterator
Definition: _slist.h:240
iterator begin()
Definition: _slist.h:416
__kernel_ptrdiff_t ptrdiff_t
Definition: linux.h:247
#define _STLP_TEMPLATE_FOR_CONT_EXT
Definition: features.h:623
#define _STLP_TYPENAME_ON_RETURN_TYPE
Definition: features.h:600
#define _STLP_MOVE_TO_STD_NAMESPACE
Definition: features.h:525
#define _STLP_TYPENAME
Definition: features.h:612
#define __STATIC_CAST(__x, __y)
Definition: features.h:585
#define __CONST_CAST(__x, __y)
Definition: features.h:584
#define _STLP_KEY_TYPE_FOR_CONT_EXT(type)
Definition: features.h:622
#define _STLP_EXPORT_TEMPLATE_CLASS
Definition: features.h:987
#define _STLP_BEGIN_NAMESPACE
Definition: features.h:501
#define _STLP_END_NAMESPACE
Definition: features.h:503
#define _STLP_MOVE_TO_PRIV_NAMESPACE
Definition: features.h:524
GLenum src
Definition: glext.h:6340
GLint reference
Definition: glext.h:11729
static float(__cdecl *square_half_float)(float x
int k
Definition: mpi.c:3369
_In_ int _Val
Definition: memory.h:91
_Rebind_type::other allocator_type
Definition: _alloc.h:201
_Self operator++(int)
Definition: _hashtable.h:138
_Ht_iterator< _BaseIte, _ConstTraits > const_iterator
Definition: _hashtable.h:122
_Traits::_NonConstTraits _NonConstTraits
Definition: _hashtable.h:110
forward_iterator_tag iterator_category
Definition: _hashtable.h:117
_Ht_iterator< _BaseIte, _Traits > _Self
Definition: _hashtable.h:112
ptrdiff_t difference_type
Definition: _hashtable.h:118
_Ht_iterator< _BaseIte, _NonConstTraits > iterator
Definition: _hashtable.h:121
_Traits::pointer pointer
Definition: _hashtable.h:115
_BaseIte _M_ite
Definition: _hashtable.h:151
reference operator*() const
Definition: _hashtable.h:129
_Traits::value_type value_type
Definition: _hashtable.h:114
size_t size_type
Definition: _hashtable.h:119
_STLP_DEFINE_ARROW_OPERATOR _Self & operator++()
Definition: _hashtable.h:134
_Ht_iterator(const iterator &__it)
Definition: _hashtable.h:126
_Ht_iterator(_BaseIte __it)
Definition: _hashtable.h:127
_Traits::reference reference
Definition: _hashtable.h:116
_Traits::_ConstTraits _ConstTraits
Definition: _hashtable.h:109
__type_traits< _Tp >::has_trivial_destructor complete
__false_type implemented
__bool2type< pod >::_Ret is_POD_type
__bool2type< trivial_destructor >::_Ret has_trivial_destructor
__bool2type< trivial_constructor >::_Ret has_trivial_default_constructor
__bool2type< trivial_copy >::_Ret has_trivial_copy_constructor
__bool2type< trivial_assign >::_Ret has_trivial_assignment_operator
Definition: _pair.h:47
void reserve(size_type __n)
Definition: _vector.c:62
void swap(_Self &__x)
Definition: _vector.h:404
size_type size() const
Definition: _vector.h:192
void assign(size_type __n, const _Tp &__val)
Definition: _vector.h:318
bool operator==(const TKeyDef &t1, const TKeyDef &t2)
Definition: tkeydef.cpp:122
#define const
Definition: zconf.h:233