PostgreSQL Source Code  git master
hashutils.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)
 

Functions

Datum hash_any (const unsigned char *k, int keylen)
 
Datum hash_any_extended (const unsigned char *k, int keylen, uint64 seed)
 
Datum hash_uint32 (uint32 k)
 
Datum hash_uint32_extended (uint32 k, uint64 seed)
 
static uint32 hash_combine (uint32 a, uint32 b)
 
static uint64 hash_combine64 (uint64 a, uint64 b)
 
static uint32 murmurhash32 (uint32 data)
 

Macro Definition Documentation

◆ ROTATE_HIGH_AND_LOW_32BITS

#define ROTATE_HIGH_AND_LOW_32BITS (   v)
Value:
((((v) << 1) & UINT64CONST(0xfffffffefffffffe)) | \
(((v) >> 31) & UINT64CONST(0x100000001)))

Definition at line 18 of file hashutils.h.

Referenced by hash_range_extended(), and JsonbHashScalarValueExtended().

Function Documentation

◆ hash_any()

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

Definition at line 148 of file hashfn.c.

References mix, UINT32_ALIGN_MASK, and UInt32GetDatum.

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

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

◆ hash_any_extended()

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

Definition at line 374 of file hashfn.c.

References mix, PG_RETURN_UINT64, and UINT32_ALIGN_MASK.

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

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

◆ hash_combine()

static uint32 hash_combine ( uint32  a,
uint32  b 
)
inlinestatic

Definition at line 36 of file hashutils.h.

Referenced by hashTupleDesc().

37 {
38  a ^= b + 0x9e3779b9 + (a << 6) + (a >> 2);
39  return a;
40 }

◆ hash_combine64()

static uint64 hash_combine64 ( uint64  a,
uint64  b 
)
inlinestatic

Definition at line 48 of file hashutils.h.

Referenced by compute_partition_hash_value(), and satisfies_hash_partition().

49 {
50  /* 0x49a0f4dd15e5a8e3 is 64bit random data */
51  a ^= b + UINT64CONST(0x49a0f4dd15e5a8e3) + (a << 54) + (a >> 7);
52  return a;
53 }

◆ hash_uint32()

Datum hash_uint32 ( uint32  k)

Definition at line 613 of file hashfn.c.

References UInt32GetDatum.

Referenced by hash_range(), hashchar(), hashenum(), hashint2(), hashint4(), hashint8(), hashoid(), hashTupleDesc(), macaddr_abbrev_convert(), network_abbrev_convert(), numeric_cmp_abbrev(), timetz_hash(), uint32_hash(), uuid_abbrev_convert(), and varstr_abbrev_convert().

614 {
615  uint32 a,
616  b,
617  c;
618 
619  a = b = c = 0x9e3779b9 + (uint32) sizeof(uint32) + 3923095;
620  a += k;
621 
622  final(a, b, c);
623 
624  /* report the result */
625  return UInt32GetDatum(c);
626 }
char * c
unsigned int uint32
Definition: c.h:359
#define UInt32GetDatum(X)
Definition: postgres.h:493

◆ hash_uint32_extended()

Datum hash_uint32_extended ( uint32  k,
uint64  seed 
)

Definition at line 634 of file hashfn.c.

References mix, and PG_RETURN_UINT64.

Referenced by hash_aclitem_extended(), hash_range_extended(), hashcharextended(), hashenumextended(), hashint2extended(), hashint4extended(), hashint8extended(), hashoidextended(), and timetz_hash_extended().

635 {
636  uint32 a,
637  b,
638  c;
639 
640  a = b = c = 0x9e3779b9 + (uint32) sizeof(uint32) + 3923095;
641 
642  if (seed != 0)
643  {
644  a += (uint32) (seed >> 32);
645  b += (uint32) seed;
646  mix(a, b, c);
647  }
648 
649  a += k;
650 
651  final(a, b, c);
652 
653  /* report the result */
654  PG_RETURN_UINT64(((uint64) b << 32) | c);
655 }
#define mix(a, b, c)
Definition: hashfn.c:84
#define PG_RETURN_UINT64(x)
Definition: fmgr.h:358
char * c
unsigned int uint32
Definition: c.h:359

◆ murmurhash32()

static uint32 murmurhash32 ( uint32  data)
inlinestatic

Definition at line 60 of file hashutils.h.

Referenced by BuildTupleHashTableExt(), charhashfast(), int2hashfast(), int4hashfast(), and TupleHashTableHash().

61 {
62  uint32 h = data;
63 
64  h ^= h >> 16;
65  h *= 0x85ebca6b;
66  h ^= h >> 13;
67  h *= 0xc2b2ae35;
68  h ^= h >> 16;
69  return h;
70 }
unsigned int uint32
Definition: c.h:359