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

   1 /*
   2  * Project:     libFIRM
   3  * File name:   ir/adt/hashptr.h
   4  * Purpose:     Hash function for pointers
   5  * Author:      Michael Beck, Sebastian Hack
   6  * Modified by:
   7  * Created:     2004
   8  * CVS-ID:      $Id$
   9  * Copyright:   (C) 2004 University of Karlsruhe
  10  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  11  */
  12 #ifndef __HASHPTR_H__
  13 #define __HASHPTR_H__
  14
  15 #include "firm_config.h"
  16
  17 #define _FIRM_FNV_OFFSET_BASIS 2166136261U
  18 #define _FIRM_FNV_FNV_PRIME 16777619U
  19
  20 /* Computing x * _FIRM_FNV_FNV_PRIME */
  21 #define _FIRM_FNV_TIMES_PRIME(x) \
  22   (((x) << 24) + ((x) << 8) + ((x) << 7) + ((x) << 4) + ((x) << 1) + 1)
  23
  24 static INLINE unsigned firm_fnv_hash(const unsigned char *data, unsigned bytes)
  25 {
  26         unsigned i;
  27         unsigned hash = _FIRM_FNV_OFFSET_BASIS;
  28
  29         for(i = 0; i < bytes; ++i) {
  30                 hash = _FIRM_FNV_TIMES_PRIME(hash);
  31                 hash ^= data[i];
  32         }
  33
  34         return hash;
  35 }
  36
  37 /**
  38  * hash a pointer value: Pointer addresses are mostly aligned to 4
  39  * or 8 bytes. So we remove the lowest 3 bits
  40  */
  41 #define HASH_PTR(ptr)    (((char *) (ptr) - (char *)0) >> 3)
  42
  43 /**
  44  * Hash a string.
  45  * @param str The string (can be const).
  46  * @param len The length of the string.
  47  * @return A hash value for the string.
  48  */
  49 #define HASH_STR(str,len) firm_fnv_hash((const unsigned char *) (str), (len))
  50
  51 #ifdef _MSC_VER
  52 #pragma warning(disable:4307)
  53 #endif /* _MSC_VER */
  54
  55 static INLINE unsigned _hash_combine(unsigned x, unsigned y)
  56 {
  57   unsigned hash = _FIRM_FNV_TIMES_PRIME(_FIRM_FNV_OFFSET_BASIS);
  58   hash ^= x;
  59   hash  = _FIRM_FNV_TIMES_PRIME(hash);
  60   hash ^= y;
  61   return hash;
  62 }
  63
  64 #ifdef _MSC_VER
  65 #pragma warning(default:4307)
  66 #endif /* _MSC_VER */
  67
  68 /**
  69  * Make one hash value out of two others.
  70  * @param a One hash value.
  71  * @param b Another hash value.
  72  * @return A hash value computed from the both.
  73  */
  74 #define HASH_COMBINE(a,b) _hash_combine(a, b)
  75
  76 #endif /* __HASHPTR_H__ */