PostgreSQL Source Code git master
Macros | Functions
hashfn.c File Reference
#include "postgres.h"
#include "common/hashfn.h"
#include "port/pg_bitutils.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)   pg_rotate_left32(x, k)
 
#define mix(a, b, c)
 
#define final(a, b, c)
 

Functions

uint32 hash_bytes (const unsigned char *k, int keylen)
 
uint64 hash_bytes_extended (const unsigned char *k, int keylen, uint64 seed)
 
uint32 hash_bytes_uint32 (uint32 k)
 
uint64 hash_bytes_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)
 

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); \
}
rot
#define rot(x, k)
Definition: hashfn.c:48
b
int b
Definition: isn.c:69
a
int a
Definition: isn.c:68
c
char * c
Definition: preproc-cursor.c:31

Definition at line 116 of file hashfn.c.

◆ 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; \
}

Definition at line 82 of file hashfn.c.

◆ rot

#define rot (   x,
  k 
)    pg_rotate_left32(x, k)

Definition at line 48 of file hashfn.c.

◆ UINT32_ALIGN_MASK

#define UINT32_ALIGN_MASK   (sizeof(uint32) - 1)

Definition at line 46 of file hashfn.c.

Function Documentation

◆ hash_bytes()

uint32 hash_bytes ( const unsigned char *  k,
int  keylen 
)

Definition at line 146 of file hashfn.c.

147{
148 uint32 a,
149 b,
150 c,
151 len;
152
153 /* Set up the internal state */
154 len = keylen;
155 a = b = c = 0x9e3779b9 + len + 3923095;
156
157 /* If the source pointer is word-aligned, we use word-wide fetches */
158 if (((uintptr_t) k & UINT32_ALIGN_MASK) == 0)
159 {
160 /* Code path for aligned source data */
161 const uint32 *ka = (const uint32 *) k;
162
163 /* handle most of the key */
164 while (len >= 12)
165 {
166 a += ka[0];
167 b += ka[1];
168 c += ka[2];
169 mix(a, b, c);
170 ka += 3;
171 len -= 12;
172 }
173
174 /* handle the last 11 bytes */
175 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 switch (len)
217 {
218 case 11:
219 c += ((uint32) k[10] << 24);
220 /* fall through */
221 case 10:
222 c += ((uint32) k[9] << 16);
223 /* fall through */
224 case 9:
225 c += ((uint32) k[8] << 8);
226 /* fall through */
227 case 8:
228 /* the lowest byte of c is reserved for the length */
229 b += ka[1];
230 a += ka[0];
231 break;
232 case 7:
233 b += ((uint32) k[6] << 16);
234 /* fall through */
235 case 6:
236 b += ((uint32) k[5] << 8);
237 /* fall through */
238 case 5:
239 b += k[4];
240 /* fall through */
241 case 4:
242 a += ka[0];
243 break;
244 case 3:
245 a += ((uint32) k[2] << 16);
246 /* fall through */
247 case 2:
248 a += ((uint32) k[1] << 8);
249 /* fall through */
250 case 1:
251 a += k[0];
252 /* case 0: nothing left to add */
253 }
254#endif /* WORDS_BIGENDIAN */
255 }
256 else
257 {
258 /* Code path for non-aligned source data */
259
260 /* handle most of the key */
261 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 a += (k[0] + ((uint32) k[1] << 8) + ((uint32) k[2] << 16) + ((uint32) k[3] << 24));
269 b += (k[4] + ((uint32) k[5] << 8) + ((uint32) k[6] << 16) + ((uint32) k[7] << 24));
270 c += (k[8] + ((uint32) k[9] << 8) + ((uint32) k[10] << 16) + ((uint32) k[11] << 24));
271#endif /* WORDS_BIGENDIAN */
272 mix(a, b, c);
273 k += 12;
274 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 switch (len)
318 {
319 case 11:
320 c += ((uint32) k[10] << 24);
321 /* fall through */
322 case 10:
323 c += ((uint32) k[9] << 16);
324 /* fall through */
325 case 9:
326 c += ((uint32) k[8] << 8);
327 /* fall through */
328 case 8:
329 /* the lowest byte of c is reserved for the length */
330 b += ((uint32) k[7] << 24);
331 /* fall through */
332 case 7:
333 b += ((uint32) k[6] << 16);
334 /* fall through */
335 case 6:
336 b += ((uint32) k[5] << 8);
337 /* fall through */
338 case 5:
339 b += k[4];
340 /* fall through */
341 case 4:
342 a += ((uint32) k[3] << 24);
343 /* fall through */
344 case 3:
345 a += ((uint32) k[2] << 16);
346 /* fall through */
347 case 2:
348 a += ((uint32) k[1] << 8);
349 /* fall through */
350 case 1:
351 a += k[0];
352 /* case 0: nothing left to add */
353 }
354#endif /* WORDS_BIGENDIAN */
355 }
356
357 final(a, b, c);
358
359 /* report the result */
360 return c;
361}
uint32
uint32_t uint32
Definition: c.h:488
UINT32_ALIGN_MASK
#define UINT32_ALIGN_MASK
Definition: hashfn.c:46
mix
#define mix(a, b, c)
Definition: hashfn.c:82
len
const void size_t len
Definition: pg_crc32c_sse42.c:25

