PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
hashfunc.c File Reference
#include "postgres.h"
#include "access/hash.h"
#include "utils/builtins.h"
Include dependency graph for hashfunc.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 hashchar (PG_FUNCTION_ARGS)
 
Datum hashint2 (PG_FUNCTION_ARGS)
 
Datum hashint4 (PG_FUNCTION_ARGS)
 
Datum hashint8 (PG_FUNCTION_ARGS)
 
Datum hashoid (PG_FUNCTION_ARGS)
 
Datum hashenum (PG_FUNCTION_ARGS)
 
Datum hashfloat4 (PG_FUNCTION_ARGS)
 
Datum hashfloat8 (PG_FUNCTION_ARGS)
 
Datum hashoidvector (PG_FUNCTION_ARGS)
 
Datum hashname (PG_FUNCTION_ARGS)
 
Datum hashtext (PG_FUNCTION_ARGS)
 
Datum hashvarlena (PG_FUNCTION_ARGS)
 
Datum hash_any (register const unsigned char *k, register int keylen)
 
Datum hash_uint32 (uint32 k)
 

Macro Definition Documentation

#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); \
}
#define rot(x, k)
Definition: hashfunc.c:209
char * c

Definition at line 277 of file hashfunc.c.

#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; \
}
#define rot(x, k)
Definition: hashfunc.c:209
char * c

Definition at line 243 of file hashfunc.c.

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

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

Definition at line 209 of file hashfunc.c.

#define UINT32_ALIGN_MASK   (sizeof(uint32) - 1)

Definition at line 206 of file hashfunc.c.

Referenced by hash_any().

Function Documentation

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

Definition at line 307 of file hashfunc.c.

References mix, UINT32_ALIGN_MASK, and UInt32GetDatum.

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

