Age Owner Branch data TLA Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * hashfunc.c
4 : : * Support functions for hash access method.
5 : : *
6 : : * Portions Copyright (c) 1996-2024, PostgreSQL Global Development Group
7 : : * Portions Copyright (c) 1994, Regents of the University of California
8 : : *
9 : : *
10 : : * IDENTIFICATION
11 : : * src/backend/access/hash/hashfunc.c
12 : : *
13 : : * NOTES
14 : : * These functions are stored in pg_amproc. For each operator class
15 : : * defined for hash indexes, they compute the hash value of the argument.
16 : : *
17 : : * Additional hash functions appear in /utils/adt/ files for various
18 : : * specialized datatypes.
19 : : *
20 : : * It is expected that every bit of a hash function's 32-bit result is
21 : : * as random as every other; failure to ensure this is likely to lead
22 : : * to poor performance of hash joins, for example. In most cases a hash
23 : : * function should use hash_any() or its variant hash_uint32().
24 : : *-------------------------------------------------------------------------
25 : : */
26 : :
27 : : #include "postgres.h"
28 : :
29 : : #include "common/hashfn.h"
30 : : #include "utils/float.h"
31 : : #include "utils/fmgrprotos.h"
32 : : #include "utils/pg_locale.h"
33 : : #include "varatt.h"
34 : :
35 : : /*
36 : : * Datatype-specific hash functions.
37 : : *
38 : : * These support both hash indexes and hash joins.
39 : : *
40 : : * NOTE: some of these are also used by catcache operations, without
41 : : * any direct connection to hash indexes. Also, the common hash_any
42 : : * routine is also used by dynahash tables.
43 : : */
44 : :
45 : : /* Note: this is used for both "char" and boolean datatypes */
46 : : Datum
8700 tgl@sss.pgh.pa.us 47 :CBC 94959 : hashchar(PG_FUNCTION_ARGS)
48 : : {
6162 49 : 94959 : return hash_uint32((int32) PG_GETARG_CHAR(0));
50 : : }
51 : :
52 : : Datum
2418 rhaas@postgresql.org 53 : 33 : hashcharextended(PG_FUNCTION_ARGS)
54 : : {
55 : 33 : return hash_uint32_extended((int32) PG_GETARG_CHAR(0), PG_GETARG_INT64(1));
56 : : }
57 : :
58 : : Datum
8714 tgl@sss.pgh.pa.us 59 : 171964 : hashint2(PG_FUNCTION_ARGS)
60 : : {
6162 61 : 171964 : return hash_uint32((int32) PG_GETARG_INT16(0));
62 : : }
63 : :
64 : : Datum
2418 rhaas@postgresql.org 65 : 24 : hashint2extended(PG_FUNCTION_ARGS)
66 : : {
67 : 24 : return hash_uint32_extended((int32) PG_GETARG_INT16(0), PG_GETARG_INT64(1));
68 : : }
69 : :
70 : : Datum
8714 tgl@sss.pgh.pa.us 71 : 13389207 : hashint4(PG_FUNCTION_ARGS)
72 : : {
6162 73 : 13389207 : return hash_uint32(PG_GETARG_INT32(0));
74 : : }
75 : :
76 : : Datum
2418 rhaas@postgresql.org 77 : 102604 : hashint4extended(PG_FUNCTION_ARGS)
78 : : {
79 : 102604 : return hash_uint32_extended(PG_GETARG_INT32(0), PG_GETARG_INT64(1));
80 : : }
81 : :
82 : : Datum
8714 tgl@sss.pgh.pa.us 83 : 315394 : hashint8(PG_FUNCTION_ARGS)
84 : : {
85 : : /*
86 : : * The idea here is to produce a hash value compatible with the values
87 : : * produced by hashint4 and hashint2 for logically equal inputs; this is
88 : : * necessary to support cross-type hash joins across these input types.
89 : : * Since all three types are signed, we can xor the high half of the int8
90 : : * value if the sign is positive, or the complement of the high half when
91 : : * the sign is negative.
92 : : */
7245 93 : 315394 : int64 val = PG_GETARG_INT64(0);
94 : 315394 : uint32 lohalf = (uint32) val;
95 : 315394 : uint32 hihalf = (uint32) (val >> 32);
96 : :
97 [ + + ]: 315394 : lohalf ^= (val >= 0) ? hihalf : ~hihalf;
98 : :
6162 99 : 315394 : return hash_uint32(lohalf);
100 : : }
101 : :
102 : : Datum
2418 rhaas@postgresql.org 103 : 186 : hashint8extended(PG_FUNCTION_ARGS)
104 : : {
105 : : /* Same approach as hashint8 */
106 : 186 : int64 val = PG_GETARG_INT64(0);
107 : 186 : uint32 lohalf = (uint32) val;
108 : 186 : uint32 hihalf = (uint32) (val >> 32);
109 : :
110 [ - + ]: 186 : lohalf ^= (val >= 0) ? hihalf : ~hihalf;
111 : :
112 : 186 : return hash_uint32_extended(lohalf, PG_GETARG_INT64(1));
113 : : }
114 : :
115 : : Datum
8700 tgl@sss.pgh.pa.us 116 : 6044105 : hashoid(PG_FUNCTION_ARGS)
117 : : {
6162 118 : 6044105 : return hash_uint32((uint32) PG_GETARG_OID(0));
119 : : }
120 : :
121 : : Datum
2418 rhaas@postgresql.org 122 : 36 : hashoidextended(PG_FUNCTION_ARGS)
123 : : {
124 : 36 : return hash_uint32_extended((uint32) PG_GETARG_OID(0), PG_GETARG_INT64(1));
125 : : }
126 : :
127 : : Datum
6222 tgl@sss.pgh.pa.us 128 : 1571 : hashenum(PG_FUNCTION_ARGS)
129 : : {
6162 130 : 1571 : return hash_uint32((uint32) PG_GETARG_OID(0));
131 : : }
132 : :
133 : : Datum
2418 rhaas@postgresql.org 134 : 2018 : hashenumextended(PG_FUNCTION_ARGS)
135 : : {
136 : 2018 : return hash_uint32_extended((uint32) PG_GETARG_OID(0), PG_GETARG_INT64(1));
137 : : }
138 : :
139 : : Datum
8714 tgl@sss.pgh.pa.us 140 : 21161 : hashfloat4(PG_FUNCTION_ARGS)
141 : : {
142 : 21161 : float4 key = PG_GETARG_FLOAT4(0);
143 : : float8 key8;
144 : :
145 : : /*
146 : : * On IEEE-float machines, minus zero and zero have different bit patterns
147 : : * but should compare as equal. We must ensure that they have the same
148 : : * hash value, which is most reliably done this way:
149 : : */
7602 150 [ + + ]: 21161 : if (key == (float4) 0)
151 : 12 : PG_RETURN_UINT32(0);
152 : :
153 : : /*
154 : : * To support cross-type hashing of float8 and float4, we want to return
155 : : * the same hash value hashfloat8 would produce for an equal float8 value.
156 : : * So, widen the value to float8 and hash that. (We must do this rather
157 : : * than have hashfloat8 try to narrow its value to float4; that could fail
158 : : * on overflow.)
159 : : */
6322 160 : 21149 : key8 = key;
161 : :
162 : : /*
163 : : * Similarly, NaNs can have different bit patterns but they should all
164 : : * compare as equal. For backwards-compatibility reasons we force them to
165 : : * have the hash value of a standard float8 NaN. (You'd think we could
166 : : * replace key with a float4 NaN and then widen it; but on some old
167 : : * platforms, that way produces a different bit pattern.)
168 : : */
953 169 [ + + ]: 21149 : if (isnan(key8))
170 : 9 : key8 = get_float8_nan();
171 : :
6322 172 : 21149 : return hash_any((unsigned char *) &key8, sizeof(key8));
173 : : }
174 : :
175 : : Datum
2418 rhaas@postgresql.org 176 : 36 : hashfloat4extended(PG_FUNCTION_ARGS)
177 : : {
178 : 36 : float4 key = PG_GETARG_FLOAT4(0);
179 : 36 : uint64 seed = PG_GETARG_INT64(1);
180 : : float8 key8;
181 : :
182 : : /* Same approach as hashfloat4 */
183 [ + + ]: 36 : if (key == (float4) 0)
184 : 6 : PG_RETURN_UINT64(seed);
185 : 30 : key8 = key;
953 tgl@sss.pgh.pa.us 186 [ - + ]: 30 : if (isnan(key8))
953 tgl@sss.pgh.pa.us 187 :UBC 0 : key8 = get_float8_nan();
188 : :
2418 rhaas@postgresql.org 189 :CBC 30 : return hash_any_extended((unsigned char *) &key8, sizeof(key8), seed);
190 : : }
191 : :
192 : : Datum
8714 tgl@sss.pgh.pa.us 193 : 67984 : hashfloat8(PG_FUNCTION_ARGS)
194 : : {
195 : 67984 : float8 key = PG_GETARG_FLOAT8(0);
196 : :
197 : : /*
198 : : * On IEEE-float machines, minus zero and zero have different bit patterns
199 : : * but should compare as equal. We must ensure that they have the same
200 : : * hash value, which is most reliably done this way:
201 : : */
7602 202 [ + + ]: 67984 : if (key == (float8) 0)
203 : 346 : PG_RETURN_UINT32(0);
204 : :
205 : : /*
206 : : * Similarly, NaNs can have different bit patterns but they should all
207 : : * compare as equal. For backwards-compatibility reasons we force them to
208 : : * have the hash value of a standard NaN.
209 : : */
955 210 [ + + ]: 67638 : if (isnan(key))
211 : 9 : key = get_float8_nan();
212 : :
8072 213 : 67638 : return hash_any((unsigned char *) &key, sizeof(key));
214 : : }
215 : :
216 : : Datum
2418 rhaas@postgresql.org 217 : 36 : hashfloat8extended(PG_FUNCTION_ARGS)
218 : : {
219 : 36 : float8 key = PG_GETARG_FLOAT8(0);
220 : 36 : uint64 seed = PG_GETARG_INT64(1);
221 : :
222 : : /* Same approach as hashfloat8 */
223 [ + + ]: 36 : if (key == (float8) 0)
224 : 6 : PG_RETURN_UINT64(seed);
955 tgl@sss.pgh.pa.us 225 [ - + ]: 30 : if (isnan(key))
955 tgl@sss.pgh.pa.us 226 :UBC 0 : key = get_float8_nan();
227 : :
2418 rhaas@postgresql.org 228 :CBC 30 : return hash_any_extended((unsigned char *) &key, sizeof(key), seed);
229 : : }
230 : :
231 : : Datum
8714 tgl@sss.pgh.pa.us 232 : 186169 : hashoidvector(PG_FUNCTION_ARGS)
233 : : {
6956 234 : 186169 : oidvector *key = (oidvector *) PG_GETARG_POINTER(0);
235 : :
236 : 186169 : return hash_any((unsigned char *) key->values, key->dim1 * sizeof(Oid));
237 : : }
238 : :
239 : : Datum
2418 rhaas@postgresql.org 240 : 30 : hashoidvectorextended(PG_FUNCTION_ARGS)
241 : : {
242 : 30 : oidvector *key = (oidvector *) PG_GETARG_POINTER(0);
243 : :
244 : 60 : return hash_any_extended((unsigned char *) key->values,
245 : 30 : key->dim1 * sizeof(Oid),
246 : 30 : PG_GETARG_INT64(1));
247 : : }
248 : :
249 : : Datum
8700 tgl@sss.pgh.pa.us 250 : 257476 : hashname(PG_FUNCTION_ARGS)
251 : : {
8424 bruce@momjian.us 252 : 257476 : char *key = NameStr(*PG_GETARG_NAME(0));
253 : :
2666 tgl@sss.pgh.pa.us 254 : 257476 : return hash_any((unsigned char *) key, strlen(key));
255 : : }
256 : :
257 : : Datum
2418 rhaas@postgresql.org 258 : 30 : hashnameextended(PG_FUNCTION_ARGS)
259 : : {
260 : 30 : char *key = NameStr(*PG_GETARG_NAME(0));
261 : :
262 : 30 : return hash_any_extended((unsigned char *) key, strlen(key),
263 : 30 : PG_GETARG_INT64(1));
264 : : }
265 : :
266 : : Datum
7602 tgl@sss.pgh.pa.us 267 : 709468 : hashtext(PG_FUNCTION_ARGS)
268 : : {
6050 269 : 709468 : text *key = PG_GETARG_TEXT_PP(0);
1850 peter@eisentraut.org 270 : 709468 : Oid collid = PG_GET_COLLATION();
1789 tgl@sss.pgh.pa.us 271 : 709468 : pg_locale_t mylocale = 0;
272 : : Datum result;
273 : :
1850 peter@eisentraut.org 274 [ + + ]: 709468 : if (!collid)
275 [ + - ]: 3 : ereport(ERROR,
276 : : (errcode(ERRCODE_INDETERMINATE_COLLATION),
277 : : errmsg("could not determine which collation to use for string hashing"),
278 : : errhint("Use the COLLATE clause to set the collation explicitly.")));
279 : :
815 280 [ + + ]: 709465 : if (!lc_collate_is_c(collid))
1850 281 : 497481 : mylocale = pg_newlocale_from_collation(collid);
282 : :
416 jdavis@postgresql.or 283 [ + + ]: 709465 : if (pg_locale_deterministic(mylocale))
284 : : {
1850 peter@eisentraut.org 285 [ + + ]: 709378 : result = hash_any((unsigned char *) VARDATA_ANY(key),
286 [ - + - - : 709378 : VARSIZE_ANY_EXHDR(key));
- - - - +
+ ]
287 : : }
288 : : else
289 : : {
290 : : Size bsize,
291 : : rsize;
292 : : char *buf;
416 jdavis@postgresql.or 293 [ + - ]: 87 : const char *keydata = VARDATA_ANY(key);
294 [ - + - - : 87 : size_t keylen = VARSIZE_ANY_EXHDR(key);
- - - - +
- ]
295 : :
296 : :
297 : 87 : bsize = pg_strnxfrm(NULL, 0, keydata, keylen, mylocale);
298 : 87 : buf = palloc(bsize + 1);
299 : :
300 : 87 : rsize = pg_strnxfrm(buf, bsize + 1, keydata, keylen, mylocale);
301 [ - + ]: 87 : if (rsize != bsize)
416 jdavis@postgresql.or 302 [ # # ]:UBC 0 : elog(ERROR, "pg_strnxfrm() returned unexpected result");
303 : :
304 : : /*
305 : : * In principle, there's no reason to include the terminating NUL
306 : : * character in the hash, but it was done before and the behavior must
307 : : * be preserved.
308 : : */
416 jdavis@postgresql.or 309 :CBC 87 : result = hash_any((uint8_t *) buf, bsize + 1);
310 : :
311 : 87 : pfree(buf);
312 : : }
313 : :
314 : : /* Avoid leaking memory for toasted inputs */
7602 tgl@sss.pgh.pa.us 315 [ - + ]: 709465 : PG_FREE_IF_COPY(key, 0);
316 : :
317 : 709465 : return result;
318 : : }
319 : :
320 : : Datum
2418 rhaas@postgresql.org 321 : 2034 : hashtextextended(PG_FUNCTION_ARGS)
322 : : {
323 : 2034 : text *key = PG_GETARG_TEXT_PP(0);
1850 peter@eisentraut.org 324 : 2034 : Oid collid = PG_GET_COLLATION();
1789 tgl@sss.pgh.pa.us 325 : 2034 : pg_locale_t mylocale = 0;
326 : : Datum result;
327 : :
1850 peter@eisentraut.org 328 [ - + ]: 2034 : if (!collid)
1850 peter@eisentraut.org 329 [ # # ]:UBC 0 : ereport(ERROR,
330 : : (errcode(ERRCODE_INDETERMINATE_COLLATION),
331 : : errmsg("could not determine which collation to use for string hashing"),
332 : : errhint("Use the COLLATE clause to set the collation explicitly.")));
333 : :
815 peter@eisentraut.org 334 [ + + ]:CBC 2034 : if (!lc_collate_is_c(collid))
1850 335 : 1364 : mylocale = pg_newlocale_from_collation(collid);
336 : :
416 jdavis@postgresql.or 337 [ + + ]: 2034 : if (pg_locale_deterministic(mylocale))
338 : : {
1850 peter@eisentraut.org 339 [ + + ]: 2022 : result = hash_any_extended((unsigned char *) VARDATA_ANY(key),
340 [ - + - - : 2022 : VARSIZE_ANY_EXHDR(key),
- - - - +
+ ]
341 : 2022 : PG_GETARG_INT64(1));
342 : : }
343 : : else
344 : : {
345 : : Size bsize,
346 : : rsize;
347 : : char *buf;
416 jdavis@postgresql.or 348 [ - + ]: 12 : const char *keydata = VARDATA_ANY(key);
349 [ - + - - : 12 : size_t keylen = VARSIZE_ANY_EXHDR(key);
- - - - -
+ ]
350 : :
351 : 12 : bsize = pg_strnxfrm(NULL, 0, keydata, keylen, mylocale);
352 : 12 : buf = palloc(bsize + 1);
353 : :
354 : 12 : rsize = pg_strnxfrm(buf, bsize + 1, keydata, keylen, mylocale);
355 [ - + ]: 12 : if (rsize != bsize)
416 jdavis@postgresql.or 356 [ # # ]:UBC 0 : elog(ERROR, "pg_strnxfrm() returned unexpected result");
357 : :
358 : : /*
359 : : * In principle, there's no reason to include the terminating NUL
360 : : * character in the hash, but it was done before and the behavior must
361 : : * be preserved.
362 : : */
416 jdavis@postgresql.or 363 :CBC 12 : result = hash_any_extended((uint8_t *) buf, bsize + 1,
364 : 12 : PG_GETARG_INT64(1));
365 : :
366 : 12 : pfree(buf);
367 : : }
368 : :
2418 rhaas@postgresql.org 369 [ - + ]: 2034 : PG_FREE_IF_COPY(key, 0);
370 : :
371 : 2034 : return result;
372 : : }
373 : :
374 : : /*
375 : : * hashvarlena() can be used for any varlena datatype in which there are
376 : : * no non-significant bits, ie, distinct bitpatterns never compare as equal.
377 : : */
378 : : Datum
8700 tgl@sss.pgh.pa.us 379 : 3075 : hashvarlena(PG_FUNCTION_ARGS)
380 : : {
6050 381 : 3075 : struct varlena *key = PG_GETARG_VARLENA_PP(0);
382 : : Datum result;
383 : :
384 [ + + ]: 3075 : result = hash_any((unsigned char *) VARDATA_ANY(key),
385 [ - + - - : 3075 : VARSIZE_ANY_EXHDR(key));
- - - - +
+ ]
386 : :
387 : : /* Avoid leaking memory for toasted inputs */
8528 388 [ + + ]: 3075 : PG_FREE_IF_COPY(key, 0);
389 : :
390 : 3075 : return result;
391 : : }
392 : :
393 : : Datum
2418 rhaas@postgresql.org 394 :UBC 0 : hashvarlenaextended(PG_FUNCTION_ARGS)
395 : : {
396 : 0 : struct varlena *key = PG_GETARG_VARLENA_PP(0);
397 : : Datum result;
398 : :
399 [ # # ]: 0 : result = hash_any_extended((unsigned char *) VARDATA_ANY(key),
400 [ # # # # : 0 : VARSIZE_ANY_EXHDR(key),
# # # # #
# ]
401 : 0 : PG_GETARG_INT64(1));
402 : :
403 [ # # ]: 0 : PG_FREE_IF_COPY(key, 0);
404 : :
405 : 0 : return result;
406 : : }
|
