pintos-os.org Git - pspp/blob - src/libpspp/hash-functions.c

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 1997-9, 2000, 2008 Free Software Foundation, Inc.
   3
   4    This program is free software: you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation, either version 3 of the License, or
   7    (at your option) any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program.  If not, see <http://www.gnu.org/licenses/>. */
  16
  17 #include <config.h>
  18 #include <libpspp/hash-functions.h>
  19 #include <assert.h>
  20 #include <ctype.h>
  21 #include <math.h>
  22
  23 /* Fowler-Noll-Vo hash constants, for 32-bit word sizes. */
  24 #define FNV_32_PRIME 16777619u
  25 #define FNV_32_BASIS 2166136261u
  26
  27 /* Fowler-Noll-Vo 32-bit hash, for bytes. */
  28 unsigned
  29 hsh_hash_bytes (const void *buf_, size_t size)
  30 {
  31   const unsigned char *buf = (const unsigned char *) buf_;
  32   unsigned hash;
  33
  34   assert (buf != NULL);
  35
  36   hash = FNV_32_BASIS;
  37   while (size-- > 0)
  38     hash = (hash * FNV_32_PRIME) ^ *buf++;
  39
  40   return hash;
  41 }
  42
  43 /* Fowler-Noll-Vo 32-bit hash, for strings. */
  44 unsigned
  45 hsh_hash_string (const char *s_)
  46 {
  47   const unsigned char *s = (const unsigned char *) s_;
  48   unsigned hash;
  49
  50   assert (s != NULL);
  51
  52   hash = FNV_32_BASIS;
  53   while (*s != '\0')
  54     hash = (hash * FNV_32_PRIME) ^ *s++;
  55
  56   return hash;
  57 }
  58
  59 /* Fowler-Noll-Vo 32-bit hash, for case-insensitive strings. */
  60 unsigned
  61 hsh_hash_case_string (const char *s_)
  62 {
  63   const unsigned char *s = (const unsigned char *) s_;
  64   unsigned hash;
  65
  66   assert (s != NULL);
  67
  68   hash = FNV_32_BASIS;
  69   while (*s != '\0')
  70     hash = (hash * FNV_32_PRIME) ^ toupper (*s++);
  71
  72   return hash;
  73 }
  74
  75 /* Hash for ints. */
  76 unsigned
  77 hsh_hash_int (int i)
  78 {
  79   return hsh_hash_bytes (&i, sizeof i);
  80 }
  81
  82 /* Hash for double. */
  83 unsigned
  84 hsh_hash_double (double d)
  85 {
  86   if (!isnan (d))
  87     return hsh_hash_bytes (&d, sizeof d);
  88   else
  89     return 0;
  90 }