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