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-2025, 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
9210 tgl@sss.pgh.pa.us 47 :CBC 71394 : hashchar(PG_FUNCTION_ARGS)
48 : : {
6672 49 : 71394 : return hash_uint32((int32) PG_GETARG_CHAR(0));
50 : : }
51 : :
52 : : Datum
2928 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
9224 tgl@sss.pgh.pa.us 59 : 183698 : hashint2(PG_FUNCTION_ARGS)
60 : : {
6672 61 : 183698 : return hash_uint32((int32) PG_GETARG_INT16(0));
62 : : }
63 : :
64 : : Datum
2928 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
9224 tgl@sss.pgh.pa.us 71 : 13695841 : hashint4(PG_FUNCTION_ARGS)
72 : : {
6672 73 : 13695841 : return hash_uint32(PG_GETARG_INT32(0));
74 : : }
75 : :
76 : : Datum
2928 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
9224 tgl@sss.pgh.pa.us 83 : 316039 : 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 : : */
7755 93 : 316039 : int64 val = PG_GETARG_INT64(0);
94 : 316039 : uint32 lohalf = (uint32) val;
95 : 316039 : uint32 hihalf = (uint32) (val >> 32);
96 : :
97 [ + + ]: 316039 : lohalf ^= (val >= 0) ? hihalf : ~hihalf;
98 : :
6672 99 : 316039 : return hash_uint32(lohalf);
100 : : }
101 : :
102 : : Datum
2928 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
9210 tgl@sss.pgh.pa.us 116 : 8896089 : hashoid(PG_FUNCTION_ARGS)
117 : : {
6672 118 : 8896089 : return hash_uint32((uint32) PG_GETARG_OID(0));
119 : : }
120 : :
121 : : Datum
2928 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
6732 tgl@sss.pgh.pa.us 128 : 1571 : hashenum(PG_FUNCTION_ARGS)
129 : : {
6672 130 : 1571 : return hash_uint32((uint32) PG_GETARG_OID(0));
131 : : }
132 : :
133 : : Datum
2928 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
9224 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 : : */
8112 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 : : */
6832 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 : : */
1463 169 [ + + ]: 21149 : if (isnan(key8))
170 : 9 : key8 = get_float8_nan();
171 : :
6832 172 : 21149 : return hash_any((unsigned char *) &key8, sizeof(key8));
173 : : }
174 : :
175 : : Datum
2928 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;
1463 tgl@sss.pgh.pa.us 186 [ - + ]: 30 : if (isnan(key8))
1463 tgl@sss.pgh.pa.us 187 :UBC 0 : key8 = get_float8_nan();
188 : :
2928 rhaas@postgresql.org 189 :CBC 30 : return hash_any_extended((unsigned char *) &key8, sizeof(key8), seed);
190 : : }
191 : :
192 : : Datum
9224 tgl@sss.pgh.pa.us 193 : 68556 : hashfloat8(PG_FUNCTION_ARGS)
194 : : {
195 : 68556 : 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 : : */
8112 202 [ + + ]: 68556 : 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 : : */
1465 210 [ + + ]: 68210 : if (isnan(key))
211 : 9 : key = get_float8_nan();
212 : :
8582 213 : 68210 : return hash_any((unsigned char *) &key, sizeof(key));
214 : : }
215 : :
216 : : Datum
2928 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);
1465 tgl@sss.pgh.pa.us 225 [ - + ]: 30 : if (isnan(key))
1465 tgl@sss.pgh.pa.us 226 :UBC 0 : key = get_float8_nan();
227 : :
2928 rhaas@postgresql.org 228 :CBC 30 : return hash_any_extended((unsigned char *) &key, sizeof(key), seed);
229 : : }
230 : :
231 : : Datum
9224 tgl@sss.pgh.pa.us 232 : 222592 : hashoidvector(PG_FUNCTION_ARGS)
233 : : {
7466 234 : 222592 : oidvector *key = (oidvector *) PG_GETARG_POINTER(0);
235 : :
236 : 222592 : return hash_any((unsigned char *) key->values, key->dim1 * sizeof(Oid));
237 : : }
238 : :
239 : : Datum
2928 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
9210 tgl@sss.pgh.pa.us 250 : 283384 : hashname(PG_FUNCTION_ARGS)
251 : : {
8934 bruce@momjian.us 252 : 283384 : char *key = NameStr(*PG_GETARG_NAME(0));
253 : :
3176 tgl@sss.pgh.pa.us 254 : 283384 : return hash_any((unsigned char *) key, strlen(key));
255 : : }
256 : :
257 : : Datum
2928 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
8112 tgl@sss.pgh.pa.us 267 : 757208 : hashtext(PG_FUNCTION_ARGS)
268 : : {
6560 269 : 757208 : text *key = PG_GETARG_TEXT_PP(0);
2360 peter@eisentraut.org 270 : 757208 : Oid collid = PG_GET_COLLATION();
271 : : pg_locale_t mylocale;
272 : : Datum result;
273 : :
274 [ + + ]: 757208 : 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 : :
397 jdavis@postgresql.or 280 : 757205 : mylocale = pg_newlocale_from_collation(collid);
281 : :
359 282 [ + + ]: 757205 : if (mylocale->deterministic)
283 : : {
2360 peter@eisentraut.org 284 [ + + ]: 754802 : result = hash_any((unsigned char *) VARDATA_ANY(key),
285 [ - + - - : 754802 : VARSIZE_ANY_EXHDR(key));
- - - - +
+ ]
286 : : }
287 : : else
288 : : {
289 : : Size bsize,
290 : : rsize;
291 : : char *buf;
926 jdavis@postgresql.or 292 [ + - ]: 2403 : const char *keydata = VARDATA_ANY(key);
293 [ - + - - : 2403 : size_t keylen = VARSIZE_ANY_EXHDR(key);
- - - - +
- ]
294 : :
295 : :
296 : 2403 : bsize = pg_strnxfrm(NULL, 0, keydata, keylen, mylocale);
297 : 2403 : buf = palloc(bsize + 1);
298 : :
299 : 2403 : rsize = pg_strnxfrm(buf, bsize + 1, keydata, keylen, mylocale);
300 : :
301 : : /* the second call may return a smaller value than the first */
403 302 [ - + ]: 2403 : if (rsize > bsize)
926 jdavis@postgresql.or 303 [ # # ]:UBC 0 : elog(ERROR, "pg_strnxfrm() returned unexpected result");
304 : :
305 : : /*
306 : : * In principle, there's no reason to include the terminating NUL
307 : : * character in the hash, but it was done before and the behavior must
308 : : * be preserved.
309 : : */
926 jdavis@postgresql.or 310 :CBC 2403 : result = hash_any((uint8_t *) buf, bsize + 1);
311 : :
312 : 2403 : pfree(buf);
313 : : }
314 : :
315 : : /* Avoid leaking memory for toasted inputs */
8112 tgl@sss.pgh.pa.us 316 [ - + ]: 757205 : PG_FREE_IF_COPY(key, 0);
317 : :
318 : 757205 : return result;
319 : : }
320 : :
321 : : Datum
2928 rhaas@postgresql.org 322 : 2034 : hashtextextended(PG_FUNCTION_ARGS)
323 : : {
324 : 2034 : text *key = PG_GETARG_TEXT_PP(0);
2360 peter@eisentraut.org 325 : 2034 : Oid collid = PG_GET_COLLATION();
326 : : pg_locale_t mylocale;
327 : : Datum result;
328 : :
329 [ - + ]: 2034 : if (!collid)
2360 peter@eisentraut.org 330 [ # # ]:UBC 0 : ereport(ERROR,
331 : : (errcode(ERRCODE_INDETERMINATE_COLLATION),
332 : : errmsg("could not determine which collation to use for string hashing"),
333 : : errhint("Use the COLLATE clause to set the collation explicitly.")));
334 : :
397 jdavis@postgresql.or 335 :CBC 2034 : mylocale = pg_newlocale_from_collation(collid);
336 : :
359 337 [ + + ]: 2034 : if (mylocale->deterministic)
338 : : {
2360 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;
926 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 : :
356 : : /* the second call may return a smaller value than the first */
403 357 [ - + ]: 12 : if (rsize > bsize)
926 jdavis@postgresql.or 358 [ # # ]:UBC 0 : elog(ERROR, "pg_strnxfrm() returned unexpected result");
359 : :
360 : : /*
361 : : * In principle, there's no reason to include the terminating NUL
362 : : * character in the hash, but it was done before and the behavior must
363 : : * be preserved.
364 : : */
926 jdavis@postgresql.or 365 :CBC 12 : result = hash_any_extended((uint8_t *) buf, bsize + 1,
366 : 12 : PG_GETARG_INT64(1));
367 : :
368 : 12 : pfree(buf);
369 : : }
370 : :
2928 rhaas@postgresql.org 371 [ - + ]: 2034 : PG_FREE_IF_COPY(key, 0);
372 : :
373 : 2034 : return result;
374 : : }
375 : :
376 : : /*
377 : : * hashvarlena() can be used for any varlena datatype in which there are
378 : : * no non-significant bits, ie, distinct bitpatterns never compare as equal.
379 : : *
380 : : * (However, you need to define an SQL-level wrapper function around it with
381 : : * the concrete input data type; otherwise hashvalidate() won't accept it.
382 : : * Moreover, at least for built-in types, a C-level wrapper function is also
383 : : * recommended; otherwise, the opr_sanity test will get upset.)
384 : : */
385 : : Datum
9210 tgl@sss.pgh.pa.us 386 : 3075 : hashvarlena(PG_FUNCTION_ARGS)
387 : : {
6560 388 : 3075 : struct varlena *key = PG_GETARG_VARLENA_PP(0);
389 : : Datum result;
390 : :
391 [ + + ]: 3075 : result = hash_any((unsigned char *) VARDATA_ANY(key),
392 [ - + - - : 3075 : VARSIZE_ANY_EXHDR(key));
- - - - +
+ ]
393 : :
394 : : /* Avoid leaking memory for toasted inputs */
9038 395 [ + + ]: 3075 : PG_FREE_IF_COPY(key, 0);
396 : :
397 : 3075 : return result;
398 : : }
399 : :
400 : : Datum
2928 rhaas@postgresql.org 401 :UBC 0 : hashvarlenaextended(PG_FUNCTION_ARGS)
402 : : {
403 : 0 : struct varlena *key = PG_GETARG_VARLENA_PP(0);
404 : : Datum result;
405 : :
406 [ # # ]: 0 : result = hash_any_extended((unsigned char *) VARDATA_ANY(key),
407 [ # # # # : 0 : VARSIZE_ANY_EXHDR(key),
# # # # #
# ]
408 : 0 : PG_GETARG_INT64(1));
409 : :
410 [ # # ]: 0 : PG_FREE_IF_COPY(key, 0);
411 : :
412 : 0 : return result;
413 : : }
414 : :
415 : : Datum
359 peter@eisentraut.org 416 :CBC 3075 : hashbytea(PG_FUNCTION_ARGS)
417 : : {
418 : 3075 : return hashvarlena(fcinfo);
419 : : }
420 : :
421 : : Datum
359 peter@eisentraut.org 422 :UBC 0 : hashbyteaextended(PG_FUNCTION_ARGS)
423 : : {
424 : 0 : return hashvarlenaextended(fcinfo);
425 : : }
|