References a, b, len, mix, and UINT32_ALIGN_MASK.

Referenced by datum_image_hash(), hash_any(), hash_string_pointer(), json_unique_hash(), missing_hash(), string_hash(), and tag_hash().

◆ hash_bytes_extended()

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

Definition at line 372 of file hashfn.c.

373{
374 uint32 a,
375 b,
376 c,
377 len;
378
379 /* Set up the internal state */
380 len = keylen;
381 a = b = c = 0x9e3779b9 + len + 3923095;
382
383 /* If the seed is non-zero, use it to perturb the internal state. */
384 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 a += (uint32) (seed >> 32);
392 b += (uint32) seed;
393 mix(a, b, c);
394 }
395
396 /* If the source pointer is word-aligned, we use word-wide fetches */
397 if (((uintptr_t) k & UINT32_ALIGN_MASK) == 0)
398 {
399 /* Code path for aligned source data */
400 const uint32 *ka = (const uint32 *) k;
401
402 /* handle most of the key */
403 while (len >= 12)
404 {
405 a += ka[0];
406 b += ka[1];
407 c += ka[2];
408 mix(a, b, c);
409 ka += 3;
410 len -= 12;
411 }
412
413 /* handle the last 11 bytes */
414 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 switch (len)
456 {
457 case 11:
458 c += ((uint32) k[10] << 24);
459 /* fall through */
460 case 10:
461 c += ((uint32) k[9] << 16);
462 /* fall through */
463 case 9:
464 c += ((uint32) k[8] << 8);
465 /* fall through */
466 case 8:
467 /* the lowest byte of c is reserved for the length */
468 b += ka[1];
469 a += ka[0];
470 break;
471 case 7:
472 b += ((uint32) k[6] << 16);
473 /* fall through */
474 case 6:
475 b += ((uint32) k[5] << 8);
476 /* fall through */
477 case 5:
478 b += k[4];
479 /* fall through */
480 case 4:
481 a += ka[0];
482 break;
483 case 3:
484 a += ((uint32) k[2] << 16);
485 /* fall through */
486 case 2:
487 a += ((uint32) k[1] << 8);
488 /* fall through */
489 case 1:
490 a += k[0];
491 /* case 0: nothing left to add */
492 }
493#endif /* WORDS_BIGENDIAN */
494 }
495 else
496 {
497 /* Code path for non-aligned source data */
498
499 /* handle most of the key */
500 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 a += (k[0] + ((uint32) k[1] << 8) + ((uint32) k[2] << 16) + ((uint32) k[3] << 24));
508 b += (k[4] + ((uint32) k[5] << 8) + ((uint32) k[6] << 16) + ((uint32) k[7] << 24));
509 c += (k[8] + ((uint32) k[9] << 8) + ((uint32) k[10] << 16) + ((uint32) k[11] << 24));
510#endif /* WORDS_BIGENDIAN */
511 mix(a, b, c);
512 k += 12;
513 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 switch (len)
557 {
558 case 11:
559 c += ((uint32) k[10] << 24);
560 /* fall through */
561 case 10:
562 c += ((uint32) k[9] << 16);
563 /* fall through */
564 case 9:
565 c += ((uint32) k[8] << 8);
566 /* fall through */
567 case 8:
568 /* the lowest byte of c is reserved for the length */
569 b += ((uint32) k[7] << 24);
570 /* fall through */
571 case 7:
572 b += ((uint32) k[6] << 16);
573 /* fall through */
574 case 6:
575 b += ((uint32) k[5] << 8);
576 /* fall through */
577 case 5:
578 b += k[4];
579 /* fall through */
580 case 4:
581 a += ((uint32) k[3] << 24);
582 /* fall through */
583 case 3:
584 a += ((uint32) k[2] << 16);
585 /* fall through */
586 case 2:
587 a += ((uint32) k[1] << 8);
588 /* fall through */
589 case 1:
590 a += k[0];
591 /* case 0: nothing left to add */
592 }
593#endif /* WORDS_BIGENDIAN */
594 }
595
596 final(a, b, c);
597
598 /* report the result */
599 return ((uint64) b << 32) | c;
600}
uint64
uint64_t uint64
Definition: c.h:489

