gcc/inchash.h

   1 /* An incremental hash abstract data type.
   2    Copyright (C) 2014-2015 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify it under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 3, or (at your option) any later
   9 version.
  10
  11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 #ifndef INCHASH_H
  21 #define INCHASH_H 1
  22
  23 #include "hashtab.h"
  24
  25 /* This file implements an incremential hash function ADT, to be used
  26    by code that incrementially hashes a lot of unrelated data
  27    (not in a single memory block) into a single value. The goal
  28    is to make it easy to plug in efficient hash algorithms.
  29    Currently it just implements the plain old jhash based
  30    incremental hash from gcc's tree.c.  */
  31
  32 hashval_t iterative_hash_host_wide_int (HOST_WIDE_INT, hashval_t);
  33 hashval_t iterative_hash_hashval_t (hashval_t, hashval_t);
  34
  35 namespace inchash
  36 {
  37
  38 class hash
  39 {
  40  public:
  41
  42   /* Start incremential hashing, optionally with SEED.  */
  43   hash (hashval_t seed = 0)
  44   {
  45     val = seed;
  46     bits = 0;
  47   }
  48
  49   /* End incremential hashing and provide the final value.  */
  50   hashval_t end ()
  51   {
  52     return val;
  53   }
  54
  55   /* Add unsigned value V.  */
  56   void add_int (unsigned v)
  57   {
  58     val = iterative_hash_hashval_t (v, val);
  59   }
  60
  61   /* Add HOST_WIDE_INT value V.  */
  62   void add_wide_int (HOST_WIDE_INT v)
  63   {
  64     val = iterative_hash_host_wide_int (v, val);
  65   }
  66
  67   /* Hash in pointer PTR.  */
  68   void add_ptr (const void *ptr)
  69   {
  70     add (&ptr, sizeof (ptr));
  71   }
  72
  73   /* Add a memory block DATA with size LEN.  */
  74   void add (const void *data, size_t len)
  75   {
  76     val = iterative_hash (data, len, val);
  77   }
  78
  79   /* Merge hash value OTHER.  */
  80   void merge_hash (hashval_t other)
  81   {
  82     val = iterative_hash_hashval_t (other, val);
  83   }
  84
  85   /* Hash in state from other inchash OTHER.  */
  86   void merge (hash &other)
  87   {
  88     merge_hash (other.val);
  89   }
  90
  91   template<class T> void add_object(T &obj)
  92   {
  93     add (&obj, sizeof(T));
  94   }
  95
  96   /* Support for accumulating boolean flags */
  97
  98   void add_flag (bool flag)
  99   {
 100     bits = (bits << 1) | flag;
 101   }
 102
 103   void commit_flag ()
 104   {
 105     add_int (bits);
 106     bits = 0;
 107   }
 108
 109   /* Support for commutative hashing. Add A and B in a defined order
 110      based on their value. This is useful for hashing commutative
 111      expressions, so that A+B and B+A get the same hash.  */
 112
 113   void add_commutative (hash &a, hash &b)
 114   {
 115     if (a.end() > b.end())
 116       {
 117         merge (b);
 118         merge (a);
 119       }
 120     else
 121       {
 122         merge (a);
 123         merge (b);
 124       }
 125   }
 126
 127  private:
 128   hashval_t val;
 129   unsigned bits;
 130 };
 131
 132 }
 133
 134 /* Borrowed from hashtab.c iterative_hash implementation.  */
 135 #define mix(a,b,c) \
 136 { \
 137   a -= b; a -= c; a ^= (c>>13); \
 138   b -= c; b -= a; b ^= (a<< 8); \
 139   c -= a; c -= b; c ^= ((b&0xffffffff)>>13); \
 140   a -= b; a -= c; a ^= ((c&0xffffffff)>>12); \
 141   b -= c; b -= a; b = (b ^ (a<<16)) & 0xffffffff; \
 142   c -= a; c -= b; c = (c ^ (b>> 5)) & 0xffffffff; \
 143   a -= b; a -= c; a = (a ^ (c>> 3)) & 0xffffffff; \
 144   b -= c; b -= a; b = (b ^ (a<<10)) & 0xffffffff; \
 145   c -= a; c -= b; c = (c ^ (b>>15)) & 0xffffffff; \
 146 }
 147
 148
 149 /* Produce good hash value combining VAL and VAL2.  */
 150 inline
 151 hashval_t
 152 iterative_hash_hashval_t (hashval_t val, hashval_t val2)
 153 {
 154   /* the golden ratio; an arbitrary value.  */
 155   hashval_t a = 0x9e3779b9;
 156
 157   mix (a, val, val2);
 158   return val2;
 159 }
 160
 161 /* Produce good hash value combining VAL and VAL2.  */
 162
 163 inline
 164 hashval_t
 165 iterative_hash_host_wide_int (HOST_WIDE_INT val, hashval_t val2)
 166 {
 167   if (sizeof (HOST_WIDE_INT) == sizeof (hashval_t))
 168     return iterative_hash_hashval_t (val, val2);
 169   else
 170     {
 171       hashval_t a = (hashval_t) val;
 172       /* Avoid warnings about shifting of more than the width of the type on
 173          hosts that won't execute this path.  */
 174       int zero = 0;
 175       hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 8 + zero));
 176       mix (a, b, val2);
 177       if (sizeof (HOST_WIDE_INT) > 2 * sizeof (hashval_t))
 178         {
 179           hashval_t a = (hashval_t) (val >> (sizeof (hashval_t) * 16 + zero));
 180           hashval_t b = (hashval_t) (val >> (sizeof (hashval_t) * 24 + zero));
 181           mix (a, b, val2);
 182         }
 183       return val2;
 184     }
 185 }
 186
 187 #endif