hash_map.hxx.in 13.3 KB
Newer Older
Kitware Robot's avatar
Kitware Robot committed
1 2
/* Distributed under the OSI-approved BSD 3-Clause License.  See accompanying
   file Copyright.txt or https://cmake.org/licensing#kwsys for details.  */
Kitware Robot's avatar
Kitware Robot committed
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
/*
 * Copyright (c) 1996
 * Silicon Graphics Computer Systems, Inc.
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Silicon Graphics makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Hewlett-Packard Company makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *
 */
#ifndef @KWSYS_NAMESPACE@_hash_map_hxx
#define @KWSYS_NAMESPACE@_hash_map_hxx

#include <@KWSYS_NAMESPACE@/hashtable.hxx>
Kitware Robot's avatar
Kitware Robot committed
32

Kitware Robot's avatar
Kitware Robot committed
33
#include <@KWSYS_NAMESPACE@/hash_fun.hxx>
Kitware Robot's avatar
Kitware Robot committed
34

Kitware Robot's avatar
Kitware Robot committed
35
#include <functional> // equal_to
Kitware Robot's avatar
Kitware Robot committed
36 37

#if defined(_MSC_VER)
Kitware Robot's avatar
Kitware Robot committed
38 39 40
#  pragma warning(push)
#  pragma warning(disable : 4284)
#  pragma warning(disable : 4786)
Kitware Robot's avatar
Kitware Robot committed
41 42 43
#endif

#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
Kitware Robot's avatar
Kitware Robot committed
44 45
#  pragma set woff 1174
#  pragma set woff 1375
Kitware Robot's avatar
Kitware Robot committed
46 47
#endif

Kitware Robot's avatar
Kitware Robot committed
48
namespace @KWSYS_NAMESPACE@ {
Kitware Robot's avatar
Kitware Robot committed
49 50 51

// select1st is an extension: it is not part of the standard.
template <class T1, class T2>
Kitware Robot's avatar
Kitware Robot committed
52
struct hash_select1st
Kitware Robot's avatar
Kitware Robot committed
53
{
Kitware Robot's avatar
Kitware Robot committed
54
  const T1& operator()(const std::pair<T1, T2>& __x) const
Kitware Robot's avatar
Kitware Robot committed
55 56 57
  {
    return __x.first;
  }
Kitware Robot's avatar
Kitware Robot committed
58 59 60 61
};

// Forward declaration of equality operator; needed for friend declaration.

Kitware Robot's avatar
Kitware Robot committed
62
template <class _Key, class _Tp, class _HashFcn = hash<_Key>,
Kitware Robot's avatar
Kitware Robot committed
63 64
          class _EqualKey = std::equal_to<_Key>,
          class _Alloc = std::allocator<char> >
Kitware Robot's avatar
Kitware Robot committed
65 66 67 68 69 70
class hash_map;

template <class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc>
bool operator==(const hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>&,
                const hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>&);

Kitware Robot's avatar
Kitware Robot committed
71
template <class _Key, class _Tp, class _HashFcn, class _EqualKey, class _Alloc>
Kitware Robot's avatar
Kitware Robot committed
72 73 74
class hash_map
{
private:
Kitware Robot's avatar
Kitware Robot committed
75 76 77
  typedef hashtable<std::pair<const _Key, _Tp>, _Key, _HashFcn,
                    hash_select1st<const _Key, _Tp>, _EqualKey, _Alloc>
    _Ht;
Kitware Robot's avatar
Kitware Robot committed
78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104
  _Ht _M_ht;

public:
  typedef typename _Ht::key_type key_type;
  typedef _Tp data_type;
  typedef _Tp mapped_type;
  typedef typename _Ht::value_type value_type;
  typedef typename _Ht::hasher hasher;
  typedef typename _Ht::key_equal key_equal;

  typedef typename _Ht::size_type size_type;
  typedef typename _Ht::difference_type difference_type;
  typedef typename _Ht::pointer pointer;
  typedef typename _Ht::const_pointer const_pointer;
  typedef typename _Ht::reference reference;
  typedef typename _Ht::const_reference const_reference;

  typedef typename _Ht::iterator iterator;
  typedef typename _Ht::const_iterator const_iterator;

  typedef typename _Ht::allocator_type allocator_type;

