aGrUM  0.13.2
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 #if ULONG_MAX == 4294967295UL // unsigned long = 32 bits
75  static constexpr unsigned long gold = 2654435769UL;
76  static constexpr unsigned long pi = 3373259426UL;
77  static constexpr unsigned long mask = 4294967295UL;
78  static constexpr size_t offset = 32;
79 #else // unsigned long = 64 bits
80  static constexpr unsigned long gold = 11400714819323198486UL;
81  static constexpr unsigned long pi = 14488038916154245684UL;
82  static constexpr unsigned long mask = 18446744073709551615UL;
83  static constexpr size_t offset = 64;
84 #endif /* unsigned long = 32 bits */
85  };
86 
87  // ===========================================================================
88  // === BASE CLASS SHARED BY ALL THE HASH FUNCTIONS ===
89  // ===========================================================================
149  template < typename Key >
150  class HashFuncBase {
151  public:
168  virtual void resize(Size new_size);
169 
175  virtual Size operator()(const Key& key) const = 0;
176 
181  Size size() const noexcept;
182 
183  protected:
185  Size _hash_size{0};
186 
188  unsigned int _hash_log2_size{0};
189 
194  Size _hash_mask{0};
195  };
196 
197  // ===========================================================================
198  // === GENERIC MULTIPURPOSE HASH FUNCTIONS ===
199  // ===========================================================================
200 
209  template < typename Key >
210  class HashFuncSmallKey : private HashFuncBase< Key > {
211  public:
214 
231  void resize(Size new_size) override;
232 
238  Size operator()(const Key& key) const override;
239 
240  protected:
242  unsigned int _right_shift;
243  };
244 
253  template < typename Key >
254  class HashFuncSmallCastKey : private HashFuncBase< Key > {
255  public:
260 
277  void resize(Size new_size) override;
278 
284  Size castToSize(const Key& key) const;
285 
291  Size operator()(const Key& key) const override;
292 
293  protected:
295  unsigned int _right_shift;
296 
301  unsigned long _small_key_mask;
302  };
303 
312  template < typename Key >
313  class HashFuncMediumCastKey : private HashFuncBase< Key > {
314  public:
317 
334  void resize(Size new_size) override;
335 
341  Size operator()(const Key& key) const override;
342 
348  Size castToSize(const Key& key) const;
349 
350 
351  protected:
353  unsigned int _right_shift;
354  };
355 
364  template < typename Key >
365  class HashFuncLargeCastKey : private HashFuncBase< Key > {
366  public:
369 
386  void resize(Size new_size) override;
387 
393  Size castToSize(const Key& key) const;
394 
400  Size operator()(const Key& key) const;
401 
402  protected:
404  unsigned int _right_shift;
405  };
406 
407 
417  template < typename Key1, typename Key2 >
418  class HashFuncSmallKeyPair : public HashFuncBase< std::pair< Key1, Key2 > > {
419  public:
436  void resize(Size new_size) override;
437 
443  Size operator()(const std::pair< Key1, Key2 >& key) const override;
444 
445  protected:
447  unsigned int _right_shift;
448  };
449 
461  template < typename Key1, typename Key2, typename Func1, typename Func2 >
462  class HashFuncAllCastKeyPair : public HashFuncBase< std::pair< Key1, Key2 > > {
463  public:
480  void resize(Size new_size) override;
481 
487  Size operator()(const std::pair< Key1, Key2 >& key) const override;
488 
489  protected:
491  unsigned int _right_shift;
492 
493  private:
495  Func1 __func1;
497  Func2 __func2;
498  };
499 
500 
501  // ===========================================================================
502  // === GENERAL HASH FUNCTIONS CASTING AND CONDITIONAL TYPES ===
503  // ===========================================================================
504 
514  template < typename T >
517  using type = typename std::conditional<
518  sizeof(T) < sizeof(long),
520  typename std::conditional< sizeof(T) == 2 * sizeof(long),
523  };
524 
525 
535  template < typename T1, typename T2 >
539 
542 
545  };
546 
547 
548  template < typename T >
549  class dummyHash {};
550 
551  template < typename... >
553 
554  template < typename HASH_TYPE >
555  struct HashFuncConditionalType< HASH_TYPE > {
556  using type = HASH_TYPE;
557  };
558 
559  template < typename HASH_TYPE, typename TYPE >
560  struct HashFuncConditionalType< HASH_TYPE, TYPE > {
561  using type = typename std::conditional< std::is_same< HASH_TYPE, TYPE >::value,
563  HASH_TYPE >::type;
564  };
565 
587  template < typename HASH_TYPE, typename FIRST_TYPE, typename... OTHER_TYPES >
588  struct HashFuncConditionalType< HASH_TYPE, FIRST_TYPE, OTHER_TYPES... > {
589  using type = typename std::conditional<
590  std::is_same< HASH_TYPE, FIRST_TYPE >::value,
592  typename HashFuncConditionalType< HASH_TYPE, OTHER_TYPES... >::type >::type;
593  };
594 
595 
596  // ===========================================================================
597  // === WIDELY USED HASH FUNCTIONS ===
598  // ===========================================================================
599 
611  template < typename key >
612  class HashFunc {};
613 
619  template <>
620  class HashFunc< bool > : public HashFuncSmallKey< bool > {};
621 
627  template <>
628  class HashFunc< int > : public HashFuncSmallKey< int > {};
629 
635  template <>
636  class HashFunc< unsigned int > : public HashFuncSmallKey< unsigned int > {};
637 
643  template <>
644  class HashFunc< long > : public HashFuncSmallKey< long > {};
645 
651  template <>
652  class HashFunc< unsigned long > : public HashFuncSmallKey< unsigned long > {};
653 
659  template <>
660  class HashFunc< typename HashFuncConditionalType< std::size_t,
661  unsigned long,
662  unsigned int,
663  long,
664  int >::type >
665  : public HashFuncCastKey< std::size_t >::type {};
666 
672  template <>
673  class HashFunc< float > : public HashFuncCastKey< float >::type {};
674 
680  template <>
681  class HashFunc< double > : public HashFuncCastKey< double >::type {};
682 
688  template < typename Type >
689  class HashFunc< Type* > : public HashFuncCastKey< Type* >::type {};
690 
696  template <>
697  class HashFunc< std::pair< int, int > >
698  : public HashFuncSmallKeyPair< int, int > {};
699 
705  template <>
706  class HashFunc< std::pair< unsigned int, unsigned int > >
707  : public HashFuncSmallKeyPair< unsigned int, unsigned int > {};
708 
714  template <>
715  class HashFunc< std::pair< long, long > >
716  : public HashFuncSmallKeyPair< long, long > {};
717 
723  template <>
724  class HashFunc< std::pair< unsigned long, unsigned long > >
725  : public HashFuncSmallKeyPair< unsigned long, unsigned long > {};
726 
732  template <>
733  class HashFunc< std::pair< float, float > >
734  : public HashFuncCastKeyPair< float, float >::type {};
735 
741  template <>
742  class HashFunc< std::pair< double, double > >
743  : public HashFuncCastKeyPair< float, float >::type {};
744 
750  template <>
751  class HashFunc< std::pair< double, long unsigned int > >
752  : public HashFuncCastKeyPair< double, long unsigned int >::type {};
753 
762  template <>
763  class HashFunc< std::pair< long unsigned int, double > >
764  : public HashFuncCastKeyPair< long unsigned int, double >::type {};
765 
771  template <>
772  class HashFunc< std::pair< double, long int > >
773  : public HashFuncCastKeyPair< double, long int >::type {};
774 
781  template < typename Type >
782  class HashFunc< RefPtr< Type > > : public HashFunc< unsigned int* > {
783  public:
789  Size operator()(const RefPtr< Type >& key) const;
790  };
791 
797  template <>
798  class HashFunc< std::string > : public HashFuncBase< std::string > {
799  public:
805  Size operator()(const std::string& key) const override;
806  };
807 
813  template <>
814  class HashFunc< std::pair< std::string, std::string > >
815  : public HashFuncBase< std::pair< std::string, std::string > > {
816  public:
822  Size operator()(const std::pair< std::string, std::string >& key) const;
823  };
824 
830  template <>
831  class HashFunc< std::vector< Idx > >
832  : public HashFuncBase< std::vector< Idx > > {
833  public:
839  Size operator()(const std::vector< Idx >& key) const;
840  };
841 
847  template <>
848  class HashFunc< Debug > : public HashFuncBase< Debug > {
849  public:
855  Size operator()(const Debug& key) const;
856  };
857 } /* namespace gum */
858 
860 #ifndef GUM_NO_INLINE
861 # include <agrum/core/hashFunc_inl.h>
862 #endif /* GUM_NO_INLINE */
863 
865 #include <agrum/core/hashFunc_tpl.h>
866 
867 #endif /* GUM_HASHFUNC_H */
typename HashFuncCastKey< T2 >::type Func2
The casting function for T2.
Definition: hashFunc.h:541
Inlined implementation of the basic hash functions.
unsigned long Size
In aGrUM, hashed values are unsigned long int.
Definition: types.h:50
Generic hash functions for keys castable as unsigned longs and whose size is precisely twice that of ...
Definition: hashFunc.h:365
static constexpr unsigned long gold
Definition: hashFunc.h:80
unsigned int _right_shift
The number of right shift to perform to get correct hashed values.
Definition: hashFunc.h:447
unsigned int _right_shift
The number of right shift to perform to get correct hashed values.
Definition: hashFunc.h:295
STL namespace.
Class providing aGrUM&#39;s "smart" pointers.
Class template representing hashing function of LpCol.
Definition: hashFunc.h:612
gum is the global namespace for all aGrUM entities
Definition: agrum.h:25
Generic hash functions for keys castable as unsigned longs whose size is either smaller than unsigned...
Definition: hashFunc.h:515
Generic hash functions for keys castable as unsigned longs and whose size is precisely that of unsign...
Definition: hashFunc.h:313
typename std::conditional< std::is_same< HASH_TYPE, FIRST_TYPE >::value, dummyHash< HASH_TYPE >, typename HashFuncConditionalType< HASH_TYPE, OTHER_TYPES... >::type >::type type
Definition: hashFunc.h:592
typename HashFuncCastKey< T1 >::type Func1
The casting function for T1.
Definition: hashFunc.h:538
typename std::conditional< std::is_same< HASH_TYPE, TYPE >::value, dummyHash< HASH_TYPE >, HASH_TYPE >::type type
Definition: hashFunc.h:563
Smart pointersaGrUM&#39;s smart pointers keep track of the number of times the value they point to is ref...
Definition: refPtr.h:114
unsigned int _right_shift
The number of right shift to perform to get correct hashed values.
Definition: hashFunc.h:404
static constexpr unsigned long mask
Definition: hashFunc.h:82
Func2 __func2
The functions used to hash Key2.
Definition: hashFunc.h:497
Template implementation of the basic hash functions.
Func1 __func1
The functions used to hash Key1.
Definition: hashFunc.h:495
static constexpr size_t offset
Definition: hashFunc.h:83
Constants for hash functions.
Definition: hashFunc.h:73
Generic hash functions for keys smaller than or equal to long integers.
Definition: hashFunc.h:210
unsigned int _right_shift
The number of right shift to perform to get correct hashed values.
Definition: hashFunc.h:491
unsigned int _right_shift
The number of right shift to perform to get correct hashed values.
Definition: hashFunc.h:353
Generic hash functions for pairs of keys whose sizes are precisely twice that of unsigned longs and w...
Definition: hashFunc.h:462
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...
typename std::conditional< sizeof(T)< sizeof(long), HashFuncSmallCastKey< T >, typename std::conditional< sizeof(T)==2 *sizeof(long), HashFuncLargeCastKey< T >, HashFuncMediumCastKey< T > >::type >::type type
The type used by this class.
Definition: hashFunc.h:522
Generic hash functions for keys castable as unsigned longs whose size is either smaller than unsigned...
Definition: hashFunc.h:536
All hash functions should inherit from this class.
Definition: hashFunc.h:150
This class enables to safely define hash functions for types that may or may not already has defined ...
Definition: hashFunc.h:552
unsigned int _right_shift
The number of right shift to perform to get correct hashed values.
Definition: hashFunc.h:242
Generic hash functions for keys castable as unsigned longs and whose size is strictly smaller than th...
Definition: hashFunc.h:254
Generic hash functions for pairs of, at most, two long integer keys.
Definition: hashFunc.h:418
static constexpr unsigned long pi
Definition: hashFunc.h:81
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