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  */
  25 #ifndef FIRM_ADT_HASHPTR_H
  26 #define FIRM_ADT_HASHPTR_H
  27
  28 #include <stdlib.h>
  29 #include "../begin.h"
  30
  31 #define _FIRM_FNV_OFFSET_BASIS 2166136261U
  32 #define _FIRM_FNV_FNV_PRIME 16777619U
  33
  34 /* Computing x * _FIRM_FNV_FNV_PRIME */
  35 #define _FIRM_FNV_TIMES_PRIME(x) ((x) * _FIRM_FNV_FNV_PRIME)
  36
  37 static inline unsigned hash_data(const unsigned char *data, size_t bytes)
  38 {
  39         size_t   i;
  40         unsigned hash = _FIRM_FNV_OFFSET_BASIS;
  41
  42         for(i = 0; i < bytes; ++i) {
  43                 hash = _FIRM_FNV_TIMES_PRIME(hash);
  44                 hash ^= data[i];
  45         }
  46
  47         return hash;
  48 }
  49
  50 /**
  51  * Returns a hash value for a string.
  52  * @param str The string (can be const).
  53  * @param len The length of the string.
  54  * @return A hash value for the string.
  55  */
  56 static inline unsigned hash_str(const char *data)
  57 {
  58         unsigned i;
  59         unsigned hash = _FIRM_FNV_OFFSET_BASIS;
  60
  61         for(i = 0; data[i] != '\0'; ++i) {
  62                 hash = _FIRM_FNV_TIMES_PRIME(hash);
  63                 hash ^= data[i];
  64         }
  65
  66         return hash;
  67 }
  68
  69 /**
  70  * Returns a hash value for a pointer.
  71  * Pointer addresses are mostly aligned to 4 or 8 bytes. So we remove the
  72  * lowest 3 bits.
  73  */
  74 static inline unsigned hash_ptr(const void *ptr)
  75 {
  76         return ((unsigned)(((char *) (ptr) - (char *)0) >> 3));
  77 }
  78
  79 /**
  80  * Combines 2 hash values.
  81  * @param a One hash value.
  82  * @param b Another hash value.
  83  * @return A hash value computed from both.
  84  */
  85 static inline unsigned hash_combine(unsigned x, unsigned y)
  86 {
  87         unsigned hash = _FIRM_FNV_TIMES_PRIME(_FIRM_FNV_OFFSET_BASIS);
  88         hash ^= x;
  89         hash  = _FIRM_FNV_TIMES_PRIME(hash);
  90         hash ^= y;
  91         return hash;
  92 }
  93
  94 #include "../end.h"
  95
  96 #endif