  hasher hash_funct() const { return _M_ht.hash_funct(); }
  key_equal key_eq() const { return _M_ht.key_eq(); }
  allocator_type get_allocator() const { return _M_ht.get_allocator(); }

public:
Kitware Robot's avatar
Kitware Robot committed
105 106 107 108
  hash_map()
    : _M_ht(100, hasher(), key_equal(), allocator_type())
  {
  }
Kitware Robot's avatar
Kitware Robot committed
109
  explicit hash_map(size_type __n)
Kitware Robot's avatar
Kitware Robot committed
110 111 112
    : _M_ht(__n, hasher(), key_equal(), allocator_type())
  {
  }
Kitware Robot's avatar
Kitware Robot committed
113
  hash_map(size_type __n, const hasher& __hf)
Kitware Robot's avatar
Kitware Robot committed
114 115 116
    : _M_ht(__n, __hf, key_equal(), allocator_type())
  {
  }
Kitware Robot's avatar
Kitware Robot committed
117 118
  hash_map(size_type __n, const hasher& __hf, const key_equal& __eql,
           const allocator_type& __a = allocator_type())
Kitware Robot's avatar
Kitware Robot committed
119 120 121
    : _M_ht(__n, __hf, __eql, __a)
  {
  }
Kitware Robot's avatar
Kitware Robot committed
122 123 124 125

  template <class _InputIterator>
  hash_map(_InputIterator __f, _InputIterator __l)
    : _M_ht(100, hasher(), key_equal(), allocator_type())
Kitware Robot's avatar
Kitware Robot committed
126 127 128
  {
    _M_ht.insert_unique(__f, __l);
  }
Kitware Robot's avatar
Kitware Robot committed
129 130 131
  template <class _InputIterator>
  hash_map(_InputIterator __f, _InputIterator __l, size_type __n)
    : _M_ht(__n, hasher(), key_equal(), allocator_type())
Kitware Robot's avatar
Kitware Robot committed
132 133 134
  {
    _M_ht.insert_unique(__f, __l);
  }
Kitware Robot's avatar
Kitware Robot committed
135 136 137 138
  template <class _InputIterator>
  hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
           const hasher& __hf)
    : _M_ht(__n, __hf, key_equal(), allocator_type())
Kitware Robot's avatar
Kitware Robot committed
139 140 141
  {
    _M_ht.insert_unique(__f, __l);
  }
Kitware Robot's avatar
Kitware Robot committed
142 143 144 145 146
  template <class _InputIterator>
  hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
           const hasher& __hf, const key_equal& __eql,
           const allocator_type& __a = allocator_type())
    : _M_ht(__n, __hf, __eql, __a)
Kitware Robot's avatar
Kitware Robot committed
147 148 149
  {
    _M_ht.insert_unique(__f, __l);
  }
Kitware Robot's avatar
Kitware Robot committed
150 151 152 153 154 155 156

public:
  size_type size() const { return _M_ht.size(); }
  size_type max_size() const { return _M_ht.max_size(); }
  bool empty() const { return _M_ht.empty(); }
  void swap(hash_map& __hs) { _M_ht.swap(__hs._M_ht); }

Kitware Robot's avatar
Kitware Robot committed
157
  friend bool operator==<>(const hash_map&, const hash_map&);
Kitware Robot's avatar
Kitware Robot committed
158 159 160 161 162 163 164

  iterator begin() { return _M_ht.begin(); }
  iterator end() { return _M_ht.end(); }
  const_iterator begin() const { return _M_ht.begin(); }
  const_iterator end() const { return _M_ht.end(); }

public:
Kitware Robot's avatar
Kitware Robot committed
165 166 167 168
  std::pair<iterator, bool> insert(const value_type& __obj)
  {
    return _M_ht.insert_unique(__obj);
  }
Kitware Robot's avatar
Kitware Robot committed
169 170
  template <class _InputIterator>
  void insert(_InputIterator __f, _InputIterator __l)
Kitware Robot's avatar
Kitware Robot committed
171 172 173 174 175 176 177
  {
    _M_ht.insert_unique(__f, __l);
  }
  std::pair<iterator, bool> insert_noresize(const value_type& __obj)
  {
    return _M_ht.insert_unique_noresize(__obj);
  }