308 {
309  register uint32 a,
310  b,
311  c,
312  len;
313 
314  /* Set up the internal state */
315  len = keylen;
316  a = b = c = 0x9e3779b9 + len + 3923095;
317 
318  /* If the source pointer is word-aligned, we use word-wide fetches */
319  if (((uintptr_t) k & UINT32_ALIGN_MASK) == 0)
320  {
321  /* Code path for aligned source data */
322  register const uint32 *ka = (const uint32 *) k;
323 
324  /* handle most of the key */
325  while (len >= 12)
326  {
327  a += ka[0];
328  b += ka[1];
329  c += ka[2];
330  mix(a, b, c);
331  ka += 3;
332  len -= 12;
333  }
334 
335  /* handle the last 11 bytes */
336  k = (const unsigned char *) ka;
337 #ifdef WORDS_BIGENDIAN
338  switch (len)
339  {
340  case 11:
341  c += ((uint32) k[10] << 8);
342  /* fall through */
343  case 10:
344  c += ((uint32) k[9] << 16);
345  /* fall through */
346  case 9:
347  c += ((uint32) k[8] << 24);
348  /* the lowest byte of c is reserved for the length */
349  /* fall through */
350  case 8:
351  b += ka[1];
352  a += ka[0];
353  break;
354  case 7:
355  b += ((uint32) k[6] << 8);
356  /* fall through */
357  case 6:
358  b += ((uint32) k[5] << 16);
359  /* fall through */
360  case 5:
361  b += ((uint32) k[4] << 24);
362  /* fall through */
363  case 4:
364  a += ka[0];
365  break;
366  case 3:
367  a += ((uint32) k[2] << 8);
368  /* fall through */
369  case 2:
370  a += ((uint32) k[1] << 16);
371  /* fall through */
372  case 1:
373  a += ((uint32) k[0] << 24);
374  /* case 0: nothing left to add */
375  }
376 #else /* !WORDS_BIGENDIAN */
377  switch (len)
378  {
379  case 11:
380  c += ((uint32) k[10] << 24);
381  /* fall through */
382  case 10:
383  c += ((uint32) k[9] << 16);
384  /* fall through */
385  case 9:
386  c += ((uint32) k[8] << 8);
387  /* the lowest byte of c is reserved for the length */
388  /* fall through */
389  case 8:
390  b += ka[1];
391  a += ka[0];
392  break;
393  case 7:
394  b += ((uint32) k[6] << 16);
395  /* fall through */
396  case 6:
397  b += ((uint32) k[5] << 8);
398  /* fall through */
399  case 5:
400  b += k[4];
401  /* fall through */
402  case 4:
403  a += ka[0];
404  break;
405  case 3:
406  a += ((uint32) k[2] << 16);
407  /* fall through */
408  case 2:
409  a += ((uint32) k[1] << 8);
410  /* fall through */
411  case 1:
412  a += k[0];
413  /* case 0: nothing left to add */
414  }
415 #endif /* WORDS_BIGENDIAN */
416  }
417  else
418  {
419  /* Code path for non-aligned source data */
420 
421  /* handle most of the key */
422  while (len >= 12)
423  {
424 #ifdef WORDS_BIGENDIAN
425  a += (k[3] + ((uint32) k[2] << 8) + ((uint32) k[1] << 16) + ((uint32) k[0] << 24));
426  b += (k[7] + ((uint32) k[6] << 8) + ((uint32) k[5] << 16) + ((uint32) k[4] << 24));
427  c += (k[11] + ((uint32) k[10] << 8) + ((uint32) k[9] << 16) + ((uint32) k[8] << 24));
428 #else /* !WORDS_BIGENDIAN */
429  a += (k[0] + ((uint32) k[1] << 8) + ((uint32) k[2] << 16) + ((uint32) k[3] << 24));
430  b += (k[4] + ((uint32) k[5] << 8) + ((uint32) k[6] << 16) + ((uint32) k[7] << 24));
431  c += (k[8] + ((uint32) k[9] << 8) + ((uint32) k[10] << 16) + ((uint32) k[11] << 24));
432 #endif /* WORDS_BIGENDIAN */
433  mix(a, b, c);
434  k += 12;
435  len -= 12;
436  }
437 
438  /* handle the last 11 bytes */
439 #ifdef WORDS_BIGENDIAN
440  switch (len) /* all the case statements fall through */
441  {
442  case 11:
443  c += ((uint32) k[10] << 8);
444  case 10:
445  c += ((uint32) k[9] << 16);
446  case 9:
447  c += ((uint32) k[8] << 24);
448  /* the lowest byte of c is reserved for the length */
449  case 8:
450  b += k[7];
451  case 7:
452  b += ((uint32) k[6] << 8);
453  case 6:
454  b += ((uint32) k[5] << 16);
455  case 5:
456  b += ((uint32) k[4] << 24);
457  case 4:
458  a += k[3];
459  case 3:
460  a += ((uint32) k[2] << 8);
461  case 2:
462  a += ((uint32) k[1] << 16);
463  case 1:
464  a += ((uint32) k[0] << 24);
465  /* case 0: nothing left to add */
466  }
467 #else /* !WORDS_BIGENDIAN */
468  switch (len) /* all the case statements fall through */
469  {
470  case 11:
471  c += ((uint32) k[10] << 24);
472  case 10:
473  c += ((uint32) k[9] << 16);
474  case 9:
475  c += ((uint32) k[8] << 8);
476  /* the lowest byte of c is reserved for the length */
477  case 8:
478  b += ((uint32) k[7] << 24);
479  case 7:
480  b += ((uint32) k[6] << 16);
481  case 6:
482  b += ((uint32) k[5] << 8);
483  case 5:
484  b += k[4];
485  case 4:
486  a += ((uint32) k[3] << 24);
487  case 3:
488  a += ((uint32) k[2] << 16);
489  case 2:
490  a += ((uint32) k[1] << 8);
491  case 1:
492  a += k[0];
493  /* case 0: nothing left to add */
494  }
495 #endif /* WORDS_BIGENDIAN */
496  }
497 
498  final(a, b, c);
499 
500  /* report the result */
501  return UInt32GetDatum(c);
502 }
char * c
unsigned int uint32
Definition: c.h:268
#define UInt32GetDatum(X)
Definition: postgres.h:499
#define UINT32_ALIGN_MASK
Definition: hashfunc.c:206
#define mix(a, b, c)
Definition: hashfunc.c:243
Datum hash_uint32 ( uint32  k)

Definition at line 512 of file hashfunc.c.

References UInt32GetDatum.

Referenced by BuildTupleHashTable(), hash_range(), hashchar(), hashenum(), hashint2(), hashint4(), hashint8(), hashoid(), macaddr_abbrev_convert(), pgss_hash_fn(), timetz_hash(), uint32_hash(), uuid_abbrev_convert(), and varstr_abbrev_convert().

513 {
514  register uint32 a,
515  b,
516  c;
517 
518  a = b = c = 0x9e3779b9 + (uint32) sizeof(uint32) + 3923095;
519  a += k;
520 
521  final(a, b, c);
522 
523  /* report the result */
524  return UInt32GetDatum(c);
525 }
char * c
unsigned int uint32
Definition: c.h:268
#define UInt32GetDatum(X)
Definition: postgres.h:499
Datum hashchar ( PG_FUNCTION_ARGS  )

Definition at line 44 of file hashfunc.c.

References hash_uint32(), and PG_GETARG_CHAR.

Referenced by GetCCHashEqFuncs().

45 {
46  return hash_uint32((int32) PG_GETARG_CHAR(0));
47 }
signed int int32
Definition: c.h:256
Datum hash_uint32(uint32 k)
Definition: hashfunc.c:512
#define PG_GETARG_CHAR(n)
Definition: fmgr.h:238
Datum hashenum ( PG_FUNCTION_ARGS  )

