nsz Git - libfirm/blob - include/libfirm/adt/hashptr.h

   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 function for pointers
  23  * @author      Michael Beck, Sebastian Hack
  24  * @version     $Id$
  25  */
  26 #ifndef FIRM_ADT_HASHPTR_H
  27 #define FIRM_ADT_HASHPTR_H
  28
  29 #include <stdlib.h>
  30 #include "../begin.h"
  31
  32 #define _FIRM_FNV_OFFSET_BASIS 2166136261U
  33 #define _FIRM_FNV_FNV_PRIME 16777619U
  34
  35 /* Computing x * _FIRM_FNV_FNV_PRIME */
  36 #define _FIRM_FNV_TIMES_PRIME(x) ((x) * _FIRM_FNV_FNV_PRIME)
  37
  38 static inline unsigned firm_fnv_hash(const unsigned char *data, size_t bytes)
  39 {
  40         size_t   i;
  41         unsigned hash = _FIRM_FNV_OFFSET_BASIS;
  42
  43         for(i = 0; i < bytes; ++i) {
  44                 hash = _FIRM_FNV_TIMES_PRIME(hash);
  45                 hash ^= data[i];
  46         }
  47
  48         return hash;
  49 }
  50
  51 static inline unsigned firm_fnv_hash_str(const char *data)
  52 {
  53         unsigned i;
  54         unsigned hash = _FIRM_FNV_OFFSET_BASIS;
  55
  56         for(i = 0; data[i] != '\0'; ++i) {
  57                 hash = _FIRM_FNV_TIMES_PRIME(hash);
  58                 hash ^= data[i];
  59         }
  60
  61         return hash;
  62 }
  63
  64 /**
  65  * hash a pointer value: Pointer addresses are mostly aligned to 4
  66  * or 8 bytes. So we remove the lowest 3 bits
  67  */
  68 #define HASH_PTR(ptr)    ((unsigned)(((char *) (ptr) - (char *)0) >> 3))
  69
  70 static inline unsigned hash_ptr(const void *ptr)
  71 {
  72         return HASH_PTR(ptr);
  73 }
  74
  75 /**
  76  * Hash a string.
  77  * @param str The string (can be const).
  78  * @param len The length of the string.
  79  * @return A hash value for the string.
  80  */
  81 #define HASH_STR(str,len) firm_fnv_hash((const unsigned char *) (str), (len))
  82
  83 #ifdef _MSC_VER
  84 #pragma warning(disable:4307)
  85 #endif /* _MSC_VER */
  86
  87 static inline unsigned _hash_combine(unsigned x, unsigned y)
  88 {
  89         unsigned hash = _FIRM_FNV_TIMES_PRIME(_FIRM_FNV_OFFSET_BASIS);
  90         hash ^= x;
  91         hash  = _FIRM_FNV_TIMES_PRIME(hash);
  92         hash ^= y;
  93         return hash;
  94 }
  95
  96 #ifdef _MSC_VER
  97 #pragma warning(default:4307)
  98 #endif /* _MSC_VER */
  99
 100 /**
 101  * Make one hash value out of two others.
 102  * @param a One hash value.
 103  * @param b Another hash value.
 104  * @return A hash value computed from the both.
 105  */
 106 #define HASH_COMBINE(a,b) _hash_combine(a, b)
 107
 108 #include "../end.h"
 109
 110 #endif