contrib/gcc-4.7/libstdc++-v3/include/backward/hash_map

   1 // Hashing map implementation -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002, 2004, 2005, 2006, 2009, 2010
   4 // Free Software Foundation, Inc.
   5 //
   6 // This file is part of the GNU ISO C++ Library.  This library is free
   7 // software; you can redistribute it and/or modify it under the
   8 // terms of the GNU General Public License as published by the
   9 // Free Software Foundation; either version 3, or (at your option)
  10 // any later version.
  11
  12 // This library is distributed in the hope that it will be useful,
  13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 // GNU General Public License for more details.
  16
  17 // Under Section 7 of GPL version 3, you are granted additional
  18 // permissions described in the GCC Runtime Library Exception, version
  19 // 3.1, as published by the Free Software Foundation.
  20
  21 // You should have received a copy of the GNU General Public License and
  22 // a copy of the GCC Runtime Library Exception along with this program;
  23 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  24 // <http://www.gnu.org/licenses/>.
  25
  26 /*
  27  * Copyright (c) 1996
  28  * Silicon Graphics Computer Systems, Inc.
  29  *
  30  * Permission to use, copy, modify, distribute and sell this software
  31  * and its documentation for any purpose is hereby granted without fee,
  32  * provided that the above copyright notice appear in all copies and
  33  * that both that copyright notice and this permission notice appear
  34  * in supporting documentation.  Silicon Graphics makes no
  35  * representations about the suitability of this software for any
  36  * purpose.  It is provided "as is" without express or implied warranty.
  37  *
  38  *
  39  * Copyright (c) 1994
  40  * Hewlett-Packard Company
  41  *
  42  * Permission to use, copy, modify, distribute and sell this software
  43  * and its documentation for any purpose is hereby granted without fee,
  44  * provided that the above copyright notice appear in all copies and
  45  * that both that copyright notice and this permission notice appear
  46  * in supporting documentation.  Hewlett-Packard Company makes no
  47  * representations about the suitability of this software for any
  48  * purpose.  It is provided "as is" without express or implied warranty.
  49  *
  50  */
  51
  52 /** @file backward/hash_map
  53  *  This file is a GNU extension to the Standard C++ Library (possibly
  54  *  containing extensions from the HP/SGI STL subset).
  55  */
  56
  57 #ifndef _BACKWARD_HASH_MAP
  58 #define _BACKWARD_HASH_MAP 1
  59
  60 #ifndef _GLIBCXX_PERMIT_BACKWARD_HASH
  61 #include "backward_warning.h"
  62 #endif
  63
  64 #include <bits/c++config.h>
  65 #include <backward/hashtable.h>
  66 #include <bits/concept_check.h>
  67
  68 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
  69 {
  70 _GLIBCXX_BEGIN_NAMESPACE_VERSION
  71
  72   using std::equal_to;
  73   using std::allocator;
  74   using std::pair;
  75   using std::_Select1st;
  76
  77   /**
  78    *  This is an SGI extension.
  79    *  @ingroup SGIextensions
  80    *  @doctodo
  81    */
  82   template<class _Key, class _Tp, class _HashFn = hash<_Key>,
  83            class _EqualKey = equal_to<_Key>, class _Alloc = allocator<_Tp> >
  84     class hash_map
  85     {
  86     private:
  87       typedef hashtable<pair<const _Key, _Tp>,_Key, _HashFn,
  88                         _Select1st<pair<const _Key, _Tp> >,
  89                         _EqualKey, _Alloc> _Ht;
  90
  91       _Ht _M_ht;
  92
  93     public:
  94       typedef typename _Ht::key_type key_type;
  95       typedef _Tp data_type;
  96       typedef _Tp mapped_type;
  97       typedef typename _Ht::value_type value_type;
  98       typedef typename _Ht::hasher hasher;
  99       typedef typename _Ht::key_equal key_equal;
 100
 101       typedef typename _Ht::size_type size_type;
 102       typedef typename _Ht::difference_type difference_type;
 103       typedef typename _Ht::pointer pointer;
 104       typedef typename _Ht::const_pointer const_pointer;
 105       typedef typename _Ht::reference reference;
 106       typedef typename _Ht::const_reference const_reference;
 107
 108       typedef typename _Ht::iterator iterator;
 109       typedef typename _Ht::const_iterator const_iterator;
 110
 111       typedef typename _Ht::allocator_type allocator_type;
 112
 113       hasher
 114       hash_funct() const
 115       { return _M_ht.hash_funct(); }
 116
 117       key_equal
 118       key_eq() const
 119       { return _M_ht.key_eq(); }
 120
 121       allocator_type
 122       get_allocator() const
 123       { return _M_ht.get_allocator(); }
 124
 125       hash_map()
 126       : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
 127
 128       explicit
 129       hash_map(size_type __n)
 130       : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
 131
 132       hash_map(size_type __n, const hasher& __hf)
 133       : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
 134
 135       hash_map(size_type __n, const hasher& __hf, const key_equal& __eql,
 136                const allocator_type& __a = allocator_type())
 137       : _M_ht(__n, __hf, __eql, __a) {}
 138
 139       template<class _InputIterator>
 140         hash_map(_InputIterator __f, _InputIterator __l)
 141         : _M_ht(100, hasher(), key_equal(), allocator_type())
 142         { _M_ht.insert_unique(__f, __l); }
 143
 144       template<class _InputIterator>
 145         hash_map(_InputIterator __f, _InputIterator __l, size_type __n)
 146         : _M_ht(__n, hasher(), key_equal(), allocator_type())
 147         { _M_ht.insert_unique(__f, __l); }
 148
 149       template<class _InputIterator>
 150         hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
 151                  const hasher& __hf)
 152         : _M_ht(__n, __hf, key_equal(), allocator_type())
 153         { _M_ht.insert_unique(__f, __l); }
 154
 155       template<class _InputIterator>
 156         hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
 157                  const hasher& __hf, const key_equal& __eql,
 158                  const allocator_type& __a = allocator_type())
 159         : _M_ht(__n, __hf, __eql, __a)
 160         { _M_ht.insert_unique(__f, __l); }
 161
 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       pair<iterator, bool>
 200       insert(const value_type& __obj)
 201       { return _M_ht.insert_unique(__obj); }
 202
 203       template<class _InputIterator>
 204         void
 205         insert(_InputIterator __f, _InputIterator __l)
 206         { _M_ht.insert_unique(__f, __l); }
 207
 208       pair<iterator, bool>
 209       insert_noresize(const value_type& __obj)
 210       { return _M_ht.insert_unique_noresize(__obj); }
 211
 212       iterator
 213       find(const key_type& __key)
 214       { return _M_ht.find(__key); }
 215
 216       const_iterator
 217       find(const key_type& __key) const
 218       { return _M_ht.find(__key); }
 219
 220       _Tp&
 221       operator[](const key_type& __key)
 222       { return _M_ht.find_or_insert(value_type(__key, _Tp())).second; }
 223
 224       size_type
 225       count(const key_type& __key) const
 226       { return _M_ht.count(__key); }
 227
 228       pair<iterator, iterator>
 229       equal_range(const key_type& __key)
 230       { return _M_ht.equal_range(__key); }
 231
 232       pair<const_iterator, const_iterator>
 233       equal_range(const key_type& __key) const
 234       { return _M_ht.equal_range(__key); }
 235
 236       size_type
 237       erase(const key_type& __key)
 238       {return _M_ht.erase(__key); }
 239
 240       void
 241       erase(iterator __it)
 242       { _M_ht.erase(__it); }
 243
 244       void
 245       erase(iterator __f, iterator __l)
 246       { _M_ht.erase(__f, __l); }
 247
 248       void
 249       clear()
 250       { _M_ht.clear(); }
 251
 252       void
 253       resize(size_type __hint)
 254       { _M_ht.resize(__hint); }
 255
 256       size_type
 257       bucket_count() const
 258       { return _M_ht.bucket_count(); }
 259
 260       size_type
 261       max_bucket_count() const
 262       { return _M_ht.max_bucket_count(); }
 263
 264       size_type
 265       elems_in_bucket(size_type __n) const
 266       { return _M_ht.elems_in_bucket(__n); }
 267     };
 268
 269   template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
 270     inline bool
 271     operator==(const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
 272                const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
 273     { return __hm1._M_ht == __hm2._M_ht; }
 274
 275   template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
 276     inline bool
 277     operator!=(const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
 278                const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
 279     { return !(__hm1 == __hm2); }
 280
 281   template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
 282     inline void
 283     swap(hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
 284          hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
 285     { __hm1.swap(__hm2); }
 286
 287
 288   /**
 289    *  This is an SGI extension.
 290    *  @ingroup SGIextensions
 291    *  @doctodo
 292    */
 293   template<class _Key, class _Tp,
 294            class _HashFn = hash<_Key>,
 295            class _EqualKey = equal_to<_Key>,
 296            class _Alloc = allocator<_Tp> >
 297     class hash_multimap
 298     {
 299       // concept requirements
 300       __glibcxx_class_requires(_Key, _SGIAssignableConcept)
 301       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
 302       __glibcxx_class_requires3(_HashFn, size_t, _Key, _UnaryFunctionConcept)
 303       __glibcxx_class_requires3(_EqualKey, _Key, _Key, _BinaryPredicateConcept)
 304
 305     private:
 306       typedef hashtable<pair<const _Key, _Tp>, _Key, _HashFn,
 307                         _Select1st<pair<const _Key, _Tp> >, _EqualKey, _Alloc>
 308           _Ht;
 309
 310       _Ht _M_ht;
 311
 312     public:
 313       typedef typename _Ht::key_type key_type;
 314       typedef _Tp data_type;
 315       typedef _Tp mapped_type;
 316       typedef typename _Ht::value_type value_type;
 317       typedef typename _Ht::hasher hasher;
 318       typedef typename _Ht::key_equal key_equal;
 319
 320       typedef typename _Ht::size_type size_type;
 321       typedef typename _Ht::difference_type difference_type;
 322       typedef typename _Ht::pointer pointer;
 323       typedef typename _Ht::const_pointer const_pointer;
 324       typedef typename _Ht::reference reference;
 325       typedef typename _Ht::const_reference const_reference;
 326
 327       typedef typename _Ht::iterator iterator;
 328       typedef typename _Ht::const_iterator const_iterator;
 329
 330       typedef typename _Ht::allocator_type allocator_type;
 331
 332       hasher
 333       hash_funct() const
 334       { return _M_ht.hash_funct(); }
 335
 336       key_equal
 337       key_eq() const
 338       { return _M_ht.key_eq(); }
 339
 340       allocator_type
 341       get_allocator() const
 342       { return _M_ht.get_allocator(); }
 343
 344       hash_multimap()
 345       : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
 346
 347       explicit
 348       hash_multimap(size_type __n)
 349       : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
 350
 351       hash_multimap(size_type __n, const hasher& __hf)
 352       : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
 353
 354       hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql,
 355                     const allocator_type& __a = allocator_type())
 356       : _M_ht(__n, __hf, __eql, __a) {}
 357
 358       template<class _InputIterator>
 359         hash_multimap(_InputIterator __f, _InputIterator __l)
 360         : _M_ht(100, hasher(), key_equal(), allocator_type())
 361         { _M_ht.insert_equal(__f, __l); }
 362
 363       template<class _InputIterator>
 364         hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n)
 365         : _M_ht(__n, hasher(), key_equal(), allocator_type())
 366         { _M_ht.insert_equal(__f, __l); }
 367
 368       template<class _InputIterator>
 369         hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
 370                       const hasher& __hf)
 371         : _M_ht(__n, __hf, key_equal(), allocator_type())
 372         { _M_ht.insert_equal(__f, __l); }
 373
 374       template<class _InputIterator>
 375         hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
 376                       const hasher& __hf, const key_equal& __eql,
 377                       const allocator_type& __a = allocator_type())
 378         : _M_ht(__n, __hf, __eql, __a)
 379         { _M_ht.insert_equal(__f, __l); }
 380
 381       size_type
 382       size() const
 383       { return _M_ht.size(); }
 384
 385       size_type
 386       max_size() const
 387       { return _M_ht.max_size(); }
 388
 389       bool
 390       empty() const
 391       { return _M_ht.empty(); }
 392
 393       void
 394       swap(hash_multimap& __hs)
 395       { _M_ht.swap(__hs._M_ht); }
 396
 397       template<class _K1, class _T1, class _HF, class _EqK, class _Al>
 398         friend bool
 399         operator==(const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&,
 400                    const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&);
 401
 402       iterator
 403       begin()
 404       { return _M_ht.begin(); }
 405
 406       iterator
 407       end()
 408       { return _M_ht.end(); }
 409
 410       const_iterator
 411       begin() const
 412       { return _M_ht.begin(); }
 413
 414       const_iterator
 415       end() const
 416       { return _M_ht.end(); }
 417
 418       iterator
 419       insert(const value_type& __obj)
 420       { return _M_ht.insert_equal(__obj); }
 421
 422       template<class _InputIterator>
 423         void
 424         insert(_InputIterator __f, _InputIterator __l)
 425         { _M_ht.insert_equal(__f,__l); }
 426
 427       iterator
 428       insert_noresize(const value_type& __obj)
 429       { return _M_ht.insert_equal_noresize(__obj); }
 430
 431       iterator
 432       find(const key_type& __key)
 433       { return _M_ht.find(__key); }
 434
 435       const_iterator
 436       find(const key_type& __key) const
 437       { return _M_ht.find(__key); }
 438
 439       size_type
 440       count(const key_type& __key) const
 441       { return _M_ht.count(__key); }
 442
 443       pair<iterator, iterator>
 444       equal_range(const key_type& __key)
 445       { return _M_ht.equal_range(__key); }
 446
 447       pair<const_iterator, const_iterator>
 448       equal_range(const key_type& __key) const
 449       { return _M_ht.equal_range(__key); }
 450
 451       size_type
 452       erase(const key_type& __key)
 453       { return _M_ht.erase(__key); }
 454
 455       void
 456       erase(iterator __it)
 457       { _M_ht.erase(__it); }
 458
 459       void
 460       erase(iterator __f, iterator __l)
 461       { _M_ht.erase(__f, __l); }
 462
 463       void
 464       clear()
 465       { _M_ht.clear(); }
 466
 467       void
 468       resize(size_type __hint)
 469       { _M_ht.resize(__hint); }
 470
 471       size_type
 472       bucket_count() const
 473       { return _M_ht.bucket_count(); }
 474
 475       size_type
 476       max_bucket_count() const
 477       { return _M_ht.max_bucket_count(); }
 478
 479       size_type
 480       elems_in_bucket(size_type __n) const
 481       { return _M_ht.elems_in_bucket(__n); }
 482     };
 483
 484   template<class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
 485     inline bool
 486     operator==(const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm1,
 487                const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm2)
 488     { return __hm1._M_ht == __hm2._M_ht; }
 489
 490   template<class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
 491     inline bool
 492     operator!=(const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm1,
 493                const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm2)
 494     { return !(__hm1 == __hm2); }
 495
 496   template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
 497     inline void
 498     swap(hash_multimap<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
 499          hash_multimap<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
 500     { __hm1.swap(__hm2); }
 501
 502 _GLIBCXX_END_NAMESPACE_VERSION
 503 } // namespace
 504
 505 namespace std _GLIBCXX_VISIBILITY(default)
 506 {
 507 _GLIBCXX_BEGIN_NAMESPACE_VERSION
 508
 509   // Specialization of insert_iterator so that it will work for hash_map
 510   // and hash_multimap.
 511   template<class _Key, class _Tp, class _HashFn,  class _EqKey, class _Alloc>
 512     class insert_iterator<__gnu_cxx::hash_map<_Key, _Tp, _HashFn,
 513                                               _EqKey, _Alloc> >
 514     {
 515     protected:
 516       typedef __gnu_cxx::hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>
 517         _Container;
 518       _Container* container;
 519
 520     public:
 521       typedef _Container          container_type;
 522       typedef output_iterator_tag iterator_category;
 523       typedef void                value_type;
 524       typedef void                difference_type;
 525       typedef void                pointer;
 526       typedef void                reference;
 527
 528       insert_iterator(_Container& __x)
 529       : container(&__x) {}
 530
 531       insert_iterator(_Container& __x, typename _Container::iterator)
 532       : container(&__x) {}
 533
 534       insert_iterator<_Container>&
 535       operator=(const typename _Container::value_type& __value)
 536       {
 537         container->insert(__value);
 538         return *this;
 539       }
 540
 541       insert_iterator<_Container>&
 542       operator*()
 543       { return *this; }
 544
 545       insert_iterator<_Container>&
 546       operator++() { return *this; }
 547
 548       insert_iterator<_Container>&
 549       operator++(int)
 550       { return *this; }
 551     };
 552
 553   template<class _Key, class _Tp, class _HashFn,  class _EqKey, class _Alloc>
 554     class insert_iterator<__gnu_cxx::hash_multimap<_Key, _Tp, _HashFn,
 555                                                    _EqKey, _Alloc> >
 556     {
 557     protected:
 558       typedef __gnu_cxx::hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc>
 559         _Container;
 560       _Container* container;
 561       typename _Container::iterator iter;
 562
 563     public:
 564       typedef _Container          container_type;
 565       typedef output_iterator_tag iterator_category;
 566       typedef void                value_type;
 567       typedef void                difference_type;
 568       typedef void                pointer;
 569       typedef void                reference;
 570
 571       insert_iterator(_Container& __x)
 572       : container(&__x) {}
 573
 574       insert_iterator(_Container& __x, typename _Container::iterator)
 575       : container(&__x) {}
 576
 577       insert_iterator<_Container>&
 578       operator=(const typename _Container::value_type& __value)
 579       {
 580         container->insert(__value);
 581         return *this;
 582       }
 583
 584       insert_iterator<_Container>&
 585       operator*()
 586       { return *this; }
 587
 588       insert_iterator<_Container>&
 589       operator++()
 590       { return *this; }
 591
 592       insert_iterator<_Container>&
 593       operator++(int)
 594       { return *this; }
 595     };
 596
 597 _GLIBCXX_END_NAMESPACE_VERSION
 598 } // namespace
 599
 600 #endif