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-2026, 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/builtins.h"
31 : : #include "utils/float.h"
32 : : #include "utils/fmgrprotos.h"
33 : : #include "utils/pg_locale.h"
34 : : #include "varatt.h"
35 : :
36 : : /*
37 : : * Datatype-specific hash functions.
38 : : *
39 : : * These support both hash indexes and hash joins.
40 : : *
41 : : * NOTE: some of these are also used by catcache operations, without
42 : : * any direct connection to hash indexes. Also, the common hash_any
43 : : * routine is also used by dynahash tables.
44 : : */
45 : :
46 : : /* Note: this is used for both "char" and boolean datatypes */
47 : : Datum
9400 tgl@sss.pgh.pa.us 48 :CBC 76177 : hashchar(PG_FUNCTION_ARGS)
49 : : {
6862 50 : 76177 : return hash_uint32((int32) PG_GETARG_CHAR(0));
51 : : }
52 : :
53 : : Datum
3118 rhaas@postgresql.org 54 : 33 : hashcharextended(PG_FUNCTION_ARGS)
55 : : {
56 : 33 : return hash_uint32_extended((int32) PG_GETARG_CHAR(0), PG_GETARG_INT64(1));
57 : : }
58 : :
59 : : Datum
9414 tgl@sss.pgh.pa.us 60 : 289390 : hashint2(PG_FUNCTION_ARGS)
61 : : {
6862 62 : 289390 : return hash_uint32((int32) PG_GETARG_INT16(0));
63 : : }
64 : :
65 : : Datum
3118 rhaas@postgresql.org 66 : 24 : hashint2extended(PG_FUNCTION_ARGS)
67 : : {
68 : 24 : return hash_uint32_extended((int32) PG_GETARG_INT16(0), PG_GETARG_INT64(1));
69 : : }
70 : :
71 : : Datum
9414 tgl@sss.pgh.pa.us 72 : 14771246 : hashint4(PG_FUNCTION_ARGS)
73 : : {
6862 74 : 14771246 : return hash_uint32(PG_GETARG_INT32(0));
75 : : }
76 : :
77 : : Datum
3118 rhaas@postgresql.org 78 : 102604 : hashint4extended(PG_FUNCTION_ARGS)
79 : : {
80 : 102604 : return hash_uint32_extended(PG_GETARG_INT32(0), PG_GETARG_INT64(1));
81 : : }
82 : :
83 : : Datum
9414 tgl@sss.pgh.pa.us 84 : 316635 : hashint8(PG_FUNCTION_ARGS)
85 : : {
86 : : /*
87 : : * The idea here is to produce a hash value compatible with the values
88 : : * produced by hashint4 and hashint2 for logically equal inputs; this is
89 : : * necessary to support cross-type hash joins across these input types.
90 : : * Since all three types are signed, we can xor the high half of the int8
91 : : * value if the sign is positive, or the complement of the high half when
92 : : * the sign is negative.
93 : : */
7945 94 : 316635 : int64 val = PG_GETARG_INT64(0);
95 : 316635 : uint32 lohalf = (uint32) val;
96 : 316635 : uint32 hihalf = (uint32) (val >> 32);
97 : :
98 [ + + ]: 316635 : lohalf ^= (val >= 0) ? hihalf : ~hihalf;
99 : :
6862 100 : 316635 : return hash_uint32(lohalf);
101 : : }
102 : :
103 : : Datum
3118 rhaas@postgresql.org 104 : 222 : hashint8extended(PG_FUNCTION_ARGS)
105 : : {
106 : : /* Same approach as hashint8 */
107 : 222 : int64 val = PG_GETARG_INT64(0);
108 : 222 : uint32 lohalf = (uint32) val;
109 : 222 : uint32 hihalf = (uint32) (val >> 32);
110 : :
111 [ - + ]: 222 : lohalf ^= (val >= 0) ? hihalf : ~hihalf;
112 : :
113 : 222 : return hash_uint32_extended(lohalf, PG_GETARG_INT64(1));
114 : : }
115 : :
116 : : Datum
9400 tgl@sss.pgh.pa.us 117 : 10199689 : hashoid(PG_FUNCTION_ARGS)
118 : : {
6862 119 : 10199689 : return hash_uint32((uint32) PG_GETARG_OID(0));
120 : : }
121 : :
122 : : Datum
3118 rhaas@postgresql.org 123 : 36 : hashoidextended(PG_FUNCTION_ARGS)
124 : : {
125 : 36 : return hash_uint32_extended((uint32) PG_GETARG_OID(0), PG_GETARG_INT64(1));
126 : : }
127 : :
128 : : Datum
6922 tgl@sss.pgh.pa.us 129 : 1571 : hashenum(PG_FUNCTION_ARGS)
130 : : {
6862 131 : 1571 : return hash_uint32((uint32) PG_GETARG_OID(0));
132 : : }
133 : :
134 : : Datum
3118 rhaas@postgresql.org 135 : 2018 : hashenumextended(PG_FUNCTION_ARGS)
136 : : {
137 : 2018 : return hash_uint32_extended((uint32) PG_GETARG_OID(0), PG_GETARG_INT64(1));
138 : : }
139 : :
140 : : Datum
9414 tgl@sss.pgh.pa.us 141 : 22853 : hashfloat4(PG_FUNCTION_ARGS)
142 : : {
143 : 22853 : float4 key = PG_GETARG_FLOAT4(0);
144 : : float8 key8;
145 : :
146 : : /*
147 : : * On IEEE-float machines, minus zero and zero have different bit patterns
148 : : * but should compare as equal. We must ensure that they have the same
149 : : * hash value, which is most reliably done this way:
150 : : */
8302 151 [ + + ]: 22853 : if (key == (float4) 0)
152 : 108 : PG_RETURN_UINT32(0);
153 : :
154 : : /*
155 : : * To support cross-type hashing of float8 and float4, we want to return
156 : : * the same hash value hashfloat8 would produce for an equal float8 value.
157 : : * So, widen the value to float8 and hash that. (We must do this rather
158 : : * than have hashfloat8 try to narrow its value to float4; that could fail
159 : : * on overflow.)
160 : : */
7022 161 : 22745 : key8 = key;
162 : :
163 : : /*
164 : : * Similarly, NaNs can have different bit patterns but they should all
165 : : * compare as equal. For backwards-compatibility reasons we force them to
166 : : * have the hash value of a standard float8 NaN. (You'd think we could
167 : : * replace key with a float4 NaN and then widen it; but on some old
168 : : * platforms, that way produces a different bit pattern.)
169 : : */
1653 170 [ + + ]: 22745 : if (isnan(key8))
171 : 9 : key8 = get_float8_nan();
172 : :
7022 173 : 22745 : return hash_any((unsigned char *) &key8, sizeof(key8));
174 : : }
175 : :
176 : : Datum
3118 rhaas@postgresql.org 177 : 36 : hashfloat4extended(PG_FUNCTION_ARGS)
178 : : {
179 : 36 : float4 key = PG_GETARG_FLOAT4(0);
180 : 36 : uint64 seed = PG_GETARG_INT64(1);
181 : : float8 key8;
182 : :
183 : : /* Same approach as hashfloat4 */
184 [ + + ]: 36 : if (key == (float4) 0)
185 : 6 : PG_RETURN_UINT64(seed);
186 : 30 : key8 = key;
1653 tgl@sss.pgh.pa.us 187 [ - + ]: 30 : if (isnan(key8))
1653 tgl@sss.pgh.pa.us 188 :UBC 0 : key8 = get_float8_nan();
189 : :
3118 rhaas@postgresql.org 190 :CBC 30 : return hash_any_extended((unsigned char *) &key8, sizeof(key8), seed);
191 : : }
192 : :
193 : : Datum
9414 tgl@sss.pgh.pa.us 194 : 68960 : hashfloat8(PG_FUNCTION_ARGS)
195 : : {
196 : 68960 : float8 key = PG_GETARG_FLOAT8(0);
197 : :
198 : : /*
199 : : * On IEEE-float machines, minus zero and zero have different bit patterns
200 : : * but should compare as equal. We must ensure that they have the same
201 : : * hash value, which is most reliably done this way:
202 : : */
8302 203 [ + + ]: 68960 : if (key == (float8) 0)
204 : 346 : PG_RETURN_UINT32(0);
205 : :
206 : : /*
207 : : * Similarly, NaNs can have different bit patterns but they should all
208 : : * compare as equal. For backwards-compatibility reasons we force them to
209 : : * have the hash value of a standard NaN.
210 : : */
1655 211 [ + + ]: 68614 : if (isnan(key))
212 : 9 : key = get_float8_nan();
213 : :
8772 214 : 68614 : return hash_any((unsigned char *) &key, sizeof(key));
215 : : }
216 : :
217 : : Datum
3118 rhaas@postgresql.org 218 : 36 : hashfloat8extended(PG_FUNCTION_ARGS)
219 : : {
220 : 36 : float8 key = PG_GETARG_FLOAT8(0);
221 : 36 : uint64 seed = PG_GETARG_INT64(1);
222 : :
223 : : /* Same approach as hashfloat8 */
224 [ + + ]: 36 : if (key == (float8) 0)
225 : 6 : PG_RETURN_UINT64(seed);
1655 tgl@sss.pgh.pa.us 226 [ - + ]: 30 : if (isnan(key))
1655 tgl@sss.pgh.pa.us 227 :UBC 0 : key = get_float8_nan();
228 : :
3118 rhaas@postgresql.org 229 :CBC 30 : return hash_any_extended((unsigned char *) &key, sizeof(key), seed);
230 : : }
231 : :
232 : : Datum
9414 tgl@sss.pgh.pa.us 233 : 221835 : hashoidvector(PG_FUNCTION_ARGS)
234 : : {
7656 235 : 221835 : oidvector *key = (oidvector *) PG_GETARG_POINTER(0);
236 : :
34 237 : 221835 : check_valid_oidvector(key);
7656 238 : 221835 : return hash_any((unsigned char *) key->values, key->dim1 * sizeof(Oid));
239 : : }
240 : :
241 : : Datum
3118 rhaas@postgresql.org 242 : 30 : hashoidvectorextended(PG_FUNCTION_ARGS)
243 : : {
244 : 30 : oidvector *key = (oidvector *) PG_GETARG_POINTER(0);
245 : :
34 tgl@sss.pgh.pa.us 246 : 30 : check_valid_oidvector(key);
3118 rhaas@postgresql.org 247 : 60 : return hash_any_extended((unsigned char *) key->values,
248 : 30 : key->dim1 * sizeof(Oid),
249 : 30 : PG_GETARG_INT64(1));
250 : : }
251 : :
252 : : Datum
9400 tgl@sss.pgh.pa.us 253 : 284720 : hashname(PG_FUNCTION_ARGS)
254 : : {
9124 bruce@momjian.us 255 : 284720 : char *key = NameStr(*PG_GETARG_NAME(0));
256 : :
3366 tgl@sss.pgh.pa.us 257 : 284720 : return hash_any((unsigned char *) key, strlen(key));
258 : : }
259 : :
260 : : Datum
3118 rhaas@postgresql.org 261 : 30 : hashnameextended(PG_FUNCTION_ARGS)
262 : : {
263 : 30 : char *key = NameStr(*PG_GETARG_NAME(0));
264 : :
265 : 30 : return hash_any_extended((unsigned char *) key, strlen(key),
266 : 30 : PG_GETARG_INT64(1));
267 : : }
268 : :
269 : : Datum
8302 tgl@sss.pgh.pa.us 270 : 771116 : hashtext(PG_FUNCTION_ARGS)
271 : : {
6750 272 : 771116 : text *key = PG_GETARG_TEXT_PP(0);
2550 peter@eisentraut.org 273 : 771116 : Oid collid = PG_GET_COLLATION();
274 : : pg_locale_t mylocale;
275 : : Datum result;
276 : :
277 [ + + ]: 771116 : if (!collid)
278 [ + - ]: 3 : ereport(ERROR,
279 : : (errcode(ERRCODE_INDETERMINATE_COLLATION),
280 : : errmsg("could not determine which collation to use for string hashing"),
281 : : errhint("Use the COLLATE clause to set the collation explicitly.")));
282 : :
587 jdavis@postgresql.or 283 : 771113 : mylocale = pg_newlocale_from_collation(collid);
284 : :
549 285 [ + + ]: 771113 : if (mylocale->deterministic)
286 : : {
2550 peter@eisentraut.org 287 [ + + ]: 769778 : result = hash_any((unsigned char *) VARDATA_ANY(key),
288 [ - + - - : 769778 : VARSIZE_ANY_EXHDR(key));
- - - - +
+ ]
289 : : }
290 : : else
291 : : {
292 : : Size bsize,
293 : : rsize;
294 : : char *buf;
1116 jdavis@postgresql.or 295 [ + - ]: 1335 : const char *keydata = VARDATA_ANY(key);
296 [ - + - - : 1335 : size_t keylen = VARSIZE_ANY_EXHDR(key);
- - - - +
- ]
297 : :
298 : :
299 : 1335 : bsize = pg_strnxfrm(NULL, 0, keydata, keylen, mylocale);
300 : 1335 : buf = palloc(bsize + 1);
301 : :
302 : 1335 : rsize = pg_strnxfrm(buf, bsize + 1, keydata, keylen, mylocale);
303 : :
304 : : /* the second call may return a smaller value than the first */
593 305 [ - + ]: 1335 : if (rsize > bsize)
1116 jdavis@postgresql.or 306 [ # # ]:UBC 0 : elog(ERROR, "pg_strnxfrm() returned unexpected result");
307 : :
308 : : /*
309 : : * In principle, there's no reason to include the terminating NUL
310 : : * character in the hash, but it was done before and the behavior must
311 : : * be preserved.
312 : : */
1116 jdavis@postgresql.or 313 :CBC 1335 : result = hash_any((uint8_t *) buf, bsize + 1);
314 : :
315 : 1335 : pfree(buf);
316 : : }
317 : :
318 : : /* Avoid leaking memory for toasted inputs */
8302 tgl@sss.pgh.pa.us 319 [ - + ]: 771113 : PG_FREE_IF_COPY(key, 0);
320 : :
321 : 771113 : return result;
322 : : }
323 : :
324 : : Datum
3118 rhaas@postgresql.org 325 : 2034 : hashtextextended(PG_FUNCTION_ARGS)
326 : : {
327 : 2034 : text *key = PG_GETARG_TEXT_PP(0);
2550 peter@eisentraut.org 328 : 2034 : Oid collid = PG_GET_COLLATION();
329 : : pg_locale_t mylocale;
330 : : Datum result;
331 : :
332 [ - + ]: 2034 : if (!collid)
2550 peter@eisentraut.org 333 [ # # ]:UBC 0 : ereport(ERROR,
334 : : (errcode(ERRCODE_INDETERMINATE_COLLATION),
335 : : errmsg("could not determine which collation to use for string hashing"),
336 : : errhint("Use the COLLATE clause to set the collation explicitly.")));
337 : :
587 jdavis@postgresql.or 338 :CBC 2034 : mylocale = pg_newlocale_from_collation(collid);
339 : :
549 340 [ + + ]: 2034 : if (mylocale->deterministic)
341 : : {
2550 peter@eisentraut.org 342 [ + + ]: 2022 : result = hash_any_extended((unsigned char *) VARDATA_ANY(key),
343 [ - + - - : 2022 : VARSIZE_ANY_EXHDR(key),
- - - - +
+ ]
344 : 2022 : PG_GETARG_INT64(1));
345 : : }
346 : : else
347 : : {
348 : : Size bsize,
349 : : rsize;
350 : : char *buf;
1116 jdavis@postgresql.or 351 [ - + ]: 12 : const char *keydata = VARDATA_ANY(key);
352 [ - + - - : 12 : size_t keylen = VARSIZE_ANY_EXHDR(key);
- - - - -
+ ]
353 : :
354 : 12 : bsize = pg_strnxfrm(NULL, 0, keydata, keylen, mylocale);
355 : 12 : buf = palloc(bsize + 1);
356 : :
357 : 12 : rsize = pg_strnxfrm(buf, bsize + 1, keydata, keylen, mylocale);
358 : :
359 : : /* the second call may return a smaller value than the first */
593 360 [ - + ]: 12 : if (rsize > bsize)
1116 jdavis@postgresql.or 361 [ # # ]:UBC 0 : elog(ERROR, "pg_strnxfrm() returned unexpected result");
362 : :
363 : : /*
364 : : * In principle, there's no reason to include the terminating NUL
365 : : * character in the hash, but it was done before and the behavior must
366 : : * be preserved.
367 : : */
1116 jdavis@postgresql.or 368 :CBC 12 : result = hash_any_extended((uint8_t *) buf, bsize + 1,
369 : 12 : PG_GETARG_INT64(1));
370 : :
371 : 12 : pfree(buf);
372 : : }
373 : :
3118 rhaas@postgresql.org 374 [ - + ]: 2034 : PG_FREE_IF_COPY(key, 0);
375 : :
376 : 2034 : return result;
377 : : }
378 : :
379 : : /*
380 : : * hashvarlena() can be used for any varlena datatype in which there are
381 : : * no non-significant bits, ie, distinct bitpatterns never compare as equal.
382 : : *
383 : : * (However, you need to define an SQL-level wrapper function around it with
384 : : * the concrete input data type; otherwise hashvalidate() won't accept it.
385 : : * Moreover, at least for built-in types, a C-level wrapper function is also
386 : : * recommended; otherwise, the opr_sanity test will get upset.)
387 : : */
388 : : Datum
9400 tgl@sss.pgh.pa.us 389 : 3123 : hashvarlena(PG_FUNCTION_ARGS)
390 : : {
32 michael@paquier.xyz 391 :GNC 3123 : varlena *key = PG_GETARG_VARLENA_PP(0);
392 : : Datum result;
393 : :
6750 tgl@sss.pgh.pa.us 394 [ + + ]:CBC 3123 : result = hash_any((unsigned char *) VARDATA_ANY(key),
395 [ - + - - : 3123 : VARSIZE_ANY_EXHDR(key));
- - - - +
+ ]
396 : :
397 : : /* Avoid leaking memory for toasted inputs */
9228 398 [ + + ]: 3123 : PG_FREE_IF_COPY(key, 0);
399 : :
400 : 3123 : return result;
401 : : }
402 : :
403 : : Datum
3118 rhaas@postgresql.org 404 :UBC 0 : hashvarlenaextended(PG_FUNCTION_ARGS)
405 : : {
32 michael@paquier.xyz 406 :UNC 0 : varlena *key = PG_GETARG_VARLENA_PP(0);
407 : : Datum result;
408 : :
3118 rhaas@postgresql.org 409 [ # # ]:UBC 0 : result = hash_any_extended((unsigned char *) VARDATA_ANY(key),
410 [ # # # # : 0 : VARSIZE_ANY_EXHDR(key),
# # # # #
# ]
411 : 0 : PG_GETARG_INT64(1));
412 : :
413 [ # # ]: 0 : PG_FREE_IF_COPY(key, 0);
414 : :
415 : 0 : return result;
416 : : }
417 : :
418 : : Datum
549 peter@eisentraut.org 419 :CBC 3123 : hashbytea(PG_FUNCTION_ARGS)
420 : : {
421 : 3123 : return hashvarlena(fcinfo);
422 : : }
423 : :
424 : : Datum
549 peter@eisentraut.org 425 :UBC 0 : hashbyteaextended(PG_FUNCTION_ARGS)
426 : : {
427 : 0 : return hashvarlenaextended(fcinfo);
428 : : }
|
