contrib/libstdc++/include/ext/hash_map

   1 // Hashing map implementation -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002, 2004, 2005, 2006 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, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  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).
  59  */
  60
  61 #ifndef _HASH_MAP
  62 #define _HASH_MAP 1
  63
  64 #include <bits/c++config.h>
  65 #include <ext/hashtable.h>
  66 #include <bits/concept_check.h>
  67
  68 _GLIBCXX_BEGIN_NESTED_NAMESPACE(__gnu_cxx, _GLIBCXX_EXT)
  69
  70   using std::equal_to;
  71   using std::allocator;
  72   using std::pair;
  73   using std::_Select1st;
  74
  75   /**
  76    *  This is an SGI extension.
  77    *  @ingroup SGIextensions
  78    *  @doctodo
  79    */
  80   template<class _Key, class _Tp, class _HashFn = hash<_Key>,
  81            class _EqualKey = equal_to<_Key>, class _Alloc = allocator<_Tp> >
  82     class hash_map
  83     {
  84     private:
  85       typedef hashtable<pair<const _Key, _Tp>,_Key, _HashFn,
  86                         _Select1st<pair<const _Key, _Tp> >,
  87                         _EqualKey, _Alloc> _Ht;
  88
  89       _Ht _M_ht;
  90
  91     public:
  92       typedef typename _Ht::key_type key_type;
  93       typedef _Tp data_type;
  94       typedef _Tp mapped_type;
  95       typedef typename _Ht::value_type value_type;
  96       typedef typename _Ht::hasher hasher;
  97       typedef typename _Ht::key_equal key_equal;
  98
  99       typedef typename _Ht::size_type size_type;
 100       typedef typename _Ht::difference_type difference_type;
 101       typedef typename _Ht::pointer pointer;
 102       typedef typename _Ht::const_pointer const_pointer;
 103       typedef typename _Ht::reference reference;
 104       typedef typename _Ht::const_reference const_reference;
 105
 106       typedef typename _Ht::iterator iterator;
 107       typedef typename _Ht::const_iterator const_iterator;
 108
 109       typedef typename _Ht::allocator_type allocator_type;
 110
 111       hasher
 112       hash_funct() const
 113       { return _M_ht.hash_funct(); }
 114
 115       key_equal
 116       key_eq() const
 117       { return _M_ht.key_eq(); }
 118
 119       allocator_type
 120       get_allocator() const
 121       { return _M_ht.get_allocator(); }
 122
 123     public:
 124       hash_map()
 125       : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
 126
 127       explicit
 128       hash_map(size_type __n)
 129       : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
 130
 131       hash_map(size_type __n, const hasher& __hf)
 132       : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
 133
 134       hash_map(size_type __n, const hasher& __hf, const key_equal& __eql,
 135                const allocator_type& __a = allocator_type())
 136       : _M_ht(__n, __hf, __eql, __a) {}
 137
 138       template<class _InputIterator>
 139         hash_map(_InputIterator __f, _InputIterator __l)
 140         : _M_ht(100, hasher(), key_equal(), allocator_type())
 141         { _M_ht.insert_unique(__f, __l); }
 142
 143       template<class _InputIterator>
 144         hash_map(_InputIterator __f, _InputIterator __l, size_type __n)
 145         : _M_ht(__n, hasher(), key_equal(), allocator_type())
 146         { _M_ht.insert_unique(__f, __l); }
 147
 148       template<class _InputIterator>
 149         hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
 150                  const hasher& __hf)
 151         : _M_ht(__n, __hf, key_equal(), allocator_type())
 152         { _M_ht.insert_unique(__f, __l); }
 153
 154       template<class _InputIterator>
 155         hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
 156                  const hasher& __hf, const key_equal& __eql,
 157                  const allocator_type& __a = allocator_type())
 158         : _M_ht(__n, __hf, __eql, __a)
 159         { _M_ht.insert_unique(__f, __l); }
 160
 161     public:
 162       size_type
 163       size() const
 164       { return _M_ht.size(); }
 165
 166       size_type
 167       max_size() const
 168       { return _M_ht.max_size(); }
 169
 170       bool
 171       empty() const
 172       { return _M_ht.empty(); }
 173
 174       void
 175       swap(hash_map& __hs)
 176       { _M_ht.swap(__hs._M_ht); }
 177
 178       template<class _K1, class _T1, class _HF, class _EqK, class _Al>
 179         friend bool
 180         operator== (const hash_map<_K1, _T1, _HF, _EqK, _Al>&,
 181                     const hash_map<_K1, _T1, _HF, _EqK, _Al>&);
 182
 183       iterator
 184       begin()
 185       { return _M_ht.begin(); }
 186
 187       iterator
 188       end()
 189       { return _M_ht.end(); }
 190
 191       const_iterator
 192       begin() const
 193       { return _M_ht.begin(); }
 194
 195       const_iterator
 196       end() const
 197       { return _M_ht.end(); }
 198
 199     public:
 200       pair<iterator, bool>
 201       insert(const value_type& __obj)
 202       { return _M_ht.insert_unique(__obj); }
 203
 204       template<class _InputIterator>
 205         void
 206         insert(_InputIterator __f, _InputIterator __l)
 207         { _M_ht.insert_unique(__f, __l); }
 208
 209       pair<iterator, bool>
 210       insert_noresize(const value_type& __obj)
 211       { return _M_ht.insert_unique_noresize(__obj); }
 212
 213       iterator
 214       find(const key_type& __key)
 215       { return _M_ht.find(__key); }
 216
 217       const_iterator
 218       find(const key_type& __key) const
 219       { return _M_ht.find(__key); }
 220
 221       _Tp&
 222       operator[](const key_type& __key)
 223       { return _M_ht.find_or_insert(value_type(__key, _Tp())).second; }
 224
 225       size_type
 226       count(const key_type& __key) const
 227       { return _M_ht.count(__key); }
 228
 229       pair<iterator, iterator>
 230       equal_range(const key_type& __key)
 231       { return _M_ht.equal_range(__key); }
 232
 233       pair<const_iterator, const_iterator>
 234       equal_range(const key_type& __key) const
 235       { return _M_ht.equal_range(__key); }
 236
 237       size_type
 238       erase(const key_type& __key)
 239       {return _M_ht.erase(__key); }
 240
 241       void
 242       erase(iterator __it)
 243       { _M_ht.erase(__it); }
 244
 245       void
 246       erase(iterator __f, iterator __l)
 247       { _M_ht.erase(__f, __l); }
 248
 249       void
 250       clear()
 251       { _M_ht.clear(); }
 252
 253       void
 254       resize(size_type __hint)
 255       { _M_ht.resize(__hint); }
 256
 257       size_type
 258       bucket_count() const
 259       { return _M_ht.bucket_count(); }
 260
 261       size_type
 262       max_bucket_count() const
 263       { return _M_ht.max_bucket_count(); }
 264
 265       size_type
 266       elems_in_bucket(size_type __n) const
 267       { return _M_ht.elems_in_bucket(__n); }
 268     };
 269
 270   template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
 271     inline bool
 272     operator==(const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
 273                const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
 274     { return __hm1._M_ht == __hm2._M_ht; }
 275
 276   template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
 277     inline bool
 278     operator!=(const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
 279                const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
 280     { return !(__hm1 == __hm2); }
 281
 282   template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
 283     inline void
 284     swap(hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
 285          hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
 286     { __hm1.swap(__hm2); }
 287
 288
 289   /**
 290    *  This is an SGI extension.
 291    *  @ingroup SGIextensions
 292    *  @doctodo
 293    */
 294   template<class _Key, class _Tp,
 295            class _HashFn = hash<_Key>,
 296            class _EqualKey = equal_to<_Key>,
 297            class _Alloc = allocator<_Tp> >
 298     class hash_multimap
 299     {
 300       // concept requirements
 301       __glibcxx_class_requires(_Key, _SGIAssignableConcept)
 302       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
 303       __glibcxx_class_requires3(_HashFn, size_t, _Key, _UnaryFunctionConcept)
 304       __glibcxx_class_requires3(_EqualKey, _Key, _Key, _BinaryPredicateConcept)
 305
 306     private:
 307       typedef hashtable<pair<const _Key, _Tp>, _Key, _HashFn,
 308                         _Select1st<pair<const _Key, _Tp> >, _EqualKey, _Alloc>
 309           _Ht;
 310
 311       _Ht _M_ht;
 312
 313     public:
 314       typedef typename _Ht::key_type key_type;
 315       typedef _Tp data_type;
 316       typedef _Tp mapped_type;
 317       typedef typename _Ht::value_type value_type;
 318       typedef typename _Ht::hasher hasher;
 319       typedef typename _Ht::key_equal key_equal;
 320
 321       typedef typename _Ht::size_type size_type;
 322       typedef typename _Ht::difference_type difference_type;
 323       typedef typename _Ht::pointer pointer;
 324       typedef typename _Ht::const_pointer const_pointer;
 325       typedef typename _Ht::reference reference;
 326       typedef typename _Ht::const_reference const_reference;
 327
 328       typedef typename _Ht::iterator iterator;
 329       typedef typename _Ht::const_iterator const_iterator;
 330
 331       typedef typename _Ht::allocator_type allocator_type;
 332
 333       hasher
 334       hash_funct() const
 335       { return _M_ht.hash_funct(); }
 336
 337       key_equal
 338       key_eq() const
 339       { return _M_ht.key_eq(); }
 340
 341       allocator_type
 342       get_allocator() const
 343       { return _M_ht.get_allocator(); }
 344
 345     public:
 346       hash_multimap()
 347       : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
 348
 349       explicit
 350       hash_multimap(size_type __n)
 351       : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
 352
 353       hash_multimap(size_type __n, const hasher& __hf)
 354       : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
 355
 356       hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql,
 357                     const allocator_type& __a = allocator_type())
 358       : _M_ht(__n, __hf, __eql, __a) {}
 359
 360       template<class _InputIterator>
 361         hash_multimap(_InputIterator __f, _InputIterator __l)
 362         : _M_ht(100, hasher(), key_equal(), allocator_type())
 363         { _M_ht.insert_equal(__f, __l); }
 364
 365       template<class _InputIterator>
 366         hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n)
 367         : _M_ht(__n, hasher(), key_equal(), allocator_type())
 368         { _M_ht.insert_equal(__f, __l); }
 369
 370       template<class _InputIterator>
 371         hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
 372                       const hasher& __hf)
 373         : _M_ht(__n, __hf, key_equal(), allocator_type())
 374         { _M_ht.insert_equal(__f, __l); }
 375
 376       template<class _InputIterator>
 377         hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
 378                       const hasher& __hf, const key_equal& __eql,
 379                       const allocator_type& __a = allocator_type())
 380         : _M_ht(__n, __hf, __eql, __a)
 381         { _M_ht.insert_equal(__f, __l); }
 382
 383     public:
 384       size_type
 385       size() const
 386       { return _M_ht.size(); }
 387
 388       size_type
 389       max_size() const
 390       { return _M_ht.max_size(); }
 391
 392       bool
 393       empty() const
 394       { return _M_ht.empty(); }
 395
 396       void
 397       swap(hash_multimap& __hs)
 398       { _M_ht.swap(__hs._M_ht); }
 399
 400       template<class _K1, class _T1, class _HF, class _EqK, class _Al>
 401         friend bool
 402         operator==(const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&,
 403                    const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&);
 404
 405       iterator
 406       begin()
 407       { return _M_ht.begin(); }
 408
 409       iterator
 410       end()
 411       { return _M_ht.end(); }
 412
 413       const_iterator
 414       begin() const
 415       { return _M_ht.begin(); }
 416
 417       const_iterator
 418       end() const
 419       { return _M_ht.end(); }
 420
 421     public:
 422       iterator
 423       insert(const value_type& __obj)
 424       { return _M_ht.insert_equal(__obj); }
 425
 426       template<class _InputIterator>
 427         void
 428         insert(_InputIterator __f, _InputIterator __l)
 429         { _M_ht.insert_equal(__f,__l); }
 430
 431       iterator
 432       insert_noresize(const value_type& __obj)
 433       { return _M_ht.insert_equal_noresize(__obj); }
 434
 435       iterator
 436       find(const key_type& __key)
 437       { return _M_ht.find(__key); }
 438
 439       const_iterator
 440       find(const key_type& __key) const
 441       { return _M_ht.find(__key); }
 442
 443       size_type
 444       count(const key_type& __key) const
 445       { return _M_ht.count(__key); }
 446
 447       pair<iterator, iterator>
 448       equal_range(const key_type& __key)
 449       { return _M_ht.equal_range(__key); }
 450
 451       pair<const_iterator, const_iterator>
 452       equal_range(const key_type& __key) const
 453       { return _M_ht.equal_range(__key); }
 454
 455       size_type
 456       erase(const key_type& __key)
 457       { return _M_ht.erase(__key); }
 458
 459       void
 460       erase(iterator __it)
 461       { _M_ht.erase(__it); }
 462
 463       void
 464       erase(iterator __f, iterator __l)
 465       { _M_ht.erase(__f, __l); }
 466
 467       void
 468       clear()
 469       { _M_ht.clear(); }
 470
 471     public:
 472       void
 473       resize(size_type __hint)
 474       { _M_ht.resize(__hint); }
 475
 476       size_type
 477       bucket_count() const
 478       { return _M_ht.bucket_count(); }
 479
 480       size_type
 481       max_bucket_count() const
 482       { return _M_ht.max_bucket_count(); }
 483
 484       size_type
 485       elems_in_bucket(size_type __n) const
 486       { return _M_ht.elems_in_bucket(__n); }
 487     };
 488
 489   template<class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
 490     inline bool
 491     operator==(const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm1,
 492                const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm2)
 493     { return __hm1._M_ht == __hm2._M_ht; }
 494
 495   template<class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
 496     inline bool
 497     operator!=(const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm1,
 498                const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm2)
 499     { return !(__hm1 == __hm2); }
 500
 501   template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
 502     inline void
 503     swap(hash_multimap<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
 504          hash_multimap<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
 505     { __hm1.swap(__hm2); }
 506
 507 _GLIBCXX_END_NESTED_NAMESPACE
 508
 509 #ifdef _GLIBCXX_DEBUG
 510 # include <debug/hash_map>
 511 #endif
 512
 513 _GLIBCXX_BEGIN_NAMESPACE(std)
 514
 515   // Specialization of insert_iterator so that it will work for hash_map
 516   // and hash_multimap.
 517   template<class _Key, class _Tp, class _HashFn,  class _EqKey, class _Alloc>
 518     class insert_iterator<__gnu_cxx::hash_map<_Key, _Tp, _HashFn,
 519                                               _EqKey, _Alloc> >
 520     {
 521     protected:
 522       typedef __gnu_cxx::hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>
 523         _Container;
 524       _Container* container;
 525
 526     public:
 527       typedef _Container          container_type;
 528       typedef output_iterator_tag iterator_category;
 529       typedef void                value_type;
 530       typedef void                difference_type;
 531       typedef void                pointer;
 532       typedef void                reference;
 533
 534       insert_iterator(_Container& __x)
 535       : container(&__x) {}
 536
 537       insert_iterator(_Container& __x, typename _Container::iterator)
 538       : container(&__x) {}
 539
 540       insert_iterator<_Container>&
 541       operator=(const typename _Container::value_type& __value)
 542       {
 543         container->insert(__value);
 544         return *this;
 545       }
 546
 547       insert_iterator<_Container>&
 548       operator*()
 549       { return *this; }
 550
 551       insert_iterator<_Container>&
 552       operator++() { return *this; }
 553
 554       insert_iterator<_Container>&
 555       operator++(int)
 556       { return *this; }
 557     };
 558
 559   template<class _Key, class _Tp, class _HashFn,  class _EqKey, class _Alloc>
 560     class insert_iterator<__gnu_cxx::hash_multimap<_Key, _Tp, _HashFn,
 561                                                    _EqKey, _Alloc> >
 562     {
 563     protected:
 564       typedef __gnu_cxx::hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc>
 565         _Container;
 566       _Container* container;
 567       typename _Container::iterator iter;
 568
 569     public:
 570       typedef _Container          container_type;
 571       typedef output_iterator_tag iterator_category;
 572       typedef void                value_type;
 573       typedef void                difference_type;
 574       typedef void                pointer;
 575       typedef void                reference;
 576
 577       insert_iterator(_Container& __x)
 578       : container(&__x) {}
 579
 580       insert_iterator(_Container& __x, typename _Container::iterator)
 581       : container(&__x) {}
 582
 583       insert_iterator<_Container>&
 584       operator=(const typename _Container::value_type& __value)
 585       {
 586         container->insert(__value);
 587         return *this;
 588       }
 589
 590       insert_iterator<_Container>&
 591       operator*()
 592       { return *this; }
 593
 594       insert_iterator<_Container>&
 595       operator++()
 596       { return *this; }
 597
 598       insert_iterator<_Container>&
 599       operator++(int)
 600       { return *this; }
 601     };
 602
 603 _GLIBCXX_END_NAMESPACE
 604
 605 #endif