1// Hashing map implementation -*- C++ -*- 2 3// Copyright (C) 2001, 2002 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 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). You should only 59 * include this header if you are using GCC 3 or later. 60 */ 61 62#ifndef __SGI_STL_INTERNAL_HASH_MAP_H 63#define __SGI_STL_INTERNAL_HASH_MAP_H 64 65#include <ext/stl_hashtable.h> 66#include <bits/concept_check.h> 67 68namespace __gnu_cxx 69{ 70using std::equal_to; 71using std::allocator; 72using std::pair; 73using std::_Select1st; 74 75// Forward declaration of equality operator; needed for friend declaration. 76 77template <class _Key, class _Tp, 78 class _HashFcn = hash<_Key>, 79 class _EqualKey = equal_to<_Key>, 80 class _Alloc = allocator<_Tp> > 81class hash_map; 82 83template <class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc> 84inline bool operator==(const hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>&, 85 const hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>&); 86/** 87 * This is an SGI extension. 88 * @ingroup SGIextensions 89 * @doctodo 90*/ 91template <class _Key, class _Tp, class _HashFcn, class _EqualKey, 92 class _Alloc> 93class hash_map 94{ 95private: 96 typedef hashtable<pair<const _Key,_Tp>,_Key,_HashFcn, 97 _Select1st<pair<const _Key,_Tp> >,_EqualKey,_Alloc> _Ht; 98 _Ht _M_ht; 99 100public: 101 typedef typename _Ht::key_type key_type; 102 typedef _Tp data_type; 103 typedef _Tp mapped_type; 104 typedef typename _Ht::value_type value_type; 105 typedef typename _Ht::hasher hasher; 106 typedef typename _Ht::key_equal key_equal; 107 108 typedef typename _Ht::size_type size_type; 109 typedef typename _Ht::difference_type difference_type; 110 typedef typename _Ht::pointer pointer; 111 typedef typename _Ht::const_pointer const_pointer; 112 typedef typename _Ht::reference reference; 113 typedef typename _Ht::const_reference const_reference; 114 115 typedef typename _Ht::iterator iterator; 116 typedef typename _Ht::const_iterator const_iterator; 117 118 typedef typename _Ht::allocator_type allocator_type; 119 120 hasher hash_funct() const { return _M_ht.hash_funct(); } 121 key_equal key_eq() const { return _M_ht.key_eq(); } 122 allocator_type get_allocator() const { return _M_ht.get_allocator(); } 123 124public: 125 hash_map() : _M_ht(100, hasher(), key_equal(), allocator_type()) {} 126 explicit hash_map(size_type __n) 127 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {} 128 hash_map(size_type __n, const hasher& __hf) 129 : _M_ht(__n, __hf, key_equal(), allocator_type()) {} 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 template <class _InputIterator> 139 hash_map(_InputIterator __f, _InputIterator __l, size_type __n) 140 : _M_ht(__n, hasher(), key_equal(), allocator_type()) 141 { _M_ht.insert_unique(__f, __l); } 142 template <class _InputIterator> 143 hash_map(_InputIterator __f, _InputIterator __l, size_type __n, 144 const hasher& __hf) 145 : _M_ht(__n, __hf, key_equal(), allocator_type()) 146 { _M_ht.insert_unique(__f, __l); } 147 template <class _InputIterator> 148 hash_map(_InputIterator __f, _InputIterator __l, size_type __n, 149 const hasher& __hf, const key_equal& __eql, 150 const allocator_type& __a = allocator_type()) 151 : _M_ht(__n, __hf, __eql, __a) 152 { _M_ht.insert_unique(__f, __l); } 153 154public: 155 size_type size() const { return _M_ht.size(); } 156 size_type max_size() const { return _M_ht.max_size(); } 157 bool empty() const { return _M_ht.empty(); } 158 void swap(hash_map& __hs) { _M_ht.swap(__hs._M_ht); } 159 160 template <class _K1, class _T1, class _HF, class _EqK, class _Al> 161 friend bool operator== (const hash_map<_K1, _T1, _HF, _EqK, _Al>&, 162 const hash_map<_K1, _T1, _HF, _EqK, _Al>&); 163 164 iterator begin() { return _M_ht.begin(); } 165 iterator end() { return _M_ht.end(); } 166 const_iterator begin() const { return _M_ht.begin(); } 167 const_iterator end() const { return _M_ht.end(); } 168 169public: 170 pair<iterator,bool> insert(const value_type& __obj) 171 { return _M_ht.insert_unique(__obj); } 172 template <class _InputIterator> 173 void insert(_InputIterator __f, _InputIterator __l) 174 { _M_ht.insert_unique(__f,__l); } 175 pair<iterator,bool> insert_noresize(const value_type& __obj) 176 { return _M_ht.insert_unique_noresize(__obj); } 177 178 iterator find(const key_type& __key) { return _M_ht.find(__key); } 179 const_iterator find(const key_type& __key) const 180 { return _M_ht.find(__key); } 181 182 _Tp& operator[](const key_type& __key) { 183 return _M_ht.find_or_insert(value_type(__key, _Tp())).second; 184 } 185 186 size_type count(const key_type& __key) const { return _M_ht.count(__key); } 187 188 pair<iterator, iterator> equal_range(const key_type& __key) 189 { return _M_ht.equal_range(__key); } 190 pair<const_iterator, const_iterator> 191 equal_range(const key_type& __key) const 192 { return _M_ht.equal_range(__key); } 193 194 size_type erase(const key_type& __key) {return _M_ht.erase(__key); } 195 void erase(iterator __it) { _M_ht.erase(__it); } 196 void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); } 197 void clear() { _M_ht.clear(); } 198 199 void resize(size_type __hint) { _M_ht.resize(__hint); } 200 size_type bucket_count() const { return _M_ht.bucket_count(); } 201 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); } 202 size_type elems_in_bucket(size_type __n) const 203 { return _M_ht.elems_in_bucket(__n); } 204}; 205 206template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc> 207inline bool 208operator==(const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1, 209 const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2) 210{ 211 return __hm1._M_ht == __hm2._M_ht; 212} 213 214template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc> 215inline bool 216operator!=(const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1, 217 const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2) { 218 return !(__hm1 == __hm2); 219} 220 221template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc> 222inline void 223swap(hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1, 224 hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2) 225{ 226 __hm1.swap(__hm2); 227} 228 229// Forward declaration of equality operator; needed for friend declaration. 230 231template <class _Key, class _Tp, 232 class _HashFcn = hash<_Key>, 233 class _EqualKey = equal_to<_Key>, 234 class _Alloc = allocator<_Tp> > 235class hash_multimap; 236 237template <class _Key, class _Tp, class _HF, class _EqKey, class _Alloc> 238inline bool 239operator==(const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm1, 240 const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm2); 241 242/** 243 * This is an SGI extension. 244 * @ingroup SGIextensions 245 * @doctodo 246*/ 247template <class _Key, class _Tp, class _HashFcn, class _EqualKey, class _Alloc> 248class hash_multimap 249{ 250 // concept requirements 251 __glibcpp_class_requires(_Key, _SGIAssignableConcept) 252 __glibcpp_class_requires(_Tp, _SGIAssignableConcept) 253 __glibcpp_class_requires3(_HashFcn, size_t, _Key, _UnaryFunctionConcept); 254 __glibcpp_class_requires3(_EqualKey, _Key, _Key, _BinaryPredicateConcept); 255 256private: 257 typedef hashtable<pair<const _Key, _Tp>, _Key, _HashFcn, 258 _Select1st<pair<const _Key, _Tp> >, _EqualKey, _Alloc> 259 _Ht; 260 _Ht _M_ht; 261 262public: 263 typedef typename _Ht::key_type key_type; 264 typedef _Tp data_type; 265 typedef _Tp mapped_type; 266 typedef typename _Ht::value_type value_type; 267 typedef typename _Ht::hasher hasher; 268 typedef typename _Ht::key_equal key_equal; 269 270 typedef typename _Ht::size_type size_type; 271 typedef typename _Ht::difference_type difference_type; 272 typedef typename _Ht::pointer pointer; 273 typedef typename _Ht::const_pointer const_pointer; 274 typedef typename _Ht::reference reference; 275 typedef typename _Ht::const_reference const_reference; 276 277 typedef typename _Ht::iterator iterator; 278 typedef typename _Ht::const_iterator const_iterator; 279 280 typedef typename _Ht::allocator_type allocator_type; 281 282 hasher hash_funct() const { return _M_ht.hash_funct(); } 283 key_equal key_eq() const { return _M_ht.key_eq(); } 284 allocator_type get_allocator() const { return _M_ht.get_allocator(); } 285 286public: 287 hash_multimap() : _M_ht(100, hasher(), key_equal(), allocator_type()) {} 288 explicit hash_multimap(size_type __n) 289 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {} 290 hash_multimap(size_type __n, const hasher& __hf) 291 : _M_ht(__n, __hf, key_equal(), allocator_type()) {} 292 hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql, 293 const allocator_type& __a = allocator_type()) 294 : _M_ht(__n, __hf, __eql, __a) {} 295 296 template <class _InputIterator> 297 hash_multimap(_InputIterator __f, _InputIterator __l) 298 : _M_ht(100, hasher(), key_equal(), allocator_type()) 299 { _M_ht.insert_equal(__f, __l); } 300 template <class _InputIterator> 301 hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n) 302 : _M_ht(__n, hasher(), key_equal(), allocator_type()) 303 { _M_ht.insert_equal(__f, __l); } 304 template <class _InputIterator> 305 hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n, 306 const hasher& __hf) 307 : _M_ht(__n, __hf, key_equal(), allocator_type()) 308 { _M_ht.insert_equal(__f, __l); } 309 template <class _InputIterator> 310 hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n, 311 const hasher& __hf, const key_equal& __eql, 312 const allocator_type& __a = allocator_type()) 313 : _M_ht(__n, __hf, __eql, __a) 314 { _M_ht.insert_equal(__f, __l); } 315 316public: 317 size_type size() const { return _M_ht.size(); } 318 size_type max_size() const { return _M_ht.max_size(); } 319 bool empty() const { return _M_ht.empty(); } 320 void swap(hash_multimap& __hs) { _M_ht.swap(__hs._M_ht); } 321 322 template <class _K1, class _T1, class _HF, class _EqK, class _Al> 323 friend bool operator== (const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&, 324 const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&); 325 326 iterator begin() { return _M_ht.begin(); } 327 iterator end() { return _M_ht.end(); } 328 const_iterator begin() const { return _M_ht.begin(); } 329 const_iterator end() const { return _M_ht.end(); } 330 331public: 332 iterator insert(const value_type& __obj) 333 { return _M_ht.insert_equal(__obj); } 334 template <class _InputIterator> 335 void insert(_InputIterator __f, _InputIterator __l) 336 { _M_ht.insert_equal(__f,__l); } 337 iterator insert_noresize(const value_type& __obj) 338 { return _M_ht.insert_equal_noresize(__obj); } 339 340 iterator find(const key_type& __key) { return _M_ht.find(__key); } 341 const_iterator find(const key_type& __key) const 342 { return _M_ht.find(__key); } 343 344 size_type count(const key_type& __key) const { return _M_ht.count(__key); } 345 346 pair<iterator, iterator> equal_range(const key_type& __key) 347 { return _M_ht.equal_range(__key); } 348 pair<const_iterator, const_iterator> 349 equal_range(const key_type& __key) const 350 { return _M_ht.equal_range(__key); } 351 352 size_type erase(const key_type& __key) {return _M_ht.erase(__key); } 353 void erase(iterator __it) { _M_ht.erase(__it); } 354 void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); } 355 void clear() { _M_ht.clear(); } 356 357public: 358 void resize(size_type __hint) { _M_ht.resize(__hint); } 359 size_type bucket_count() const { return _M_ht.bucket_count(); } 360 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); } 361 size_type elems_in_bucket(size_type __n) const 362 { return _M_ht.elems_in_bucket(__n); } 363}; 364 365template <class _Key, class _Tp, class _HF, class _EqKey, class _Alloc> 366inline bool 367operator==(const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm1, 368 const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm2) 369{ 370 return __hm1._M_ht == __hm2._M_ht; 371} 372 373template <class _Key, class _Tp, class _HF, class _EqKey, class _Alloc> 374inline bool 375operator!=(const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm1, 376 const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm2) { 377 return !(__hm1 == __hm2); 378} 379 380template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc> 381inline void 382swap(hash_multimap<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1, 383 hash_multimap<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2) 384{ 385 __hm1.swap(__hm2); 386} 387 388} // namespace __gnu_cxx 389 390namespace std 391{ 392// Specialization of insert_iterator so that it will work for hash_map 393// and hash_multimap. 394 395template <class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc> 396class insert_iterator<__gnu_cxx::hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc> > { 397protected: 398 typedef __gnu_cxx::hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc> _Container; 399 _Container* container; 400public: 401 typedef _Container container_type; 402 typedef output_iterator_tag iterator_category; 403 typedef void value_type; 404 typedef void difference_type; 405 typedef void pointer; 406 typedef void reference; 407 408 insert_iterator(_Container& __x) : container(&__x) {} 409 insert_iterator(_Container& __x, typename _Container::iterator) 410 : container(&__x) {} 411 insert_iterator<_Container>& 412 operator=(const typename _Container::value_type& __value) { 413 container->insert(__value); 414 return *this; 415 } 416 insert_iterator<_Container>& operator*() { return *this; } 417 insert_iterator<_Container>& operator++() { return *this; } 418 insert_iterator<_Container>& operator++(int) { return *this; } 419}; 420 421template <class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc> 422class insert_iterator<__gnu_cxx::hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc> > { 423protected: 424 typedef __gnu_cxx::hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc> _Container; 425 _Container* container; 426 typename _Container::iterator iter; 427public: 428 typedef _Container container_type; 429 typedef output_iterator_tag iterator_category; 430 typedef void value_type; 431 typedef void difference_type; 432 typedef void pointer; 433 typedef void reference; 434 435 insert_iterator(_Container& __x) : container(&__x) {} 436 insert_iterator(_Container& __x, typename _Container::iterator) 437 : container(&__x) {} 438 insert_iterator<_Container>& 439 operator=(const typename _Container::value_type& __value) { 440 container->insert(__value); 441 return *this; 442 } 443 insert_iterator<_Container>& operator*() { return *this; } 444 insert_iterator<_Container>& operator++() { return *this; } 445 insert_iterator<_Container>& operator++(int) { return *this; } 446}; 447 448} // namespace std 449 450#endif /* __SGI_STL_INTERNAL_HASH_MAP_H */ 451 452// Local Variables: 453// mode:C++ 454// End: 455