DDD 1.9.0.20250409152518
hashfunc.hh
Go to the documentation of this file.
1/****************************************************************************/
2/* */
3/* This file is part of libDDD, a library for manipulation of DDD and SDD. */
4/* */
5/* Copyright (C) 2001-2008 Yann Thierry-Mieg, Jean-Michel Couvreur */
6/* and Denis Poitrenaud */
7/* Based on a file written by Alexandre Duret-Lutz for Spot, */
8/* Alexandre.Duret-Lutz@lip6.fr */
9/* */
10/* This program is free software; you can redistribute it and/or modify */
11/* it under the terms of the GNU Lesser General Public License as */
12/* published by the Free Software Foundation; either version 3 of the */
13/* License, or (at your option) any later version. */
14/* This program is distributed in the hope that it will be useful, */
15/* but WITHOUT ANY WARRANTY; without even the implied warranty of */
16/* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */
17/* GNU LEsserGeneral Public License for more details. */
18/* */
19/* You should have received a copy of the GNU Lesser General Public License */
20/* along with this program; if not, write to the Free Software */
21/*Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */
22/* */
23/****************************************************************************/
24#ifndef __DDD_MISC_HASHFUNC_HH
25#define __DDD_MISC_HASHFUNC_HH
26
27/******************************************************************************/
28
29#include <stdint.h>
30
31namespace ddd
32{
36
41 inline size_t
42 wang32_hash(size_t key)
43 {
44 // We assume that size_t has at least 32bits.
45 key += ~(key << 15);
46 key ^= (key >> 10);
47 key += (key << 3);
48 key ^= (key >> 6);
49 key += ~(key << 11);
50 key ^= (key >> 16);
51 return key;
52 }
53
56 inline uint32_t int32_hash(uint32_t a) {
57 a = (a ^ 61) ^ (a >> 16);
58 a = a + (a << 3);
59 a = a ^ (a >> 4);
60 a = a * 0x27d4eb2d;
61 a = a ^ (a >> 15);
62 return a;
63 }
64
65
72 inline size_t
73 knuth32_hash(size_t key)
74 {
75 // 2654435761 is the golden ratio of 2^32. The right shift of 3
76 // bits assumes that all objects are aligned on a 8 byte boundary.
77 return (key >> 3) * 2654435761U;
78 }
80}
81
82#endif // DDD_MISC_HASHFUNC_HH
size_t wang32_hash(size_t key)
Thomas Wang's 32 bit hash function.
Definition hashfunc.hh:42
uint32_t int32_hash(uint32_t a)
Another of Wang's fast hash with a magic number.
Definition hashfunc.hh:56
size_t knuth32_hash(size_t key)
Knuth's Multiplicative hash function.
Definition hashfunc.hh:73
Definition hashfunc.hh:32

Please comment this page and report errors about it on the RefDocComments page.
Generated on Wed Apr 9 2025 15:27:42 for DDD by doxygen 1.9.8