blob: 6cf11d22bf62a429d5c198c3866923f06b2f58e8 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
|
/*-------------------------------------------------------------------------
*
* hashfn.c--
*
*
* Copyright (c) 1994, Regents of the University of California
*
*
* IDENTIFICATION
* $Header: /cvsroot/pgsql/src/backend/utils/hash/hashfn.c,v 1.7 1998/02/26 04:37:51 momjian Exp $
*
*-------------------------------------------------------------------------
*/
#include <string.h>
#include "postgres.h"
#include "utils/hsearch.h"
/*
* Assume that we've already split the bucket to which this
* key hashes, calculate that bucket, and check that in fact
* we did already split it.
*/
long
string_hash(char *key, int keysize)
{
int h;
unsigned char *k = (unsigned char *) key;
h = 0;
/*
* Convert string to integer
*/
while (*k)
h = h * PRIME1 ^ (*k++ - ' ');
h %= PRIME2;
return (h);
}
long
tag_hash(int *key, int keysize)
{
long h = 0;
/*
* Convert tag to integer; Use four byte chunks in a "jump table" to
* go a little faster. Currently the maximum keysize is 16 (mar 17
* 1992) I have put in cases for up to 24. Bigger than this will
* resort to the old behavior of the for loop. (see the default case).
*/
switch (keysize)
{
case 6 * sizeof(int):
h = h * PRIME1 ^ (*key);
key++;
/* fall through */
case 5 * sizeof(int):
h = h * PRIME1 ^ (*key);
key++;
/* fall through */
case 4 * sizeof(int):
h = h * PRIME1 ^ (*key);
key++;
/* fall through */
case 3 * sizeof(int):
h = h * PRIME1 ^ (*key);
key++;
/* fall through */
case 2 * sizeof(int):
h = h * PRIME1 ^ (*key);
key++;
/* fall through */
case sizeof(int):
h = h * PRIME1 ^ (*key);
key++;
break;
default:
for (; keysize > (sizeof(int) - 1); keysize -= sizeof(int), key++)
h = h * PRIME1 ^ (*key);
/*
* now let's grab the last few bytes of the tag if the tag has
* (size % 4) != 0 (which it sometimes will on a sun3).
*/
if (keysize)
{
char *keytmp = (char *) key;
switch (keysize)
{
case 3:
h = h * PRIME1 ^ (*keytmp);
keytmp++;
/* fall through */
case 2:
h = h * PRIME1 ^ (*keytmp);
keytmp++;
/* fall through */
case 1:
h = h * PRIME1 ^ (*keytmp);
break;
}
}
break;
}
h %= PRIME2;
return (h);
}
/*
* This is INCREDIBLY ugly, but fast.
* We break the string up into 8 byte units. On the first time
* through the loop we get the "leftover bytes" (strlen % 8).
* On every other iteration, we perform 8 HASHC's so we handle
* all 8 bytes. Essentially, this saves us 7 cmp & branch
* instructions. If this routine is heavily used enough, it's
* worth the ugly coding
*/
#ifdef NOT_USED
long
disk_hash(char *key)
{
int n = 0;
char *str = key;
int len = strlen(key);
int loop;
#define HASHC n = *str++ + 65599 * n
if (len > 0)
{
loop = (len + 8 - 1) >> 3;
switch (len & (8 - 1))
{
case 0:
do
{ /* All fall throughs */
HASHC;
case 7:
HASHC;
case 6:
HASHC;
case 5:
HASHC;
case 4:
HASHC;
case 3:
HASHC;
case 2:
HASHC;
case 1:
HASHC;
} while (--loop);
}
}
return (n);
}
#endif
|
