This file is indexed.

/usr/include/dune/common/hash.hh is in libdune-common-dev 2.3.1-1.

This file is owned by root:root, with mode 0o644.

The actual contents of the file can be viewed below.

  1
  2
  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
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
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
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
// -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*-
// vi: set et ts=4 sw=2 sts=2:
#ifndef DUNE_COMMON_HASH_HH
#define DUNE_COMMON_HASH_HH

#include <dune/common/typetraits.hh>
#include <dune/common/static_assert.hh>

#if HAVE_STD_HASH
#include <functional>
#endif

#if HAVE_TR1_HASH
#include <tr1/functional>
#endif

#if HAVE_DUNE_BOOST

#include <boost/version.hpp>

// Boost 1.34.0 seems to be the first usable version of boost::functional::hash
#if BOOST_VERSION >= 103400
#define HAVE_BOOST_HASH 1

// only pull in boost if really necessary
#if !HAVE_STD_HASH && !HAVE_TR1_HASH

#include <boost/functional/hash.hpp>

#endif // !HAVE_STD_HASH && !HAVE_TR1_HASH
#endif // BOOST_VERSION >= 103400
#endif // HAVE_DUNE_BOOST

/**
 * \file
 * \brief Support for calculating hash values of objects.
 *
 * This file provides the functor Dune::hash to calculate hash values and
 * some infrastructure to simplify extending Dune::hash for user-defined types,
 * independent of the actual underlying implementation.
 *
 */



// ********************************************************************************
// Doxygen documentation
// ********************************************************************************

#ifdef DOXYGEN

namespace Dune {

  //! Functor for hashing objects of type T.
  /**
   * The interface outlined below is compatible with std::hash, std::tr1::hash and
   * boost::hash, so it is possible to use Dune::hash in associative containers from
   * those libraries.
   *
   * The current implementation piggybacks on top of C++11, TR1 or Boost, in that order.
   * As there is no local fallback implementation, hashing will not work without at least
   * one of those dependencies installed.
   */
  template<typename T>
  struct hash
  {

    //! Calculates the hash of t.
    std::size_t operator()(const T& t) const
    {
      return hash(t);
    }

  };

}

//! Defines the required struct specialization to make type hashable via `Dune::hash`.
/**
 * In order to calculate the hash, operator() of the generated specialization will
 * return the result of an unqualified call to the global function `hash_value(const type&)`.
 * As the call is not qualified, the function will be found using argument-dependent lookup,
 * allowing implementors to conveniently place it inside the class body.
 *
 * Consider the following type:
 *
 * \code
 * namespace ns {
 *   template<typename A, int i>
 *   class Foo
 *   {
 *     ...
 *   };
 * }
 * \endcode
 *
 * In order to add support for `Dune::hash`, you need to extend the definition like this:
 *
 * \code
 * namespace ns {
 *   template<typename A, int i>
 *   class Foo
 *   {
 *     ...
 *     // The keyword "friend" turns this into a global function that is a friend of Foo.
 *     inline friend std::size_t hash_value(const Foo& arg)
 *     {
 *       return ...;
 *     }
 *   };
 * }
 *
 * // Define hash struct specialization
 * DUNE_DEFINE_HASH(DUNE_HASH_TEMPLATE_ARGS(typename A, int i),DUNE_HASH_TYPE(Foo<A,i>))
 * \endcode
 *
 * \warning
 * As the specialization has to be placed in the original namespace of the
 * `hash` struct (e.g. `std`), this macro *must* be called from the global namespace!
 *
 * \param template_args  The template arguments required by the hash struct specialization,
 *                       wrapped in a call to DUNE_HASH_TEMPLATE_ARGS. If this is a complete
 *                       specialization, call DUNE_HASH_TEMPLATE_ARGS without arguments.
 * \param type           The exact type of the specialization, wrapped in a call to DUNE_HASH_TYPE.
 */
#define DUNE_DEFINE_HASH(template_args,type)


