PostgreSQL Source Code git master
•All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
Macros | Functions
hashfn.h File Reference
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Macros

#define ROTATE_HIGH_AND_LOW_32BITS(v)
 
#define oid_hash   uint32_hash /* Remove me eventually */
 

Functions

uint32 hash_bytes (const unsigned char *k, int keylen)
 
uint64 hash_bytes_extended (const unsigned char *k, int keylen, uint64 seed)
 
uint32 hash_bytes_uint32 (uint32 k)
 
uint64 hash_bytes_uint32_extended (uint32 k, uint64 seed)
 
static Datum hash_any (const unsigned char *k, int keylen)
 
static Datum hash_any_extended (const unsigned char *k, int keylen, uint64 seed)
 
static Datum hash_uint32 (uint32 k)
 
static Datum hash_uint32_extended (uint32 k, uint64 seed)
 
uint32 string_hash (const void *key, Size keysize)
 
uint32 tag_hash (const void *key, Size keysize)
 
uint32 uint32_hash (const void *key, Size keysize)
 
static uint32 hash_combine (uint32 a, uint32 b)
 
static uint64 hash_combine64 (uint64 a, uint64 b)
 
static uint32 murmurhash32 (uint32 data)
 
static uint64 murmurhash64 (uint64 data)
 

Macro Definition Documentation

◆ oid_hash

#define oid_hash   uint32_hash /* Remove me eventually */

Definition at line 59 of file hashfn.h.

◆ ROTATE_HIGH_AND_LOW_32BITS

#define ROTATE_HIGH_AND_LOW_32BITS (   v)
Value:
((((v) << 1) & UINT64CONST(0xfffffffefffffffe)) | \
(((v) >> 31) & UINT64CONST(0x100000001)))
UINT64CONST
#define UINT64CONST(x)
Definition: c.h:517

Definition at line 18 of file hashfn.h.

Function Documentation

◆ hash_any()

static Datum hash_any ( const unsigned char *  k,
int  keylen 
)
inlinestatic

Definition at line 31 of file hashfn.h.

32{
33 return UInt32GetDatum(hash_bytes(k, keylen));
34}
hash_bytes
uint32 hash_bytes(const unsigned char *k, int keylen)
Definition: hashfn.c:146
UInt32GetDatum
static Datum UInt32GetDatum(uint32 X)
Definition: postgres.h:237

References hash_bytes(), and UInt32GetDatum().

Referenced by bernoulli_nextsampletuple(), bms_hash_value(), cfunc_hash(), ChooseTablespace(), citext_hash(), hash_ltree(), hash_numeric(), hashbpchar(), hashfloat4(), hashfloat8(), hashinet(), hashmacaddr(), hashmacaddr8(), hashname(), hashoidvector(), hashtext(), hashtid(), hashvarlena(), hstore_hash(), JsonbHashScalarValue(), lexeme_hash(), make_text_key(), namehashfast(), notification_hash(), sepgsql_avc_hash(), system_nextsampleblock(), uuid_hash(), and varstr_abbrev_convert().

◆ hash_any_extended()

static Datum hash_any_extended ( const unsigned char *  k,
int  keylen,
uint64  seed 
)
inlinestatic

Definition at line 37 of file hashfn.h.

38{
39 return UInt64GetDatum(hash_bytes_extended(k, keylen, seed));
40}
hash_bytes_extended
uint64 hash_bytes_extended(const unsigned char *k, int keylen, uint64 seed)
Definition: hashfn.c:372
UInt64GetDatum
static Datum UInt64GetDatum(uint64 X)
Definition: postgres.h:441

References hash_bytes_extended(), and UInt64GetDatum().

Referenced by AppendJumbleInternal(), citext_hash_extended(), DoJumble(), hash_ltree_extended(), hash_numeric_extended(), hashbpcharextended(), hashfloat4extended(), hashfloat8extended(), hashinetextended(), hashmacaddr8extended(), hashmacaddrextended(), hashnameextended(), hashoidvectorextended(), hashtextextended(), hashtidextended(), hashvarlenaextended(), hstore_hash_extended(), JsonbHashScalarValueExtended(), k_hashes(), and uuid_hash_extended().

◆ hash_bytes()

uint32 hash_bytes ( const unsigned char *  k,
int  keylen 
)