Definition at line 88 of file hashfunc.c.

References hash_uint32(), and PG_GETARG_OID.

89 {
90  return hash_uint32((uint32) PG_GETARG_OID(0));
91 }
#define PG_GETARG_OID(n)
Definition: fmgr.h:240
unsigned int uint32
Definition: c.h:268
Datum hash_uint32(uint32 k)
Definition: hashfunc.c:512
Datum hashfloat4 ( PG_FUNCTION_ARGS  )

Definition at line 94 of file hashfunc.c.

References hash_any(), PG_GETARG_FLOAT4, and PG_RETURN_UINT32.

95 {
96  float4 key = PG_GETARG_FLOAT4(0);
97  float8 key8;
98 
99  /*
100  * On IEEE-float machines, minus zero and zero have different bit patterns
101  * but should compare as equal. We must ensure that they have the same
102  * hash value, which is most reliably done this way:
103  */
104  if (key == (float4) 0)
105  PG_RETURN_UINT32(0);
106 
107  /*
108  * To support cross-type hashing of float8 and float4, we want to return
109  * the same hash value hashfloat8 would produce for an equal float8 value.
110  * So, widen the value to float8 and hash that. (We must do this rather
111  * than have hashfloat8 try to narrow its value to float4; that could fail
112  * on overflow.)
113  */
114  key8 = key;
115 
116  return hash_any((unsigned char *) &key8, sizeof(key8));
117 }
#define PG_RETURN_UINT32(x)
Definition: fmgr.h:315
double float8
Definition: c.h:381
#define PG_GETARG_FLOAT4(n)
Definition: fmgr.h:245
float float4
Definition: c.h:380
Datum hash_any(register const unsigned char *k, register int keylen)
Definition: hashfunc.c:307
Datum hashfloat8 ( PG_FUNCTION_ARGS  )

Definition at line 120 of file hashfunc.c.

References hash_any(), PG_GETARG_FLOAT8, and PG_RETURN_UINT32.

Referenced by tablesample_init().

121 {
122  float8 key = PG_GETARG_FLOAT8(0);
123 
124  /*
125  * On IEEE-float machines, minus zero and zero have different bit patterns
126  * but should compare as equal. We must ensure that they have the same
127  * hash value, which is most reliably done this way:
128  */
129  if (key == (float8) 0)
130  PG_RETURN_UINT32(0);
131 
132  return hash_any((unsigned char *) &key, sizeof(key));
133 }
#define PG_GETARG_FLOAT8(n)
Definition: fmgr.h:246
#define PG_RETURN_UINT32(x)
Definition: fmgr.h:315
double float8
Definition: c.h:381
Datum hash_any(register const unsigned char *k, register int keylen)
Definition: hashfunc.c:307
Datum hashint2 ( PG_FUNCTION_ARGS  )

Definition at line 50 of file hashfunc.c.

References hash_uint32(), and PG_GETARG_INT16.

Referenced by GetCCHashEqFuncs().

51 {
52  return hash_uint32((int32) PG_GETARG_INT16(0));
53 }
signed int int32
Definition: c.h:256
Datum hash_uint32(uint32 k)
Definition: hashfunc.c:512
#define PG_GETARG_INT16(n)
Definition: fmgr.h:236
Datum hashint4 ( PG_FUNCTION_ARGS  )

Definition at line 56 of file hashfunc.c.

References hash_uint32(), and PG_GETARG_INT32.

Referenced by GetCCHashEqFuncs().

57 {
58  return hash_uint32(PG_GETARG_INT32(0));
59 }
#define PG_GETARG_INT32(n)
Definition: fmgr.h:234
Datum hash_uint32(uint32 k)
Definition: hashfunc.c:512
Datum hashint8 ( PG_FUNCTION_ARGS  )

Definition at line 62 of file hashfunc.c.

References hash_uint32(), PG_GETARG_INT64, and val.

Referenced by interval_hash(), pg_lsn_hash(), time_hash(), timestamp_hash(), and timetz_hash().

63 {
64  /*
65  * The idea here is to produce a hash value compatible with the values
66  * produced by hashint4 and hashint2 for logically equal inputs; this is
67  * necessary to support cross-type hash joins across these input types.
68  * Since all three types are signed, we can xor the high half of the int8
69  * value if the sign is positive, or the complement of the high half when
70  * the sign is negative.
71  */
72  int64 val = PG_GETARG_INT64(0);
73  uint32 lohalf = (uint32) val;
74  uint32 hihalf = (uint32) (val >> 32);
75 
76  lohalf ^= (val >= 0) ? hihalf : ~hihalf;
77 
78  return hash_uint32(lohalf);
79 }
unsigned int uint32
Definition: c.h:268
Datum hash_uint32(uint32 k)
Definition: hashfunc.c:512
#define PG_GETARG_INT64(n)
Definition: fmgr.h:247
long val
Definition: informix.c:689
Datum hashname ( PG_FUNCTION_ARGS  )

