PostgreSQL Source Code  git master
hashfn.c File Reference
#include "postgres.h"
#include "fmgr.h"
#include "nodes/bitmapset.h"
#include "utils/hashutils.h"
#include "utils/hsearch.h"
Include dependency graph for hashfn.c:

Go to the source code of this file.

Macros

#define UINT32_ALIGN_MASK   (sizeof(uint32) - 1)
 
#define rot(x, k)   (((x)<<(k)) | ((x)>>(32-(k))))
 
#define mix(a, b, c)
 
#define final(a, b, c)
 

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)
 
uint32 string_hash (const void *key, Size keysize)
 
uint32 tag_hash (const void *key, Size keysize)
 
uint32 uint32_hash (const void *key, Size keysize)
 
uint32 bitmap_hash (const void *key, Size keysize)
 
int bitmap_match (const void *key1, const void *key2, Size keysize)
 

Macro Definition Documentation

◆ final

#define final (   a,
  b,
  c 
)
Value:
{ \
c ^= b; c -= rot(b,14); \
a ^= c; a -= rot(c,11); \
b ^= a; b -= rot(a,25); \
c ^= b; c -= rot(b,16); \
a ^= c; a -= rot(c, 4); \
b ^= a; b -= rot(a,14); \
c ^= b; c -= rot(b,24); \
}
char * c
#define rot(x, k)
Definition: hashfn.c:50

Definition at line 118 of file hashfn.c.

Referenced by _bt_bestsplitloc().

◆ mix

#define mix (   a,
  b,
  c 
)
Value:
{ \
a -= c; a ^= rot(c, 4); c += b; \
b -= a; b ^= rot(a, 6); a += c; \
c -= b; c ^= rot(b, 8); b += a; \
a -= c; a ^= rot(c,16); c += b; \
b -= a; b ^= rot(a,19); a += c; \
c -= b; c ^= rot(b, 4); b += a; \
}
char * c
#define rot(x, k)
Definition: hashfn.c:50

Definition at line 84 of file hashfn.c.

Referenced by hash_any(), hash_any_extended(), hash_uint32_extended(), pgp_cfb_decrypt(), and pgp_cfb_encrypt().

◆ rot

#define rot (   x,
 
)    (((x)<<(k)) | ((x)>>(32-(k))))

Definition at line 50 of file hashfn.c.

◆ UINT32_ALIGN_MASK

#define UINT32_ALIGN_MASK   (sizeof(uint32) - 1)

Definition at line 47 of file hashfn.c.

Referenced by hash_any(), and hash_any_extended().

Function Documentation

◆ bitmap_hash()

uint32 bitmap_hash ( const void *  key,
Size  keysize 
)

Definition at line 705 of file hashfn.c.

References Assert, and bms_hash_value().

Referenced by build_join_rel_hash().

706 {
707  Assert(keysize == sizeof(Bitmapset *));
708  return bms_hash_value(*((const Bitmapset *const *) key));
709 }
uint32 bms_hash_value(const Bitmapset *a)
Definition: bitmapset.c:1154
#define Assert(condition)
Definition: c.h:733

◆ bitmap_match()

int bitmap_match ( const void *  key1,
const void *  key2,
Size  keysize 
)

Definition at line 715 of file hashfn.c.

References Assert, and bms_equal().

Referenced by build_join_rel_hash().

716 {
717  Assert(keysize == sizeof(Bitmapset *));
718  return !bms_equal(*((const Bitmapset *const *) key1),
719  *((const Bitmapset *const *) key2));
720 }
#define Assert(condition)
Definition: c.h:733
bool bms_equal(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:94

◆ 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_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

◆ string_hash()

uint32 string_hash ( const void *  key,
Size  keysize 
)

Definition at line 663 of file hashfn.c.

References DatumGetUInt32, hash_any(), and Min.

Referenced by hash_create().

664 {
665  /*
666  * If the string exceeds keysize-1 bytes, we want to hash only that many,
667  * because when it is copied into the hash table it will be truncated at
668  * that length.
669  */
670  Size s_len = strlen((const char *) key);
671 
672  s_len = Min(s_len, keysize - 1);
673  return DatumGetUInt32(hash_any((const unsigned char *) key,
674  (int) s_len));
675 }
#define DatumGetUInt32(X)
Definition: postgres.h:486
Datum hash_any(const unsigned char *k, int keylen)
Definition: hashfn.c:148
#define Min(x, y)
Definition: c.h:905
size_t Size
Definition: c.h:467

◆ tag_hash()

uint32 tag_hash ( const void *  key,
Size  keysize 
)

Definition at line 681 of file hashfn.c.

References DatumGetUInt32, and hash_any().

Referenced by dshash_memhash(), and hash_create().

682 {
683  return DatumGetUInt32(hash_any((const unsigned char *) key,
684  (int) keysize));
685 }
#define DatumGetUInt32(X)
Definition: postgres.h:486
Datum hash_any(const unsigned char *k, int keylen)
Definition: hashfn.c:148

◆ uint32_hash()

uint32 uint32_hash ( const void *  key,
Size  keysize 
)

Definition at line 693 of file hashfn.c.

References Assert, DatumGetUInt32, and hash_uint32().

Referenced by hash_create().

694 {
695  Assert(keysize == sizeof(uint32));
696  return DatumGetUInt32(hash_uint32(*((const uint32 *) key)));
697 }
#define DatumGetUInt32(X)
Definition: postgres.h:486
Datum hash_uint32(uint32 k)
Definition: hashfn.c:613
unsigned int uint32
Definition: c.h:359
#define Assert(condition)
Definition: c.h:733