Definition at line 146 of file hashfn.c.

147{
148 uint32 a,
149 b,
150 c,
151 len;
152
153 /* Set up the internal state */
154 len = keylen;
155 a = b = c = 0x9e3779b9 + len + 3923095;
156
157 /* If the source pointer is word-aligned, we use word-wide fetches */
158 if (((uintptr_t) k & UINT32_ALIGN_MASK) == 0)
159 {
160 /* Code path for aligned source data */
161 const uint32 *ka = (const uint32 *) k;
162
163 /* handle most of the key */
164 while (len >= 12)
165 {
166 a += ka[0];
167 b += ka[1];
168 c += ka[2];
169 mix(a, b, c);
170 ka += 3;
171 len -= 12;
172 }
173
174 /* handle the last 11 bytes */
175 k = (const unsigned char *) ka;
176#ifdef WORDS_BIGENDIAN
177 switch (len)
178 {
179 case 11:
180 c += ((uint32) k[10] << 8);
181 /* fall through */
182 case 10:
183 c += ((uint32) k[9] << 16);
184 /* fall through */
185 case 9:
186 c += ((uint32) k[8] << 24);
187 /* fall through */
188 case 8:
189 /* the lowest byte of c is reserved for the length */
190 b += ka[1];
191 a += ka[0];
192 break;
193 case 7:
194 b += ((uint32) k[6] << 8);
195 /* fall through */
196 case 6:
197 b += ((uint32) k[5] << 16);
198 /* fall through */
199 case 5:
200 b += ((uint32) k[4] << 24);
201 /* fall through */
202 case 4:
203 a += ka[0];
204 break;
205 case 3:
206 a += ((uint32) k[2] << 8);
207 /* fall through */
208 case 2:
209 a += ((uint32) k[1] << 16);
210 /* fall through */
211 case 1:
212 a += ((uint32) k[0] << 24);
213 /* case 0: nothing left to add */
214 }
215#else /* !WORDS_BIGENDIAN */
216 switch (len)
217 {
218 case 11:
219 c += ((uint32) k[10] << 24);
220 /* fall through */
221 case 10:
222 c += ((uint32) k[9] << 16);
223 /* fall through */
224 case 9:
225 c += ((uint32) k[8] << 8);
226 /* fall through */
227 case 8:
228 /* the lowest byte of c is reserved for the length */
229 b += ka[1];
230 a += ka[0];
231 break;
232 case 7:
233 b += ((uint32) k[6] << 16);
234 /* fall through */
235 case 6:
236 b += ((uint32) k[5] << 8);
237 /* fall through */
238 case 5:
239 b += k[4];
240 /* fall through */
241 case 4:
242 a += ka[0];
243 break;
244 case 3:
245 a += ((uint32) k[2] << 16);
246 /* fall through */
247 case 2:
248 a += ((uint32) k[1] << 8);
249 /* fall through */
250 case 1:
251 a += k[0];
252 /* case 0: nothing left to add */
253 }
254#endif /* WORDS_BIGENDIAN */
255 }
256 else
257 {
258 /* Code path for non-aligned source data */
259
260 /* handle most of the key */
261 while (len >= 12)
262 {
263#ifdef WORDS_BIGENDIAN
264 a += (k[3] + ((uint32) k[2] << 8) + ((uint32) k[1] << 16) + ((uint32) k[0] << 24));
265 b += (k[7] + ((uint32) k[6] << 8) + ((uint32) k[5] << 16) + ((uint32) k[4] << 24));
266 c += (k[11] + ((uint32) k[10] << 8) + ((uint32) k[9] << 16) + ((uint32) k[8] << 24));
267#else /* !WORDS_BIGENDIAN */
268 a += (k[0] + ((uint32) k[1] << 8) + ((uint32) k[2] << 16) + ((uint32) k[3] << 24));
269 b += (k[4] + ((uint32) k[5] << 8) + ((uint32) k[6] << 16) + ((uint32) k[7] << 24));
270 c += (k[8] + ((uint32) k[9] << 8) + ((uint32) k[10] << 16) + ((uint32) k[11] << 24));
271#endif /* WORDS_BIGENDIAN */
272 mix(a, b, c);
273 k += 12;
274 len -= 12;
275 }
276
277 /* handle the last 11 bytes */
278#ifdef WORDS_BIGENDIAN
279 switch (len)
280 {
281 case 11:
282 c += ((uint32) k[10] << 8);
283 /* fall through */
284 case 10:
285 c += ((uint32) k[9] << 16);
286 /* fall through */
287 case 9:
288 c += ((uint32) k[8] << 24);
289 /* fall through */
290 case 8:
291 /* the lowest byte of c is reserved for the length */
292 b += k[7];
293 /* fall through */
294 case 7:
295 b += ((uint32) k[6] << 8);
296 /* fall through */
297 case 6:
298 b += ((uint32) k[5] << 16);
299 /* fall through */
300 case 5:
301 b += ((uint32) k[4] << 24);
302 /* fall through */
303 case 4:
304 a += k[3];
305 /* fall through */
306 case 3:
307 a += ((uint32) k[2] << 8);
308 /* fall through */
309 case 2:
310 a += ((uint32) k[1] << 16);
311 /* fall through */
312 case 1:
313 a += ((uint32) k[0] << 24);
314 /* case 0: nothing left to add */
315 }
316#else /* !WORDS_BIGENDIAN */
317 switch (len)
318 {
319 case 11:
320 c += ((uint32) k[10] << 24);
321 /* fall through */
322 case 10:
323 c += ((uint32) k[9] << 16);
324 /* fall through */
325 case 9:
326 c += ((uint32) k[8] << 8);
327 /* fall through */
328 case 8:
329 /* the lowest byte of c is reserved for the length */
330 b += ((uint32) k[7] << 24);
331 /* fall through */
332 case 7:
333 b += ((uint32) k[6] << 16);
334 /* fall through */
335 case 6:
336 b += ((uint32) k[5] << 8);
337 /* fall through */
338 case 5:
339 b += k[4];
340 /* fall through */
341 case 4:
342 a += ((uint32) k[3] << 24);
343 /* fall through */
344 case 3:
345 a += ((uint32) k[2] << 16);
346 /* fall through */
347 case 2:
348 a += ((uint32) k[1] << 8);
349 /* fall through */
350 case 1:
351 a += k[0];
352 /* case 0: nothing left to add */
353 }
354#endif /* WORDS_BIGENDIAN */
355 }
356
357 final(a, b, c);
358
359 /* report the result */
360 return c;
361}
uint32
uint32_t uint32
Definition: c.h:502
UINT32_ALIGN_MASK
#define UINT32_ALIGN_MASK
Definition: hashfn.c:46
mix
#define mix(a, b, c)
Definition: hashfn.c:82
b
int b
Definition: isn.c:74
a
int a
Definition: isn.c:73
len
const void size_t len
Definition: pg_crc32c_sse42.c:28
c
char * c
Definition: preproc-cursor.c:31