References a, b, len, mix, and UINT32_ALIGN_MASK.

Referenced by hash_any_extended().

◆ hash_bytes_uint32()

uint32 hash_bytes_uint32 ( uint32  k)

Definition at line 610 of file hashfn.c.

611{
612 uint32 a,
613 b,
614 c;
615
616 a = b = c = 0x9e3779b9 + (uint32) sizeof(uint32) + 3923095;
617 a += k;
618
619 final(a, b, c);
620
621 /* report the result */
622 return c;
623}

References a, and b.

Referenced by hash_uint32(), hashagg_spill_tuple(), json_unique_hash(), and uint32_hash().

◆ hash_bytes_uint32_extended()

uint64 hash_bytes_uint32_extended ( uint32  k,
uint64  seed 
)

Definition at line 631 of file hashfn.c.

632{
633 uint32 a,
634 b,
635 c;
636
637 a = b = c = 0x9e3779b9 + (uint32) sizeof(uint32) + 3923095;
638
639 if (seed != 0)
640 {
641 a += (uint32) (seed >> 32);
642 b += (uint32) seed;
643 mix(a, b, c);
644 }
645
646 a += k;
647
648 final(a, b, c);
649
650 /* report the result */
651 return ((uint64) b << 32) | c;
652}

References a, b, and mix.

Referenced by bloom_add_value(), bloom_contains_value(), and hash_uint32_extended().

◆ string_hash()

uint32 string_hash ( const void *  key,
Size  keysize 
)

Definition at line 660 of file hashfn.c.

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 Size s_len = strlen((const char *) key);
668
669 s_len = Min(s_len, keysize - 1);
670 return hash_bytes((const unsigned char *) key, (int) s_len);
671}
Min
#define Min(x, y)
Definition: c.h:961
Size
size_t Size
Definition: c.h:562
hash_bytes
uint32 hash_bytes(const unsigned char *k, int keylen)
Definition: hashfn.c:146

References hash_bytes(), sort-test::key, and Min.

Referenced by dshash_strhash(), and hash_create().

◆ tag_hash()

uint32 tag_hash ( const void *  key,
Size  keysize 
)

Definition at line 677 of file hashfn.c.

678{
679 return hash_bytes((const unsigned char *) key, (int) keysize);
680}

References hash_bytes(), and sort-test::key.

Referenced by dshash_memhash(), and hash_create().

◆ uint32_hash()

uint32 uint32_hash ( const void *  key,
Size  keysize 
)

Definition at line 688 of file hashfn.c.

689{
690 Assert(keysize == sizeof(uint32));
691 return hash_bytes_uint32(*((const uint32 *) key));
692}
Assert
#define Assert(condition)
Definition: c.h:815
hash_bytes_uint32
uint32 hash_bytes_uint32(uint32 k)
Definition: hashfn.c:610

References Assert, hash_bytes_uint32(), and sort-test::key.

Referenced by hash_create().