hashptr.h 2.57 KB
Newer Older
1
/*
2
 * Copyright (C) 1995-2011 University of Karlsruhe.  All right reserved.
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 *
 * This file is part of libFirm.
 *
 * This file may be distributed and/or modified under the terms of the
 * GNU General Public License version 2 as published by the Free Software
 * Foundation and appearing in the file LICENSE.GPL included in the
 * packaging of this file.
 *
 * Licensees holding valid libFirm Professional Edition licenses may use
 * this file in accordance with the libFirm Commercial License.
 * Agreement provided with the Software.
 *
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE.
18
 */
19
20
21
22
23
24
25
26
27

/**
 * @file
 * @brief       Hash function for pointers
 * @author      Michael Beck, Sebastian Hack
 * @version     $Id$
 */
#ifndef FIRM_ADT_HASHPTR_H
#define FIRM_ADT_HASHPTR_H
28

29
30
#include "../begin.h"

Götz Lindenmaier's avatar
Götz Lindenmaier committed
31
32
#define _FIRM_FNV_OFFSET_BASIS 2166136261U
#define _FIRM_FNV_FNV_PRIME 16777619U
33

34
/* Computing x * _FIRM_FNV_FNV_PRIME */
Sebastian Hack's avatar
Sebastian Hack committed
35
#define _FIRM_FNV_TIMES_PRIME(x) ((x) * _FIRM_FNV_FNV_PRIME)
36

37
static inline unsigned firm_fnv_hash(const unsigned char *data, size_t bytes)
38
{
39
	size_t   i;
40
41
42
	unsigned hash = _FIRM_FNV_OFFSET_BASIS;

	for(i = 0; i < bytes; ++i) {
43
		hash = _FIRM_FNV_TIMES_PRIME(hash);
Sebastian Hack's avatar
Sebastian Hack committed
44
45
46
47
48
49
		hash ^= data[i];
	}

	return hash;
}

50
static inline unsigned firm_fnv_hash_str(const char *data)
Sebastian Hack's avatar
Sebastian Hack committed
51
52
53
54
55
56
{
	unsigned i;
	unsigned hash = _FIRM_FNV_OFFSET_BASIS;

	for(i = 0; data[i] != '\0'; ++i) {
		hash = _FIRM_FNV_TIMES_PRIME(hash);
57
58
59
60
61
62
		hash ^= data[i];
	}

	return hash;
}

63
64
65
66
/**
 * hash a pointer value: Pointer addresses are mostly aligned to 4
 * or 8 bytes. So we remove the lowest 3 bits
 */
67
#define HASH_PTR(ptr)    ((unsigned)(((char *) (ptr) - (char *)0) >> 3))
68

69
70
71
72
73
static inline unsigned hash_ptr(const void *ptr)
{
	return HASH_PTR(ptr);
}

74
75
76
77
78
79
80
/**
 * Hash a string.
 * @param str The string (can be const).
 * @param len The length of the string.
 * @return A hash value for the string.
 */
#define HASH_STR(str,len) firm_fnv_hash((const unsigned char *) (str), (len))
81

82
83
#ifdef _MSC_VER
#pragma warning(disable:4307)
FIRM Projekt Account's avatar
FIRM Projekt Account committed
84
#endif /* _MSC_VER */
85

86
static inline unsigned _hash_combine(unsigned x, unsigned y)
87
{
88
89
90
91
92
	unsigned hash = _FIRM_FNV_TIMES_PRIME(_FIRM_FNV_OFFSET_BASIS);
	hash ^= x;
	hash  = _FIRM_FNV_TIMES_PRIME(hash);
	hash ^= y;
	return hash;
93
94
}

95
96
#ifdef _MSC_VER
#pragma warning(default:4307)
FIRM Projekt Account's avatar
FIRM Projekt Account committed
97
#endif /* _MSC_VER */
98

99
100
101
102
103
104
105
106
/**
 * Make one hash value out of two others.
 * @param a One hash value.
 * @param b Another hash value.
 * @return A hash value computed from the both.
 */
#define HASH_COMBINE(a,b) _hash_combine(a, b)

107
108
#include "../end.h"

109
#endif