Definition at line 144 of file hashfunc.c.

References hash_any(), NameStr, and PG_GETARG_NAME.

Referenced by GetCCHashEqFuncs().

145 {
146  char *key = NameStr(*PG_GETARG_NAME(0));
147 
148  return hash_any((unsigned char *) key, strlen(key));
149 }
Datum hash_any(register const unsigned char *k, register int keylen)
Definition: hashfunc.c:307
#define NameStr(name)
Definition: c.h:499
#define PG_GETARG_NAME(n)
Definition: fmgr.h:243
Datum hashoid ( PG_FUNCTION_ARGS  )

Definition at line 82 of file hashfunc.c.

References hash_uint32(), and PG_GETARG_OID.

Referenced by GetCCHashEqFuncs().

83 {
84  return hash_uint32((uint32) PG_GETARG_OID(0));
85 }
#define PG_GETARG_OID(n)
Definition: fmgr.h:240
unsigned int uint32
Definition: c.h:268
Datum hash_uint32(uint32 k)
Definition: hashfunc.c:512
Datum hashoidvector ( PG_FUNCTION_ARGS  )

Definition at line 136 of file hashfunc.c.

References oidvector::dim1, hash_any(), PG_GETARG_POINTER, and oidvector::values.

Referenced by GetCCHashEqFuncs().

137 {
138  oidvector *key = (oidvector *) PG_GETARG_POINTER(0);
139 
140  return hash_any((unsigned char *) key->values, key->dim1 * sizeof(Oid));
141 }
Definition: c.h:478
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:241
unsigned int Oid
Definition: postgres_ext.h:31
Oid values[FLEXIBLE_ARRAY_MEMBER]
Definition: c.h:486
int dim1
Definition: c.h:484
Datum hash_any(register const unsigned char *k, register int keylen)
Definition: hashfunc.c:307
Datum hashtext ( PG_FUNCTION_ARGS  )

Definition at line 152 of file hashfunc.c.

References hash_any(), PG_FREE_IF_COPY, PG_GETARG_TEXT_PP, result, VARDATA_ANY, and VARSIZE_ANY_EXHDR.

Referenced by GetCCHashEqFuncs().

153 {
154  text *key = PG_GETARG_TEXT_PP(0);
155  Datum result;
156 
157  /*
158  * Note: this is currently identical in behavior to hashvarlena, but keep
159  * it as a separate function in case we someday want to do something
160  * different in non-C locales. (See also hashbpchar, if so.)
161  */
162  result = hash_any((unsigned char *) VARDATA_ANY(key),
163  VARSIZE_ANY_EXHDR(key));
164 
165  /* Avoid leaking memory for toasted inputs */
166  PG_FREE_IF_COPY(key, 0);
167 
168  return result;
169 }
#define VARDATA_ANY(PTR)
Definition: postgres.h:347
return result
Definition: formatting.c:1632
#define PG_GETARG_TEXT_PP(n)
Definition: fmgr.h:273
uintptr_t Datum
Definition: postgres.h:372
Datum hash_any(register const unsigned char *k, register int keylen)
Definition: hashfunc.c:307
#define PG_FREE_IF_COPY(ptr, n)
Definition: fmgr.h:225
#define VARSIZE_ANY_EXHDR(PTR)
Definition: postgres.h:340
Definition: c.h:439
Datum hashvarlena ( PG_FUNCTION_ARGS  )

Definition at line 176 of file hashfunc.c.

References hash_any(), PG_FREE_IF_COPY, PG_GETARG_VARLENA_PP, result, VARDATA_ANY, and VARSIZE_ANY_EXHDR.

177 {
178  struct varlena *key = PG_GETARG_VARLENA_PP(0);
179  Datum result;
180 
181  result = hash_any((unsigned char *) VARDATA_ANY(key),
182  VARSIZE_ANY_EXHDR(key));
183 
184  /* Avoid leaking memory for toasted inputs */
185  PG_FREE_IF_COPY(key, 0);
186 
187  return result;
188 }
#define VARDATA_ANY(PTR)
Definition: postgres.h:347
return result
Definition: formatting.c:1632
#define PG_GETARG_VARLENA_PP(n)
Definition: fmgr.h:253
uintptr_t Datum
Definition: postgres.h:372
Datum hash_any(register const unsigned char *k, register int keylen)
Definition: hashfunc.c:307
#define PG_FREE_IF_COPY(ptr, n)
Definition: fmgr.h:225
#define VARSIZE_ANY_EXHDR(PTR)
Definition: postgres.h:340
Definition: c.h:439