src/INTERP_KERNEL/Bases/InterpKernelHashMap.hxx

   1 // Copyright (C) 2001, 2002, 2004, 2005, 2006, 2009 Free Software Foundation, Inc.
   2 //
   3 // This file is part of the GNU ISO C++ Library.  This library is free
   4 // software; you can redistribute it and/or modify it under the
   5 // terms of the GNU General Public License as published by the
   6 // Free Software Foundation; either version 3, or (at your option)
   7 // any later version.
   8
   9 // This library is distributed in the hope that it will be useful,
  10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 // GNU General Public License for more details.
  13
  14 // Under Section 7 of GPL version 3, you are granted additional
  15 // permissions described in the GCC Runtime Library Exception, version
  16 // 3.1, as published by the Free Software Foundation.
  17
  18 // You should have received a copy of the GNU General Public License and
  19 // a copy of the GCC Runtime Library Exception along with this program;
  20 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  21 // <http://www.gnu.org/licenses/>.
  22
  23 /*
  24  * Copyright (c) 1996
  25  * Silicon Graphics Computer Systems, Inc.
  26  *
  27  * Permission to use, copy, modify, distribute and sell this software
  28  * and its documentation for any purpose is hereby granted without fee,
  29  * provided that the above copyright notice appear in all copies and
  30  * that both that copyright notice and this permission notice appear
  31  * in supporting documentation.  Silicon Graphics makes no
  32  * representations about the suitability of this software for any
  33  * purpose.  It is provided "as is" without express or implied warranty.
  34  *
  35  *
  36  * Copyright (c) 1994
  37  * Hewlett-Packard Company
  38  *
  39  * Permission to use, copy, modify, distribute and sell this software
  40  * and its documentation for any purpose is hereby granted without fee,
  41  * provided that the above copyright notice appear in all copies and
  42  * that both that copyright notice and this permission notice appear
  43  * in supporting documentation.  Hewlett-Packard Company makes no
  44  * representations about the suitability of this software for any
  45  * purpose.  It is provided "as is" without express or implied warranty.
  46  *
  47  */
  48 #ifndef __INTERPKERNELHASHMAP__
  49 #define __INTERPKERNELHASHMAP__
  50
  51 #include "InterpKernelStlExt.hxx"
  52 #include "InterpKernelHashTable.hxx"
  53
  54 namespace INTERP_KERNEL
  55 {
  56   template<class _Key, class _Tp, class _HashFn = hash<_Key>,
  57            class _EqualKey = std::equal_to<_Key>, class _Alloc = std::allocator<_Tp> >
  58   class HashMap
  59   {
  60   private:
  61     typedef hashtable<std::pair<const _Key, _Tp>,_Key, _HashFn,
  62                       STLEXT::Select1st<std::pair<const _Key, _Tp> >,
  63                       _EqualKey, _Alloc> _Ht;
  64
  65     _Ht _M_ht;
  66
  67   public:
  68     typedef typename _Ht::key_type key_type;
  69     typedef _Tp data_type;
  70     typedef _Tp mapped_type;
  71     typedef typename _Ht::value_type value_type;
  72     typedef typename _Ht::hasher hasher;
  73     typedef typename _Ht::key_equal key_equal;
  74
  75     typedef typename _Ht::size_type size_type;
  76     typedef typename _Ht::difference_type difference_type;
  77     typedef typename _Ht::pointer pointer;
  78     typedef typename _Ht::const_pointer const_pointer;
  79     typedef typename _Ht::reference reference;
  80     typedef typename _Ht::const_reference const_reference;
  81
  82     typedef typename _Ht::iterator iterator;
  83     typedef typename _Ht::const_iterator const_iterator;
  84
  85     typedef typename _Ht::allocator_type allocator_type;
  86
  87     hasher hash_funct() const { return _M_ht.hash_funct(); }
  88
  89     key_equal key_eq() const { return _M_ht.key_eq(); }
  90
  91     allocator_type get_allocator() const { return _M_ht.get_allocator(); }
  92
  93     HashMap() : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
  94
  95     explicit HashMap(size_type __n) : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
  96
  97     HashMap(size_type __n, const hasher& __hf) : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
  98
  99     HashMap(size_type __n, const hasher& __hf, const key_equal& __eql,
 100             const allocator_type& __a = allocator_type()) : _M_ht(__n, __hf, __eql, __a) {}
 101
 102     template<class _InputIterator>
 103     HashMap(_InputIterator __f, _InputIterator __l) : _M_ht(100, hasher(), key_equal(), allocator_type())
 104     { _M_ht.insert_unique(__f, __l); }
 105
 106     template<class _InputIterator>
 107     HashMap(_InputIterator __f, _InputIterator __l, size_type __n) : _M_ht(__n, hasher(), key_equal(), allocator_type())
 108     { _M_ht.insert_unique(__f, __l); }
 109
 110     template<class _InputIterator>
 111     HashMap(_InputIterator __f, _InputIterator __l, size_type __n, const hasher& __hf)
 112       : _M_ht(__n, __hf, key_equal(), allocator_type())
 113     { _M_ht.insert_unique(__f, __l); }
 114
 115     template<class _InputIterator>
 116     HashMap(_InputIterator __f, _InputIterator __l, size_type __n,
 117             const hasher& __hf, const key_equal& __eql,
 118             const allocator_type& __a = allocator_type()) : _M_ht(__n, __hf, __eql, __a)
 119     { _M_ht.insert_unique(__f, __l); }
 120
 121     size_type size() const { return _M_ht.size(); }
 122
 123     size_type max_size() const { return _M_ht.max_size(); }
 124
 125     bool empty() const { return _M_ht.empty(); }
 126
 127     void swap(HashMap& __hs) { _M_ht.swap(__hs._M_ht); }
 128
 129     template<class _K1, class _T1, class _HF, class _EqK, class _Al>
 130     friend bool operator== (const HashMap<_K1, _T1, _HF, _EqK, _Al>&,
 131                             const HashMap<_K1, _T1, _HF, _EqK, _Al>&);
 132
 133     iterator begin() { return _M_ht.begin(); }
 134
 135     iterator end() { return _M_ht.end(); }
 136
 137     const_iterator begin() const { return _M_ht.begin(); }
 138
 139     const_iterator end() const { return _M_ht.end(); }
 140
 141     std::pair<iterator, bool> insert(const value_type& __obj) { return _M_ht.insert_unique(__obj); }
 142
 143     template<class _InputIterator>
 144     void insert(_InputIterator __f, _InputIterator __l) { _M_ht.insert_unique(__f, __l); }
 145
 146     std::pair<iterator, bool>
 147     insert_noresize(const value_type& __obj) { return _M_ht.insert_unique_noresize(__obj); }
 148
 149     iterator find(const key_type& __key) { return _M_ht.find(__key); }
 150
 151     const_iterator find(const key_type& __key) const { return _M_ht.find(__key); }
 152
 153     _Tp& operator[](const key_type& __key) { return _M_ht.find_or_insert(value_type(__key, _Tp())).second; }
 154
 155     size_type count(const key_type& __key) const { return _M_ht.count(__key); }
 156
 157     std::pair<iterator, iterator> equal_range(const key_type& __key) { return _M_ht.equal_range(__key); }
 158
 159     std::pair<const_iterator, const_iterator> equal_range(const key_type& __key) const { return _M_ht.equal_range(__key); }
 160
 161     size_type erase(const key_type& __key) { return _M_ht.erase(__key); }
 162
 163     void erase(iterator __it) { _M_ht.erase(__it); }
 164
 165     void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
 166
 167     void clear() { _M_ht.clear(); }
 168
 169     void resize(size_type __hint) { _M_ht.resize(__hint); }
 170
 171     size_type bucket_count() const { return _M_ht.bucket_count(); }
 172
 173     size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
 174
 175     size_type elems_in_bucket(size_type __n) const { return _M_ht.elems_in_bucket(__n); }
 176   };
 177
 178   template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
 179   inline bool operator==(const HashMap<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
 180                          const HashMap<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
 181   { return __hm1._M_ht == __hm2._M_ht; }
 182
 183   template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
 184   inline bool operator!=(const HashMap<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
 185                          const HashMap<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
 186   { return !(__hm1 == __hm2); }
 187
 188   template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
 189   inline void swap(HashMap<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
 190                    HashMap<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
 191   { __hm1.swap(__hm2); }
 192
 193   template<class _Key, class _Tp,
 194            class _HashFn = hash<_Key>,
 195            class _EqualKey = std::equal_to<_Key>,
 196            class _Alloc = std::allocator<_Tp> >
 197   class HashMultiMap
 198   {
 199   private:
 200     typedef hashtable<std::pair<const _Key, _Tp>, _Key, _HashFn,
 201                       STLEXT::Select1st<std::pair<const _Key, _Tp> >, _EqualKey, _Alloc>
 202     _Ht;
 203     _Ht _M_ht;
 204   public:
 205     typedef typename _Ht::key_type key_type;
 206     typedef _Tp data_type;
 207     typedef _Tp mapped_type;
 208     typedef typename _Ht::value_type value_type;
 209     typedef typename _Ht::hasher hasher;
 210     typedef typename _Ht::key_equal key_equal;
 211
 212     typedef typename _Ht::size_type size_type;
 213     typedef typename _Ht::difference_type difference_type;
 214     typedef typename _Ht::pointer pointer;
 215     typedef typename _Ht::const_pointer const_pointer;
 216     typedef typename _Ht::reference reference;
 217     typedef typename _Ht::const_reference const_reference;
 218
 219     typedef typename _Ht::iterator iterator;
 220     typedef typename _Ht::const_iterator const_iterator;
 221
 222     typedef typename _Ht::allocator_type allocator_type;
 223
 224     hasher hash_funct() const { return _M_ht.hash_funct(); }
 225
 226     key_equal key_eq() const { return _M_ht.key_eq(); }
 227
 228     allocator_type get_allocator() const { return _M_ht.get_allocator(); }
 229
 230     HashMultiMap() : _M_ht(100, hasher(), key_equal(), allocator_type()) { }
 231
 232     explicit HashMultiMap(size_type __n) : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
 233
 234     HashMultiMap(size_type __n, const hasher& __hf) : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
 235
 236     HashMultiMap(size_type __n, const hasher& __hf, const key_equal& __eql,
 237                  const allocator_type& __a = allocator_type()) : _M_ht(__n, __hf, __eql, __a) {}
 238
 239     template<class _InputIterator>
 240     HashMultiMap(_InputIterator __f, _InputIterator __l) : _M_ht(100, hasher(), key_equal(), allocator_type())
 241     { _M_ht.insert_equal(__f, __l); }
 242
 243     template<class _InputIterator>
 244     HashMultiMap(_InputIterator __f, _InputIterator __l, size_type __n) : _M_ht(__n, hasher(), key_equal(), allocator_type())
 245     { _M_ht.insert_equal(__f, __l); }
 246
 247     template<class _InputIterator>
 248     HashMultiMap(_InputIterator __f, _InputIterator __l, size_type __n, const hasher& __hf)
 249       : _M_ht(__n, __hf, key_equal(), allocator_type())
 250     { _M_ht.insert_equal(__f, __l); }
 251
 252     template<class _InputIterator>
 253     HashMultiMap(_InputIterator __f, _InputIterator __l, size_type __n,
 254                  const hasher& __hf, const key_equal& __eql,
 255                  const allocator_type& __a = allocator_type())
 256       : _M_ht(__n, __hf, __eql, __a)
 257     { _M_ht.insert_equal(__f, __l); }
 258
 259     size_type size() const { return _M_ht.size(); }
 260
 261     size_type max_size() const { return _M_ht.max_size(); }
 262
 263     bool empty() const { return _M_ht.empty(); }
 264
 265     void swap(HashMultiMap& __hs) { _M_ht.swap(__hs._M_ht); }
 266
 267     template<class _K1, class _T1, class _HF, class _EqK, class _Al>
 268     friend bool operator==(const HashMultiMap<_K1, _T1, _HF, _EqK, _Al>&,
 269                            const HashMultiMap<_K1, _T1, _HF, _EqK, _Al>&);
 270
 271     iterator begin() { return _M_ht.begin(); }
 272
 273     iterator end() { return _M_ht.end(); }
 274
 275     const_iterator begin() const { return _M_ht.begin(); }
 276
 277     const_iterator end() const { return _M_ht.end(); }
 278
 279     iterator insert(const value_type& __obj) { return _M_ht.insert_equal(__obj); }
 280
 281     template<class _InputIterator>
 282     void insert(_InputIterator __f, _InputIterator __l) { _M_ht.insert_equal(__f,__l); }
 283
 284     iterator insert_noresize(const value_type& __obj) { return _M_ht.insert_equal_noresize(__obj); }
 285
 286     iterator find(const key_type& __key) { return _M_ht.find(__key); }
 287
 288     const_iterator find(const key_type& __key) const { return _M_ht.find(__key); }
 289
 290     size_type count(const key_type& __key) const { return _M_ht.count(__key); }
 291
 292     std::pair<iterator, iterator> equal_range(const key_type& __key) { return _M_ht.equal_range(__key); }
 293
 294     std::pair<const_iterator, const_iterator> equal_range(const key_type& __key) const { return _M_ht.equal_range(__key); }
 295
 296     size_type erase(const key_type& __key) { return _M_ht.erase(__key); }
 297
 298     void erase(iterator __it) { _M_ht.erase(__it); }
 299
 300     void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
 301
 302     void clear() { _M_ht.clear(); }
 303
 304     void resize(size_type __hint) { _M_ht.resize(__hint); }
 305
 306     size_type bucket_count() const { return _M_ht.bucket_count(); }
 307
 308     size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
 309
 310     size_type elems_in_bucket(size_type __n) const { return _M_ht.elems_in_bucket(__n); }
 311   };
 312
 313   template<class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
 314   inline bool operator==(const HashMultiMap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm1,
 315                          const HashMultiMap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm2)
 316   { return __hm1._M_ht == __hm2._M_ht; }
 317
 318   template<class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
 319   inline bool operator!=(const HashMultiMap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm1,
 320                          const HashMultiMap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm2)
 321   { return !(__hm1 == __hm2); }
 322
 323   template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
 324   inline void swap(HashMultiMap<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
 325                    HashMultiMap<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
 326   { __hm1.swap(__hm2); }
 327
 328 }
 329
 330 namespace std
 331 {
 332   // Specialization of insert_iterator so that it will work for HashMap
 333   // and HashMultiMap.
 334   template<class _Key, class _Tp, class _HashFn,  class _EqKey, class _Alloc>
 335   class insert_iterator<INTERP_KERNEL::HashMap<_Key, _Tp, _HashFn,
 336                                                _EqKey, _Alloc> >
 337   {
 338   protected:
 339     typedef INTERP_KERNEL::HashMap<_Key, _Tp, _HashFn, _EqKey, _Alloc>
 340     _Container;
 341     _Container* container;
 342   public:
 343     typedef _Container          container_type;
 344     typedef output_iterator_tag iterator_category;
 345     typedef void                value_type;
 346     typedef void                difference_type;
 347     typedef void                pointer;
 348     typedef void                reference;
 349
 350     insert_iterator(_Container& __x) : container(&__x) {}
 351
 352     insert_iterator(_Container& __x, typename _Container::iterator) : container(&__x) {}
 353
 354     insert_iterator<_Container>& operator=(const typename _Container::value_type& __value__)
 355     {
 356       container->insert(__value__);
 357       return *this;
 358     }
 359
 360     insert_iterator<_Container>& operator*() { return *this; }
 361
 362     insert_iterator<_Container>& operator++() { return *this; }
 363
 364     insert_iterator<_Container>& operator++(int) { return *this; }
 365   };
 366
 367   template<class _Key, class _Tp, class _HashFn,  class _EqKey, class _Alloc>
 368   class insert_iterator<INTERP_KERNEL::HashMultiMap<_Key, _Tp, _HashFn,
 369                                                     _EqKey, _Alloc> >
 370   {
 371   protected:
 372     typedef INTERP_KERNEL::HashMultiMap<_Key, _Tp, _HashFn, _EqKey, _Alloc>
 373     _Container;
 374     _Container* container;
 375     typename _Container::iterator iter;
 376
 377   public:
 378     typedef _Container          container_type;
 379     typedef output_iterator_tag iterator_category;
 380     typedef void                value_type;
 381     typedef void                difference_type;
 382     typedef void                pointer;
 383     typedef void                reference;
 384
 385     insert_iterator(_Container& __x) : container(&__x) {}
 386
 387     insert_iterator(_Container& __x, typename _Container::iterator) : container(&__x) {}
 388
 389     insert_iterator<_Container>& operator=(const typename _Container::value_type& __value__)
 390     {
 391       container->insert(__value__);
 392       return *this;
 393     }
 394
 395     insert_iterator<_Container>& operator*() { return *this; }
 396
 397     insert_iterator<_Container>& operator++() { return *this; }
 398
 399     insert_iterator<_Container>& operator++(int) { return *this; }
 400   };
 401 }
 402
 403 #endif