//! Wrapper macro for the template arguments in DUNE_DEFINE_HASH.
/**
 * This macro should always be used as a wrapper for the template arguments when calling DUNE_DEFINE_HASH.
 * It works around some preprocessor limitations when the template arguments contain commas or the list
 * is completely empty.
 */
#define DUNE_HASH_TEMPLATE_ARGS(...)

//! Wrapper macro for the type to be hashed in DUNE_DEFINE_HASH.
/**
 * This macro should always be used as a wrapper for the type of the specialization when calling
 * DUNE_DEFINE_HASH.
 * It works around some preprocessor limitations when the type contains commas.
 */
#define DUNE_HASH_TYPE(...)

#else // DOXYGEN - hide all the ugly implementation



// ********************************************************************************
// C++11 support
// ********************************************************************************

#if HAVE_STD_HASH
// We have std::hash from C++11

// Announce that we provide Dune::hash
#define HAVE_DUNE_HASH 1

// import std::hash into Dune namespace
namespace Dune {

  using std::hash;

}

// Macro for defining a std::hash specialization for type.
// This should not be called directly. Call DUNE_DEFINE_HASH
// instead.
#define DUNE_DEFINE_STD_HASH(template_args,type) \
  namespace std {                                  \
                                                 \
    template<template_args>                          \
    struct hash<type>                                \
    {                                                \
      std::size_t operator()(const type& arg) const  \
      {                                              \
        return hash_value(arg);                      \
      }                                              \
    };                                               \
                                                 \
  }                                                \

#else // HAVE_STD_HASH

// We do not support std::hash, so don't do anything here.
#define DUNE_DEFINE_STD_HASH(template_args,type)

#endif // HAVE_STD_HASH



// ********************************************************************************
// TR1 support
// ********************************************************************************

#if HAVE_TR1_HASH
// We have std::tr1::hash from TR1

#ifndef HAVE_DUNE_HASH
// std::hash wasn't found, so use std::tr1::hash

// Announce that we provide Dune::hash
#define HAVE_DUNE_HASH 1

// import std::tr1::hash into Dune namespace
namespace Dune {

  using std::tr1::hash;

}

#endif // HAVE_DUNE_HASH

// Macro for defining a std::tr1::hash specialization for type.
// This should not be called directly. Call DUNE_DEFINE_HASH
// instead.
#define DUNE_DEFINE_TR1_HASH(template_args,type) \
  namespace std {                                  \
    namespace tr1 {                                  \
                                                 \
      template<template_args>                          \
      struct hash<type>                                \
      {                                                \
        std::size_t operator()(const type& arg) const  \
        {                                              \
          return hash_value(arg);                      \
        }                                              \
      };                                               \
                                                 \
    }                                                \
  }                                                \

#else // HAVE_TR1_HASH

// We do not support std::tr1::hash, so don't do anything here.
#define DUNE_DEFINE_TR1_HASH(template_args,type)

#endif // HAVE_TR1_HASH



// ********************************************************************************
// common macros for both C++11 and TR1 support
// ********************************************************************************

#if HAVE_STD_HASH || HAVE_TR1_HASH

// Wrapper macro for template arguments.
// This is required because the template arguments can contain commas,
// which will create a macro argument list of unknown length. That in itself
// would not be a problem, but DUNE_DEFINE_HASH has to be called with two argument
// lists of unknown length. So this macro wraps its arguments with parentheses,
// turning it into a single argument. The result is used as the parameter list of
// an expansion macro in the calls to the implementation-specific macros
// for C++11 and TR1. Noto that technically, this trick is only legal for C++11,
// but pretty much every compiler supports variadic macros in C++03 mode, as they
// are part of C99.
#define DUNE_HASH_TEMPLATE_ARGS(...) (__VA_ARGS__)

// Wrapper macro for type to be hashed.
// See above for rationale.
#define DUNE_HASH_TYPE(...) (__VA_ARGS__)

