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)50static 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)68static 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)86static 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)97static 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