src/cstringHash.c

   1 /*
   2 ** Splint - annotation-assisted static program checker
   3 ** Copyright (C) 1994-2003 University of Virginia,
   4 **         Massachusetts Institute of Technology
   5 **
   6 ** This program is free software; you can redistribute it and/or modify it
   7 ** under the terms of the GNU General Public License as published by the
   8 ** Free Software Foundation; either version 2 of the License, or (at your
   9 ** option) any later version.
  10 **
  11 ** This program is distributed in the hope that it will be useful, but
  12 ** WITHOUT ANY WARRANTY; without even the implied warranty of
  13 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 ** General Public License for more details.
  15 **
  16 ** The GNU General Public License is available from http://www.gnu.org/ or
  17 ** the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  18 ** MA 02111-1307, USA.
  19 **
  20 ** For information on splint: info@splint.org
  21 ** To report a bug: splint-bug@splint.org
  22 ** For more information: http://www.splint.org
  23 */
  24 /*
  25 ** cstringHash.c
  26 */
  27
  28 # include "splintMacros.nf"
  29 # include "basic.h"
  30 # include "cstringHash.h"
  31
  32 /*@constant int NUM_RANDOM=256@*/
  33 # define NUM_RANDOM 256
  34
  35 /*@+ignoresigns@*/
  36 static const unsigned int
  37 g_randomNumbers[NUM_RANDOM] = {
  38   0x7be9c1bd,
  39   0x088aa102,
  40   0x3d38509b,
  41   0x746b9fbe,
  42   0x2d04417f,
  43   0x775d4351,
  44   0x53c48d96,
  45   0x02b26e0b,
  46   0x418fedcf,
  47   0x19dbc19e,
  48   0x78512adb,
  49   0x1a1f5e2b,
  50   0x307d7761,
  51   0x6584c1f0,
  52   0x24e3c36f,
  53   0x2232310f,
  54   0x2dac5ceb,
  55   0x106e8b5a,
  56   0x5a05a938,
  57   0x5e6392b6,
  58   0x66b90348,
  59   0x75264901,
  60   0x4174f402,
  61   0x618b18a4,
  62   0x3a6ab4bf,
  63   0x3c4bc289,
  64   0x2657a9a9,
  65   0x4e68589b,
  66   0x09648aa6,
  67   0x3fc489bb,
  68   0x1c1b715c,
  69   0x054e4c63,
  70   0x484f2abd,
  71   0x5953c1f8,
  72   0x79b9ec22,
  73   0x75536c3d,
  74   0x50b10549,
  75   0x4d7e79b8,
  76   0x7805da48,
  77   0x1240f318,
  78   0x675a3b56,
  79   0x70570523,
  80   0x2c605143,
  81   0x17d7b2b7,
  82   0x55dbc713,
  83   0x514414b2,
  84   0x3a09e3c7,
  85   0x038823ff,
  86   0x61b2a00c,
  87   0x140f8cff,
  88   0x61ebb6b5,
  89   0x486ba354,
  90   0x0935d600,
  91   0x2360aab8,
  92   0x29f6bbf8,
  93   0x43a08abf,
  94   0x5fac6d41,
  95   0x504e65a2,
  96   0x1208e35b,
  97   0x6910f7e7,
  98   0x1012ef5d,
  99   0x2e2454b7,
 100   0x6e5f444b,
 101   0x58621a1b,
 102   0x077816af,
 103   0x6819306d,
 104   0x4db58658,
 105   0x58291bf8,
 106   0x3597aa25,
 107   0x45bb60a0,
 108   0x6a6a0f11,
 109   0x1cf1e57c,
 110   0x361265c4,
 111   0x16ca6054,
 112   0x34c99833,
 113   0x0bee2cd7,
 114   0x680e7507,
 115   0x6ed37bfa,
 116   0x0f7650d6,
 117   0x49c11513,
 118   0x02e308f9,
 119   0x7162078c,
 120   0x122cb868,
 121   0x0c18defa,
 122   0x14c2b244,
 123   0x3c237460,
 124   0x4fb969b9,
 125   0x746f1f85,
 126   0x0c71da02,
 127   0x61c24d14,
 128   0x5d80176d,
 129   0x1c84c960,
 130   0x0fe6a1cc,
 131   0x4bdf5bb8,
 132   0x74e6e37b,
 133   0x175eb87b,
 134   0x33f88c25,
 135   0x429c69d3,
 136   0x6f87d474,
 137   0x6990364a,
 138   0x0857ca73,
 139   0x59f1e385,
 140   0x06821bc6,
 141   0x3e6a3037,
 142   0x70bc43d9,
 143   0x3b4bb3fa,
 144   0x4a585d0f,
 145   0x58cab8e0,
 146   0x2a1f2ff4,
 147   0x59ceade5,
 148   0x228bcdf4,
 149   0x2d0238ee,
 150   0x4b30b571,
 151   0x34b8865c,
 152   0x391b17e8,
 153   0x5ff367b5,
 154   0x70dbfabc,
 155   0x08d481a1,
 156   0x5462873b,
 157   0x7d4dd4bf,
 158   0x6a96ceb6,
 159   0x31e29ea8,
 160   0x19d29e1f,
 161   0x7a7d7082,
 162   0x7dc1fa60,
 163   0x0eb9819a,
 164   0x11dc28fd,
 165   0x31ba8685,
 166   0x5155eb6d,
 167   0x0163fd71,
 168   0x1b4abccf,
 169   0x59adb5e0,
 170   0x5b55e0f6,
 171   0x21ccd896,
 172   0x1817e618,
 173   0x4c1224d0,
 174   0x5d188c90,
 175   0x62704327,
 176   0x24dcddb0,
 177   0x0737bc84,
 178   0x3c3ef10c,
 179   0x4768aba4,
 180   0x3439f572,
 181   0x076fa67e,
 182   0x7c213200,
 183   0x6d550d5a,
 184   0x67630e33,
 185   0x6cfd2cbd,
 186   0x76298efc,
 187   0x3bc5956e,
 188   0x6a4b017c,
 189   0x60c05db2,
 190   0x6da83416,
 191   0x041d9f9b,
 192   0x5b3dce34,
 193   0x6b6a2e76,
 194   0x12d72135,
 195   0x6d19f731,
 196   0x1d24b4fb,
 197   0x642d0ca2,
 198   0x6e7df4a3,
 199   0x386f71cb,
 200   0x3ddac282,
 201   0x49d3d599,
 202   0x5a3c4a61,
 203   0x55f2a89a,
 204   0x15e5fa69,
 205   0x3754d6f1,
 206   0x3862ebc1,
 207   0x3ac2d81a,
 208   0x3e8c9375,
 209   0x74a1dcce,
 210   0x022b83be,
 211   0x72c688e8,
 212   0x7c11834c,
 213   0x7e4cb5bf,
 214   0x601b9642,
 215   0x6374917f,
 216   0x6b49e27c,
 217   0x5645253e,
 218   0x1f3a26ee,
 219   0x5594e3f8,
 220   0x370582f0,
 221   0x0ce25b04,
 222   0x59b28393,
 223   0x12435124,
 224   0x784c897b,
 225   0x6c89a4c8,
 226   0x7f5d4856,
 227   0x15713e76,
 228   0x50b6b16a,
 229   0x6ddb3cf9,
 230   0x4de0b041,
 231   0x0e9173ec,
 232   0x37af1292,
 233   0x281cfaa2,
 234   0x64841c87,
 235   0x4d950cfc,
 236   0x5f71d193,
 237   0x1ce70848,
 238   0x0857e516,
 239   0x1dfe6509,
 240   0x1188e516,
 241   0x0a8368d4,
 242   0x10c4edf1,
 243   0x0d9a6862,
 244   0x08d01e93,
 245   0x70e08433,
 246   0x710ef9e2,
 247   0x741a010f,
 248   0x4725a972,
 249   0x104920d0,
 250   0x49aee507,
 251   0x7e2b2c62,
 252   0x1d2b7bd4,
 253   0x2361689a,
 254   0x106e7d87,
 255   0x1578054f,
 256   0x0feb0d62,
 257   0x0fcbc5dd,
 258   0x2ae943c6,
 259   0x60a1becc,
 260   0x7da702d6,
 261   0x78c9f407,
 262   0x6f3332b9,
 263   0x35561568,
 264   0x20e6eeaa,
 265   0x53b74f40,
 266   0x02eb2264,
 267   0x0058c03d,
 268   0x709e5788,
 269   0x0b43077a,
 270   0x1e572546,
 271   0x02273c9f,
 272   0x15c6704f,
 273   0x2f1c1337,
 274   0x0fc1a501,
 275   0x1e968ee2,
 276   0x1ffc976b,
 277   0x00d09ee3,
 278   0x12b08ff2,
 279   0x672240dd,
 280   0x1119bfb3,
 281   0x5c5f74f9,
 282   0x654d6d3f,
 283   0x2e453b88,
 284   0x7fc0dd94,
 285   0x75bbeac6,
 286   0x43bd40d7,
 287   0x0fabeaf6,
 288   0x0587b0a3,
 289   0x6ea6849d,
 290   0x704da9c3,
 291   0x032eb379,
 292   0x677078a5,
 293   0x5f80dc7c
 294 } ;
 295 /*@=ignoresigns@*/
 296
 297 /*
 298 ** hash function snarfed from quake/hash.c Hash_String
 299 ** by Stephen Harrison
 300 */
 301
 302 unsigned int
 303 cstring_hashValue (cstring key)
 304 {
 305   char *p;
 306   unsigned int hash_value = 0;
 307
 308   for (p = cstring_toCharsSafe (key); *p != '\0'; p++)
 309     {
 310       hash_value = (hash_value << 1) ^ g_randomNumbers[*p % NUM_RANDOM];
 311     }
 312
 313   return hash_value;
 314 }
 315