// Expansion macro for the parenthesed argument lists created by
// DUNE_HASH_TEMPLATE_ARGS and DUNE_HASH_TYPE.
#define DUNE_HASH_EXPAND_VA_ARGS(...) __VA_ARGS__

// Define specializations for all discovered hash implementations.
#define DUNE_DEFINE_HASH(template_args,type)                                                  \
  DUNE_DEFINE_STD_HASH(DUNE_HASH_EXPAND_VA_ARGS template_args, DUNE_HASH_EXPAND_VA_ARGS type) \
  DUNE_DEFINE_TR1_HASH(DUNE_HASH_EXPAND_VA_ARGS template_args,DUNE_HASH_EXPAND_VA_ARGS type)  \


#else // HAVE_STD_HASH || HAVE_TR1_HASH


// Fallback implementation that doesn't do anything.
#define DUNE_DEFINE_HASH(template_args,type)

// Consider DUNE_HASH_TEMPLATE_ARGS as an argument-less macro and
// replace it with an empty token.
// This will leave its arguments in parentheses, causing them
// to be considered as a single argument to DUNE_DEFINE_HASH, which
// will ignore them anyway.
#define DUNE_HASH_TEMPLATE_ARGS

// Replace DUNE_HASH_TYPE with an empty token. See above for rationale.
#define DUNE_HASH_TYPE

#endif // HAVE_STD_HASH || HAVE_TR1_HASH



// ********************************************************************************
// Boost support
// ********************************************************************************

#if !HAVE_DUNE_HASH && HAVE_BOOST_HASH
// We haven't found a hash implementation yet and Boost is available

// Announce that we provide Dune::hash
#define HAVE_DUNE_HASH 1

// import boost::hash into Dune namespace
namespace Dune {

  using boost::hash;

}

// We no not need to register our types with boost::hash, as its extension
// mechanism will automatically pick up the global hash_value() functions.

#endif // !HAVE_DUNE_HASH && HAVE_BOOST_HASH

#endif // DOXYGEN



// ********************************************************************************
// Some utility functions for combining hashes of member variables.
// ********************************************************************************

#if HAVE_DUNE_HASH || defined(DOXYGEN)

namespace Dune {

  // The following functions are an implementation of the proposed hash extensions for
  // the C++ standard by Peter Dimov
  // (cf. http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2005/n1756.pdf, issue 6.18).
  // They are also contained in the boost::functional::hash library by Daniel James, but
  // that implementation uses boost::hash internally, while we want to use Dune::hash. They
  // are also considered for inclusion in TR2 (then based on std::hash, of course).

#ifndef DOXYGEN

  // helper struct for providing different hash combining algorithms dependent on
  // the size of size_t.
  // hash_combiner has to be specialized for the size (in bytes) of std::size_t.
  // Specialized versions should provide a method
  //
  // template <typename typeof_size_t, typename T>
  // void operator()(typeof_size_t& seed, const T& arg) const;
  //
  // that will be called by the interface function hash_combine() described further below.
  // The redundant template parameter typeof_size_t is needed to avoid warnings for the
  // unused 64-bit specialization on 32-bit systems.
  //
  // There is no default implementation!
  template<int sizeof_size_t>
  struct hash_combiner;


  // hash combining for 64-bit platforms.
  template<>
  struct hash_combiner<8>
  {

