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 606