contrib/gcc-3.4/libstdc++-v3/include/ext/hash_map

   1 // Hashing map implementation -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 2, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // You should have received a copy of the GNU General Public License along
  17 // with this library; see the file COPYING.  If not, write to the Free
  18 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
  19 // USA.
  20
  21 // As a special exception, you may use this file as part of a free software
  22 // library without restriction.  Specifically, if other files instantiate
  23 // templates or use macros or inline functions from this file, or you compile
  24 // this file and link it with other files to produce an executable, this
  25 // file does not by itself cause the resulting executable to be covered by
  26 // the GNU General Public License.  This exception does not however
  27 // invalidate any other reasons why the executable file might be covered by
  28 // the GNU General Public License.
  29
  30 /*
  31  * Copyright (c) 1996
  32  * Silicon Graphics Computer Systems, Inc.
  33  *
  34  * Permission to use, copy, modify, distribute and sell this software
  35  * and its documentation for any purpose is hereby granted without fee,
  36  * provided that the above copyright notice appear in all copies and
  37  * that both that copyright notice and this permission notice appear
  38  * in supporting documentation.  Silicon Graphics makes no
  39  * representations about the suitability of this software for any
  40  * purpose.  It is provided "as is" without express or implied warranty.
  41  *
  42  *
  43  * Copyright (c) 1994
  44  * Hewlett-Packard Company
  45  *
  46  * Permission to use, copy, modify, distribute and sell this software
  47  * and its documentation for any purpose is hereby granted without fee,
  48  * provided that the above copyright notice appear in all copies and
  49  * that both that copyright notice and this permission notice appear
  50  * in supporting documentation.  Hewlett-Packard Company makes no
  51  * representations about the suitability of this software for any
  52  * purpose.  It is provided "as is" without express or implied warranty.
  53  *
  54  */
  55
  56 /** @file ext/hash_map
  57  *  This file is a GNU extension to the Standard C++ Library (possibly
  58  *  containing extensions from the HP/SGI STL subset).  You should only
  59  *  include this header if you are using GCC 3 or later.
  60  */
  61
  62 #ifndef _HASH_MAP
  63 #define _HASH_MAP 1
  64
  65 #include <ext/hashtable.h>
  66 #include <bits/concept_check.h>
  67
  68 namespace __gnu_cxx
  69 {
  70   using std::equal_to;
  71   using std::allocator;
  72   using std::pair;
  73   using std::_Select1st;
  74
  75   // Forward declaration of equality operator; needed for friend
  76   // declaration.
  77   template<class _Key, class _Tp, class _HashFcn  = hash<_Key>,
  78             class _EqualKey = equal_to<_Key>, class _Alloc =  allocator<_Tp> >
  79     class hash_map;
  80
  81   template<class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc>
  82   inline bool operator==(const hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>&,
  83                          const hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>&);
  84 /**
  85  *  This is an SGI extension.
  86  *  @ingroup SGIextensions
  87  *  @doctodo
  88 */
  89 template <class _Key, class _Tp, class _HashFcn, class _EqualKey,
  90           class _Alloc>
  91 class hash_map
  92 {
  93 private:
  94   typedef hashtable<pair<const _Key,_Tp>,_Key,_HashFcn,
  95                     _Select1st<pair<const _Key,_Tp> >,_EqualKey,_Alloc> _Ht;
  96   _Ht _M_ht;
  97
  98 public:
  99   typedef typename _Ht::key_type key_type;
 100   typedef _Tp data_type;
 101   typedef _Tp mapped_type;
 102   typedef typename _Ht::value_type value_type;
 103   typedef typename _Ht::hasher hasher;
 104   typedef typename _Ht::key_equal key_equal;
 105
 106   typedef typename _Ht::size_type size_type;
 107   typedef typename _Ht::difference_type difference_type;
 108   typedef typename _Ht::pointer pointer;
 109   typedef typename _Ht::const_pointer const_pointer;
 110   typedef typename _Ht::reference reference;
 111   typedef typename _Ht::const_reference const_reference;
 112
 113   typedef typename _Ht::iterator iterator;
 114   typedef typename _Ht::const_iterator const_iterator;
 115
 116   typedef typename _Ht::allocator_type allocator_type;
 117
 118   hasher hash_funct() const { return _M_ht.hash_funct(); }
 119   key_equal key_eq() const { return _M_ht.key_eq(); }
 120   allocator_type get_allocator() const { return _M_ht.get_allocator(); }
 121
 122 public:
 123   hash_map() : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
 124   explicit hash_map(size_type __n)
 125     : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
 126   hash_map(size_type __n, const hasher& __hf)
 127     : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
 128   hash_map(size_type __n, const hasher& __hf, const key_equal& __eql,
 129            const allocator_type& __a = allocator_type())
 130     : _M_ht(__n, __hf, __eql, __a) {}
 131
 132   template <class _InputIterator>
 133   hash_map(_InputIterator __f, _InputIterator __l)
 134     : _M_ht(100, hasher(), key_equal(), allocator_type())
 135     { _M_ht.insert_unique(__f, __l); }
 136   template <class _InputIterator>
 137   hash_map(_InputIterator __f, _InputIterator __l, size_type __n)
 138     : _M_ht(__n, hasher(), key_equal(), allocator_type())
 139     { _M_ht.insert_unique(__f, __l); }
 140   template <class _InputIterator>
 141   hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
 142            const hasher& __hf)
 143     : _M_ht(__n, __hf, key_equal(), allocator_type())
 144     { _M_ht.insert_unique(__f, __l); }
 145   template <class _InputIterator>
 146   hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
 147            const hasher& __hf, const key_equal& __eql,
 148            const allocator_type& __a = allocator_type())
 149     : _M_ht(__n, __hf, __eql, __a)
 150     { _M_ht.insert_unique(__f, __l); }
 151
 152 public:
 153   size_type size() const { return _M_ht.size(); }
 154   size_type max_size() const { return _M_ht.max_size(); }
 155   bool empty() const { return _M_ht.empty(); }
 156   void swap(hash_map& __hs) { _M_ht.swap(__hs._M_ht); }
 157
 158   template <class _K1, class _T1, class _HF, class _EqK, class _Al>
 159   friend bool operator== (const hash_map<_K1, _T1, _HF, _EqK, _Al>&,
 160                           const hash_map<_K1, _T1, _HF, _EqK, _Al>&);
 161
 162   iterator begin() { return _M_ht.begin(); }
 163   iterator end() { return _M_ht.end(); }
 164   const_iterator begin() const { return _M_ht.begin(); }
 165   const_iterator end() const { return _M_ht.end(); }
 166
 167 public:
 168   pair<iterator,bool> insert(const value_type& __obj)
 169     { return _M_ht.insert_unique(__obj); }
 170   template <class _InputIterator>
 171   void insert(_InputIterator __f, _InputIterator __l)
 172     { _M_ht.insert_unique(__f,__l); }
 173   pair<iterator,bool> insert_noresize(const value_type& __obj)
 174     { return _M_ht.insert_unique_noresize(__obj); }
 175
 176   iterator find(const key_type& __key) { return _M_ht.find(__key); }
 177   const_iterator find(const key_type& __key) const
 178     { return _M_ht.find(__key); }
 179
 180   _Tp& operator[](const key_type& __key) {
 181     return _M_ht.find_or_insert(value_type(__key, _Tp())).second;
 182   }
 183
 184   size_type count(const key_type& __key) const { return _M_ht.count(__key); }
 185
 186   pair<iterator, iterator> equal_range(const key_type& __key)
 187     { return _M_ht.equal_range(__key); }
 188   pair<const_iterator, const_iterator>
 189   equal_range(const key_type& __key) const
 190     { return _M_ht.equal_range(__key); }
 191
 192   size_type erase(const key_type& __key) {return _M_ht.erase(__key); }
 193   void erase(iterator __it) { _M_ht.erase(__it); }
 194   void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
 195   void clear() { _M_ht.clear(); }
 196
 197   void resize(size_type __hint) { _M_ht.resize(__hint); }
 198   size_type bucket_count() const { return _M_ht.bucket_count(); }
 199   size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
 200   size_type elems_in_bucket(size_type __n) const
 201     { return _M_ht.elems_in_bucket(__n); }
 202 };
 203
 204 template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc>
 205 inline bool
 206 operator==(const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1,
 207            const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2)
 208 {
 209   return __hm1._M_ht == __hm2._M_ht;
 210 }
 211
 212 template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc>
 213 inline bool
 214 operator!=(const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1,
 215            const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2) {
 216   return !(__hm1 == __hm2);
 217 }
 218
 219 template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc>
 220 inline void
 221 swap(hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1,
 222      hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2)
 223 {
 224   __hm1.swap(__hm2);
 225 }
 226
 227 // Forward declaration of equality operator; needed for friend declaration.
 228
 229 template <class _Key, class _Tp,
 230           class _HashFcn  = hash<_Key>,
 231           class _EqualKey = equal_to<_Key>,
 232           class _Alloc =  allocator<_Tp> >
 233 class hash_multimap;
 234
 235 template <class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
 236 inline bool
 237 operator==(const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm1,
 238            const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm2);
 239
 240 /**
 241  *  This is an SGI extension.
 242  *  @ingroup SGIextensions
 243  *  @doctodo
 244 */
 245 template <class _Key, class _Tp, class _HashFcn, class _EqualKey, class _Alloc>
 246 class hash_multimap
 247 {
 248   // concept requirements
 249   __glibcxx_class_requires(_Key, _SGIAssignableConcept)
 250   __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
 251   __glibcxx_class_requires3(_HashFcn, size_t, _Key, _UnaryFunctionConcept)
 252   __glibcxx_class_requires3(_EqualKey, _Key, _Key, _BinaryPredicateConcept)
 253
 254 private:
 255   typedef hashtable<pair<const _Key, _Tp>, _Key, _HashFcn,
 256                     _Select1st<pair<const _Key, _Tp> >, _EqualKey, _Alloc>
 257           _Ht;
 258   _Ht _M_ht;
 259
 260 public:
 261   typedef typename _Ht::key_type key_type;
 262   typedef _Tp data_type;
 263   typedef _Tp mapped_type;
 264   typedef typename _Ht::value_type value_type;
 265   typedef typename _Ht::hasher hasher;
 266   typedef typename _Ht::key_equal key_equal;
 267
 268   typedef typename _Ht::size_type size_type;
 269   typedef typename _Ht::difference_type difference_type;
 270   typedef typename _Ht::pointer pointer;
 271   typedef typename _Ht::const_pointer const_pointer;
 272   typedef typename _Ht::reference reference;
 273   typedef typename _Ht::const_reference const_reference;
 274
 275   typedef typename _Ht::iterator iterator;
 276   typedef typename _Ht::const_iterator const_iterator;
 277
 278   typedef typename _Ht::allocator_type allocator_type;
 279
 280   hasher hash_funct() const { return _M_ht.hash_funct(); }
 281   key_equal key_eq() const { return _M_ht.key_eq(); }
 282   allocator_type get_allocator() const { return _M_ht.get_allocator(); }
 283
 284 public:
 285   hash_multimap() : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
 286   explicit hash_multimap(size_type __n)
 287     : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
 288   hash_multimap(size_type __n, const hasher& __hf)
 289     : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
 290   hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql,
 291                 const allocator_type& __a = allocator_type())
 292     : _M_ht(__n, __hf, __eql, __a) {}
 293
 294   template <class _InputIterator>
 295   hash_multimap(_InputIterator __f, _InputIterator __l)
 296     : _M_ht(100, hasher(), key_equal(), allocator_type())
 297     { _M_ht.insert_equal(__f, __l); }
 298   template <class _InputIterator>
 299   hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n)
 300     : _M_ht(__n, hasher(), key_equal(), allocator_type())
 301     { _M_ht.insert_equal(__f, __l); }
 302   template <class _InputIterator>
 303   hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
 304                 const hasher& __hf)
 305     : _M_ht(__n, __hf, key_equal(), allocator_type())
 306     { _M_ht.insert_equal(__f, __l); }
 307   template <class _InputIterator>
 308   hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
 309                 const hasher& __hf, const key_equal& __eql,
 310                 const allocator_type& __a = allocator_type())
 311     : _M_ht(__n, __hf, __eql, __a)
 312     { _M_ht.insert_equal(__f, __l); }
 313
 314 public:
 315   size_type size() const { return _M_ht.size(); }
 316   size_type max_size() const { return _M_ht.max_size(); }
 317   bool empty() const { return _M_ht.empty(); }
 318   void swap(hash_multimap& __hs) { _M_ht.swap(__hs._M_ht); }
 319
 320   template <class _K1, class _T1, class _HF, class _EqK, class _Al>
 321   friend bool operator== (const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&,
 322                           const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&);
 323
 324   iterator begin() { return _M_ht.begin(); }
 325   iterator end() { return _M_ht.end(); }
 326   const_iterator begin() const { return _M_ht.begin(); }
 327   const_iterator end() const { return _M_ht.end(); }
 328
 329 public:
 330   iterator insert(const value_type& __obj)
 331     { return _M_ht.insert_equal(__obj); }
 332   template <class _InputIterator>
 333   void insert(_InputIterator __f, _InputIterator __l)
 334     { _M_ht.insert_equal(__f,__l); }
 335   iterator insert_noresize(const value_type& __obj)
 336     { return _M_ht.insert_equal_noresize(__obj); }
 337
 338   iterator find(const key_type& __key) { return _M_ht.find(__key); }
 339   const_iterator find(const key_type& __key) const
 340     { return _M_ht.find(__key); }
 341
 342   size_type count(const key_type& __key) const { return _M_ht.count(__key); }
 343
 344   pair<iterator, iterator> equal_range(const key_type& __key)
 345     { return _M_ht.equal_range(__key); }
 346   pair<const_iterator, const_iterator>
 347   equal_range(const key_type& __key) const
 348     { return _M_ht.equal_range(__key); }
 349
 350   size_type erase(const key_type& __key) {return _M_ht.erase(__key); }
 351   void erase(iterator __it) { _M_ht.erase(__it); }
 352   void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
 353   void clear() { _M_ht.clear(); }
 354
 355 public:
 356   void resize(size_type __hint) { _M_ht.resize(__hint); }
 357   size_type bucket_count() const { return _M_ht.bucket_count(); }
 358   size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
 359   size_type elems_in_bucket(size_type __n) const
 360     { return _M_ht.elems_in_bucket(__n); }
 361 };
 362
 363 template <class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
 364 inline bool
 365 operator==(const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm1,
 366            const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm2)
 367 {
 368   return __hm1._M_ht == __hm2._M_ht;
 369 }
 370
 371 template <class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
 372 inline bool
 373 operator!=(const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm1,
 374            const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm2) {
 375   return !(__hm1 == __hm2);
 376 }
 377
 378 template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc>
 379 inline void
 380 swap(hash_multimap<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1,
 381      hash_multimap<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2)
 382 {
 383   __hm1.swap(__hm2);
 384 }
 385
 386 } // namespace __gnu_cxx
 387
 388 namespace std
 389 {
 390 // Specialization of insert_iterator so that it will work for hash_map
 391 // and hash_multimap.
 392
 393 template <class _Key, class _Tp, class _HashFn,  class _EqKey, class _Alloc>
 394 class insert_iterator<__gnu_cxx::hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc> > {
 395 protected:
 396   typedef __gnu_cxx::hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc> _Container;
 397   _Container* container;
 398 public:
 399   typedef _Container          container_type;
 400   typedef output_iterator_tag iterator_category;
 401   typedef void                value_type;
 402   typedef void                difference_type;
 403   typedef void                pointer;
 404   typedef void                reference;
 405
 406   insert_iterator(_Container& __x) : container(&__x) {}
 407   insert_iterator(_Container& __x, typename _Container::iterator)
 408     : container(&__x) {}
 409   insert_iterator<_Container>&
 410   operator=(const typename _Container::value_type& __value) {
 411     container->insert(__value);
 412     return *this;
 413   }
 414   insert_iterator<_Container>& operator*() { return *this; }
 415   insert_iterator<_Container>& operator++() { return *this; }
 416   insert_iterator<_Container>& operator++(int) { return *this; }
 417 };
 418
 419 template <class _Key, class _Tp, class _HashFn,  class _EqKey, class _Alloc>
 420 class insert_iterator<__gnu_cxx::hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc> > {
 421 protected:
 422   typedef __gnu_cxx::hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc> _Container;
 423   _Container* container;
 424   typename _Container::iterator iter;
 425 public:
 426   typedef _Container          container_type;
 427   typedef output_iterator_tag iterator_category;
 428   typedef void                value_type;
 429   typedef void                difference_type;
 430   typedef void                pointer;
 431   typedef void                reference;
 432
 433   insert_iterator(_Container& __x) : container(&__x) {}
 434   insert_iterator(_Container& __x, typename _Container::iterator)
 435     : container(&__x) {}
 436   insert_iterator<_Container>&
 437   operator=(const typename _Container::value_type& __value) {
 438     container->insert(__value);
 439     return *this;
 440   }
 441   insert_iterator<_Container>& operator*() { return *this; }
 442   insert_iterator<_Container>& operator++() { return *this; }
 443   insert_iterator<_Container>& operator++(int) { return *this; }
 444 };
 445 } // namespace std
 446
 447 #endif