    template<typename typeof_size_t, typename T>
    void operator()(typeof_size_t& seed, const T& arg) const
    {
      dune_static_assert(sizeof(typeof_size_t)==8, "hash_combiner::operator() instantiated with nonmatching type and size");

      // The following algorithm for combining two 64-bit hash values is inspired by a similar
      // function in CityHash (http://cityhash.googlecode.com/svn-history/r2/trunk/src/city.h),
      // which is in turn based on ideas from the MurmurHash library. The basic idea is easy to
      // grasp, though: New information is XORed into the existing hash multiple times at different
      // places (using shift operations), and the resulting pattern is spread over the complete
      // range of available bits via multiplication with a "magic" constant. The constants used
      // below (47 and  0x9ddfea08eb382d69ULL) are taken from the CityHash implementation.
      //
      // We opted not to use the mixing algorithm proposed in the C++ working group defect list at
      // http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2005/n1756.pdf, p. 57f. because it
      // has very bad hash distribution properties if you apply it to lists of very small numbers,
      // an application that is frequent in PDELab's ordering framework.

      Dune::hash<T> hasher;
      const typeof_size_t kMul = 0x9ddfea08eb382d69ULL;
      typeof_size_t h = hasher(arg);
      typeof_size_t a = (seed ^ h) * kMul;
      a ^= (a >> 47);
      typeof_size_t b = (h ^ a) * kMul;
      b ^= (b >> 47);
      b *= kMul;
      seed = b;
    }

  };


  // hash combining for 32-bit platforms.
  template<>
  struct hash_combiner<4>
  {

    template<typename typeof_size_t, typename T>
    void operator()(typeof_size_t& seed, const T& arg) const
    {
      dune_static_assert(sizeof(typeof_size_t)==4, "hash_combiner::operator() instantiated with nonmatching type and size");

      // The default algorithm above requires a 64-bit std::size_t. The following algorithm is a
      // 32-bit compatible fallback, again inspired by CityHash and MurmurHash
      // (http://cityhash.googlecode.com/svn-history/r2/trunk/src/city.cc).
      // It uses 32-bit constants and relies on rotation instead of multiplication to spread the
      // mixed bits as that is apparently more efficient on IA-32. The constants used below are again
      // taken from CityHash, in particular from the file referenced above.

      Dune::hash<T> hasher;
      const typeof_size_t c1 = 0xcc9e2d51;
      const typeof_size_t c2 = 0x1b873593;
      const typeof_size_t c3 = 0xe6546b64;
      typeof_size_t h = hasher(arg);
      typeof_size_t a = seed * c1;
      a = (a >> 17) | (a << (32 - 17));
      a *= c2;
      h ^= a;
      h = (h >> 19) | (h << (32 - 19));
      seed = h * 5 + c3;
    }

  };

#endif // DOXYGEN

  //! Calculates the hash value of arg and combines it in-place with seed.
  /**
   * \note This function is only available if the macro `HAVE_DUNE_HASH` is defined.
   *
   * \param seed  The hash value that will be combined with the hash of arg.
   * \param arg   The object for which to calculate a hash value and combine it with seed.
   */
  template<typename T>
  inline void hash_combine(std::size_t& seed, const T& arg)
  {
    hash_combiner<sizeof(std::size_t)>()(seed,arg);
  }

  //! Hashes all elements in the range [first,last) and returns the combined hash.
  /**
   * \note This function is only available if the macro `HAVE_DUNE_HASH` is defined.
   *
   * \param first  Iterator pointing to the first object to hash.
   * \param last   Iterator pointing one past the last object to hash.

   * \returns      The result of hashing all objects in the range and combining them
   *               using hash_combine() in sequential fashion, starting with seed 0.
   */
  template<typename It>
  inline std::size_t hash_range(It first, It last)
  {
    std::size_t seed = 0;
    for (; first != last; ++first)
    {
      hash_combine(seed,*first);
    }
    return seed;
  }

  //! Hashes all elements in the range [first,last) and combines the hashes in-place with seed.
  /**
   * \note This function is only available if the macro `HAVE_DUNE_HASH` is defined.
   *
   * \param seed   Start value that will be combined with the hash values of all objects in
   *               the range using hash_combine() in sequential fashion.
   * \param first  Iterator pointing to the first ojbect to hash.
   * \param last   Iterator pointing one past the last object to hash.
   */
  template<typename It>
  inline void hash_range(std::size_t& seed, It first, It last)
  {
    for (; first != last; ++first)
    {
      hash_combine(seed,*first);
    }
  }

} // end namespace Dune

#endif // HAVE_DUNE_HASH || defined(DOXYGEN)

#endif // DUNE_COMMON_HASH_HH