Kitware Robot's avatar
Kitware Robot committed
178 179 180

  iterator find(const key_type& __key) { return _M_ht.find(__key); }
  const_iterator find(const key_type& __key) const
Kitware Robot's avatar
Kitware Robot committed
181 182 183
  {
    return _M_ht.find(__key);
  }
Kitware Robot's avatar
Kitware Robot committed
184

Kitware Robot's avatar
Kitware Robot committed
185 186
  _Tp& operator[](const key_type& __key)
  {
Kitware Robot's avatar
Kitware Robot committed
187 188 189 190 191
    return _M_ht.find_or_insert(value_type(__key, _Tp())).second;
  }

  size_type count(const key_type& __key) const { return _M_ht.count(__key); }

Kitware Robot's avatar
Kitware Robot committed
192
  std::pair<iterator, iterator> equal_range(const key_type& __key)
Kitware Robot's avatar
Kitware Robot committed
193 194 195 196 197 198 199 200
  {
    return _M_ht.equal_range(__key);
  }
  std::pair<const_iterator, const_iterator> equal_range(
    const key_type& __key) const
  {
    return _M_ht.equal_range(__key);
  }
Kitware Robot's avatar
Kitware Robot committed
201

Kitware Robot's avatar
Kitware Robot committed
202
  size_type erase(const key_type& __key) { return _M_ht.erase(__key); }
Kitware Robot's avatar
Kitware Robot committed
203 204 205 206 207 208 209 210
  void erase(iterator __it) { _M_ht.erase(__it); }
  void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
  void clear() { _M_ht.clear(); }

  void resize(size_type __hint) { _M_ht.resize(__hint); }
  size_type bucket_count() const { return _M_ht.bucket_count(); }
  size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
  size_type elems_in_bucket(size_type __n) const
Kitware Robot's avatar
Kitware Robot committed
211 212 213
  {
    return _M_ht.elems_in_bucket(__n);
  }
Kitware Robot's avatar
Kitware Robot committed
214 215 216
};

template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc>
Kitware Robot's avatar
Kitware Robot committed
217 218
bool operator==(const hash_map<_Key, _Tp, _HashFcn, _EqlKey, _Alloc>& __hm1,
                const hash_map<_Key, _Tp, _HashFcn, _EqlKey, _Alloc>& __hm2)
Kitware Robot's avatar
Kitware Robot committed
219 220 221 222 223
{
  return __hm1._M_ht == __hm2._M_ht;
}

template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc>
Kitware Robot's avatar
Kitware Robot committed
224 225 226 227
inline bool operator!=(
  const hash_map<_Key, _Tp, _HashFcn, _EqlKey, _Alloc>& __hm1,
  const hash_map<_Key, _Tp, _HashFcn, _EqlKey, _Alloc>& __hm2)
{
Kitware Robot's avatar
Kitware Robot committed
228 229 230 231
  return !(__hm1 == __hm2);
}

template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc>
Kitware Robot's avatar
Kitware Robot committed
232 233
inline void swap(hash_map<_Key, _Tp, _HashFcn, _EqlKey, _Alloc>& __hm1,
                 hash_map<_Key, _Tp, _HashFcn, _EqlKey, _Alloc>& __hm2)
Kitware Robot's avatar
Kitware Robot committed
234 235 236 237 238 239
{
  __hm1.swap(__hm2);
}

// Forward declaration of equality operator; needed for friend declaration.

Kitware Robot's avatar
Kitware Robot committed
240
template <class _Key, class _Tp, class _HashFcn = hash<_Key>,
Kitware Robot's avatar
Kitware Robot committed
241 242
          class _EqualKey = std::equal_to<_Key>,
          class _Alloc = std::allocator<char> >
Kitware Robot's avatar
Kitware Robot committed
243 244 245
class hash_multimap;

template <class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
Kitware Robot's avatar
Kitware Robot committed
246 247
bool operator==(const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm1,
                const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm2);
Kitware Robot's avatar
Kitware Robot committed
248

