1 /* _________________________________________________________________________
2 *
3 * UTILIB: A utility library for developing portable C++ codes.
4 * Copyright (c) 2008 Sandia Corporation.
5 * This software is distributed under the BSD License.
6 * Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
7 * the U.S. Government retains certain rights in this software.
8 * For more information, see the README file in the top UTILIB directory.
9 * _________________________________________________________________________
10 */
11
12 /**
13 * \file hash_fn.h
14 *
15 * Defines commonly used hash functions
16 */
17
18 #ifndef utilib_hash_fn_h
19 #define utilib_hash_fn_h
20
21 #include <utilib/std_headers.h>
22 #include <utilib/ValuedContainer.h>
23 #include <utilib/BasicArray.h>
24 #include <utilib/CharString.h>
25
26 namespace utilib {
27
28 //
29 // Declarations for the Bob Jenkins hash function (which is quite good!)
30 //
31 /// unsigned 4-byte quantities
32 typedef unsigned long int ub4;
33 /// unsigned 1-byte quantities
34 typedef unsigned char ub1;
35 /// The Bob Jenkins hash function
36 ub4 bjlookup( ub1* k, ub4 length, ub4 level);
37
38 /// Hash a long int
39 inline unsigned long int hash_bj(const long int& val, unsigned long int level=0)
40 {return bjlookup((ub1*)&val,sizeof(long int),level);}
41
42 /// Hash a double
43 inline unsigned long int hash_bj(const double& val, unsigned long int level=0)
44 {return bjlookup((ub1*)&val,sizeof(double),level);}
45
46 /// Hash an integer
47 inline unsigned long int hash_bj(const int& val, unsigned long int level=0)
48 {return bjlookup((ub1*)&val,sizeof(int),level);}
49
50 /// Hash a vector of ints
51 inline unsigned long int hash_bj(const std::vector<int>& array,
52 unsigned long int level=0)
53 {return bjlookup((ub1*)(&(array[0])),array.size()*sizeof(int),level);}
54
55 /// Hash a BasicArray of ints
56 inline unsigned long int hash_bj(const BasicArray<int>& array,
57 unsigned long int level=0)
58 {return bjlookup((ub1*)(array.data()),array.size()*sizeof(int),level);}
59
60 /// Hash an array of ints
61 inline unsigned long int hash_bj(const int* array, const int arraylen,
62 unsigned long int level=0)
63 {return bjlookup((ub1*)(array),arraylen*sizeof(int),level);}
64
65 /// Hash a vector of doubles
66 inline unsigned long int hash_bj(const std::vector<double>& array,
67 unsigned long int level=0)
68 {return bjlookup((ub1*)(&(array[0])),array.size()*sizeof(double),level);}
69
70 /// Hash a BasicArray of doubles
71 inline unsigned long int hash_bj(const BasicArray<double>& array,
72 unsigned long int level=0)
73 {return bjlookup((ub1*)(array.data()),array.size()*sizeof(double),level);}
74
75 /// Hash an array of doubles
76 inline unsigned long int hash_bj(const double* array, const int arraylen,
77 unsigned long int level=0)
78 {return bjlookup((ub1*)(array),arraylen*sizeof(double),level);}
79
80
81
82 /// A default hash function declaration.
83 template <class T>
hash_fn(const T & key,size_type table_size)84 size_type hash_fn(const T& key, size_type table_size)
85 {return key.hash(table_size);}
86
87 /// Default hash function for BasicArray objects
88 template<class T>
hash_fn(const BasicArray<T> & key,size_type table_size)89 inline size_type hash_fn(const BasicArray<T>& key, size_type table_size)
90 {return hash_fn1(*((const BasicArray<T>*)&key),table_size);}
91
92 /// A default hash function for ValuedContainer objects
93 template <class V, class T>
hash_fn(const ValuedContainer<V,T> & key,size_type table_size)94 size_type hash_fn(const ValuedContainer<V,T>& key, size_type table_size)
95 {return hash_fn(key.info,table_size);}
96
97
98
99 /// Hash a CharString
100 size_type hash_fn1(const CharString& key, size_type table_size);
101 /// Hash a CharString
102 size_type hash_fn2(const CharString& key, size_type table_size);
103 /// Hash a CharString
104 size_type hash_fn3(const CharString& key, size_type table_size);
105 /// Default hash function for CharString objects
106 template<>
hash_fn(const CharString & key,size_type table_size)107 inline size_type hash_fn(const CharString& key, size_type table_size)
108 {return hash_fn3(key,table_size);}
109
110 /// Hash a string
111 size_type hash_fn3(const std::string& key, size_type table_size);
112 /// Default hash function for strings
113 template<>
hash_fn(const std::string & key,size_type table_size)114 inline size_type hash_fn(const std::string& key, size_type table_size)
115 {return hash_fn3(key,table_size);}
116
117 /// Hash an integer
118 size_type hash_fn1(const int& key, size_type table_size);
119 /// Hash an integer
hash_fn2(const int & key,size_type table_size)120 inline size_type hash_fn2(const int& key, size_type table_size)
121 {return hash_bj(key) % table_size;}
122 /// Default hash function for integers
123 template<>
hash_fn(const int & key,size_type table_size)124 inline size_type hash_fn(const int& key, size_type table_size)
125 {return hash_fn2(key,table_size);}
126
127 /// Hash a long integer
128 template<>
hash_fn(const long int & key,size_type table_size)129 inline size_type hash_fn(const long int& key, size_type table_size)
130 {return hash_bj(key) % table_size;}
131
132 /// Hash a double
133 size_type hash_fn1(const double& key, size_type table_size);
134 /// Hash a double
hash_fn2(const double & key,size_type table_size)135 inline size_type hash_fn2(const double& key, size_type table_size)
136 {return hash_bj(key) % table_size;}
137 /// Default hash function for doubles
138 template<>
hash_fn(const double & key,size_type table_size)139 inline size_type hash_fn(const double& key, size_type table_size)
140 {return hash_fn2(key,table_size);}
141
142 /// Hash a BasicArray of ints
143 size_type hash_fn1(const BasicArray<int>& key, size_type table_size);
144 /// Hash a BasicArray of ints
hash_fn2(const BasicArray<int> & key,size_type table_size)145 inline size_type hash_fn2(const BasicArray<int>& key, size_type table_size)
146 {return hash_bj(key) % table_size;}
147 /// Default hash function for BasicArray<int> objects
148 template<>
hash_fn(const BasicArray<int> & key,size_type table_size)149 inline size_type hash_fn(const BasicArray<int>& key, size_type table_size)
150 {return hash_fn2(key,table_size);}
151
152 /// Hash a BasicArray of doubles
153 size_type hash_fn1(const BasicArray<double>& key, size_type table_size);
154 /// Hash a BasicArray of doubles
155 size_type hash_fn2(const BasicArray<double>& key, size_type table_size);
156 /// Hash a BasicArray of doubles
hash_fn3(const BasicArray<double> & key,size_type table_size)157 inline size_type hash_fn3(const BasicArray<double>& key, size_type table_size)
158 {return hash_bj(key) % table_size;}
159 /// Default hash function for BasicArray<doubles> objects
160 template<>
hash_fn(const BasicArray<double> & key,size_type table_size)161 inline size_type hash_fn(const BasicArray<double>& key, size_type table_size)
162 {return hash_fn3(key,table_size);}
163
164 /// Hash a vector of doubles
165 size_type hash_fn1(const std::vector<int>& key, size_type table_size);
166 /// Hash a vector of doubles
hash_fn2(const std::vector<int> & key,size_type table_size)167 inline size_type hash_fn2(const std::vector<int>& key, size_type table_size)
168 {return hash_bj(key) % table_size;}
169 /// Default hash function for std::vector<int> objects
170 template<>
hash_fn(const std::vector<int> & key,size_type table_size)171 inline size_type hash_fn(const std::vector<int>& key, size_type table_size)
172 {return hash_fn2(key,table_size);}
173
174 /// Hash a vector of doubles
175 size_type hash_fn1(const std::vector<double>& key, size_type table_size);
176 /// Hash a vector of doubles
177 size_type hash_fn2(const std::vector<double>& key, size_type table_size);
178 /// Hash a vector of doubles
hash_fn3(const std::vector<double> & key,size_type table_size)179 inline size_type hash_fn3(const std::vector<double>& key, size_type table_size)
180 {return hash_bj(key) % table_size;}
181 /// Default hash function for std::vector<doubles> objects
182 template<>
hash_fn(const std::vector<double> & key,size_type table_size)183 inline size_type hash_fn(const std::vector<double>& key, size_type table_size)
184 {return hash_fn3(key,table_size);}
185
186 } // namespace utilib
187
188 #endif
189