References a, b, len, mix, and UINT32_ALIGN_MASK.

Referenced by datum_image_hash(), hash_any(), hash_string_pointer(), json_unique_hash(), missing_hash(), string_hash(), and tag_hash().

◆ hash_bytes_extended()

uint64 hash_bytes_extended ( const unsigned char *  k,
int  keylen,
uint64  seed 
)

Definition at line 372 of file hashfn.c.

373{
374 uint32 a,
375 b,
376 c,
377 len;
378
379 /* Set up the internal state */
380 len = keylen;
381 a = b = c = 0x9e3779b9 + len + 3923095;
382
383 /* If the seed is non-zero, use it to perturb the internal state. */
384 if (seed != 0)
385 {
386 /*
387 * In essence, the seed is treated as part of the data being hashed,
388 * but for simplicity, we pretend that it's padded with four bytes of
389 * zeroes so that the seed constitutes a 12-byte chunk.
390 */
391 a += (uint32) (seed >> 32);
392 b += (uint32) seed;
393 mix(a, b, c);
394 }
395
396 /* If the source pointer is word-aligned, we use word-wide fetches */
397 if (((uintptr_t) k & UINT32_ALIGN_MASK) == 0)
398 {
399 /* Code path for aligned source data */
400 const uint32 *ka = (const uint32 *) k;
401
402 /* handle most of the key */
403 while (len >= 12)
404 {
405 a += ka[0];
406 b += ka[1];
407 c += ka[2];
408 mix(a, b, c);
409 ka += 3;
410 len -= 12;
411 }
412
413 /* handle the last 11 bytes */
414 k = (const unsigned char *) ka;
415#ifdef WORDS_BIGENDIAN
416 switch (len)
417 {
418 case 11:
419 c += ((uint32) k[10] << 8);
420 /* fall through */
421 case 10:
422 c += ((uint32) k[9] << 16);
423 /* fall through */
424 case 9:
425 c += ((uint32) k[8] << 24);
426 /* fall through */
427 case 8:
428 /* the lowest byte of c is reserved for the length */
429 b += ka[1];
430 a += ka[0];
431 break;
432 case 7:
433 b += ((uint32) k[6] << 8);
434 /* fall through */
435 case 6:
436 b += ((uint32) k[5] << 16);
437 /* fall through */
438 case 5:
439 b += ((uint32) k[4] << 24);
440 /* fall through */
441 case 4:
442 a += ka[0];
443 break;
444 case 3:
445 a += ((uint32) k[2] << 8);
446 /* fall through */
447 case 2:
448 a += ((uint32) k[1] << 16);
449 /* fall through */
450 case 1:
451 a += ((uint32) k[0] << 24);
452 /* case 0: nothing left to add */
453 }
454#else /* !WORDS_BIGENDIAN */
455 switch (len)
456 {
457 case 11:
458 c += ((uint32) k[10] << 24);
459 /* fall through */
460 case 10:
461 c += ((uint32) k[9] << 16);
462 /* fall through */
463 case 9:
464 c += ((uint32) k[8] << 8);
465 /* fall through */
466 case 8:
467 /* the lowest byte of c is reserved for the length */
468 b += ka[1];
469 a += ka[0];
470 break;
471 case 7:
472 b += ((uint32) k[6] << 16);
473 /* fall through */
474 case 6:
475 b += ((uint32) k[5] << 8);
476 /* fall through */
477 case 5:
478 b += k[4];
479 /* fall through */
480 case 4:
481 a += ka[0];
482 break;
483 case 3:
484 a += ((uint32) k[2] << 16);
485 /* fall through */
486 case 2:
487 a += ((uint32) k[1] << 8);
488 /* fall through */
489 case 1:
490 a += k[0];
491 /* case 0: nothing left to add */
492 }
493#endif /* WORDS_BIGENDIAN */
494 }
495 else
496 {
497 /* Code path for non-aligned source data */
498
499 /* handle most of the key */
500 while (len >= 12)
501 {
502#ifdef WORDS_BIGENDIAN
503 a += (k[3] + ((uint32) k[2] << 8) + ((uint32) k[1] << 16) + ((uint32) k[0] << 24));
504 b += (k[7] + ((uint32) k[6] << 8) + ((uint32) k[5] << 16) + ((uint32) k[4] << 24));
505 c += (k[11] + ((uint32) k[10] << 8) + ((uint32) k[9] << 16) + ((uint32) k[8] << 24));
506#else /* !WORDS_BIGENDIAN */
507 a += (k[0] + ((uint32) k[1] << 8) + ((uint32) k[2] << 16) + ((uint32) k[3] << 24));
508 b += (k[4] + ((uint32) k[5] << 8) + ((uint32) k[6] << 16) + ((uint32) k[7] << 24));
509 c += (k[8] + ((uint32) k[9] << 8) + ((uint32) k[10] << 16) + ((uint32) k[11] << 24));
510#endif /* WORDS_BIGENDIAN */
511 mix(a, b, c);
512 k += 12;
513 len -= 12;
514 }
515
516 /* handle the last 11 bytes */
517#ifdef WORDS_BIGENDIAN
518 switch (len)
519 {
520 case 11:
521 c += ((uint32) k[10] << 8);
522 /* fall through */
523 case 10:
524 c += ((uint32) k[9] << 16);
525 /* fall through */
526 case 9:
527 c += ((uint32) k[8] << 24);
528 /* fall through */
529 case 8:
530 /* the lowest byte of c is reserved for the length */
531 b += k[7];
532 /* fall through */
533 case 7:
534 b += ((uint32) k[6] << 8);
535 /* fall through */
536 case 6:
537 b += ((uint32) k[5] << 16);
538 /* fall through */
539 case 5:
540 b += ((uint32) k[4] << 24);
541 /* fall through */
542 case 4:
543 a += k[3];
544 /* fall through */
545 case 3:
546 a += ((uint32) k[2] << 8);
547 /* fall through */
548 case 2:
549 a += ((uint32) k[1] << 16);
550 /* fall through */
551 case 1:
552 a += ((uint32) k[0] << 24);
553 /* case 0: nothing left to add */
554 }
555#else /* !WORDS_BIGENDIAN */
556 switch (len)
557 {
558 case 11:
559 c += ((uint32) k[10] << 24);
560 /* fall through */
561 case 10:
562 c += ((uint32) k[9] << 16);
563 /* fall through */
564 case 9:
565 c += ((uint32) k[8] << 8);
566 /* fall through */
567 case 8:
568 /* the lowest byte of c is reserved for the length */
569 b += ((uint32) k[7] << 24);
570 /* fall through */
571 case 7:
572 b += ((uint32) k[6] << 16);
573 /* fall through */
574 case 6:
575 b += ((uint32) k[5] << 8);
576 /* fall through */
577 case 5:
578 b += k[4];
579 /* fall through */
580 case 4:
581 a += ((uint32) k[3] << 24);
582 /* fall through */
583 case 3:
584 a += ((uint32) k[2] << 16);
585 /* fall through */
586 case 2:
587 a += ((uint32) k[1] << 8);
588 /* fall through */
589 case 1:
590 a += k[0];
591 /* case 0: nothing left to add */
592 }
593#endif /* WORDS_BIGENDIAN */
594 }
595
596 final(a, b, c);
597
598 /* report the result */
599 return ((uint64) b << 32) | c;
600}
uint64
uint64_t uint64
Definition: c.h:503

