PostgreSQL Source Code  git master
hashfunc.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * hashfunc.c
4  * Support functions for hash access method.
5  *
6  * Portions Copyright (c) 1996-2017, 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 "access/hash.h"
30 #include "utils/builtins.h"
31 
32 /*
33  * Datatype-specific hash functions.
34  *
35  * These support both hash indexes and hash joins.
36  *
37  * NOTE: some of these are also used by catcache operations, without
38  * any direct connection to hash indexes. Also, the common hash_any
39  * routine is also used by dynahash tables.
40  */
41 
42 /* Note: this is used for both "char" and boolean datatypes */
43 Datum
45 {
46  return hash_uint32((int32) PG_GETARG_CHAR(0));
47 }
48 
49 Datum
51 {
53 }
54 
55 Datum
57 {
58  return hash_uint32((int32) PG_GETARG_INT16(0));
59 }
60 
61 Datum
63 {
65 }
66 
67 Datum
69 {
70  return hash_uint32(PG_GETARG_INT32(0));
71 }
72 
73 Datum
75 {
77 }
78 
79 Datum
81 {
82  /*
83  * The idea here is to produce a hash value compatible with the values
84  * produced by hashint4 and hashint2 for logically equal inputs; this is
85  * necessary to support cross-type hash joins across these input types.
86  * Since all three types are signed, we can xor the high half of the int8
87  * value if the sign is positive, or the complement of the high half when
88  * the sign is negative.
89  */
90  int64 val = PG_GETARG_INT64(0);
91  uint32 lohalf = (uint32) val;
92  uint32 hihalf = (uint32) (val >> 32);
93 
94  lohalf ^= (val >= 0) ? hihalf : ~hihalf;
95 
96  return hash_uint32(lohalf);
97 }
98 
99 Datum
101 {
102  /* Same approach as hashint8 */
103  int64 val = PG_GETARG_INT64(0);
104  uint32 lohalf = (uint32) val;
105  uint32 hihalf = (uint32) (val >> 32);
106 
107  lohalf ^= (val >= 0) ? hihalf : ~hihalf;
108 
109  return hash_uint32_extended(lohalf, PG_GETARG_INT64(1));
110 }
111 
112 Datum
114 {
115  return hash_uint32((uint32) PG_GETARG_OID(0));
116 }
117 
118 Datum
120 {
122 }
123 
124 Datum
126 {
127  return hash_uint32((uint32) PG_GETARG_OID(0));
128 }
129 
130 Datum
132 {
134 }
135 
136 Datum
138 {
139  float4 key = PG_GETARG_FLOAT4(0);
140  float8 key8;
141 
142  /*
143  * On IEEE-float machines, minus zero and zero have different bit patterns
144  * but should compare as equal. We must ensure that they have the same
145  * hash value, which is most reliably done this way:
146  */
147  if (key == (float4) 0)
148  PG_RETURN_UINT32(0);
149 
150  /*
151  * To support cross-type hashing of float8 and float4, we want to return
152  * the same hash value hashfloat8 would produce for an equal float8 value.
153  * So, widen the value to float8 and hash that. (We must do this rather
154  * than have hashfloat8 try to narrow its value to float4; that could fail
155  * on overflow.)
156  */
157  key8 = key;
158 
159  return hash_any((unsigned char *) &key8, sizeof(key8));
160 }
161 
162 Datum
164 {
165  float4 key = PG_GETARG_FLOAT4(0);
166  uint64 seed = PG_GETARG_INT64(1);
167  float8 key8;
168 
169  /* Same approach as hashfloat4 */
170  if (key == (float4) 0)
171  PG_RETURN_UINT64(seed);
172  key8 = key;
173 
174  return hash_any_extended((unsigned char *) &key8, sizeof(key8), seed);
175 }
176 
177 Datum
179 {
180  float8 key = PG_GETARG_FLOAT8(0);
181 
182  /*
183  * On IEEE-float machines, minus zero and zero have different bit patterns
184  * but should compare as equal. We must ensure that they have the same
185  * hash value, which is most reliably done this way:
186  */
187  if (key == (float8) 0)
188  PG_RETURN_UINT32(0);
189 
190  return hash_any((unsigned char *) &key, sizeof(key));
191 }
192 
193 Datum
195 {
196  float8 key = PG_GETARG_FLOAT8(0);
197  uint64 seed = PG_GETARG_INT64(1);
198 
199  /* Same approach as hashfloat8 */
200  if (key == (float8) 0)
201  PG_RETURN_UINT64(seed);
202 
203  return hash_any_extended((unsigned char *) &key, sizeof(key), seed);
204 }
205 
206 Datum
208 {
209  oidvector *key = (oidvector *) PG_GETARG_POINTER(0);
210 
211  return hash_any((unsigned char *) key->values, key->dim1 * sizeof(Oid));
212 }
213 
214 Datum
216 {
217  oidvector *key = (oidvector *) PG_GETARG_POINTER(0);
218 
219  return hash_any_extended((unsigned char *) key->values,
220  key->dim1 * sizeof(Oid),
221  PG_GETARG_INT64(1));
222 }
223 
224 Datum
226 {
227  char *key = NameStr(*PG_GETARG_NAME(0));
228 
229  return hash_any((unsigned char *) key, strlen(key));
230 }
231 
232 Datum
234 {
235  char *key = NameStr(*PG_GETARG_NAME(0));
236 
237  return hash_any_extended((unsigned char *) key, strlen(key),
238  PG_GETARG_INT64(1));
239 }
240 
241 Datum
243 {
244  text *key = PG_GETARG_TEXT_PP(0);
245  Datum result;
246 
247  /*
248  * Note: this is currently identical in behavior to hashvarlena, but keep
249  * it as a separate function in case we someday want to do something
250  * different in non-C locales. (See also hashbpchar, if so.)
251  */
252  result = hash_any((unsigned char *) VARDATA_ANY(key),
253  VARSIZE_ANY_EXHDR(key));
254 
255  /* Avoid leaking memory for toasted inputs */
256  PG_FREE_IF_COPY(key, 0);
257 
258  return result;
259 }
260 
261 Datum
263 {
264  text *key = PG_GETARG_TEXT_PP(0);
265  Datum result;
266 
267  /* Same approach as hashtext */
268  result = hash_any_extended((unsigned char *) VARDATA_ANY(key),
269  VARSIZE_ANY_EXHDR(key),
270  PG_GETARG_INT64(1));
271 
272  PG_FREE_IF_COPY(key, 0);
273 
274  return result;
275 }
276 
277 /*
278  * hashvarlena() can be used for any varlena datatype in which there are
279  * no non-significant bits, ie, distinct bitpatterns never compare as equal.
280  */
281 Datum
283 {
284  struct varlena *key = PG_GETARG_VARLENA_PP(0);
285  Datum result;
286 
287  result = hash_any((unsigned char *) VARDATA_ANY(key),
288  VARSIZE_ANY_EXHDR(key));
289 
290  /* Avoid leaking memory for toasted inputs */
291  PG_FREE_IF_COPY(key, 0);
292 
293  return result;
294 }
295 
296 Datum
298 {
299  struct varlena *key = PG_GETARG_VARLENA_PP(0);
300  Datum result;
301 
302  result = hash_any_extended((unsigned char *) VARDATA_ANY(key),
303  VARSIZE_ANY_EXHDR(key),
304  PG_GETARG_INT64(1));
305 
306  PG_FREE_IF_COPY(key, 0);
307 
308  return result;
309 }
310 
311 /*
312  * This hash function was written by Bob Jenkins
313  * (bob_jenkins@burtleburtle.net), and superficially adapted
314  * for PostgreSQL by Neil Conway. For more information on this
315  * hash function, see http://burtleburtle.net/bob/hash/doobs.html,
316  * or Bob's article in Dr. Dobb's Journal, Sept. 1997.
317  *
318  * In the current code, we have adopted Bob's 2006 update of his hash
319  * function to fetch the data a word at a time when it is suitably aligned.
320  * This makes for a useful speedup, at the cost of having to maintain
321  * four code paths (aligned vs unaligned, and little-endian vs big-endian).
322  * It also uses two separate mixing functions mix() and final(), instead
323  * of a slower multi-purpose function.
324  */
325 
326 /* Get a bit mask of the bits set in non-uint32 aligned addresses */
327 #define UINT32_ALIGN_MASK (sizeof(uint32) - 1)
328 
329 /* Rotate a uint32 value left by k bits - note multiple evaluation! */
330 #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
331 
332 /*----------
333  * mix -- mix 3 32-bit values reversibly.
334  *
335  * This is reversible, so any information in (a,b,c) before mix() is
336  * still in (a,b,c) after mix().
337  *
338  * If four pairs of (a,b,c) inputs are run through mix(), or through
339  * mix() in reverse, there are at least 32 bits of the output that
340  * are sometimes the same for one pair and different for another pair.
341  * This was tested for:
342  * * pairs that differed by one bit, by two bits, in any combination
343  * of top bits of (a,b,c), or in any combination of bottom bits of
344  * (a,b,c).
345  * * "differ" is defined as +, -, ^, or ~^. For + and -, I transformed
346  * the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
347  * is commonly produced by subtraction) look like a single 1-bit
348  * difference.
349  * * the base values were pseudorandom, all zero but one bit set, or
350  * all zero plus a counter that starts at zero.
351  *
352  * This does not achieve avalanche. There are input bits of (a,b,c)
353  * that fail to affect some output bits of (a,b,c), especially of a. The
354  * most thoroughly mixed value is c, but it doesn't really even achieve
355  * avalanche in c.
356  *
357  * This allows some parallelism. Read-after-writes are good at doubling
358  * the number of bits affected, so the goal of mixing pulls in the opposite
359  * direction from the goal of parallelism. I did what I could. Rotates
360  * seem to cost as much as shifts on every machine I could lay my hands on,
361  * and rotates are much kinder to the top and bottom bits, so I used rotates.
362  *----------
363  */
364 #define mix(a,b,c) \
365 { \
366  a -= c; a ^= rot(c, 4); c += b; \
367  b -= a; b ^= rot(a, 6); a += c; \
368  c -= b; c ^= rot(b, 8); b += a; \
369  a -= c; a ^= rot(c,16); c += b; \
370  b -= a; b ^= rot(a,19); a += c; \
371  c -= b; c ^= rot(b, 4); b += a; \
372 }
373 
374 /*----------
375  * final -- final mixing of 3 32-bit values (a,b,c) into c
376  *
377  * Pairs of (a,b,c) values differing in only a few bits will usually
378  * produce values of c that look totally different. This was tested for
379  * * pairs that differed by one bit, by two bits, in any combination
380  * of top bits of (a,b,c), or in any combination of bottom bits of
381  * (a,b,c).
382  * * "differ" is defined as +, -, ^, or ~^. For + and -, I transformed
383  * the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
384  * is commonly produced by subtraction) look like a single 1-bit
385  * difference.
386  * * the base values were pseudorandom, all zero but one bit set, or
387  * all zero plus a counter that starts at zero.
388  *
389  * The use of separate functions for mix() and final() allow for a
390  * substantial performance increase since final() does not need to
391  * do well in reverse, but is does need to affect all output bits.
392  * mix(), on the other hand, does not need to affect all output
393  * bits (affecting 32 bits is enough). The original hash function had
394  * a single mixing operation that had to satisfy both sets of requirements
395  * and was slower as a result.
396  *----------
397  */
398 #define final(a,b,c) \
399 { \
400  c ^= b; c -= rot(b,14); \
401  a ^= c; a -= rot(c,11); \
402  b ^= a; b -= rot(a,25); \
403  c ^= b; c -= rot(b,16); \
404  a ^= c; a -= rot(c, 4); \
405  b ^= a; b -= rot(a,14); \
406  c ^= b; c -= rot(b,24); \
407 }
408 
409 /*
410  * hash_any() -- hash a variable-length key into a 32-bit value
411  * k : the key (the unaligned variable-length array of bytes)
412  * len : the length of the key, counting by bytes
413  *
414  * Returns a uint32 value. Every bit of the key affects every bit of
415  * the return value. Every 1-bit and 2-bit delta achieves avalanche.
416  * About 6*len+35 instructions. The best hash table sizes are powers
417  * of 2. There is no need to do mod a prime (mod is sooo slow!).
418  * If you need less than 32 bits, use a bitmask.
419  *
420  * This procedure must never throw elog(ERROR); the ResourceOwner code
421  * relies on this not to fail.
422  *
423  * Note: we could easily change this function to return a 64-bit hash value
424  * by using the final values of both b and c. b is perhaps a little less
425  * well mixed than c, however.
426  */
427 Datum
428 hash_any(register const unsigned char *k, register int keylen)
429 {
430  register uint32 a,
431  b,
432  c,
433  len;
434 
435  /* Set up the internal state */
436  len = keylen;
437  a = b = c = 0x9e3779b9 + len + 3923095;
438 
439  /* If the source pointer is word-aligned, we use word-wide fetches */
440  if (((uintptr_t) k & UINT32_ALIGN_MASK) == 0)
441  {
442  /* Code path for aligned source data */
443  register const uint32 *ka = (const uint32 *) k;
444 
445  /* handle most of the key */
446  while (len >= 12)
447  {
448  a += ka[0];
449  b += ka[1];
450  c += ka[2];
451  mix(a, b, c);
452  ka += 3;
453  len -= 12;
454  }
455 
456  /* handle the last 11 bytes */
457  k = (const unsigned char *) ka;
458 #ifdef WORDS_BIGENDIAN
459  switch (len)
460  {
461  case 11:
462  c += ((uint32) k[10] << 8);
463  /* fall through */
464  case 10:
465  c += ((uint32) k[9] << 16);
466  /* fall through */
467  case 9:
468  c += ((uint32) k[8] << 24);
469  /* the lowest byte of c is reserved for the length */
470  /* fall through */
471  case 8:
472  b += ka[1];
473  a += ka[0];
474  break;
475  case 7:
476  b += ((uint32) k[6] << 8);
477  /* fall through */
478  case 6:
479  b += ((uint32) k[5] << 16);
480  /* fall through */
481  case 5:
482  b += ((uint32) k[4] << 24);
483  /* fall through */
484  case 4:
485  a += ka[0];
486  break;
487  case 3:
488  a += ((uint32) k[2] << 8);
489  /* fall through */
490  case 2:
491  a += ((uint32) k[1] << 16);
492  /* fall through */
493  case 1:
494  a += ((uint32) k[0] << 24);
495  /* case 0: nothing left to add */
496  }
497 #else /* !WORDS_BIGENDIAN */
498  switch (len)
499  {
500  case 11:
501  c += ((uint32) k[10] << 24);
502  /* fall through */
503  case 10:
504  c += ((uint32) k[9] << 16);
505  /* fall through */
506  case 9:
507  c += ((uint32) k[8] << 8);
508  /* the lowest byte of c is reserved for the length */
509  /* fall through */
510  case 8:
511  b += ka[1];
512  a += ka[0];
513  break;
514  case 7:
515  b += ((uint32) k[6] << 16);
516  /* fall through */
517  case 6:
518  b += ((uint32) k[5] << 8);
519  /* fall through */
520  case 5:
521  b += k[4];
522  /* fall through */
523  case 4:
524  a += ka[0];
525  break;
526  case 3:
527  a += ((uint32) k[2] << 16);
528  /* fall through */
529  case 2:
530  a += ((uint32) k[1] << 8);
531  /* fall through */
532  case 1:
533  a += k[0];
534  /* case 0: nothing left to add */
535  }
536 #endif /* WORDS_BIGENDIAN */
537  }
538  else
539  {
540  /* Code path for non-aligned source data */
541 
542  /* handle most of the key */
543  while (len >= 12)
544  {
545 #ifdef WORDS_BIGENDIAN
546  a += (k[3] + ((uint32) k[2] << 8) + ((uint32) k[1] << 16) + ((uint32) k[0] << 24));
547  b += (k[7] + ((uint32) k[6] << 8) + ((uint32) k[5] << 16) + ((uint32) k[4] << 24));
548  c += (k[11] + ((uint32) k[10] << 8) + ((uint32) k[9] << 16) + ((uint32) k[8] << 24));
549 #else /* !WORDS_BIGENDIAN */
550  a += (k[0] + ((uint32) k[1] << 8) + ((uint32) k[2] << 16) + ((uint32) k[3] << 24));
551  b += (k[4] + ((uint32) k[5] << 8) + ((uint32) k[6] << 16) + ((uint32) k[7] << 24));
552  c += (k[8] + ((uint32) k[9] << 8) + ((uint32) k[10] << 16) + ((uint32) k[11] << 24));
553 #endif /* WORDS_BIGENDIAN */
554  mix(a, b, c);
555  k += 12;
556  len -= 12;
557  }
558 
559  /* handle the last 11 bytes */
560 #ifdef WORDS_BIGENDIAN
561  switch (len) /* all the case statements fall through */
562  {
563  case 11:
564  c += ((uint32) k[10] << 8);
565  case 10:
566  c += ((uint32) k[9] << 16);
567  case 9:
568  c += ((uint32) k[8] << 24);
569  /* the lowest byte of c is reserved for the length */
570  case 8:
571  b += k[7];
572  case 7:
573  b += ((uint32) k[6] << 8);
574  case 6:
575  b += ((uint32) k[5] << 16);
576  case 5:
577  b += ((uint32) k[4] << 24);
578  case 4:
579  a += k[3];
580  case 3:
581  a += ((uint32) k[2] << 8);
582  case 2:
583  a += ((uint32) k[1] << 16);
584  case 1:
585  a += ((uint32) k[0] << 24);
586  /* case 0: nothing left to add */
587  }
588 #else /* !WORDS_BIGENDIAN */
589  switch (len) /* all the case statements fall through */
590  {
591  case 11:
592  c += ((uint32) k[10] << 24);
593  case 10:
594  c += ((uint32) k[9] << 16);
595  case 9:
596  c += ((uint32) k[8] << 8);
597  /* the lowest byte of c is reserved for the length */
598  case 8:
599  b += ((uint32) k[7] << 24);
600  case 7:
601  b += ((uint32) k[6] << 16);
602  case 6:
603  b += ((uint32) k[5] << 8);
604  case 5:
605  b += k[4];
606  case 4:
607  a += ((uint32) k[3] << 24);
608  case 3:
609  a += ((uint32) k[2] << 16);
610  case 2:
611  a += ((uint32) k[1] << 8);
612  case 1:
613  a += k[0];
614  /* case 0: nothing left to add */
615  }
616 #endif /* WORDS_BIGENDIAN */
617  }
618 
619  final(a, b, c);
620 
621  /* report the result */
622  return UInt32GetDatum(c);
623 }
624 
625 /*
626  * hash_any_extended() -- hash into a 64-bit value, using an optional seed
627  * k : the key (the unaligned variable-length array of bytes)
628  * len : the length of the key, counting by bytes
629  * seed : a 64-bit seed (0 means no seed)
630  *
631  * Returns a uint64 value. Otherwise similar to hash_any.
632  */
633 Datum
634 hash_any_extended(register const unsigned char *k, register int keylen,
635  uint64 seed)
636 {
637  register uint32 a,
638  b,
639  c,
640  len;
641 
642  /* Set up the internal state */
643  len = keylen;
644  a = b = c = 0x9e3779b9 + len + 3923095;
645 
646  /* If the seed is non-zero, use it to perturb the internal state. */
647  if (seed != 0)
648  {
649  /*
650  * In essence, the seed is treated as part of the data being hashed,
651  * but for simplicity, we pretend that it's padded with four bytes of
652  * zeroes so that the seed constitutes a 12-byte chunk.
653  */
654  a += (uint32) (seed >> 32);
655  b += (uint32) seed;
656  mix(a, b, c);
657  }
658 
659  /* If the source pointer is word-aligned, we use word-wide fetches */
660  if (((uintptr_t) k & UINT32_ALIGN_MASK) == 0)
661  {
662  /* Code path for aligned source data */
663  register const uint32 *ka = (const uint32 *) k;
664 
665  /* handle most of the key */
666  while (len >= 12)
667  {
668  a += ka[0];
669  b += ka[1];
670  c += ka[2];
671  mix(a, b, c);
672  ka += 3;
673  len -= 12;
674  }
675 
676  /* handle the last 11 bytes */
677  k = (const unsigned char *) ka;
678 #ifdef WORDS_BIGENDIAN
679  switch (len)
680  {
681  case 11:
682  c += ((uint32) k[10] << 8);
683  /* fall through */
684  case 10:
685  c += ((uint32) k[9] << 16);
686  /* fall through */
687  case 9:
688  c += ((uint32) k[8] << 24);
689  /* the lowest byte of c is reserved for the length */
690  /* fall through */
691  case 8:
692  b += ka[1];
693  a += ka[0];
694  break;
695  case 7:
696  b += ((uint32) k[6] << 8);
697  /* fall through */
698  case 6:
699  b += ((uint32) k[5] << 16);
700  /* fall through */
701  case 5:
702  b += ((uint32) k[4] << 24);
703  /* fall through */
704  case 4:
705  a += ka[0];
706  break;
707  case 3:
708  a += ((uint32) k[2] << 8);
709  /* fall through */
710  case 2:
711  a += ((uint32) k[1] << 16);
712  /* fall through */
713  case 1:
714  a += ((uint32) k[0] << 24);
715  /* case 0: nothing left to add */
716  }
717 #else /* !WORDS_BIGENDIAN */
718  switch (len)
719  {
720  case 11:
721  c += ((uint32) k[10] << 24);
722  /* fall through */
723  case 10:
724  c += ((uint32) k[9] << 16);
725  /* fall through */
726  case 9:
727  c += ((uint32) k[8] << 8);
728  /* the lowest byte of c is reserved for the length */
729  /* fall through */
730  case 8:
731  b += ka[1];
732  a += ka[0];
733  break;
734  case 7:
735  b += ((uint32) k[6] << 16);
736  /* fall through */
737  case 6:
738  b += ((uint32) k[5] << 8);
739  /* fall through */
740  case 5:
741  b += k[4];
742  /* fall through */
743  case 4:
744  a += ka[0];
745  break;
746  case 3:
747  a += ((uint32) k[2] << 16);
748  /* fall through */
749  case 2:
750  a += ((uint32) k[1] << 8);
751  /* fall through */
752  case 1:
753  a += k[0];
754  /* case 0: nothing left to add */
755  }
756 #endif /* WORDS_BIGENDIAN */
757  }
758  else
759  {
760  /* Code path for non-aligned source data */
761 
762  /* handle most of the key */
763  while (len >= 12)
764  {
765 #ifdef WORDS_BIGENDIAN
766  a += (k[3] + ((uint32) k[2] << 8) + ((uint32) k[1] << 16) + ((uint32) k[0] << 24));
767  b += (k[7] + ((uint32) k[6] << 8) + ((uint32) k[5] << 16) + ((uint32) k[4] << 24));
768  c += (k[11] + ((uint32) k[10] << 8) + ((uint32) k[9] << 16) + ((uint32) k[8] << 24));
769 #else /* !WORDS_BIGENDIAN */
770  a += (k[0] + ((uint32) k[1] << 8) + ((uint32) k[2] << 16) + ((uint32) k[3] << 24));
771  b += (k[4] + ((uint32) k[5] << 8) + ((uint32) k[6] << 16) + ((uint32) k[7] << 24));
772  c += (k[8] + ((uint32) k[9] << 8) + ((uint32) k[10] << 16) + ((uint32) k[11] << 24));
773 #endif /* WORDS_BIGENDIAN */
774  mix(a, b, c);
775  k += 12;
776  len -= 12;
777  }
778 
779  /* handle the last 11 bytes */
780 #ifdef WORDS_BIGENDIAN
781  switch (len) /* all the case statements fall through */
782  {
783  case 11:
784  c += ((uint32) k[10] << 8);
785  case 10:
786  c += ((uint32) k[9] << 16);
787  case 9:
788  c += ((uint32) k[8] << 24);
789  /* the lowest byte of c is reserved for the length */
790  case 8:
791  b += k[7];
792  case 7:
793  b += ((uint32) k[6] << 8);
794  case 6:
795  b += ((uint32) k[5] << 16);
796  case 5:
797  b += ((uint32) k[4] << 24);
798  case 4:
799  a += k[3];
800  case 3:
801  a += ((uint32) k[2] << 8);
802  case 2:
803  a += ((uint32) k[1] << 16);
804  case 1:
805  a += ((uint32) k[0] << 24);
806  /* case 0: nothing left to add */
807  }
808 #else /* !WORDS_BIGENDIAN */
809  switch (len) /* all the case statements fall through */
810  {
811  case 11:
812  c += ((uint32) k[10] << 24);
813  case 10:
814  c += ((uint32) k[9] << 16);
815  case 9:
816  c += ((uint32) k[8] << 8);
817  /* the lowest byte of c is reserved for the length */
818  case 8:
819  b += ((uint32) k[7] << 24);
820  case 7:
821  b += ((uint32) k[6] << 16);
822  case 6:
823  b += ((uint32) k[5] << 8);
824  case 5:
825  b += k[4];
826  case 4:
827  a += ((uint32) k[3] << 24);
828  case 3:
829  a += ((uint32) k[2] << 16);
830  case 2:
831  a += ((uint32) k[1] << 8);
832  case 1:
833  a += k[0];
834  /* case 0: nothing left to add */
835  }
836 #endif /* WORDS_BIGENDIAN */
837  }
838 
839  final(a, b, c);
840 
841  /* report the result */
842  PG_RETURN_UINT64(((uint64) b << 32) | c);
843 }
844 
845 /*
846  * hash_uint32() -- hash a 32-bit value to a 32-bit value
847  *
848  * This has the same result as
849  * hash_any(&k, sizeof(uint32))
850  * but is faster and doesn't force the caller to store k into memory.
851  */
852 Datum
854 {
855  register uint32 a,
856  b,
857  c;
858 
859  a = b = c = 0x9e3779b9 + (uint32) sizeof(uint32) + 3923095;
860  a += k;
861 
862  final(a, b, c);
863 
864  /* report the result */
865  return UInt32GetDatum(c);
866 }
867 
868 /*
869  * hash_uint32_extended() -- hash a 32-bit value to a 64-bit value, with a seed
870  *
871  * Like hash_uint32, this is a convenience function.
872  */
873 Datum
875 {
876  register uint32 a,
877  b,
878  c;
879 
880  a = b = c = 0x9e3779b9 + (uint32) sizeof(uint32) + 3923095;
881 
882  if (seed != 0)
883  {
884  a += (uint32) (seed >> 32);
885  b += (uint32) seed;
886  mix(a, b, c);
887  }
888 
889  a += k;
890 
891  final(a, b, c);
892 
893  /* report the result */
894  PG_RETURN_UINT64(((uint64) b << 32) | c);
895 }
#define PG_GETARG_FLOAT8(n)
Definition: fmgr.h:246
Definition: c.h:526
#define PG_GETARG_INT32(n)
Definition: fmgr.h:234
Datum hashoid(PG_FUNCTION_ARGS)
Definition: hashfunc.c:113
#define VARDATA_ANY(PTR)
Definition: postgres.h:347
Datum hashname(PG_FUNCTION_ARGS)
Definition: hashfunc.c:225
Datum hashint8(PG_FUNCTION_ARGS)
Definition: hashfunc.c:80
Datum hash_uint32_extended(uint32 k, uint64 seed)
Definition: hashfunc.c:874
Datum hashint2extended(PG_FUNCTION_ARGS)
Definition: hashfunc.c:62
#define PG_GETARG_POINTER(n)
Definition: fmgr.h:241
Datum hashint8extended(PG_FUNCTION_ARGS)
Definition: hashfunc.c:100
unsigned int Oid
Definition: postgres_ext.h:31
#define PG_RETURN_UINT64(x)
Definition: fmgr.h:328
Datum hashvarlenaextended(PG_FUNCTION_ARGS)
Definition: hashfunc.c:297
#define PG_RETURN_UINT32(x)
Definition: fmgr.h:315
signed int int32
Definition: c.h:284
#define PG_GETARG_TEXT_PP(n)
Definition: fmgr.h:273
Datum hashenumextended(PG_FUNCTION_ARGS)
Definition: hashfunc.c:131
Datum hashchar(PG_FUNCTION_ARGS)
Definition: hashfunc.c:44
Datum hashvarlena(PG_FUNCTION_ARGS)
Definition: hashfunc.c:282
double float8
Definition: c.h:429
Datum hashtextextended(PG_FUNCTION_ARGS)
Definition: hashfunc.c:262
Datum hashtext(PG_FUNCTION_ARGS)
Definition: hashfunc.c:242
#define PG_GETARG_VARLENA_PP(n)
Definition: fmgr.h:253
char * c
#define PG_GETARG_OID(n)
Definition: fmgr.h:240
Oid values[FLEXIBLE_ARRAY_MEMBER]
Definition: c.h:534
int dim1
Definition: c.h:532
unsigned int uint32
Definition: c.h:296
Datum hashoidvectorextended(PG_FUNCTION_ARGS)
Definition: hashfunc.c:215
Datum hashint4(PG_FUNCTION_ARGS)
Definition: hashfunc.c:68
#define UInt32GetDatum(X)
Definition: postgres.h:499
Datum hashfloat4(PG_FUNCTION_ARGS)
Definition: hashfunc.c:137
#define PG_GETARG_FLOAT4(n)
Definition: fmgr.h:245
Datum hashfloat8(PG_FUNCTION_ARGS)
Definition: hashfunc.c:178
Datum hashint4extended(PG_FUNCTION_ARGS)
Definition: hashfunc.c:74
float float4
Definition: c.h:428
#define UINT32_ALIGN_MASK
Definition: hashfunc.c:327
Datum hash_uint32(uint32 k)
Definition: hashfunc.c:853
uintptr_t Datum
Definition: postgres.h:372
#define PG_GETARG_INT16(n)
Definition: fmgr.h:236
#define mix(a, b, c)
Definition: hashfunc.c:364
Datum hash_any(register const unsigned char *k, register int keylen)
Definition: hashfunc.c:428
Datum hashenum(PG_FUNCTION_ARGS)
Definition: hashfunc.c:125
#define PG_FREE_IF_COPY(ptr, n)
Definition: fmgr.h:225
Datum hashoidextended(PG_FUNCTION_ARGS)
Definition: hashfunc.c:119
Datum hashint2(PG_FUNCTION_ARGS)
Definition: hashfunc.c:56
#define VARSIZE_ANY_EXHDR(PTR)
Definition: postgres.h:340
Datum hashcharextended(PG_FUNCTION_ARGS)
Definition: hashfunc.c:50
Datum hashoidvector(PG_FUNCTION_ARGS)
Definition: hashfunc.c:207
#define NameStr(name)
Definition: c.h:547
Datum hashfloat4extended(PG_FUNCTION_ARGS)
Definition: hashfunc.c:163
Definition: c.h:487
#define PG_FUNCTION_ARGS
Definition: fmgr.h:158
#define PG_GETARG_INT64(n)
Definition: fmgr.h:247
long val
Definition: informix.c:689
Datum hashnameextended(PG_FUNCTION_ARGS)
Definition: hashfunc.c:233
#define PG_GETARG_CHAR(n)
Definition: fmgr.h:238
Datum hash_any_extended(register const unsigned char *k, register int keylen, uint64 seed)
Definition: hashfunc.c:634
#define PG_GETARG_NAME(n)
Definition: fmgr.h:243
Datum hashfloat8extended(PG_FUNCTION_ARGS)
Definition: hashfunc.c:194