Graphviz  2.41.20170921.2350
dtstrhash.c
Go to the documentation of this file.
1 #include "dthdr.h"
2 
3 /* Hashing a string into an unsigned integer.
4 ** The basic method is to continuingly accumulate bytes and multiply
5 ** with some given prime. The length n of the string is added last.
6 ** The recurrent equation is like this:
7 ** h[k] = (h[k-1] + bytes)*prime for 0 <= k < n
8 ** h[n] = (h[n-1] + n)*prime
9 ** The prime is chosen to have a good distribution of 1-bits so that
10 ** the multiplication will distribute the bits in the accumulator well.
11 ** The below code accumulates 2 bytes at a time for speed.
12 **
13 ** Written by Kiem-Phong Vo (02/28/03)
14 */
15 
16 uint dtstrhash(reg uint h, void* args, reg int n)
17 {
18  reg unsigned char* s = (unsigned char*)args;
19 
20  if(n <= 0)
21  { for(; *s != 0; s += s[1] ? 2 : 1)
22  h = (h + (s[0]<<8) + s[1])*DT_PRIME;
23  n = s - (unsigned char*)args;
24  }
25  else
26  { reg unsigned char* ends;
27  for(ends = s+n-1; s < ends; s += 2)
28  h = (h + (s[0]<<8) + s[1])*DT_PRIME;
29  if(s <= ends)
30  h = (h + (s[0]<<8))*DT_PRIME;
31  }
32  return (h+n)*DT_PRIME;
33 }
#define uint
Definition: dthdr.h:15
CDT_API unsigned int dtstrhash(unsigned int, void *, int)
#define reg
Definition: dthdr.h:14
Definition: grammar.c:79
#define DT_PRIME
Definition: cdt.h:270