1 /*
2  * Copyright (C) 1995-2011 University of Karlsruhe.  All right reserved.
3  *
4  * This file is part of libFirm.
5  *
6  * This file may be distributed and/or modified under the terms of the
7  * GNU General Public License version 2 as published by the Free Software
8  * Foundation and appearing in the file LICENSE.GPL included in the
9  * packaging of this file.
10  *
11  * Licensees holding valid libFirm Professional Edition licenses may use
12  * this file in accordance with the libFirm Commercial License.
13  * Agreement provided with the Software.
14  *
15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
17  * PURPOSE.
18  */
19 
20 /**
21  * @file
22  * @brief       Hash functions
23  * @author      Michael Beck, Sebastian Hack
24  */
25 #ifndef FIRM_ADT_HASHPTR_H
26 #define FIRM_ADT_HASHPTR_H
27 
28 #include <stdlib.h>
29 #include "../begin.h"
30 
31 /**
32  * @ingroup algorithms
33  * @defgroup hashptr Hash Functions
34  * @{
35  */
36 
37 /** @cond DISABLED */
38 
39 #define _FIRM_FNV_OFFSET_BASIS 2166136261U
40 #define _FIRM_FNV_FNV_PRIME 16777619U
41 
42 /* Computing x * _FIRM_FNV_FNV_PRIME */
43 #define _FIRM_FNV_TIMES_PRIME(x) ((x) * _FIRM_FNV_FNV_PRIME)
44 
45 /** @endcond */
46 
47 /**
48  * Returns a hash value for a block of data.
49  */
hash_data(const unsigned char * data,size_t bytes)50 static inline unsigned hash_data(const unsigned char *data, size_t bytes)
51 {
52 	size_t   i;
53 	unsigned hash = _FIRM_FNV_OFFSET_BASIS;
54 
55 	for(i = 0; i < bytes; ++i) {
56 		hash = _FIRM_FNV_TIMES_PRIME(hash);
57 		hash ^= data[i];
58 	}
59 
60 	return hash;
61 }
62 
63 /**
64  * Returns a hash value for a string.
65  * @param str The string (can be const).
66  * @return A hash value for the string.
67  */
hash_str(const char * str)68 static inline unsigned hash_str(const char *str)
69 {
70 	unsigned i;
71 	unsigned hash = _FIRM_FNV_OFFSET_BASIS;
72 
73 	for(i = 0; str[i] != '\0'; ++i) {
74 		hash = _FIRM_FNV_TIMES_PRIME(hash);
75 		hash ^= str[i];
76 	}
77 
78 	return hash;
79 }
80 
81 /**
82  * Returns a hash value for a pointer.
83  * Pointer addresses are mostly aligned to 4 or 8 bytes. So we remove the
84  * lowest 3 bits.
85  */
hash_ptr(const void * ptr)86 static inline unsigned hash_ptr(const void *ptr)
87 {
88 	return ((unsigned)(((char *) (ptr) - (char *)0) >> 3));
89 }
90 
91 /**
92  * Combines 2 hash values.
93  * @param x One hash value.
94  * @param y Another hash value.
95  * @return  A hash value computed from both.
96  */
hash_combine(unsigned x,unsigned y)97 static inline unsigned hash_combine(unsigned x, unsigned y)
98 {
99 	unsigned hash = _FIRM_FNV_TIMES_PRIME(_FIRM_FNV_OFFSET_BASIS);
100 	hash ^= x;
101 	hash  = _FIRM_FNV_TIMES_PRIME(hash);
102 	hash ^= y;
103 	return hash;
104 }
105 
106 /** @} */
107 
108 #include "../end.h"
109 
110 #endif
111