williamr@4: /*
williamr@4:  * Portions Copyright (c) 2008 Nokia Corporation and/or its subsidiary(-ies). All rights reserved.
williamr@4:  *
williamr@4:  * Copyright (c) 1994
williamr@4:  * Hewlett-Packard Company
williamr@4:  *
williamr@4:  * Copyright (c) 1996,1997
williamr@4:  * Silicon Graphics Computer Systems, Inc.
williamr@4:  *
williamr@4:  * Copyright (c) 1997
williamr@4:  * Moscow Center for SPARC Technology
williamr@4:  *
williamr@4:  * Copyright (c) 1999
williamr@4:  * Boris Fomitchev
williamr@4:  *
williamr@4:  * This material is provided "as is", with absolutely no warranty expressed
williamr@4:  * or implied. Any use is at your own risk.
williamr@4:  *
williamr@4:  * Permission to use or copy this software for any purpose is hereby granted
williamr@4:  * without fee, provided the above notices are retained on all copies.
williamr@4:  * Permission to modify the code and to distribute modified code is granted,
williamr@4:  * provided the above notices are retained, and a notice that the code was
williamr@4:  * modified is included with the above copyright notice.
williamr@4:  *
williamr@4:  */
williamr@4: 
williamr@4: /* NOTE: This is an internal header file, included by other STL headers.
williamr@4:  *   You should not attempt to use it directly.
williamr@4:  */
williamr@4: 
williamr@4: #ifndef _STLP_INTERNAL_HASHTABLE_H
williamr@4: #define _STLP_INTERNAL_HASHTABLE_H
williamr@4: 
williamr@4: #ifndef _STLP_INTERNAL_VECTOR_H
williamr@4: #  include <stl/_vector.h>
williamr@4: #endif
williamr@4: 
williamr@4: #ifndef _STLP_INTERNAL_SLIST_H
williamr@4: #  include <stl/_slist.h>
williamr@4: #endif
williamr@4: 
williamr@4: #ifndef _STLP_INTERNAL_ITERATOR_H
williamr@4: #  include <stl/_iterator.h>
williamr@4: #endif
williamr@4: 
williamr@4: #ifndef _STLP_INTERNAL_FUNCTION_BASE_H
williamr@4: #  include <stl/_function_base.h>
williamr@4: #endif
williamr@4: 
williamr@4: #ifndef _STLP_INTERNAL_ALGOBASE_H
williamr@4: #  include <stl/_algobase.h>
williamr@4: #endif
williamr@4: 
williamr@4: #ifndef _STLP_HASH_FUN_H
williamr@4: #  include <stl/_hash_fun.h>
williamr@4: #endif
williamr@4: 
williamr@4: /*
williamr@4:  * Hashtable class, used to implement the hashed associative containers
williamr@4:  * hash_set, hash_map, hash_multiset, hash_multimap,
williamr@4:  * unordered_set, unordered_map, unordered_multiset, unordered_multimap.
williamr@4:  */
williamr@4: 
williamr@4: _STLP_BEGIN_NAMESPACE
williamr@4: 
williamr@4: #if defined (_STLP_USE_TEMPLATE_EXPORT)
williamr@4: //Export of the classes used to represent buckets in the hashtable implementation.
williamr@4: #  if !defined (_STLP_USE_PTR_SPECIALIZATIONS)
williamr@4: //If pointer specialization is enabled vector<_Slist_node_base*> will use the void*
williamr@4: //storage type for which internal classes have already been exported.
williamr@4: _STLP_EXPORT_TEMPLATE_CLASS allocator<_STLP_PRIV _Slist_node_base*>;
williamr@4: 
williamr@4: _STLP_MOVE_TO_PRIV_NAMESPACE
williamr@4: _STLP_EXPORT_TEMPLATE_CLASS _STLP_alloc_proxy<_Slist_node_base**, _Slist_node_base*,
williamr@4:                                               allocator<_Slist_node_base*> >;
williamr@4: _STLP_EXPORT_TEMPLATE_CLASS _Vector_base<_Slist_node_base*,
williamr@4:                                          allocator<_Slist_node_base*> >;
williamr@4: _STLP_MOVE_TO_STD_NAMESPACE
williamr@4: #  endif
williamr@4: 
williamr@4: #  if defined (_STLP_DEBUG)
williamr@4: _STLP_MOVE_TO_PRIV_NAMESPACE
williamr@4: #    define _STLP_NON_DBG_VECTOR _STLP_NON_DBG_NAME(vector)
williamr@4: _STLP_EXPORT_TEMPLATE_CLASS __construct_checker<_STLP_NON_DBG_VECTOR<_Slist_node_base*, allocator<_Slist_node_base*> > >;
williamr@4: _STLP_EXPORT_TEMPLATE_CLASS _STLP_NON_DBG_VECTOR<_Slist_node_base*, allocator<_Slist_node_base*> >;
williamr@4: #    undef _STLP_NON_DBG_VECTOR
williamr@4: _STLP_MOVE_TO_STD_NAMESPACE
williamr@4: #  endif
williamr@4: 
williamr@4: _STLP_EXPORT_TEMPLATE_CLASS vector<_STLP_PRIV _Slist_node_base*,
williamr@4:                                    allocator<_STLP_PRIV _Slist_node_base*> >;
williamr@4: #endif
williamr@4: 
williamr@4: #if defined (_STLP_DEBUG)
williamr@4: #  define hashtable _STLP_NON_DBG_NAME(hashtable)
williamr@4: _STLP_MOVE_TO_PRIV_NAMESPACE
williamr@4: #endif
williamr@4: 
williamr@4: // some compilers require the names of template parameters to be the same
williamr@4: template <class _Val, class _Key, class _HF,
williamr@4:           class _Traits, class _ExK, class _EqK, class _All>
williamr@4: class hashtable;
williamr@4: 
williamr@4: #if !defined (_STLP_DEBUG)
williamr@4: _STLP_MOVE_TO_PRIV_NAMESPACE
williamr@4: #endif
williamr@4: 
williamr@4: template <class _BaseIte, class _Traits>
williamr@4: struct _Ht_iterator {
williamr@4:   typedef typename _Traits::_ConstTraits _ConstTraits;
williamr@4:   typedef typename _Traits::_NonConstTraits _NonConstTraits;
williamr@4: 
williamr@4:   typedef _Ht_iterator<_BaseIte,_Traits> _Self;
williamr@4: 
williamr@4:   typedef typename _Traits::value_type value_type;
williamr@4:   typedef typename _Traits::pointer pointer;
williamr@4:   typedef typename _Traits::reference reference;
williamr@4:   typedef forward_iterator_tag iterator_category;
williamr@4:   typedef ptrdiff_t difference_type;
williamr@4:   typedef size_t size_type;
williamr@4: 
williamr@4:   typedef _Ht_iterator<_BaseIte, _NonConstTraits> iterator;
williamr@4:   typedef _Ht_iterator<_BaseIte, _ConstTraits> const_iterator;
williamr@4: 
williamr@4:   _Ht_iterator() {}
williamr@4:   //copy constructor for iterator and constructor from iterator for const_iterator
williamr@4:   _Ht_iterator(const iterator& __it) : _M_ite(__it._M_ite) {}
williamr@4:   _Ht_iterator(_BaseIte __it) : _M_ite(__it) {}
williamr@4: 
williamr@4:   reference operator*() const {
williamr@4:     return *_M_ite;
williamr@4:   }
williamr@4:   _STLP_DEFINE_ARROW_OPERATOR
williamr@4: 
williamr@4:   _Self& operator++() {
williamr@4:     ++_M_ite;
williamr@4:     return *this;
williamr@4:   }
williamr@4:   _Self operator++(int) {
williamr@4:     _Self __tmp = *this;
williamr@4:     ++*this;
williamr@4:     return __tmp;
williamr@4:   }
williamr@4: 
williamr@4:   bool operator == (const_iterator __rhs) const {
williamr@4:     return _M_ite == __rhs._M_ite;
williamr@4:   }
williamr@4:   bool operator != (const_iterator __rhs) const {
williamr@4:     return _M_ite != __rhs._M_ite;
williamr@4:   }
williamr@4: 
williamr@4:   _BaseIte _M_ite;
williamr@4: };
williamr@4: 
williamr@4: _STLP_MOVE_TO_STD_NAMESPACE
williamr@4: 
williamr@4: #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
williamr@4: template <class _BaseIte, class _Traits>
williamr@4: struct __type_traits<_STLP_PRIV _Ht_iterator<_BaseIte, _Traits> > {
williamr@4:   typedef __false_type   has_trivial_default_constructor;
williamr@4:   typedef __true_type    has_trivial_copy_constructor;
williamr@4:   typedef __true_type    has_trivial_assignment_operator;
williamr@4:   typedef __true_type    has_trivial_destructor;
williamr@4:   typedef __false_type   is_POD_type;
williamr@4: };
williamr@4: #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
williamr@4: 
williamr@4: #if defined (_STLP_USE_OLD_HP_ITERATOR_QUERIES)
williamr@4: template <class _BaseIte, class _Traits>
williamr@4: inline
williamr@4: #  if defined (_STLP_NESTED_TYPE_PARAM_BUG)
williamr@4: _STLP_TYPENAME_ON_RETURN_TYPE _Traits::value_type *
williamr@4: #  else
williamr@4: _STLP_TYPENAME_ON_RETURN_TYPE _STLP_PRIV _Ht_iterator<_BaseIte,_Traits>::value_type *
williamr@4: #  endif
williamr@4: value_type(const _STLP_PRIV _Ht_iterator<_BaseIte,_Traits>&) {
williamr@4:   typedef typename _STLP_PRIV _Ht_iterator<_BaseIte,_Traits>::value_type _Val;
williamr@4:   return (_Val*) 0;
williamr@4: }
williamr@4: template <class _BaseIte, class _Traits>
williamr@4: inline forward_iterator_tag iterator_category(const _STLP_PRIV _Ht_iterator<_BaseIte,_Traits>&)
williamr@4: { return forward_iterator_tag(); }
williamr@4: template <class _BaseIte, class _Traits>
williamr@4: inline ptrdiff_t* distance_type(const _STLP_PRIV _Ht_iterator<_BaseIte,_Traits>&)
williamr@4: { return (ptrdiff_t*) 0; }
williamr@4: #endif
williamr@4: 
williamr@4: _STLP_MOVE_TO_PRIV_NAMESPACE
williamr@4: 
williamr@4: template <class _Dummy>
williamr@4: class _Stl_prime {
williamr@4: public:
williamr@4:   //Returns the maximum number of buckets handled by the hashtable implementation
williamr@4:   static size_t _STLP_CALL _S_max_nb_buckets();
williamr@4: 
williamr@4:   //Returns the bucket size next to a required size
williamr@4:   static size_t _STLP_CALL _S_next_size(size_t);
williamr@4: };
williamr@4: 
williamr@4: #if defined (_STLP_USE_TEMPLATE_EXPORT)
williamr@4: _STLP_EXPORT_TEMPLATE_CLASS _Stl_prime<bool>;
williamr@4: #endif
williamr@4: 
williamr@4: typedef _Stl_prime<bool> _Stl_prime_type;
williamr@4: 
williamr@4: #if !defined (_STLP_DEBUG)
williamr@4: _STLP_MOVE_TO_STD_NAMESPACE
williamr@4: #endif
williamr@4: 
williamr@4: /*
williamr@4:  * Hashtables handle allocators a bit differently than other containers
williamr@4:  * do. If we're using standard-conforming allocators, then a hashtable
williamr@4:  * unconditionally has a member variable to hold its allocator, even if
williamr@4:  * it so happens that all instances of the allocator type are identical.
williamr@4:  * This is because, for hashtables, this extra storage is negligible.
williamr@4:  * Additionally, a base class wouldn't serve any other purposes; it
williamr@4:  * wouldn't, for example, simplify the exception-handling code.
williamr@4:  */
williamr@4: template <class _Val, class _Key, class _HF,
williamr@4:           class _Traits, class _ExK, class _EqK, class _All>
williamr@4: class hashtable {
williamr@4:   typedef hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All> _Self;
williamr@4:   typedef typename _Traits::_NonConstTraits _NonConstTraits;
williamr@4:   typedef typename _Traits::_ConstTraits _ConstTraits;
williamr@4:   typedef typename _Traits::_NonConstLocalTraits _NonConstLocalTraits;
williamr@4:   typedef typename _Traits::_ConstLocalTraits _ConstLocalTraits;
williamr@4: 
williamr@4: public:
williamr@4:   typedef _Key key_type;
williamr@4:   typedef _Val value_type;
williamr@4:   typedef _HF hasher;
williamr@4:   typedef _EqK key_equal;
williamr@4: 
williamr@4:   typedef size_t            size_type;
williamr@4:   typedef ptrdiff_t         difference_type;
williamr@4:   typedef typename _NonConstTraits::pointer pointer;
williamr@4:   typedef const value_type* const_pointer;
williamr@4:   typedef typename _NonConstTraits::reference reference;
williamr@4:   typedef const value_type& const_reference;
williamr@4:   typedef forward_iterator_tag _Iterator_category;
williamr@4: 
williamr@4:   hasher hash_funct() const { return _M_hash; }
williamr@4:   key_equal key_eq() const { return _M_equals; }
williamr@4: 
williamr@4: private:
williamr@4:   _STLP_FORCE_ALLOCATORS(_Val, _All)
williamr@4: #if defined (_STLP_DEBUG)
williamr@4:   typedef _STLP_PRIV _STLP_NON_DBG_NAME(slist)<value_type, _All> _ElemsCont;
williamr@4: #else
williamr@4:   typedef slist<value_type, _All> _ElemsCont;
williamr@4: #endif
williamr@4:   typedef typename _ElemsCont::iterator _ElemsIte;
williamr@4:   typedef typename _ElemsCont::const_iterator _ElemsConstIte;
williamr@4:   typedef _STLP_PRIV _Slist_node_base _BucketType;
williamr@4:   typedef typename _Alloc_traits<_BucketType*, _All>::allocator_type _M_bucket_allocator_type;
williamr@4:   /*
williamr@4:    * We are going to use vector of _Slist_node_base pointers for 2 reasons:
williamr@4:    *  - limit code bloat, all hashtable instanciation use the same buckets representation.
williamr@4:    *  - avoid _STLP_DEBUG performance trouble: with a vector of iterator on slist the resize
williamr@4:    *    method would be too slow because the slist::splice_after method become linear on
williamr@4:    *    the number of iterators in the buckets rather than constant in time as the iterator
williamr@4:    *    has to be move from a slist to the other.
williamr@4:    */
williamr@4: #if defined (_STLP_DEBUG)
williamr@4:   typedef _STLP_PRIV _STLP_NON_DBG_NAME(vector)<_BucketType*, _M_bucket_allocator_type> _BucketVector;
williamr@4: #else
williamr@4:   typedef vector<_BucketType*, _M_bucket_allocator_type> _BucketVector;
williamr@4: #endif
williamr@4: 
williamr@4:   hasher                _M_hash;
williamr@4:   key_equal             _M_equals;
williamr@4:   _ExK                  _M_get_key;
williamr@4:   _ElemsCont            _M_elems;
williamr@4:   _BucketVector         _M_buckets;
williamr@4:   size_type             _M_num_elements;
williamr@4:   float                 _M_max_load_factor;
williamr@4:   _STLP_KEY_TYPE_FOR_CONT_EXT(key_type)
williamr@4: 
williamr@4: public:
williamr@4:   typedef _STLP_PRIV _Ht_iterator<_ElemsIte, _NonConstTraits> iterator;
williamr@4:   typedef _STLP_PRIV _Ht_iterator<_ElemsIte, _ConstTraits> const_iterator;
williamr@4:   //TODO: Avoids this debug check and make the local_iterator different from
williamr@4:   //iterator in debug mode too.
williamr@4: #if !defined (_STLP_DEBUG)
williamr@4:   typedef _STLP_PRIV _Ht_iterator<_ElemsIte, _NonConstLocalTraits> local_iterator;
williamr@4:   typedef _STLP_PRIV _Ht_iterator<_ElemsIte, _ConstLocalTraits> const_local_iterator;
williamr@4: #else
williamr@4:   typedef iterator       local_iterator;
williamr@4:   typedef const_iterator const_local_iterator;
williamr@4: #endif
williamr@4: 
williamr@4:   typedef typename _Alloc_traits<_Val, _All>::allocator_type allocator_type;
williamr@4:   allocator_type get_allocator() const { return _M_elems.get_allocator(); }
williamr@4: 
williamr@4: #if !defined (_STLP_DONT_SUP_DFLT_PARAM)
williamr@4:   hashtable(size_type __n,
williamr@4:             const _HF&  __hf,
williamr@4:             const _EqK& __eql,
williamr@4:             const _ExK& __ext,
williamr@4:             const allocator_type& __a = allocator_type())
williamr@4: #else
williamr@4:   hashtable(size_type __n,
williamr@4:             const _HF&  __hf,
williamr@4:             const _EqK& __eql,
williamr@4:             const _ExK& __ext)
williamr@4:     : _M_hash(__hf),
williamr@4:       _M_equals(__eql),
williamr@4:       _M_get_key(__ext),
williamr@4:       _M_elems(allocator_type()),
williamr@4:       _M_buckets(_STLP_CONVERT_ALLOCATOR(__a, _BucketType*)),
williamr@4:       _M_num_elements(0),
williamr@4:       _M_max_load_factor(1.0f)
williamr@4:   { _M_initialize_buckets(__n); }
williamr@4: 
williamr@4:   hashtable(size_type __n,
williamr@4:             const _HF&  __hf,
williamr@4:             const _EqK& __eql,
williamr@4:             const _ExK& __ext,
williamr@4:             const allocator_type& __a)
williamr@4: #endif
williamr@4:     : _M_hash(__hf),
williamr@4:       _M_equals(__eql),
williamr@4:       _M_get_key(__ext),
williamr@4:       _M_elems(__a),
williamr@4:       _M_buckets(_STLP_CONVERT_ALLOCATOR(__a, _BucketType*)),
williamr@4:       _M_num_elements(0),
williamr@4:       _M_max_load_factor(1.0f)
williamr@4:   { _M_initialize_buckets(__n); }
williamr@4: 
williamr@4: #if !defined (_STLP_DONT_SUP_DFLT_PARAM)
williamr@4:   hashtable(size_type __n,
williamr@4:             const _HF&    __hf,
williamr@4:             const _EqK&   __eql,
williamr@4:             const allocator_type& __a = allocator_type())
williamr@4: #else
williamr@4:   hashtable(size_type __n,
williamr@4:             const _HF&    __hf,
williamr@4:             const _EqK&   __eql)
williamr@4:     : _M_hash(__hf),
williamr@4:       _M_equals(__eql),
williamr@4:       _M_get_key(_ExK()),
williamr@4:       _M_elems(allocator_type()),
williamr@4:       _M_buckets(_STLP_CONVERT_ALLOCATOR(__a, _BucketType*)),
williamr@4:       _M_num_elements(0),
williamr@4:       _M_max_load_factor(1.0f)
williamr@4:   { _M_initialize_buckets(__n); }
williamr@4: 
williamr@4:   hashtable(size_type __n,
williamr@4:             const _HF&    __hf,
williamr@4:             const _EqK&   __eql,
williamr@4:             const allocator_type& __a)
williamr@4: #endif
williamr@4:     : _M_hash(__hf),
williamr@4:       _M_equals(__eql),
williamr@4:       _M_get_key(_ExK()),
williamr@4:       _M_elems(__a),
williamr@4:       _M_buckets(_STLP_CONVERT_ALLOCATOR(__a, _BucketType*)),
williamr@4:       _M_num_elements(0),
williamr@4:       _M_max_load_factor(1.0f)
williamr@4:   { _M_initialize_buckets(__n); }
williamr@4: 
williamr@4:   hashtable(const _Self& __ht)
williamr@4:     : _M_hash(__ht._M_hash),
williamr@4:       _M_equals(__ht._M_equals),
williamr@4:       _M_get_key(__ht._M_get_key),
williamr@4:       _M_elems(__ht.get_allocator()),
williamr@4:       _M_buckets(_STLP_CONVERT_ALLOCATOR(__ht.get_allocator(), _BucketType*)),
williamr@4:       _M_num_elements(0),
williamr@4:       _M_max_load_factor(1.0f)
williamr@4:   { _M_copy_from(__ht); }
williamr@4: 
williamr@4:   hashtable(__move_source<_Self> src)
williamr@4:     : _M_hash(_STLP_PRIV _AsMoveSource(src.get()._M_hash)),
williamr@4:       _M_equals(_STLP_PRIV _AsMoveSource(src.get()._M_equals)),
williamr@4:       _M_get_key(_STLP_PRIV _AsMoveSource(src.get()._M_get_key)),
williamr@4:       _M_elems(__move_source<_ElemsCont>(src.get()._M_elems)),
williamr@4:       _M_buckets(__move_source<_BucketVector>(src.get()._M_buckets)),
williamr@4:       _M_num_elements(src.get()._M_num_elements),
williamr@4:       _M_max_load_factor(src.get()._M_max_load_factor) {}
williamr@4: 
williamr@4:   _Self& operator= (const _Self& __ht) {
williamr@4:     if (&__ht != this) {
williamr@4:       clear();
williamr@4:       _M_hash = __ht._M_hash;
williamr@4:       _M_equals = __ht._M_equals;
williamr@4:       _M_get_key = __ht._M_get_key;
williamr@4:       _M_copy_from(__ht);
williamr@4:     }
williamr@4:     return *this;
williamr@4:   }
williamr@4: 
williamr@4:   ~hashtable() { clear(); }
williamr@4: 
williamr@4:   size_type size() const { return _M_num_elements; }
williamr@4:   size_type max_size() const { return size_type(-1); }
williamr@4:   bool empty() const { return size() == 0; }
williamr@4: 
williamr@4:   void swap(_Self& __ht) {
williamr@4:     _STLP_STD::swap(_M_hash, __ht._M_hash);
williamr@4:     _STLP_STD::swap(_M_equals, __ht._M_equals);
williamr@4:     _STLP_STD::swap(_M_get_key, __ht._M_get_key);
williamr@4:     _M_elems.swap(__ht._M_elems);
williamr@4:     _M_buckets.swap(__ht._M_buckets);
williamr@4:     _STLP_STD::swap(_M_num_elements, __ht._M_num_elements);
williamr@4:     _STLP_STD::swap(_M_max_load_factor, __ht._M_max_load_factor);
williamr@4:   }
williamr@4: 
williamr@4:   iterator begin() { return _M_elems.begin(); }
williamr@4:   iterator end() { return _M_elems.end(); }
williamr@4:   local_iterator begin(size_type __n) { return _ElemsIte(_M_buckets[__n]); }
williamr@4:   local_iterator end(size_type __n) { return _ElemsIte(_M_buckets[__n + 1]); }
williamr@4: 
williamr@4:   const_iterator begin() const { return __CONST_CAST(_ElemsCont&, _M_elems).begin(); }
williamr@4:   const_iterator end() const { return __CONST_CAST(_ElemsCont&, _M_elems).end(); }
williamr@4:   const_local_iterator begin(size_type __n) const { return _ElemsIte(_M_buckets[__n]); }
williamr@4:   const_local_iterator end(size_type __n) const { return _ElemsIte(_M_buckets[__n + 1]); }
williamr@4: 
williamr@4:   //static bool _STLP_CALL _M_equal (const _Self&, const _Self&);
williamr@4: 
williamr@4: public:
williamr@4:   //The number of buckets is size() - 1 because the last bucket always contains
williamr@4:   //_M_elems.end() to make algo easier to implement.
williamr@4:   size_type bucket_count() const { return _M_buckets.size() - 1; }
williamr@4:   size_type max_bucket_count() const { return _STLP_PRIV _Stl_prime_type::_S_max_nb_buckets(); }
williamr@4:   size_type elems_in_bucket(size_type __bucket) const
williamr@4:   { return distance(_ElemsIte(_M_buckets[__bucket]), _ElemsIte(_M_buckets[__bucket + 1])); }
williamr@4: 
williamr@4:   _STLP_TEMPLATE_FOR_CONT_EXT
williamr@4:   size_type bucket(const _KT& __k) const { return _M_bkt_num_key(__k); }
williamr@4: 
williamr@4:   // hash policy
williamr@4:   float load_factor() const { return (float)size() / (float)bucket_count(); }
williamr@4:   float max_load_factor() const { return _M_max_load_factor; }
williamr@4:   void max_load_factor(float __z) { _M_max_load_factor = __z;}
williamr@4: 
williamr@4:   pair<iterator, bool> insert_unique(const value_type& __obj) {
williamr@4:     resize(_M_num_elements + 1);
williamr@4:     return insert_unique_noresize(__obj);
williamr@4:   }
williamr@4: 
williamr@4:   iterator insert_equal(const value_type& __obj) {
williamr@4:     resize(_M_num_elements + 1);
williamr@4:     return insert_equal_noresize(__obj);
williamr@4:   }
williamr@4: 
williamr@4: protected:
williamr@4:   iterator _M_insert_noresize(size_type __n, const value_type& __obj);
williamr@4: public:
williamr@4:   pair<iterator, bool> insert_unique_noresize(const value_type& __obj);
williamr@4:   iterator insert_equal_noresize(const value_type& __obj);
williamr@4: 
williamr@4: #if defined (_STLP_MEMBER_TEMPLATES)
williamr@4:   template <class _InputIterator>
williamr@4:   void insert_unique(_InputIterator __f, _InputIterator __l)
williamr@4:   { insert_unique(__f, __l, _STLP_ITERATOR_CATEGORY(__f, _InputIterator)); }
williamr@4: 
williamr@4:   template <class _InputIterator>
williamr@4:   void insert_equal(_InputIterator __f, _InputIterator __l)
williamr@4:   { insert_equal(__f, __l, _STLP_ITERATOR_CATEGORY(__f, _InputIterator)); }
williamr@4: 
williamr@4:   template <class _InputIterator>
williamr@4:   void insert_unique(_InputIterator __f, _InputIterator __l,
williamr@4:                      const input_iterator_tag &) {
williamr@4:     for ( ; __f != __l; ++__f)
williamr@4:       insert_unique(*__f);
williamr@4:   }
williamr@4: 
williamr@4:   template <class _InputIterator>
williamr@4:   void insert_equal(_InputIterator __f, _InputIterator __l,
williamr@4:                     const input_iterator_tag &) {
williamr@4:     for ( ; __f != __l; ++__f)
williamr@4:       insert_equal(*__f);
williamr@4:   }
williamr@4: 
williamr@4:   template <class _ForwardIterator>
williamr@4:   void insert_unique(_ForwardIterator __f, _ForwardIterator __l,
williamr@4:                      const forward_iterator_tag &) {
williamr@4:     size_type __n = distance(__f, __l);
williamr@4:     resize(_M_num_elements + __n);
williamr@4:     for ( ; __n > 0; --__n, ++__f)
williamr@4:       insert_unique_noresize(*__f);
williamr@4:   }
williamr@4: 
williamr@4:   template <class _ForwardIterator>
williamr@4:   void insert_equal(_ForwardIterator __f, _ForwardIterator __l,
williamr@4:                     const forward_iterator_tag &) {
williamr@4:     size_type __n = distance(__f, __l);
williamr@4:     resize(_M_num_elements + __n);
williamr@4:     for ( ; __n > 0; --__n, ++__f)
williamr@4:       insert_equal_noresize(*__f);
williamr@4:   }
williamr@4: 
williamr@4: #else /* _STLP_MEMBER_TEMPLATES */
williamr@4:   void insert_unique(const value_type* __f, const value_type* __l) {
williamr@4:     size_type __n = __l - __f;
williamr@4:     resize(_M_num_elements + __n);
williamr@4:     for ( ; __n > 0; --__n, ++__f)
williamr@4:       insert_unique_noresize(*__f);
williamr@4:   }
williamr@4: 
williamr@4:   void insert_equal(const value_type* __f, const value_type* __l) {
williamr@4:     size_type __n = __l - __f;
williamr@4:     resize(_M_num_elements + __n);
williamr@4:     for ( ; __n > 0; --__n, ++__f)
williamr@4:       insert_equal_noresize(*__f);
williamr@4:   }
williamr@4: 
williamr@4:   void insert_unique(const_iterator __f, const_iterator __l) {
williamr@4:     size_type __n = distance(__f, __l);
williamr@4:     resize(_M_num_elements + __n);
williamr@4:     for ( ; __n > 0; --__n, ++__f)
williamr@4:       insert_unique_noresize(*__f);
williamr@4:   }
williamr@4: 
williamr@4:   void insert_equal(const_iterator __f, const_iterator __l) {
williamr@4:     size_type __n = distance(__f, __l);
williamr@4:     resize(_M_num_elements + __n);
williamr@4:     for ( ; __n > 0; --__n, ++__f)
williamr@4:       insert_equal_noresize(*__f);
williamr@4:   }
williamr@4: #endif /*_STLP_MEMBER_TEMPLATES */
williamr@4: 
williamr@4:   //reference find_or_insert(const value_type& __obj);
williamr@4: 
williamr@4: private:
williamr@4:   _STLP_TEMPLATE_FOR_CONT_EXT
williamr@4:   _ElemsIte _M_find(const _KT& __key) const {
williamr@4:     size_type __n = _M_bkt_num_key(__key);
williamr@4:     _ElemsIte __first(_M_buckets[__n]);
williamr@4:     _ElemsIte __last(_M_buckets[__n + 1]);
williamr@4:     for ( ; (__first != __last) && !_M_equals(_M_get_key(*__first), __key); ++__first) {}
williamr@4:     if (__first != __last)
williamr@4:       return __first;
williamr@4:     else
williamr@4:       return __CONST_CAST(_ElemsCont&, _M_elems).end();
williamr@4:   }
williamr@4: 
williamr@4: public:
williamr@4:   _STLP_TEMPLATE_FOR_CONT_EXT
williamr@4:   iterator find(const _KT& __key) { return _M_find(__key); }
williamr@4:   _STLP_TEMPLATE_FOR_CONT_EXT
williamr@4:   const_iterator find(const _KT& __key) const { return _M_find(__key); }
williamr@4: 
williamr@4:   _STLP_TEMPLATE_FOR_CONT_EXT
williamr@4:   size_type count(const _KT& __key) const {
williamr@4:     const size_type __n = _M_bkt_num_key(__key);
williamr@4: 
williamr@4:     _ElemsIte __cur(_M_buckets[__n]);
williamr@4:     _ElemsIte __last(_M_buckets[__n + 1]);
williamr@4:     for (; __cur != __last; ++__cur) {
williamr@4:       if (_M_equals(_M_get_key(*__cur), __key)) {
williamr@4:         size_type __result = 1;
williamr@4:         for (++__cur;
williamr@4:              __cur != __last && _M_equals(_M_get_key(*__cur), __key);
williamr@4:              ++__result, ++__cur);
williamr@4:         return __result;
williamr@4:       }
williamr@4:     }
williamr@4:     return 0;
williamr@4:   }
williamr@4: 
williamr@4:   _STLP_TEMPLATE_FOR_CONT_EXT
williamr@4:   pair<iterator, iterator> equal_range(const _KT& __key) {
williamr@4:     typedef pair<iterator, iterator> _Pii;
williamr@4:     const size_type __n = _M_bkt_num_key(__key);
williamr@4: 
williamr@4:     for (_ElemsIte __first(_M_buckets[__n]), __last(_M_buckets[__n + 1]);
williamr@4:          __first != __last; ++__first) {
williamr@4:       if (_M_equals(_M_get_key(*__first), __key)) {
williamr@4:         _ElemsIte __cur(__first);
williamr@4:         for (++__cur; (__cur != __last) && _M_equals(_M_get_key(*__cur), __key); ++__cur);
williamr@4:         return _Pii(__first, __cur);
williamr@4:       }
williamr@4:     }
williamr@4:     return _Pii(end(), end());
williamr@4:   }
williamr@4: 
williamr@4:   _STLP_TEMPLATE_FOR_CONT_EXT
williamr@4:   pair<const_iterator, const_iterator> equal_range(const _KT& __key) const {
williamr@4:     typedef pair<const_iterator, const_iterator> _Pii;
williamr@4:     const size_type __n = _M_bkt_num_key(__key);
williamr@4: 
williamr@4:     for (_ElemsIte __first(_M_buckets[__n]), __last(_M_buckets[__n + 1]);
williamr@4:          __first != __last; ++__first) {
williamr@4:       if (_M_equals(_M_get_key(*__first), __key)) {
williamr@4:         _ElemsIte __cur(__first);
williamr@4:         for (++__cur; (__cur != __last) && _M_equals(_M_get_key(*__cur), __key); ++__cur);
williamr@4:         return _Pii(__first, __cur);
williamr@4:       }
williamr@4:     }
williamr@4:     return _Pii(end(), end());
williamr@4:   }
williamr@4: 
williamr@4:   size_type erase(const key_type& __key);
williamr@4:   void erase(const_iterator __it);
williamr@4:   void erase(const_iterator __first, const_iterator __last);
williamr@4: 
williamr@4: private:
williamr@4:   void _M_rehash(size_type __num_buckets);
williamr@4: #if defined (_STLP_DEBUG)
williamr@4:   void _M_check() const;
williamr@4: #endif
williamr@4: 
williamr@4: public:
williamr@4:   void rehash(size_type __num_buckets_hint);
williamr@4:   void resize(size_type __num_elements_hint);
williamr@4:   void clear();
williamr@4: 
williamr@4:   // this is for hash_map::operator[]
williamr@4:   reference _M_insert(const value_type& __obj);
williamr@4: 
williamr@4: private:
williamr@4:   //__n is set to the first bucket that has to be modified if any
williamr@4:   //erase/insert operation is done after the returned iterator.
williamr@4:   iterator _M_before_begin(size_type &__n) const;
williamr@4: 
williamr@4:   static iterator _S_before_begin(const _ElemsCont& __elems, const _BucketVector& __buckets,
williamr@4:                                   size_type &__n);
williamr@4: 
williamr@4:   void _M_initialize_buckets(size_type __n) {
williamr@4:     const size_type __n_buckets = _STLP_PRIV _Stl_prime_type::_S_next_size(__n) + 1;
williamr@4:     _M_buckets.reserve(__n_buckets);
williamr@4:     _M_buckets.assign(__n_buckets, __STATIC_CAST(_BucketType*, 0));
williamr@4:   }
williamr@4: 
williamr@4:   _STLP_TEMPLATE_FOR_CONT_EXT
williamr@4:   size_type _M_bkt_num_key(const _KT& __key) const
williamr@4:   { return _M_bkt_num_key(__key, bucket_count()); }
williamr@4: 
williamr@4:   size_type _M_bkt_num(const value_type& __obj) const
williamr@4:   { return _M_bkt_num_key(_M_get_key(__obj)); }
williamr@4: 
williamr@4:   _STLP_TEMPLATE_FOR_CONT_EXT
williamr@4:   size_type _M_bkt_num_key(const _KT& __key, size_type __n) const
williamr@4:   { return _M_hash(__key) % __n; }
williamr@4: 
williamr@4:   size_type _M_bkt_num(const value_type& __obj, size_t __n) const
williamr@4:   { return _M_bkt_num_key(_M_get_key(__obj), __n); }
williamr@4: 
williamr@4:   void _M_copy_from(const _Self& __ht);
williamr@4: };
williamr@4: 
williamr@4: #if defined (_STLP_DEBUG)
williamr@4: #  undef hashtable
williamr@4: _STLP_MOVE_TO_STD_NAMESPACE
williamr@4: #endif
williamr@4: 
williamr@4: _STLP_END_NAMESPACE
williamr@4: 
williamr@4: #if !defined (_STLP_LINK_TIME_INSTANTIATION)
williamr@4: #  include <stl/_hashtable.c>
williamr@4: #endif
williamr@4: 
williamr@4: #if defined (_STLP_DEBUG)
williamr@4: #  include <stl/debug/_hashtable.h>
williamr@4: #endif
williamr@4: 
williamr@4: _STLP_BEGIN_NAMESPACE
williamr@4: 
williamr@4: #define _STLP_TEMPLATE_HEADER template <class _Val, class _Key, class _HF, class _Traits, class _ExK, class _EqK, class _All>
williamr@4: #define _STLP_TEMPLATE_CONTAINER hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
williamr@4: #include <stl/_relops_hash_cont.h>
williamr@4: #undef _STLP_TEMPLATE_CONTAINER
williamr@4: #undef _STLP_TEMPLATE_HEADER
williamr@4: 
williamr@4: #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
williamr@4: template <class _Val, class _Key, class _HF, class _Traits, class _ExK, class _EqK, class _All>
williamr@4: struct __move_traits<hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All> > {
williamr@4:   //Hashtables are movable:
williamr@4:   typedef __stlp_movable implemented;
williamr@4: 
williamr@4:   //Completeness depends on many template parameters, for the moment we consider it not complete:
williamr@4:   typedef __false_type complete;
williamr@4: };
williamr@4: #endif
williamr@4: 
williamr@4: _STLP_END_NAMESPACE
williamr@4: 
williamr@4: #endif /* _STLP_INTERNAL_HASHTABLE_H */
williamr@4: 
williamr@4: // Local Variables:
williamr@4: // mode:C++
williamr@4: // End: