1 _hashtable.h

     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_DBG_HASHTABLE_H

    31 #define _STLP_INTERNAL_DBG_HASHTABLE_H

    32 

    33 // Hashtable class, used to implement the hashed associative containers

    34 // hash_set, hash_map, hash_multiset, and hash_multimap.

    35 

    36 # include <stl/debug/_iterator.h>

    37 

    38 #  undef  hashtable

    39 #  undef  _DBG_hashtable

    40 #  define _DBG_hashtable  hashtable

    41 

    42 #  define _STLP_DBG_HT_SUPER \

    43 __WORKAROUND_DBG_RENAME(hashtable) <_Val, _Key, _HF, _ExK, _EqK, _All>

    44 

    45 _STLP_BEGIN_NAMESPACE

    46 

    47 # ifdef _STLP_DEBUG_USE_DISTINCT_VALUE_TYPE_HELPERS

    48 template <class _Val, class _Key, class _HF,

    49           class _ExK, class _EqK, class _All>

    50 inline _Val*

    51 value_type(const  _DBG_iter_base< _STLP_DBG_HT_SUPER >&) {

    52   return (_Val*)0;

    53 }

    54 

    55 template <class _Val, class _Key, class _HF,

    56           class _ExK, class _EqK, class _All>

    57 inline forward_iterator_tag

    58 iterator_category(const  _DBG_iter_base< _STLP_DBG_HT_SUPER >&) {

    59   return forward_iterator_tag();

    60 }

    61 # endif

    62 

    63 template <class _Val, class _Key, class _HF,

    64           class _ExK, class _EqK, class _All>

    65 class _DBG_hashtable : public _STLP_DBG_HT_SUPER {

    66   typedef _DBG_hashtable<_Val, _Key, _HF, _ExK, _EqK, _All> _Self;

    67   typedef _STLP_DBG_HT_SUPER _Base;

    68 

    69 public:

    70   typedef _Key key_type;

    71   typedef _HF hasher;

    72   typedef _EqK key_equal;

    73 

    74   __IMPORT_CONTAINER_TYPEDEFS(_Base)

    75 

    76 public:

    77   typedef _DBG_iter<_Base, _Nonconst_traits<value_type> >  iterator;

    78   typedef _DBG_iter<_Base, _Const_traits<value_type> > const_iterator;

    79   typedef typename _Base::iterator _Base_iterator;

    80   typedef typename _Base::const_iterator _Base_const_iterator;

    81 

    82 protected:

    83   void _Invalidate_all() {_M_iter_list._Invalidate_all();}

    84 

    85   void _Invalidate_iterator(const const_iterator& __it) { 

    86     __invalidate_iterator(&_M_iter_list,__it); 

    87   }

    88   void _Invalidate_iterators(const const_iterator& __first, const const_iterator& __last) {

    89     const_iterator __cur = __first;

    90     while (__cur != __last) __invalidate_iterator(&_M_iter_list, __cur++); 

    91   }

    92 

    93   const _Base* _Get_base() const { return (const _Base*)this; }

    94   _Base* _Get_base() { return (_Base*)this; }

    95 

    96 public:

    97   _DBG_hashtable(size_type __n,

    98 		 const _HF&  __hf,

    99 		 const _EqK& __eql,

   100 		 const _ExK& __ext,

   101 		 const allocator_type& __a = allocator_type()):

   102     _STLP_DBG_HT_SUPER(__n, __hf, __eql, __ext, __a),

   103     _M_iter_list(_Get_base()) {}

   104   

   105   _DBG_hashtable(size_type __n,

   106 		 const _HF&    __hf,

   107 		 const _EqK&   __eql,

   108 		 const allocator_type& __a = allocator_type()):

   109     

   110     _STLP_DBG_HT_SUPER(__n, __hf, __eql, __a),

   111     _M_iter_list(_Get_base()) {}

   112   

   113   _DBG_hashtable(const _Self& __ht):

   114     _STLP_DBG_HT_SUPER(__ht),

   115     _M_iter_list(_Get_base()) {}

   116   

   117   _Self& operator= (const _Self& __ht) {

   118     _Invalidate_all();

   119     _Base::operator=(__ht);

   120     return *this;

   121   }

   122   

   123   void swap(_Self& __ht)

   124   {

   125    _M_iter_list._Swap_owners(__ht._M_iter_list);

   126    _Base::swap(__ht);

   127   }

   128 

   129   iterator begin() { return iterator(&_M_iter_list, _Base::begin()); }

   130   iterator end()   { return iterator(&_M_iter_list, _Base::end()); }

   131 

   132   const_iterator begin() const { return const_iterator(&_M_iter_list, _Base::begin()); }

   133   const_iterator end() const { return const_iterator(&_M_iter_list, _Base::end()); }

   134 

   135   pair<iterator, bool> insert_unique(const value_type& __obj)

   136   {

   137     pair < _Base_iterator, bool> __res =

   138       _Base::insert_unique(__obj);

   139     return pair<iterator, bool> ( iterator(&_M_iter_list, __res.first), __res.second);

   140   }

   141 

   142   iterator insert_equal(const value_type& __obj) {

   143     return iterator(&_M_iter_list, _Base::insert_equal(__obj));

   144   }

   145   

   146   pair<iterator, bool> insert_unique_noresize(const value_type& __obj) {

   147     pair < _Base_iterator, bool> __res =

   148       _Base::insert_unique_noresize(__obj);

   149     return pair<iterator, bool> ( iterator(&_M_iter_list, __res.first), __res.second);

   150   }

   151   

   152   iterator insert_equal_noresize(const value_type& __obj) {

   153     return iterator(&_M_iter_list, _Base::insert_equal_noresize(__obj));

   154   }

   155   

   156 #ifdef _STLP_MEMBER_TEMPLATES

   157   template <class _InputIterator>

   158   void insert_unique(_InputIterator __f, _InputIterator __l) {

   159     _Base::insert_unique(__f, __l);

   160   }

   161 

   162   template <class _InputIterator>

   163   void insert_equal(_InputIterator __f, _InputIterator __l){

   164     _Base::insert_equal(__f, __l);

   165   }

   166 

   167 #else /* _STLP_MEMBER_TEMPLATES */

   168 

   169   void insert_unique(const value_type* __f, const value_type* __l) {

   170     _Base::insert_unique(__f, __l);

   171   }

   172   

   173   void insert_equal(const value_type* __f, const value_type* __l) {

   174     _Base::insert_equal(__f, __l);

   175   }

   176   

   177   void insert_unique(const_iterator __f, const_iterator __l) {

   178     _Base::insert_unique(__f._M_iterator, __l._M_iterator);

   179   }

   180   

   181   void insert_equal(const_iterator __f, const_iterator __l) {

   182     _Base::insert_equal(__f._M_iterator, __l._M_iterator);

   183   }

   184 #endif /*_STLP_MEMBER_TEMPLATES */

   185   

   186   iterator find(const key_type& __key) {

   187     return iterator(&_M_iter_list, _Base::find(__key));

   188   } 

   189 

   190   const_iterator find(const key_type& __key) const {

   191     return const_iterator(&_M_iter_list, _Base::find(__key));

   192   } 

   193 

   194   pair<iterator, iterator> 

   195   equal_range(const key_type& __key) {

   196     pair < _Base_iterator, _Base_iterator > __res =

   197       _Base::equal_range(__key);

   198     return pair<iterator,iterator> (iterator(&_M_iter_list,__res.first),

   199 				    iterator(&_M_iter_list,__res.second));

   200   }

   201 

   202   pair<const_iterator, const_iterator> 

   203   equal_range(const key_type& __key) const {

   204     pair <  _Base_const_iterator, _Base_const_iterator > __res =

   205       _Base::equal_range(__key);

   206     return pair<const_iterator,const_iterator> (const_iterator(&_M_iter_list,__res.first),

   207 				    const_iterator(&_M_iter_list,__res.second));

   208   }

   209 

   210   size_type erase(const key_type& __key) {

   211     pair<const_iterator, const_iterator> __p = equal_range(__key);

   212     size_type __n = distance(__p.first, __p.second);

   213     _Invalidate_iterators(__p.first, __p.second);

   214     _Base::erase(__p.first._M_iterator, __p.second._M_iterator);

   215     return __n;

   216   }

   217 

   218   void erase(const const_iterator& __it) {

   219     _STLP_DEBUG_CHECK(__check_if_owner(&_M_iter_list, __it))

   220     _STLP_DEBUG_CHECK(_Dereferenceable(__it))

   221     _Invalidate_iterator(__it);

   222     _Base::erase(__it._M_iterator);

   223   }

   224   void erase(const_iterator __first, const_iterator __last) {

   225     _STLP_DEBUG_CHECK(__check_if_owner(&_M_iter_list, __first)&&

   226                       __check_if_owner(&_M_iter_list, __last))

   227     _Invalidate_iterators(__first, __last);

   228     _Base::erase(__first._M_iterator, __last._M_iterator);

   229   }

   230   void resize(size_type __num_elements_hint) {

   231     _Base::resize(__num_elements_hint);

   232   }

   233   

   234   void clear() {

   235     _Invalidate_all();

   236     _Base::clear();

   237   }

   238 

   239 private:

   240   __owned_list _M_iter_list;

   241 

   242 };

   243 

   244 #define _STLP_TEMPLATE_HEADER template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>

   245 #define _STLP_TEMPLATE_CONTAINER _DBG_hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>

   246 #define _STLP_TEMPLATE_CONTAINER_BASE hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>

   247 #include <stl/debug/_relops_hash_cont.h>

   248 #undef _STLP_TEMPLATE_CONTAINER_BASE

   249 #undef _STLP_TEMPLATE_CONTAINER

   250 #undef _STLP_TEMPLATE_HEADER

   251 

   252 _STLP_END_NAMESPACE

   253 #  undef  hashtable

   254 

   255 #endif /* _STLP_INTERNAL_HASHTABLE_H */

   256 

   257 // Local Variables:

   258 // mode:C++

   259 // End:

   260 

   261