aGrUM  0.13.2
hashFunc_tpl.h
Go to the documentation of this file.
1 /***************************************************************************
2  * Copyright (C) 2005 by Christophe GONZALES and Pierre-Henri WUILLEMIN *
3  * {prenom.nom}_at_lip6.fr *
4  * *
5  * This program is free software; you can redistribute it and/or modify *
6  * it under the terms of the GNU General Public License as published by *
7  * the Free Software Foundation; either version 2 of the License, or *
8  * (at your option) any later version. *
9  * *
10  * This program is distributed in the hope that it will be useful, *
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of *
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
13  * GNU General Public License for more details. *
14  * *
15  * You should have received a copy of the GNU General Public License *
16  * along with this program; if not, write to the *
17  * Free Software Foundation, Inc., *
18  * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. *
19  ***************************************************************************/
20 
28 // to help IDE parser
29 #include <agrum/core/hashFunc.h>
30 
31 namespace gum {
32 
33  // ===========================================================================
34  // === GUM_HASH_FUNC_BASE IMPLEMENTATION ===
35  // ===========================================================================
36 
37  //@beforeMerging authorized gum::HashFunc<std::pair<unsigned int, double> >
38  // for instance when gum::Idx==gum::Size===unsigned int
39 
40  template < typename Key >
41  INLINE void HashFuncBase< Key >::resize(Size new_size) {
42  // things work properly only for hashtables with at least 2 elements
43  if (new_size < 2) {
44  GUM_ERROR(SizeError, "the size of the hashtable is too small");
45  }
46 
47  _hash_log2_size = __hashTableLog2(new_size);
48  _hash_size = Size(1) << _hash_log2_size;
49  _hash_mask = _hash_size - 1;
50  }
51 
52  template < typename Key >
53  INLINE Size HashFuncBase< Key >::size() const noexcept {
54  return _hash_size;
55  }
56 
57  // ===========================================================================
58  // === GUM_HASH_FUNC_SMALL_KEY IMPLEMENTATION ===
59  // ===========================================================================
60 
61  template < typename Key >
62  INLINE void HashFuncSmallKey< Key >::resize(Size new_size) {
63  static_assert(std::is_integral< Key >::value
64  && sizeof(Key) <= sizeof(unsigned long),
65  "Error: using HashFuncSmallKey for a key which cannot be "
66  "converted (without narrowing) into a long int");
69  }
70 
71  template < typename Key >
72  INLINE Size HashFuncSmallKey< Key >::operator()(const Key& key) const {
73  return (((unsigned long)key * HashFuncConst::gold) >> _right_shift);
74  }
75 
76  // ===========================================================================
77  // === GUM_HASH_FUNC_SMALL_CAST_KEY IMPLEMENTATION ===
78  // ===========================================================================
79 
80  template < typename Key >
82  _small_key_mask((1UL << (8 * sizeof(Key))) - 1UL) {
83  static_assert(sizeof(Key) < sizeof(unsigned long),
84  "Error: using HashFuncSmallCastKey for a key whose size "
85  "is longer than or equal to that of long int");
86  }
87 
88  template < typename Key >
89  INLINE void HashFuncSmallCastKey< Key >::resize(Size new_size) {
92  }
93 
94  template < typename Key >
95  INLINE Size HashFuncSmallCastKey< Key >::castToSize(const Key& key) const {
96  return *((unsigned long*)(&key)) & _small_key_mask;
97  }
98 
99  template < typename Key >
100  INLINE Size HashFuncSmallCastKey< Key >::operator()(const Key& key) const {
101  return (((*((unsigned long*)(&key)) & _small_key_mask) * HashFuncConst::gold)
102  >> _right_shift);
103  }
104 
105  // ===========================================================================
106  // === GUM_HASH_FUNC_MEDIUM_CAST_KEY IMPLEMENTATION ===
107  // ===========================================================================
108 
109  template < typename Key >
111  static_assert(sizeof(Key) == sizeof(unsigned long),
112  "Error: using HashFuncMediumCastKey for a key whose size "
113  "is different from that of long int");
114  HashFuncBase< Key >::resize(new_size);
116  }
117 
118  template < typename Key >
119  INLINE Size HashFuncMediumCastKey< Key >::castToSize(const Key& key) const {
120  return *((unsigned long*)(&key));
121  }
122 
123  template < typename Key >
124  INLINE Size HashFuncMediumCastKey< Key >::operator()(const Key& key) const {
125  return ((*((unsigned long*)(&key)) * HashFuncConst::gold) >> _right_shift);
126  }
127 
128  // ===========================================================================
129  // === GUM_HASH_FUNC_LARGE_CAST_KEY IMPLEMENTATION ===
130  // ===========================================================================
131 
132  template < typename Key >
134  static_assert(sizeof(Key) == 2 * sizeof(unsigned long),
135  "Error: using HashFuncLargeCastKey for a key whose size "
136  "is different from twice that of long int");
137  HashFuncBase< Key >::resize(new_size);
139  }
140 
141  template < typename Key >
142  INLINE Size HashFuncLargeCastKey< Key >::castToSize(const Key& key) const {
143  const unsigned long* ptr = reinterpret_cast< const unsigned long* >(&key);
144  return ptr[0] ^ ptr[1];
145  }
146 
147  template < typename Key >
148  INLINE Size HashFuncLargeCastKey< Key >::operator()(const Key& key) const {
149  const unsigned long* ptr = reinterpret_cast< const unsigned long* >(&key);
150  return ((ptr[0] ^ ptr[1]) * HashFuncConst::gold) >> _right_shift;
151  }
152 
153  // ===========================================================================
154  // === GUM_HASH_FUNC_SMALL_KEY_PAIR IMPLEMENTATION ===
155  // ===========================================================================
156 
157  template < typename Key1, typename Key2 >
159  static_assert(std::is_integral< Key1 >::value
160  && sizeof(Key1) <= sizeof(unsigned long),
161  "Error: using HashFuncSmallKeyPair for key1 which cannot be "
162  "converted (without narrowing) into a long int");
163  static_assert(std::is_integral< Key2 >::value
164  && sizeof(Key2) <= sizeof(unsigned long),
165  "Error: using HashFuncSmallKeyPair for key2 which cannot be "
166  "converted (without narrowing) into a long int");
170  }
171 
172  template < typename Key1, typename Key2 >
174  operator()(const std::pair< Key1, Key2 >& key) const {
175  return (((unsigned long)key.first * HashFuncConst::gold
176  + (unsigned long)key.second * HashFuncConst::pi)
177  >> _right_shift);
178  }
179 
180  // ===========================================================================
181  // === GUM_HASH_FUNC_CAST_KEY_PAIR IMPLEMENTATION ===
182  // ===========================================================================
183 
184  template < typename Key1, typename Key2, typename Func1, typename Func2 >
185  INLINE void
187  __func1.resize(new_size);
188  __func2.resize(new_size);
192  }
193 
194  template < typename Key1, typename Key2, typename Func1, typename Func2 >
196  operator()(const std::pair< Key1, Key2 >& key) const {
197  return (__func1.castToSize(key.first) * HashFuncConst::gold
198  + __func2.castToSize(key.second) * HashFuncConst::pi)
199  >> _right_shift;
200  }
201 
202  template < typename Type >
203  INLINE Size HashFunc< RefPtr< Type > >::
204  operator()(const RefPtr< Type >& key) const {
205  static_assert(sizeof(RefPtr< Type >) == sizeof(long),
206  "Error: HashFunc<Type*> assumes that pointers have a size "
207  "equal to a long integer");
208  return HashFunc< unsigned int* >::operator()(key.__refCountPtr());
209  }
210 
211 } /* namespace gum */
unsigned long Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:50
HashFuncSmallCastKey()
Class constructor.
Definition: hashFunc_tpl.h:81
static constexpr unsigned long gold
Definition: hashFunc.h:80
Size operator()(const std::pair< Key1, Key2 > &key) const override
Computes the hashed value of a key.
Definition: hashFunc_tpl.h:196
void resize(Size new_size) override
Update the hash function to take into account a resize of the hash table.
Definition: hashFunc_tpl.h:158
unsigned int _right_shift
The number of right shift to perform to get correct hashed values.
Definition: hashFunc.h:295
void resize(Size new_size) override
Update the hash function to take into account a resize of the hash table.
Definition: hashFunc_tpl.h:89
Size operator()(const Key &key) const
Computes the hashed value of a key.
Definition: hashFunc_tpl.h:148
void resize(Size new_size) override
Update the hash function to take into account a resize of the hash table.
Definition: hashFunc_tpl.h:186
Size castToSize(const Key &key) const
Returns the value of a key as an unsigned long.
Definition: hashFunc_tpl.h:119
Size castToSize(const Key &key) const
Cast key to the exepcted type.
Definition: hashFunc_tpl.h:142
void resize(Size new_size) override
Update the hash function to take into account a resize of the hash table.
Definition: hashFunc_tpl.h:133
Classes providing basic hash functions for hash tables.
Class template representing hashing function of LpCol.
Definition: hashFunc.h:612
gum is the global namespace for all aGrUM entities
Definition: agrum.h:25
void resize(Size new_size) override
Update the hash function to take into account a resize of the hash table.
Definition: hashFunc_tpl.h:110
Smart pointersaGrUM&#39;s smart pointers keep track of the number of times the value they point to is ref...
Definition: refPtr.h:114
Size operator()(const std::pair< Key1, Key2 > &key) const override
Computes the hashed value of a key.
Definition: hashFunc_tpl.h:174
void resize(Size new_size) override
Update the hash function to take into account a resize of the hash table.
Definition: hashFunc_tpl.h:62
unsigned int _hash_log2_size
Log of the size of the hash table in base 2.
Definition: hashFunc.h:188
Size castToSize(const Key &key) const
Returns the value of a key as an unsigned long.
Definition: hashFunc_tpl.h:95
static constexpr size_t offset
Definition: hashFunc.h:83
unsigned int __hashTableLog2(const Size &nb)
Returns the size in bits - 1 necessary to store the smallest power of 2 greater or equal to nb...
All hash functions should inherit from this class.
Definition: hashFunc.h:150
Size size() const noexcept
Returns the hash table size as known by the hash function.
Definition: hashFunc_tpl.h:53
Size operator()(const Key &key) const override
Computes the hashed value of a key.
Definition: hashFunc_tpl.h:124
virtual void resize(Size new_size)
Update the hash function to take into account a resize of the hash table.
Definition: hashFunc_tpl.h:41
Size operator()(const Key &key) const override
Computes the hashed value of a key.
Definition: hashFunc_tpl.h:72
static constexpr unsigned long pi
Definition: hashFunc.h:81
#define GUM_ERROR(type, msg)
Definition: exceptions.h:66
Size operator()(const Key &key) const override
Computes the hashed value of a key.
Definition: hashFunc_tpl.h:100
unsigned long _small_key_mask
An additional mask to ensure that keys with fewer bits than unsigned longs are cast correctly...
Definition: hashFunc.h:301