Kitware Robot's avatar
Kitware Robot committed
249
template <class _Key, class _Tp, class _HashFcn, class _EqualKey, class _Alloc>
Kitware Robot's avatar
Kitware Robot committed
250 251 252
class hash_multimap
{
private:
Kitware Robot's avatar
Kitware Robot committed
253
  typedef hashtable<std::pair<const _Key, _Tp>, _Key, _HashFcn,
Kitware Robot's avatar
Kitware Robot committed
254
                    hash_select1st<const _Key, _Tp>, _EqualKey, _Alloc>
Kitware Robot's avatar
Kitware Robot committed
255
    _Ht;
Kitware Robot's avatar
Kitware Robot committed
256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282
  _Ht _M_ht;

public:
  typedef typename _Ht::key_type key_type;
  typedef _Tp data_type;
  typedef _Tp mapped_type;
  typedef typename _Ht::value_type value_type;
  typedef typename _Ht::hasher hasher;
  typedef typename _Ht::key_equal key_equal;

  typedef typename _Ht::size_type size_type;
  typedef typename _Ht::difference_type difference_type;
  typedef typename _Ht::pointer pointer;
  typedef typename _Ht::const_pointer const_pointer;
  typedef typename _Ht::reference reference;
  typedef typename _Ht::const_reference const_reference;

  typedef typename _Ht::iterator iterator;
  typedef typename _Ht::const_iterator const_iterator;

  typedef typename _Ht::allocator_type allocator_type;

  hasher hash_funct() const { return _M_ht.hash_funct(); }
  key_equal key_eq() const { return _M_ht.key_eq(); }
  allocator_type get_allocator() const { return _M_ht.get_allocator(); }

public:
Kitware Robot's avatar
Kitware Robot committed
283 284 285 286
  hash_multimap()
    : _M_ht(100, hasher(), key_equal(), allocator_type())
  {
  }
Kitware Robot's avatar
Kitware Robot committed
287
  explicit hash_multimap(size_type __n)
Kitware Robot's avatar
Kitware Robot committed
288 289 290
    : _M_ht(__n, hasher(), key_equal(), allocator_type())
  {
  }
Kitware Robot's avatar
Kitware Robot committed
291
  hash_multimap(size_type __n, const hasher& __hf)
Kitware Robot's avatar
Kitware Robot committed
292 293 294
    : _M_ht(__n, __hf, key_equal(), allocator_type())
  {
  }
Kitware Robot's avatar
Kitware Robot committed
295 296
  hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql,
                const allocator_type& __a = allocator_type())
Kitware Robot's avatar
Kitware Robot committed
297 298 299
    : _M_ht(__n, __hf, __eql, __a)
  {
  }
Kitware Robot's avatar
Kitware Robot committed
300 301 302 303

  template <class _InputIterator>
  hash_multimap(_InputIterator __f, _InputIterator __l)
    : _M_ht(100, hasher(), key_equal(), allocator_type())
Kitware Robot's avatar
Kitware Robot committed
304 305 306
  {
    _M_ht.insert_equal(__f, __l);
  }
Kitware Robot's avatar
Kitware Robot committed
307 308 309
  template <class _InputIterator>
  hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n)
    : _M_ht(__n, hasher(), key_equal(), allocator_type())
Kitware Robot's avatar
Kitware Robot committed
310 311 312
  {
    _M_ht.insert_equal(__f, __l);
  }
Kitware Robot's avatar
Kitware Robot committed
313 314 315 316
  template <class _InputIterator>
  hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
                const hasher& __hf)
    : _M_ht(__n, __hf, key_equal(), allocator_type())
Kitware Robot's avatar
Kitware Robot committed
317 318 319
  {
    _M_ht.insert_equal(__f, __l);
  }
Kitware Robot's avatar
Kitware Robot committed
320 321 322 323 324
  template <class _InputIterator>
  hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
                const hasher& __hf, const key_equal& __eql,
                const allocator_type& __a = allocator_type())
    : _M_ht(__n, __hf, __eql, __a)
Kitware Robot's avatar
Kitware Robot committed
325 326 327
  {
    _M_ht.insert_equal(__f, __l);
  }
Kitware Robot's avatar
Kitware Robot committed
328 329 330 331 332 333 334

public:
  size_type size() const { return _M_ht.size(); }
  size_type max_size() const { return _M_ht.max_size(); }
  bool empty() const { return _M_ht.empty(); }
  void swap(hash_multimap& __hs) { _M_ht.swap(__hs._M_ht); }

Kitware Robot's avatar
Kitware Robot committed
335
  friend bool operator==<>(const hash_multimap&, const hash_multimap&);
