aGrUM  0.14.1
hashFunc.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 
27 #ifndef GUM_HASH_FUNC_H
28 #define GUM_HASH_FUNC_H
29 
30 // utility provides the std::pair <> template
31 #include <climits>
32 #include <string>
33 #include <type_traits>
34 #include <utility>
35 
36 #include <agrum/agrum.h>
37 #include <agrum/core/refPtr.h>
38 
39 namespace gum {
40 
56  unsigned int __hashTableLog2(const Size nb);
57 
73  struct HashFuncConst {
74  static constexpr Size gold =
75  sizeof(Size) == 4 ? Size(2654435769UL) : Size(11400714819323198486UL);
76  static constexpr Size pi =
77  sizeof(Size) == 4 ? Size(3373259426UL) : Size(14488038916154245684UL);
78  static constexpr Size mask =
79  sizeof(Size) == 4 ? Size(4294967295UL) : Size(18446744073709551615UL);
80  static constexpr Size offset = sizeof(Size) == 4 ? Size(32) : Size(64);
81  };
82 
83 
84  // ===========================================================================
85  // === BASE CLASS SHARED BY ALL THE HASH FUNCTIONS ===
86  // ===========================================================================
146  template < typename Key >
147  class HashFuncBase {
148  public:
164  void resize(const Size new_size);
165 
171  Size size() const;
172 
195  virtual Size operator()(const Key& key) const = 0;
196 
197  protected:
199  Size _hash_size{Size(0)};
200 
202  unsigned int _hash_log2_size{0};
203 
213  Size _hash_mask{Size(0)};
214 
224  unsigned int _right_shift{0};
225  };
226 
227 
228  // ===========================================================================
229  // === GENERIC HASH FUNCTIONS FOR SIMPLE TYPES ===
230  // ===========================================================================
231 
239  template < typename Key >
240  class HashFuncSmallKey : public HashFuncBase< Key > {
241  public:
246 
252  static Size castToSize(const Key& key);
253 
259  virtual Size operator()(const Key& key) const override final;
260  };
261 
262 
271  template < typename Key >
272  class HashFuncSmallCastKey : public HashFuncBase< Key > {
273  public:
278 
284  static Size castToSize(const Key& key);
285 
291  virtual Size operator()(const Key& key) const override final;
292 
293  protected:
298  static constexpr Size _small_key_mask{(Size(1) << (8 * sizeof(Key)))
299  - Size(1)};
300  };
301 
302 
311  template < typename Key >
312  class HashFuncMediumCastKey : public HashFuncBase< Key > {
313  public:
318 
324  static Size castToSize(const Key& key);
325 
331  virtual Size operator()(const Key& key) const override final;
332  };
333 
334 
343  template < typename Key >
344  class HashFuncLargeCastKey : public HashFuncBase< Key > {
345  public:
350 
356  static Size castToSize(const Key& key);
357 
363  virtual Size operator()(const Key& key) const override final;
364  };
365 
366 
379  template < typename Key >
382  using type = typename std::conditional<
383  sizeof(Key) <= sizeof(Size) && std::is_integral< Key >::value,
385  typename std::conditional<
386  sizeof(Key) < sizeof(Size),
388  typename std::conditional<
389  sizeof(Key) == sizeof(Size),
391  typename std::conditional< sizeof(Key) == 2 * sizeof(Size),
394  };
395 
396 
397  // ===========================================================================
398  // === CLASSES FOR NOT DEFINING SEVERAL TIMES THE SAME HASH FUNCTIONS ===
399  // ===========================================================================
400 
401  // a dummy hash type
402  template < typename Key >
403  class dummyHash {};
404 
405  // the general type of the recursive type to select the appropriate hash function
406  template < typename... >
408 
409  // base of the recursive type to select the appropriate hash function
410  template < typename Key >
411  struct HashFuncConditionalType< Key > {
412  using type = Key;
413  };
414 
415  // base of the recursive type to select the appropriate hash function
416  template < typename KEY_TYPE, typename TYPE >
417  struct HashFuncConditionalType< KEY_TYPE, TYPE > {
418  using type = typename std::conditional< std::is_same< KEY_TYPE, TYPE >::value,
420  KEY_TYPE >::type;
421  };
422 
444  template < typename KEY_TYPE, typename FIRST_TYPE, typename... OTHER_TYPES >
445  struct HashFuncConditionalType< KEY_TYPE, FIRST_TYPE, OTHER_TYPES... > {
446  using type = typename std::conditional<
447  std::is_same< KEY_TYPE, FIRST_TYPE >::value,
449  typename HashFuncConditionalType< KEY_TYPE, OTHER_TYPES... >::type >::type;
450  };
451 
452 
453  // ===========================================================================
454  // === HASH FUNCTIONS FOR PAIRS OF KEYS ===
455  // ===========================================================================
456 
468  template < typename key >
469  class HashFunc {};
470 
479  template < typename Key1, typename Key2 >
480  class HashFunc< std::pair< Key1, Key2 > >
481  : public HashFuncBase< std::pair< Key1, Key2 > > {
482  public:
488  static Size castToSize(const std::pair< Key1, Key2 >& key);
489 
495  virtual Size
496  operator()(const std::pair< Key1, Key2 >& key) const override final;
497  };
498 
499 
500  // ===========================================================================
501  // === WIDELY USED HASH FUNCTIONS ===
502  // ===========================================================================
503 
509  template <>
510  class HashFunc< bool > : public HashFuncSmallKey< bool > {};
511 
517  template <>
518  class HashFunc< int > : public HashFuncSmallKey< int > {};
519 
525  template <>
526  class HashFunc< unsigned int > : public HashFuncSmallKey< unsigned int > {};
527 
533  template <>
534  class HashFunc< long > : public HashFuncSmallKey< long > {};
535 
541  template <>
542  class HashFunc< unsigned long > : public HashFuncSmallKey< unsigned long > {};
543 
549  template <>
550  class HashFunc< typename HashFuncConditionalType< std::size_t,
551  unsigned long,
552  unsigned int,
553  long,
554  int >::type >
555  : public HashFuncCastKey< std::size_t >::type {};
556 
562  template <>
563  class HashFunc< float > : public HashFuncCastKey< float >::type {};
564 
570  template <>
571  class HashFunc< double > : public HashFuncCastKey< double >::type {};
572 
578  template < typename Type >
579  class HashFunc< Type* > : public HashFuncCastKey< Type* >::type {};
580 
586  template <>
587  class HashFunc< std::string > : public HashFuncBase< std::string > {
588  public:
594  static Size castToSize(const std::string& key);
595 
601  virtual Size operator()(const std::string& key) const override final;
602  };
603 
604 
610  template <>
611  class HashFunc< std::vector< Idx > >
612  : public HashFuncBase< std::vector< Idx > > {
613  public:
619  static Size castToSize(const std::vector< Idx >& key);
620 
626  virtual Size operator()(const std::vector< Idx >& key) const override final;
627  };
628 
629 
635  template <>
636  class HashFunc< Debug > : public HashFuncBase< Debug > {
637  public:
643  static Size castToSize(const Debug& key);
644 
650  virtual Size operator()(const Debug& key) const override final;
651 
652  template < typename OTHER_KEY >
653  friend class HashFunc;
654  };
655 
656 
663  template < typename Type >
664  class HashFunc< RefPtr< Type > > : public HashFuncBase< RefPtr< Type > > {
665  public:
671  static Size castToSize(const RefPtr< Type >& key);
672 
678  virtual Size operator()(const RefPtr< Type >& key) const override final;
679  };
680 
681 } /* namespace gum */
682 
683 
685 #ifndef GUM_NO_INLINE
686 # include <agrum/core/hashFunc_inl.h>
687 #endif /* GUM_NO_INLINE */
688 
690 #include <agrum/core/hashFunc_tpl.h>
691 
692 #endif /* GUM_HASHFUNC_H */
static constexpr Size pi
Definition: hashFunc.h:76
unsigned int __hashTableLog2(const Size nb)
Returns the size in bits - 1 necessary to store the smallest power of 2 greater than or equal to nb...
Inlined implementation of the basic hash functions.
static constexpr Size offset
Definition: hashFunc.h:80
Generic hash functions for keys castable as Size and whose size is precisely twice that of Size...
Definition: hashFunc.h:344
static constexpr Size gold
Definition: hashFunc.h:74
typename std::conditional< std::is_same< KEY_TYPE, FIRST_TYPE >::value, dummyHash< KEY_TYPE >, typename HashFuncConditionalType< KEY_TYPE, OTHER_TYPES... >::type >::type type
Definition: hashFunc.h:449
STL namespace.
static constexpr Size mask
Definition: hashFunc.h:78
Class providing aGrUM&#39;s "smart" pointers.
Class template representing hashing function of LpCol.
Definition: hashFunc.h:469
gum is the global namespace for all aGrUM entities
Definition: agrum.h:25
Generic hash functions for keys castable as Size whose size is either smaller than Size...
Definition: hashFunc.h:380
Generic hash functions for keys castable as Size and whose size is precisely that of Size...
Definition: hashFunc.h:312
Smart pointersaGrUM&#39;s smart pointers keep track of the number of times the value they point to is ref...
Definition: refPtr.h:114
Template implementation of the basic hash functions.
Useful constants for hash functions.
Definition: hashFunc.h:73
Generic hash functions for numeric keys smaller than or equal to Size.
Definition: hashFunc.h:240
typename std::conditional< std::is_same< KEY_TYPE, TYPE >::value, dummyHash< KEY_TYPE >, KEY_TYPE >::type type
Definition: hashFunc.h:420
All hash functions should inherit from this class.
Definition: hashFunc.h:147
typename std::conditional< sizeof(Key)<=sizeof(Size) &&std::is_integral< Key >::value, HashFuncSmallKey< Key >, typename std::conditional< sizeof(Key)< sizeof(Size), HashFuncSmallCastKey< Key >, typename std::conditional< sizeof(Key)==sizeof(Size), HashFuncMediumCastKey< Key >, typename std::conditional< sizeof(Key)==2 *sizeof(Size), HashFuncLargeCastKey< Key >, void >::type >::type >::type >::type type
The type used by this class.
Definition: hashFunc.h:393
This class enables to safely define hash functions for types that may or may not already has defined ...
Definition: hashFunc.h:407
std::size_t Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:45
Generic hash functions for keys castable as Size and whose size is strictly smaller than that of Size...
Definition: hashFunc.h:272