References a, b, len, mix, and UINT32_ALIGN_MASK.

Referenced by hash_any_extended().

◆ hash_bytes_uint32()

uint32 hash_bytes_uint32 ( uint32  k)

Definition at line 610 of file hashfn.c.

611{
612 uint32 a,
613 b,
614 c;
615
616 a = b = c = 0x9e3779b9 + (uint32) sizeof(uint32) + 3923095;
617 a += k;
618
619 final(a, b, c);
620
621 /* report the result */
622 return c;
623}

References a, and b.

Referenced by hash_uint32(), hashagg_spill_tuple(), json_unique_hash(), and uint32_hash().

◆ hash_bytes_uint32_extended()

uint64 hash_bytes_uint32_extended ( uint32  k,
uint64  seed 
)

Definition at line 631 of file hashfn.c.

632{
633 uint32 a,
634 b,
635 c;
636
637 a = b = c = 0x9e3779b9 + (uint32) sizeof(uint32) + 3923095;
638
639 if (seed != 0)
640 {
641 a += (uint32) (seed >> 32);
642 b += (uint32) seed;
643 mix(a, b, c);
644 }
645
646 a += k;
647
648 final(a, b, c);
649
650 /* report the result */
651 return ((uint64) b << 32) | c;
652}

References a, b, and mix.

