blob: aa236cbb0054d0f56f4c5950d5bb7591fe068917 [file] [log] [blame]
Bhaskar98634f02013-10-29 23:30:51 -04001/*
2 * Hash function implementation
3 *
4 * See mailing list thread on "Consistent hashing alternative to sdbm"
5 * http://marc.info/?l=haproxy&m=138213693909219
6 *
7 * Copyright 2000-2010 Willy Tarreau <w@1wt.eu>
8 *
9 * This program is free software; you can redistribute it and/or
10 * modify it under the terms of the GNU General Public License
11 * as published by the Free Software Foundation; either version
12 * 2 of the License, or (at your option) any later version.
13 *
14 */
15
16
17#include <common/hash.h>
18
19
Dan Dubovikbd57a9f2014-07-08 08:51:03 -070020unsigned int hash_wt6(const char *key, int len)
Willy Tarreaua0f42712013-11-14 14:30:35 +010021{
22 unsigned h0 = 0xa53c965aUL;
23 unsigned h1 = 0x5ca6953aUL;
24 unsigned step0 = 6;
25 unsigned step1 = 18;
26
27 for (; len > 0; len--) {
28 unsigned int t;
29
30 t = ((unsigned int)*key);
31 key++;
32
33 h0 = ~(h0 ^ t);
34 h1 = ~(h1 + t);
35
36 t = (h1 << step0) | (h1 >> (32-step0));
37 h1 = (h0 << step1) | (h0 >> (32-step1));
38 h0 = t;
39
40 t = ((h0 >> 16) ^ h1) & 0xffff;
41 step0 = t & 0x1F;
42 step1 = t >> 11;
43 }
44 return h0 ^ h1;
45}
46
Dan Dubovikbd57a9f2014-07-08 08:51:03 -070047unsigned int hash_djb2(const char *key, int len)
Bhaskar98634f02013-10-29 23:30:51 -040048{
Dan Dubovikbd57a9f2014-07-08 08:51:03 -070049 unsigned int hash = 5381;
Bhaskar98634f02013-10-29 23:30:51 -040050
51 /* the hash unrolled eight times */
52 for (; len >= 8; len -= 8) {
53 hash = ((hash << 5) + hash) + *key++;
54 hash = ((hash << 5) + hash) + *key++;
55 hash = ((hash << 5) + hash) + *key++;
56 hash = ((hash << 5) + hash) + *key++;
57 hash = ((hash << 5) + hash) + *key++;
58 hash = ((hash << 5) + hash) + *key++;
59 hash = ((hash << 5) + hash) + *key++;
60 hash = ((hash << 5) + hash) + *key++;
61 }
62 switch (len) {
63 case 7: hash = ((hash << 5) + hash) + *key++; /* fallthrough... */
64 case 6: hash = ((hash << 5) + hash) + *key++; /* fallthrough... */
65 case 5: hash = ((hash << 5) + hash) + *key++; /* fallthrough... */
66 case 4: hash = ((hash << 5) + hash) + *key++; /* fallthrough... */
67 case 3: hash = ((hash << 5) + hash) + *key++; /* fallthrough... */
68 case 2: hash = ((hash << 5) + hash) + *key++; /* fallthrough... */
69 case 1: hash = ((hash << 5) + hash) + *key++; break;
70 default: /* case 0: */ break;
71 }
72 return hash;
73}
74
Dan Dubovikbd57a9f2014-07-08 08:51:03 -070075unsigned int hash_sdbm(const char *key, int len)
Bhaskar98634f02013-10-29 23:30:51 -040076{
Dan Dubovikbd57a9f2014-07-08 08:51:03 -070077 unsigned int hash = 0;
Bhaskar98634f02013-10-29 23:30:51 -040078 int c;
79
80 while (len--) {
81 c = *key++;
82 hash = c + (hash << 6) + (hash << 16) - hash;
83 }
84
85 return hash;
86}
87
88