ReactOS  0.4.13-dev-73-gcfe54aa
_hashtable.c
Go to the documentation of this file.
1 /*
2  * Copyright (c) 1994
3  * Hewlett-Packard Company
4  *
5  * Copyright (c) 1996,1997
6  * Silicon Graphics Computer Systems, Inc.
7  *
8  * Copyright (c) 1997
9  * Moscow Center for SPARC Technology
10  *
11  * Copyright (c) 1999
12  * Boris Fomitchev
13  *
14  * This material is provided "as is", with absolutely no warranty expressed
15  * or implied. Any use is at your own risk.
16  *
17  * Permission to use or copy this software for any purpose is hereby granted
18  * without fee, provided the above notices are retained on all copies.
19  * Permission to modify the code and to distribute modified code is granted,
20  * provided the above notices are retained, and a notice that the code was
21  * modified is included with the above copyright notice.
22  *
23  */
24 #ifndef _STLP_HASHTABLE_C
25 #define _STLP_HASHTABLE_C
26 
27 #ifndef _STLP_INTERNAL_HASHTABLE_H
28 # include <stl/_hashtable.h>
29 #endif
30 
32 
33 #if defined (_STLP_EXPOSE_GLOBALS_IMPLEMENTATION)
34 
36 
37 # define __PRIME_LIST_BODY { \
38  7ul, 23ul, \
39  53ul, 97ul, 193ul, 389ul, 769ul, \
40  1543ul, 3079ul, 6151ul, 12289ul, 24593ul, \
41  49157ul, 98317ul, 196613ul, 393241ul, 786433ul, \
42  1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul, \
43  50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,\
44  1610612741ul, 3221225473ul, 4294967291ul \
45 }
46 
47 template <class _Dummy>
48 const size_t* _STLP_CALL
49 _Stl_prime<_Dummy>::_S_primes(size_t &__size) {
50  static const size_t _list[] = __PRIME_LIST_BODY;
51 # ifndef __MWERKS__
52  __size = sizeof(_list) / sizeof(_list[0]);
53 # else
54  __size = 30;
55 # endif
56  return _list;
57 }
58 
59 template <class _Dummy>
60 size_t _STLP_CALL
62  size_t __size;
63  const size_t* __first = _S_primes(__size);
64  return *(__first + __size - 1);
65 }
66 
67 template <class _Dummy>
68 size_t _STLP_CALL
70  size_t __size;
71  const size_t* __first = _S_primes(__size);
72  const size_t* __last = __first + __size;
73  const size_t* pos = __lower_bound(__first, __last, __n,
74  __less((size_t*)0), __less((size_t*)0), (ptrdiff_t*)0);
75  return (pos == __last ? *(__last - 1) : *pos);
76 }
77 
78 template <class _Dummy>
79 void _STLP_CALL
80 _Stl_prime<_Dummy>::_S_prev_sizes(size_t __n, size_t const*&__begin, size_t const*&__pos) {
81  size_t __size;
82  __begin = _S_primes(__size);
83  const size_t* __last = __begin + __size;
84  __pos = __lower_bound(__begin, __last, __n,
85  __less((size_t*)0), __less((size_t*)0), (ptrdiff_t*)0);
86 
87  if (__pos== __last)
88  --__pos;
89  else if (*__pos == __n) {
90  if (__pos != __begin)
91  --__pos;
92  }
93 }
94 
95 # undef __PRIME_LIST_BODY
96 
98 
99 #endif
100 
101 #if defined (_STLP_DEBUG)
102 # define hashtable _STLP_NON_DBG_NAME(hashtable)
104 #endif
105 
106 // fbp: these defines are for outline methods definitions.
107 // needed to definitions to be portable. Should not be used in method bodies.
108 
109 #if defined ( _STLP_NESTED_TYPE_PARAM_BUG )
110 # define __size_type__ size_t
111 # define size_type size_t
112 # define value_type _Val
113 # define key_type _Key
114 # define __reference__ _Val&
115 
116 # define __iterator__ _Ht_iterator<_Val, _STLP_HEADER_TYPENAME _Traits::_NonConstTraits, \
117  _Key, _HF, _ExK, _EqK, _All>
118 # define __const_iterator__ _Ht_iterator<_Val, _STLP_HEADER_TYPENAME _Traits::_ConstTraits, \
119  _Key, _HF, _ExK, _EqK, _All>
120 #else
121 # define __size_type__ _STLP_TYPENAME_ON_RETURN_TYPE hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All>::size_type
122 # define __reference__ _STLP_TYPENAME_ON_RETURN_TYPE hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All>::reference
123 # define __iterator__ _STLP_TYPENAME_ON_RETURN_TYPE hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All>::iterator
124 # define __const_iterator__ _STLP_TYPENAME_ON_RETURN_TYPE hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All>::const_iterator
125 #endif
126 
127 /*
128  * This method is too difficult to implement for hashtable that do not
129  * require a sorted operation on the stored type.
130 template <class _Val, class _Key, class _HF,
131  class _Traits, class _ExK, class _EqK, class _All>
132 bool hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>::_M_equal(
133  const hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>& __ht1,
134  const hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>& __ht2) {
135  return __ht1._M_buckets == __ht2._M_buckets &&
136  __ht1._M_elems == __ht2._M_elems;
137 }
138 */
139 
140 /* Returns the iterator before the first iterator of the bucket __n and set
141  * __n to the first previous bucket having the same first iterator as bucket
142  * __n.
143  */
144 template <class _Val, class _Key, class _HF,
145  class _Traits, class _ExK, class _EqK, class _All>
149  return _S_before_begin(_M_elems, _M_buckets, __n);
150 }
151 
152 template <class _Val, class _Key, class _HF,
153  class _Traits, class _ExK, class _EqK, class _All>
156  ::_S_before_begin(const _ElemsCont& __elems, const _BucketVector& __buckets,
157  size_type &__n) {
158  _ElemsCont &__mutable_elems = __CONST_CAST(_ElemsCont&, __elems);
159  typename _BucketVector::const_iterator __bpos(__buckets.begin() + __n);
160 
161  _ElemsIte __pos(*__bpos);
162  if (__pos == __mutable_elems.begin()) {
163  __n = 0;
164  return __mutable_elems.before_begin();
165  }
166 
167  typename _BucketVector::const_iterator __bcur(__bpos);
168  _BucketType *__pos_node = __pos._M_node;
169  for (--__bcur; __pos_node == *__bcur; --__bcur);
170 
171  __n = __bcur - __buckets.begin() + 1;
172  _ElemsIte __cur(*__bcur);
173  _ElemsIte __prev = __cur++;
174  for (; __cur != __pos; ++__prev, ++__cur);
175  return __prev;
176 }
177 
178 
179 template <class _Val, class _Key, class _HF,
180  class _Traits, class _ExK, class _EqK, class _All>
184  //We always insert this element as 1st in the bucket to not break
185  //the elements order as equal elements must be kept next to each other.
186  size_type __prev = __n;
187  _ElemsIte __pos = _M_before_begin(__prev)._M_ite;
188 
189  fill(_M_buckets.begin() + __prev, _M_buckets.begin() + __n + 1,
190  _M_elems.insert_after(__pos, __obj)._M_node);
191  ++_M_num_elements;
192  return iterator(_ElemsIte(_M_buckets[__n]));
193 }
194 
195 template <class _Val, class _Key, class _HF,
196  class _Traits, class _ExK, class _EqK, class _All>
200  const size_type __n = _M_bkt_num(__obj);
201  _ElemsIte __cur(_M_buckets[__n]);
202  _ElemsIte __last(_M_buckets[__n + 1]);
203 
204  if (__cur != __last) {
205  for (; __cur != __last; ++__cur) {
206  if (_M_equals(_M_get_key(*__cur), _M_get_key(__obj))) {
207  //We check that equivalent keys have equals hash code as otherwise, on resize,
208  //equivalent value might not be in the same bucket
209  _STLP_ASSERT(_M_hash(_M_get_key(*__cur)) == _M_hash(_M_get_key(__obj)))
210  return pair<iterator, bool>(iterator(__cur), false);
211  }
212  }
213  /* Here we do not rely on the _M_insert_noresize method as we know
214  * that we cannot break element orders, elements are unique, and
215  * insertion after the first bucket element is faster than what is
216  * done in _M_insert_noresize.
217  */
218  __cur = _M_elems.insert_after(_ElemsIte(_M_buckets[__n]), __obj);
219  ++_M_num_elements;
220  return pair<iterator, bool>(iterator(__cur), true);
221  }
222 
223  return pair<iterator, bool>(_M_insert_noresize(__n, __obj), true);
224 }
225 
226 template <class _Val, class _Key, class _HF,
227  class _Traits, class _ExK, class _EqK, class _All>
231  const size_type __n = _M_bkt_num(__obj);
232  {
233  _ElemsIte __cur(_M_buckets[__n]);
234  _ElemsIte __last(_M_buckets[__n + 1]);
235 
236  for (; __cur != __last; ++__cur) {
237  if (_M_equals(_M_get_key(*__cur), _M_get_key(__obj))) {
238  //We check that equivalent keys have equals hash code as otherwise, on resize,
239  //equivalent value might not be in the same bucket
240  _STLP_ASSERT(_M_hash(_M_get_key(*__cur)) == _M_hash(_M_get_key(__obj)))
241  ++_M_num_elements;
242  return _M_elems.insert_after(__cur, __obj);
243  }
244  }
245  }
246 
247  return _M_insert_noresize(__n, __obj);
248 }
249 
250 template <class _Val, class _Key, class _HF,
251  class _Traits, class _ExK, class _EqK, class _All>
254  ::_M_insert(const value_type& __obj) {
255  _M_enlarge(_M_num_elements + 1);
256  return *insert_unique_noresize(__obj).first;
257 }
258 
259 template <class _Val, class _Key, class _HF,
260  class _Traits, class _ExK, class _EqK, class _All>
263  ::erase(const key_type& __key) {
264  const size_type __n = _M_bkt_num_key(__key);
265 
266  _ElemsIte __cur(_M_buckets[__n]);
267  _ElemsIte __last(_M_buckets[__n + 1]);
268  if (__cur == __last)
269  return 0;
270 
271  size_type __erased = 0;
272  if (_M_equals(_M_get_key(*__cur), __key)) {
273  //We look for the pos before __cur:
274  size_type __prev_b = __n;
275  _ElemsIte __prev = _M_before_begin(__prev_b)._M_ite;
276  do {
277  __cur = _M_elems.erase_after(__prev);
278  ++__erased;
279  } while ((__cur != __last) && _M_equals(_M_get_key(*__cur), __key));
280  fill(_M_buckets.begin() + __prev_b, _M_buckets.begin() + __n + 1, __cur._M_node);
281  }
282  else {
283  _ElemsIte __prev = __cur++;
284  for (; __cur != __last; ++__prev, ++__cur) {
285  if (_M_equals(_M_get_key(*__cur), __key)) {
286  do {
287  __cur = _M_elems.erase_after(__prev);
288  ++__erased;
289  } while ((__cur != __last) && _M_equals(_M_get_key(*__cur), __key));
290  break;
291  }
292  }
293  }
294 
295  _M_num_elements -= __erased;
296  _M_reduce();
297  return __erased;
298 }
299 
300 template <class _Val, class _Key, class _HF,
301  class _Traits, class _ExK, class _EqK, class _All>
304  const size_type __n = _M_bkt_num(*__it);
305  _ElemsIte __cur(_M_buckets[__n]);
306 
307  size_type __erased = 0;
308  if (__cur == __it._M_ite) {
309  size_type __prev_b = __n;
310  _ElemsIte __prev = _M_before_begin(__prev_b)._M_ite;
311  fill(_M_buckets.begin() + __prev_b, _M_buckets.begin() + __n + 1,
312  _M_elems.erase_after(__prev)._M_node);
313  ++__erased;
314  }
315  else {
316  _ElemsIte __prev = __cur++;
317  _ElemsIte __last(_M_buckets[__n + 1]);
318  for (; __cur != __last; ++__prev, ++__cur) {
319  if (__cur == __it._M_ite) {
320  _M_elems.erase_after(__prev);
321  ++__erased;
322  break;
323  }
324  }
325  }
326 
327  _M_num_elements -= __erased;
328  _M_reduce();
329 }
330 
331 template <class _Val, class _Key, class _HF,
332  class _Traits, class _ExK, class _EqK, class _All>
335  if (__first == __last)
336  return;
337  size_type __f_bucket = _M_bkt_num(*__first);
338  size_type __l_bucket = __last != end() ? _M_bkt_num(*__last) : (_M_buckets.size() - 1);
339 
340  _ElemsIte __cur(_M_buckets[__f_bucket]);
341  _ElemsIte __prev;
342  if (__cur == __first._M_ite) {
343  __prev = _M_before_begin(__f_bucket)._M_ite;
344  }
345  else {
346  _ElemsIte __last(_M_buckets[++__f_bucket]);
347  __prev = __cur++;
348  for (; (__cur != __last) && (__cur != __first._M_ite); ++__prev, ++__cur);
349  }
350  size_type __erased = 0;
351  //We do not use the slist::erase_after method taking a range to count the
352  //number of erased elements:
353  while (__cur != __last._M_ite) {
354  __cur = _M_elems.erase_after(__prev);
355  ++__erased;
356  }
357  fill(_M_buckets.begin() + __f_bucket, _M_buckets.begin() + __l_bucket + 1, __cur._M_node);
358  _M_num_elements -= __erased;
359  _M_reduce();
360 }
361 
362 template <class _Val, class _Key, class _HF,
363  class _Traits, class _ExK, class _EqK, class _All>
365  ::rehash(size_type __num_buckets_hint) {
366  if (bucket_count() >= __num_buckets_hint) {
367  // We are trying to reduce number of buckets, we have to validate it:
368  size_type __limit_num_buckets = (size_type)((float)size() / max_load_factor());
369  if (__num_buckets_hint < __limit_num_buckets) {
370  // Targetted number of buckets __num_buckets_hint would break
371  // load_factor() <= max_load_factor() rule.
372  return;
373  }
374  }
375 
376  _M_rehash(__num_buckets_hint);
377 }
378 
379 template <class _Val, class _Key, class _HF,
380  class _Traits, class _ExK, class _EqK, class _All>
383  size_type __num_buckets = bucket_count();
384  size_type __num_buckets_hint = (size_type)((float)__to_size / max_load_factor());
385  if (__num_buckets_hint <= __num_buckets) {
386  return;
387  }
388  __num_buckets = _STLP_PRIV _Stl_prime_type::_S_next_size(__num_buckets_hint);
389 
390  _M_rehash(__num_buckets);
391 }
392 
393 template <class _Val, class _Key, class _HF,
394  class _Traits, class _ExK, class _EqK, class _All>
397  size_type __num_buckets = bucket_count();
398  // We only try to reduce the hashtable if the theorical load factor
399  // is lower than a fraction of the max load factor:
400  // 4 factor is coming from the fact that prime number list is almost a
401  // geometrical suite with reason 2, as we try to jump 2 levels is means
402  // a 4 factor.
403  if ((float)size() / (float)__num_buckets > max_load_factor() / 4.0f)
404  return;
405 
406  const size_type *__first;
407  const size_type *__prev;
408  _STLP_PRIV _Stl_prime_type::_S_prev_sizes(__num_buckets, __first, __prev);
409 
410  /* We are only going to reduce number of buckets if moving to yet the previous number
411  * of buckets in the prime numbers would respect the load rule. Otherwise algorithm
412  * successively removing and adding an element would each time perform an expensive
413  * rehash operation. */
414  const size_type *__prev_prev = __prev;
415  if (__prev_prev != __first) {
416  --__prev_prev;
417  if ((float)size() / (float)*__prev_prev > max_load_factor())
418  return;
419  }
420  else {
421  if (*__prev >= __num_buckets)
422  return;
423  }
424 
425  // Can we reduce further:
426  while (__prev_prev != __first) {
427  --__prev_prev;
428  if ((float)size() / (float)*__prev_prev > max_load_factor())
429  // We cannot reduce further.
430  break;
431  --__prev;
432  }
433 
434  _M_rehash(*__prev);
435 }
436 
437 template <class _Val, class _Key, class _HF,
438  class _Traits, class _ExK, class _EqK, class _All>
441  if (load_factor() > max_load_factor()) {
442  // We have to enlarge
443  _M_enlarge(size());
444  }
445  else {
446  // We can try to reduce size:
447  _M_reduce();
448  }
449 }
450 
451 template <class _Val, class _Key, class _HF,
452  class _Traits, class _ExK, class _EqK, class _All>
454  ::_M_rehash(size_type __num_buckets) {
455 #if defined (_STLP_DEBUG)
456  _M_check();
457 #endif
458  _ElemsCont __tmp_elems(_M_elems.get_allocator());
459  _BucketVector __tmp(__num_buckets + 1, __STATIC_CAST(_BucketType*, 0), _M_buckets.get_allocator());
460  _ElemsIte __cur, __last(_M_elems.end());
461  while (!_M_elems.empty()) {
462  __cur = _M_elems.begin();
463  size_type __new_bucket = _M_bkt_num(*__cur, __num_buckets);
464  _ElemsIte __ite(__cur), __before_ite(__cur);
465  for (++__ite;
466  __ite != __last && _M_equals(_M_get_key(*__cur), _M_get_key(*__ite));
467  ++__ite, ++__before_ite);
468  size_type __prev_bucket = __new_bucket;
469  _ElemsIte __prev = _S_before_begin(__tmp_elems, __tmp, __prev_bucket)._M_ite;
470  __tmp_elems.splice_after(__prev, _M_elems, _M_elems.before_begin(), __before_ite);
471  fill(__tmp.begin() + __prev_bucket, __tmp.begin() + __new_bucket + 1, __cur._M_node);
472  }
473  _M_elems.swap(__tmp_elems);
474  _M_buckets.swap(__tmp);
475 }
476 
477 #if defined (_STLP_DEBUG)
478 template <class _Val, class _Key, class _HF,
479  class _Traits, class _ExK, class _EqK, class _All>
481  //We check that hash code of stored keys haven't change and also that equivalent
482  //relation hasn't been modified
483  size_t __num_buckets = bucket_count();
484  for (size_t __b = 0; __b < __num_buckets; ++__b) {
485  _ElemsIte __cur(_M_buckets[__b]), __last(_M_buckets[__b + 1]);
486  _ElemsIte __fst(__cur), __snd(__cur);
487  for (; __cur != __last; ++__cur) {
488  _STLP_ASSERT( _M_bkt_num(*__cur, __num_buckets) == __b )
489  _STLP_ASSERT( !_M_equals(_M_get_key(*__fst), _M_get_key(*__cur)) || _M_equals(_M_get_key(*__snd), _M_get_key(*__cur)) )
490  if (__fst != __snd)
491  ++__fst;
492  if (__snd != __cur)
493  ++__snd;
494  }
495  }
496 }
497 #endif
498 
499 template <class _Val, class _Key, class _HF,
500  class _Traits, class _ExK, class _EqK, class _All>
502  _M_elems.clear();
503  _M_buckets.assign(_M_buckets.size(), __STATIC_CAST(_BucketType*, 0));
504  _M_num_elements = 0;
505 }
506 
507 template <class _Val, class _Key, class _HF,
508  class _Traits, class _ExK, class _EqK, class _All>
511  _M_elems.clear();
512  _M_elems.insert(_M_elems.end(), __ht._M_elems.begin(), __ht._M_elems.end());
513  _M_buckets.resize(__ht._M_buckets.size());
514  _ElemsConstIte __src(__ht._M_elems.begin()), __src_end(__ht._M_elems.end());
515  _ElemsIte __dst(_M_elems.begin());
516  typename _BucketVector::const_iterator __src_b(__ht._M_buckets.begin()),
517  __src_end_b(__ht._M_buckets.end());
518  typename _BucketVector::iterator __dst_b(_M_buckets.begin()), __dst_end_b(_M_buckets.end());
519  for (; __src != __src_end; ++__src, ++__dst) {
520  for (; __src_b != __src_end_b; ++__src_b, ++__dst_b) {
521  if (*__src_b == __src._M_node) {
522  *__dst_b = __dst._M_node;
523  }
524  else
525  break;
526  }
527  }
528  fill(__dst_b, __dst_end_b, __STATIC_CAST(_BucketType*, 0));
529  _M_num_elements = __ht._M_num_elements;
530  _M_max_load_factor = __ht._M_max_load_factor;
531 }
532 
533 #undef __iterator__
534 #undef const_iterator
535 #undef __size_type__
536 #undef __reference__
537 #undef size_type
538 #undef value_type
539 #undef key_type
540 #undef __stl_num_primes
541 
542 #if defined (_STLP_DEBUG)
543 # undef hashtable
545 #endif
546 
548 
549 #endif /* _STLP_HASHTABLE_C */
550 
551 // Local Variables:
552 // mode:C++
553 // End:
return __n
Definition: _algo.h:75
void _M_reduce()
Definition: _hashtable.c:396
iterator end()
Definition: _vector.h:184
#define __STATIC_CAST(__x, __y)
Definition: features.h:585
#define __reference__
Definition: _hashtable.c:122
#define __iterator__
Definition: _hashtable.c:123
float _M_max_load_factor
Definition: _hashtable.h:279
iterator before_begin()
Definition: _slist.h:412
GLuint GLuint end
Definition: gl.h:1545
_STLP_MOVE_TO_PRIV_NAMESPACE less< _Tp > __less(_Tp *)
iterator begin()
Definition: _slist.h:416
_STLP_MOVE_TO_PRIV_NAMESPACE _ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last, const _Tp &__val, _Compare1 __comp1, _Compare2 __comp2, _Distance *)
Definition: _algobase.c:453
#define _STLP_MOVE_TO_PRIV_NAMESPACE
Definition: features.h:524
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
static void _STLP_CALL _S_prev_sizes(size_t __hint, const size_t *&__begin, const size_t *&__end)
iterator _M_insert_noresize(size_type __n, const value_type &__obj)
Definition: _hashtable.c:183
void clear()
Definition: _hashtable.c:501
_STLP_INLINE_LOOP _InputIter __last
Definition: _algo.h:68
#define _STLP_MOVE_TO_STD_NAMESPACE
Definition: features.h:525
GLfloat f
Definition: glext.h:7540
GLsizeiptr size
Definition: glext.h:5919
_STLP_MOVE_TO_STD_NAMESPACE void fill(_ForwardIter __first, _ForwardIter __last, const _Tp &__val)
Definition: _algobase.h:449
#define __size_type__
Definition: _hashtable.c:121
void rehash(size_type __num_buckets_hint)
Definition: _hashtable.c:365
_BucketVector _M_buckets
Definition: _hashtable.h:277
iterator _M_before_begin(size_type &__n) const
Definition: _hashtable.c:148
pair< iterator, bool > insert_unique_noresize(const value_type &__obj)
Definition: _hashtable.c:199
_STLP_MOVE_TO_PRIV_NAMESPACE const _InputIterator const input_iterator_tag &_InputIterator __it(__first)
void _M_rehash(size_type __num_buckets)
Definition: _hashtable.c:454
iterator begin()
Definition: _vector.h:182
_ElemsCont _M_elems
Definition: _hashtable.h:276
#define _STLP_PRIV
Definition: _dm.h:70
static size_t _STLP_CALL _S_max_nb_buckets()
iterator insert_equal_noresize(const value_type &__obj)
Definition: _hashtable.c:230
_In_ int _Val
Definition: memory.h:91
iterator end()
Definition: _slist.h:420
#define __CONST_CAST(__x, __y)
Definition: features.h:584
static size_t _STLP_CALL _S_next_size(size_t)
#define _STLP_END_NAMESPACE
Definition: features.h:503
Definition: _pair.h:47
__kernel_ptrdiff_t ptrdiff_t
Definition: linux.h:247
void _M_copy_from(const _Self &__ht)
Definition: _hashtable.c:510
#define _STLP_ASSERT(expr)
Definition: _debug.h:165
static const size_t * _S_primes(size_t &)
size_type size() const
Definition: _vector.h:192
#define _STLP_BEGIN_NAMESPACE
Definition: features.h:501
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
size_type erase(const key_type &__key)
Definition: _hashtable.c:263
size_type _M_num_elements
Definition: _hashtable.h:278