Referenced by bloom_add_value(), bloom_contains_value(), and hash_uint32_extended().

◆ hash_combine()

static uint32 hash_combine ( uint32  a,
uint32  b 
)
inlinestatic

Definition at line 68 of file hashfn.h.

69{
70 a ^= b + 0x9e3779b9 + (a << 6) + (a >> 2);
71 return a;
72}

References a, and b.

Referenced by cfunc_hash(), hash_resource_elem(), and hashRowType().

◆ hash_combine64()

static uint64 hash_combine64 ( uint64  a,
uint64  b 
)
inlinestatic

Definition at line 80 of file hashfn.h.

81{
82 /* 0x49a0f4dd15e5a8e3 is 64bit random data */
83 a ^= b + UINT64CONST(0x49a0f4dd15e5a8e3) + (a << 54) + (a >> 7);
84 return a;
85}

References a, b, and UINT64CONST.

Referenced by compute_partition_hash_value(), hash_resource_elem(), and satisfies_hash_partition().

◆ hash_uint32()

static Datum hash_uint32 ( uint32  k)
inlinestatic

Definition at line 43 of file hashfn.h.

44{
45 return UInt32GetDatum(hash_bytes_uint32(k));
46}
hash_bytes_uint32
uint32 hash_bytes_uint32(uint32 k)
Definition: hashfn.c:610

