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 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  */
  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  */
  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  */
  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  */
  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