Kitware Robot's avatar
Kitware Robot committed
336 337 338 339 340 341 342 343

  iterator begin() { return _M_ht.begin(); }
  iterator end() { return _M_ht.end(); }
  const_iterator begin() const { return _M_ht.begin(); }
  const_iterator end() const { return _M_ht.end(); }

public:
  iterator insert(const value_type& __obj)
Kitware Robot's avatar
Kitware Robot committed
344 345 346
  {
    return _M_ht.insert_equal(__obj);
  }
Kitware Robot's avatar
Kitware Robot committed
347 348
  template <class _InputIterator>
  void insert(_InputIterator __f, _InputIterator __l)
Kitware Robot's avatar
Kitware Robot committed
349 350 351
  {
    _M_ht.insert_equal(__f, __l);
  }
Kitware Robot's avatar
Kitware Robot committed
352
  iterator insert_noresize(const value_type& __obj)
Kitware Robot's avatar
Kitware Robot committed
353 354 355
  {
    return _M_ht.insert_equal_noresize(__obj);
  }
Kitware Robot's avatar
Kitware Robot committed
356 357 358

  iterator find(const key_type& __key) { return _M_ht.find(__key); }
  const_iterator find(const key_type& __key) const
Kitware Robot's avatar
Kitware Robot committed
359 360 361
  {
    return _M_ht.find(__key);
  }
Kitware Robot's avatar
Kitware Robot committed
362 363 364

  size_type count(const key_type& __key) const { return _M_ht.count(__key); }

Kitware Robot's avatar
Kitware Robot committed
365
  std::pair<iterator, iterator> equal_range(const key_type& __key)
Kitware Robot's avatar
Kitware Robot committed
366 367 368 369 370 371 372 373
  {
    return _M_ht.equal_range(__key);
  }
  std::pair<const_iterator, const_iterator> equal_range(
    const key_type& __key) const
  {
    return _M_ht.equal_range(__key);
  }
Kitware Robot's avatar
Kitware Robot committed
374

Kitware Robot's avatar
Kitware Robot committed
375
  size_type erase(const key_type& __key) { return _M_ht.erase(__key); }
Kitware Robot's avatar
Kitware Robot committed
376 377 378 379 380 381 382 383 384
  void erase(iterator __it) { _M_ht.erase(__it); }
  void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
  void clear() { _M_ht.clear(); }

public:
  void resize(size_type __hint) { _M_ht.resize(__hint); }
  size_type bucket_count() const { return _M_ht.bucket_count(); }
  size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
  size_type elems_in_bucket(size_type __n) const
Kitware Robot's avatar
Kitware Robot committed
385 386 387
  {
    return _M_ht.elems_in_bucket(__n);
  }
Kitware Robot's avatar
Kitware Robot committed
388 389 390
};

template <class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
Kitware Robot's avatar
Kitware Robot committed
391 392
bool operator==(const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm1,
                const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm2)
Kitware Robot's avatar
Kitware Robot committed
393 394 395 396 397
{
  return __hm1._M_ht == __hm2._M_ht;
}

template <class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
Kitware Robot's avatar
Kitware Robot committed
398 399 400 401
inline bool operator!=(
  const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm1,
  const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm2)
{
Kitware Robot's avatar
Kitware Robot committed
402 403 404 405
  return !(__hm1 == __hm2);
}

template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc>
Kitware Robot's avatar
Kitware Robot committed
406 407
inline void swap(hash_multimap<_Key, _Tp, _HashFcn, _EqlKey, _Alloc>& __hm1,
                 hash_multimap<_Key, _Tp, _HashFcn, _EqlKey, _Alloc>& __hm2)
Kitware Robot's avatar
Kitware Robot committed
408 409 410 411 412 413 414
{
  __hm1.swap(__hm2);
}

} // namespace @KWSYS_NAMESPACE@

#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
Kitware Robot's avatar
Kitware Robot committed
415 416
#  pragma reset woff 1174
#  pragma reset woff 1375
Kitware Robot's avatar
Kitware Robot committed
417 418 419
#endif

#if defined(_MSC_VER)
Kitware Robot's avatar
Kitware Robot committed
420
#  pragma warning(pop)
Kitware Robot's avatar
Kitware Robot committed
421 422 423
#endif

#endif