References hash_bytes_uint32(), and UInt32GetDatum().

Referenced by hash_multirange(), hash_range(), hashbool(), hashchar(), hashcid(), hashdate(), hashenum(), hashint2(), hashint4(), hashint8(), hashoid(), hashRowType(), hashxid(), macaddr_abbrev_convert(), network_abbrev_convert(), timetz_hash(), uuid_abbrev_convert(), and varstr_abbrev_convert().

◆ hash_uint32_extended()

static Datum hash_uint32_extended ( uint32  k,
uint64  seed 
)
inlinestatic

Definition at line 49 of file hashfn.h.

50{
51 return UInt64GetDatum(hash_bytes_uint32_extended(k, seed));
52}
hash_bytes_uint32_extended
uint64 hash_bytes_uint32_extended(uint32 k, uint64 seed)
Definition: hashfn.c:631

References hash_bytes_uint32_extended(), and UInt64GetDatum().

Referenced by hash_aclitem_extended(), hash_multirange_extended(), hash_range_extended(), hashboolextended(), hashcharextended(), hashcidextended(), hashdateextended(), hashenumextended(), hashint2extended(), hashint4extended(), hashint8extended(), hashoidextended(), hashxidextended(), and timetz_hash_extended().

◆ murmurhash32()

static uint32 murmurhash32 ( uint32  data)
inlinestatic

Definition at line 92 of file hashfn.h.

93{
94 uint32 h = data;
95
96 h ^= h >> 16;
97 h *= 0x85ebca6b;
98 h ^= h >> 13;
99 h *= 0xc2b2ae35;
100 h ^= h >> 16;
101 return h;
102}
data
const void * data
Definition: pg_crc32c_sse42.c:27

References data.

Referenced by BuildTupleHashTable(), charhashfast(), hash_resource_elem(), int2hashfast(), int4hashfast(), MemoizeHash_hash(), and TupleHashTableHash_internal().

◆ murmurhash64()

static uint64 murmurhash64 ( uint64  data)
inlinestatic

Definition at line 106 of file hashfn.h.

107{
108 uint64 h = data;
109
110 h ^= h >> 33;
111 h *= 0xff51afd7ed558ccd;
112 h ^= h >> 33;
113 h *= 0xc4ceb9fe1a85ec53;
114 h ^= h >> 33;
115
116 return h;
117}

References data.

Referenced by hash_resource_elem().

◆ string_hash()

uint32 string_hash ( const void *  key,
Size  keysize 
)

Definition at line 660 of file hashfn.c.

661{
662 /*
663 * If the string exceeds keysize-1 bytes, we want to hash only that many,
664 * because when it is copied into the hash table it will be truncated at
665 * that length.
666 */
667 Size s_len = strlen((const char *) key);
668
669 s_len = Min(s_len, keysize - 1);
670 return hash_bytes((const unsigned char *) key, (int) s_len);
671}
Min
#define Min(x, y)
Definition: c.h:975
Size
size_t Size
Definition: c.h:576
hash_bytes
uint32 hash_bytes(const unsigned char *k, int keylen)
Definition: hashfn.c:146

References hash_bytes(), sort-test::key, and Min.

Referenced by dshash_strhash(), and hash_create().

◆ tag_hash()

uint32 tag_hash ( const void *  key,
Size  keysize 
)

Definition at line 677 of file hashfn.c.

678{
679 return hash_bytes((const unsigned char *) key, (int) keysize);
680}

References hash_bytes(), and sort-test::key.

Referenced by dshash_memhash(), and hash_create().

◆ uint32_hash()

uint32 uint32_hash ( const void *  key,
Size  keysize 
)

Definition at line 688 of file hashfn.c.

689{
690 Assert(keysize == sizeof(uint32));
691 return hash_bytes_uint32(*((const uint32 *) key));
692}
hash_bytes_uint32
uint32 hash_bytes_uint32(uint32 k)
Definition: hashfn.c:610
Assert
Assert(PointerIsAligned(start, uint64))

References Assert(), hash_bytes_uint32(), and sort-test::key.

Referenced by hash_create().