LCOV - code coverage report
Current view: top level - src/common - hashfn.c (source / functions) Hit Total Coverage
Test: PostgreSQL 13beta1 Lines: 168 170 98.8 %
Date: 2020-06-01 09:07:10 Functions: 7 7 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*-------------------------------------------------------------------------
       2             :  *
       3             :  * hashfn.c
       4             :  *      Generic hashing functions, and hash functions for use in dynahash.c
       5             :  *      hashtables
       6             :  *
       7             :  *
       8             :  * Portions Copyright (c) 1996-2020, PostgreSQL Global Development Group
       9             :  * Portions Copyright (c) 1994, Regents of the University of California
      10             :  *
      11             :  *
      12             :  * IDENTIFICATION
      13             :  *    src/common/hashfn.c
      14             :  *
      15             :  * NOTES
      16             :  *    It is expected that every bit of a hash function's 32-bit result is
      17             :  *    as random as every other; failure to ensure this is likely to lead
      18             :  *    to poor performance of hash tables.  In most cases a hash
      19             :  *    function should use hash_bytes() or its variant hash_bytes_uint32(),
      20             :  *    or the wrappers hash_any() and hash_uint32 defined in hashfn.h.
      21             :  *
      22             :  *-------------------------------------------------------------------------
      23             :  */
      24             : #include "postgres.h"
      25             : 
      26             : #include "common/hashfn.h"
      27             : 
      28             : 
      29             : /*
      30             :  * This hash function was written by Bob Jenkins
      31             :  * (bob_jenkins@burtleburtle.net), and superficially adapted
      32             :  * for PostgreSQL by Neil Conway. For more information on this
      33             :  * hash function, see http://burtleburtle.net/bob/hash/doobs.html,
      34             :  * or Bob's article in Dr. Dobb's Journal, Sept. 1997.
      35             :  *
      36             :  * In the current code, we have adopted Bob's 2006 update of his hash
      37             :  * function to fetch the data a word at a time when it is suitably aligned.
      38             :  * This makes for a useful speedup, at the cost of having to maintain
      39             :  * four code paths (aligned vs unaligned, and little-endian vs big-endian).
      40             :  * It also uses two separate mixing functions mix() and final(), instead
      41             :  * of a slower multi-purpose function.
      42             :  */
      43             : 
      44             : /* Get a bit mask of the bits set in non-uint32 aligned addresses */
      45             : #define UINT32_ALIGN_MASK (sizeof(uint32) - 1)
      46             : 
      47             : /* Rotate a uint32 value left by k bits - note multiple evaluation! */
      48             : #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
      49             : 
      50             : /*----------
      51             :  * mix -- mix 3 32-bit values reversibly.
      52             :  *
      53             :  * This is reversible, so any information in (a,b,c) before mix() is
      54             :  * still in (a,b,c) after mix().
      55             :  *
      56             :  * If four pairs of (a,b,c) inputs are run through mix(), or through
      57             :  * mix() in reverse, there are at least 32 bits of the output that
      58             :  * are sometimes the same for one pair and different for another pair.
      59             :  * This was tested for:
      60             :  * * pairs that differed by one bit, by two bits, in any combination
      61             :  *   of top bits of (a,b,c), or in any combination of bottom bits of
      62             :  *   (a,b,c).
      63             :  * * "differ" is defined as +, -, ^, or ~^.  For + and -, I transformed
      64             :  *   the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
      65             :  *   is commonly produced by subtraction) look like a single 1-bit
      66             :  *   difference.
      67             :  * * the base values were pseudorandom, all zero but one bit set, or
      68             :  *   all zero plus a counter that starts at zero.
      69             :  *
      70             :  * This does not achieve avalanche.  There are input bits of (a,b,c)
      71             :  * that fail to affect some output bits of (a,b,c), especially of a.  The
      72             :  * most thoroughly mixed value is c, but it doesn't really even achieve
      73             :  * avalanche in c.
      74             :  *
      75             :  * This allows some parallelism.  Read-after-writes are good at doubling
      76             :  * the number of bits affected, so the goal of mixing pulls in the opposite
      77             :  * direction from the goal of parallelism.  I did what I could.  Rotates
      78             :  * seem to cost as much as shifts on every machine I could lay my hands on,
      79             :  * and rotates are much kinder to the top and bottom bits, so I used rotates.
      80             :  *----------
      81             :  */
      82             : #define mix(a,b,c) \
      83             : { \
      84             :   a -= c;  a ^= rot(c, 4);  c += b; \
      85             :   b -= a;  b ^= rot(a, 6);  a += c; \
      86             :   c -= b;  c ^= rot(b, 8);  b += a; \
      87             :   a -= c;  a ^= rot(c,16);  c += b; \
      88             :   b -= a;  b ^= rot(a,19);  a += c; \
      89             :   c -= b;  c ^= rot(b, 4);  b += a; \
      90             : }
      91             : 
      92             : /*----------
      93             :  * final -- final mixing of 3 32-bit values (a,b,c) into c
      94             :  *
      95             :  * Pairs of (a,b,c) values differing in only a few bits will usually
      96             :  * produce values of c that look totally different.  This was tested for
      97             :  * * pairs that differed by one bit, by two bits, in any combination
      98             :  *   of top bits of (a,b,c), or in any combination of bottom bits of
      99             :  *   (a,b,c).
     100             :  * * "differ" is defined as +, -, ^, or ~^.  For + and -, I transformed
     101             :  *   the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
     102             :  *   is commonly produced by subtraction) look like a single 1-bit
     103             :  *   difference.
     104             :  * * the base values were pseudorandom, all zero but one bit set, or
     105             :  *   all zero plus a counter that starts at zero.
     106             :  *
     107             :  * The use of separate functions for mix() and final() allow for a
     108             :  * substantial performance increase since final() does not need to
     109             :  * do well in reverse, but is does need to affect all output bits.
     110             :  * mix(), on the other hand, does not need to affect all output
     111             :  * bits (affecting 32 bits is enough).  The original hash function had
     112             :  * a single mixing operation that had to satisfy both sets of requirements
     113             :  * and was slower as a result.
     114             :  *----------
     115             :  */
     116             : #define final(a,b,c) \
     117             : { \
     118             :   c ^= b; c -= rot(b,14); \
     119             :   a ^= c; a -= rot(c,11); \
     120             :   b ^= a; b -= rot(a,25); \
     121             :   c ^= b; c -= rot(b,16); \
     122             :   a ^= c; a -= rot(c, 4); \
     123             :   b ^= a; b -= rot(a,14); \
     124             :   c ^= b; c -= rot(b,24); \
     125             : }
     126             : 
     127             : /*
     128             :  * hash_bytes() -- hash a variable-length key into a 32-bit value
     129             :  *      k       : the key (the unaligned variable-length array of bytes)
     130             :  *      len     : the length of the key, counting by bytes
     131             :  *
     132             :  * Returns a uint32 value.  Every bit of the key affects every bit of
     133             :  * the return value.  Every 1-bit and 2-bit delta achieves avalanche.
     134             :  * About 6*len+35 instructions. The best hash table sizes are powers
     135             :  * of 2.  There is no need to do mod a prime (mod is sooo slow!).
     136             :  * If you need less than 32 bits, use a bitmask.
     137             :  *
     138             :  * This procedure must never throw elog(ERROR); the ResourceOwner code
     139             :  * relies on this not to fail.
     140             :  *
     141             :  * Note: we could easily change this function to return a 64-bit hash value
     142             :  * by using the final values of both b and c.  b is perhaps a little less
     143             :  * well mixed than c, however.
     144             :  */
     145             : uint32
     146   228056874 : hash_bytes(const unsigned char *k, int keylen)
     147             : {
     148             :     uint32      a,
     149             :                 b,
     150             :                 c,
     151             :                 len;
     152             : 
     153             :     /* Set up the internal state */
     154   228056874 :     len = keylen;
     155   228056874 :     a = b = c = 0x9e3779b9 + len + 3923095;
     156             : 
     157             :     /* If the source pointer is word-aligned, we use word-wide fetches */
     158   228056874 :     if (((uintptr_t) k & UINT32_ALIGN_MASK) == 0)
     159             :     {
     160             :         /* Code path for aligned source data */
     161   225416752 :         const uint32 *ka = (const uint32 *) k;
     162             : 
     163             :         /* handle most of the key */
     164   450483340 :         while (len >= 12)
     165             :         {
     166   225066588 :             a += ka[0];
     167   225066588 :             b += ka[1];
     168   225066588 :             c += ka[2];
     169   225066588 :             mix(a, b, c);
     170   225066588 :             ka += 3;
     171   225066588 :             len -= 12;
     172             :         }
     173             : 
     174             :         /* handle the last 11 bytes */
     175   225416752 :         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   225416752 :         switch (len)
     217             :         {
     218      473358 :             case 11:
     219      473358 :                 c += ((uint32) k[10] << 24);
     220             :                 /* fall through */
     221     1364654 :             case 10:
     222     1364654 :                 c += ((uint32) k[9] << 16);
     223             :                 /* fall through */
     224     1834982 :             case 9:
     225     1834982 :                 c += ((uint32) k[8] << 8);
     226             :                 /* fall through */
     227   184683386 :             case 8:
     228             :                 /* the lowest byte of c is reserved for the length */
     229   184683386 :                 b += ka[1];
     230   184683386 :                 a += ka[0];
     231   184683386 :                 break;
     232      629348 :             case 7:
     233      629348 :                 b += ((uint32) k[6] << 16);
     234             :                 /* fall through */
     235     1271418 :             case 6:
     236     1271418 :                 b += ((uint32) k[5] << 8);
     237             :                 /* fall through */
     238     1663584 :             case 5:
     239     1663584 :                 b += k[4];
     240             :                 /* fall through */
     241    36875512 :             case 4:
     242    36875512 :                 a += ka[0];
     243    36875512 :                 break;
     244      657962 :             case 3:
     245      657962 :                 a += ((uint32) k[2] << 16);
     246             :                 /* fall through */
     247     1666410 :             case 2:
     248     1666410 :                 a += ((uint32) k[1] << 8);
     249             :                 /* fall through */
     250     2552332 :             case 1:
     251     2552332 :                 a += k[0];
     252             :                 /* case 0: nothing left to add */
     253             :         }
     254             : #endif                          /* WORDS_BIGENDIAN */
     255   225416752 :     }
     256             :     else
     257             :     {
     258             :         /* Code path for non-aligned source data */
     259             : 
     260             :         /* handle most of the key */
     261     3081568 :         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      441446 :             a += (k[0] + ((uint32) k[1] << 8) + ((uint32) k[2] << 16) + ((uint32) k[3] << 24));
     269      441446 :             b += (k[4] + ((uint32) k[5] << 8) + ((uint32) k[6] << 16) + ((uint32) k[7] << 24));
     270      441446 :             c += (k[8] + ((uint32) k[9] << 8) + ((uint32) k[10] << 16) + ((uint32) k[11] << 24));
     271             : #endif                          /* WORDS_BIGENDIAN */
     272      441446 :             mix(a, b, c);
     273      441446 :             k += 12;
     274      441446 :             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     2640122 :         switch (len)
     318             :         {
     319       40166 :             case 11:
     320       40166 :                 c += ((uint32) k[10] << 24);
     321             :                 /* fall through */
     322      126818 :             case 10:
     323      126818 :                 c += ((uint32) k[9] << 16);
     324             :                 /* fall through */
     325      183616 :             case 9:
     326      183616 :                 c += ((uint32) k[8] << 8);
     327             :                 /* fall through */
     328      224766 :             case 8:
     329             :                 /* the lowest byte of c is reserved for the length */
     330      224766 :                 b += ((uint32) k[7] << 24);
     331             :                 /* fall through */
     332      261012 :             case 7:
     333      261012 :                 b += ((uint32) k[6] << 16);
     334             :                 /* fall through */
     335      384558 :             case 6:
     336      384558 :                 b += ((uint32) k[5] << 8);
     337             :                 /* fall through */
     338      440176 :             case 5:
     339      440176 :                 b += k[4];
     340             :                 /* fall through */
     341      934794 :             case 4:
     342      934794 :                 a += ((uint32) k[3] << 24);
     343             :                 /* fall through */
     344     1053008 :             case 3:
     345     1053008 :                 a += ((uint32) k[2] << 16);
     346             :                 /* fall through */
     347     1496842 :             case 2:
     348     1496842 :                 a += ((uint32) k[1] << 8);
     349             :                 /* fall through */
     350     1552442 :             case 1:
     351     1552442 :                 a += k[0];
     352             :                 /* case 0: nothing left to add */
     353             :         }
     354             : #endif                          /* WORDS_BIGENDIAN */
     355             :     }
     356             : 
     357   228056874 :     final(a, b, c);
     358             : 
     359             :     /* report the result */
     360   228056874 :     return c;
     361             : }
     362             : 
     363             : /*
     364             :  * hash_bytes_extended() -- hash into a 64-bit value, using an optional seed
     365             :  *      k       : the key (the unaligned variable-length array of bytes)
     366             :  *      len     : the length of the key, counting by bytes
     367             :  *      seed    : a 64-bit seed (0 means no seed)
     368             :  *
     369             :  * Returns a uint64 value.  Otherwise similar to hash_bytes.
     370             :  */
     371             : uint64
     372     4966962 : hash_bytes_extended(const unsigned char *k, int keylen, uint64 seed)
     373             : {
     374             :     uint32      a,
     375             :                 b,
     376             :                 c,
     377             :                 len;
     378             : 
     379             :     /* Set up the internal state */
     380     4966962 :     len = keylen;
     381     4966962 :     a = b = c = 0x9e3779b9 + len + 3923095;
     382             : 
     383             :     /* If the seed is non-zero, use it to perturb the internal state. */
     384     4966962 :     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     4966404 :         a += (uint32) (seed >> 32);
     392     4966404 :         b += (uint32) seed;
     393     4966404 :         mix(a, b, c);
     394             :     }
     395             : 
     396             :     /* If the source pointer is word-aligned, we use word-wide fetches */
     397     4966962 :     if (((uintptr_t) k & UINT32_ALIGN_MASK) == 0)
     398             :     {
     399             :         /* Code path for aligned source data */
     400     4966846 :         const uint32 *ka = (const uint32 *) k;
     401             : 
     402             :         /* handle most of the key */
     403     7376766 :         while (len >= 12)
     404             :         {
     405     2409920 :             a += ka[0];
     406     2409920 :             b += ka[1];
     407     2409920 :             c += ka[2];
     408     2409920 :             mix(a, b, c);
     409     2409920 :             ka += 3;
     410     2409920 :             len -= 12;
     411             :         }
     412             : 
     413             :         /* handle the last 11 bytes */
     414     4966846 :         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     4966846 :         switch (len)
     456             :         {
     457          40 :             case 11:
     458          40 :                 c += ((uint32) k[10] << 24);
     459             :                 /* fall through */
     460          80 :             case 10:
     461          80 :                 c += ((uint32) k[9] << 16);
     462             :                 /* fall through */
     463         144 :             case 9:
     464         144 :                 c += ((uint32) k[8] << 8);
     465             :                 /* fall through */
     466         312 :             case 8:
     467             :                 /* the lowest byte of c is reserved for the length */
     468         312 :                 b += ka[1];
     469         312 :                 a += ka[0];
     470         312 :                 break;
     471     2955458 :             case 7:
     472     2955458 :                 b += ((uint32) k[6] << 16);
     473             :                 /* fall through */
     474     3315624 :             case 6:
     475     3315624 :                 b += ((uint32) k[5] << 8);
     476             :                 /* fall through */
     477     3351634 :             case 5:
     478     3351634 :                 b += k[4];
     479             :                 /* fall through */
     480     4165962 :             case 4:
     481     4165962 :                 a += ka[0];
     482     4165962 :                 break;
     483         390 :             case 3:
     484         390 :                 a += ((uint32) k[2] << 16);
     485             :                 /* fall through */
     486         454 :             case 2:
     487         454 :                 a += ((uint32) k[1] << 8);
     488             :                 /* fall through */
     489         550 :             case 1:
     490         550 :                 a += k[0];
     491             :                 /* case 0: nothing left to add */
     492             :         }
     493             : #endif                          /* WORDS_BIGENDIAN */
     494     4966846 :     }
     495             :     else
     496             :     {
     497             :         /* Code path for non-aligned source data */
     498             : 
     499             :         /* handle most of the key */
     500         170 :         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          54 :             a += (k[0] + ((uint32) k[1] << 8) + ((uint32) k[2] << 16) + ((uint32) k[3] << 24));
     508          54 :             b += (k[4] + ((uint32) k[5] << 8) + ((uint32) k[6] << 16) + ((uint32) k[7] << 24));
     509          54 :             c += (k[8] + ((uint32) k[9] << 8) + ((uint32) k[10] << 16) + ((uint32) k[11] << 24));
     510             : #endif                          /* WORDS_BIGENDIAN */
     511          54 :             mix(a, b, c);
     512          54 :             k += 12;
     513          54 :             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         116 :         switch (len)
     557             :         {
     558           0 :             case 11:
     559           0 :                 c += ((uint32) k[10] << 24);
     560             :                 /* fall through */
     561          10 :             case 10:
     562          10 :                 c += ((uint32) k[9] << 16);
     563             :                 /* fall through */
     564          12 :             case 9:
     565          12 :                 c += ((uint32) k[8] << 8);
     566             :                 /* fall through */
     567          44 :             case 8:
     568             :                 /* the lowest byte of c is reserved for the length */
     569          44 :                 b += ((uint32) k[7] << 24);
     570             :                 /* fall through */
     571          54 :             case 7:
     572          54 :                 b += ((uint32) k[6] << 16);
     573             :                 /* fall through */
     574          54 :             case 6:
     575          54 :                 b += ((uint32) k[5] << 8);
     576             :                 /* fall through */
     577          62 :             case 5:
     578          62 :                 b += k[4];
     579             :                 /* fall through */
     580          70 :             case 4:
     581          70 :                 a += ((uint32) k[3] << 24);
     582             :                 /* fall through */
     583          80 :             case 3:
     584          80 :                 a += ((uint32) k[2] << 16);
     585             :                 /* fall through */
     586          88 :             case 2:
     587          88 :                 a += ((uint32) k[1] << 8);
     588             :                 /* fall through */
     589         116 :             case 1:
     590         116 :                 a += k[0];
     591             :                 /* case 0: nothing left to add */
     592             :         }
     593             : #endif                          /* WORDS_BIGENDIAN */
     594             :     }
     595             : 
     596     4966962 :     final(a, b, c);
     597             : 
     598             :     /* report the result */
     599     4966962 :     return ((uint64) b << 32) | c;
     600             : }
     601             : 
     602             : /*
     603             :  * hash_bytes_uint32() -- hash a 32-bit value to a 32-bit value
     604             :  *
     605             :  * This has the same result as
     606             :  *      hash_bytes(&k, sizeof(uint32))
     607             :  * but is faster and doesn't force the caller to store k into memory.
     608             :  */
     609             : uint32
     610    71241944 : hash_bytes_uint32(uint32 k)
     611             : {
     612             :     uint32      a,
     613             :                 b,
     614             :                 c;
     615             : 
     616    71241944 :     a = b = c = 0x9e3779b9 + (uint32) sizeof(uint32) + 3923095;
     617    71241944 :     a += k;
     618             : 
     619    71241944 :     final(a, b, c);
     620             : 
     621             :     /* report the result */
     622    71241944 :     return c;
     623             : }
     624             : 
     625             : /*
     626             :  * hash_bytes_uint32_extended() -- hash 32-bit value to 64-bit value, with seed
     627             :  *
     628             :  * Like hash_bytes_uint32, this is a convenience function.
     629             :  */
     630             : uint64
     631      200916 : hash_bytes_uint32_extended(uint32 k, uint64 seed)
     632             : {
     633             :     uint32      a,
     634             :                 b,
     635             :                 c;
     636             : 
     637      200916 :     a = b = c = 0x9e3779b9 + (uint32) sizeof(uint32) + 3923095;
     638             : 
     639      200916 :     if (seed != 0)
     640             :     {
     641      200540 :         a += (uint32) (seed >> 32);
     642      200540 :         b += (uint32) seed;
     643      200540 :         mix(a, b, c);
     644             :     }
     645             : 
     646      200916 :     a += k;
     647             : 
     648      200916 :     final(a, b, c);
     649             : 
     650             :     /* report the result */
     651      200916 :     return ((uint64) b << 32) | c;
     652             : }
     653             : 
     654             : /*
     655             :  * string_hash: hash function for keys that are NUL-terminated strings.
     656             :  *
     657             :  * NOTE: this is the default hash function if none is specified.
     658             :  */
     659             : uint32
     660     1957488 : string_hash(const void *key, Size keysize)
     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     1957488 :     Size        s_len = strlen((const char *) key);
     668             : 
     669     1957488 :     s_len = Min(s_len, keysize - 1);
     670     1957488 :     return hash_bytes((const unsigned char *) key, (int) s_len);
     671             : }
     672             : 
     673             : /*
     674             :  * tag_hash: hash function for fixed-size tag values
     675             :  */
     676             : uint32
     677   214306564 : tag_hash(const void *key, Size keysize)
     678             : {
     679   214306564 :     return hash_bytes((const unsigned char *) key, (int) keysize);
     680             : }
     681             : 
     682             : /*
     683             :  * uint32_hash: hash function for keys that are uint32 or int32
     684             :  *
     685             :  * (tag_hash works for this case too, but is slower)
     686             :  */
     687             : uint32
     688    43756632 : uint32_hash(const void *key, Size keysize)
     689             : {
     690             :     Assert(keysize == sizeof(uint32));
     691    43756632 :     return hash_bytes_uint32(*((const uint32 *) key));
     692             : }

Generated by: LCOV version 1.13