aGrUM  0.13.2
hashFunc_inl.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  ***************************************************************************/
25 #include <string>
26 #include <utility>
27 
28 #include <agrum/agrum.h>
29 
30 // to ease parsing in IDE
31 #include <agrum/core/hashFunc.h>
32 
33 #ifndef DOXYGEN_SHOULD_SKIP_THIS
34 
35 namespace gum {
36 
37  /* in aGrUM, the sizes of hash tables (number of slots) are powers of 2. This
38  * is
39  * not actually compulsory for the hash function we use. However, as it
40  * speeds up the computations of hashed values, we chose to impose
41  * this restriction. Function __hashTableLog2 thus returns the size in
42  * bits - 1 necessary to store the smallest power of 2 greater than or
43  * equal nb. */
44  INLINE unsigned int __hashTableLog2(const Size& nb) {
45  unsigned int i = 0;
46 
47  for (Size nbb = nb; nbb > 1UL; ++i, nbb >>= 1) {};
48 
49  return ((1UL << i) < nb ? i + 1U : i);
50  }
51 
54  INLINE Size HashFunc< std::string >::operator()(const std::string& key) const {
55  Size h = 0;
56  auto size = (unsigned int)key.size();
57  const char* char_ptr = key.c_str();
58  auto int_ptr = (const unsigned long*)char_ptr;
59 
60  for (; size >= sizeof(unsigned long);
61  size -= sizeof(unsigned long), ++int_ptr) {
62  h = h * HashFuncConst::gold + *int_ptr;
63  }
64 
65  for (char_ptr = (const char*)int_ptr; size != 0; --size, ++char_ptr) {
66  h = 19 * h + *char_ptr;
67  }
68 
69  return (h & _hash_mask);
70  }
71 
74  INLINE Size HashFunc< std::pair< std::string, std::string > >::
75  operator()(const std::pair< std::string, std::string >& key) const {
76  Size h = 0;
77 
78  const std::string& s1 = key.first;
79  auto size = (unsigned int)s1.size();
80  const char* char_ptr = s1.c_str();
81  auto int_ptr = (const unsigned long*)char_ptr;
82 
83  for (; size >= sizeof(unsigned long);
84  size -= sizeof(unsigned long), ++int_ptr) {
85  h = h * HashFuncConst::gold + *int_ptr;
86  }
87 
88  for (char_ptr = (const char*)int_ptr; size != 0; --size, ++char_ptr) {
89  h = 19 * h + *char_ptr;
90  }
91 
92  const std::string& s2 = key.second;
93  size = (unsigned int)s2.size();
94  char_ptr = s2.c_str();
95  int_ptr = (const unsigned long*)char_ptr;
96 
97  for (; size >= sizeof(unsigned long);
98  size -= sizeof(unsigned long), ++int_ptr) {
99  h = h * HashFuncConst::gold + *int_ptr;
100  }
101 
102  for (char_ptr = (const char*)int_ptr; size != 0; --size, ++char_ptr) {
103  h = 19 * h + *char_ptr;
104  }
105 
106  return (h & this->_hash_mask);
107  }
108 
111  INLINE Size HashFunc< std::vector< Idx > >::
112  operator()(const std::vector< Idx >& key) const {
113  Size h = 0;
114  Size siz = Size(key.size());
115  for (Size i = 0; i < siz; ++i)
116  h += i * key[i];
117 
118  return ((h * HashFuncConst::gold) & this->_hash_mask);
119  }
120 
123  INLINE Size HashFunc< Debug >::operator()(const Debug& key) const {
124  Size h = 0;
125 
126  for (size_t i = 0, j = key.size(); i < j; ++i)
127  h = 19 * h + key[i];
128 
129  return ((h * HashFuncConst::gold) & this->_hash_mask);
130  }
131 
132 } /* namespace gum */
133 
134 #endif /* DOXYGEN_SHOULD_SKIP_THIS */
unsigned long Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:50
static constexpr unsigned long gold
Definition: hashFunc.h:80
Size operator()(const Debug &key) const
Computes the hashed value of a key.
Classes providing basic hash functions for hash tables.
gum is the global namespace for all aGrUM entities
Definition: agrum.h:25
Size operator()(const std::string &key) const override
Computes the hashed value of a key.
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...