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