← Back to branch summary

~ubuntu-branches/ubuntu/precise/dwarves-dfsg/precise

« back to all changes in this revision

Viewing changes to hash.h

  • Committer: Bazaar Package Importer
  • Author(s): Thomas Girard
  • Date: 2011-05-02 19:34:31 UTC
  • mfrom: (1.1.1 upstream) (2.1.3 maverick)
  • Revision ID: james.westby@ubuntu.com-20110502193431-xd7eeb4sarnmyd7e
Tags: 1.9-1
http://bugs.debian.org/513573
http://bugs.debian.org/621530
http://bugs.debian.org/625158
http://bugs.debian.org/534529
http://bugs.debian.org/517180
* Acknowledge 1.3-1.1 NMU (thanks to Michael Banck) and resynch with
  Ubuntu release (thanks Bhavani Shankar).
* New upstream release:
  - patch from 1.3-1.1ubuntu1 no longer needed.
  - new manpage for pahole.
  - new program scncopy to copy ELF sections.
  - fixes crash when encountering a pointer in a struct. Closes: #513573.
  - recognizes C++ classes. Closes: #621530.
  - no longer FTBFS with gcc 4.6. Closes: #625158.
* Remove libebl detection and use. Closes: #534529.
* debian/control:
  - bump debhelper level to 7.
  - add Vcs-Git: and Vcs-Browser:
  - bump Standards-Version: to 3.9.2.
  - add zlib1g-dev build dependency.
* debian/copyright: add missing copyright holders.
* debian/rules:
  - allow to be compiled twice in a row.
  - ensure package building aborts if a program is not installed.
  - use dh_prep instead of dh_clean -k.
* debian/dwarves.install:
  - include syscse. Closes: #517180.
  - add ctracer. See README.ctracer for information on how to use it.
* Switch to dpkg-source 3.0 (quilt) format.
* Fix many lintian warnings.

Show diffs side-by-side

added added

removed removed

Lines of Context:
hash.h
 
1
#ifndef _LINUX_HASH_H
 
2
#define _LINUX_HASH_H
 
3
/* Fast hashing routine for ints,  longs and pointers.
 
4
   (C) 2002 William Lee Irwin III, IBM */
 
5
 
 
6
/*
 
7
 * Knuth recommends primes in approximately golden ratio to the maximum
 
8
 * integer representable by a machine word for multiplicative hashing.
 
9
 * Chuck Lever verified the effectiveness of this technique:
 
10
 * http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf
 
11
 *
 
12
 * These primes are chosen to be bit-sparse, that is operations on
 
13
 * them can use shifts and additions instead of multiplications for
 
14
 * machines where multiplications are slow.
 
15
 */
 
16
 
 
17
#include <stdint.h>
 
18
 
 
19
/* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */
 
20
#define GOLDEN_RATIO_PRIME_32 0x9e370001UL
 
21
/*  2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */
 
22
#define GOLDEN_RATIO_PRIME_64 0x9e37fffffffc0001UL
 
23
 
 
24
#if __WORDSIZE == 32
 
25
#define GOLDEN_RATIO_PRIME GOLDEN_RATIO_PRIME_32
 
26
#define hash_long(val, bits) hash_32(val, bits)
 
27
#elif __WORDSIZE == 64
 
28
#define hash_long(val, bits) hash_64(val, bits)
 
29
#define GOLDEN_RATIO_PRIME GOLDEN_RATIO_PRIME_64
 
30
#else
 
31
#error Wordsize not 32 or 64
 
32
#endif
 
33
 
 
34
static inline uint64_t hash_64(const uint64_t val, const unsigned int bits)
 
35
{
 
36
        uint64_t hash = val;
 
37
 
 
38
        /*  Sigh, gcc can't optimise this alone like it does for 32 bits. */
 
39
        uint64_t n = hash;
 
40
        n <<= 18;
 
41
        hash -= n;
 
42
        n <<= 33;
 
43
        hash -= n;
 
44
        n <<= 3;
 
45
        hash += n;
 
46
        n <<= 3;
 
47
        hash -= n;
 
48
        n <<= 4;
 
49
        hash += n;
 
50
        n <<= 2;
 
51
        hash += n;
 
52
 
 
53
        /* High bits are more random, so use them. */
 
54
        return hash >> (64 - bits);
 
55
}
 
56
 
 
57
static inline uint32_t hash_32(uint32_t val, unsigned int bits)
 
58
{
 
59
        /* On some cpus multiply is faster, on others gcc will do shifts */
 
60
        uint32_t hash = val * GOLDEN_RATIO_PRIME_32;
 
61
 
 
62
        /* High bits are more random, so use them. */
 
63
        return hash >> (32 - bits);
 
64
}
 
65
 
 
66
static inline unsigned long hash_ptr(void *ptr, unsigned int bits)
 
67
{
 
68
        return hash_long((unsigned long)ptr, bits);
 
69
}
 
70
#endif /* _LINUX_HASH_H */