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

   1 /*
   2  * This file is part of libFirm.
   3  * Copyright (C) 2012 University of Karlsruhe.
   4  */
   5
   6 /**
   7  * @file
   8  * @brief       Hash functions
   9  * @author      Michael Beck, Sebastian Hack
  10  */
  11 #ifndef FIRM_ADT_HASHPTR_H
  12 #define FIRM_ADT_HASHPTR_H
  13
  14 #include <stdlib.h>
  15 #include "../begin.h"
  16
  17 /**
  18  * @ingroup algorithms
  19  * @defgroup hashptr Hash Functions
  20  * @{
  21  */
  22
  23 /** @cond DISABLED */
  24
  25 #define _FIRM_FNV_OFFSET_BASIS 2166136261U
  26 #define _FIRM_FNV_FNV_PRIME 16777619U
  27
  28 /* Computing x * _FIRM_FNV_FNV_PRIME */
  29 #define _FIRM_FNV_TIMES_PRIME(x) ((x) * _FIRM_FNV_FNV_PRIME)
  30
  31 /** @endcond */
  32
  33 /**
  34  * Returns a hash value for a block of data.
  35  */
  36 static inline unsigned hash_data(const unsigned char *data, size_t bytes)
  37 {
  38         size_t   i;
  39         unsigned hash = _FIRM_FNV_OFFSET_BASIS;
  40
  41         for(i = 0; i < bytes; ++i) {
  42                 hash = _FIRM_FNV_TIMES_PRIME(hash);
  43                 hash ^= data[i];
  44         }
  45
  46         return hash;
  47 }
  48
  49 /**
  50  * Returns a hash value for a string.
  51  * @param str The string (can be const).
  52  * @return A hash value for the string.
  53  */
  54 static inline unsigned hash_str(const char *str)
  55 {
  56         unsigned i;
  57         unsigned hash = _FIRM_FNV_OFFSET_BASIS;
  58
  59         for(i = 0; str[i] != '\0'; ++i) {
  60                 hash = _FIRM_FNV_TIMES_PRIME(hash);
  61                 hash ^= str[i];
  62         }
  63
  64         return hash;
  65 }
  66
  67 /**
  68  * Returns a hash value for a pointer.
  69  * Pointer addresses are mostly aligned to 4 or 8 bytes. So we remove the
  70  * lowest 3 bits.
  71  */
  72 static inline unsigned hash_ptr(const void *ptr)
  73 {
  74         return ((unsigned)(((char *) (ptr) - (char *)0) >> 3));
  75 }
  76
  77 /**
  78  * Combines 2 hash values.
  79  * @param x One hash value.
  80  * @param y Another hash value.
  81  * @return  A hash value computed from both.
  82  */
  83 static inline unsigned hash_combine(unsigned x, unsigned y)
  84 {
  85         unsigned hash = _FIRM_FNV_TIMES_PRIME(_FIRM_FNV_OFFSET_BASIS);
  86         hash ^= x;
  87         hash  = _FIRM_FNV_TIMES_PRIME(hash);
  88         hash ^= y;
  89         return hash;
  90 }
  91
  92 /** @} */
  93
  94 #include "../end.h"
  95
  96 #endif